第三章 第二讲 线性表和数组.ppt

《第三章 第二讲 线性表和数组.ppt》由会员分享，可在线阅读，更多相关《第三章 第二讲 线性表和数组.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院第二讲第二讲 线性表线性表线性结构特点：在数据元素的非空有限集中:1.存在存在唯一唯一的一个被称作的一个被称作“第一个第一个”的数据元素的数据元素.2.存在存在唯一唯一的一个被称作的一个被称作“最后一个最后一个”的数据元的数据元素素.3.除第一个外，集合中的每个数据元素均除第一个外，集合中的每个数据元素均只有一只有一个前驱个前驱.4.除最后一个外，集合中的每个数据元素均除最后一个外，集合中的每个数据元素均只有只有一个后继一个后继.1C C C C语言与程序设计语言与程序设计语言与程序设计语言

2、与程序设计 江汉大学数计学院江汉大学数计学院2.1 2.1 线性表的逻辑结构线性表的逻辑结构定义：一个线性表是定义：一个线性表是n n个数据元素的有限序列个数据元素的有限序列例例1 英文字母表（英文字母表（A,B,C,.Z)是一个线性表是一个线性表例例2数据元素特征：特征：元素个数元素个数n=n=表长度，表长度，n=0n=0空表空表11inin时时aiai的直接的直接前驱前驱是是ai-1ai-1，a1a1无直接前驱无直接前驱aiai的直接的直接后继后继是是ai+1ai+1，anan无直接后继无直接后继2C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉

3、大学数计学院顺序表：顺序表：定义：用一组地址连续的存储单元存放一个线性表叫定义：用一组地址连续的存储单元存放一个线性表叫元素地址计算方法：元素地址计算方法：LOC(aiLOC(ai)=LOC(a1)+(i-1)*L)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai+1)=LOC(ai)+LLOC(ai)+Ln其中：其中：L:L:一个元素占用的存储单元个数一个元素占用的存储单元个数LOC(aiLOC(ai):):线性表第线性表第i i个元素的地址个元素的地址特点：特点：逻辑上相邻逻辑上相邻物理地址相邻物理地址相邻.随机存取随机存取.可用可用C C语言的一维数组实现语言的一维数组实

4、现 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构3C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院a1a2an01n-112n内存内存A A数组下标数组下标元素序号元素序号M#define M 1000int dataM;例例 struct card int num;char name20;char author10;char publisher30;float price;struct card dataM;备备用用空空间间数据元素不是简单类型时数据元素不是简单类型时,可定义可定义结构体数组结构体数组4C C C C语言与程

5、序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院 1.1.插入节点定义：插入节点定义：线性表的插入是指在第线性表的插入是指在第i i（1 1 i i n+1n+1）个元素之前插入一个新的数个元素之前插入一个新的数据元素据元素x x，使长度为使长度为n n的线性表的线性表加。加。变成变成长度为长度为n+1n+1的线性表的线性表 需将第需将第i i至第至第n n共（共（n-i+1)n-i+1)个元素后移个元素后移2.3 2.3 线性表的插入和删除算法线性表的插入和删除算法5C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉

6、大学数计学院内存内存a1a2aiai+1an01i-1A A 数组下标数组下标n-1in12i元素序号元素序号i+1nn+1内存内存a1a2aiai+1an01i-1A 数组下标数组下标n-1in12i元素序号元素序号i+1nn+1an-1x6C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院简简化化插插入入算算法法 void insert(int A ,n,i,X)/类类c c语言描述语言描述/*i表示第表示第i个元素个元素*/int j;if(in+1)printf(“i值错！值错！n”);else for(j=n;j=i;j-)A j

7、=Aj-1;/*/*将第将第i i个元素及其后面的元素后移个元素及其后面的元素后移*/A i-1=X;n+;/*/*线性表长度加线性表长度加1*/1*/7C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院算法时间复杂度算法时间复杂度T(n)T(n)设设PiPi是在第是在第i i个元素之前插入一个元素的概率，个元素之前插入一个元素的概率，则在长度为则在长度为n n的线性表中插入一个元素时，所需的线性表中插入一个元素时，所需移动的元素次数的平均次数为：移动的元素次数的平均次数为：8C C C C语言与程序设计语言与程序设计语言与程序设计语言与程

