1.线性表的基本概念

• 定义

  线性表（Linear List）是具有相同数据类型的n个数据元素的有限序列。

  • n为表长，n=0时线性表是个空表

• 前驱、后继

  • 前驱：其中一个数据元素的前一个元素。第一个元素没有前驱。
  • 后继：其中一个数据元素的后一个元素。最后一个元素没有后继。

• 存储/物理结构

  • 顺序表（顺序存储）
  • 链表（链式存储）

2.顺序表

2.1 顺序表的定义

• 顺序表定义

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

  是用一组地址连续的存储单元依次存储线性表中的数据元素。

  • 特点：

    1.表中元素的逻辑顺序与物理顺序相同。

    2.可以随机存取——知道顺序表起始位置LOC(A)和每个元素所占内存的大小sizeof(ElemType)后，可知道任意一个元素的位置。

• 优点

  1.可随机访问，O(1)时间内找到指定元素；

  2.存储密度高，每个结点只存储数据元素。

• 缺点

  1.元素的插入和删除要移动大量数据元素。

  2.需要连续存储空间，不够灵活。

2.1.1 静态分配

//静态分配结构存储
#define MaxSize 10 //最大长度
typedef struct{int data[MaxSize]; //静态数组存放数据元素int length; //顺序表当前长度
}SqList; //顺序表类型定义//静态分配初始化
void InitList(SqList &L){L.Length=0;
}

• 如果数组存满怎么办？

  没办法了，因为顺序表表长刚开始确定后就无法改变，∴有了动态分配

2.1.2 动态分配

//动态分配结构存储
#define InitSize 100 //表长度的初始定义
typedef struct{ElemType *data; //指示动态分配数组的指针int MaxSize; //最大容量int length; //当前个数
}SeqList;//动态分配初始化
void InitList(SeqList &L){L.data=(ElemType*)malloc(MaxSize*sizeof(ElemType));L.length=0;L.MaxSize=InitSize;
}

C动态分配语句

L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);
free(L.data);

C++动态分配语句

L.data=new ElemType[InitSize];
delete[]指针变量名;
或
delete 指针变量名;

• 增加动态数组长度

  void IncreaseSize(SeqList &L,int len){int *p=L.data; //将表中数据存储到p中L.data=(int*)malloc((L.MaxSize+len)*sizeof(int)); //开辟新空间for(int i=0;i<L.length;i++){L.data[i]=p[i]; //数据复制到新区域}L.MaxSize=L.MaxSize+len;free(p);
  }
  

• 注：动态分配不是链式存储，同样顺序存储，只是空间大小可变。

2.2 顺序表的插入

• 原理

  在线性表L的第i个位置插入元素e：

  将第i个元素及其后面的所有元素向后移一位，腾出空位插e。

  

//在L的位序i处插入元素e
bool ListInsert(SqList &L,int i,int e){//判i范围是否有效if(i<1||i>L.length+1)return false;//判存储空间是否已满if(L.length>=MaxSize)return false;//将第i个元素及之后元素后移for(int j=L.length;j>=i;j--) {L.data[j]=L.data[j-1]; //注意：位序和数组下标的关系，并从后面元素依次移动}L.data[i-1]=e;L.length++;return true;
}

• 时间复杂度

  • 最好情况：在表尾插入，元素后移不用执行，O(1)。
  • 最坏情况：在表头插入，元素后移执行n次，O(n)。
  • 平均情况：O(n/2)，即O(n)。

2.3 顺序表的删除

• 原理

  删除顺序表L中的第i个元素：

  将被删元素赋给引用变量e，将第i+1个元素及其后的所有元素往前移一位。

  

//删除L中的第i个元素，并用返回
bool ListDelete(SqList &L,int i,ElemType &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;
}

• 时间复杂度

  • 最坏情况：删除表尾元素，无需移动元素，O(1)。
  • 最好情况：删除表头元素，需移动除表尾外的所有元素，O(n)。
  • 平均情况：O(n/2)，即O(n)。

2.4 顺序表的查找

2.4.1 按位查找

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

• 时间复杂度：O(1)

2.4.2 按序查找

