浙大_数据结构_第二讲_线性结构_笔记
2.1 线性表及其实现
2.1.1 引子:多项式的表示
方法1:顺序存储结构直接表示
可以看出,这样的存储方法方便,但是会造成空间的极大浪费,并且运算时也可能会有很多无意义的”0+0”运算.
方法2:顺序存储结构表示非零项 结构数组
使用结构数组只要保存非零项就可以了.可见,空间结构大大地节省了.
这样的保存方法运算如下:
因为指数大小是有序存储的,只要按顺序依次比较P1,P2的指数,指数大的一方输出,然后剩下的接着比较;如果遇到指数相等的情况就把两者的系数相加.这样的计算效率不算差.
方法3:链表结构存储非零项
同样是按照有序(指针递减)的方式排列.它的加法运算和方法2类似:从头开始依次比较指数大小,输出指数大的剩下的继续比较,指数相等时系数相加.
2.1.2 线性表及顺序存储
什么是线性表
多项式问题表示的启示
- 同一个问题可以有不同的表示(存储)方法
- 有一类共性问题:有序线性序列的组织和管理
线性表(Linear List):由同类型数据元素构成的有序序列的线性结构.
- 表中元素个数称为线性表的长度
- 线性表没有元素时.称为空表
- 表起始位置称表头,表结束位置称表尾
线性表的抽象数据类型描述
类型名称: 线性表(List)
数据对象集: 线性表是n(n>=0)个元素构成的有序序列(a1.a2,…,an)
操作集: 线性表L ∈ List,整数i表示位置,元素X ∈ ElementType,线性表的基本操作有:
- List MakeEmpty(): 初始化一个空线性表L
- ElementType FindKth(int K,List L): 根据位序K,返回相应的元素
- int Find(ElementType X,List L): 在线性表中查找X第一次出现的位置
- void Insert(ElementType X,int i,List L): 在位序i前插入一个新元素X
- void Delete(int i,List L): 删除位序为i的元素
- int Length(List L): 返回线性表L的长度n
线性表的顺序存储实现
符号->老师念做”point”,指向.
主要操作的实现:
- 初始化
- 查找
2.1.3 顺序存储的插入和删除
- 插入
先移动,再插入;注意移动的顺序是从后面往前依次往后挪而不是从前面开始挪.
以上代码没考虑是否插入成功的结果返回.
- 删除
把i之后的元素往前挪即可以完成删除操作.
索引i要进行数据合法性检查.
2.1.4 线性表的链式存储实现
区别上面数组存储线性表的方式:数组方式相邻的两个元素无论逻辑还是物理上都是相连的;而链表形式只是逻辑上相连而不要求物理上相连.
主要操作的实现
- 求表长(遍历)
- 查找(遍历)
- 插入
注意i==1 插入到链表头上的处理
- 删除
注意要将被删除节点占用的空间释放掉!
2.1.6 广义表与多重链表
注意一个链表节点有三个属性:y元素链表指针,x的指数(常数),指向下一个x链表元素的指针.这个表就称为广义表.
广义表
广义表(Generalized List)
- 广义表是线性表的推广
- 对于线性表而言,n个元素都是基本的单元素
- 广义表中,这些元素不仅可以使单元素也可以是另一个广义表
用的是C语言的union关键字实现的.联合体union内部的各个元素共用一个内存首地址,union内的各个元素不能共存,也就是”互斥“的.
上图结构体定义中使用Tag变量作为标记来区分union中存储的数据类型.
广义表是多重链表的一个例子.
多重链表
多重链表: 链表中的节点可能同时隶属于多个链
- 多重链表中的结点的指针域会有多个,如前面例子里包含了Next和SubList两个指针域
- 但包含两个指针域的链表并不一定是多重链表.比如双向链表不是多重链表
多重链表有广泛的用途:
基本上如树,图这样相对复杂的数据结构都可以采用多重链表方式实现存储.
矩阵存储的例子
矩阵A存储的多重链表图
Term类型节点有两个指针,分别指向同一行和同一列,且行列都是循环链表.这种节点既属于行有属于列,构成的结构为十字形,所以又叫十字链表.
入口节点也是Term类型,存的数表示这个矩阵有4行5列,非零项个数为7.
Head头节点也有两个指针,分别指向行和列两个方向.和Term类似,但是它内部存储的内容和Term类型节点不一样.所以同样可以使用Tag+union联合体的方式把它们串在一起:
未完待续