8、序设计 江汉大学数计学院江汉大学数计学院2.2.删除删除：线性表的删除是指将第：线性表的删除是指将第i i（1 1 i i n n）个元素删除，使长度为个元素删除，使长度为n n的线性表的线性表.变成变成长度为长度为n-1n-1的线性表的线性表 需将第需将第i+1i+1至第至第n n共共（n-i)n-i)个元素前移个元素前移9C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院内存内存a1a2aiai+1an01i-1A 数组下标数组下标n-1in12i元素序号元素序号i+1nn+1内存内存a1a2ai+1A 数组下标数组下标01i-1n-2

9、in-112i元素序号元素序号i+1n-1nanai+210C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院简化简化删除删除函数函数 void delete(int A ,int n,i)/*i表示第表示第i个元素个元素*/int j;if(in)printf(“i值错！值错！n”);else for(j=i;jdatap-data表示表示p p指向结点的指向结点的数据域数据域;(*p).link(*p).linkp-linkp-link表示表示p p指向结点的指向结点的指针域指针域;2.3.1 2.3.1 单链表单链表定义：结点中只含一

10、个指针域的链表叫单链表定义：结点中只含一个指针域的链表叫单链表.16C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院单链表的基本运算单链表的基本运算查找：查找单链表中是否存在结点查找：查找单链表中是否存在结点X X，若有则返回，若有则返回指向指向X X结点的指针；否则返回结点的指针；否则返回NULLNULL.(.(不带头节点不带头节点)算法描述：算法描述：ListNode*find(ListNode head,int x)ListNode*p;P=head;while (p&p-data!=x)p=p-next;return p;17C

11、C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院2.2.单链表的插入单链表的插入 实现插入算法主要完成三个基本操作：实现插入算法主要完成三个基本操作：1)1)在单链表上找到插入位置，即找到第在单链表上找到插入位置，即找到第i i个结点。个结点。可可以以用用遍遍历历的的方方法法，即即从从表表头头起起顺顺次次访访问问单单链链表表的的结结点，直至找到第点，直至找到第i i个结点。个结点。2)2)生成一个以生成一个以x x为值的新结点。为值的新结点。可通过可通过C C的库函数的库函数malloc(sizemalloc(size)来产生。来产生。3)3

12、)将新结点链入单链表中。将新结点链入单链表中。需要改变相关结点的指针需要改变相关结点的指针 ，如下面的图所示。，如下面的图所示。单链表的插入单链表的插入:所谓插入是指在单链表中第所谓插入是指在单链表中第i i个结个结点点(i0)(i0)之后插入一个元素为之后插入一个元素为x x的结点。的结点。18C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院 假设指针假设指针p p指向单链表中的第指向单链表中的第i i个结点，指针个结点，指针s s指向已生成的新结点，链入新结点的操作如下：指向已生成的新结点，链入新结点的操作如下：将新结点将新结点*s

13、s的链域指向结点的链域指向结点*p p的后继结点的后继结点 (即即s-next=p-next)；将结点将结点*p p的链域指向新结点的链域指向新结点 (即即p-next=s)p-next=s)。19C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院插插入入算算法法 void insert(node*head,int i,x)node*s,*p;int j;s=(node*)malloc(sizeof(node);/*/*生成新结点生成新结点*/s-data=x;if(i=0)/*/*如果如果i=0,i=0,则将则将s s所指结点插入到表头所

14、指结点插入到表头*/s-next=head;head=s;else p=head;j=1;/*/*查找第查找第i i个结点，由个结点，由p p所指向所指向*/20C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院插入算法续插入算法续 while(p!=NULL&jnext;if(p!=NULL)/*把新结点插入其后把新结点插入其后*/s-next=p-next;p-next=s;else printf(“未找到！未找到！n”);21C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院3.3

15、.单链表的删除单链表的删除删除单链表上一个其值为删除单链表上一个其值为x x的结点的主要操作是：的结点的主要操作是：1)1)用遍历的方法在单链表上找到该结点；用遍历的方法在单链表上找到该结点；2)2)从单链表上删除该结点。从单链表上删除该结点。注意注意:从单链表上删除一个结点，需修改该结点从单链表上删除一个结点，需修改该结点的前一个结点的指针，如下面的图所示。的前一个结点的指针，如下面的图所示。22C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院 假设指针假设指针q q指向待删除结点的前一个结点，指针指向待删除结点的前一个结点，指针p p

