顺序表的建立（C语言）_构建顺序表

顺序表

线性表的顺序储存是指在内存中用一组地址连续的内存单元一次存储线性表的各元素，用这种存储形式存储的线性表成为顺序表。

顺序表的存储结构

//定义储存结构
typedef struct Node
{
	int *elem;  //数据域
	int length;  //顺序表长度
	int listsize;//顺序表容量
}List;
1
2
3
4
5
6
7

顺序表的初始化

将L->length赋值为零，表示此时顺序表中没有数据存在;
L->listsize赋值为最大容量;

//初始化链表
int InitList(List* L)
{
	L->elem = (int*)malloc(sizeof(int)*MAXSIZE);
	if (!L->elem)
	{
		printf("储存已满\n");   //储存空间已满，无法分配内存.
		return FALSE;
	}
	L->length = 0;
	L->listsize = MAXSIZE;
	return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

插入数据

首先判断输入的数字是否符合约定的要求;
然后判断顺序表是否已经满了，如果已满，再增加容量，如果没有满，从最后一个数据开始，每个数据依次后移，直到要插入的位置，将要添加的数据在相应位置赋值

//插入数据
int InsertList(List* L, int i, int data)
{
	int* newbase = (int *)malloc(sizeof(int));
	if (i < 1 || i > L->length+1)
	{
		printf("输入序列错误\n");
		return FALSE;
	}
	if (L->length  >= L->listsize)
	{
		newbase = (int*)realloc(L->elem, (L->listsize + INCREASE_SIZE) * sizeof(int));
		if (!newbase)
		{
			return FALSE;
		}
		L->elem = newbase;
		L->listsize = L->listsize + INCREASE_SIZE;
	}
	for (int j = L->length-1; j >= i-1; j--)
	{
		L->elem[j+1] = L->elem[j];
	}
	L->elem[i-1] = data;
	L->length++;
	return TRUE;
}
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

数据的删除

如果要查找的位置超出范围，返回FALSE;
从要删除的位置开始，将数据依次前移;

//线性表的删除
int DeleteList(List* L, int i)
{
	if (i < 1 || i>L->length)
	{
		return FALSE;
	}
	if (i - 1 > L->length - 1)
	{
		return FALSE;
	}
	for (int j = i - 1; j < L->length-1; j++)
	{
		L->elem[j] = L->elem[j + 1];
	}
	L->length--;
	return TRUE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

顺序表的查找

首先判断是否如何约定的要求
遍历线性表，找到要查找的位置，返回数据;
如果遍历完之后也没找到，返回FALSE;

//线性表的查找
int SearchList(List* L, int i)
{
	if (i < 1 || i>L->length)
	{
		return FALSE;
	}
	for (int j = 0; j < L->length; j++)
	{
		if (j + 1 == i)
		{
			return L->elem[j];
		}
	}
	return FALSE;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16