前驱取后继基本操作五插入基本操作六

删除线性表的顺序存储结构实现基本操作实现线性表的小结由n(n≥0)个数据特性相同的元素构成的有限序列称为线性表。

线性表的特点

线性表中元素的个数n(n≥O)定义为线性表的长度n0时称为空表。

这里的数据元素ai(1≤i≤n)只是个抽象的符号其具体含义在不同情况下可以不同。

在非空的线性表有且仅有一个开始结点a1,它没有直接前趋而仅有一个直接后继a2;

有且仅有一个终端结点an,它没有直接后继而仅有一个直接前趋an-1;

其余的内部结点ai,(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai1

同一线性表中的元素必定具有相同的特性数据元素之间关系是线性的。

案例引入

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vGJqGNRc-1677728036862)(https://typora01u.oss-cn-beijing.aliyuncs.com/img/8823c906008c1dc04447be453964f97f10d9058b.png437w_69h_progressive.webp)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TpVMVYVC-1677728036862)(https://typora01u.oss-cn-beijing.aliyuncs.com/img/7e847d9bbf0f3126aa0151016c58e4ceb1f7997b.png272w_77h_progressive.webp)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TnYQEqDH-1677728036862)(https://typora01u.oss-cn-beijing.aliyuncs.com/img/e40f15560243aaf01e64866cbcea9afa52ef53c9.png848w_155h_progressive.webp)]

的多项式时就要用一个长度为20001的线性表来表示而表中仅有3个非零元素此时将会造成存储空间的很大浪费由此可改变元素设定对多项式的每一项可用系数指数唯一确定。

每一个系数与指数也构成了一个线性表只不过是线性表的每个数据元素有2个数据项

多项式加法

A((7,0),(3,1),(9,8),(5,17))[4项]

和有多少项呢

最少:指数一样,系数正好互为相反数项数为0最多指数都不一样项数为元素个数之和。

项数不容易确定太大了浪费空间太小了放不下。

逻辑结构根据图书表的特点将其抽象成一个线性表每本图书作为线性表中的一个元素

存储结构

比较这两种存储结构的优缺点根据实际情况选择适当的存储结构实现此存储结构上的基本操作利用基本操作完成功能。

当然学生信息管理也是类似的

在计算机中线性表有两种存储结构1.

初始条件线性表L已经存在compare()是数据元素判定函数。

操作结果返回L中第一个与e满足compare()的数据元素的位序。

若这样的数据元素不存在则返回为0.

基本操作四取前驱取后继

操作结果若cur_e是L的数据元素且不是第一个则用pre_e返回他的前驱否则操作失败pre_e无意义

初始条件线性表L已经存在

操作结果若cur_e是L的数据元素且不是最后一个则用next_e返回他的后继否则操作失败next_e无意义

基本操作五插入

顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

线性表的第1个数据元素a1的存储位置称为线性表的起始位置或基地址

线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。

例如:线性表(1,2,3,4,5,6)

一个教室最多容纳50人(数组长度/线性表的最大存储容量)但现在教室里坐着34(线性表中当前元素个数)个数。

由于顺序表中的元素要求地址连续、依次存放、随机存取、类型相同高级程序设计语言当中可以用一维数组来实现

类型说明符

说明常量表达式中可以包含常量和符号常量(宏命名)不能包含变量。

即C语言中不允许对数组的大小作动态定义。

线性表经常进行插入和删除的操作长度可变而C中数组的长度是不可变的。

ElemType是根据实际问题你需要什么类型的数组就定义成什么一般是根据问题定义一个结构体或者是

typedef

数组名其实就是首元素的地址所以也可以直接定义一个指针。

数组的大小用相应的函数来动态分配内存

*pL;p-data…;

1.malloc()函数是在程序运行时分配内存的重要工具接受一个参数:所需的内存字节数但并不会为其赋名.然而,但他确实返回了动态分配内存块的首地址.因此可以把该地址赋给一个指针变量,并使用指针访问这块内存注意要强制类型转换

如向内存要100个int(类型说明符*)malloc(100*sizeof(int));

需要加载头文件stdlib.h

线性表的按值查找算法(在查找的一章还要详细介绍这里我们先说最简单的顺序查找)

查找算法的基本操作:将记录的关键字同给定值进行比较(L.eleme)

比较的次数与输入的定值e有关(假设7个数字出现的概率均为1/7)

平均比较次数(123…7)/74

在查找时为确定元素在顺序表中的位置需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearch

Length,

插入位置在最前在原线性表的第1个元素之前插入一个新的元素线性表的所有元素都要移动

移动次数最多

空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)

存储密度大(结点本身所占用的空间/结点结构所占存储量1)无需为表示表中元素之间的逻辑关系而增加额外的存储空间

插入、删除某一元素需移动大量元素

当线性表长度变化较大时难以确定存储空间的容量数据元素的个数不能自由扩充(存储空间不灵活)