16、指指向要删除的结点，删除该结点的操作如下：将该结向要删除的结点，删除该结点的操作如下：将该结点的前一个结点点的前一个结点*q q的链域指向的链域指向*p p的后继结点的后继结点 （即（即q-next=p-nextq-next=p-next）。）。23C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院删删 除除 算算 法法void delete(node*head,int x)node *p,*q;if(head=NULL)printf (“(“链表下溢！链表下溢！n”);/*n”);/*判空判空*/if(head-data=x)/*/*如表

17、头结点值等于如表头结点值等于x*/x*/p=head;head=head-next;free(p);else q=head;/*/*从第二个结点开始查找从第二个结点开始查找*/p=head-next;heada pxhead24C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院删除算法续删除算法续 while(p!=NULL&p-data!=x)q=p;p=p-next;if(p!=NULL)/*/*找到该结点，删除找到该结点，删除*/q-next=p-next;free(p);else printf(“未找到！未找到！n”);25C C

18、C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院核心代码：核心代码：while(ch!=n)p=(node*)malloc(size of(Node);p-data=ch;p-next=head;head=p;ch=getchar();补充补充:动态建立单链表算法动态建立单链表算法 头插法建表：该方法是从一个空表开始，重复的读头插法建表：该方法是从一个空表开始，重复的读入数据，生成新的节点，将数据存放到数据域中，然入数据，生成新的节点，将数据存放到数据域中，然后将新节点插入到表头，只到遇到结束标志为止。后将新节点插入到表头，只到遇到结束标志为止。

19、bha c p26C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院单链表特点：单链表特点：1.它是一种它是一种动态结构动态结构，整个存储空间为多，整个存储空间为多个链表共用。个链表共用。2.不需预先分配不需预先分配空间。空间。3.指针占用指针占用额外额外存储空间。存储空间。4.不能随机存取不能随机存取，查找速度慢。，查找速度慢。27C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院2.3.22.3.2循环链表循环链表(circular linked list(circular link

20、ed list)()(补充补充)1.1.环链表是表中循最后一个结点的指针指向头结点，环链表是表中循最后一个结点的指针指向头结点，使链表构成环状使链表构成环状2.2.特点：从表中任一结点出发均可找到表中其他结点，特点：从表中任一结点出发均可找到表中其他结点，提高查找效率提高查找效率3.3.操作与单链表基本一致操作与单链表基本一致,循环条件不同循环条件不同单链表单链表p-link!=NULLp-link!=NULL循环链表循环链表p-link!=H p-link!=H /*/*从表头开始从表头开始hh空表28C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江

21、汉大学数计学院1.1.在循环链表在循环链表CLCL中检索值为中检索值为e e的数据元素的数据元素NODE*find(NODE*head,e)NODE*p;for(p=head-next;(p!=head)&(p-data!=e);p=p-next);if(p!=head)return p;else return NULL;h29C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院 在循环链表中在循环链表中,访问后继结点，只需要向后走访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。一步，而访问前驱结点，就需要转一圈。问题：循环链表

22、并不适用于经常访问前驱问题：循环链表并不适用于经常访问前驱 结点的情况结点的情况,怎么办怎么办?解决方法：在需要频繁地同时访问前驱和后继结点解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。的时候，使用双向链表。所谓双向链表所谓双向链表,双向链表就是每个结点有两个指针双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点域。一个指向后继结点，另一个指向前驱结点。2.3.3 2.3.3 双向循环链表双向循环链表30C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院双向链表就是每个结点有两个指针域。一个指向后双向

23、链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点继结点，另一个指向前驱结点llinkdatarlinkhead(a)(b)Typedef struct node int data;struct node*llink,*rlink;JD;31C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院bcaPvoid del_dulist(JD*p)(p-Llink)-rlink=p-rlink;(p-rlink)-Llink=p-Llink;free(p);双向链表删除一个节点双向链表删除一个节点(p-Llink)-rlink=p-

24、rlink;(p-rlink)-Llink=p-Llink;32C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院void ins_dulist(Node*p,int x)Node*s;s=malloc(sizeof(Node);s-data=x;s-Llink=p-Llink;(p-Llink)-rlink=s;s-rlink=p;p-Llink=s;xSbaP插入一个节点插入一个节点33C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院 3.3.链表的应用链表的应用3.1 3.1 一

25、元多项式的算术运算一元多项式的算术运算设一个一元多项式为设一个一元多项式为如果用数组来表示一元多项式，以各项的指数如果用数组来表示一元多项式，以各项的指数作为下标，将各个系数存入一维数组中。作为下标，将各个系数存入一维数组中。34C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院2.2.用单链表表示一元多项式用单链表表示一元多项式将单链表的每个结点对应着一元多项式中的一将单链表的每个结点对应着一元多项式中的一个非零项，它由三个域组成，分别表示非零项个非零项，它由三个域组成，分别表示非零项的系数、指数和指向下一个结点的指针。的系数、指数和指向

26、下一个结点的指针。设两个一元多项式为设两个一元多项式为:求此两一元多项式之和求此两一元多项式之和C(x)=A(x)+B(x)C(x)=A(x)+B(x)。35C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院3.3.运算规则运算规则将二个一元多项式中所有指数相同项的系数相加，将二个一元多项式中所有指数相同项的系数相加，相加后，若和不为零，则构成相加后，若和不为零，则构成“和一元多项式和一元多项式”中的一项；中的一项；若和为零，则若和为零，则“和一元多项式和一元多项式”中无此项；中无此项；所有指数不相同的项均抄到所有指数不相同的项均抄到“和一

27、元多项式和一元多项式”中。中。36C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院37C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院习题与练习习题与练习一、基础知识题一、基础知识题1.1.试比较顺序表与链表的优缺点。试比较顺序表与链表的优缺点。2.2.试分析单链表与双链表的优缺点。试分析单链表与双链表的优缺点。3.3.为什么在单循环链表中设置尾指针比设置头指针为什么在单循环链表中设置尾指针比设置头指针更好？更好？4.4.写出在循环双链表中的写出在循环双链表中的p p所指结点之后插入

28、一个所指结点之后插入一个s s所指结点的操作。所指结点的操作。5.5.写出在单链表中的写出在单链表中的p p所指结点之前插入一个所指结点之前插入一个s s所指所指结点的操作。结点的操作。38C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院一一.有两个循环单链表，头指针分为有两个循环单链表，头指针分为headhead1 1和和headhead2 2，编写函数将链表编写函数将链表headhead2 2链接到链表链接到链表headhead1 1之后，链接之后，链接后的链表仍保持是循环链表的形式。后的链表仍保持是循环链表的形式。提示：先分别找到两

29、个链表的表尾，将提示：先分别找到两个链表的表尾，将headhead1 1的表尾指的表尾指向向headhead2 2,将两个链表链接起来将两个链表链接起来;然后将然后将headhead2 2链表的链表的表尾指向表尾指向headhead1 1，构成新的循环链表。，构成新的循环链表。算法设计题算法设计题39C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院二二 ：给出在双链表中第：给出在双链表中第i i个结点个结点(i0)(i0)之后之后插入一个元素为插入一个元素为x x的结点的函数的结点的函数。提示：在前面双链表一节中，已经给出了提示：在前面双

30、链表一节中，已经给出了在一个结点之前插入一个新结点的方法，在一个结点之前插入一个新结点的方法，在一个结点之后插入一个新结点的思想与在一个结点之后插入一个新结点的思想与前面是一样的。前面是一样的。40C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院第一题算法link(node*head1,head2)node*p,*q;p=head1;while(p-next!=head1)p=p-next;q=head2;while(q-next!=head2)q=q-next;p-next=head2;q-next=head1;41C C C C语言与

31、程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院例例二二算算法法void insert(node*head,int i,x)node*s,*p;int j;s=(node*)malloc(size of(node);/*/*建立一个待插入的结点，由建立一个待插入的结点，由s s指向指向*/s-data=x;if(i=0)/*/*如如i=0,i=0,将将s s所指结点插入到表头后返回所指结点插入到表头后返回*/s-rlink=head;head-Llink=s;head=s;42C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数

32、计学院江汉大学数计学院例例二二算算法法续续 else p=head;/*/*查找第查找第i i个结点，由个结点，由p p指向指向*/j=1;while(p!=NULL&jnext;if(p!=NULL)/*/*若查找成功，把若查找成功，把s s插入到插入到p p之后之后*/if(p-rlink=NULL)/*/*若若p p是最后一个结点，则直接把是最后一个结点，则直接把s s结点链入结点链入*/43C C C C语言与程序设计语言与程序设计语言与程序设计语言与程序设计 江汉大学数计学院江汉大学数计学院例例二二算算法法续续2 2 p-rlink=s;s-rlink=NULL;s-Llink=p;else s-rlink=p-rlink;s-Llink=p;p-rlink-Llink=s;p-rlink=s;else printf(“未找到未找到!n”);返回44