混子数据结构学习之第二章线性表笔记上
2021-11-15 本文已影响0人
那个混子
"磨棱角，褪优越，沉下心"
"不止于心动，更付诸于行动，执行力！“
引言
从这里开始，就真正进入数据结构核心内容的学习了，第二章主要是介绍了线性表以及他的顺序表示方法和链式表示方法，本章还是非常的重要，利用每天晚上零碎的时间，内容我大概学了一半多一点，现在对上周的内容进行一个总结，整理一下笔记。
知识回顾
线性表
定义：
线性表是具有相同特性的数据元素的一个有限序列，零个或者多个数据元素的有限序列。
空表：没有数据元素的线性表。
举例说明：
1、英文26个字母属于线性表
2、12星座是一个线性表
3、公司的组织架构不属于线性表（一个领导可能管理多个下层）
4、同学间的友谊不属于线性表（一个同学可能有多个朋友）
线性表的逻辑特征
- 在非空的线性表，有且仅有一个开始结点，它没有直接前驱，而仅有一个直接后继。
- 有且仅有一个终端结点，它没有直接后继，只有一个直接前驱。
- 除首尾结点外，中间的结点都有且仅有一个直接前驱和一个直接后继。
线性表的类型定义、基本操作
抽象数据类型表示
ADT List{
数据对象：D={ai|ai属于Elemset,(i=1,2,...,n,n>=0)}
数据关系：R={<ai-1,ai>|ai-1,ai属于D,(i=2,3,...,n)}
基本操作：
InitList(&L);
DestroyList(&L);
ListInsert(&L,i,e);
ListDelete(&L,i,&e);
……等等
}ADT List
基本操作
不需要死记硬背，大概知道有这么一些操作即可！
归纳基本操作就是：增、删、补、查···········
- （1）
InitList(&L)（Initialization List）//初始化
操作结果：构造一个空的线性表L。 - （2）
DestroyList(&L)//销毁
初始条件：线性表L已经存在。
操作结果：销毁线性表L。 - （3）
ClearList(&L)//清除
初始条件：线性表L已经存在。
操作结果：将线性表L重置为空表。 - （4）
ListEmpty(L)//判断空表
初始条件：线性表L已经存在。
操作结果：若线性表L为空表，则返回TRUE；否则返回FALSE。 - （5）
ListLength(L)//求线性表的长度
初始条件：线性表L已经存在。
操作结果：返回线性表L中的数据元素个数。 - （6）
GetElem(L,i,&e)//获取线性表特定元素
初始条件：线性表L已经存在，。
操作结果：用e返回线性表L中第i个数据元素的值。 - （7）
LocateElem(L,e,compare())//查找线性表的元素（根据特殊条件）
初始条件：线性表L已经存在，compare()是数据元素判定函数。
操作结果：返回L中第1个与e满足compare()的数据元素的位序。若这样的数据元素不存在则返回值为0。 - （8）
PriorElem(L,cur_e,&pre_e)//求一个元素的前驱
初始条件：线性表L已经存在。
操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱；否则操作失败，pre_e无意义。 - （9）
NextElem(L,cur_e,&next_e)//求一个元素的后继
初始条件：线性表L已经存在。
操作结果：若cur_e是L的数据元素，且不是第最后个，则用next_e返回它的后继；否则操作失败，next_e无意义。 - （10）
ListInsert(&L,i,e)//插入线性表元素
初始条件：线性表L已经存在，。
操作结果：在L的第i个位置之前插入新的数据元素e，L的长度加一。
插入元素e之前（长度为n）：。
插入元素e之后（长度为n+1）：。 - （11）
ListDelete(&L,i,&e)//删除指定元素
初始条件：线性表L已经存在，。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减一。
删除前（长度为n）：。
删除后（长度为n-1）：。 - （12）
ListTraverse(&L,visited())//遍历所有元素
初始条件：线性表L已经存在。
操作结果：依次对线性表中每个元素调用visited()。
小结
这里暂时记录这些了，为了内容上的连贯性，这里相当于简单总结引出了线性表的概念和理解。上述所设计的定义、还有程序函数，都是伪代码，不必纠结程序语法问题，关键我认为要理解其中的思路逻辑，指导如何操作的。下面将分别用两篇来总结线性表的两种表示方法，即线性表的顺序表示和链式表示！
参考资料：
青岛大学.王卓.数据结构与算法
《数据结构 C语言版》.严蔚敏
《大话数据结构》.程杰
欢迎关注本人微信公众号：那个混子
记录自己学习的过程，分享乐趣、技术、想法、感悟、情感！
单片机类嵌入式交流学习可加企鹅群：120653336
