数据结构之链表课件.ppt

1、SCIE,University of Electronic Science and Technology of China12.1线性表线性表线性表不同的实现方式：2.1.1顺序表 数组存储 顺序表定义 顺序表基本操作：遍历、插入、删除 顺序表算法分析2.1.2单链表2.1.3双向链表 链接存储2.1.4循环链表SCIE,University of Electronic Science and Technology of China22.1线性表线性表#include stdio.h“struct list_seq int data20;int length;int main()struct

2、list_seq list;int no,i;list.length=0;for(i=0;inext=null;带头节点单链表对链表尾的判断空表：p-next=null;非空表：p-next=null;SCIE,University of Electronic Science and Technology of China92.1.2单链表单链表初始化算法：elemtype initlist(node*h)*h=(node*)malloc(sizeof(node);(*h)-next=null;三、链表的基本操作访问插入删除SCIE,University of Electronic Scien

3、ce and Technology of China102.1.2单链表单链表n访问操作p问题描述：访问链表的第i个节点p问题分析：输入：链表，i输出：链点指向链点的指针p算法实现分析：只能从链表头开始，一个一个“数”下去，直到第i个。a1anheadtaila2temptemptempSCIE,University of Electronic Science and Technology of China112.1.2单链表单链表从自然语言到算法语言从自然语言到算法语言n如何描述我们找到第i个节点的动作。p 1、先找到链表首结点的地址p 2、通过“地址”，找到链点p 3、在链点中找到后继元素

4、的“地址”p 4、记录这个地址p=list-head;while()p-data p=p-next;p-next SCIE,University of Electronic Science and Technology of China122.1.2单链表单链表 继续完善描述继续完善描述p 1、先找到链表首结点的地址p 2、通过“地址”，找到链点p 3、在链点中找到后继元素的“地址”p 4、记录这个地址，回到2p=list-head;while(1)p-data p=p-next;p-next,计数，如果计数到i，就结束counter=1;counter+;if(counter=i)break

5、;SCIE,University of Electronic Science and Technology of China132.1.2单链表单链表node_type*get_node(list,i)while(counter next;int counter;node_type*p;return p;if(p=NULL)return NULL;p=list-head;counter=1;a1nextaiai+1an pa2逐个“数”的动作counter：1 23设i 3当in时算法结果怎样？思考SCIE,University of Electronic Science and Techno

6、logy of China142.1.2单链表单链表n注意1、p=p-next;沿链表前进2、循环结束条件counter=i 或 node=NULLcounter list-length思考如果希望获得值为x的元素，如何实现？while(p-data=x&p!=NULL)SCIE,University of Electronic Science and Technology of China152.1.2单链表单链表n链表插入操作p问题描述：在元素ai前插入新的元素new_node;p问题分析：输入：链表，location，x输出：插入新元素后的链表。p算法实现分析SCIE,Universit

7、y of Electronic Science and Technology of China162.1.2单链表单链表a1aianheadtailai-1.anewa1aianheadtailai-1.anew两个步骤：ai-1-next=anew;anew-next=ai;SCIE,University of Electronic Science and Technology of China172.1.2单链表单链表SCIE,University of Electronic Science and Technology of China182.1.22.1.2单链表单链表while(co

8、unter next;void insertl（list,new_node,location）找到ai-1p-next=new_node;new_node-next=?ai-1-next=anew;anew-next=ai;a1ai-1aianpnewnodea2p list-header;counter=1qq=p-next;q;法一SCIE,University of Electronic Science and Technology of China192.1.2单链表单链表while(counter next;void insertl（list,new_node,location）ne

9、w_node-next=p-next;p-next=new_node;a1ai-1aianpnewnodea2p list-header;counter=1法二SCIE,University of Electronic Science and Technology of China202.1.2单链表单链表void insertl（list,new_node,location）while(counter next;new_node-next=p-next;p-next=new_node;counter=1;p=list-head;初始化list-length+;边界情况：表首插入表尾插入SCI

10、E,University of Electronic Science and Technology of China212.1.2单链表单链表a1ai-1aianlist-headnewnodenew_node-next=a1;list-head;list-head=new_node;SCIE,University of Electronic Science and Technology of China222.1.22.1.2单链表单链表void insertl（list,new_node,location）while(counter next;new_node-next=p-next;p-

11、next=new_node;counter=1;p=list-head;初始化if(location=1)elsenew_node=list-head;list-head=new_node;list-length+;边界情况：表首插入表尾插入SCIE,University of Electronic Science and Technology of China232.1.22.1.2单链表单链表a1ai-1aianlist-head注意当循环执行到表尾时p 的值为NULL（空）p-next是悬空的值while(counter next;new_node-next=p-next;p-next=

12、new_node;p-next!=NULL)NULL p因此循环结束应以p-next=NULL为条件当i 链表长度 时会造成系统崩溃表尾插入SCIE,University of Electronic Science and Technology of China242.1.2单链表单链表void insertl（list,new_node,location）while(counter next!=NULL)counter=counter+1;p=p-next;new_node-next=p-next;p-next=new_node;counter=1;p=list-head;if(locati

13、on=1)elsenew_node-next=list-head;list-head=new_node;list-length+;SCIE,University of Electronic Science and Technology of China252.1.2单链表单链表从插入算法中对链表操作的体会从插入算法中对链表操作的体会n1、链表操作往往从表头开始，逐个找到需要的链点n2、链表操作的有向性 不能回退；n3、链表指针小心使用，谨防丢失。n4、不能访问空指针的成员n5、插入过程没有进行链点内容进行搬移。SCIE,University of Electronic Science and

14、Technology of China262.1.2单链表单链表n链表的删除操作p问题描述：删除元素ai;p问题分析：输入：链表，location输出：删除元素后的链表。p算法实现分析SCIE,University of Electronic Science and Technology of China272.1.2单链表单链表a1ai+1anheadtailai-1.aiai-1-next =ai-next;即ai-1-next=ai-1-next-next;SCIE,University of Electronic Science and Technology of China282.1

15、.22.1.2单链表单链表找到ai-1执行删除动作ai-1-next=ai-1-next-nextvoid deletel（list,location）注意，从链表上取下的链点ai-1需要挂在一个指针上，否则可能丢失a1ai+1anheadtailai-1.aitempSCIE,University of Electronic Science and Technology of China292.1.2单链表单链表void deletel（list,location）while(counter next;p-next=p-next-next;counter=1;p=list-head;初始化i

16、f(location=1)elselist-head=list-head-next;temp=p-next;free(temp);temp=list-head;free(temp);list-length-;从链表删除的链点，一般应该释放其空间SCIE,University of Electronic Science and Technology of China302.1.2单链表单链表n注意:p对被删除删除链点的处理往往需要要free（）SCIE,University of Electronic Science and Technology of China312.1.2单链表单链表四、链

17、表的特点p、操作的顺序性有平均次查找过程。p、离散存放不受链表大小限制不进行链点内容的搬移p查找操作：数组效率优于链表p插入、删除操作：链表效率优于数组SCIE,University of Electronic Science and Technology of China322.1.2单链表单链表作业作业 教材74页第9题（用链表实现）、第10题SCIE,University of Electronic Science and Technology of China332.1.3 双向链表双向链表n 特点：每一个链点包含两个指针，前趋指针后继指针a1headtailNa2NPanPa1NPP

18、：priorN：nextSCIE,University of Electronic Science and Technology of China342.1.3双向链表双向链表一、双向链表的定义struct double_link_node_typestruct double_link_node_type*prior;struct double_link_node_type*next;elemtype data;struct double_link_list_typedl_node_type*head;dl_node_type*tail;int length;链点的定义链表的定义SCIE,Un

19、iversity of Electronic Science and Technology of China352.1.32.1.3双向链表双向链表二、双向链表的插入操作ai-1ai问题描述：在第i个元素前插入新元素anewp2、anew-next=p;1、p-prior-next=anew;3、anew-prior=p-prior;4、p-prior=anew;可以有几种插入方法？SCIE,University of Electronic Science and Technology of China362.1.3双向链表双向链表n算法实现（略）p找到aip执行插入操作n体会p插入操作有多种

20、方式实现，步骤比较复杂p双向链表的使用灵活，可进可退通过这个练习，加强链表指针操作的训练SCIE,University of Electronic Science and Technology of China372.1.32.1.3双向链表双向链表三、双向链表的删除操作p问题描述：删除第i个元素ai-1aiai1ppp（1）（2）（3）（1）当p在ai1处时p-next-next-prior=p;p-next=p-next-nextq=p-nextfree(q)SCIE,University of Electronic Science and Technology of China382.1

21、.32.1.3双向链表双向链表三、双向链表的删除操作p问题描述：删除第i个元素ai-1aiai1ppp（1）（2）（3）（2）当p在ai处时课堂作业请完成算法（3）当p在ai+1处时SCIE,University of Electronic Science and Technology of China392.1.42.1.4循环链表循环链表a1ai+1anheadtailai-1.ai将链表头尾相接headerai+1antaila1.ai对循环链表的遍历可以从任何一个节点开始SCIE,University of Electronic Science and Technology of China402.1.4循环链表循环链表n作业：p完成以下算法片段：1、删除双向链表的ai元素时，指针P现在指向ai元素。2、删除双向链表的ai元素时，指针P现在指向ai+1元素