【数据结构学习-线性表顺序结构】数据结构基础学习笔记

线性表（a1,a2,a3…ai-1,ai,ai+i,…an）
由零个或者多个数据元素组成的有限序列
注意：
1.有先后顺序
2.如果存在多个元素，那么第一个元素没有前驱，最后一个元素没有后继。其它元素都有一个前驱和一个后继。
3.ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。
4.线性表元素的个数n(n>=0)就是线性表的长度。
n=0时，线性表为空。

线性表的数据类型

ADT 抽象数据类型名
Data
 	数据元素之间逻辑关系的定义
 Operation 
 	 操作
 endADT

//
ADT 线性表(List)
线性表数据类型集合为{a1,a2,a3…an}
每个元素的类型都是DataType
数据元素之间的关系都是“一对一”

//Operation
1.InitList(*L):初始化操作，建立一个空的线性表L
2.ListEmpty(L):判断线性表是否为空表，若线性表为空，则返回true,否则返回false。
3.ClearList(*L)：将线性表清空
4.GetElem(L,i,*e):将线性表L中的第i个位置元素值返回给e
返回数组下标为i-1的值。
ElemType *e:表示地址
5.LocateElem(L,e):在线性表L中查找与给定值e相等的元素,如果查找成功，返回该元素在表中序号表示成功，否则，返回0表示失败。
6.ListInsert(*L,i,e):在线性表L中第i个位置插入新元素e
注意：
①时间复杂度为O(n)
②如果插入位置不合理，抛出异常，插入的合理位置：1<=i<=length+1
③从最后一个元素开始遍历到第i个位置，分别把它们往后移动一个位置。
④将要插入的元素填进第i个位置
⑤线性表长加1【不要忘记！！】

length+1:表示要插入的位置在原数组的最后一个元素后面，即插入的位置在表尾。
7.ListDelete(*L,i,*e):删除线性表L中第i个位置元素，并用e返回其值。
时间复杂度：O(n)
①删除位置不合理，抛出异常，合理位置：1<=i<=length
②取出删除元素，data[i-1]
③从删除位置到最后一个元素位置，分别将它们向前移动一个位置。
④表长减1【不要忘记！！】

8.ListLength（L）：返回线性表L的元素个数/就是线性表长度
注意：在线性表中，序号从1开始。

endADT

#define MAXSIZE 20 //数组的长度
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int length;//线性表当前长度

}SqList;

//

转自小甲鱼