2022年C语言双向链表 .pdf
链表的 C 语言实现之循环链表及双向链表一、循环链表循环链表是与单链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。循环链表的运算与单链表的运算基本一致。所不同的有以下几点：1、在建立一个循环链表时，必须使其最后一个结点的指针指向表头结点，而不是象单链表那样置为NULL。此种情况还使用于在最后一个结点后插入一个新的结点。2、在判断是否到表尾时，是判断该结点链域的值是否是表头结点，当链域值等于表头指针时，说明已到表尾。而非象单链表那样判断链域值是否为NULL。二、双向链表双向链表其实是单链表的改进。当我们对单链表进行操作时，有时你要对某个结点的直接前驱进行操作时，又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域，那么能不能定义一个既有存储直接后继结点地址的链域，又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢？这就是双向链表。在双向链表中，结点除含有数据域外，还有两个链域，一个存储直接后继结点地址，一般称之为右链域；一个存储直接前驱结点地址，一般称之为左链域。在c 语言中双向链表结点类型可以定义为：typedef struct node int data;/*数据域*/struct node*llink,*rlink;/*链域，*llink 是左链域指针，*rlink 是右链域指针*/JD;当然，也可以把一个双向链表构建成一个双向循环链表。双向链表与单向链表一样，也有三种基本运算：查找、插入和删除。双向链表的基本运算：1、查找假若我们要在一个带表头的双向循环链表中查找数据域为一特定值的某个结点时，我们同样从表头结名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 9 页 -点往后依次比较各结点数据域的值，若正是该特定值，则返回指向结点的指针，否则继续往后查，直到表尾。下例就是应用双向循环链表查找算法的一个程序。#include stdio.h#include malloc.h#define N 10 typedef struct node char name20;struct node*llink,*rlink;stud;stud*creat(int n)stud*p,*h,*s;int i;if(h=(stud*)malloc(sizeof(stud)=NULL)printf(不能分配内存空间!);exit(0);h-name0=0;h-llink=NULL;h-rlink=NULL;p=h;for(i=0;i n;i+)if(s=(stud*)malloc(sizeof(stud)=NULL)printf(不能分配内存空间!);exit(0);p-rlink=s;printf(请输入第%d 个人的姓名,i+1);scanf(%s,s-name);s-llink=p;s-rlink=NULL;p=s;h-llink=s;p-rlink=h;名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 9 页 -return(h);stud*search(stud*h,char*x)stud*p;char*y;p=h-rlink;while(p!=h)y=p-name;if(strcmp(y,x)=0)return(p);else p=p-rlink;printf(没有查找到该数据!);void print(stud*h)int n;stud*p;p=h-rlink;printf(数据信息为：n);while(p!=h)printf(%s,&*(p-name);p=p-rlink;printf(n);main()int number;char studname20;stud*head,*searchpoint;number=N;clrscr();head=creat(number);print(head);printf(请输入你要查找的人的姓名:);scanf(%s,studname);searchpoint=search(head,studname);名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 9 页 -printf(你所要查找的人的姓名是:%s,*&searchpoint-name);2、插入对于双向循环链表，我们现在可以随意地在某已知结点p 前或者 p 后插入一个新的结点。假若 s,p,q 是连续三个结点的指针，若我们要在p 前插入一个新结点r，则只需把 s 的右链域指针指向r，r 的左链域指针指向s，r 的右链域指针指向p，p 的左链域指针指向r 即可。在 p,q 之间插入原理也一样。下面就是一个应用双向循环链表插入算法的例子：#include stdio.h#include malloc.h#include string.h#define N 10 typedef struct node char name20;struct node*llink,*rlink;stud;stud*creat(int n)stud*p,*h,*s;int i;if(h=(stud*)malloc(sizeof(stud)=NULL)printf(不能分配内存空间!);exit(0);h-name0=0;h-llink=NULL;h-rlink=NULL;p=h;for(i=0;i n;i+)if(s=(stud*)malloc(sizeof(stud)=NULL)printf(不能分配内存空间!);exit(0);名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 9 页 -p-rlink=s;printf(请输入第%d 个人的姓名,i+1);scanf(%s,s-name);s-llink=p;s-rlink=NULL;p=s;h-llink=s;p-rlink=h;return(h);stud*search(stud*h,char*x)stud*p;char*y;p=h-rlink;while(p!=h)y=p-name;if(strcmp(y,x)=0)return(p);else p=p-rlink;printf(没有查找到该数据!);void print(stud*h)int n;stud*p;p=h-rlink;printf(数据信息为：n);while(p!=h)printf(%s,&*(p-name);p=p-rlink;printf(n);void insert(stud*p)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 9 页 -char stuname20;stud*s;if(s=(stud*)malloc(sizeof(stud)=NULL)printf(不能分配内存空间!);exit(0);printf(请输入你要插入的人的姓名:);scanf(%s,stuname);strcpy(s-name,stuname);s-rlink=p-rlink;p-rlink=s;s-llink=p;(s-rlink)-llink=s;main()int number;char studname20;stud*head,*searchpoint;number=N;clrscr();head=creat(number);print(head);printf(请输入你要查找的人的姓名:);scanf(%s,studname);searchpoint=search(head,studname);printf(你所要查找的人的姓名是:%sn,*&searchpoint-name);insert(searchpoint);print(head);3、删除删除某个结点，其实就是插入某个结点的逆操作。还是对于双向循环链表，要在连续的三个结点s,p,q中删除 p 结点，只需把s 的右链域指针指向q，q 的左链域指针指向s，并收回 p 结点就完成了。下面就是一个应用双向循环链表删除算法的例子：#include#include#include#define N 10 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 9 页 -typedef struct node char name20;struct node*llink,*rlink;stud;stud*creat(int n)stud*p,*h,*s;int i;if(h=(stud*)malloc(sizeof(stud)=NULL)printf(不能分配内存空间!);exit(0);h-name0=0;h-llink=NULL;h-rlink=NULL;p=h;for(i=0;i n;i+)if(s=(stud*)malloc(sizeof(stud)=NULL)printf(不能分配内存空间!);exit(0);p-rlink=s;printf(请输入第%d 个人的姓名,i+1);scanf(%s,s-name);s-llink=p;s-rlink=NULL;p=s;h-llink=s;p-rlink=h;return(h);stud*search(stud*h,char*x)stud*p;char*y;p=h-rlink;while(p!=h)名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 9 页 -y=p-name;if(strcmp(y,x)=0)return(p);else p=p-rlink;printf(没有查找到该数据!);void print(stud*h)int n;stud*p;p=h-rlink;printf(数据信息为：n);while(p!=h)printf(%s,&*(p-name);p=p-rlink;printf(n);void del(stud*p)(p-rlink)-llink=p-llink;(p-llink)-rlink=p-rlink;free(p);main()int number;char studname20;stud*head,*searchpoint;number=N;clrscr();head=creat(number);print(head);printf(请输入你要查找的人的姓名:);scanf(%s,studname);searchpoint=search(head,studname);printf(你所要查找的人的姓名是:%sn,*&searchpoint-name);del(searchpoint);名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 9 页 -print(head);名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 9 页 -
