# 顺序表
# 1. 概念
定义:具有相同数据类型的 n (n≥0) 个数据元素组成的有限
序列。是最简单、最常用的数据结构。
・线性表的顺序表示就是用一组地址连续的存储单
元依次存储线性表的数据元素。
・线性表的这种机内表示称做线性表的顺序存储结
构或顺序映像。
・通常,称这种存储结构的线性表为顺序表。
# 2. 定义
// 静态描述 | |
typedef struct node | |
{ | |
DataType data[maxsize]; | |
int length; | |
}sqlist; | |
sqlist L; | |
// 动态描述 | |
typedef struct node | |
{ | |
DataType *elem; | |
int length; | |
}sqlist; | |
sqlist L; | |
L.elem=(DataType*)malloc(maxsize*sizeof(DataType)) |
# 3. 操作
1) 初始化
void Init_SqList(SqList *L) | |
{ | |
L->data=(DataType *)malloc(MAXSIZE*sizeof(DataType))); | |
// 注动态初始化才需要上一步 | |
L->length=0; | |
} |
2) 插入
在线性表的第 i-1 个元素和第 i 个元素之前插入一个新的元素,先移动,后插入。
步骤:
(1) 将 ai ~ an 顺序向后移动,为新元素让出位置
(2) 将 x 置入空出的第 i 个位置
void InsertList(SeqList *L,DataType x,int i) | |
{ | |
// 在顺序线性表 L 中第 i 个位置插入新的元素 X | |
int j; | |
if(i<1||i>L->length+1) // 此时 i 为元素位置 | |
Error("position error"); // 非法位置,退出 | |
if(L->length>=ListSize) | |
Error("overflow"); // 表空间溢出 | |
for(j=L->length-1;j>=i;j--) | |
L->data[j+1]=L->data[j]; // 从最后一个结点开始往后移 | |
L->data[i-1]=x; // 插入 x,此时 i 为下标 | |
L->length++; // 表长加1 | |
} |
3) 删除
步骤:
(1) 删除 ai
(2) 将 ai+1 ~ an, 顺序向前移动
void DeleteList(Seqlist *L,int i) | |
{ | |
int j; | |
if(i<1||i>L->length) | |
Error("position error"); | |
for(j=i;j<=L->length-1;j++) | |
L->data[j-1]=L->data[j]; // 注意区分此时 i 是作为下标 | |
L->length--; | |
} |
4) 查找
// 按值查找 | |
int location_sqlist(sqlist *L,datatype x) | |
{ | |
// 在顺序线性表 L 中查找值与 x 相等的元素 | |
// 若找到,则返回其在 L 中的位序,否则返回 - 1 | |
int i; | |
i=0; //i 是下标 | |
while(i<=L->length&&L->data[i]!=x) | |
i++; | |
if(i<=L->length) return(i+1) ; | |
else return –1; | |
} | |
// 时间复杂度为:T (n)=O (n) |
5) 顺序表的合并
Void merge(sqlist A,sqlist B,sqlist *c) | |
{ | |
int i,j,k;// 分别表示 A,B,C 的下标 | |
int i=0;j=0;k=0; | |
while (i<=A.length-1 && j<=B.length-1) | |
// 将 A 与 B 当前小的放到 C 中 | |
if(A.data[i]<B.data[j]) | |
C->data[k++]=A.data[i++]; | |
else | |
C->data[k++]=B.data[j++]; | |
while(i<=A.length-1) | |
C->data[k++]=A.data[i++]; | |
while(j<=B.length-1) | |
C->data[k++]=B.data[j++]; | |
} |