数据结构单链表.ppt

上传人:夺命阿水 文档编号:229811 上传时间:2023-03-02 格式:PPT 页数:36 大小:1,023.50KB
返回 下载 相关 举报
数据结构单链表.ppt_第1页
第1页 / 共36页
数据结构单链表.ppt_第2页
第2页 / 共36页
数据结构单链表.ppt_第3页
第3页 / 共36页
数据结构单链表.ppt_第4页
第4页 / 共36页
数据结构单链表.ppt_第5页
第5页 / 共36页
点击查看更多>>
资源描述

《数据结构单链表.ppt》由会员分享,可在线阅读,更多相关《数据结构单链表.ppt(36页珍藏版)》请在课桌文档上搜索。

1、上堂课要点回顾,线性表的抽象数据类型定义顺序表类型定义基本操作实现应用,数据结构课程内容,第 三 次 课,阅读:朱战立,第26-35页练习:作业3,2.3 线性表的链式表示和实现 链表,链式存储结构 定义:用一组任意的存储单元来存放线性表 中的数据元素。特点:逻辑结构上相邻的元素在其存储的物 理位置上不一定相邻。通过指针把链表的存储结点链接成一 个链。,2.3.1 单链表的存储结构,结点结构:链表每个结点中只有一个指针 域指向直接后继结点。,结点类型定义(借用指针类型)typedef int DataType;typedef struct Node DataType data;struct N

