数据结构之链表.ppt

SCIE,University of Electronic Science and Technology of China,1,2.1线性表,线性表不同的实现方式：2.1.1顺序表 数组存储 顺序表定义 顺序表基本操作：遍历、插入、删除 顺序表算法分析2.1.2单链表2.1.3双向链表 链接存储2.1.4循环链表,SCIE,University of Electronic Science and Technology of China,2,2.1线性表,#include stdio.h“struct list_seq int data20;int length;int main()struct list_seq list;int no,i;list.length=0;for(i=0;i10;i+)scanf(%d,SCIE,University of Electronic Science and Technology of China,3,2.1.2单链表,一、链表的引入数组结构的缺点:1、在插入、删除时要移动大量的节点2、表的大小固定。预先在申明数组时指定，无法更改原因：存放的连续性突破离散存放用指针来表示元素之间的关系。,SCIE,University of Electronic Science and Technology of China,4,2.1.2单链表,用链表实现线性表（非连续存储）,线性表元素：a1、a2、a3、a4.,链表链点,线性关系：,a1,a2,a3,a4,指针域，指针关系,a1,a2,a3,a4,顺序存储,链式存储,SCIE,University of Electronic Science and Technology of China,5,2.1.2单链表,二、链表的定义 链点,元素域,链接域,数据域（数据元素域）：存放一个数据元素。链接域（关系域）：存放指向下一个元素的指针元素间的关系。,数据域+链接域=结点（链点）,SCIE,University of Electronic Science and Technology of China,6,2.1.2单链表,链表,由链点及链点相互间的链接构成,head,链表头,链表尾,链表长度（节点数目）,SCIE,University of Electronic Science and Technology of China,7,2.1.2单链表,定义,struct node_typeelemtype data;struct node_type*next;,struct list_typenode_type*head;node_type*tail;int length;,链点的定义,链表的定义,data,next,8,2.1.2单链表,SCIE,University of Electronic Science and Technology of China,8,带头节点的单链表,head,带头节点链表的引入是为了使算法对空表和非空表的处理一致,普通单链表对链表尾的判断(假定p是链表尾的指针)空表：p=null;非空表：p-next=null;,带头节点单链表对链表尾的判断空表：p-next=null;非空表：p-next=null;,SCIE,University of Electronic Science and Technology of China,9,2.1.2单链表,初始化算法：elemtype initlist(node*h)*h=(node*)malloc(sizeof(node);(*h)-next=null;三、链表的基本操作访问插入删除,SCIE,University of Electronic Science and Technology of China,10,2.1.2单链表,访问操作问题描述：访问链表的第i个节点问题分析：输入：链表，i输出：链点指向链点的指针算法实现分析：,只能从链表头开始，一个一个“数”下去，直到第i个。,a1,an,head,a2,temp,temp,temp,SCIE,University of Electronic Science and Technology of China,11,2.1.2单链表,从自然语言到算法语言,如何描述我们找到第i个节点的动作。1、先找到链表首结点的地址2、通过“地址”，找到链点3、在链点中找到后继元素的“地址”4、记录这个地址,p=list-head;,p-data,p=p-next;,p-next,SCIE,University of Electronic Science and Technology of China,12,2.1.2单链表,继续完善描述1、先找到链表首结点的地址2、通过“地址”，找到链点3、在链点中找到后继元素的“地址”4、记录这个地址，回到2,p=list-head;,p-data,p=p-next;,p-next,计数，如果计数到i，就结束,counter=1;,counter+;,if(counter=i),break;,SCIE,University of Electronic Science and Technology of China,13,2.1.2单链表,node_type*get_node(list,i),while(counter next;,int counter;node_type*p;,return p;,if(p=NULL)return NULL;,p=list-head;counter=1;,p,逐个“数”的动作,counter：,1,2,3,设i 3,当in时算法结果怎样？,思考,SCIE,University of Electronic Science and Technology of China,14,2.1.2单链表,注意,1、p=p-next;,沿链表前进,2、循环结束条件,counter=i 或 node=NULL,counter list-length,思考,如果希望获得值为x的元素，如何实现？,while(p-data=x&p!=NULL),SCIE,University of Electronic Science and Technology of China,15,2.1.2单链表,链表插入操作问题描述：在元素ai前插入新的元素new_node;问题分析：输入：链表，location，x输出：插入新元素后的链表。算法实现分析,SCIE,University of Electronic Science and Technology of China,16,2.1.2单链表,a1,ai,an,head,ai-1,.,.,anew,SCIE,University of Electronic Science and Technology of China,17,2.1.2单链表,void insertl（list,new_node,location）,找到ai-1,执行插入动作,两个步骤：,ai-1-next=anew;,anew-next=ai;,SCIE,University of Electronic Science and Technology of China,18,2.1.2单链表,while(counter next;,void insertl（list,new_node,location）,找到ai-1,p-next=new_node;,new_node-next=,?,ai-1-next=anew;,anew-next=ai;,p,p list-header;counter=1,q,q=p-next;,q;,法一,SCIE,University of Electronic Science and Technology of China,19,2.1.2单链表,while(counter next;,void insertl（list,new_node,location）,new_node-next=p-next;,p-next=new_node;,p,p list-header;counter=1,法二,SCIE,University of Electronic Science and Technology of China,20,2.1.2单链表,void insertl（list,new_node,location）,while(counter next;,new_node-next=p-next;,p-next=new_node;,counter=1;p=list-head;初始化,list-length+;,边界情况：表首插入表尾插入,SCIE,University of Electronic Science and Technology of China,21,2.1.2单链表,list-head,new_node-next=a1;,list-head;,list-head=new_node;,SCIE,University of Electronic Science and Technology of China,22,2.1.2单链表,void insertl（list,new_node,location）,while(counter next;,new_node-next=p-next;,p-next=new_node;,counter=1;p=list-head;初始化,if(location=1),else,new_node=list-head;list-head=new_node;,list-length+;,边界情况：表首插入表尾插入,SCIE,University of Electronic Science and Technology of China,23,2.1.2单链表,list-head,注意当循环执行到表尾时p 的值为NULL（空）p-next是悬空的值,while(counter next;,new_node-next=p-next;,p-next=new_node;,p-next!=NULL),NULL,因此循环结束应以p-next=NULL为条件,当i 链表长度 时,会造成系统崩溃,表尾插入,SCIE,University of Electronic Science and Technology of China,24,2.1.2单链表,void insertl（list,new_node,location）,while(counter next!=NULL)counter=counter+1;p=p-next;,new_node-next=p-next;,p-next=new_node;,counter=1;p=list-head;,if(location=1),else,new_node-next=list-head;list-head=new_node;,list-length+;,SCIE,University of Electronic Science and Technology of China,25,2.1.2单链表,从插入算法中对链表操作的体会,1、链表操作往往从表头开始，逐个找到需要的链点2、链表操作的有向性 不能回退；3、链表指针小心使用，谨防丢失。4、不能访问空指针的成员5、插入过程没有进行链点内容进行搬移。,SCIE,University of Electronic Science and Technology of China,26,2.1.2单链表,链表的创建,参见教材P15,问题描述：根据输入的元素，生成一个链点，把它插入到链表头；逐个插入链点，形成链表,链表的删除操作问题描述：删除元素ai;问题分析：输入：链表，location输出：删除元素后的链表。算法实现分析,SCIE,University of Electronic Science and Technology of China,27,2.1.2单链表,a1,ai+1,an,head,ai-1,.,.,ai-1-next=ai-next;,即,ai-1-next=ai-1-next-next;,SCIE,University of Electronic Science and Technology of China,28,2.1.2单链表,找到ai-1,执行删除动作,ai-1-next=ai-1-next-next,void deletel（list,location）,注意，从链表上取下的链点ai-1需要挂在一个指针上，否则可能丢失,a1,ai+1,an,head,ai-1,.,.,temp,SCIE,University of Electronic Science and Technology of China,29,2.1.2单链表,void deletel（list,location）,while(counter next;,p-next=p-next-next;,counter=1;p=list-head;初始化,if(location=1),else,list-head=list-head-next;,list-length-;,从链表删除的链点，一般应该释放其空间,SCIE,University of Electronic Science and Technology of China,30,2.1.2单链表,注意:对被删除删除链点的处理往往需要要free（）,SCIE,University of Electronic Science and Technology of China,31,2.1.2单链表,四、链表的特点、操作的顺序性有平均次查找过程。、离散存放不受链表大小限制不进行链点内容的搬移查找操作：数组效率优于链表插入、删除操作：链表效率优于数组,SCIE,University of Electronic Science and Technology of China,32,2.1.2单链表,作业,教材74页第9题（用链表实现）、第10题,SCIE,University of Electronic Science and Technology of China,33,2.1.3 双向链表,特点：每一个链点包含两个指针，前趋指针后继指针,a1,head,N,a2,N,P,an,P,SCIE,University of Electronic Science and Technology of China,34,2.1.3双向链表,一、双向链表的定义,struct double_link_node_typestruct double_link_node_type*prior;struct double_link_node_type*next;elemtype data;,struct double_link_list_typedl_node_type*head;dl_node_type*tail;int length;,链点的定义,链表的定义,SCIE,University of Electronic Science and Technology of China,35,2.1.3双向链表,二、双向链表的插入操作,ai-1,ai,问题描述：在第i个元素前插入新元素,anew,2、anew-next=p;,1、p-prior-next=anew;,3、anew-prior=p-prior;,4、p-prior=anew;,可以有几种插入方法？,SCIE,University of Electronic Science and Technology of China,36,2.1.3双向链表,算法实现（略）找到ai执行插入操作体会插入操作有多种方式实现，步骤比较复杂双向链表的使用灵活，可进可退通过这个练习，加强链表指针操作的训练,SCIE,University of Electronic Science and Technology of China,37,2.1.3双向链表,三、双向链表的删除操作问题描述：删除第i个元素,ai-1,ai1,（1）,（2）,（3）,（1）当p在ai1处时,p-next-next-prior=p;,p-next=p-next-next,q=p-next,free(q),SCIE,University of Electronic Science and Technology of China,38,2.1.3双向链表,三、双向链表的删除操作问题描述：删除第i个元素,ai-1,ai1,（1）,（2）,（3）,（2）当p在ai处时,课堂作业请完成算法,（3）当p在ai+1处时,SCIE,University of Electronic Science and Technology of China,39,2.1.4循环链表,a1,ai+1,an,head,ai-1,.,.,将链表头尾相接,对循环链表的遍历可以从任何一个节点开始,SCIE,University of Electronic Science and Technology of China,40,2.1.4循环链表,作业：完成以下算法片段：1、删除双向链表的ai元素时，指针P现在指向ai元素。2、删除双向链表的ai元素时，指针P现在指向ai+1元素,