考研数据结构线性表之顺序表

第二章线性表

1.1线性表的定义和基本操作

定义：线性表时具有\textcolor{blue}{相同数据类型}的n（n≥0）个数据元素的\textcolor{blue}{有限序列}，其中n为表长，当n=0时线性表是一个空表。若用L命名线性表，则其一般表示为：L=(a_1,a_2,...,a_i,a_{i+1},...,a_n).

涉及概念：

1. $a_i$ 是线性表的“第i个”元素线性表中的位序。（位序是从一开始，但是数组是从0开始的）

2. $a_1$ 是表头元素， $a_n$ 是表尾元素。

3.除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继。

线性表的基本操作：

当需要将参数修改结构带回来时。加上“&”。

InitList(&L)：初始化表。构造一个新的空线性表L，分配内存空间。

DestroyList(&L):销毁操作。

ListInsert(&L,i,e):插入操作。在第i个位置插入元素e。

ListDetele(&L,i,&e):删除操作。在第i个位置删除元素e。

LocateElem(L,e):按值查找元素。

GetElem(L,i):按位查找元素。

其他操作：

Length(L):求表长。返回线性表长度。

PrintList(L):输出操作。

Empty(L):判空操作。如果L为空表，返回true。

注：为什么要使用这些封装函数？

1.定义的数据结构方便别人使用；

2.避免重复工作，降低出错风险。

1.2线性表的顺序存储

顺序表定义：用顺序存储的方式实现线性表的顺序存储。

顺序表操作的实现：

顺序表的实现——静态分配：

//静态的大小一旦生成就不可变了

#define MaxSize = 10
typedef struct{int data[MaxSize];  //用静态的数组存放数据元素  int length;         //顺序表当前的长度
}SqList;                //顺序表的类型定义

初始化函数：

void InitList(SqList &L){for(int i=0;i<MaxSize;i++)L.data[i]=0;L.length=0;
}

插入函数：

bool ListInsert(SqList &L,int i,int e){if(i<1||i>L.length+1)       return false;if(L.length>=MaxSize)       return false;for(int j=L.length;j>=i;J--)    //第i个元素及之后的元素后移L.data[j]=L.data[j-1];L.data[i]=e;            //给第i个赋值L.length++;             //长度+1return true;
}

这个函数的的最好情况是0，最坏情况是n，因此平均时间复杂度为 $\frac{n}{2}$

删除函数：

bool ListDelete(SqList &L,int i,int &e){    //这里的e是用来存储删除的那个元素的值的if(i<1||i>L.length)     return false;e=L.data[i-1];          //位序跟数组不一样for(int j=i;j<L.length;j++)     //注意这里是＜，不是≤.L.data[j-1]=L.data[j];L.length--;return true;
}

这个函数的的最好情况是0，最坏情况是n-1，因此平均时间复杂度为 $\frac{n-1}{2}$

按位序查找元素函数：

int GetElem(SqList L,int i){return L.data[i-1];
}

按值查找元素函数

int Locate(SqList L,int e){for(int i=0;i<L.length-1;i++)if(L.data[i]==e)return i+1;return 0;
}

顺序表的实现——动态分配：

#define InitSize = 10
typedef struct{ElemType *data;     //指示动态分配数组的指针int MaxSize;        //顺序表的最大容量int length;         //顺序表当前的长度
}SqList;                //顺序表的类型定

这里面就涉及了怎么申请空间，并让data指过去，在C/C++中动态申请和释放内存空间的函数

C   ——  malloc、free函数L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize) //后面的*是乘号的意思
C++ ——  new、delete关键字

初始化函数：

void InitList(SqList &L){L.data=(int *)malloc(InitSize*sizeof(int));L.length=0;L.MaxSize=InitSize;
}
//增加动态数组长度的函数
void IncreaseSize(SqList &L,int len){int* p=L.data;L.data=(int *)malloc((L.Maxsize+len))*sizeof(int)); //data指向新产生的空间for(int i=0;i<L.length;i++){L.data[i]=p[i];             //将数据复制到新区域}L.MaxSize=L.MaxSize+len;free(p);
}