文章目录线性表顺序存储结构的总结
p17 线性表的顺序存储结构的表示与实现
线性表的顺序存储表示：
一般采用数组的方式，但是有插入、删除等操作，这个歌数组是变长的，所以还需要引入一个变量来记录线性表的长度 。
既可以使用数组的方式定义线性表，也可以用动态数组的模式定义 。
定义线性表
对线性表的操作：1.通过 L; L.elem[i] 进行操作 2.也可以通过指针：* L ; L->elem[i]的方式进行操作 。
线性表的基本操作
预定义：
#include#include typedef int ElementType;typedef int status;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define MaxSize 100typedef struct{ElementType* elem;int length;}SqList;// 初始化一个空的线性表status InintListList(SqList &L){L.elem = new ElementType[MaxSize];if(!L.elem) exit(OVERFLOW);L.length=0;return OK;}// 销毁线性表void DestoryList(SqList& L){ // 判断是否分配出了内存if(L.elem) delete L.elem;// 释放存储空间}// 清空线性表void ClearList(SqList& L){L.length = 0;} //求线性表的长度int GetLength(SqList& L){return (L.length);}// 判断线性表是否为空int IsEmpty(SqList& L){if(L.length==0) return 1;else return 0;}// 顺序表的取值int GetElem(SqList& L,int i , ElementType& e)// 通过引用类型ElemType& e 作为返回值{if(i<1||i>L.length) return ERROR;e = L.elem[i-1];return OK;}// 查找线性表中值为e的位置，未找到则返回0int LocaltElem(SqList& L, ElementType e){for(int i=0;i
p18 线性表的顺序存储结构的表示与实现
// 查找线性表中值为e的位置，未找到则返回0int LocaltElem(SqList L, ElementType e){for(int i=0;i
分析其算法复杂度：
对于线性表中有n个元素：
算法时间复杂的o(n)
p19 线性表的顺序存储结构的表示与实现(插入操作)
算法思想：
// 顺序表的插入 传入序号、传入插入的值int Listinsert_sq(SqList& L,int i,ElementType e){if(i>L.length||i<1) return ERROR;if(L.length == MaxSize) return OVERFLOW;for(int j=L.length-1;j>=i-1;j--){L.elem[j+1]=L.elem[j];}L.elem[i-1] = e;L.length++;return OK;}
算法时间复杂的分析：
共有n+1中插入位置，则有1/(n+1)的概率 。插入最后一个位置（n+1）,需要后移0个元素；插入第n个位置，需要后移1个元素；插入第n-1个位置，需要后移2个元素； 。。。。；插入第一个位置，需要后移n个元素 。
算法复杂的为O(n)
在顺序表中插入元素是比较慢的
p20 线性表的顺序存储结构的表示与实现(删除操作)
算法思路：
// 顺序表的删除 出入序号int DeleteList_sq(SqList& L , int n){if(n>L.length||n<1) return ERROR;for( int j =n ;j
【青岛大学-王卓老师数据结构与算法——学习笔记（第2周）】算法复杂度分析：
删除的元素是最后一个（第n个），移动元素为0个；删除倒数第二个元素，移动元素为1个；删除第一个元素，移动元素为n-1个；