（第三讲）（第三讲）绍兴文理学院绍兴文理学院计算机系计算机应用教研室计算机系计算机应用教研室TKSTKS2 2如何把一批数据如何把一批数据“链链”起来？起来？09:53 第第2 2章章 线性表（线性表（2 2）一一、教教学学目目的的：明明明明确确确确线线线线性性性性表表表表的的的的链链链链式式式式存存存存储储储储结结结结构构构构；掌掌掌掌握握握握单单单单链链链链表表表表、循循循循环环链链链链表表表表和和和和双双双双向向向向链链链链表表表表的的的的结结结结构构构构定定定定义义义义和和和和基基基基本本本本操操操操作作作作；算算算算法法法法设设设设计训练。计训练。计训练。计训练。二二、教教学学重重点点：线线线线性性性性表表表表的的的的链链链链式式式式存存存存储储储储结结结结构构构构；单单单单链链链链表表表表的的的的结结结结构构构构定义和基本操作；定义和基本操作；定义和基本操作；定义和基本操作；算法设计。算法设计。算法设计。算法设计。三、教学难点：三、教学难点：单链表的基本操作；算法设计。单链表的基本操作；算法设计。单链表的基本操作；算法设计。单链表的基本操作；算法设计。四、教学过程：四、教学过程： n n个结点链接成一个个结点链接成一个链表链表 数据元素数据元素( (数据域数据域) )+ +指示后继元素存储位置指示后继元素存储位置( (指针域指针域( (指针指针、链链) = =数据元素的存储映象数据元素的存储映象- 结点结点 - 线性表的链式存储结构线性表的链式存储结构 链表的每个结点中只包含一个指针域链表的每个结点中只包含一个指针域线性链表线性链表、单链表单链表 顺序表的优缺点顺序表的优缺点 无须为表示节点间的逻辑关系而增加额外的存储空间。无须为表示节点间的逻辑关系而增加额外的存储空间。 可以方便的随机存取表中的任一结点。可以方便的随机存取表中的任一结点。 插入和删除运算不方便。插入和删除运算不方便。 由于要求占用连续的存储空间，存储分配只能预先进行。由于要求占用连续的存储空间，存储分配只能预先进行。2.3.1 2.3.1 单链表的定义和表示单链表的定义和表示(1) (1) 概念概念 用一组地址用一组地址任意的任意的存储单元存放线性表中的存储单元存放线性表中的数据元素数据元素。 2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现TKSTKS4 409:53 (2) (2) 线性表及其链式存储结构线性表及其链式存储结构 线性表线性表(ZHAO(ZHAO，QIANQIAN，SUNSUN，LILI，ZHOUZHOU，WUWU，ZHENGZHENG，WANG)WANG) 链式存储结构链式存储结构为：为： 存储地址存储地址 数据域数据域 指针域指针域头指针头指针 3131 1 1 LI LI 4343 7 7 QIAN QIAN 1313 1313 SUN SUN 1 1 1919 WANG WANG NULLNULL 2525 WU WU 3737 3131 ZHAO ZHAO 7 7 3737 ZHENG ZHENG 1919 4343 ZHOU ZHOU 2525TKSTKS5 509:53 线性链表可表示线性链表可表示为：为： ZHAOZHAO QIANQIAN SUN SUN LI LI ZHOU ZHOU WU WU ZHENG ZHENG WANG WANG H H(3)(3) 单链表存储结构单链表存储结构 typedeftypedef structstruct lnodelnode elemtypeelemtype data; data; structstruct lnodelnode *next; *next; lnodelnode,*,*linklistlinklist; ; data nextdata next(4) (4) 带头结点的单链表带头结点的单链表 a a1 1 a a2 2a an nL LL L TKSTKS6 609:53 2.3.2 2.3.2 单链表基本操作的实现单链表基本操作的实现1 1、动态链表的建立动态链表的建立(1)(1) 算法思想算法思想 设：链表的结点结构为：设：链表的结点结构为：typedeftypedef structstruct node nodechar data;char data; node *next;node *next; * *linklistlinklist; ; 首先要建立一个只有头结点的空链表首先要建立一个只有头结点的空链表L L，可调用算法，可调用算法initlist_linitlist_l完成，为了使新结点能够插入到表尾，需要增加一个尾指针完成，为了使新结点能够插入到表尾，需要增加一个尾指针r r指向链指向链表的尾结点。表的尾结点。 初始时，初始时，r r与与L L均指向头结点。每读入一个数据元素则申请一个均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点新结点，将新结点插入到尾结点r r之后，然后使之后，然后使r r指向新的尾结点。指向新的尾结点。 当输入当输入*时结束，时结束，*不是元素。不是元素。TKSTKS7 709:53 (2) (2) 算法算法2.11 2.11 后插法创建单链表及其演示后插法创建单链表及其演示 void void createlist_l(linklistcreatelist_l(linklist l) l) / / 输入若干个元素的值，后插输入若干个元素的值，后插 / / 法建立带表头结点的单链表法建立带表头结点的单链表 TKSTKS8 809:53 intint initlist_l(linklistinitlist_l(linklist &l) &l) / / 生成新结点作为头结点生成新结点作为头结点， / / 用头指针用头指针l l指向头结点指向头结点 L L r r return 1;return 1; l=new node; l=new node; l-next=NULL;l-next=NULL; linklistlinklist p,r;charp,r;char chch; ; r=l;r=l; p p p-next=NULL;p-next=NULL; cincinchch; ; while(chwhile(ch!=*)!=*) p=new node;p=new node; p-data=p-data=chch; ;a a r-next=p;r-next=p; r=p;r=p; r r r r cincinchch; ; p=new node;p=new node; p p e e b b p-data=p-data=chch; ; p-next=NULL;p-next=NULL; r-next=p;r-next=p; r=p;r=p; r r cincinchch; ; p=new node;p=new node; p p p-data=p-data=chch; ;c c p-next=NULL;p-next=NULL; r-next=p;r-next=p; r r r=p;r=p; cincinchch; ; p=new node;p=new node; p p p-data=p-data=chch; ;d d p-next=NULL;p-next=NULL; r-next=p;r-next=p; r=p;r=p; r r cincinchch; ; p=new node;p=new node; p p p-data=p-data=chch; ;p-next=NULL;p-next=NULL; r-next=p;r-next=p; r=p;r=p; cincinchch; ; 算法算法2.11 2.11 后插法创建单链表后插法创建单链表 S3_1S3_1 (3) (3) 算法算法2.11 2.11 前插法创建单链表及其演示前插法创建单链表及其演示 void void createlist_l(linklistcreatelist_l(linklist l) l) / / 输入若干个元素的值，后插输入若干个元素的值，后插 / / 法建立带表头结点的单链表法建立带表头结点的单链表 TKSTKS9 909:53 intint initlist_l(linklistinitlist_l(linklist &l) &l) / / 生成新结点作为头结点生成新结点作为头结点， / / 用头指针用头指针l l指向头结点指向头结点 L L return 1;return 1; l=new node; l=new node; l-next=NULL;l-next=NULL; linklistlinklist p,charp,char chch; ; p-next=l-next; p-next=l-next; cincinchch; ; while(chwhile(ch!=*)!=*) p=new node;p=new node; p-data=p-data=chch; ;a a l-next=p; l-next=p; cincinchch; ; p p e e b b c c p p p p 算法算法算法算法2.10 2.10 2.10 2.10 前前前前插法创建单链表插法创建单链表插法创建单链表插法创建单链表 S3_2S3_2S3_2S3_2 p=new node;p=new node; p p p-data=p-data=chch; ;d d p-next=l-next; p-next=l-next; l-next=p; l-next=p; L L cincinchch; ; p=new node;p=new node; p-data=p-data=chch; ; p-next=l-next; p-next=l-next; l-next=p; l-next=p; L L cincinchch; ; p=new node;p=new node; p p p-data=p-data=chch; ; p-next=l-next; p-next=l-next; l-next=p; l-next=p; L L cincinchch; ; p=new node;p=new node; p-data=p-data=chch; ; p-next=l-next; p-next=l-next; p p l-next=p; l-next=p; L L cincinchch; ; 2 2、查找、查找(1) (1) 算法算法2.6 2.6 在带头结点的单链表在带头结点的单链表l l中查找第中查找第i i个元素个元素intint getelem_l(linklistgetelem_l(linklist l,intl,int i,chari,char &e) &e) linklistlinklist p;intp;int j; j;p=l-p=l-next;jnext;j=1;=1;while(p&jwhile(p&ji)next;p=p-next;j+;j+; if(!p|jif(!p|ji) return 0;i) return 0;e=p-data;e=p-data;return 1;return 1; TKSTKS 101009:53 算法算法算法算法 2.6 2.6 2.6 2.6 在带头结点的单链在带头结点的单链在带头结点的单链在带头结点的单链表表表表l l l l中查找第中查找第中查找第中查找第i i i i个元素个元素个元素个元素 S3_3S3_3S3_3S3_3算法的时间复杂度为算法的时间复杂度为 (n)(n)(2) (2) 算法算法2.7 2.7 在带头结点的单链表在带头结点的单链表l l中查找值为中查找值为e e的元素的元素linklistlinklist locateelem_l(linklistlocateelem_l(linklist l,charl,char e) e) linklistlinklist p; p;p=l-next;p=l-next;while(p&pwhile(p&p-data!=e)-data!=e)p=p-next;p=p-next;return p;return p; TKSTKS 111109:53 算法算法算法算法2.7 2.7 2.7 2.7 在带头结点的单链表在带头结点的单链表在带头结点的单链表在带头结点的单链表l l l l中查找值为中查找值为中查找值为中查找值为e e e e的元素的元素的元素的元素 S3_4S3_4S3_4S3_4intint listinsert_l(linklistlistinsert_l(linklist l,intl,int i,chari,char e) e) linklistlinklist p= p=l,s;intl,s;int j=0; j=0; while(p&jwhile(p&ji-1) p=p-next;jnext;j+; +; if(!p|jif(!p|ji-1) return 0;i-1) return 0; 3 3、插入、插入TKSTKS 121209:53 算法算法算法算法2.8 2.8 2.8 2.8 将值为将值为将值为将值为e e e e的新结点插入到单的新结点插入到单的新结点插入到单的新结点插入到单链表的第链表的第链表的第链表的第i i i i个结点的位置上个结点的位置上个结点的位置上个结点的位置上 S3_5S3_5S3_5S3_5p p a a b b s s s=new node; s=new node; return 1; return 1; x x s-data=e; s-data=e; s-next=p-next; s-next=p-next; p-next=s; p-next=s;算法的时间复杂度为算法的时间复杂度为 (n)(n) 对单链表的操作，其关键是不能使单链表对单链表的操作，其关键是不能使单链表断链断链。对于插入操作，。对于插入操作，要要抓住抓住插入位置前的一个结点。插入位置前的一个结点。 算法算法2.8 2.8 将值为将值为e e的新结点插入到单链表的第的新结点插入到单链表的第i i个结点的位置上个结点的位置上intint listdelete_l(linklistlistdelete_l(linklist l,intl,int i,chari,char &e) &e) linklistlinklist p= p=l,q;intl,q;int j=0; j=0; while(pwhile(p-next&jnext&ji-1) p=p-next;jnext;j+;+; if(!(pif(!(p-next)|jnext)|ji-1) return 0;i-1) return 0;4 4、删除、删除TKSTKS 131309:53 算法算法算法算法2.8 2.8 2.8 2.8 在单链表在单链表在单链表在单链表l l l l中，删除第中，删除第中，删除第中，删除第i i i i个元素，并由个元素，并由个元素，并由个元素，并由e e e e返回其值返回其值返回其值返回其值 S3_6S3_6S3_6S3_6p p 算法的时间复杂度为算法的时间复杂度为 (n)(n) 同样，对于在单链表中删除结点的操作，也要抓住删除位置前的同样，对于在单链表中删除结点的操作，也要抓住删除位置前的一个结点。一个结点。 算法算法2.9 2.9 在单链表在单链表l l中，删除第中，删除第i i个元素，并由个元素，并由e e返回其值返回其值 return 1; return 1; a a b b c c q q q=p-next;q=p-next; p-next=q-next; p-next=q-next; e=q-data;e=q-data; delete q; delete q; TKSTKS 141409:53 即即 p-nextp-nextL L 最后一个结点的指针域的指针又最后一个结点的指针域的指针又指回指回第一个结点的链表。第一个结点的链表。 ？2.3.3 2.3.3 循环循环链表链表 和单链表的差别仅在于，和单链表的差别仅在于，判别判别链表中最后一个结点的链表中最后一个结点的条件条件不再不再是是“后继是否为空后继是否为空”，而是，而是“后继是否为头结点后继是否为头结点”。 有时候，在循环链表中设立尾指针而不设头指针，可使某些操有时候，在循环链表中设立尾指针而不设头指针，可使某些操作简化。例如，将两个线性表合并成一个表的操作：作简化。例如，将两个线性表合并成一个表的操作： p=B-next-p=B-next-next;next;B-next=A-B-next=A-next;next;A-next=pA-next=p；(a) (a) 非空单循环链表非空单循环链表L(b) (b) 空单循环链表空单循环链表L.A.B.BATKSTKS 151509:53 1 1、概念、概念 每个结点有每个结点有两个两个指针域，一个指向直接后继元素结点，另一个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点指向直接前趋元素结点。若干个这样的结点组成的链表称若干个这样的结点组成的链表称双向双向链表链表。数据域数据域指针域指针域指针域指针域结点结点存储后继结存储后继结点的地址点的地址存储前趋结存储前趋结点的地址点的地址2.3.4 2.3.4 双向双向链表链表 2 2、双向链表的存储结构双向链表的存储结构typedeftypedef structstruct dulnodedulnode ElemTypeElemType data; data; dulnodedulnode *prior; *prior; dulnodedulnode *next; *next; dulnodedulnode, *, *dulinklistdulinklist; ;TKSTKS 161609:53 3 3、双向链表图示、双向链表图示 4 4、操作特点、操作特点 “查询查询”和单链表相同。和单链表相同。 “插入插入”和和“删除删除”时需要同时修改两个方向上的指针。时需要同时修改两个方向上的指针。(a) (a) 空双向循环链表空双向循环链表L-next=L(b) (b) 双向循环链表双向循环链表TKSTKS 171709:53 ai-1aies-next = p-next; p-next = s;s-next-prior = s; s-prior = p;psai插入插入ai-1ai-1删除删除aiai+1p-next = p-next-next;p-next-prior = p;pai-1TKSTKS 181809:53 有关算法实现作为阅读材料。有关算法实现作为阅读材料。TKS 1919五、作业：五、作业：1 1、书面作业：、书面作业：p41 1p41 1中中 (4)(4)(8)(8)、(11)(11)(15)(15)2 2、上机编程：、上机编程： ( (数据结构编程练习数据结构编程练习) )中中 p43 2p43 2中中 (6)(6)(8806)(8806)、 (7)(7)(8807)(8807)、(1)(1)(8801)(8801)、(2)(2)(8802)(8802) ？