数据结构 C语言版 第2版 教学课件 ppt 李云清 杨庆红 揭安全 第03章_线性表（II）.ppt

数据结构,李云清 杨庆红 揭安全,高等学校精品课程,人民邮电出版社,（第2版）,数据结构,揭安全,江西省高等学校精品课程,E_mail: jieanquan@,江西师范大学计算机信息工程学院,第3章 线性表的链式存储,链式存储,单链表,带头结点的单链表,循环单链表,,,,双链表,链式栈,链式队列,线性表的存储方式除了常用的顺序存储外，采用链式方式存储也是一种常见的方式本章将介绍一般线性表的几种链式存储实现方式，如单链表、带头结点单链表、循环单链表、双链表以及特殊的线性表------栈和队列的链式存储实现3.1链式存储,数据结构的存储方式必须体现它的逻辑关系 在链式存储方式下，实现中除存放一个结点的信息外，还需附设指针，用指针体现结点之间的逻辑关系如果一个结点有多个后继或多个前驱，那么可以附设相应个数的指针，一个结点附设的指针指向的是这个结点的某个前驱或后继线性结构中，每个结点最多只有一个前驱和一个后继，这里暂且设定更关心它的后继，这样在存储时除了存放该结点的信息外，只要附设一个指针即可，该指针指向它的后继结点的存放位置每个结点的存储形式是：,例，数据的逻辑结构B=（K，R） 其中 K={k1,k2,k3,k4,k5} R={r} R={,,,} 是一个线性结构，它的链式存储如图所示,为了清晰，上图可以更简洁地用下图表示。

3.2 单链表,单链表是线性表链式存储的一种形式，其中的结点一般含有两个域，一个是存放数据信息的info域，另一个是指向该结点的后继结点的存放地址的指针域next一个单链表必须有一个首指针指向单链表中的第一个结点◎,,◎,,◎,数据域,指针域,…,节点,直观化的描述方法：,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名例如：若头指针名是head，则把链表称为表headhead,,(a) 非空表,head=NULL,(b) 非空表,3.2.2单链表的实现,单链表结构的C语言描述如下： // / 链表实现的头文件,文件名slnklist.h / // typedef int datatype; typedef struct link_node{ datatype info; struct link_node next; }node;,单链表几个基本操作的具体实现：,建立一个空的单链表 // / 函数功能:建立一个空的单链表 / / 函数参数:无 / / 函数返回值:指向node类型变量的指针 / / 文件名:slnklist.c,函数名:init() / // node init() /建立一个空的单链表/ { return NULL; } 算法3.1 建立一个空的单链表,输出单链表中各个结点的值 void display(node head) { node p; p=head; if(!p) printf(“\n单链表是空的！“); else { printf(“\n单链表各个结点的值为:\n“); while(p) { printf(“%5d“,p-info);p=p-next;} } } 算法3.2输出单链表中各个结点的值,在单链表中查找一个值为x的结点 node find(node head,int i) { int j=1; node p=head; if(inext;j++; } return p; } 算法3.3 在单链表中查找一个值为x的结点,单链表的插入过程见下图所示 ：,,(2) head=p;,(1),(1) p-next=head;,(a) 在单链表的最前面插入一个值为x的新结点,单链表的插入过程见下图所示 ：,,∧,,,,,,head,(2),,(2) head=p;,(a) 在单链表的最前面插入一个值为x的新结点,(1),(1) p-next=head;,单链表的插入过程见下图所示 ：,,(b) 在q所指的结点后插入一个p所指的值为x的新结点,(1) p-next=q-next;,(1),单链表的插入过程见下图所示 ：,head,,,,,,(b) 在q所指的结点后插入一个p所指的值为x的新结点,(1) p-next=q-next;,p,q,(2) q-next=p;,(1),(2),// / 函数功能:单链表第i个结点后插入值为x的新结点 / / 函数参数:指向node类型变量的指针head / / datatype 类型变量x,int型变量I / / 函数返回值:指向node类型变量的指针 / / 文件名:slnklist.c,函数名:insert() / // node insert(node head,datatype x,int i) { node p,q; q=find(head,i); /查找第i个结点/ if(!q /设置新结点/,if(i==0){ /* 插入的结点作为单链表的第一个结点*/ p-next=head; /插入(1)/ head=p; /插入(2)/ } else { p-next=q-next; /插入(1)/ q-next=p; /插入(2)/ } } return head; } 算法3.4 在单链表中第i个结点后插入一个值为x的新结点,删除操作见下图所示：,∧,,,,,,,head,(1) head=head-next;,(a) 删除单链表的最前面的（第一个）结点,(2) free(p),,删除操作见下图所示：,∧,,,,,head,(1) head=head-next;,(a) 删除单链表的最前面的（第一个）结点,(2) free(p),(b) 删除p指向的结点，pre为p的前驱结点,(1) pre-next=p-next;,head,,,,(b) 删除p指向的结点，pre为p的前驱结点,(1) pre-next=p-next;,head,,,(1),(b) 删除p指向的结点，pre为p的前驱结点,(1) pre-next=p-next;,head,,pre,,(1),(2) free(p),// / 函数功能:在单链表中删除一个值为x的结点 / / 函数参数:指向node类型变量的指针head / / datatype 类型变量x / / 函数返回值:指向node类型变量的指针 / / 文件名:slnklist.c,函数名:dele() / // node dele(node head,datatype x) { node pre=NULL,p; if(!head) {printf(“单链表是空的！“);return head;} p=head; while(p /删除(1)/,else pre-next=p-next; free(p); return head; } 算法3.5 在单链表中删除一个值为x的结点,链式存储的插入和删除操作比顺序存储方便，但不能随机访问某个结点！,3.3 带头结点单链表,3.3.1带头结点单链表,带头结点单链表见下图所示：,3.3.2带头结点单链表的实现,一般的单链表中，第一个结点由head指示，而在带头结点单链表中，head指示的是所谓的头结点，它不是存储数据结构中的实际结点，第一个实际的结点是head-next指示的。

