数据结构顺序表

1. 顺序表的实现

//一般在生活中用到的是动态顺序表
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;//typedef的目的是方便以后修改存储什么类型的数据

typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//有效数据的个数
	int capacity;//容量
}SL;

//定义顺序表的接口函数

void SeqListInit(SL* ps);//顺序表的初始化
void SeqListPrint(SL* ps);//顺序表的打印
void CheckCapacity(SL* ps);//增容函数

void SeqListPushBack(SL* ps,SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删

void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);//头删

int SeqListFind(SL* ps, int pos);//查找接口
void SeqListInsert(SL* ps, int pos, SLDataType x);//在pos位置之前插入
void SeqListErase(SL* ps, int pos);//删除pos位置的数据
void SeqListDestory(SL* ps)；//释放空间

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

然后在sqlist.c文件中实现接口

#include"SeqList.h"

void SeqListPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%%d ", ps->a[i]);
	}
}
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void CheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//如果size==capacity就得增容
	{
		int newcapacity = ps->capacity == 0 ? 4: 2 * (ps->capacity);//如果capacity=0,就给他赋值为4，如果不为0就赋值它的2倍
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		//用一个指针接收它realloc后的地址
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}

void SeqListPushBack(SL* ps, SLDataType x)
{
	CheckCapacity(ps);//先判断是否需要增容
	ps->a[ps->size] = x;
	ps->size++;//个数增加
}

void SeqListPopBack(SL* ps)
{
//断言的作用：如果顺序表中一个数据也没有，就没法尾删（方便找到错误）
	assert(ps->size > 0);
	ps->size--;
	//size--就访问不到尾部，就能尾删
}

void SeqListPushFront(SL* ps, SLDataType x)
{
	CheckCapacity(ps);
	int end = ps->size;
	while (end)
	{
		ps->a[end] = ps->a[end - 1];//从尾部开始，依次往后挪动一位
		end--;
	}
	//这是end的值为0，ps->a[end]就是头
	ps->a[end] = x;
	ps->size++;
}

void SeqListPopFront(SL* ps)//头删
{
	assert(ps->size);
	int first = 1;
	while (first<ps->size)
	{
		ps->a[first - 1] = ps->a[first];//从第二个位置开始，依次往前挪动一位
		first++;
	}
	ps->size--;//数据个数减少
}

int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] ==x)
		{
			return i;//i的位置就是pos的位置
		}
	}
	return -1;//如果找不到返回-1
}

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
//断言的作用：避免访问到顺序表中不存在的位置
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
	int end = ps->size;
	while (end != pos)
	{
		ps->a[end] = ps->a[end - 1];//从pos位置开始,依次往后挪动一位
		end--;
	}
	ps->a[pos] = x;//在pos位置插入数据
	ps->size++;
}

void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos <= ps->size);
	while (pos <ps->size-1)
	{
		ps->a[pos] = ps->a[pos + 1];//从pos+1开始，依次往前挪动一位
		pos++;
	}
	ps->size--;
}

void SeqListDestory(SL* ps)
{
	free(ps->a);
	ps->a = NULL;
	ps->size = ps->capacity = 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
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

剩下的就是在test.c中进行增删查改等功能

void TestSeqList2()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4); 
	SeqListPushBack(&s1, 5);
	SeqListPushBack(&s1, 6);
	int pos = SeqListFind(&s1, 4);
	if (pos != -1)
	{
		SeqListInsert(&s1, pos, 40);
	}

	pos = SeqListFind(&s1, 5);
	if (pos != -1)
	{
		SeqListErase(&s1, pos);
	}
	SeqListPrint(&s1);
	SeqListDestory(&s1);
	
}

int main()
{
	TestSeqList2();


	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

值得注意的是:

头插，尾插，头删，尾删都可以用 SeqListInsert 和 SeqListErase 代替
比如:
头插就可以直接调用SeqListInsert（ps,0,x);
尾插调用SeqListInsert（ps,ps->size,x);
头删调用SeqListErase（ps,0);
尾删调用SeqListErase（ps,ps->size);