线性表总结
线性表是最基本、最简单、也是最常用的一种数据结构。线性表是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限数列(a1,a2,、、、an)。
其中:n:数据元素的个数,也称表的长度。
空表:n=0,记为()。
举例:
由26个英文字母构成的表(a,b,c,、、、、z)是一个线性表。
我们常玩的扑克牌,数据元素----牌,是由牌点,花色两项组成的,是复合数据类型,这种类型的线性表称为复合线性表。
线性表的特征:
1. 在非空的线性表,有且只有一个开始结点a1,它没有直接前趋,而仅有一个直接后继a2.;
2. 有且只有一个终端结点an,它没有直接后趋,而仅有一个直接前趋a(n-1);
3. 其余的内部节点ai(2=<i=<n-1)都有且仅有一个直接前趋a(i-1)和一个直接后继a(i+1);
线性表的基本运算:
1. 求表长----求线性表中元素的个数;
2. 遍历----从左到右(从右到左)扫描(或读取)表中的各元素。
3. 按编号查找----找出表中的第i个元素;
4. 按特征查找----按某个特定值查找线性表;
5. 插入----在第i个位置上(即原第i个元素前)插入一个新元素
6. 删除----删除原表中的第i个元素
7. 排序----按元素某特征值的递增(或递减)排序,重排表中各元素
顺序表是很守规矩的,每个元素都前后有序、整整齐齐地站在一起。如果有人有急事,想插到顺序表前边去,该怎么保持顺序表的整齐?
顺序表的插入:
图一:
图二:
图一是原来的顺序表,然后我要在3的位置插入x,这个是怎么实现的呢?
这个它是从后面最后一个元素开始往后移,然后空出3的位置插入x。这个就是顺序表的插入,为什么要这样插入呢?因为顺序表是很守规矩的,顺序表中的每个元素都有它自己的位置,不能随便插入的。看看实现代码