网站建设案例教程视频教程,全网营销策划公司,软文发布的平台与板块,网站建设策划书范文六篇精选初识线性表 文章目录初识线性表线性表的类型定义基本操作#xff08;一#xff09;init#xff0c;destory#xff0c;clear基本操作#xff08;二#xff09; 判空 #xff0c;求长基本操作#xff08;三#xff09;取值#xff0c;取位置基本操作#xff08;四一initdestoryclear基本操作二 判空 求长基本操作三取值取位置基本操作四取前驱取后继基本操作五插入基本操作六 删除线性表的顺序存储结构实现基本操作实现线性表的小结由n(n≥0)个数据特性相同的元素构成的有限序列称为线性表。线性表的特点
线性表中元素的个数n(n≥O)定义为线性表的长度n0时称为空表。
将非空的线性表(nO)记作(a1a2a3…an)
这里的数据元素ai(1≤i≤n)只是个抽象的符号其具体含义在不同情况下可以不同。
在非空的线性表有且仅有一个开始结点a1,它没有直接前趋而仅有一个直接后继a2;
有且仅有一个终端结点an,它没有直接后继而仅有一个直接前趋an-1;
其余的内部结点ai,(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai1
线性表的例子、
26个英文字母的字母表(A, B, C, …Z)学生信息表12星座。
同一线性表中的元素必定具有相同的特性数据元素之间关系是线性的。
案例引入 逻辑结构抽象为线性表存储结构呢
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(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项]
B((8,1),(22,7),(-9,8),)[3项]
创建一个新的多项式c用来存放a与b和 分别从头遍历比较a和b的每一项 指数相同对应系数相加若其和不为零则在c中增加一个新项 指数不相同则将指数较小的项复制到c中 一个多项式已遍历完毕时将另一个剩余项依次复制到c中即可
和有多少项呢
最少:指数一样,系数正好互为相反数项数为0最多指数都不一样项数为元素个数之和。项数不容易确定太大了浪费空间太小了放不下。
顺序存储结构存在问题存储空间分配不灵活运算的空间复杂度高
尝试链式存储结构(不需要额外的空间只利用已有的空间) 逻辑结构根据图书表的特点将其抽象成一个线性表每本图书作为线性表中的一个元素
存储结构 a.顺序 b.链式 比较这两种存储结构的优缺点根据实际情况选择适当的存储结构实现此存储结构上的基本操作利用基本操作完成功能。当然学生信息管理也是类似的
线性表的类型定义 线性表的存储结构
在计算机中线性表有两种存储结构1. 顺序存储结构 2. 链式存储结构
抽象数据类型线性表的定义如下
ADT List { 数据对象D { ai丨ai属于Elemset(i 1,2,3…)} 数据关系R {ai-1 , ai丨ai-1 , ai 属于D,(i 1,2,3…) } 基本操作
InitList(L); DestroyList(L);
ListInsert(L,i,e); ListDelete(L,i,e);
} ADT List
基本操作一initdestoryclear
InitList(L)
操作结果构造一个空的线性表L
DestoryList(L)
初始条件线性表L已经存在
操作结果销毁线性表L
ClearList(L)
初始条件线性表L已经存在
操作结果将线性表L重置为空表
基本操作二 判空 求长
ListEmpty(L)
初始条件线性表L已经存在
操作结果若线性表L为空表(n0)则返回TURE 否则返回FALSE
Listlength(L)
初始条件线性表L已经存在
操作结果返回线性表L中元素的个数
基本操作三取值取位置
GetElem(L,i,e)
初始条件线性表L已经存在1≤ i ≤ ListLength(L)
操作结果用e返回线性表L中第i个数据元素的值
LocateElem(L,e,compare())
初始条件线性表L已经存在compare()是数据元素判定函数。
操作结果返回L中第一个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回为0.
基本操作四取前驱取后继
priorElem(L,cur_e,pre_e)
初始条件线性表L已经存在
操作结果若cur_e是L的数据元素且不是第一个则用pre_e返回他的前驱否则操作失败pre_e无意义
NextElem(L,cur_e,next_e)
初始条件线性表L已经存在
操作结果若cur_e是L的数据元素且不是最后一个则用next_e返回他的后继否则操作失败next_e无意义
基本操作五插入
ListInsert(L,i,e)
初识条件线性表L已经存在1≤ i ≤ ListLength(L)1
操作结果在L的第i个位置之前插入新的数据元素eL的长度1
基本操作六 删除
ListDelete(L,i,e)
初识条件线性表L已经存在1≤ i ≤ ListLength(L)
操作结果删除L的第i个元素并用e返回其值L的长度-1
ListTraverse(L,visited())
初识条件线性表L已经存在
操作结果依次对线性表中每个元素调用visited()
线性表的顺序存储结构实现
**线性表的顺序表示(又称顺序存储结构或顺序映象) ** 顺序存储定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。
线性表的第1个数据元素a1的存储位置称为线性表的起始位置或基地址
线性表的顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。
例如:线性表(1,2,3,4,5,6) 顺序存储结构的寻址公式 数组长度与线性表长度
数组长度线性表最多可容纳数据元素的个数
线性表长度(length)当前数据元素个数
一个教室最多容纳50人(数组长度/线性表的最大存储容量)但现在教室里坐着34(线性表中当前元素个数)个数。
由于顺序表中的元素要求地址连续、依次存放、随机存取、类型相同高级程序设计语言当中可以用一维数组来实现
一维数组的定义方式
类型说明符 数组名[常量表达式]
说明常量表达式中可以包含常量和符号常量(宏命名)不能包含变量。即C语言中不允许对数组的大小作动态定义。
线性表经常进行插入和删除的操作长度可变而C中数组的长度是不可变的。
用一个额外的变量表示线性表的长度 ElemType是根据实际问题你需要什么类型的数组就定义成什么一般是根据问题定义一个结构体或者是 typedef char ElemType
**数组的定义 ** 数组名其实就是首元素的地址所以也可以直接定义一个指针。数组的大小用相应的函数来动态分配内存 用结构体变量名.成员变量名对成员访问指针SqList *pL;p-data…;
1.malloc()函数是在程序运行时分配内存的重要工具接受一个参数:所需的内存字节数但并不会为其赋名.然而,但他确实返回了动态分配内存块的首地址.因此可以把该地址赋给一个指针变量,并使用指针访问这块内存注意要强制类型转换
(类型说明符*)malloc(size);
如向内存要100个int(类型说明符*)malloc(100*sizeof(int));
2.sizeof(x)计算变量/数据类型x所占据的字节数
3.free§释放指针p所指变量的存储空间即彻底删除一个变量
需要加载头文件stdlib.h
C内容 定义一个线性表 类型说明 变量名SqList L;
SqList L; 定义变量L L是SqList这种类型的L是个顺序表
基本操作实现
操作中常用的预定义常量与类型 初始化(分配空间赋初值) 销毁线性表 线性表置空/清空线性表 求表长 判断线性表是否为空 线性表的按值查找算法(在查找的一章还要详细介绍这里我们先说最简单的顺序查找) 查找算法的算法分析
查找算法的基本操作:将记录的关键字同给定值进行比较(L.eleme) 比较的次数与输入的定值e有关(假设7个数字出现的概率均为1/7) 当ea1次当eb2次当ec3次…eg,7次 平均比较次数(123…7)/74
在查找时为确定元素在顺序表中的位置需和给定值进行比较的数据元素个数的期望值称为查找算法在查找成功时的平均查找长度(AverageSearch Length, ASL)。 插入算法
(在线性表a3位置之前插入一个新元素e(e6)) 插入位置在最后在线性表的最后添加一个元素不需要移动直接添加
插入位置在最前在原线性表的第1个元素之前插入一个新的元素线性表的所有元素都要移动 移动次数最多
插入位置在中间如上例 删除操作 ①判断删除位置i是否合法合法值为1≤i≤n)
②将欲删除的元素保留在e当中
③将第il个至第n个的元素依次向前移动一个位置(i n时无需移动
④表长减1 删除算法分析 线性表的小结
查找、插入、删除的平均算法复杂度为O(n)
空间复杂度显然顺序表操作没有占用辅助空间算法的空间复杂度O(1)
线性表的优缺点
优点
存储密度大(结点本身所占用的空间/结点结构所占存储量1)无需为表示表中元素之间的逻辑关系而增加额外的存储空间
可以随机存取表中任意位置的元素
缺点
插入、删除某一元素需移动大量元素
当线性表长度变化较大时难以确定存储空间的容量数据元素的个数不能自由扩充(存储空间不灵活)
