Wendy_Jacky
// main.c -- 双向循环链表，带头结点
#include <stdio.h>
#include <stdlib.h>
typedef char ElemType;
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
} DuLNode, *DuLinkList;
#define NUM 26
int InitList(DuLinkList *L, int n);
void TraverseList(DuLinkList L, int i);
void DestroyList(DuLinkList *L);
int main(int argc, char const *argv[])
{
DuLinkList L = NULL;
InitList(&L, NUM);
printf("L = 0x%x\n", L);
// printf("%c\n", L->data);
TraverseList(L, 3);
printf("L = 0x%x\n", L);
// printf("%c\n", L->data);
DestroyList(&L);
printf("L = 0x%x\n", L);
printf("\nBye!\n");
return 0;
}
int InitList(DuLinkList *L, int n)
{
int i;
DuLinkList p;// 保存尾结点
DuLinkList q;// 保存每次新建的结点
*L = (DuLinkList)malloc(sizeof(DuLNode));
if (!(*L))
{
return 0;
}
(*L)->data = '#';
(*L)->prior = (*L)->next = NULL;
p = *L;
for (i = 0; i < n; ++i)
{
q = (DuLinkList)malloc(sizeof(DuLNode));
if (!q)
{
return 0;
}
q->data = 'A' + i;
q->prior = p;
q->next = p->next;
p->next = q;
p = q;
}
// +---+ +---+ +---+ +---+ +---+ +---+
// NULL <- | P | <- | P | <- | P | <- | P | <- | P | <- | P |
// | | | A | | B | |...| | Y | | Z |
// | N | -> | N | -> | N | -> | N | -> | N | -> | N | -> NULL
// +---+ +---+ +---+ +---+ +---+ +---+
// *L p
if ((*L)->next != NULL)
{
(*L)->next->prior = p;
p->next = (*L)->next;
}
// ___________________________________
// ↑ ↓
// +---+ +---+ +---+ +---+ +---+ +---+
// NULL <- | P | | P | <- | P | <- | P | <- | P | <- | P |
// | | | A | | B | |...| | Y | | Z |
// | N | -> | N | -> | N | -> | N | -> | N | -> | N |
// +---+ +---+ +---+ +---+ +---+ +---+
// ↑___________________________________↓
// *L p
return 1;
}
void TraverseList(DuLinkList L, int i)
{
int j;
DuLinkList p;
if (!L)
{
return;
}
if (L->next == NULL)
{
return;
}
p = L->next;
if (i > 0)
{
do
{
p = p->next;
} while (--i);
}
if (i < 0)
{
do
{
p = p->prior;
} while (++i);
}
for (j = 0; j < NUM; ++j)
{
printf("%c ", p->data);
p = p->next;
}
printf("\n");
}
void DestroyList(DuLinkList *L)
{
// DuLinkList head = (*L)->next;
// DuLinkList p = (*L)->next;
// DuLinkList q;
// do
// {
// q = p->next;
// printf("free %c ", p->data);
// free(p);
// p = q;
// } while (p != head);
// printf("free %c\n", (*L)->data);
// free(*L);
// *L = NULL;
DuLinkList rear;
DuLinkList p;
if ((*L)->next != NULL)
{
rear = (*L)->next->prior;
while ((*L) != rear)
{
p = (*L)->next;
printf("free %c ", (*L)->data);
free(*L);
*L = p;
}
}
printf("free %c\n", (*L)->data);
free(*L);
*L = NULL;
}