【数据结构】顺序表的实现_构造顺序表

一、顺序表概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删。一般分为静态顺序表和动态顺序表。

二、动态顺序表和静态顺序表的选择

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以我们实现动态顺序表。

三、动态顺序表的实现逻辑

（1）创建结构体

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity; 
}SL;
1
2
3
4
5
6
7

使用动态顺序表先创建结构体是必须的，先使用typedef int SLDateType;是为了方便改类型，在结构体里创建三个成员变量，SLDateType* a，为了方便增容，用指针的形式，int size代表a指向空间里的个数，int capacity代表a指向空间里的容量。

（2）具体函数实现

（*）顺序表初始化

void SeqListInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;

}
1
2
3
4
5
6
7
8

先用assert断言，为了更方便查看在哪个地方出错，初始化就是把ps指向的结构体成员变量a置为空指针，size和capacity置为0。

（*）释放顺序表

void SeqListDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
1
2
3
4
5
6
7
8

释放顺序表也就是把a指向的空间的释放掉，并把a置为空指针，而另外两个成员变量置为0。

（*）打印顺序表

void SeqListPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

打印顺序表只需要用for循环依次打印，用ps找到size，即成员个数，再用printf进行打印，ps找到数组a。

（*）是否需要扩容

void if_add(SL*ps)
{
	if (ps->capacity == ps->size)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->a, NewCapacity*sizeof(SLDateType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = NewCapacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

为了提高代码的可读性，把是否需要扩容封装一个函数，而且下面有好多函数需要用到。
先判断capacity和size是否相等，如果相等，说明需要增容，再用三目运算符判断capacity是否等于0，如是则设置一个有一定大小的初始值，反之，则指定的倍数进行扩容。再把它赋给Newcapacity，再realloc进行开辟空间，用另外一个指针tmp表示，再判断tmp是否为空，如是则用perror显示开辟失败，并非正常退出程序exit（-1），反之则把新指针再赋给原来的a，最后capacity进行更新，Newcapacity赋给capacity。

（*）顺序表尾插

void SeqListPushBack(SL* ps, SLDateType x)
{
	assert(ps);
	if_add(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
1
2
3
4
5
6
7

尾插先判断空间是否足够，再把x依次插入ps->size元素下标的位置，并进行ps->size加加，记录已尾插的个数。

（*） 顺序表头插

void SeqListPushFront(SL* ps, SLDateType x)
{
	assert(ps);
	if_add(ps);
	for (int i = ps->size - 1; i >=0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[0] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11

头插也是先判断空间是否足够，再从后面进行尾插，用for循环从i=ps->size开始，每头插一个就把此位置的值往后移，直到第一个位置也就是0位置可用的时候，在把x赋给0位置处，直到i<0为止，最后size加加。

（*）顺序表尾插删除

void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}
1
2
3
4
5

头删，需要用asser断言一下，里面的内容为ps->size>0，防止size<0,以便告诉我们在哪出错，最后直接ps->szie–

（*）顺序表头插删除

void SeqListPopFront(SL* ps)
{
	assert(ps);
	for (int i = 1; i < ps->size; i++)
	{
		ps->a[i-1] = ps->a[i];
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9

头插删除，直接用for循环把后面内容往前移，注意i是从1开始的，如果写成0会越界，而且也只能从1开始，因为删除的是开头的元素，最后ps->szie–。

（*）顺序表查找

int SeqListFind(SL* ps, SLDateType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

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

顺序表查找返回值是int类型，返回的是下表元素，那就用for循环直接遍历，如果找到x，就返回下标元素i，最后遍历完也没有找到返回-1。
这个函数需要结合测试函数test.c的部分代码用，如下，如果返回不是-1，就打印下标元素i，否则打印失败。

int ret = SeqListFind(&sl, 6);
	  if (ret!=-1)
	  {
		  printf("%d\n", ret);

	  }
	  else
	  {
		  printf("find fail\n");
	  }
1
2
3
4
5
6
7
8
9
10

（*）顺序表在pos位置插入x

void SeqListInsert(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos <= ps->size);
	if_add(ps);
	for (int i = ps->size-1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12

顺序表在下标元素pos插入x，先写两个断言函数，pos不能比szie大，因为我们是在size个数里面插入，再判断是否需要扩容，再用for循环进行移动元素，初始位置为当前数组的最后一个元素开始，直到pos结束，也就是pos位置可用可插入的时候再进行插入x，最后size++。

（*）顺序表删除pos位置的值

void SeqListErase(SL* ps, int pos)
{
	assert(ps && pos < ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9

顺序表删除下标pos位置的值，同上用assert进行断言，从
pos位置开始，进行覆盖，直到ps->size-1结束，防止越界，因为有可能capacity等于size，最后size–。

四、动态顺序表实现代码

（1）test.c

#include"SeqList.h"

int main()
{
      SL sl;
	  SeqListInit(&sl);

	  SeqListPushBack(&sl, 1);
	  SeqListPushBack(&sl, 2);
	  SeqListPushBack(&sl, 3);
	  SeqListPushBack(&sl, 4);
	  SeqListPrint(&sl);

	  SeqListPopBack(&sl);
	  SeqListPopBack(&sl);
	  SeqListPopBack(&sl);
	  SeqListPrint(&sl);

	  SeqListPushFront(&sl,3);
	  SeqListPushFront(&sl, 4);
	  SeqListPushFront(&sl, 5);
	  SeqListPrint(&sl);

	  SeqListPopFront(&sl);
	  SeqListPopFront(&sl);
	  SeqListPrint(&sl);

	  int ret = SeqListFind(&sl, 6);
	  if (ret!=-1)
	  {
		  printf("%d\n", ret);

	  }
	  else
	  {
		  printf("find fail\n");
	  }

	  SeqListInsert(&sl, 1, 4);
	  SeqListPrint(&sl);

	  SeqListInsert(&sl, 3, 6);
	  SeqListPrint(&sl);

	  SeqListErase(&sl, 2);
	  SeqListPrint(&sl);

	  SeqListDestroy(&sl);
	  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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

（2）SeqList.h

#pragma once//防止头文件包含
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity; 
}SL;
void SeqListInit(SL* ps);//顺序表初始化
void SeqListDestroy(SL* ps);//释放顺序表

void SeqListPrint(SL* ps);//打印顺序表
void SeqListPushBack(SL* ps, SLDateType x);//顺序表尾插
void SeqListPushFront(SL* ps, SLDateType x); //顺序表头插
void SeqListPopFront(SL* ps);//顺序表头插删除
void SeqListPopBack(SL* ps);//顺序表尾插删除
void if_add(SL* ps);//是否需要扩容

int SeqListFind(SL* ps, SLDateType x);//顺序表查找
void SeqListInsert(SL* ps, int pos, SLDateType x); 顺序表在pos位置插入x
void SeqListErase(SL* ps, int pos);// 顺序表删除pos位置的值
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

（3）SeqList.c

#include"SeqList.h"
void SeqListInit(SL* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;

}
void SeqListDestroy(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
void SeqListPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}
void if_add(SL*ps)
{
	if (ps->capacity == ps->size)
	{
		int NewCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDateType* tmp = (SLDateType*)realloc(ps->a, NewCapacity*sizeof(SLDateType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = NewCapacity;
	}
}
void SeqListPushBack(SL* ps, SLDateType x)
{
	assert(ps);
	if_add(ps);
	ps->a[ps->size] = x;
	ps->size++;
}
void SeqListPopBack(SL* ps)
{
	assert(ps->size > 0);
	ps->size--;
}
void SeqListPushFront(SL* ps, SLDateType x)
{
	assert(ps);
	if_add(ps);
	for (int i = ps->size - 1; i >=0; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[0] = x;
	ps->size++;
}
void SeqListPopFront(SL* ps)
{
	assert(ps);
	for (int i = 1; i < ps->size; i++)
	{
		ps->a[i-1] = ps->a[i];
	}
	ps->size--;
}
int SeqListFind(SL* ps, SLDateType x)
{
	for (int i = 0; i < ps->size; i++)
	{
		if (ps->a[i] == x)
		{
			return i;
		}
	}
	return -1;
}

void SeqListInsert(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos <= ps->size);
	if_add(ps);
	for (int i = ps->size-1; i >= pos; i--)
	{
		ps->a[i + 1] = ps->a[i];
	}
	ps->a[pos] = x;
	ps->size++;
}
void SeqListErase(SL* ps, int pos)
{
	assert(ps && pos < ps->size);
	for (int i = pos; i < ps->size-1; i++)
	{
		ps->a[i] = ps->a[i + 1];
	}
	ps->size--;
}

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

五、动态顺序表测试结果