C语言双向链表讲解

一、双向链表的概念

双向链表基于单链表。单链表是单向的，有一个头结点，一个尾结点，要访问任何结点，都必须知道头结点，不能逆着进行。而双链表添加了一个指针域，通过两个指针域，分别指向结点的前结点和后结点。这样的话，可以通过双链表的任何结点，访问到它的前结点和后结点。

在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点的地址，一般称为右链域；一个存储直接前驱结点地址，一般称之为左链域。

双向链表结构示意图

表头为空，表头的后继节点为"节点10"(数据为10的节点)；"节点10"的后继节点是"节点20"(数据为10的节点)，"节点20"的前继节点是"节点10"；"节点20"的后继节点是"节点30"，"节点30"的前继节点是"节点20"；...；末尾节点的后继节点是表头。

双链表删除节点

删除"节点30"
删除之前："节点20"的后继节点为"节点30"，"节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40"，"节点40" 的前继节点为"节点30"。
删除之后："节点20"的后继节点为"节点40"，"节点40" 的前继节点为"节点20"。

双链表添加节点

在"节点10"与"节点20"之间添加"节点15"
添加之前："节点10"的后继节点为"节点20"，"节点20" 的前继节点为"节点10"。
添加之后："节点10"的后继节点为"节点15"，"节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20"，"节点20" 的前继节点为"节点15"。

二、C语言实现双向链表

2.1 头文件

 #pragma once

 //新建双向链表。成功返回链表头，否则，返回NULL

 extern int create_dLink();

 //撤销双向链表，成功返回0，否则返回-1

 extern int destory_dLink();

 //双向列表是否为空，为空返回1，否则返回0

 extern int  is_empty_dLink();

 //双向链表的大小

 extern int dLink_size();

 //获取索引index位置的元素，成功返回节点指针，否则返回NULL

 extern  void* dLink_get(int index);

 //获取双向链表中第一个元素，成功返回节点指针，否则返回NULL

 extern void* dLink_getFirst();

 //获取双向链表中最后一个元素，成功返回节点指针，否则返回NULL

 extern void* dLink_getTail();

 /*

 链表中增加

 */

 //在Index位置插值value,成功返回0，否则返回-1；

 extern int dLink_insert(int index,void * pVal);

 //在表头插入值

 extern int dLink_insert_head(void *pVal);

 //在表尾插入值

 extern int dLink_insert_tail(void *pVal);

 /*

 链表中删除

 */

 //在index处删除

 extern int  dLink_delete(int index);

 //删除第一个节点

 extern int dLink_delete_first();

 //闪电湖第二个节点

 extern int dLink_delete_tail();

2.2 .c

 #include<stdio.h>

 #include "double_link.h"

 #include<malloc.h>

 //双向链表节点

 typedef struct My_node

 {

     struct My_node *prev;

     struct  My_node *pNext;

     void * p;

 }my_node;

 //b表头不存放元素值

 my_node *phead = NULL;

 //节点的个数

 int node_count = ;

 //创建节点，成功返回节点指针，否则，返回NULL

 my_node* create_node(void *pVal)

 {

     my_node *pnode = NULL;

     pnode = (my_node*)malloc(sizeof(My_node));

     if (!pnode)

     {

         printf("create pnode error\n");

         return NULL;

     }

     //默认的，pnode的前一节点和后一节点都指向他自己

     pnode->prev  = pnode->pNext = pnode;

     //节点的值为pVal

     pnode->p = pVal;

     return pnode;

 }

 //新建双向链表 成功返回0 否则返回-1

 int create_dLink()

 {

     phead = create_node(NULL);

     if (!phead)

         return -;

     //设置节点的个数

     node_count = ;

     return ;

 }

 int destory_dLink()

 {

     if (!phead)

     {

         printf("%s failed! dlink is null!\n", __func__);

          return -;

     }

     My_node*pnode = phead->pNext;

     my_node* ptmp = NULL;

     if (pnode!=phead)

     {

         ptmp = pnode;

         pnode = pnode->pNext;

         free(pnode);

     }

     free(phead);

     phead = NULL;

     node_count = ;

     return ;

 }

 int is_empty_dLink()

 {

     return node_count==;

 }

 int dLink_size()

 {

     return node_count;

 }

 //获取双向链表中第Index位置的节点

 my_node* get_node(int index)

 {

     if (index< || index >= node_count)

     {

         printf("%s failed ! index out of bound\n", __func__);

         return NULL;

     }

     //正向查找

     if (index <= (node_count / ))

     {

         int i = ;

         my_node *pnode = phead->pNext;

         while ((i++)<index)

         {

             pnode = pnode->pNext;

         }

         return pnode;

     }

     //反向查找

     int j = ;

     int rindex = node_count - index - ;

     my_node *rnode = phead->prev;

     while ((j++)<rindex)

     {

         rnode = rnode->prev;

     }

     return rnode;

 }

 void * dLink_get(int index)

 {

     my_node *pindex = get_node(index);

     if (!pindex)

     {

         printf("%s failed!\n", __func__);

         return NULL;

     }

     return pindex->p;

 }

 //获取第一个节点

 void * dLink_getFirst()

 {

     return get_node() ;

 }

 //获取最后一个节点

 void * dLink_getTail()

 {

     return get_node(node_count-);

 }

 //将值插入到index位置，成功返回0；否则 返回-1

 int dLink_insert(int index, void * pVal)

 {

     //插入表头

     if (index == )

         return dLink_insert_head(pVal);

     //获取要插入位置对应的节点

     my_node* pindex = get_node(index);

     if (!pindex)

         return -;

     //创建节点

     my_node* pnode = create_node(pVal);

     if (!pnode)

         return -;

     pnode->prev = pindex->prev;

     pnode->pNext = pindex;

     pindex->prev->pNext = pnode;

     pindex->prev = pnode;

     node_count++;

     return ;

 }

 //数值插入表头

 int dLink_insert_head(void * pVal)

 {

     my_node* pnode = create_node(pVal);

     if (!pnode)

         return -;

     pnode->prev = phead;

     pnode->pNext = phead->pNext;

     phead->pNext->prev = pnode;

     phead->pNext = pnode;

     node_count++;

     return ;

 }

 int dLink_insert_tail(void * pVal)

 {

     my_node* pnode = create_node(pVal);

     if (!pnode)

         return -;

     pnode->pNext = phead;

     pnode->prev = phead->prev;

     phead->prev->pNext = pnode;

     phead->prev = pnode;

     return ;

 }

 int dLink_delete(int index)

 {

     my_node* pindex = get_node(index);

     if (!pindex)

     {

         printf("%s failed! the index in out of bound\n",__func__);

         return -;

     }

     pindex->pNext->prev = pindex->prev;

     pindex->prev->pNext = pindex->pNext;

     free(pindex);

     node_count--;

     return ;

 }

 int dLink_delete_first()

 {

     return dLink_delete();

 }

 int dLink_delete_tail()

 {

     return dLink_delete(node_count-);

 }

