第三篇、C_双向链表（循环链表）

简介：

　　在用C/C++开发系统中，我们知道用数组或者单链表来开发，如果是数据比较大的话，性能很不好，效率也不高。因此常常需要考虑系统的实用性，常常采用双向链表来开发。

示例：

1.数据

typedef struct node{

　　int data;                // 数据

　　struct node *last;  // 前一个数据节点 

　　struct node *next;  // 后一个数据节点

}Node;

typedef struct {

　　Node *head;

　　Node *tail;

}LinkList;

2.创建链表

LinkList *createList()

{

    LinkList *list = malloc(sizeof(LinkList));

    list -> head = NULL;

    lsit ->tail = NULL;

    return list;

}

3.插入

　　3.1头插法

void addNodeBeHead(LinkList *list,int num)

{

    Node *p = malloc(sizeof(Node));

    p -> data = num;

    p -> last = NULL;

    P -> next = NULL;

    if(list - > head != NULL)

    {

        // 1.指向新的节点

      // 2.新节点的next指向原来的节点

        // 3.新节点变成头节点

        list ->head->last = p;

        node ->next = list ->head;

        list -> head = p;

    }

    else{

        list -> head = P;

        list -> tail = p;

    }

}

　　3.2尾插法

void addNodeAfterTail(LinkList *list,int num)

{

    Node *p = malloc(sizeof(Node));

    p -> data = num;

    p -> last = NULL;

    P -> next = NULL;

    if(list - > head != NULL)

    {

        // 1.指向新的节点

      // 2.新节点的last指向原来的节点

      // 3.新节点变成尾节点

      list ->tail->next = p;

        node ->last = list -> tail;

        list -> tail = p;

    }

    else{

        list -> head = P;

        list -> tail = p;

    }

}

4.打印链表

void printList(LinkList *list)

{

    Node *p = list -> head;

    if(p == NULL)

    {

        printf("当前为空链表")；

    }else

    {

        while(p != NULL)

        {

                printf("%s",p-> data);

                p = p-> next;

        }

    }

}

5.把链表的头结点删除，并返回头结点的数值

int popHeadNode(LinkList *list)

{

    if(list -> head == NULL)

    {

        printf("the list is empty!");

        return -;

    }

    else if (list -> head == list -> tail)

    {

        Node *node = list - > head;

        int value = node ->data;

        list -> head = NULL;

        list -> tail = NULL;

        free(node);

        return value;

    }

    else

    {

        Node *node = list -> head;

        int value = node -> data;

        // 1.head指向下一个节点

      // 2.并将下一个的last置空

        list -> head = list -> head ->next;

        list -> head -> last = NULL;

        free(node);

        return value;

    }

}

6.统计节点总数

int countNodes(LinkList *list)

{

    int count = ;

    Node *p = list -> head;

    if(list -> head != NULL)

    {

        while(p != NULL)

        {

            count++;

            p = p -> next;

        }

        return count;

    }

    return ;

}

7.链表转成数组(注意：数组一定要malloc初始化，否则无法返回)

int *listToArray(LinkList *list)

{

    if(list -> head == NULL)

    {

        return NULL;

    }

    int i = ;

    int n = countNodes(list);

    int *arr = malloc(sizeof(int) * n);

    Node *p = list -> head;

    while(p != NULL)

    {

        arr[i] = p -> data;

        i++;

        p = p -> next;

    }

        return arr;

}

8.把链表所有的节点头尾对调

1->2->3->NULL 对调后 NULL->3->2->1

void reverseList(LinkList *list)

{

    if(list -> head != NULL)

    {

        int *arr = listToArray(list);

        int i = countNodes(list) - ;

        Node *node = list -> head;

        while(p != NULL)

        {

            P -> data = arr[i];

            i --;

            p = p -> next;

        }

    }

}

第二种做法：（把原来的链表重新连接）

void reverseList(LinkList *list)

{

    Node *prev = NULL;

    Node *p = list -> head;

    Node *temp;

    list -> tail = p; //  尾部变头部
    while(p != NULL)

    {

        temp = p -> next;

        p -> next = prev;

        prev = p;

        p = temp;

    }

    list ->head = prev;

}

巴特西

第三篇、C_双向链表（循环链表）

最新文章

热门文章