type
status
date
slug
summary
tags
category
icon
password
🤔
又又又从今天开始,我们将开始学习数据结构的重点内容啦(上章的算法其实也没有想象的那么重要啦),本章我们将学习线性表,你准备好了吗?

👉 推荐学习资料

《大话数据结构》——程杰

📝 正文

第三章、线性表

3.1 线性表的定义

线性表,从名字上你就能感觉到,是具有像线一样的性质的表。
那么就让我们来举个例子:
假设你是一名小学老师,小学放学后,孩子们要统一带到校门口去放学,怎样才能既快速又不少人的带出呢?
有的人会选择在班级外面排队,然后一个一个点名,有的人会选择让小朋友们按学号排队。
那如果说先让小朋友们按自己的想法排成一队,然后要求他们记住自己的前面和后面,如果少人了就报告老师,这样这个排队效率是不是大大增加了?
这便是线性表,从名字上你就能感觉到,线性表是具有像线一样的性质的序列。
  • 线性表(List):零个或多个数据元素的有限序列。
  • 线性表的长度:线性表元素的个数n(n>0) ,当n=0时,则称为空表。
  • 线性表的表头:线性表的第一个元素a1。
  • 线性表的表尾:线性表的最后一个元素a2。
  • 直接后继:后一个元素是前一个的直接后继。
  • 直接前驱:前一个元素是后一个的直接前驱。
对于非空的线性表或线性结构,其特点是: 1. 存在唯一的一个被称为“第一个”的数据元素。 2. 存在唯一的一个被称为“最后一个”的数据元素。 3. 除第一个外,结构中的每个数据元素有且只有一个直接前驱。 4. 除最后一个外,结构中的每个数据元素有且只有一个直接后继。 直接前驱和直接后继反映了数据元素之间一对一的邻接逻辑关系。
 

3.2 线性表的抽象数据类型

下面来让我们看几个线性表的例子:
COLOR= ("Red", "Orange", "Yellow", "Green", "Blue", "Black", "White")
SCORE= (87,74,92,59,37,64, 100,83, 72,90)
下面给出线性表的抽象数据类型定义:
notion image
notion image
同时,线性表有两种存储方式:顺序存储和链式存储。采用顺序存储方式实现的线性表被称为顺序表,而采用链式存储的线性表被称为链表。本章将讨论顺序存储。
 

3.3 线性表的顺序存储结构

3.3.1 顺序表的定义

首先,让我们看一下顺序表的定义:
  • 线性表的顺序存储结构:指的是用 一段地址连续的存储单元依次存储线性表的数据元素。
说白了,顺序表就是在内存中找了块地,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。
既然线性表的每个数据元素的类型都相同,所以可以用C语言 (其他语言也相同)的一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。
在知道了顺序表的概念后,我们就要开始学习下顺序表的存储结构了。顺序表的存储结构根据存储空间的分配方法可以分成静态分配和动态分配。
 

3.3.2 顺序表的静态分配

就拿占座举例子,顺序表就好比一个人从一个位置开始,按顺序一路占下来占了n个位子,而第一个占的位置便是存储空间的起始位置。这n便是这个线性表的最大存储空间,就算后来剩下的人没来齐,这位置也一样占用在那里。但是如果人来多了,也自然坐不下。这便是顺序表的静态分配。
顺序表的静态分配顺序存储结构的类型定义如下:
采用静态分配方法,定长数组需要事先分配一段固定大小的连续空间,这种方式操作非常简单。但是在运算过程中,如插入、合并等操作,容易超过预分配的空间长度而导致溢出,因此,静态分配只适合于顺序表数据元素个数稳定,并且数据元素最大个数预知的情况。
 

3.3.3 顺序表的动态分配

