数据结构与算法（青岛大学-王卓老师）——学习笔记（第2周）

文章目录 线性表顺序存储结构的总结

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的位置，未找到则返回0
int LocaltElem(SqList& L, ElementType e)
{for(int i=0;i<L.length;i++)if(L.elem[i]==e)return i+1;return 0;
}// 向线性表中存取数据
void add_num(SqList& L)
{for(int i=0;i<15;i++){L.elem[i]= i;}L.length = 15;}// 显示线性表中数据
void show_SqList(SqList L)
{for(int i = 0;i<L.length;i++)printf("%d ",L.elem[i]);printf("\n");printf("length:%d",L.length);
}int main()
{		SqList L;int ret;ret = InintListList(L);add_num(L);show_SqList(L);// DestoryList(L);// printf("%d\n",IsEmpty(L)); //int e;//printf("e:%d\n",e);//ret = GetElem(L,5,e);//printf("e:%d\n",e);printf("ret:%d",ret);getchar();return 0;
}

p18 线性表的顺序存储结构的表示与实现

// 查找线性表中值为e的位置，未找到则返回0
int LocaltElem(SqList L, ElementType e)
{for(int i=0;i<L.length;i++)if(L.elem[i]==e)return i+1;return0
}

分析其算法复杂度：

对于线性表中有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<L.length;j++)L.elem[j-1] = L.elem[j];L.length--;return OK;
}

算法复杂度分析：

删除的元素是最后一个（第n个），移动元素为0个；删除倒数第二个元素，移动元素为1个；删除第一个元素，移动元素为n-1个；

算法时间复杂度O(n)

顺序表的删除算法时间复杂度比较高，比较麻烦。

p21 线性表的顺序存储结构的总结：

线性表顺序存储结构的总结