首页 计算机科学 数据结构 线性表

# 顺序表

# 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++; // 表长加１
}
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++];
}
-->