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