【数据结构】五分钟自测主干知识（二）

���关数组的基本工具类，看这个就行啦（含很多C语言基本操作）

书继上回，接下来的内容更加干货而精彩！

2.1线性表的基本概念

线性表（Linear List）是（）个数据元素的有限序列，这些数据元素同属于一个集合，zai这个序列中相邻的数据元素之间存在一种相对的位置关系，称为序偶关系。线性表通常记为：

 正是标志数据元素相对位置的一个编号，称为位序

线性表中元素的个数n称为线性表的长度，当n=0时为空表

线性表的抽象数据类型定义如下：（这些也是初学者学C语言经常用到的）

ADT List{

数据对象:={| ElemSet,i=1,2,…,n,n≥0,ElemSet 为元素集合}

数据关系:={|,i=2,...,n)

基本操作()：

InitList(&L)

操作结果:创建一个空的线性表L。

DestroyList(&L)

操作结果:销毁线性表L。

参数说明:线性表L已存在。

ClearList(&L)

操作结果:将线性表L置空。

参数说明:线性表L已存在。

ListEmpty(L)

操作结果:检测线性表L是否为空,若线性表L为空则返回 TRUE;否则返回 FALSE。

参数说明:线性表L已存在。

ListLength(L)

操作结果:返回线性表L中的元素个数,即线性表长度。

参数说明:线性表L已存在。

GetElem(L,i,&e)

操作结果:将线性表L中位序为i的元素通过参数e 返回。

参数说明:线性表L已存在,且1≤i= L.MaxSize) {printf("插入失败\n");return false;}for (int j = L.length; j >= i; j--) {L.elem[j] = L.elem[j - 1];}L.elem[i - 1] = e;L.length++;printf("插入成功\n");return true;}

我们的算法需要具有健壮性（详见上一讲），有必要进行错误处理，这里我们先用printf显示，后面我们会使用ErrorMsg方法，处理错误信息

void ErrorMsg(const char* a) {//简易版，可以试试printf(a);}

6.增大表容量

第一种方法

void IncreaseSize(SqList& L, int len) {//第一种ElemType* p = L.elem;L.elem = (ElemType*)malloc((L.MaxSize + len) * sizeof(ElemType));for (int i = 0; i  
 更推荐第二种方法
 
#define LIST_INC_SIZE 20void Increment(SqList& L, int inc_size = LIST_INC_SIZE) {ElemType* a;a = new ElemType[L.MaxSize+inc_size];if (!a) { ErrorMsg("分配内存错误"); return; }for (int i = 0; i  
使用第二种方法，从而我们上面第五条的算法可以改进为（优化两处错误处理）
 
bool ListInsert(SqList& L, int i, ElemType e) {//插入 if (iL.length + 1) {ErrorMsg("i值非法\n");//还有这里，这样可以通过修改ErrorMsg这个方法来“重用”，管理更加灵活return false;}if (L.length == L.MaxSize) {//我改动的是这里Increment(L);//修改此处错误处理，显得更加合理}for (int j = L.length; j >= i; j--) {L.elem[j] = L.elem[j - 1];}L.elem[i - 1] = e;L.length++;printf("插入成功\n");return true;}
 
【练习】：算算时间复杂度
 
顺序表的插入操作与插入点有关。长度为n的顺序表中，如果插入位置恰为n+1，那么元素移动次数为0;如果插入位置是1，那么元素移动次数为n。一般地，如果插入位置是i，则元素移动次数为n+1-i。
 
如果考虑在所有位置插入概率相同，那么每个位置插入概率都是1/(n+1），这样等概率情况下顺序表插入元素的平均移动次数是
  
由此看出顺序表插入元素的时间复杂度为
 
7.删除元素
 
bool ListDelete(SqList& L, int i, ElemType& e) {//删除 if (iL.length){ErrorMsg("删除失败\n");return false;}e = L.elem[i - 1];for (int j = i; j  
【练习】：同理算算这个时间复杂度
 
略去同上分析
  
因此顺序表删除元素的时间复杂度也是
  
综上可看出，顺序表的插入和删除平均都要移动约一半数量的元素。当顺序表长度特别大的时候，这个时间消耗不容忽视，这也是顺序存储的一大缺陷。
 
【最后一练】利用两个顺序表La和Lb分别表示两个集合和，求集合。
 
算法参考：
 
void Union(SqList& La, SqList& Lb) {for (int i = 0; i  
内容过多，分开一次讲，主打一个快速过目知识点，查漏补缺式复习
 
下一讲非常重要，也是难点，学完下一讲【线性表的链式表示】，链表不愁！
 
附上链接：【数据结构】五分钟自测主干知识（三）
 
http://t.csdnimg.cn/ZRJdMhttp://t.csdnimg.cn/ZRJdM