数据结构4ppt课件.ppt

《数据结构4ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构4ppt课件.ppt（19页珍藏版）》请在三一办公上搜索。

1、（第三讲）,绍兴文理学院,计算机系计算机应用教研室,数据结构,如何把一批数据“链”起来？,22:16,第2章 线性表（2）,一、教学目的：明确线性表的链式存储结构；掌握单链表、循环链表和双向链表的结构定义和基本操作；算法设计训练。,二、教学重点：线性表的链式存储结构；单链表的结构定义和基本操作；算法设计。,三、教学难点：单链表的基本操作；算法设计。四、教学过程：,n个结点链接成一个链表,数据元素(数据域)+指示后继元素存储位置(指针域(指针、链)=数据元素的存储映象,-结点,-线性表的链式存储结构,链表的每个结点中只包含一个指针域,线性链表、单链表,顺序表的优缺点 无须为表示节点间的逻辑关系而

2、增加额外的存储空间。可以方便的随机存取表中的任一结点。插入和删除运算不方便。由于要求占用连续的存储空间，存储分配只能预先进行。2.3.1 单链表的定义和表示(1)概念 用一组地址任意的存储单元存放线性表中的数据元素。,2.3 线性表的链式表示和实现,22:16,(2)线性表及其链式存储结构,线性表(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)链式存储结构为：,存储地址 数据域 指针域,头指针 31,1 LI 43,7 QIAN 13,13 SUN 1,19 WANG NULL,25 WU 37,31 ZHAO 7,37 ZHENG 19,43 ZHOU 25,22:

3、16,线性链表可表示为：,(3)单链表存储结构 typedef struct lnode elemtype data;struct lnode*next;lnode,*linklist;,(4)带头结点的单链表,22:16,2.3.2 单链表基本操作的实现,1、动态链表的建立(1)算法思想 设：链表的结点结构为：typedef struct nodechar data;node*next;*linklist;首先要建立一个只有头结点的空链表L，可调用算法initlist_l完成，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾结点。初始时，r与L均指向头结点。每读入一个数据元素则申

4、请一个新结点，将新结点插入到尾结点r之后，然后使r指向新的尾结点。当输入*时结束，*不是元素。,22:16,(2)算法2.11 后插法创建单链表及其演示,void createlist_l(linklist l)/输入若干个元素的值，后插/法建立带表头结点的单链表,22:16,int initlist_l(linklist&l)/生成新结点作为头结点，/用头指针l指向头结点,L,r,return 1;,l=new node;,l-next=NULL;,linklist p,r;char ch;,r=l;,p,p-next=NULL;,cinch;,while(ch!=*)p=new node;

5、,p-data=ch;,a,r-next=p;,r=p;,cinch;,p=new node;,e,b,p-data=ch;,p-next=NULL;,r-next=p;,r=p;,cinch;,p=new node;,p-data=ch;,c,p-next=NULL;,r-next=p;,r=p;,cinch;,p=new node;,p-data=ch;,d,p-next=NULL;,r-next=p;,r=p;,cinch;,p=new node;,p-data=ch;,p-next=NULL;,r-next=p;,r=p;,cinch;,算法2.11 后插法创建单链表 S3_1,(3)

6、算法2.11 前插法创建单链表及其演示,void createlist_l(linklist l)/输入若干个元素的值，后插/法建立带表头结点的单链表,22:16,int initlist_l(linklist&l)/生成新结点作为头结点，/用头指针l指向头结点,L,return 1;,l=new node;,l-next=NULL;,linklist p,char ch;,p-next=l-next;,cinch;,while(ch!=*)p=new node;,p-data=ch;,a,l-next=p;,cinch;,e,b,c,p,算法2.10 前插法创建单链表 S3_2,p=new

7、node;,p-data=ch;,d,p-next=l-next;,l-next=p;,cinch;,p=new node;,p-data=ch;,p-next=l-next;,l-next=p;,cinch;,p=new node;,p-data=ch;,p-next=l-next;,l-next=p;,cinch;,p=new node;,p-data=ch;,p-next=l-next;,l-next=p;,cinch;,2、查找,(1)算法2.6 在带头结点的单链表l中查找第i个元素int getelem_l(linklist l,int i,char,22:16,算法 2.6 在带头

8、结点的单链表l中查找第i个元素 S3_3,算法的时间复杂度为(n),(2)算法2.7 在带头结点的单链表l中查找值为e的元素,linklist locateelem_l(linklist l,char e)linklist p;p=l-next;while(p,22:16,算法2.7 在带头结点的单链表l中查找值为e的元素 S3_4,int listinsert_l(linklist l,int i,char e)linklist p=l,s;int j=0;while(p,3、插入,22:16,算法2.8 将值为e的新结点插入到单链表的第i个结点的位置上 S3_5,s=new node;,r

9、eturn 1;,x,s-data=e;,s-next=p-next;,p-next=s;,算法的时间复杂度为(n),对单链表的操作，其关键是不能使单链表断链。对于插入操作，要抓住插入位置前的一个结点。算法2.8 将值为e的新结点插入到单链表的第i个结点的位置上,int listdelete_l(linklist l,int i,char,4、删除,22:16,算法2.8 在单链表l中，删除第i个元素，并由e返回其值 S3_6,算法的时间复杂度为(n),同样，对于在单链表中删除结点的操作，也要抓住删除位置前的一个结点。算法2.9 在单链表l中，删除第i个元素，并由e返回其值,return 1;

10、,q=p-next;,p-next=q-next;,e=q-data;delete q;,22:16,即 p-nextL,最后一个结点的指针域的指针又指回第一个结点的链表。,？,2.3.3 循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,有时候，在循环链表中设立尾指针而不设头指针，可使某些操作简化。例如，将两个线性表合并成一个表的操作：,p=B-next-next;B-next=A-next;A-next=p；,22:16,1、概念 每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。若干个这样的结点组成的

11、链表称双向链表。,存储后继结点的地址,存储前趋结点的地址,2.3.4 双向链表,2、双向链表的存储结构typedef struct dulnode ElemType data;dulnode*prior;dulnode*next;dulnode,*dulinklist;,22:16,3、双向链表图示,4、操作特点,“查询”和单链表相同。“插入”和“删除”时需要同时修改两个方向上的指针。,(a)空双向循环链表,L-next=L,(b)双向循环链表,22:16,s-next=p-next;p-next=s;s-next-prior=s;s-prior=p;,p,s,插入,删除,p-next=p-next-next;p-next-prior=p;,p,22:16,有关算法实现作为阅读材料。,五、作业：,1、书面作业：p41 1中(4)(8)、(11)(15)2、上机编程：(数据结构编程练习)中 p43 2中(6)(8806)、(7)(8807)、(1)(8801)、(2)(8802),？,