顺序表创建，初始化，赋值，取值，查找，插入与删除（附小例题）_顺序表赋值

---

title: 数据结构学习笔记 —— 线性表
tags: 数据结构

定义

由n(n≥0)个数据结构相同的元素构成的有限序列。

---

重要特点

1）除了第一个元素外，结构中的每一个数据元素均只有一个前驱

2）除了最后一个元素外，结构中的每一个数据元素均只有一个后驱

---

线性表 —— 顺序表

定义

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

---

特点

优点：随机存储

缺点：在做插入和删除操作时，需要移动大量元素。并且当元素多变化大是会造成存储空间浪费。（解决：链式存储）

---

描述

#define MAXSIZE 100
​	typedef struct
​	{
​		ElemType * elem;  //存储空间的地址
​		int length; // 当前长度
​	}SqList;  // 顺序表的结构类型 Sqlist

1
2
3
4
5
6
7

例：

 //构造顺序表
#include<stdio.h>
#define MAXSIZE 100
typedef struct
{
	int* elem;		//声明动态数组
	int length;		//记录表的当前长度
	int maxsize;		//记录表的分配容量（最大长度）
}SqList;
1
2
3
4
5
6
7
8
9

---

顺序表的基本操作

这是下面所使用函数的原型

// 创建顺序表
typedef struct
{
	int* elem;		//声明动态数组
	int length;		//记录表的当前长度
	int size;		//记录表的分配容量（最大长度）
}SqList;

// 初始化顺序表
int Initlist(SqList &L)
{
	L.elem = (int*)malloc(MAXSIZE * sizeof(int));  //构造一个空的顺序表，动态申请存储空间
	if (!L.elem)  //如果申请失败，作出提示并安全退出程序
	{
		printf("初始化失败！");
		exit(0);
	}
	L.length = 0;  //表的初始长度为0
	L.size = MAXSIZE; // 表的存储空间（最大长度）为MAXSIZE

	return L;
}

// 赋值
void get_value(SqList& L)
{
	int i, n;
	//scanf_s("%d",&n);
	for (i = 0; i < L.size; i++)
	{
		L.elem[i] = i + 1;
		L.length++;//长度随赋值情况增加
	}
}

//取值
int GetElem(SqList L, int i, int& e)
{
	if (i < 1 || i > L.length)   //判断i的值是否合理（是否为负数或是否超出表长），不合理返回ERROR
	{
		printf("获取值失败！");
		exit(0);
	}

	e = L.elem[i - 1];  // elem[i - 1]单元存储第i个数据元素

	return e;
} 

//按值查找
int LocateElem(SqList L, int e)
{
    int i ;
    for (i = 0; i < L.length; i++)
	{
	    if (L.elem[i] == e)
        {
			return i + 1;	          //数组下标为i的元素，其序号为i + 1 
        }
	}	      
	return 0;      	//查找失败， 返回0
}

// 插入
void ListInsert(SqList& L, int i, int e)
{	//在顺序表L中第i个位置的新元素e，i值的合法范围是1≤ i ≤L.length + 1
	int j;
	if (i < 0 || i > L.length)
	{
		printf("插入失败！");
		exit(0);
	}
	if (L.length == MAXSIZE)	//当前存储空间已满
	{
		printf("空间已满！");
		exit(0);
	}

	for ( j = L.length; j >= i; j--)
	{
		L.elem[j + 1] = L.elem[j];	// 插入位置及之后的元素后移
	}

	L.elem[j - 1] = e;	// 将新元素e放入第i个位置
	++L.length;		//表长加一
}

