用C语言编写一个算法

Question

建立一个循环单链表，其节点有prior，data和next三个域，其中data为数据域，存放元素的有效信息，next为指针域，指向后继节点，prior为指针域，它的值为NULL。编写一个算法将此表改为循环双链表。

Answer 1

// 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; }