《计算机软件技术程编基础链表.ppt》由会员分享，可在线阅读，更多相关《计算机软件技术程编基础链表.ppt（43页珍藏版）》请在三一办公上搜索。
1、顺序表的 特点：运算：简单，时间复杂度好存储特性：静态规模，编译前确定问题：程序的通用性和空间利用率之间的矛盾期望：在实际运行过程中，根据实际问题的需要临时确定存储空间，涉及到动态变量动态变量：在程序运行的过程中产生和释放的变量。与之相反的是静态变量静态变量：在程序运行的过程中一直存在的变量。静态变量是出现在说明语句中的变量；动态变量由于是在运行中产生的，因而不会事先说明如何实现动态变量？通过指针来实现：指针变量的说明，动态变量的产生和释放。,2.3 线性链表及其运算,线性表的链式存储结构称为线性链表，即将表中元素用链地址连接起来。,head,头指针,结点,对线性表中的每一个数据元素，都需用两
2、部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。,链表的存储结构,链式存储结构是利用任意的存储单元来存放线性表中的元素，存储数据的单元在内存中可以连续，也可以零散分布。由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系，在这种结构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息，除了存储每一个数据元素值以外，还需存储其后继或前驱元素所在内存的地址。两部分信息一起构成链表中的一个
3、结点。结点的结构如下所示。,链表结构示意图,从图中可见，每个结点的存储地址存放在直接前驱的指针域中。所以要访问链表中数据元素C，必须由头指针head得到第一个结点（数据A）的地址，由该结点的指针域得到第二个结点（数据B）的地址，再由其指针域得到存储数据C的结点地址，访问该结点的数据域就可以处理数据C了。链表这种顺着指针链依次访问数据元素的特点，表明链表是一种顺序存储结构，只能顺序操作链表中元素。不能像顺序表（数组）那样可以按下标随机存取。在链表存储结构中，不要求存储空间的连续性，数据元素之间的逻辑关系由指针来确定。,每个结点由两部分组成：data 数据域存放数据值next指针域存放后继结点的首
4、地址,链表通过每个指针域将n个结点按逻辑次序链接成一个整体。,&b,&c,&d,Head&a,头指针,结点,&b,&c,&a,&,data,next,表头的地址由head指针提供，表尾结点没有直接后继，其指针域应为空指针，指针域为NULL,单向链表,在图所示的链表中，每个结点只有一个指向后继的指针。也就是说访问数据元素只能由链表头依次到链表尾，而不能做逆向访问。称这种链表为单向链表或线性链表。这是一种最简单的链表。对于空链表，头结点的指针域为空。,图2-8（a）为带头结点的空链(b)为带头结点的单链表,定义链表结点结构的一般形式为Struct 结构体名 数据成员表；结构体名*指针变量名；,st
5、ruct studentint num;float score;student*next;,struct ListNode ELEM data；ListNode*next;,167,287,3 79,486,head,tail,/建立链表linklist*create()linklist*head,*p1,*p2;head=NULL;int x;cinx;,struct linklistint num;float score;linklist*next;,p2=p1;/将新的结点作为尾结点p2-next=NULL;cinx;,while(x0),p1=new(linklist);p1-num=
6、x;cinp1-score;n=n+1;,if(head=NULL)head=p1;,else p2-next=p1;,如果是首结点呢？,定义一个新结点,return head;,建立链表的条件,void print()coutnendl;,/链表输出,形参是什么？需要知道链表的头指针,linklist*head,如何查找链表？定义一个指针,linklist*p1;p1=head;,if(head!=NULL)docoutnumscore;coutnext;while(p1!=NULL);,查找运算 的实现 设计思路：设置一个跟踪链表结点的指针p1，初始时p1指向链表中的第一个结点，然后顺着n
7、ext域依次指向每个结点，每指向一个结点就判断其值是否等于i，若是则返回该结点地址,否则继续往后搜索.要访问单链表中第i个元素值，必须从头指针开始遍历链表，依次访问每个结点，直到访问到第i个结点为止。其时间复杂度为O(n)。,linklist*getnode else coutinot been found;return NULL;,/查找（按结点数据域的值查找）,形参是什么？,(linklist*head,int i),linklist*p1;int j=0;p1=head;,定义一个查找指针,while(p1-num!=i,如果该结点不是要找的结点？,if(p1-num=i)j+;cout
8、the node isjendl;return p1;,如果该结点是要找的结点？,linklist*del(linklist*head,int num)linklist*p1,*p2;if(head!=NULL)p1=head;else coutlist is null;return head;,/删除链表指定结点,&p1,&c,&d,p1,&c,p2,P2-next,P1-next,删除条件,if(p1-num=num)if(p1=head)head=p1-next;elsep2-next=p1-next;n=n-1;else coutnumnot been found;,/删除链表指定结点
9、,while(p1-num!=num,如果该结点不是要找的结点？,找到该结点如何删除？,线性链表的插入：在链式存储结构下的线性表中插入一个新结点,在头指针head的线性链表中包含元素x的结点之前加入一个新结点,void inslst(linklist*head,int x)linklist*p1,*p2;p1=new(linklist);cinp1-nump1-score;if(head=NULL)head=p1;p1-next=NULL;p2=getnode(head,x);/寻找包含元素x的结点,p1-next=p2-next;/将结点p1插入到结点p2后p2-next=p1;,在插入和删
10、除算法中，都是先查询确定操作位置，然后再进行插入和删除操作。所以其时间复杂度均为O(n)。另外在算法中实行插入和删除操作时没有移动元素的位置，只是修改了指针的指向，所以采用链表存储方式要比顺序存储方式的效率高,循环链表,循环链表是单链表的另一种形式，是一个首尾相接的链表。特点：最后一个结点的指针域不空，而是指向头结点，整个链表连成环状，从表中任意结点出发均可到达其他结点。,空循环链表,判断表空的条件：,head-next=head,判断指针指向结点为表尾结点的条件：,p-next=head,带头结点的单循环链表的操作算法和带头结点的单链表的操作算法很相似，差别仅在于算法中的循环条件不同。在循环
11、单链表上实现上述基本运算的改动如下：1初始化链表initlist(head)创建的头结点指针域next不为空，而是指向自身head-next=head,2线性表查找运算*getnode(linklist*head,int i)函数、链表元素输出运算print(linklist*head)函数中，循环遍历是否进行的条件由p!=NULL改为p!=head;其余函数运算没有变化，请自行写出相关函数的定义。在循环链表中，除了有头指针head外，有时还可加上一个尾指针tail。尾指针tail指向最后一结点，沿最后一个结点的指针又可立即找到链表的第一个结点。在实际应用中，使用尾指针来代替头指针进行某些操作
12、往往会更简单。【例】将两个循环链表首尾相接进行合并，La为第一个循环链表表尾指针，Lb为第二个循环链表表尾指针，合并后Lb为新链表的尾指针，head指向整个合并后的链表。【解】算法思路：对两个单循环链表La，Lb进行的连接操作，是将Lb的第一个数据结点接到La的尾部。操作时需要从La的头指针开始找到La的尾结点，其时间复杂性为O(n)。而在循环链表中若采用尾指针La，Lb来标识，则时间性能将变为O(1)。其连接过程如图2-14所示。,图 两个循环链表首尾相接进行合并,(a)连接前p=La-next;q=Lb-next,(b)连接后La-next=q;Lb-next=p;,双向链表,双向链表的结
13、点结构,struct dlnode ELEM data；dlnode*next,*prior;,对结点p而言，后继结点的地址p-next;前驱结点的地址p-prior,p,p1,p0,P-prior-next,P-next-prior,P-prior,P-next,s,p1,p0,P1-prior-next=s,P1-prior=s,s-prior=p1-prior,s-next=p1,双向链表中结点的插入,将结点s的插入结点p1之前,p,P-next,P-prior,双向链表中结点的删除,P-prior-next=p-next,P-next-prior=p-prior,delete P,应用
14、举例 一元多项式相加 假设用单链表表示多项式：A(x)=12+7x+8x10+5x17，B(x)=8x+15x7-6x10，头指针Ah与Bh分别指向这两个链表，如图2-21所示：对两个多项式进行相加运算，其结果为C(x)=12+15x+15 x7+2x10+5x17。如图所示。,图 合并以前的链表,图 2-22 合并以后的链表,对两个一元多项式进行相加操作的运算规则是：假设指针qa和qb分别指向多项式A(x)和B(x)中当前进行比较的某个结点，则需比较两个结点数据域的指数项，有三种情况：(1)指针qa所指结点的指数值指针qb所指结点的指数值时，则保留qa指针所指向的结点，qa指针后移；(2)指
15、针qa所指结点的指数值指针qb所指结点的指数值时，则将qb指针所指向的结点插入到qa所指结点前，qb指针后移；(3)指针qa所指结点的指数值指针qb所指结点的指数值时，将两个结点中的系数相加。若和不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A(x)的链表中删除相应结点，并释放指针qa和qb所指结点。,多项式相加算法：struct polynode*add_poly(polynode*Ah,polynode*Bh)polynode*qa,*qb,*s,*r,*Ch;qa=Ah;qb=Bh;/qa和qb分别指向两个链表的第一结点r=qa;Ch=Ah;/将链表Ah作为相加
16、后的结果链表while(qa!=NULL/多项式Bh的指数值小,链栈,top,栈顶,链表的头部作栈顶是最方便的链表的头指针叫做栈顶指针只允许在表头进行插入和删除运算,struct linkstackint num;float score;linkstack*next;,/置空栈linkstack*init_linkstack()return NULL;,/判断栈空int empty_linkstack(linkstack*top)if(top=NULL)return 1;else return 0;,/入栈linkstack*push_linkstack(linkstack*top,links
17、tack*stud)stud-next=top;top=stud;n=n+1;return top;,top,stud,top,top,/出栈linkstack*pop_linkstack(linkstack*top,linkstack*stud)if(top=NULL)return NULL;elsestud=top;top=top-next;n=n-1;return top;,top,top,stud,带链的队列,rear,front,先进先出的数据结构,只允许在表头删除，表尾插入的单链表,struct qnodeint num;struct qnode*next;,struct lque
18、ueqnode*front,*rear;,lqueue*init_lqueue()lqueue*l;qnode*q;l=new(lqueue);q=new(qnode);q-next=NULL;l-front=l-rear=q;return l;,创建一个空队列,front,rear,next,struct qnodeint num;struct qnode*next;,struct lqueueqnode*front,*rear;,void in_lqueue(lqueue*l,qnode*q)q-next=NULL;,/入队,front,rear,next,next,只能在表尾插入结点,l
19、-rear-next=q;,队尾结点的指针域指向新结点,l-rear=q;,rear存入新结点地址,/出队,删除表头结点,front,rear,next,next,next,qnode*out_lqueue(lqueue*l,)qnode*qreturn q;,判断队空的条件,if(l-rear=l-front)return NULL;,取出队首结点地址,q=l-front-next;,l-front-next=q-next;,队首结点地址给下一个结点,作业：P153 2.10 试写出逆转单链表的算法 2.9 试写出循环链表长度的算法上机：星期三晚上7：00（3月27日）,作业讲评：2.10
20、试写出逆转单链表的算法,如何定义一个新结点,struct linklistint num;float score;linklist*next;,如何建立一个新链表,新链表需要头指针head,构造新结点指针p1,1 指针类型的定义-所指变量类型2 申请内存空间分配地址,停止建立链表的条件输入学号为0,结点名字，包含几部分内容,如何将新结点连接到链表中,链表尾部结点如何处理,/建立链表linklist*create()linklist*head,*p1,*p2;head=NULL;int x;cinx;,void main()linklist*head,*rhead;head=create();,
21、p2=p1;/将新的结点作为尾结点p2-next=NULL;cinx;,while(x0),p1=new(linklist);p1-num=x;cinp1-score;n=n+1;,if(head=NULL)head=p1;,else p2-next=p1;,如果是首结点呢？,定义一个新结点,return head;,建立链表的条件,&p2,&p3,next,p2,p3,p1,P2=p1-next,P3=p2-next,p2-next=P1,&p1,next,p2,p3,p1,p1,p2,p3,next,P1=p2,P2=p3,P3=p2-next,p2,表头,表尾如何处理？,如何判断逆转链表到头？,p1=head;p2=p1-next;p1-next=NULL;,While(P2!=NULL)p3=p2-next;p2-next=p1;p1=p2;p2=p3;,表尾,
