数据结构 顺序表

Posted on Edited on In Views: Word count in article: 4.9k Reading time ≈ 49 mins.

一、线性表

线性结构是指结构中的数据元素之间存在着一对一的关系。线性结构的基本特征如下:

 ●有且只有一个“第一元素”;有且只有一个“最后元素”;
 ●除第一元素之外,其他元素都有唯一的直接前趋;.
 ●除最后元素之外,其他元素都有唯一的直接后继。

线性表是一种常用的、简单的数据结构,属于线性结构的范畴

1.1 线性表定义

线性表(linear list)是具有相同数据类型的n(n>=0)个数据元素的有限a序列,通常记为

          (a₁,a₂,…,aₙ₋₁,aₙ)
 其中,数据元素的个数n称为线性表的长度。当n=0时称为空表。从线性表的定义可以看出它的逻辑特征是:在非空的线性表中,有且只有一个起始结点(第一元素)a₁,它没有直接前趋,只有一个直接后继a₂;有且只有一个终端结点(最后元素)aₙ它没有直接后继,只有一个直接前趋aₙ₋₁;而除了a₁和aₙ外,其他的每一个结点aᵢ(2<i<n-1)都有且只有一个直接前趋aᵢ₋₁和一个直接后继aᵢ₊₁

1.2 顺序表定义

 线性表的顺序存储是指用一组地址连续的内存单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表
 在C语言中顺序表通过数组方式实现，数组的创建有两种方式。使用定长数组的方式称为静态分配顺序表，使用动态内存分配的方式称为动态分配顺序表。不了解动态内存分配可参考这篇博客https://blog.csdn.net/kjl167/article/details/123799963

二、静态分配顺序表

2.1 顺序表结构及接口定义

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
#define MAXSIZE 20 //数组大小

typedef	int ElemType; //元素类型重定义，以后元素类型发生改变只用改这里

typedef struct SeqList
{
	ElemType data[MAXSIZE];
	int length; //顺序表当前长度（已存放元素个数）
}SeqList;

void InitSeq(SeqList* p); //顺序表初始化

void SeqListHeadInsert(SeqList* p, ElemType elem); //头部插入元素

void SeqListHeadDelete(SeqList* p); //头部删除元素

void SeqListTailInsert(SeqList* p, ElemType elem); //尾部插入元素

void SeqListTailDelete(SeqList* p); //尾部删除元素

void SeqListInsert(SeqList* p, int pos,ElemType elem); //插入元素到pos位置,位序从1开始算，数组下标从0开始

void SeqListDelete(SeqList* p, int pos); //删除pos位置元素,位序从1开始算，数组下标从0开始

int SeqListFind(SeqList* p, ElemType elem); //查找指定值并返回下标，未找到返回-1 

void SeqListPrint(SeqList* p); //打印顺序表

2.2 顺序表初始化

1
2
3
4
5
void InitSeq(SeqList* p)
{
	assert(p);
	p->length = 0; //顺序表长度置为0
}

2.3 头插元素

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SeqListHeadInsert(SeqList* p, ElemType elem)
{
	assert(p);
	if (p->length == MAXSIZE)
	{
		printf("顺序表已满，插入失败\n");
	}
	else
	{
		int i = p->length - 1; //最后一个元素下标 
		for (i; i >= 0; i--) //最后一个元素开始遍历所有元素分别将它们向后移动一个位置
		{
			p->data[i + 1] = p->data[i];
		}
		p->data[0] = elem; //将元素插入到顺序表头部
		p->length++;
	}
}