2、ode*next;/递归定义 SLNode;/*单链表结点结构体类型SLNode*/,SLNode*head;,数据域:元素本身信息指针域:指示直接后继的存储位置,a0,a1,a2,an-1,head,空表:,非空表:,单链表的逻辑状态,首元结点,l1-next=l2;l2-next=l3;l3-next=NULL;,SLNode*l1=(SLNode*)malloc(sizeof(SLNode);SLNode*l2=(SLNode*)malloc(sizeof(SLNode);SLNode*l3=(SLNode*)malloc(sizeof(SLNode);l1-data=7;l2-data

3、=0;l3-data=6;,l1,l2,l3,sizeof(x)计算变量x的所占的字节数malloc(m)开辟m字节长度的地址空间,并返回这段空间的首地址free(p)释放指针p所指变量的存储空间,即彻底删除一个变量,存储结构,带头结点的单链表:非空表:,空表:,满足 head-next=NULL,头结点是在链表的首元结点之前附设的一个结点;其数据域不存储线性表的数据元素,只放表长等信息;其指针域存储首元结点的地址,头结点,初始化单链表,单链表的操作实现,void ListInitiate(SLNode*head)/置以head为头指针的带头结点的单链表为空表*head=(SLNode*)ma

4、lloc(sizeof(SLNode);(*head)-next=NULL;main()SLNode*head;ListInitiate(.,空表:,读取单链表中第i个结点,思想:从头指针开始,顺着链向后查找。具体:设p为搜索指针,计数器 j 从-1开始计数。初始p指向头结点。循环:p=p-next;j+;直至j=i或至表尾 循环退出后如果j=i 时,p所指结点即为第 i 个结点,否则,表空或 in-1(非法),a0,a1,an-1,ai,head,int ListGet(SLNode*head,int i,DataType*x)/*在以head为头指针的带头结点的单链表中,读取第i个元素*/

5、SLNode*p;int j;p=head;j=-1;/*从头指针开始查找ai*/while(p-next!=NULL/注意:仅当 p!=NULL时,p-data、p-next才有意义,【单链表取元素算法】,|i0,单链表取元素算法的时间复杂度:上述算法的时间复杂度与while语句的频度有关,最坏情况下搜索完整个链表,因此,对于长度为 n 的单链表而言,算法的时间复杂度为 O(n)。,插入前插,思想:要在第 i 个结点之前插入元素 x,必须先找到第 i-1 个结点的地址,这样,才能将第 i-1 个结点的指针修改指向新插入的结点,而新结点的指针指向第 i 个结点。,q-next=p-next;,

6、注意:两条语句的顺序不能颠倒,否则ai的地址会丢失。,另外,要注意合法 i 值为:0i size 若 isize,则 i 值非法。,ai-1,head,a0,p-next=q;,q-next,p-next,q=(SLNode*)malloc(sizeof(SLNode);q-data=x;,int ListInsert(SLNode*head,int i,DataType x)/*在以head为头指针的带头结点的单链表中的第i个结点之前插入值为x的结点*/SLNode*p,*q;/*p:搜索指针,q:新生成指针*/int j;p=head;j=-1;while(p-next!=NULL,【单链

7、表前插算法】,if(j!=i-1)printf(“n插入位置i不合理!”);return 0;/*产生新结点q*/q=(SLNode*)malloc(sizeof(SLNode);q-data=x;/*插入*/q-next=p-next;p-next=q;/*注意:上面两条语句的次序不能颠倒*/return 1;,思想:要删除第 i 个结点,同样必须找到第 i-1 个结点的地址,这样,才能将第 i-1个结点的指针修改指向第 i+1 个结点。,删除,s=p-next;,ai-1,p-next=p-next-next;,free(s);,an-1,ai+1,另外,要注意合法 i 值为:0i siz

8、e-1,head,a0,p-next,p-next-next,int ListDelete(SLNode*head,int i,DataType*x)/*删除以head为头指针的带头结点的单链表中的第i个结点*/SLNode*p,*s;/*p:搜索指针,s:缓冲指针*/int j;p=head;j=-1;/*寻找第i-1个结点*/while(p-next!=NULL,【单链表删除算法】,if(j!=i-1)printf(“n删除位置不合理!”);return 0;/*删除*/s=p-next;*x=s-data;p-next=p-next-next;free(s);return 1;,单链表插

9、入删除算法时间复杂度分析:插入、删除算法的时间复杂度均为O(n)。这是因为,虽在单链表中插入或删除元素时无需移动元素,只需修改指针域。但由于它不是随机存取结构,为寻找第i-1个元素,尚需执行ListGet(head,i-1,x)操作,这和顺序存储结构正好相反。,单链表空间复杂度分析:,单链表中每个结点都要增加一个指针域,相当于总共增加了n 个整型变量,空间复杂度为 O(n)。事实上,链表插入、删除运算的快捷是以空间代价来换取时间。,int ListLength(SLNode*head)/求以head为头指针的带头结点的单链表表长 SLNode*p=head;/*p:搜索指针*/int size

10、=0;while(p-next!=NULL)p=p-next;size+;return size;,【单链表求表长算法】,void Destroy(SLNode*head)/释放以head为头指针的带头结点的单链表所占空间 SLNode*p,*p1;p=*head;while(p!=NULL)p1=p;p=p-next;free(p1);*head=NULL;,【撤消单链表算法】,空表:,在单链表中为什么引入头结点?,引入头结点是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便。如果不增加头结点,插入和删除操作如何变动?,1)在带头结点单链表第一个数据元素前

11、插入结点,2)删除带头结点单链表第一个数据元素结点,3)在不带头结点单链表第一个数据元素前插入结点,4)在不带头结点单链表其他数据元素前插入结点,5)删除不带头结点单链表第一个数据元素结点,6)删除不带头结点单链表其他数据元素结点,结论:(1)带头结点单链表无论在第一个数据元素结点前插入,还是在其他结点前插入,操作方法一样;而不带头结点单链表在第一个数据元素结点前插入,和在其他结点前插入,操作方法不一样(2)删除操作和插入操作类似(3)设计带头结点单链表的算法时,头指针参数可设计成输入型参数;设计不带头结点单链表的算法时,头指针参数必须设计成输出型参数(4)因此,带头结点单链表的算法设计简单,

12、2.3.4单链表应用举例 例23(P35)文件 LinList.h(P29-34)文件 LinListExample.c(P35),作业3,算法设计题:1、补充实现单链表的基本操作1、IsEmpty()函数实现判断单链表是否为空表。2、InsertFront()函数实现在单链表首元结点前插入一新结点x。3、InsertEnd()函数实现在单链表的表尾插入一个新结点x。4、Find()函数实现在单链表中寻找值为x的元素。5、FindPrevious()函数实现在单链表中寻找值为x的前一个元素。,2、实现带尾指针和表长信息的单链表数据结构1、InsertEnd()函数实现在单链表的表尾插入新结点,但它的运行时间代价为O(n),因为要从头指针开始遍历整个链表找到尾结点。要求你修改单链表数据结构(包括类型定义和相关函数),使InsertEnd()函数的时间复杂度为O(1)。2、ListLength()函数实现求单链表的表长,但它的运行时间代价为O(n),因为要从头指针开始遍历整个链表以统计表长。要求修改单链表数据结构(包括类型定义和相关的函数),使ListLength()函数的时间复杂度为O(1)。,作业3(续),3、p46,2-24 题目“有序顺序表”改为“有序单链表”,作业3(续),

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 在线阅读 > 生活休闲


备案号:宁ICP备20000045号-1

经营许可证:宁B2-20210002

宁公网安备 64010402000986号