1、数据结构计算机与信息学院 刘勇第1页每课一贴每课一贴：原来很简单原来很简单 有个小弟在脚踏车店当学徒，有人送来一部故障的脚踏车，有个小弟在脚踏车店当学徒，有人送来一部故障的脚踏车，小弟除了将车修好，还把车子整理的漂亮如新，其它学徒笑他多小弟除了将车修好，还把车子整理的漂亮如新，其它学徒笑他多此一举，后来雇主将脚踏车领回去的第二天，小弟被挖角到那位此一举，后来雇主将脚踏车领回去的第二天，小弟被挖角到那位雇主的公司上班。雇主的公司上班。原来出人头地很简单，吃点亏就可以了。原来出人头地很简单，吃点亏就可以了。有一个网球教练对学生说：如果一个网球掉进草堆里，应有一个网球教练对学生说：如果一个网球掉进草
2、堆里，应该如何找？该如何找？有人答：从草堆中心线开始找。有人答：从草堆中心线开始找。有人答：从草堆的最凹处开始找。有人答：从草堆的最凹处开始找。有人答：从草最长的地方开始找。有人答：从草最长的地方开始找。教练宣布正确答案：按部就班的从草地的一头，搜寻到草教练宣布正确答案：按部就班的从草地的一头，搜寻到草地的另一头。地的另一头。原来寻找成功的方法很简单，从一数到十不要跳过原来寻找成功的方法很简单，从一数到十不要跳过就可以了就可以了。数据结构计算机与信息学院 刘勇第2页上堂课要点回顾上堂课要点回顾1.1.线性结构线性结构(包括表、栈、队、数组）的定义和特点：包括表、栈、队、数组）的定义和特点：仅一
3、个首、尾结点，其余元素仅一个直接前驱和一仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。个直接后继。2.2.线性表线性表逻辑结构逻辑结构：“一对一一对一”或或 1:11:1存储结构存储结构：顺序、链式：顺序、链式运运 算算：修改、插入、删除：修改、插入、删除3.3.顺序存储顺序存储特征特征：逻辑上相邻，物理上也相邻；逻辑上相邻，物理上也相邻；优点：优点：随机查找快随机查找快 O(1)O(1)缺点：缺点：插入、删除慢插入、删除慢 O(n)O(n)数据结构计算机与信息学院 刘勇第3页2.3 线性表的链式表示和实现线性表的链式表示和实现2.3.1 链表的表示链表的表示2.3.2 链链表的实现
4、表的实现2.3.3 链链表的运算效率分析表的运算效率分析链表小结链表小结数据结构计算机与信息学院 刘勇第4页2.3.1 链表的表示链表的表示1536元素元素2 21400元素元素1 11346元素元素3 3 元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 .14001400 元素元素2 2 15361536 .15361536 元素元素3 3 13461346h数据结构计算机与信息学院 刘勇第5页链式存储结构特点：链式存储结构特点：其结点在存储器中的其结点在存储器中的位置是位置是随意随意
5、的，的，即逻辑上相邻的数据元素逻辑上相邻的数据元素在物理上在物理上不一定不一定相邻相邻。如何实现？通过来实现注意：注意：每个存储结点都包含两部分：每个存储结点都包含两部分：数据域数据域和和指针域指针域2.3.1 链表的表示链表的表示数据结构计算机与信息学院 刘勇第6页例例1 画出画出26 个英文字母表的链式存储结构个英文字母表的链式存储结构。该字母表在内存的链式存放示意图如下：该字母表在内存的链式存放示意图如下：解：该字母表的逻辑结构为：解：该字母表的逻辑结构为：（a,b,y,z）aheadb/z各结点由两个域组成：各结点由两个域组成：数据域：数据域：存储元素数值数据；存储元素数值数据；指针域
6、：指针域：存储直接后继或者直接前驱的存储位置。存储直接后继或者直接前驱的存储位置。指针数据指针数据指针或或样式：样式：数据结构计算机与信息学院 刘勇第7页与链式存储有关的术语：与链式存储有关的术语：1、结点：、结点：数据元素的存储映像。由数据域和指针域两部分组成；数据元素的存储映像。由数据域和指针域两部分组成；2、链表：、链表：n 个结点由个结点由指针链指针链组成一个链表。它是线性表的链式组成一个链表。它是线性表的链式存储映像存储映像，称为线性表的链式存储结构称为线性表的链式存储结构。3、单链表、双链表、多链表、循环链表、单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为结点只有
7、一个指针域的链表，称为单链表单链表或或线性链表线性链表；有两个指针域的链表，称为有两个指针域的链表，称为双链表双链表；有多个指针域的链表，称为有多个指针域的链表，称为多链表多链表；首尾相接的链表称为首尾相接的链表称为循环链表循环链表。a1heada2anhead循环链表示意图：循环链表示意图：数据结构计算机与信息学院 刘勇第8页4、头指针、头结点和首元结点、头指针、头结点和首元结点 示意图如下：示意图如下：头指针头指针头结点头结点首元结点首元结点a1heada2infoan头指针头指针是指向链表中是指向链表中第一个结点第一个结点（或为头结点或为首元结点）（或为头结点或为首元结点）的指针；的指针
8、；头结点头结点是在链表的是在链表的首元结点之前附设的一个结点首元结点之前附设的一个结点；数据域内；数据域内只放空表标志和表长等信息只放空表标志和表长等信息;首元结点首元结点是指链表中存储线性表是指链表中存储线性表第一个数据元素第一个数据元素a a1 1的结点。的结点。数据结构计算机与信息学院 刘勇第9页一个线性表的逻辑结构为：一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存），其存储结构用单链表表示如下，储结构用单链表表示如下，请问其请问其头指针头指针的的值值是多少？是
9、多少？存储地址存储地址数据域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例例：答：答：头指针头指针是指向是指向链表中第一个结点链表中第一个结点的指针，因此关键的指针，因此关键是要寻找是要寻找第一个结第一个结点的地址点的地址。7ZHAOH31头指针的值是头指针的值是31数据结构计算机与信息学院 刘勇第10页上例链表的逻辑结构示意图有以下上例链表的逻辑结构示意图有以下两种形式两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别：
10、区别：无头结点无头结点 有头结点有头结点数据结构计算机与信息学院 刘勇第11页讨论1.在链表中设置头结点有什么好处？头结点头结点即在链表的首元结点之前附设的一个结点，该结即在链表的首元结点之前附设的一个结点，该结点的数据域中点的数据域中不存储线性表的数据元素不存储线性表的数据元素，其作用是为了对链表，其作用是为了对链表进行操作时，可以对进行操作时，可以对空表、非空表空表、非空表的情况以及对的情况以及对首元结点首元结点进行进行统一处理，编程更方便。统一处理，编程更方便。答：答：讨论2.头结点的数据域内装的是什么？头结点的头结点的数据域数据域可以为空，也可存放线性表可以为空，也可存放线性表长度长度
11、等附加信息，但此结点不能计入链表长度值。等附加信息，但此结点不能计入链表长度值。答：答：头结点的数据域头结点的数据域H数据结构计算机与信息学院 刘勇第12页讨论4.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，所以要采用因每个结点至少有两个分量，所以要采用结构结构数数据类型。据类型。答：答：什么是结构类型？如何书写表达？什么是结构类型？如何书写表达？答：答：讨论3.如何表示空表空表？无头结点时，无头结点时，当头指针的值为空当头指针的值为空时表示空表；时表示空表；有头结点时，有头结点时，当头结点的指针域为空当头结点的指针域为空时表示空表。时表示空表。头指
12、针头指针头指针头指针头结点头结点无头结点无头结点有头结点有头结点数据结构计算机与信息学院 刘勇第13页 实现实现typedef struct node Elemtype data;struct node *link;LNode，*LinkList;linklist *h,*p;datalinkp结点（结点（*p）(*p)表示表示p所指向的结点所指向的结点(*p).datap-data表示表示p指向结点的数据域指向结点的数据域(*p).linkp-link表示表示p指向结点的指针域指向结点的指针域生成一个生成一个LNode型型新结点：新结点：p=(linklist)malloc(sizeof(L
13、Node);系统回收系统回收p结点：结点：free(p)3.线性链表的实现线性链表的实现 定义：结点中只含一个指针域的链表叫定义：结点中只含一个指针域的链表叫，也叫，也叫单链表单链表数据结构计算机与信息学院 刘勇第14页 用一组用一组任意任意的存储单元存储线性表的数据元素的存储单元存储线性表的数据元素 利用利用指针指针实现了用不相邻的存储单元存放逻辑上实现了用不相邻的存储单元存放逻辑上相邻的元素相邻的元素 每个数据元素每个数据元素ai，除存储，除存储本身信息本身信息外，还需存储其外，还需存储其直接后继直接后继的的地址地址 结点结点 数据域：元素本身信息数据域：元素本身信息 指针域：指示直接后继
14、的存储位置指针域：指示直接后继的存储位置数据域数据域 指针域指针域结点结点简单总结：线性表的链式表示的基本特征：简单总结：线性表的链式表示的基本特征：数据结构计算机与信息学院 刘勇第15页4.单链表的基本运算单链表的基本运算Ch2_3.txtWhile循环中语句频度为循环中语句频度为若找到结点若找到结点X，为结点，为结点X在表中的序号在表中的序号否则，为否则，为n nOnT 算法评价算法评价v 查找：查找单链表中是否存在结点查找：查找单链表中是否存在结点X，若有则返，若有则返回指向回指向X结点的指针；否则返回结点的指针；否则返回NULL查找、插入、删除、查找、插入、删除、创建、原地逆序创建、原
15、地逆序 算法描述算法描述类似算法：求长度等，类似算法：求长度等，举一反三举一反三P36查找查找数据结构计算机与信息学院 刘勇第16页pabxs 插入插入:在线性表在线性表两个数据元素两个数据元素a和和b间间插入插入x，已知已知p指向指向as-link=p-link;p-link=s;1OnT 算法描述算法描述 算法评价算法评价注意注意前插和前插和后插后插的区别的区别数据结构计算机与信息学院 刘勇第17页算法描述算法描述pabc 1OnT算法评价算法评价删除删除：单链表中删除：单链表中删除b，设，设p指向指向ap-link=p-link-link;数据结构计算机与信息学院 刘勇第18页 nOnT
16、 动态建立单链表算法动态建立单链表算法：设线性表设线性表n个元素已存个元素已存放在数组放在数组a中，建立一个单链表，中，建立一个单链表，h为头指针为头指针 算法描述算法描述 算法评价算法评价h头结点头结点an 0h头结点头结点an-10an a2.h头结点头结点an-10an ha1a2头结点头结点an .0h头结点头结点0注意注意前插和前插和后插后插的区别的区别 P35/36数据结构计算机与信息学院 刘勇第19页 nOnT单链表单链表原地逆序原地逆序算法算法：设线性表设线性表n个元素已存放个元素已存放在链表在链表a中，要求在不改变其元素位置的条件下中，要求在不改变其元素位置的条件下将链表逆序
17、排列，将链表逆序排列，h为头为头指针指针 算法描述算法描述 算法评价算法评价ha1a2头结点头结点an .0hanan-1头结点头结点a1 .0数据结构计算机与信息学院 刘勇第20页5.5.应用举例：两个链表的归并应用举例：两个链表的归并（教材（教材P41P41）算法要求：算法要求：已知：已知：线性表线性表 A、B，分别由，分别由单链表单链表 LA,LB 存储，存储，其中数据元素按值其中数据元素按值非递减有序非递减有序排列，排列，要求：要求：将将 A，B 归并归并为一个新的线性表为一个新的线性表C,C 的数据的数据元素仍按值元素仍按值非递减排列非递减排列 。设线性表。设线性表 C 由由单链表单
18、链表 LC 存储。存储。假设：假设：A=（3，5，8，11），），B=（2，6，8，9，11）预测：预测：合并后合并后 C=（2,3,5,6,8,8,9,11，11）数据结构计算机与信息学院 刘勇第21页用链表可表示为：用链表可表示为：3 511/8 LaLa 2 611/8 LbLb 9 2 3 6 5 LcLc 8 811/911头结点头结点数据结构计算机与信息学院 刘勇第22页La3 5 8 11 Lb2 6 8 119 PaPbPaPbPa、Pb用于搜索用于搜索La和和Lb，Pc指向新链表当前结点指向新链表当前结点Lc Pa3 PcPa5 Pc11Pc2 PbPcPa数据结构计算机与信
19、息学院 刘勇第23页算法分析：算法分析：算法主要包括：算法主要包括：搜索、比较、插入搜索、比较、插入三个操作：三个操作：搜索：搜索：需要需要两个指针两个指针搜索两个链表；搜索两个链表；比较：比较：比较结点数据域中数据的大小；比较结点数据域中数据的大小；插入：插入：将两个结点中数据将两个结点中数据小的结点插入新链表小的结点插入新链表。数据结构计算机与信息学院 刘勇第24页算法实现：算法实现：Void MergeList_L(LinkList La,LinkList Lb,LinkList*Lc)/按值排序的单链表按值排序的单链表LA,LB，归并为，归并为LC后也按值排序后也按值排序 free(L
20、b);/释放释放Lb的头结点的头结点/MergeList_L pc-next=pa?pa:pb;/插入剩余段插入剩余段 while(pa&pb)/将将pa、pb结点按大小依次插入结点按大小依次插入C中中 if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next pa=La-next;pb=Lb-next;pc=Lc-next；/初始化初始化 数据结构计算机与信息学院 刘勇第25页思考：思考：1、不用、不用Lc，直接把直接把La表插到表插到Lb表中表中；或者把；或者把Lb表表 插到插到La表中，如何编程
21、？表中，如何编程？2、要求、要求不能有重复的数据元素不能有重复的数据元素，如何编程？，如何编程？Void MergeList_L(LinkList *La,LinkList Lb)相同元素不进行归并相同元素不进行归并数据结构计算机与信息学院 刘勇第26页答：能。只要定义一个结构类型（含答：能。只要定义一个结构类型（含数据域数据域和和指示指示域域）数组，就可以完全描述链表，这种链表称为）数组，就可以完全描述链表，这种链表称为静静态链表态链表。注：数据域含义注：数据域含义与前面相同，与前面相同，指示域指示域相当于前面的相当于前面的指针域。指针域。讨论讨论1 1：用一维数组也能存放链表吗？怎样实现？
22、用一维数组也能存放链表吗？怎样实现？静态链表的插入与删除操作与普通链表一样，静态链表的插入与删除操作与普通链表一样，不需要移动元素，只需修改指示器不需要移动元素，只需修改指示器就可以了。就可以了。具体实现过程可见具体实现过程可见教材教材P32-34P32-34。数据结构计算机与信息学院 刘勇第27页讨论讨论2 2：链表能不能首尾相连？怎样实现？链表能不能首尾相连？怎样实现？答：能。只要将表中最后一个结点的指针域指向头结答：能。只要将表中最后一个结点的指针域指向头结点即可点即可 (P-next=head;P-next=head;)。这种形成环路的链表称。这种形成环路的链表称为为循环链表循环链表。
23、讨论讨论3 3：单链表只能查找结点的直接后继，能不能单链表只能查找结点的直接后继，能不能查找直接前驱？如何实现？查找直接前驱？如何实现？答：答：能能。只要把单链表再多开一个指针域即可。只要把单链表再多开一个指针域即可(例例如用如用*nextnext和和*prior;prior;)。双向链表在非线性结构（如树结构）中将大量使用。双向链表在非线性结构（如树结构）中将大量使用。prior datanext这种有两个指针的链表称为这种有两个指针的链表称为双向链表双向链表。其特点是。其特点是可以双向查找表中结点。参见教材可以双向查找表中结点。参见教材P36P363838。数据结构计算机与信息学院 刘勇第
24、28页 循环链表是表中最后一个结点循环链表是表中最后一个结点p的指针指向头结的指针指向头结点，使链表构成环状点，使链表构成环状 p-next=head;p-next=head;特点特点：从表中任一结点出发均可找到表中其他结从表中任一结点出发均可找到表中其他结点，提高查找效率点，提高查找效率 操作与单链表基本一致操作与单链表基本一致,循环条件不同循环条件不同 单链表单链表p或或p-link=NULL 循环链表循环链表p或或p-link=Hhh空表空表 循环链表循环链表(circular linked list)数据结构计算机与信息学院 刘勇第29页 双向链表双向链表（double linked
25、list）单链表具有单向性的缺点单链表具有单向性的缺点typedef struct node datatype element;struct node*prior,*next;JD;priorelementnextL空双向循环链表：v结点定义非空双向循环链表：LABbcapp-prior-next=p=p-next-proir;数据结构计算机与信息学院 刘勇第30页bcaPvoid del_dulist(JD*p)p-prior-next=p-next;p-next-prior=p-prior;free(p);删除 算法描述 算法评价：T(n)=O(1)p-prior-next=p-next;
26、p-next-prior=p-prior;数据结构计算机与信息学院 刘勇第31页void ins_dulist(JD*p,int x)JD*s;s=(JD*)malloc(sizeof(JD);s-element=x;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;算法描述 算法评价：T(n)=O(1)xSbaP 插入数据结构计算机与信息学院 刘勇第32页5.链表的运算效率分析链表的运算效率分析1.查找查找 因线性链表因线性链表不能顺序存取不能顺序存取，即在查找时要，即在查找时要从头指针找起，查找的时间复杂度为从头指针找起，查找的时间复杂度为
27、 O(n)。时间效率分析2.插入和删除插入和删除 因线性链表不需要移动元素，只要修因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为改指针，一般情况下时间复杂度为 O(1)。但是，如果要在单链表中进行但是，如果要在单链表中进行前插前插或或删除删除操作，操作，由由于要从头查找前驱结点，所耗时间复杂度为于要从头查找前驱结点，所耗时间复杂度为 O(n)。数据结构计算机与信息学院 刘勇第33页练：练：空间效率分析链表中每个结点都要增加一个指针空间，相当于总链表中每个结点都要增加一个指针空间，相当于总共增加了共增加了n 个整型变量，空间复杂度为个整型变量，空间复杂度为 O(n)。在在n n个
28、结点的单链表中要删除已知结点个结点的单链表中要删除已知结点*P P，需找到它，需找到它的的 ，其时间复杂度为，其时间复杂度为 。前驱结点的地址前驱结点的地址O O(n)(n)数据结构计算机与信息学院 刘勇第34页线性表的实现与表示方法小结：线性表的实现与表示方法小结：线性表逻辑结构特点是线性表逻辑结构特点是，只有一个首结点和尾结点；，只有一个首结点和尾结点；除首尾结点外其他结点只有一个直接前驱和一个直接后继。除首尾结点外其他结点只有一个直接前驱和一个直接后继。简言之，线性结构反映结点间的逻辑关系是一对一（简言之，线性结构反映结点间的逻辑关系是一对一（1:11:1）的。的。问问1：线性表的逻辑结
29、构特点是什么？其顺序存储线性表的逻辑结构特点是什么？其顺序存储结构和链式存储结构的特点是什么？结构和链式存储结构的特点是什么？答：答：顺序存储顺序存储时，相邻数据元素的存放地址也相邻（逻辑与时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。物理统一）；要求内存中可用存储单元的地址必须是连续的。链式存储链式存储时，相邻数据元素可随意存放，但所占存储空时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。关系的指针。数据结构计算机与信息学院 刘勇第35页
30、 顺序存储的优点是存储密度大顺序存储的优点是存储密度大(1)1)，存储，存储空间利用率高。缺点是插入或删除元素效率低。空间利用率高。缺点是插入或删除元素效率低。链式存储的优点是插入或删除元素时效率高，链式存储的优点是插入或删除元素时效率高，使用灵活。缺点是存储密度小（使用灵活。缺点是存储密度小（11），存储空间），存储空间利用率低。利用率低。答：答：问问2：顺序存储和链式存储各有哪些优缺点？顺序存储和链式存储各有哪些优缺点？事实上，链表插入、删除运算的快捷是以空间事实上，链表插入、删除运算的快捷是以空间代价来换取时间。代价来换取时间。数据结构计算机与信息学院 刘勇第36页2.4 应用举例应用举
31、例1.一元多项式的数学通式？一元多项式的数学通式？2.用用C语言如何描述它的定义？语言如何描述它的定义？3.如何编程实现两个一元多项式相加？如何编程实现两个一元多项式相加？一元多项式的计算一元多项式的计算(参见严教材参见严教材P46 55)讨论：讨论：数据结构计算机与信息学院 刘勇第37页1.一元多项式的数学通式？一元多项式的数学通式？一元多项式的通式可表示为：一元多项式的通式可表示为：2012().nnnPxppxpxpx012(,.)nPpppp2012().mmmQxqqxqxqx012(,.)mQqqqq()()()nnmRxPxQx00111(,.,.,)mmmnRpqpqpqpp假
32、定假定mexpon=Pb-expon等情况，等情况，再决定是再决定是将两系数域的数值相加（并判其和是否为将两系数域的数值相加（并判其和是否为0 0），），还是将较高指数项的结点插入到新表还是将较高指数项的结点插入到新表c c中。中。3 142 81 0 aPaPa8 14-3 1010 6 bPbPb11 14-3 102 81 0 cPcPc10 6+数据结构计算机与信息学院 刘勇第42页1.设设p,q分别指向分别指向A,B中某一结点，中某一结点，p,q初值是第一结点初值是第一结点2.比较比较p-exp与与q-expp-exp exp:p结点是和多项式中的一项结点是和多项式中的一项 p后移后
33、移,q不动不动p-exp q-exp:q结点是和多项式中的一项结点是和多项式中的一项 将将q插在插在p之前之前,q后移后移,p不动不动p-exp=q-exp:系数相加系数相加0：从：从A表中删去表中删去p,释放释放p,q，p,q后移后移 0：修改：修改p系数域系数域,释放释放q，p,q后移后移3.直到直到p或或q为为NULL 若若q=NULL，结束，结束 若若p=NULL，将，将B中剩余部分连到中剩余部分连到A上即可上即可 运算规则（运算规则（将将A，B两多项式的和存储在两多项式的和存储在A中中）数据结构计算机与信息学院 刘勇第43页加法运算的拓展乘法加法运算的拓展乘法:12121()()()
34、()(.)()nieeenneiiM xA x B xA xb xb xb xb A x x数据结构计算机与信息学院 刘勇第44页本章小结本章小结1.1.线性表线性表逻辑结构逻辑结构：“一对一一对一”或或 1:11:1存储结构存储结构：顺序、链式：顺序、链式运运 算算 ：修改、插入、删除：修改、插入、删除3.3.链式存储链式存储特征特征：逻辑上相邻，物理上逻辑上相邻，物理上不一定不一定相邻；相邻；优点：优点：插入删除效率高插入删除效率高 O(1)O(1)（后后）缺点：缺点：查找慢查找慢 O(n)O(n)2.2.顺序存储顺序存储特征特征：逻辑上相邻，物理上也相邻；逻辑上相邻，物理上也相邻；优点：优点：随机查找快随机查找快 O(1)O(1)缺点：缺点：插入、删除慢插入、删除慢 O(n)O(n)有奖思考题有奖思考题：在实际应用中如何选用顺序表和链表？：在实际应用中如何选用顺序表和链表？数据结构计算机与信息学院 刘勇第45页作业作业 请下周上课时交来！请下周上课时交来！2.2自测自测 2.4，2.7，有奖附加有奖附加2.13第一次实验：第一次作业程序实现第一次实验：第一次作业程序实现，地点：电气信息楼地点：电气信息楼 2楼实验室楼实验室
