本文主要是介绍数据结构——顺序表和单链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
数据结构
基本概念:
数据结构是一门研究如何有效组织数据,并提高数据处理效率的学科。通过研究各种数据内部的逻辑关系,使用某种特定的存储形式,并在此基础上对数据实施各种操作,这些工作被称为称为广义上的算法。
逻辑结构
指数据之间的内在关系。通常有集合、线性表、树、图等常见的逻辑结构。
逻辑结构是数据之间本身的属性,跟我们怎么处理它们无关。
线性关系:
各个元素之间是一种一对一的关系,比如图书馆中的书架的书,除了首尾两本书之外,其余的任意一本书的编号假设是N,都有且仅有一个直接前驱节点N-1,有且仅有一个直接后继节点N+1。这种关系就是典型的线性逻辑。
非线性关系:
与上述线性关系的表述不同,如果各个元素之间不是严格一对一的关系,则被称为非线性关系,比如家族中的各个成员、不同城市间的交通道路等,对于它们中间的某个元素,都可能有不止一个元素与之关联。这种关系是典型的非线性逻辑。
存储形式:
数据的存储方式。比如顺序存储、链式存储等。
不同的存储形式对最终数据的处理效率通常有很大的影响。
逻辑结构与存储形式并无必然联系。
算法分析【了解】
算法分析是指算法在正确的情况下,对其优劣的分析。一个好的算法通常是指:
1. 算法对应的程序所耗时间少
2. 算法对应的程序所耗存储空间少
3. 算法结构性好、易读、易移植和调试
数据结构与算法的本质任务,是提高程序的时间空间效率,简单讲就是让程序的执行速度越快越好,所需内存空间越少越好。虽然在很多情况下,程序的时空特性是相互制约的,就像鱼和熊掌不可兼得,但我们可以根据程序实际解决问题的侧重点,去平衡时间和空间的对性能的消耗。
时间复杂度
一般而言,时间复杂度并不考察一段代码运行所需要的绝对时间,因为不同的计算机的硬件参数不同,考察绝对时间没有意义。时间复杂度一般指的是代码的语句执行总次数,称为语句频度。
在上述代码中,程序执行的语句频度理论是:T(n) = n^2 + n
但一般情况下,我们只关心多项式的最高次幂,于是上述代码的时间复杂度我们表示为:
T(n) + O(n^2)
这意味着,该程序算法所需要的时间,与传进来的参数n的平方成正比。
不同算法的时间复杂度相差很大,如下图所示,随着所处理的问题规模的增大,不同时间复杂度的程序所需要的时间有天壤之别。
空间复杂度
空间复杂度的概念更简单一点,就是一段程序运行时所需的内存字节量。
时空复杂度互换
一段程序的性能指标,既要运行快速,又要节省内存,而通常这两者又是相互制约的,很难兼得。因此在实际解决问题时,会根据需要侧重一方,牺牲另一方。
线性表
概念
对于一组拥有n个数据元素的线性表,其严格数学定义是:其中任何一个数据元素,有且仅有一个直接前驱,有且仅有一个直接后继。首元素无直接前驱,尾元素无直接后继。
满足这种数学关系的一组数据,当中的数据是一个挨着一个的,常被称为一对一关系。反
之,如果数据之间的关系不是一对一的,就是非线性的。
举例
生活中的线性表例子非常多,比如一个班级中的以学号编排的学生,一座图书馆中的以序号编排的图书、一条正常排队等候的队列、一摞从上到下堆叠的餐盘,这些都是线性表。他们的特点都是:除了首尾两个元素,其余任何一个元素前后都对应相邻的另一个元素。
注意:
线性表是一种数据内部的逻辑关系,与存储形式无关
线性表既可以采用连续的顺序存储,也可以采用离散的链式存储
顺序表
基本概念
顺序表:顺序存储的线性表。
链式表:链式存储的线性表,简称链表。
顺序存储就是将数据存储到一片连续的内存中,在C语言环境下,可以是具名的栈数组,或者是匿名的堆数组。
存储方式不仅仅只是提供数据的存储空间,而是必须要能体现数据之间的逻辑关系。当采用顺序存储的方式来存放数据时,唯一能用来表达数据间本身的逻辑关系的就是存储位置。比如队列中的两个人,小明和小花,如果小明在逻辑上排在相邻的小花的前面,那么在存储位置上也必须把小明存放在相邻的小花的前面。
基本操作
顺序表设计
一般而言,为了方便操作顺序表,需要一个专门管理顺序表的”管理结构体“,管理结构体中一般会包含:
1. 顺序表总容量
2. 顺序表当前最末元素下标位置
3. 顺序表指针
初始化
所谓初始化就是建立一个不包含任何元素的顺序表,设置好管理结构体中的表的总容量、末元素下标,申请好顺序表内存空间等系列准备工作。
增删节点
在顺序表中增加一个数据,可以有多种方式,比如在原数组的末尾增加,或者在原数组的头部增加,或者在数组中间任意一个位置增加。根据实际需要来定。
销毁顺序表
一个顺序表最后不再需要,应当要释放其所占用的内存空间,这被称为顺序表的销毁。
顺序表优缺点总结
顺序存储中,由于逻辑关系是用物理位置来表达的,因此从上述示例代码可以很清楚看到,增删数据都非常困难,需要成片地移动数据。顺序表对数据节点的增删操作是很不友好的。
总结其特点如下:
优点
1. 不需要多余的信息来记录数据间的关系,存储密度高
2. 所有数据顺序存储在一片连续的内存中,支持立即访问任意一个随机数据,比如上述顺序表中第个节点是 s->data[i]
缺点
1. 插入、删除时需要保持数据的物理位置反映其逻辑关系,一般需要成片移动数据
2. 当数据节点数量较多时,需要一整片较大的连续内存空间
3. 当数据节点数量变化剧烈时,内存的释放和分配不灵活
单链表
基本概念
顺序表:顺序存储的线性表。
链式表:链式存储的线性表,简称链表。
既然顺序存储中的数据因为挤在一起而导致需要成片移动,那很容易想到的解决方案是将数据离散地存储在不同内存块中,然后在用来指针将它们串起来。这种朴素的思路所形成的链式线性表,就是所谓的链表。
顺序表和链表在内存在的基本样态如下图所示:
链表的分类
根据链表中各个节点之间使用指针的个数,以及首尾节点是否相连,可以将链表细分为如下种类:
1. 单向链表
2. 单向循环链表
3. 双向循环链表
这些不同链表的操作都是差不多的,只是指针数目的异同。
上图中,所有的节点均保存一个指针,指向其逻辑上相邻的下一个节点(末尾节点指向
空)。另外注意到,整条链表用一个所谓的头指针 head 来指向,由 head 开始可以找到链表中的任意一个节点。head 通常被称为头指针。
链表的基本操作,一般包括:
1. 节点设计
2. 初始化空链表
3. 增删节点
4. 链表遍历
5. 销毁链表
单链表节点设计
单向链表的节点非常简单,节点中除了要保存用户数据之外(这里以整型数据为例),只需要增加一个指向本类节点的指针即可,如下所示:
typedef int DATA;typedef struct Node
{DATA data; // 存储数据---数据域struct Node *next; // 存储下一个节点的地址---指针域
} NODE;
单链表初始化
首先,空链表有两种常见的形式。一种是带所谓的头结点的,一种是不带头结点的。所谓的头结点是不存放有效数据的节点,仅仅用来方便操作,如下:
而不带头结点的空链表如下所示:
注意:
头指针 head 是必须的,是链表的入口 头节点是可选的,为了方便某些操作
由于头结点是不存放有效数据的,因此如果空链表中带有头结点,那么头指针 head 将永远不变,这会给以后的链表操作带来些许便捷。
单链表增删节点
相对于顺序表需要整片移动数据,链表增删节点只需要修改几个相关指针的指向,动作非常快速。
与顺序表类似,可以对一条链表中的任意节点进行增删操作。
注意:
删除链表的节点并不意味着释放其内存,而是将其剔除出链表
单链表的遍历
遍历的意思就是逐个访问每一个节点,对于线性表而言,由于路径唯一的选择就是从头走到尾。因此相当而言比较简单。
单链表的销毁
由于链表中的各个节点被离散地分布在各个随机的内存空间,因此销毁链表必须遍历每一个节点,释放每一个节点。
注意:
销毁链表时,遍历节点要注意不能弄丢相邻节点的指针
链表优缺点
链式存储中,所有节点的存储位置是随机的,他们之间的逻辑关系用指针来确定,跟物理存储位置无关。
另外,又由于位置与逻辑关系无关,因此也无法直接访问某一个指定的节点,只能从头到尾按遍历的方式一个个找到想要的节点。简单讲,链式存储的优缺点跟顺序存储几乎是相对的。
总结其特点如下:
优点
1. 插入、删除时只需要调整几个指针,无需移动任何数据
2. 当数据节点数量较多时,无需一整片较大的连续内存空间,可以灵活利用离散的内存
3. 当数据节点数量变化剧烈时,内存的释放和分配灵活,速度快
缺点
1. 在节点中,需要多余的指针来记录节点之间的关联。
2. 所有数据都是随机存储的,不支持立即访问任意一个随机数据。
循环链表【扩展】
所谓的循环,指得是将链表末尾节点循环地指向链表表头。比如,单向链表变成循环链表的示意图如下所示:
循环链表的操作跟普通链表操作基本上是一致的,只要针对循环特性稍作修改即可。
这篇关于数据结构——顺序表和单链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!