2.4 头删元素

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SeqListHeadDelete(SeqList* p)
{
	assert(p);
	if (p->length == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else
	{
		int i = 1;  //第2个元素下标
		for (i; i < p->length; i++) //从第2个元素位置开始遍历到最后一个元素，分别将它们都向前移动1个位置
		{
			p->data[i - 1] = p->data[i];
		}
		p->length--;
	}
	
}

2.5 尾插元素

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
void SeqListTailInsert(SeqList* p, ElemType elem)
{
	assert(p);
	if (p->length == MAXSIZE)
	{
		printf("顺序表已满，插入失败\n");
	}
	else
	{
		p->data[p->length] = elem;
		p->length++;
	}
}

2.6 尾删元素

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
void SeqListTailDelete(SeqList* p)
{
	assert(p);
	if (p->length == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else
	{
		p->length--; //只需将元素个数-1
	}
	
}

2.7 指定位置插入元素

数组下标从0开始，位置从1开始
在这里插入图片描述

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
void SeqListInsert(SeqList* p, int pos,ElemType elem)
{
	assert(p);
	if (pos >= 1 && pos <= p->length+1) //当位置为1(表头)--表尾的后一个位置时合法
	{
		if (p->length == MAXSIZE)
		{
			printf("顺序表已满，插入失败\n");
		}
		else
		{
			int i = p->length - 1; //最后一个元素下标 
			for (i; i >= pos - 1; i--) //pos-1为pos位置元素下标，从最后一个元素开始遍历到pos位置元素，分别将它们向后移动一个位置
			{
				p->data[i + 1] = p->data[i];
			}
			p->data[pos - 1] = elem;
			p->length++;
		}
	}
	else
	{
		printf("位置越界,插入失败\n");
	}
}

2.8 指定位置删除元素

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void SeqListDelete(SeqList* p, int pos)
{
	assert(p);
	if (p->length == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else if(pos >= 1 && pos <= p->length)
	{
		int i = pos; //指定位置的后1个元素
		for (i; i < p->length; i++)
		{
			p->data[i - 1] = p->data[i];
		}
		p->length--;
	}
	else
	{
		printf("位置越界,删除失败\n");
	}
}

2.9 查找指定元素下标

下标从0开始，当有多个元素的值相同时，返回找到的第一个元素下标

1
2
3
4
5
6
7
8
9
10
11
12
13
int SeqListFind(SeqList* p, ElemType elem)
{
	assert(p);
	int i = 0;
	for (i = 0; i < p->length; i++)
	{
		if (p->data[i] == elem)
		{
			return i;
		}
	}
	return -1;
}

2.10 打印顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SeqListPrint(SeqList* p)
{
	assert(p);
	if (p->length == 0)
	{
		printf("顺序表为空\n");
		return;
	}
	int i = 0;
	for (i = 0; i < p->length; i++)
	{
		printf("%d ", p->data[i]);
	}
	printf("\n");
}

2.11 程序源代码

头文件SeqList.h内容：

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
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

#define MAXSIZE 20 //数组大小

typedef	int ElemType; //元素类型重定义，以后元素类型发生改变只用改这里

typedef struct SeqList
{
	ElemType data[MAXSIZE];
	int length; //顺序表当前长度（已存放元素个数）
}SeqList;

void InitSeq(SeqList* p); //顺序表初始化

void SeqListHeadInsert(SeqList* p, ElemType elem); //头部插入元素

void SeqListHeadDelete(SeqList* p); //头部删除元素

void SeqListTailInsert(SeqList* p, ElemType elem); //尾部插入元素

void SeqListTailDelete(SeqList* p); //尾部删除元素

void SeqListInsert(SeqList* p, int pos,ElemType elem); //插入元素到pos位置,位序从1开始算，数组下标从0开始

void SeqListDelete(SeqList* p, int pos); //删除pos位置元素,位序从1开始算，数组下标从0开始

int SeqListFind(SeqList* p, ElemType elem); //查找指定值并返回下标，未找到返回-1 

void SeqListPrint(SeqList* p); //打印顺序表

源文件SeqList.c内容：

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include "SeqList.h"

void InitSeq(SeqList* p)
{
	assert(p);
	p->length = 0;
}


void SeqListHeadInsert(SeqList* p, ElemType elem)
{
	assert(p);
	if (p->length == MAXSIZE)
	{
		printf("顺序表已满，插入失败\n");
	}
	else
	{
		int i = p->length - 1; //最后一个元素下标 
		for (i; i >= 0; i--) //最后一个元素开始遍历所有元素分别将它们向后移动一个位置
		{
			p->data[i + 1] = p->data[i];
		}
		p->data[0] = elem; //将元素插入到顺序表头部
		p->length++;
	}
}

void SeqListHeadDelete(SeqList* p)
{
	assert(p);
	if (p->length == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else
	{
		int i = 1;  //第2个元素下标
		for (i; i < p->length; i++) //从第2个元素位置开始遍历到最后一个元素，分别将它们都向前移动1个位置
		{
			p->data[i - 1] = p->data[i];
		}
		p->length--;
	}
	
}

void SeqListTailInsert(SeqList* p, ElemType elem)
{
	assert(p);
	if (p->length == MAXSIZE)
	{
		printf("顺序表已满，插入失败\n");
	}
	else
	{
		p->data[p->length] = elem;
		p->length++;
	}
}

void SeqListTailDelete(SeqList* p)
{
	assert(p);
	if (p->length == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else
	{
		p->length--; //只需将元素个数-1
	}
	
}

void SeqListInsert(SeqList* p, int pos,ElemType elem)
{
	assert(p);
	if (pos >= 1 && pos <= p->length+1) //当位置为1(表头)--表尾的后一个位置时合法
	{
		if (p->length == MAXSIZE)
		{
			printf("顺序表已满，插入失败\n");
		}
		else
		{
			int i = p->length - 1; //最后一个元素下标 
			for (i; i >= pos - 1; i--) //pos-1为pos位置元素下标，从最后一个元素开始遍历到pos位置元素，分别将它们向后移动一个位置
			{
				p->data[i + 1] = p->data[i];
			}
			p->data[pos - 1] = elem;
			p->length++;
		}
	}
	else
	{
		printf("位置越界,插入失败\n");
	}
}

void SeqListDelete(SeqList* p, int pos)
{
	assert(p);
	if (p->length == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else if(pos >= 1 && pos <= p->length)
	{
		int i = pos; //指定位置的后1个元素
		for (i; i < p->length; i++)
		{
			p->data[i - 1] = p->data[i];
		}
		p->length--;
	}
	else
	{
		printf("位置越界,删除失败\n");
	}
}


int SeqListFind(SeqList* p, ElemType elem)
{
	assert(p);
	int i = 0;
	for (i = 0; i < p->length; i++)
	{
		if (p->data[i] == elem)
		{
			return i;
		}
	}
	return -1;
}

void SeqListPrint(SeqList* p)
{
	assert(p);
	if (p->length == 0)
	{
		printf("顺序表为空\n");
		return;
	}
	int i = 0;
	for (i = 0; i < p->length; i++)
	{
		printf("%d ", p->data[i]);
	}
	printf("\n");
}

源文件main.c内容：

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
#include "SeqList.h"

void menu()
{
	printf("------------------------------\n");
	printf("-- H. 头插元素  h. 头删元素 --\n");
	printf("-- T. 尾插元素  t. 尾删元素 --\n");
	printf("-- I. 插入元素  D. 删除元素 --\n");
	printf("-- F. 查找元素  P. 打印元素 --\n");
	printf("---------    Q. 退出  --------\n");
	printf("------------------------------\n\n");
}

int main()
{
	SeqList s = {0};
	InitSeq(&s);
	char choose = 'Q';
	do
	{
		menu();
		printf("请选择：");
		choose = getchar(); //接受用户选择
		ElemType elem; //待插入（或查找）元素值
		int position = 0; //待插入（删除）元素位序
		getchar(); //从输入缓冲区读取回车符，避免影响下次输入
		switch (choose)
		{
			case 'H':
				printf("请输入待插入元素值：");
				scanf("%d", &elem);
				SeqListHeadInsert(&s, elem);
				getchar();
				break;
			case 'h':
				SeqListHeadDelete(&s);
				break;
			case 'T':
				printf("请输入待插入元素值：");
				scanf("%d", &elem);
				SeqListTailInsert(&s, elem);
				getchar();
				break;
			case 't':
				SeqListTailDelete(&s);
				break;
			case 'I':
				printf("请输入待插入元素位序及值,例：2 5  >"); //位序：顺序表的第几个元素，从1开始
				scanf("%d %d",&position,&elem);
				SeqListInsert(&s,position,elem);
				getchar();
				break;
			case 'D':
				printf("请输入待删除元素位序：");
				scanf("%d", &position);
				SeqListDelete(&s, position);
				getchar();
				break;
			case 'F':
				printf("请输入待查找元素的值：");
				scanf("%d", &elem);
				int index = SeqListFind(&s, elem);
				getchar();
				if (index == -1)
				{
					printf("%d 不在顺序表中\n",elem);
				}
				else
				{
					printf("%d 元素的下标为：%d\n", elem, index);
				}
				break;
			case 'P':
				SeqListPrint(&s);
				break;
			case 'Q':
				printf("退出成功\n");
				break;
			default:
				printf("选择错误，请重新选择!!!\n");
				break;
		}
	} while (choose != 'Q');
	
	return 0;
}

三、动态分配顺序表

3.1 顺序表结构及接口定义

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
typedef	int ElemType; //元素类型重定义，以后元素类型发生改变只用改这里
#define initSize 4  // 顺序表初始化大小
typedef struct SeqList
{
	ElemType* data; //动态内存分配存放元素的数组
	size_t size; //已存放元素个数
	size_t capacity; //数组容量
}SeqList;

void InitSeq(SeqList* p); //顺序表初始化

void SeqListDestory(SeqList* p); //顺序表的销毁

void CheckCapacity(SeqList* p); //检查容量大小决定是否扩容

void SeqListHeadInsert(SeqList* p, ElemType elem); //头部插入元素

void SeqListHeadDelete(SeqList* p); //头部删除元素

void SeqListTailInsert(SeqList* p, ElemType elem); //尾部插入元素

void SeqListTailDelete(SeqList* p); //尾部删除元素

void SeqListInsert(SeqList* p, int pos,ElemType elem); //插入元素到pos位置,位序从1开始算，数组下标从0开始

void SeqListDelete(SeqList* p, int pos); //删除pos位置元素,位序从1开始算，数组下标从0开始

int SeqListFind(SeqList* p, ElemType elem); //查找指定值并返回下标，未找到返回-1 

void SeqListPrint(SeqList* p); //打印顺序表

3.2 顺序表初始化

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
void InitSeq(SeqList* p)
{
	assert(p);
	p->data = (ElemType*)malloc(sizeof(ElemType) * initSize); //先开辟容量为initSize大小的数组
	if (p->data == NULL) //动态内存分配失败则中止程序
	{
		printf("malloc fail\n");
		exit(-1);
	}
	p->size = 0;
	p->capacity = initSize;
}

3.3 顺序表销毁

1
2
3
4
5
6
7
8
void SeqListDestory(SeqList* p)
{
	assert(p);
	free(p->data);
	p->data = NULL;
	p->size = 0;
	p->capacity = 0;
}

3.4 顺序表扩容

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void CheckCapacity(SeqList* p)
{
	assert(p);
	if (p->size == p->capacity) //容量已满
	{
		size_t new_capacity = p->capacity * 2; //扩容到原来2倍
		ElemType* tmp = realloc(p->data, new_capacity * sizeof(ElemType)); 
		if (tmp == NULL) //扩容失败
		{
			printf("realloc fail\n");
			exit(-1);
		}
		p->data = tmp;
		p->capacity = new_capacity;
	}
}

3.5 头插元素

除了需要检查是否扩容外，其他与静态顺序表头插元素一致，可参考2-3的图

1
2
3
4
5
6
7
8
9
10
11
12
void SeqListHeadInsert(SeqList* p, ElemType elem)
{
	assert(p);
	CheckCapacity(p); //检查容量大小
	int i = p->size - 1; //最后一个元素下标 
	for (i; i >= 0; i--) //最后一个元素开始遍历所有元素分别将它们向后移动一个位置
	{
		p->data[i + 1] = p->data[i];
	}
	p->data[0] = elem; //将元素插入到顺序表头部
	p->size++;
}

3.6 头删元素

可参考2-4的图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void SeqListHeadDelete(SeqList* p)
{
	assert(p);
	if (p->size == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else
	{
		int i = 1;  //第2个元素下标
		for (i; i < p->size; i++) //从第2个元素位置开始遍历到最后一个元素，分别将它们都向前移动1个位置
		{
			p->data[i - 1] = p->data[i];
		}
		p->size--;
	}
	
}

3.7 尾插元素

除了需要检查是否扩容外，其他与静态顺序表尾插元素一致，可参考2-5的图

1
2
3
4
5
6
7
void SeqListTailInsert(SeqList* p, ElemType elem)
{
	assert(p);
	CheckCapacity(p); //检查容量大小
	p->data[p->size] = elem; 
	p->size++;
}

3.8 尾删元素

可参考2-6的图

1
2
3
4
5
6
7
8
9
10
11
12
13
void SeqListTailDelete(SeqList* p)
{
	assert(p);
	if (p->size == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else
	{
		p->size--; //只需将元素个数-1
	}
	
}

3.9 指定位置插入元素

除了需要检查是否扩容外，其他与静态顺序表尾插元素一致，可参考2-7的图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void SeqListInsert(SeqList* p, int pos,ElemType elem)
{
	assert(p);
	if (pos >= 1 && pos <= p->size+1) //当位置为1(表头)--表尾的后一个位置时合法
	{
		CheckCapacity(p);
		int i = p->size - 1; //最后一个元素下标 
		for (i; i >= pos - 1; i--) //pos-1为pos位置元素下标，从最后一个元素开始遍历到pos位置元素，分别将它们向后移动一个位置
		{
			p->data[i + 1] = p->data[i];
		}
		p->data[pos - 1] = elem;
		p->size++;
	}
	else
	{
		printf("位置越界,插入失败\n");
	}
}

3.10 指定位置删除元素

可参考2-8的图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void SeqListDelete(SeqList* p, int pos)
{
	assert(p);
	if (p->size == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else if(pos >= 1 && pos <= p->size)
	{
		int i = pos; //指定位置的后1个元素
		for (i; i < p->size; i++)
		{
			p->data[i - 1] = p->data[i];
		}
		p->size--;
	}
	else
	{
		printf("位置越界,删除失败\n");
	}
}

3.11 查找指定元素下标

下标从0开始，当有多个元素的值相同时，返回找到的第一个元素下标

1
2
3
4
5
6
7
8
9
10
11
12
13
int SeqListFind(SeqList* p, ElemType elem)
{
	assert(p);
	int i = 0;
	for (i = 0; i < p->size; i++)
	{
		if (p->data[i] == elem)
		{
			return i;
		}
	}
	return -1;
}

3.12 打印顺序表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void SeqListPrint(SeqList* p)
{
	assert(p);
	if (p->size == 0)
	{
		printf("顺序表为空\n");
		return;
	}
	int i = 0;
	for (i = 0; i < p->size; i++)
	{
		printf("%d ", p->data[i]);
	}
	printf("\n");
}

3.13 程序源代码

头文件SeqList.h内容：

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
#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

typedef	int ElemType; //元素类型重定义，以后元素类型发生改变只用改这里
#define initSize 4  // 顺序表初始化大小

typedef struct SeqList
{
	ElemType* data; //动态内存分配存放元素的数组
	size_t size; //已存放元素个数
	size_t capacity; //数组容量
}SeqList;

void InitSeq(SeqList* p); //顺序表初始化

void SeqListDestory(SeqList* p); //顺序表的销毁

void CheckCapacity(SeqList* p); //检查容量大小决定是否扩容

void SeqListHeadInsert(SeqList* p, ElemType elem); //头部插入元素

void SeqListHeadDelete(SeqList* p); //头部删除元素

void SeqListTailInsert(SeqList* p, ElemType elem); //尾部插入元素

void SeqListTailDelete(SeqList* p); //尾部删除元素

void SeqListInsert(SeqList* p, int pos,ElemType elem); //插入元素到pos位置,位序从1开始算，数组下标从0开始

void SeqListDelete(SeqList* p, int pos); //删除pos位置元素,位序从1开始算，数组下标从0开始

int SeqListFind(SeqList* p, ElemType elem); //查找指定值并返回下标，未找到返回-1 

void SeqListPrint(SeqList* p); //打印顺序表

源文件SeqList.c内容：

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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#include "SeqList.h"

void InitSeq(SeqList* p)
{
	assert(p);
	p->data = (ElemType*)malloc(sizeof(ElemType) * initSize); //先开辟容量为initSize大小的数组
	if (p->data == NULL) //动态内存分配失败则中止程序
	{
		printf("malloc fail\n");
		exit(-1);
	}
	p->size = 0;
	p->capacity = initSize;
}

void SeqListDestory(SeqList* p)
{
	assert(p);
	free(p->data);
	p->data = NULL;
	p->size = 0;
	p->capacity = 0;
}


void CheckCapacity(SeqList* p)
{
	assert(p);
	if (p->size == p->capacity) //容量已满
	{
		size_t new_capacity = p->capacity * 2; //扩容到原来2倍
		ElemType* tmp = realloc(p->data, new_capacity * sizeof(ElemType)); 
		if (tmp == NULL) //扩容失败
		{
			printf("realloc fail\n");
			exit(-1);
		}
		p->data = tmp;
		p->capacity = new_capacity;
	}
}

void SeqListHeadInsert(SeqList* p, ElemType elem)
{
	assert(p);
	CheckCapacity(p); //检查容量大小
	int i = p->size - 1; //最后一个元素下标 
	for (i; i >= 0; i--) //最后一个元素开始遍历所有元素分别将它们向后移动一个位置
	{
		p->data[i + 1] = p->data[i];
	}
	p->data[0] = elem; //将元素插入到顺序表头部
	p->size++;
}

void SeqListHeadDelete(SeqList* p)
{
	assert(p);
	if (p->size == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else
	{
		int i = 1;  //第2个元素下标
		for (i; i < p->size; i++) //从第2个元素位置开始遍历到最后一个元素，分别将它们都向前移动1个位置
		{
			p->data[i - 1] = p->data[i];
		}
		p->size--;
	}
	
}

void SeqListTailInsert(SeqList* p, ElemType elem)
{
	assert(p);
	CheckCapacity(p); //检查容量大小
	p->data[p->size] = elem; 
	p->size++;
}

void SeqListTailDelete(SeqList* p)
{
	assert(p);
	if (p->size == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else
	{
		p->size--; //只需将元素个数-1
	}
	
}

void SeqListInsert(SeqList* p, int pos,ElemType elem)
{
	assert(p);
	if (pos >= 1 && pos <= p->size+1) //当位置为1(表头)--表尾的后一个位置时合法
	{
		CheckCapacity(p);
		int i = p->size - 1; //最后一个元素下标 
		for (i; i >= pos - 1; i--) //pos-1为pos位置元素下标，从最后一个元素开始遍历到pos位置元素，分别将它们向后移动一个位置
		{
			p->data[i + 1] = p->data[i];
		}
		p->data[pos - 1] = elem;
		p->size++;
	}
	else
	{
		printf("位置越界,插入失败\n");
	}
}

void SeqListDelete(SeqList* p, int pos)
{
	assert(p);
	if (p->size == 0)
	{
		printf("顺序表为空，删除失败\n");
	}
	else if(pos >= 1 && pos <= p->size)
	{
		int i = pos; //指定位置的后1个元素
		for (i; i < p->size; i++)
		{
			p->data[i - 1] = p->data[i];
		}
		p->size--;
	}
	else
	{
		printf("位置越界,删除失败\n");
	}
}


int SeqListFind(SeqList* p, ElemType elem)
{
	assert(p);
	int i = 0;
	for (i = 0; i < p->size; i++)
	{
		if (p->data[i] == elem)
		{
			return i;
		}
	}
	return -1;
}




void SeqListPrint(SeqList* p)
{
	assert(p);
	if (p->size == 0)
	{
		printf("顺序表为空\n");
		return;
	}
	int i = 0;
	for (i = 0; i < p->size; i++)
	{
		printf("%d ", p->data[i]);
	}
	printf("\n");
}

源文件main.c内容：

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
#include "SeqList.h"

void menu()
{
	printf("------------------------------\n");
	printf("-- H. 头插元素  h. 头删元素 --\n");
	printf("-- T. 尾插元素  t. 尾删元素 --\n");
	printf("-- I. 插入元素  D. 删除元素 --\n");
	printf("-- F. 查找元素  P. 打印元素 --\n");
	printf("---------    Q. 退出  --------\n");
	printf("------------------------------\n\n");
}

int main()
{
	SeqList s = {0};
	InitSeq(&s);
	char choose = 'Q';
	do
	{
		menu();
		printf("请选择：");
		choose = getchar(); //接受用户选择
		ElemType elem; //待插入（或查找）元素值
		int position = 0; //待插入（删除）元素位序
		getchar(); //从输入缓冲区读取回车符，避免影响下次输入
		switch (choose)
		{
			case 'H':
				printf("请输入待插入元素值：");
				scanf("%d", &elem);
				SeqListHeadInsert(&s, elem);
				getchar();
				break;
			case 'h':
				SeqListHeadDelete(&s);
				break;
			case 'T':
				printf("请输入待插入元素值：");
				scanf("%d", &elem);
				SeqListTailInsert(&s, elem);
				getchar();
				break;
			case 't':
				SeqListTailDelete(&s);
				break;
			case 'I':
				printf("请输入待插入元素位序及值,例：2 5  >"); //位序：顺序表的第几个元素，从1开始
				scanf("%d %d",&position,&elem);
				SeqListInsert(&s,position,elem);
				getchar();
				break;
			case 'D':
				printf("请输入待删除元素位序：");
				scanf("%d", &position);
				SeqListDelete(&s, position);
				getchar();
				break;
			case 'F':
				printf("请输入待查找元素的值：");
				scanf("%d", &elem);
				int index = SeqListFind(&s, elem);
				getchar();
				if (index == -1)
				{
					printf("%d 不在顺序表中\n",elem);
				}
				else
				{
					printf("%d 元素的下标为：%d\n", elem, index);
				}
				break;
			case 'P':
				SeqListPrint(&s);
				break;
			case 'Q':
				SeqListDestory(&s);
				printf("退出成功\n");
				break;
			default:
				printf("选择错误，请重新选择!!!\n");
				break;
		}
	} while (choose != 'Q');
	
	return 0;
}