昨天在链表的顺序结构基础上对链表链式存储即单链表做了简单的介绍,今天继续。
1、单链表的读取
获得链表第i个元素的思路
(1)声明一个结点p指向链表的第一个结点,初始化j从1开始
(2)当j<1时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累加1
(3)若到链表末尾p为空,说明第i个元素不存在
(4)若查找成功,返回结点p的数据
可见,单链表的查找确实不如顺序表来的快。
2、单链表的插入和删除
插入的思路:
(1)和查找一样,先声明结点p,遍历链表,找到第i个元素
(2)若找到,则声明一个空结点s
(3)将元素e赋给s->data
(4)s->next=p->next;p->next=s
删除算法的思路:
(1)和查找一样,先声明结点p,遍历链表,找到第i个元素
(2)若查找成功,将欲删除的结点p->next赋给q
(3)p->next=q->next
(4)将q的值赋给e,作为返回
(5)释放q,返回成功
可见,插入和删除都分为两部分,先查找,然后进行插入或者删除的操作
从时间复杂度角度来说,插入和删除的时间复杂度都是O(n),但是如果我们希望从第i个位置开始,插入10个元素,对于顺序存储结构来说,每一次插入都需要移动n-i个元素,每次都是O(n),而对于链式存储,找到第i个元素,此时是O(n),接下来只是简单的赋值而已,时间复杂度都是O(1),可见,对于插入或者删除越复杂的操作,单链表的效率越高。
3、单链表的整表创建
(1)声明一结点p和计数变量i
(2)初始化一个空链表L
(3)让L的头结点的指针指向null,即建立一个带头结点的单链表
(4)循环
生成一新节点赋给p
随机生成一个数赋给p的数据域
将p插入到头结点与前一新结点之间
这种方式成为头插法,相应的还有尾插法
分享到:
相关推荐
这是数据结构c语言版第三版的课后题答案,可配套用于学习,很有帮助。
算法与数据结构课件、习题、习题详细解答;这将对你的专业学习提供极大的帮助
算法与数据结构学习指导与习题解析 王晓东编
数据结构 第1章_C语言概述.ppt 第3章_数据类型.ppt 第5章广义表.ppt
数据结构 (第三版)李春葆 全部课后程序,供大家学习交流讨论!
主要就是算法与数据结构的张乃孝的第二版,是pdf,就是电子书,主要在学习的时候可以对照这个来进行学习,没有必要一定要实实的书
数据结构与算法学习辅导及习题详解.张乃孝版
数据结构算法与应用–C++语言描述;数据结构与算法分析 Java语言描述(第2版);算法导论(第三版)英文版 ;算法导论(原书第2版) ;算法导论(中文版)(现代计算机常用数据结构和算法)
本书是与教材《数据结构》配套的教学辅导书,共分8章,顺序与《数据结构》教材前8章的顺序一致。内容包括各章的讲课提要、学习指导、习题及参考答案。编者根据多年的教学积累,对各章的知识要点进行归纳和总结,...
清华大学邓俊辉老师数据结构(第三版)光盘配套程序源码,可与书籍学习视频配套使用,完整版源码
帮助学习算法分析与数据结构,全英文版更加贴近国外最新信息
第三部分讨论数据结构的实现;第四部分描述了高级的数据结构,如伸展树、偶堆和不相交集数据结构。 本书适合作为本科生数据结构课程或研究生算法分析课程的教材。教师可以灵活地选择本书的内容,选择最适合对应课程...
数据结构与算法 数据结构与C语言 第3章 栈和队列(共150页).ppt 数据结构与算法 数据结构与C语言 第4章 串、数组和广义表(共66页).ppt 数据结构与算法 数据结构与C语言 第5章 树和二叉树(共95页).ppt 数据结构...
数据结构 (c++语言版)第三版 邓俊辉著;该资源不同于其他不完整版,是真正无缺版本,pdf分章节放在压缩包里。资源仅供学习,严禁用于商业用途经济上有余力的同学。还是购买实体书支持一下老师。
陈元春实用数据结构基础(第三版)学习指导与习题参考
数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义;抽象数据类型的定义、表示和实现方法;描述算法的类C语言;算法设计的基本要求以及从时间和空间角度分析算法的方法。 二、学习要点 1...
算发与数据结构学习指导与习题解析,讲解了第三版算法设计与分析的课后习题与解题思路.pdf
李春葆数据结构源代码,有助于学习李教授的教程
清华学堂在线国家级精品课程的配套教材。正版彩印!学习数据结构必备书籍!