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

1,第二讲线性表,线性结构特点：在数据元素的非空有限集中:存在唯一的一个被称作“第一个”的数据元素.存在唯一的一个被称作“最后一个”的数据元素.除第一个外，集合中的每个数据元素均只有一个前驱.除最后一个外，集合中的每个数据元素均只有一个后继.,2,2.1线性表的逻辑结构定义：一个线性表是n个数据元素的有限序列,例1英文字母表（A,B,C,.Z)是一个线性表,特征：元素个数n=表长度，n=0空表1link表示p指向结点的指针域;,2.3.1单链表定义：结点中只含一个指针域的链表叫单链表.,17,单链表的基本运算,查找：查找单链表中是否存在结点X，若有则返回指向X结点的指针；否则返回NULL.(不带头节点),算法描述：ListNode*find(ListNodehead,intx)ListNode*p;P=head;while(p,18,2.单链表的插入,实现插入算法主要完成三个基本操作：1)在单链表上找到插入位置，即找到第i个结点。可以用遍历的方法，即从表头起顺次访问单链表的结点，直至找到第i个结点。2)生成一个以x为值的新结点。可通过C的库函数malloc(size)来产生。3)将新结点链入单链表中。需要改变相关结点的指针，如下面的图所示。,单链表的插入:所谓插入是指在单链表中第i个结点(i0)之后插入一个元素为x的结点。,19,假设指针p指向单链表中的第i个结点，指针s指向已生成的新结点，链入新结点的操作如下：将新结点*s的链域指向结点*p的后继结点(即s-next=p-next)；将结点*p的链域指向新结点(即p-next=s)。,20,插入算法,voidinsert(node*head,inti,x)node*s,*p;intj;s=(node*)malloc(sizeof(node);/*生成新结点*/s-data=x;if(i=0)/*如果i=0,则将s所指结点插入到表头*/s-next=head;head=s;elsep=head;j=1;/*查找第i个结点，由p所指向*/,21,插入算法续,while(p!=NULL,22,3.单链表的删除,删除单链表上一个其值为x的结点的主要操作是：1)用遍历的方法在单链表上找到该结点；2)从单链表上删除该结点。注意:从单链表上删除一个结点，需修改该结点的前一个结点的指针，如下面的图所示。,23,假设指针q指向待删除结点的前一个结点，指针p指向要删除的结点，删除该结点的操作如下：将该结点的前一个结点*q的链域指向*p的后继结点（即q-next=p-next）。,24,删除算法,voiddelete(node*head,intx)node*p,*q;if(head=NULL)printf(“链表下溢！n”);/*判空*/if(head-data=x)/*如表头结点值等于x*/p=head;head=head-next;free(p);elseq=head;/*从第二个结点开始查找*/p=head-next;,x,head,25,删除算法续,while(p!=NULL,26,核心代码：while(ch!=n)p=(node*)malloc(sizeof(Node);p-data=ch;p-next=head;head=p;ch=getchar();,补充:动态建立单链表算法头插法建表：该方法是从一个空表开始，重复的读入数据，生成新的节点，将数据存放到数据域中，然后将新节点插入到表头，只到遇到结束标志为止。,p,27,单链表特点：它是一种动态结构，整个存储空间为多个链表共用。不需预先分配空间。指针占用额外存储空间。不能随机存取，查找速度慢。,28,2.3.2循环链表(circularlinkedlist)(补充)环链表是表中循最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p-link!=NULL循环链表p-link!=H/*从表头开始,29,1.在循环链表CL中检索值为e的数据元素NODE*find(NODE*head,e)NODE*p;for(p=head-next;(p!=head),30,在循环链表中,访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。问题：循环链表并不适用于经常访问前驱结点的情况,怎么办?,解决方法：在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。所谓双向链表,双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。,2.3.3双向循环链表,31,双向链表就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点,(a),(b),Typedefstructnodeintdata;structnode*llink,*rlink;JD;,32,voiddel_dulist(JD*p)(p-Llink)-rlink=p-rlink;(p-rlink)-Llink=p-Llink;free(p);,双向链表删除一个节点,(p-Llink)-rlink=p-rlink;,(p-rlink)-Llink=p-Llink;,33,voidins_dulist(Node*p,intx)Node*s;s=malloc(sizeof(Node);s-data=x;s-Llink=p-Llink;(p-Llink)-rlink=s;s-rlink=p;p-Llink=s;,插入一个节点,34,3.链表的应用3.1一元多项式的算术运算,设一个一元多项式为如果用数组来表示一元多项式，以各项的指数作为下标，将各个系数存入一维数组中。,35,2.用单链表表示一元多项式,将单链表的每个结点对应着一元多项式中的一个非零项，它由三个域组成，分别表示非零项的系数、指数和指向下一个结点的指针。设两个一元多项式为:求此两一元多项式之和C(x)=A(x)+B(x)。,36,3.运算规则,将二个一元多项式中所有指数相同项的系数相加，相加后，若和不为零，则构成“和一元多项式”中的一项；若和为零，则“和一元多项式”中无此项；所有指数不相同的项均抄到“和一元多项式”中。,37,38,习题与练习,一、基础知识题1.试比较顺序表与链表的优缺点。2.试分析单链表与双链表的优缺点。3.为什么在单循环链表中设置尾指针比设置头指针更好？4.写出在循环双链表中的p所指结点之后插入一个s所指结点的操作。5.写出在单链表中的p所指结点之前插入一个s所指结点的操作。,39,一.有两个循环单链表，头指针分为head1和head2，编写函数将链表head2链接到链表head1之后，链接后的链表仍保持是循环链表的形式。提示：先分别找到两个链表的表尾，将head1的表尾指向head2,将两个链表链接起来;然后将head2链表的表尾指向head1，构成新的循环链表。,算法设计题,40,二：给出在双链表中第i个结点(i0)之后插入一个元素为x的结点的函数。提示：在前面双链表一节中，已经给出了在一个结点之前插入一个新结点的方法，在一个结点之后插入一个新结点的思想与前面是一样的。,41,第一题算法,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;,42,例二算法,voidinsert(node*head,inti,x)node*s,*p;intj;s=(node*)malloc(sizeof(node);/*建立一个待插入的结点，由s指向*/s-data=x;if(i=0)/*如i=0,将s所指结点插入到表头后返回*/s-rlink=head;head-Llink=s;head=s;,43,例二算法续,elsep=head;/*查找第i个结点，由p指向*/j=1;while(p!=NULLif(p!=NULL)/*若查找成