




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、上堂课要点回顾,线性表的抽象数据类型定义 顺序表 类型定义 基本操作实现 应用,数据结构课程内容,第 三 次 课,阅读: 朱战立,第26-35页 练习: 作业3,2.3 线性表的链式表示和实现 链表,链式存储结构 定义:用一组任意的存储单元来存放线性表 中的数据元素。 特点:逻辑结构上相邻的元素在其存储的物 理位置上不一定相邻。 通过指针把链表的存储结点链接成一 个链。,2.3.1 单链表的存储结构, 结点结构:链表每个结点中只有一个指针 域指向直接后继结点。, 结点类型定义(借用指针类型) typedef int DataType; typedef struct Node DataType
2、data; struct Node * 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 = (
3、SLNode*) malloc ( sizeof (SLNode); l1-data = 7; l2-data = 0; l3-data = 6;,l1,l2,l3,sizeof(x)计算变量x的所占的字节数 malloc(m) 开辟m字节长度的地址空间,并返回这段空间的首地址 free(p) 释放指针p所指变量的存储空间,即彻底删除一个变量,存储结构,带头结点的单链表: 非空表:,空表:,满足 head-next=NULL,头结点是在链表的首元结点之前附设的一个结点;其数据域不存储线性表的数据元素,只放表长等信息;其指针域存储首元结点的地址,头结点,初始化单链表, 单链表的操作实现,void
4、 ListInitiate(SLNode * head) /置以head为头指针的带头结点的单链表为空表 *head = (SLNode*) malloc ( 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
5、,a1,an-1,ai,head,int ListGet(SLNode *head, int i, DataType *x) /* 在以head为头指针的带头结点的单链表中,读取第i个元素 */ SLNode *p; int j; p=head; j=-1; /*从头指针开始查找ai */ while (p-next!=NULL /注意:仅当 p!=NULL时,p-data、p-next才有意义,【单链表取元素算法】,|i0,单链表取元素算法的时间复杂度: 上述算法的时间复杂度与while语句的频度有关,最坏情况下搜索完整个链表,因此,对于长度为 n 的单链表而言,算法的时间复杂度为 O(n)
6、。,插入前插,思想:要在第 i 个结点之前插入元素 x,必须先找到第 i-1 个结点的地址,这样,才能将第 i-1 个结点的指针修改指向新插入的结点,而新结点的指针指向第 i 个结点。,q-next=p-next;,注意:两条语句的顺序不能颠倒,否则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
7、x) /*在以head为头指针的带头结点的单链表中的第i个结点之前插入值为x的结点*/ SLNode *p, *q; /*p:搜索指针,q:新生成指针*/ int j; p=head; j= - 1; while (p-next!=NULL ,【单链表前插算法】,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
8、;,思想:要删除第 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 size-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=
9、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; ,单链表插入删除算法时间复杂度分析: 插入、删除算法的时间复杂度均为O(n)。这是因为,虽在单链表中插入或删除元素时无需移动元素,只需修改指针域。但由于它不是随机存取结构,为寻找第i-1个元素,尚需执行ListGet(head, i-1, x)操作,这和顺序存储
10、结构正好相反。,单链表空间复杂度分析:,单链表中每个结点都要增加一个指针域,相当于总共增加了n 个整型变量,空间复杂度为 O(n)。事实上,链表插入、删除运算的快捷是以空间代价来换取时间。,int ListLength(SLNode *head) /求以head为头指针的带头结点的单链表表长 SLNode *p=head; /*p:搜索指针*/ int size=0; while(p-next!=NULL) p=p-next; size+; return size; ,【单链表求表长算法】,void Destroy(SLNode *head) /释放以head为头指针的带头结点的单链表所占空间
11、 SLNode *p, *p1; p = *head; while(p != NULL) p1 = p; p = p-next; free(p1); *head = NULL; ,【撤消单链表算法】,空表:,在单链表中为什么引入头结点?,引入头结点是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便。 如果不增加头结点,插入和删除操作如何变动?,1) 在带头结点单链表第一个数据元素前插入结点,2)删除带头结点单链表第一个数据元素结点,3)在不带头结点单链表第一个数据元素前插入结点,4)在不带头结点单链表其他数据元素前插入结点,5)删除不带头结点单链表第一个数据
12、元素结点,6)删除不带头结点单链表其他数据元素结点,结论: (1)带头结点单链表无论在第一个数据元素结点前插入,还是在其他结点前插入,操作方法一样;而不带头结点单链表在第一个数据元素结点前插入,和在其他结点前插入,操作方法不一样 (2)删除操作和插入操作类似 (3)设计带头结点单链表的算法时,头指针参数可设计成输入型参数;设计不带头结点单链表的算法时,头指针参数必须设计成输出型参数 (4)因此,带头结点单链表的算法设计简单, 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),因为要从头指针开始遍历整个链表找到尾结点。要求你修改单链表数据
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 河南艺术机构管理办法
- 高职人才培养质量增值评价研究
- 比质比价采购管理办法
- 钢结构维护与结构施工技术指南
- 新教师教学工作中存在的问题分析
- 小学队列队形教学计划
- 春节技师放假管理办法
- 体育与艺术融合发展的实施路径研究
- 梧州学院专业管理办法
- 接地系统安装工艺与技术研究
- 2025年7月新疆维吾尔自治区学业水平合格性考试历史试题(含答案)
- 建立并优化医院的药品管理体系
- 农村农资采购与供应长期合作协议
- 反假币培训课件
- 2025至2030中国电压暂降治理行业产业运行态势及投资规划深度研究报告
- 辽宁省2024年7月普通高中学业水平合格性考试化学试卷(含答案)
- 危险品运输学习通超星期末考试答案章节答案2024年
- (正式版)SHT 3551-2024 石油化工仪表工程施工及验收规范
- 六年级数学分数除法、解方程计算题 (含答案)
- 高速铁路竣工验收办法
- 新教材 人教版高中英语必修第一册全册各单元知识点提炼汇总(单词短语语法写作等)
评论
0/150
提交评论