int LocateElem(SqList L,ElemType e){int i;for(i=0;i<L.length;i++){if(L.data[i]==e)return i+1; //找到了返回位序}return 0; //没找到返回0
}

• 时间复杂度：O(n)

*完整代码 顺序表静态存储

//顺序表 静态分配 线性表下标从0开始
#include<stdio.h>#define ElemType int//静态结构体
#define MaxSize 99
typedef struct {ElemType data[MaxSize];int length;
}SqList;//初始化
void InitList(SqList &L)
{L.length = 0;
}//求表长
int Length(SqList &L) 
{return L.length;
}//按值查找
int LocateElem(SqList &L,ElemType e) 
{for (int i = 0; i < L.length; i++) {if (L.data[i] == e) {return i + 1;}}return 0;
}//按位查找
int GetItem(SqList& L, int i) 
{return L.data[i-1]; //i是位序，而顺序表从0开始存的，所以i要-1
}//插入操作
bool ListInsert(SqList& L, int i, ElemType e) 
{if (i<1 || i>L.length)return false;if (L.length >= MaxSize)return false;for (int j = L.length; j >= i; j--) {L.data[j] = L.data[j - 1];}L.data[i-1] = e; L.length++;return true;
}//删除操作
bool ListDelete(SqList& L, int i, ElemType& 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;
}//判空操作
bool Empty(SqList& L)
{if (L.length == 0)return true;elsereturn false;
}//销毁操作
void DestroyList(SqList &L)
{L.length = 0;
}//输出
void PrintList(SqList& L) 
{for (int i = 0; i < L.length; i++){printf("%d ", L.data[i]);}printf("\n");
}int main()
{SqList L;InitList(L);//赋值for (int i = 0; i < 10; i++){L.data[i] = i;L.length++;}PrintList(L);printf("插入:\n");int e = -1, pos = 4;ListInsert(L, pos , e);PrintList(L);printf("删除:\n");int a;ListDelete(L, pos, a);PrintList(L);printf("%d\n", a);printf("按值查找:\n");pos = LocateElem(L, 5);printf("%d\n", pos);printf("按位查找:\n");printf("%d", GetItem(L, 3));
}

*完整代码 顺序表动态存储

//顺序表 动态分配 
#include<stdio.h>
#include <stdlib.h>#define ElemType int//静态结构体
#define InitSize 2
typedef struct {ElemType *data;int length;int MaxSize;
}SeqList;//初始化
void InitList(SeqList& L)
{L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));L.length = 0;L.MaxSize = InitSize;
}//增加动态数组长度
void IncreaseSize(SeqList& L, int len) {int* p = L.data; //将表中数据存储到p中L.data = (int*)malloc((L.MaxSize + len) * sizeof(int)); //开辟新空间for (int i = 0; i < L.length; i++){L.data[i] = p[i]; //数据复制到新区域}L.MaxSize = L.MaxSize + len;free(p);
}//求表长
int Length(SeqList& L)
{return L.length;
}//按值查找
int LocateElem(SeqList& L, ElemType e)
{for (int i = 0; i < L.length; i++){if (L.data[i] == e){return i + 1;}}return 0;
}//按位查找
int GetItem(SeqList& L, int i)
{return L.data[i - 1]; //i是位序，而顺序表从0开始存的，所以i要-1
}//插入操作
bool ListInsert(SeqList& L, int i, ElemType e)
{if (i<1 || i>L.length)return false;if (L.length >= L.MaxSize)return false;for (int j = L.length; j >= i; j--){L.data[j] = L.data[j - 1];}L.data[i - 1] = e; L.length++;return true;
}//删除操作
bool ListDelete(SeqList& L, int i, ElemType& 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;
}//判空操作
bool Empty(SeqList& L)
{if (L.length == 0)return true;elsereturn false;
}//销毁操作
void DestroyList(SeqList& L)
{free(L.data);L.data = NULL; // 避免悬挂指针L.length = 0;
}//输出
void PrintList(SeqList& L)
{for (int i = 0; i < L.length; i++){printf("%d ", L.data[i]);}printf("\n");
}int main()
{SeqList L;InitList(L);IncreaseSize(L, 9);//赋值for (int i = 0; i < 10; i++){L.data[i] = i;L.length++;}PrintList(L);printf("插入:\n");int e = -1, pos = 5;ListInsert(L, pos, e);PrintList(L);printf("删除:\n");int a;ListDelete(L, pos, a);PrintList(L);printf("%d\n", a);printf("按值查找:\n");pos = LocateElem(L, 5);printf("%d\n", pos);printf("按位查找:\n");printf("%d", GetItem(L, 3));DestroyList(L);
}