数据结构之双向链表C源代码

数据结构双向链表实现源代码—鲁天伟

玩转算法与数据结构之双向链表 —HIT2000鲁天伟

前面我们讲了单链表，那么双向链表的理解就简单多了。

双向链表，就是从头结点能找到尾，也可从尾结点找到头，对于中间的结点，即可以找到它的前向结点，又可以找到它的后向结点，了解了这个会方便我们后面理解树和图的数据结构。

定义结构体如下：

struct dualList{ /*链表的数据结构定义*/ struct dualList * back; /*定义结点前向指针*/ int data; /*结点所包含的数据*/ struct dualLlist * next; /*定义结点的后向指针*/ };

typedef struct dualList listNode; /*链表结点结构体类型别名定义*/ typedef ListNode * link; /*链表结点结构体地址类型别名定义*/

下面作个小程序，对双向链表有个直观的认识：

#include #include

struct dualList{ /*链表的数据结构定义*/ struct dualList * back; /*定义结点前向指针*/ int data; /*定义结点数据*/ struct dualList * next; /*定义结点后向指针*/ };

typedef struct dualList listNode; /*链表结点结构体类型别名定义*/ typedef listNode * link; /*链表结点结构体地址类型别名定义*/

link head=NULL;

/*===从头插入===*/

link insertListhead(link head,int data){ link newNode=(link)malloc(sizeof(listNode)); newNode->data=data; newNode->back=NULL; newNode->next=NULL; if(head==NULL){ head=newNode; } else{

newNode->next=head; head->back=newNode; head=newNode;

数据结构双向链表实现源代码—鲁天伟

}

return head; }

/*===建立双向链表===*/

link createList(link head,int *nodelist,int len){ int i;

for(i=0;i

head=insertListhead(head,nodelist[i]); /*头部插入建表*/ return head; }

/*===打印双向链表===*/

void printList(link head){ link p=NULL; if(head==NULL)

printf(\); else{ p=head;

while(p!=NULL){

printf(\,p->back,p->data,p->next); p=p->next; } }

printf(\); }

/*===释放双向链表===*/

void freeList(link head){ link p=NULL; link q=NULL; p=head;

while(p!=NULL){ q=p; p=p->next; free(q); } }

void main(){ int select; int a,b;

int data[6]={2,3,4,1,56,23}; link head=NULL;

数据结构双向链表实现源代码—鲁天伟

head=createList(head,data,6); printList(head); getch(); }

一次执行的结果：

[0 23 136256] [136288 56 136224] [136256 1 136192] [136224 4 136160] [136192 3 136128] [136160 2 0]

图形化展示如下：

如上示例清晰的展现了，每个结点内存有的值。比如含有数据1的第三个结点，这个结点中的前向指针的值是136256,是第二个结点的内存地址，后向指针136192是第四个结点的内存地址。如何验证地址是否正确呢，注意看第二个结点的后向指针与第四个结点的前向指针的值都是136224，这个136224是第三个结点的地址。注意指针变量里的值就是所指向数据（基本数据类型或自定义结构体型数据）的地址。这一点要准确把握，就不难学习了。

附可执行原创双向链表源代码，实现链表的建立，头部增加结点，尾部增加结点，中部增中结点，删除指定结点，打印链表，释放链表内存的操作。

/*====================begin===========================*/

/*程序名称:dualList.c */ /*功能:双向链表的建立,插入,删除,释放 */ /*author:HIT2000 软件学院 鲁天伟 微信同电话:13701456199 */

#include #include

struct list{ /*链表的数据结构定义*/ struct list * back; int data;

struct list * next; };

typedef struct list listNode; /*链表结点结构体类型别名定义*/ typedef listNode * link; /*链表结点结构体地址类型别名定义*/