void ListDelete(SqList& L, int i)
{
	int j;
	if ((i < 0) || (i > L.length))  //i值不合法
	{
		printf("删除失败！");
		exit(0);
	}

	for ( j = i; j <= L.length - 1; j++)
	{
		L.elem[j - 1] = L.elem[j];	//被删除元素之后的元素前移
	}
	--L.length;	//表长减一
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103

初始化

算法描述

Status InitList(SqList &L) // &L 引用参数类型（因为表L会改变）
{
	L.elem = new ElemType[MAXSIZE];
    if(! L.elem)
    {
        exit(OVERFLOW);  //内存分配失败退出
	}
    l.length = 0;   // 空表长度为0
    return OK;
}
1
2
3
4
5
6
7
8
9
10

例：

#include<stdio.h>
#define MAXSIZE

int main(void)
{
	SqList L;   //声明顺序表
	Initlist(L);  //初始化
	
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11

---

取值（时间复杂度为 O(1) ）

算法描述

Status GetElem(Sqlist L, int i, ElemType &e)
{
	if(i < 1 || i > L.length)   //判断i的值是否合理（是否为负数或是否超出表长），不合理返回ERROR
    {
		return ERROR;
    }
    
    e = L.elem[i - 1];  // elem[i - 1]单元存储第i个数据元素
	
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11

例

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

int main(void)
{	
	int i= 64; 	//取值第64个元素
	int e = 0;
	int t = 0;
	SqList L;  // 声明顺序表
	Initlist(L); //初始化
    get_value(L);  //赋值
	t = GetElem(L, i, e); //取值
	
	printf("输出：%d", t);

	free(L.elem); 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

查找（平均算法复杂度为 O(n) ）

算法描述

//按值查找
Status LocateElem(SqList L, ElemType e)
{
    int i;
    for (i = 0; i < L.length; i++)
	{
	    if (L.elem[i] == e)  
        {
             return i + 1;	          //查找成功， 返回序号 i + 1           
        }      
	}	      
	return 0; 					//查找失败， 返回0
} 

1
2
3
4
5
6
7
8
9
10
11
12
13
14

例

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

int main(void)
{	
	int e;  //要查找的元素
	SqList L;  // 声明顺序表
	Initlist(L); //初始化 
	get_value(L); // 赋值

	printf("请输入1-100中任意整数:");
	scanf_s("%d", &e);
	 
	printf("查找结果：%d", LocateElem(L, e));
	
	free(L.elem);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

---

插入（平均算法复杂度为 O(n) ）

步骤

① 判断插入位置i是否合法（i值的合法范围是1≤i≤n+1），若不合法则返回ERROR（n为原顺序表长度）

②判断顺序表的存储空间是否已满，若满则返回ERROR

③将第n个至第i个位置的元素依次向后移动一个位置，空出第i个位置(i = n + 1时无需移动)

④将要插入的新元素e放入第i个位置

⑤表长加一

算法描述

//插入
Status ListInsert(SqList &L, int i, ElemType e)
{  //在顺序表L中第i个位置的新元素e，i值的合法范围是1≤ i ≤L.length + 1
	if( (i < 1) || (i > L.length + 1) )    //i值不合法
    {
		return ERROR;
	}
    if(L.length == MAXSIZE) //当前存储空间已满
    {
		return ERROR;
	}
    for(j = L.length - 1; j >= i - 1; j--)
    {
		L.elem[j + 1] = L.elem[j];  	// 插入位置及之后的元素后移
    }
    L.elem[i - 1] = e;     // 将新元素e放入第i个位置
    ++L.length;			//表长加一
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

例

int main(void)
{	
	int n;
	int i; //要插入位置
	int e;  //要插入的元素
	SqList L;  // 声明顺序表
	Initlist(L); //初始化 
	get_value(L); // 需要将get_value中的L.size 改为L.size - 1,否则表满，不能插入

	printf("初始表：");
	for (n = 0; n < L.length; n++)
	{
		printf("%d", L.elem[n]);
	}
	printf("\n请输入插入位置（1-10间）:");
	scanf_s("%d", &i);
	printf("请输入插入元素（1-10间）:");
	scanf_s("%d", &e);

	ListInsert(L, i, e);	//插入

	printf("插入后的表：");
	for (n = 0; n < L.length; n++)
	{
		printf("%d", L.elem[n]);
	}
	
	free(L.elem);
	return 0;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

---

删除

步骤

① 判断删除位置i是否合法（i值的合法范围是1≤i≤n+1），若不合法则返回ERROR（n为原顺序表长度）

②将第i + 1个至第n个位置的元素依次向前移动一个位置，（i = n时无需移动）

③表长减一

算法描述

//删除
Status ListDelete(SqList &L, int i)
{
	if( (i < 1) || (i > L.length) )    //i值不合法
    {
		return ERROR;
	}
    for(j = i; j < L.length - 1: j++)
    {
		L.elem[j - 1] = L.elem[j];   //被删除元素之后的元素前移
	}
    --L.length;   //表长减一
    return OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

例

int main(void)
{	
	int n;
	int i; //要删除位置
	SqList L;  // 声明顺序表
	Initlist(L); //初始化 
	get_value(L); // 赋值

	printf("初始表：");
	for (n = 0; n < L.length; n++)
	{
		printf("%d", L.elem[n]);
	}
	printf("\n请输入删除位置（1-10间）:");
	scanf_s("%d", &i);

	ListDelete(L, i); 	//删除第i个

	printf("删除后的表：");
	for (n = 0; n < L.length; n++)
	{
		printf("%d", L.elem[n]);
	}
	
	free(L.elem);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

									顺序表完
1