线性表 王炸篇 上
一、线性表的定义
1.1 定义
• n个(n≥0)具有相同特性的数据元素的有限序列
表示：L =（a1, a2, … ai-1，ai，ai＋1，… an），n是线性表的长度
1.2 特点
• 表中元素个数有限
• 表中元素具有顺序性
• 表中元素数据类型相同
• 表中元素具有抽象性
二、线性表的顺序表示与基本操作
2.1 线性表的顺序表示
• 定义：指的是用一组地址连续的存储单元依次存储线性表中的数据元素
【注意】
| 线性表的顺序存储又称为顺序表 |
| 逻辑上相邻的数据元素，物理上也相邻 |
| 顺序表是随机存取的存储结构 |
| 若已知表中首元素在存储器中的位置，则可求出线性表中其他元素的存放位置 |
| 线性表的起始地址为a1,称作线性表的基地址 |
2.2 顺序表的类型描述
//no.1 **静态分配**
#define MaxSize 50//宏
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
SqList L;
L.data[0] = 0;
L.length = 1;
//no.2 **动态分配**
#define InitSize 50
typedef int ElemType;
typedef struct{
ElemType *data;
int length,MaxSize;
}SqList;
SqList L;
L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
L.data[0] = 0;
L.length = 1;
L.MaxSize = InitSize;//当空间不足时，调用realloc()函数2.3 顺序表基本操作-初始化操作
目标：构造一个空表，设置表的起始位置、表长及可用空间
#define OK 1
#define OVERFLOW 0
//构造一个空的线性表L
int InitSqList(SqList &L){
L.data = (ElemType *)malloc(sizeof(ElemType)*InitSize);
if(!L.data)
exit(OVERFLOW); // 存储分配失败
L.length = 0; // 空表长度为0
L.MaxSize = InitSize; // 初始存储容量
return OK;
}2.4 顺序表基本操作-插入操作
目标：在顺序表L的第i(1≤i≤L.length+1)个位置插入新元素e
插入前：
插入后：
【注意】当插入的位置为第i个结点时，需要移动 n-i+1 个元素
int ListInsert(SqList &L,int i,ElemType e)
{
if(i<1||i>L.length+1)//判断插入位置i 是否合法
return ERROR;
if(L.length>=MaxSize)//判断顺序表的存储空间是否已满
return ERROR;
for(int j =L.length;j>=i;j--)
L.data[j] = L.data[j-1];//将第n至第i 位的元素依次向后移动一个位置，空出第i个位置
L.data[i-1] = e;//将要插入的新元素e放入第i个位置
L.length++;
return OK;//表长加1，插入成功返回OK
}
该算法的时间复杂度分析：
最好情况：在表尾插入（即i = n+1）此时为O(1)
最坏情况：在表头插入（即i = 1）此时为O(n)
平均情况：设
版权声明：本文为lastk原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。