实用数据结构电子教案链表公开课一等奖优质课大赛微课获奖课件.pptx

单击此处编辑母版标题样式,第三章 链表,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,第,三,章 链表,第1页,第1页,第,三,章 链表,知 识 点,单链表结点形式、组织办法和特点,单链表基本运算和相应算法,循环链表组织办法和基本运算算法,双链表结点形式、组织办法和特点,双链表基本运算和相应算法,顺序表与链表比较，各自优、缺点,链表应用,用十字链表表示稀疏矩阵,第三章 链表,第2页,第2页,难 点,双链表插入、删除运算算法,利用链接结构特点设计有效算法，处理与链表结构相关应用问题,要 求,纯熟掌握下列内容:,单链表结构特点、基本运算并能设计简朴算法,循环链表结构特点、基本运算并能设计简朴算法,双链表结构特点、基本运算并能设计简朴算法,理解下列内容：,用十字链表表示稀疏矩阵,链接堆栈，链接队列应用以及一元多项式加法应用实例,第三章 链表,第3页,第3页,第,三,章目录,3.1 单链表及其运算,3.2 循环链表与双向链表,3.3 链表应用举例,3.4 表示稀疏矩阵十字链表,3.5 应用举例及分析,小 结,习题与练习,第三章 链表,第4页,第4页,3.1.1,单链表,1.结点:在链式存储结构中，结点不但存储数据元素值，还附加一个指针（链），用来指向该结点直接后继结点。,其中，data部分称为数据域，用于存储线性表一个元素，next部分称为指针域或链域，用于存储一个指针，即存储该结点直接后继结点地址。,第三章 链表,第5页,第5页,2.,单链表,所有结点通过指针链接而构成线性表称为单链表。线性表（a,1,，a,2,，a,n,，）单链表可直观地画成：,head是单链表头指针，指向开始结点a,1,a,n,是终端结点，其指针域为空，不指向任何结点。,一个单链表由头指针head唯一标识和拟定，因此，可用头指针来命名单链表。,第三章 链表,第6页,第6页,3.,单链表类型定义,假设线性表中数据元素类型为datatype，单链表类型定义下列：,typedef struct node*pointer;,struct node,datatype data;,pointer next;,;,typedef pointer linklist;,一个结点是由两个域data和next构成统计,data是结点数据域，next是结点链域。,第三章 链表,第7页,第7页,4.,指针概念,假设p是一个pointer类型，应正确区分指针型变量、指针、指针所指结点和结点内容这四个密切相关不同概念：,p值（假如有话）是一个指针，即是一个所指结点地址。,该指针（若不是NULL）指向某个node型结点用*p来标识。,结点*p是由两个域组成统计，这两个域分别用pdata域和pnext域来标识，它们各有自己值，pdata值是一个数据元素，pnext值是一个指针。,第三章 链表,第8页,第8页,3.1.2,单链表基本运算,1.遍历(Traversal)：依据已给表头指针，按由前向后顺序访问单链表各个结点。,在实际应用中遍历是对单链表最基本运算，比如，当要打印或显示出各个结点数值域值、计算单链表长度(即结点数目)或寻找某一个结点时都需要遍历单链表。,假设head是单链表头指针，计算一个已建立好单链表结点个数算法下列：,第三章 链表,第9页,第9页,计算结点个数算法,int length(node*head)/*求表head长度*/,int count=0;/*计数器置初值*/,node*p=head;/*p指向头结点*/,while(p!=NULL),p=p,-,next;,count+;,return(count);/*返回表长值*/,第三章 链表,第10页,第10页,算法分析,此算法关键是while循环语句，开始时p指针指向头结点，每一循环都修改指针值，让它指向下一个结点，同时将计数链表长度变量count加1。,这样每循环一次就向后推移一个结点，直到p所指结点*p链域值为NULL为止。,空指针NULL起标志作用，若无此标志，尾结点链域值为“无定义”，上述算法中while语句在做最后一次判断时将出现“运营错”，这是应予避免。,第三章 链表,第11页,第11页,2.插入,所谓插入是指在单链表中第i个结点(i0)之后插入一个元素为x结点。,实现插入算法主要完毕三个基本操作：,1)在单链表上找到插入位置，即找到第i个结点。,能够用遍历办法，即从表头起顺次访问单链表结点，直至找到第i个结点。,2)生成一个以x为值新结点。,可通过C库函数malloc(size)来产生。,3)将新结点链入单链表中。,需要改变相关结点指针，下列面图所表示。,第三章 链表,第12页,第12页,假设指针p指向单链表中第i个结点，指针s指向已生成新结点，链入新结点操作下列：,将新结点*s链域指向结点*p后继结点,(即s-next=p-next)；,将结点*p链域指向新结点(即p-next=s)。,第三章 链表,第13页,第13页,插入算法,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,则将s所指结点插入到表头*/,s-next=NULL;,head=s;,else,p=head;,j=1;/*查找第i个结点，由p所指向*/,第三章 链表,第14页,第14页,插入算法续,while(p!=NULL&jnext;,if(p!=NULL)/*把新结点插入其后*/,s-next=p-next;,p-next=s;,else,printf(“未找到！n”);,第三章 链表,第15页,第15页,3.删除,当需要从单链表上删除结点时，就要通过删除运算来完毕。,删除单链表上一个其值为x结点主要操作是：,1)用遍历办法在单链表上找到该结点；,2)从单链表上删除该结点。,欲从单链表上删除一个结点，需修改该结点前一个结点指针，下列面图所表示。,第三章 链表,第16页,第16页,假设指针q指向待删除结点前一个结点，指针p指向要删除结点，删除该结点操作下列：将该结点前一个结点*q链域指向*p后继结点（即q-next=p-next）。,第三章 链表,第17页,第17页,删除算法,void delete(node*head,int x),node*p,*q;,if(head=NULL),printf(“链表下溢！n”);/*判空*/,if(head-data=x)/*如表头结点值等于x*/,p=head;,head=head-next;,free(p);,else,q=head;/*从第二个结点开始查找*/,p=head-next;,第三章 链表,第18页,第18页,删除算法续,while(p!=NULL&p-data!=x),q=p;,p=p-next;,if(p!=NULL)/*找到该结点，删除*/,q-next=p-next;,free(p);,else,printf(“未找到！n”);,返回,第三章 链表,第19页,第19页,3.2.1,循环链表,循环链表（circular linked list）是一个首尾相接链表，将单链表表尾结点本来空指针改为指向表头结点，就成为循环链表。,循环链表并不多占存储单元，但从循环链表任一个结点出发都能够访问到此链表每一个结点，由于当访问到表尾结点后又能返回到头结点。,第三章 链表,第20页,第20页,1.,带头指针循环链表,通常在循环链表表头结点前面再加一个空结点,也叫空表头结点。,表空时空表头结点指针指向其本身，下列面图所表示为空循环链表。,空表头结点除指针以外数据域是没有用，但为了将此结点与普通结点相区别，经常是将其赋以一个尤其数据，以与普通结点相区别。,第三章 链表,第21页,第21页,2.,带尾指针循环链表,另一个办法是不设头指针而改设尾指针，这样无论是找头结点还是尾结点都很以便。由于尾结点由尾指针rear来批示，则头结点位置是rear-next-next。,第三章 链表,第22页,第22页,3.2.2,双链表,双向链表中每个结点除了有向后指针外，还有指向其前一个结点指针，这么形成链表中有两条不同方向链，因此从某一结点均可向两个方向访问。,双链表结点形式为：,其中链域prior和next分别指向本结点直接前趋和直接后继结点。,第三章 链表,第23页,第23页,假如循环链表结点再采用双向指针，就成为双向循环链表。,第三章 链表,第24页,第24页,双链表较单链表即使要多占用一些存储单元，但对其插入和删除操作以及查找结点前趋和后继都非常以便。,双链表结构是一个对称结构，设指针p指向双链表某一结点，则双链表对称性可用下式来表示：,p=(p-prior)-next=(p-next)-prior,即结点*p地址既存储在其前趋结点,*(p-prior)后继指针域中，又存储在它后继结点*(p-next)前趋指针域中。,第三章 链表,第25页,第25页,1.,双链表插入,设要在p所指结点前面插入一个新结点*q，则需要修改4个指针：,q-prior=p-prior;,q-next=p;,(p-prior)-next=q;,p-prior=q;,第三章 链表,第26页,第26页,2.,双链表删除,设p指向待删除结点，则删除该结点环节为：,(p-prior)-next=p-next;,(p-next)-prior=p-prior;,这两个语句执行顺序能够颠倒，执行这两个语句之后，可调用free(p),将*p结点释放。,返回,第三章 链表,第27页,第27页,3.3.1,链堆栈,链堆栈是栈链接存放表示，它是只允许在表头进行插入和删除运算单链表。,它与普通单链表没有什么不同，只是将头指针head改称为栈顶指针top。,第三章 链表,第28页,第28页,链堆栈入栈算法,在栈顶指针是top链堆栈中插入一个值为x结点算法：,void push(node*top,int x),node*s;,s=(node*)malloc(sizeof(node);,/*建立一个结点指针*/,s-data=x;,s-next=top;,top=s;,第三章 链表,第29页,第29页,链堆栈出栈算法,int pop(node*top),int x;,node*p;,if(top=NULL),printf(“栈为空!n”);,else,x=top-data;,p=top;,top=top-next;,free(p);,return(x);,第三章 链表,第30页,第30页,3.3.2,链队列,链队列需要两个指针，其中队首指针front指向链表表头，队尾指针rear指向链表表尾。,普通插入时只修改队尾结点指针和队尾指针rear，删除时只修改队首指针front。当将第一个元素插入空队列或删除了最后一个元素而使队列为空时，front和rear都需要修改。,第三章 链表,第31页,第31页,链队列插入算法,void insert(node*front,rear,int x),node*s;,s=(node*)malloc(sizeof(node);,s-data=x;,s-next=NULL;,if(rear=NULL)/*处理空队列情况*/,front=s;,rear=s;,else,rear-next=s;,rear=s;,第三章 链表,第32页,第32页,链队列删除算法,int delete(node*front,rear),node*p;,int x;,if(front=NULL),printf(“空队列!n”);,else,x=front-data;,p=front;,if(front=rear),front=NULL;,rear=NULL;,else,front=front-next;,free(p);,return(x);,第三章 链表,第33页,第33页,3.3.3,一元多项式算术运算,设一个一元多项式为,1.假如用数组来表示一元多项式，以各项指数作为下标，将各个系数存入一维数组中。,第三章 链表,第34页,第34页,2.,用单链表表示一元多项式,将单链表每个结点相应着一元多项式中一个非零项，它由三个域构成，分别表示非零项系数、指数和指向下一个结点指针。,设两个一元多项式为:,求此两一元多项式之和C(x)=A(x)+B(x)。,第三章 链表,第35页,第35页,3.,运算规则,将二个一元多项式中所有指数相同项系数相加，相加后，若和不为零，则构成“和一元多项式”中一项；,若和为零，则“和一元多项式”中无此项；,所有指数不相同项均抄到“和一元多项式”中。,第三章 链表,第36页,第36页,返回,第三章 链表,第37页,第37页,3.4,表示稀疏矩阵十字链表,在十字链表中，矩阵每个非零元素相应着一个含有五个域结点，这五个域分别为该非零元素在稀疏矩阵中行号、列号、元素数值以及两个指针，其中一个指针指向同一列下一个非零元素结点，另一个指针指向同一行右边一个非零元素结点。,第三章 链表,第38页,第38页,将每行非零元素结点链接成循环链表，又将每列非零元素结点链接成循环链表，就构成了十字形链接结构。,对于每行、每列循环链表都有一个空表头结点，以利于元素插入和删除运算。这些空表头结点行号、列号都标成零，以便和其它结点相区别。,整个十字链表有一个总空表头结点，在普通结点标以行号、列号之处，此结点是标出矩阵行数m和列数n。,有一个指针HM指向这个总空表头结点。,第三章 链表,第39页,第39页,例：稀疏矩阵M及其相应十字链表如图所表示。,第三章 链表,第40页,第40页,第三章 链表,第41页,第41页,空表头结点结构,因各列、各行空表头结点中行号和列号都是零，且每列空表头结点只用到向下指针，每行空表头结点只用到向右指针，故可将这组空表头结点合用。,由于数值域也没有用，可将空表头结点数值域改为一个指针域，将各个空表头结点也链接成一个循环链表。,返回,第三章 链表,第42页,第42页,例,3.1,有一个单链表L(至少有一个结点)，其头结点指针为head，编写一个函数将L逆置，即最后一个结点变成第1个结点，本来倒数第二个结点变成第二个结点如此等等。,解：本题采用算法是，从头到尾遍历单链表L，并设置3个附加指针p、q、r,p指向当前处理结点，q指向p下一个结点，r指向q下一个结点，q、r作用是为了预防倒置指针时，下一个结点丢失而设置，有了这三个指针，就能够以便地实现指针倒置。最后将第一个结点next域置为NULL，并将头指针指向最后一个结点，这样达到了本题要求。,第三章 链表,第43页,第43页,例,3.1算法,void invert(node*head),node*p,*q,*r;,p=head;,q=p-next;,while(q!=NULL)/*没有后继时停止*/,r=q-next;,q-next=p;,p=q;,q=r;,head-next=NULL;,head=p;,第三章 链表,第44页,第44页,例,3.2,有两个循环单链表，头指针分为head,1,和head,2,，编写函数将链表head,2,链接到链表head,1,之后，链接后链表仍保持是循环链表形式。,解：先分别找到两个链表表尾，将head,2,放入链表head,1,表尾，将两个链表链接起来，然后将head,1,放入原head,2,链表表尾，构成新循环链表。,第三章 链表,第45页,第45页,例,3.2算法,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;,第三章 链表,第46页,第46页,例,3.3,给出在双链表中第i个结点(i0)之后插入一个元素为x结点函数。,解：在前面双链表一节中，已经给出了在一个结点之前插入一个新结点办法，在一个结点之后插入一个新结点思想与前面是同样。,第三章 链表,第47页,第47页,例,3.3算法,void insert(dnode*head,int i,x),dnode*s,*p;,int j;,s=(dnode*)malloc(sizeof(dnode);,/*建立一个待插入结点，由s指向*/,s-data=x;,if(i=0),/*如i=0,将s所指结点插入到表头后返回*/,s-next=head;,head-prior=s;,head=s;,第三章 链表,第48页,第48页,例,3.3算法续,else,p=head;,/*查找第i个结点，由p指向*/,j=1;,while(p!=NULL&jnext;,if(p!=NULL),/*若查找成功，把s插入到p之后*/,if(p-next=NULL),/*若p是最后一个结点，则直接把s结点链入*/,第三章 链表,第49页,第49页,例,3.3算法续,p-next=s;,s-next=NULL;,s-prior=p;,else,s-next=p-next;,p-next-prior=s;,p-next=s;,s-prior=p;,else,printf(“未找到!n”);,返回,第三章 链表,第50页,第50页,小结,单链表,循环链表,双向链表,双向循环链表,十字链表,返回,第三章 链表,第51页,第51页,习题与练习,一、基础知识题,1.试比较顺序表与链表优缺点。,2.试分析单链表与双链表优缺点。,3.为何在单循环链表中设置尾指针比设置头指针更加好？,4.写出在循环双链表中p所指结点之后插入一个s所指结点操作。,5.写出在单链表中p所指结点之前插入一个s所指结点操作。,6.请利用链表来表示下面一元多项式,第三章 链表,第52页,第52页,二、算法设计题,1.有一个有n个结点单链表，设计一个函数将第i-1个结点与第i个结点互换，但指针不变。,2.设计一个函数，查找单链表中数值为x结点。,3.已知一个单链表，编写一个删除其值为x结点前趋结点算法。,4.已知一个单链表，编写一个函数从此单链表中删除自第i个元素起length个元素。,第三章 链表,第53页,第53页,5.已知一个递增有序单链表，编写一个函数向该单链表中插入一个元素为x结点，使插入后该链表仍然递增有序。,6.已知一个单链表，编写一个函数将此单链表复制一个拷贝。,7.有一个共10个结点单链表，试设计一个函数将此单链表分为两个结点数相等单链表。,8.与上题相同单链表，设计一个函数，将此单链表分成两个单链表，要求其中一个仍以原表头指针head,1,作表头指针，表中顺序包括原线性表第一、三等奇数号结点；另一个链表以head,2,为表头指针，表中顺序包括原单链表第二、四等号结点。,第三章 链表,第54页,第54页,9.已知一个指针p指向单循环链表中一个结点，编写一个对此单循环链表进行遍历算法。,10.已知一个单循环链表，编写一个函数，将所有箭头方向取反。,11.在双链表中，若仅知道指针p指向某个结点，不知头指针，能否依据p遍历整个链表？若能，试设计算法实现。,12.试编写一个在循环双向链表中进行删除操作算法，要求删除结点是指定结点p前趋结点。,返回,第三章 链表,第55页,第55页,谢谢收看,返回,第三章 链表,第56页,第56页,