那么有一天,有个好兄弟带了他的女朋友过来上课,但是你们占的位置都坐满了,那总不好意思让嫂子站着上课吧,这时候就有个聪明的人,又多去占了一块地,专门给好兄弟和他女朋友去坐。(这种好兄弟可交不得 🤫)这便是动态分配。
  所以解决静态分配的溢出问题,可以采用动态分配的方法。在程序运行过程中根据需要动态分配一段连续的空间,其存储结构除了用一个一维数组和一个记录表中已存储元素个数的变量组成,另外用一个变量 maxSize 来存储线性表的最大容量,这样便于判断什么时候表是满的。
顺序表的动态分配顺序存储结构的类型定义如下:
 

3.3.4 顺序表的操作

那么怎么去操作线性表呢?下面我们将通过代码来介绍几个操作:
(1)顺序表的初始化
顺序表的初始化操作,通过动态内存分配构造一个空顺序表:
 
(2)顺序表的销毁与清空
销毁操作,通过动态内存分配构造一个空顺序表:
清空操作,将顺序表恢复为空表状态:
 
(3)判断顺序表是否为空/满
判断顺序表是否为空,若顺序表为空,则返回TRUE,否则返回FALSE:
判断顺序表是否满,若顺序表满,则返回TRUE,否则返回FALSE:
 
(4)顺序表的长度
返回顺序表的长度:
扩展顺序表的存储空间,新空间的大小为newSize,成功则返回TRUE,否则返回FALSE:
 
(5)顺序表的插入
为了让大家更好的理解顺序表的插入,我们来举个例子:
比如我们现在在医院排队挂号,突然有个母亲冲过来,说自己孩子病的很重,能不能让她插个队早点挂号。你心一软,便同意了。但是你必须得退后一步,否则她是没法进到队伍来的,这可不得了,后面的人,全部都得退一步,导致后面议论纷纷。
这便是顺序表的缺点,也是顺序表的插入模式:前面插入,后面往后退一格。
插入操作。在顺序表的第pos个位置之前插入新的数据元素e,成功则返回TRUE;否则返回FALSE:
插入的时间复杂度是多少呢?
插入必须先定位到其前驱结点,因此时间复杂度为O(n)。
 
(6)顺序表的删除
那我们接着之前的例子继续下去:
此时后面排队的人意见都很大,这位母亲迫于压力只能退出队伍,这时排队的人群都向前移动了一步。
这便是顺序表删除元素的过程。
删除顺序表的第pos个位置的元素,成功则返回TRUE;否则返回FALSE:
那么删除的时间复杂度是多少呢?
删除与插入相同,时间复杂度也为O(n)。
 
(7)顺序表的取值与查找
获取顺序表的第pos个位置的元素,用e返回其值,成功则返回TRUE;否则返回FALSE:
查找顺序表的首个元素值等于e的元素位置,成功则返回其位置序号;否则返回NotFound:
那么查找的时间复杂度与什么有关呢?
查找与待查找元素位置有关,因此平均时间复杂度为O(n)。
 
(8)顺序表的遍历
遍历输出顺序表中各个数据元素的值:
 

3.3.5 顺序表的优缺点

在学习完顺序表后,想必你对顺序表的优缺点也有了一定的了解了吧,下面我们来总结一下顺序表的优缺点。
优点:
  • 可以随机存取表中任一元素,其存储位置可通过一个简单、直观的公式来计算。
  • 存储密度高,无需为表示表中元素间的逻辑关系而增加额外的存储空间。
缺点:
  • 插入和删除操作需要移动大量(近一半)元素,效率低。
  • 当线性表长度变化较大 时,难以确定存储空间的容量。
  • 造成存储空间的“碎片”

📎 参考文章

《大话数据结构》——程杰
《数据结构》——陈志贤
 
💡
欢迎大佬指正笔记中的错误或者不足,对于文中例题有更好的解法也欢迎大佬留言!
数据结构笔记第四章(链表)数据结构笔记第二章(算法)
Jerry Zhu
Jerry Zhu
一个平凡但努力变得不平凡的普通人
公告
type
status
date
slug
summary
tags
category
icon
password
🎉祝贺JerryZhu的博客成立🎉
Jerry Zhu’s Wechat: jerrytao2666
(加微信请备注)
-- 感谢您的支持 ---