2.3 test测试代码

 #include<stdio.h>

 #include"double_link.h"

 //1.双向链表操作数为int

 void int_test()

 {

     int arr[] = {,,,,,,,,,};

     printf("xxxxxxxxxxxxxxxxx\n");

     create_dLink();                    //创建链表

     dLink_insert(, &arr[]);        //双向链表表头插入

     dLink_insert(, &arr[]);        //双向链表表头插入

     dLink_insert(, &arr[]);        //双向链表表头插入

     dLink_insert(, &arr[]);        //双向链表表头插入

     dLink_insert(, &arr[]);        //双向链表表头插入

     dLink_insert(, &arr[]);        //双向链表表头插入

     printf("is_empty_dLink()=%d\n",is_empty_dLink());    //双向链表是否为空

     printf("dLink_size()=%d\n", dLink_size());                    //双向链表的大小

     //遍历双向链表

     int i ;

     int * p ;

     int sz = dLink_size();

     for ( i = ; i < sz; i++)

     {

         p = (int*)dLink_get(i);

         printf("dLink_get(%d)=%d\n",i,*p);

     }

     destory_dLink();

 }

 //2.操作数为字符串

 void string_test()

 {

     char* str[] = {"one","two","three","four","five"};

     create_dLink();                    //创建链表

     dLink_insert(, str[]);        //双向链表表头插入

     dLink_insert(, str[]);        //双向链表表头插入

     dLink_insert(, str[]);        //双向链表表头插入

     printf("is_empty_dLink()=%d\n", is_empty_dLink());    //双向链表是否为空

     printf("dLink_size()=%d\n", dLink_size());                    //双向链表的大小

                                                                 //遍历双向链表

     int i ;

     char * p ;

     int sz = dLink_size();

     for (i = ; i < sz; i++)

     {

         p = (char*)dLink_get(i);

         printf("dLink_get(%d)=%s\n", i, p);

     }

     destory_dLink();

 }

 //3.双向链表为结构体

 typedef struct MyStruct

 {

     int id;

     char name[];

 } stu;

 stu arr_stu[] =

 {

     {,"lii"},

     { ,"mike" },

     { ,"lucky" },

     { ,"eric" },

 };

 #define arr_stu_size  ((sizeof(arr_stu))/(sizeof(arr_stu[0])))

 void stuc_test()

 {

     create_dLink();                    //创建链表

     dLink_insert(, &arr_stu[]);        //双向链表表头插入

     dLink_insert(, &arr_stu[]);        //双向链表表头插入

     dLink_insert(, &arr_stu[]);        //双向链表表头插入

     printf("is_empty_dLink()=%d\n", is_empty_dLink());    //双向链表是否为空

     printf("dLink_size()=%d\n", dLink_size());                    //双向链表的大小

                                                                 //遍历双向链表

     int i ;

     stu * p ;

     int sz = dLink_size();

     for (i = ; i < sz; i++)

     {

         p = (stu*)dLink_get(i);

         printf("dLink_get(%d)=[%d,%s]\n", i, p->id,p->name);

     }

     destory_dLink();

 }

 int main()

 {

     int_test();

     string_test();

     stuc_test();

     return ;

 }

2.34结果显示

巴特西

C语言双向链表讲解

最新文章

热门文章