在带头结点单链表的操作实现时要注意这一点node init() { node head; head=(node)malloc(sizeof(node)); head-next=NULL; return head; } 算法3.6 建立一个空的带头结点的单链表,void display(node head) { node p; p=head-next; /从第一个（实际）结点开始/ if(!p) printf(“\n带头结点的单链表是空的!“); else { printf(“\n带头结点的单链表各个结点的值为:\n“); while(p) { printf(“%5d“,p-info);p=p-next;} } } 算法3.7 输出带头结点的单链表中各个结点的值,// / 函数功能:在带头结点的单链表中查找第i个结点地址 / / 函数参数:指向node类型变量的指针head / / int类型变量i / / 函数返回值:指向node类型变量的指针head / / 文件名hlnklist.c,函数名find() / // node find(node head,int i) { int j=0; node p=head; if(i0){printf(“\n带头结点的单链表中不存在第%d个结点！“,i);return NULL;} else if(i==0) return p; /*此时p指向的是头结点*/,while(p /返回结果,i=0时,p指示的是头结点/ } 算法3.8 在带头结点的单链表中查找第i个结点,带头结点单链表的插入过程见图3.7 ：,带头结点的单链表的插入操作的具体实现见算法3.9。

// / 函数功能:在带头结点的单链表中第i个结点后插入一个值为x的新结点 / / 函数参数:指向node类型变量的指针head / / datatype 类型变量x,int型变量i / / 函数返回值:指向node类型变量的指针head / / 文件名:hlnklist.c,函数名:insert() / // node insert(node head,datatype x,int i) { node p,q; q=find(head,i); /查找带头结点的单链表中的第i个结点/ /i=0,表示新结点插入在头结点之后,此时q指向的是头结点/,if(!q) /没有找到/ { printf(“\n带头结点的单链表中不存在第%d个结点！不能插入%d！“,i,x);return head;} p=(node)malloc(sizeof(node)); /为准备插入的新结点分配空间/ p-info=x; /为新结点设置值x/ p-next=q-n。