【学习笔记之数据结构】顺序表

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

一般分为两类：

1. 静态顺序表：使用定长数组存储元素；
2. 动态顺序表：使用动态开辟的数组存储。

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

代码实例：

头文件SeqList.h

#pragma once

#include 
#include 
#include 

typedef int SLDataType;	//方便修改数据类型
typedef struct SeqList {
	SLDataType* a;	//指向动态开辟的数组
	int size;		//记录存储数据个数
	int capacity;	//空间容量大小
}SL;

void SLPrint(SL* ps);
void SLInit(SL* ps);
void SLDestroy(SL* ps);

//尾插尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
//头插头删
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

//顺序表查找
int SLFind(SL* ps, SLDataType x);
//顺序表在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);
//顺序表删除pos位置的值
void SLErase(SL* ps, int pos);

//扩容函数
void SLCheckCapacity(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
33

功能实现

#include "SeqList.h"

void SLPrint(SL* ps) {
	assert(ps);
	int i;
	for (i = 0; i < ps->size; i++) {
		printf("%d", ps->a[i]);
	}
	printf("\n");
}

void SLInit(SL* ps) {
	assert(ps);

	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SLDestroy(SL* ps) {
	assert(ps);
	if (ps->a) {
		free(ps->a);
		ps->a = NULL;
		ps->size = ps->capacity = 0;
	}
}

void SLCheckCapacity(SL* ps) {
	assert(ps);

	if (ps->size == ps->capacity) {
		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
		if (tmp == NULL) {
			perror("realloc fail");
			exit(-1);//终止程序
		}

		ps->a = tmp;
		ps->capacity = newCapacity;
	}
}

void SLPushBack(SL* ps, SLDataType x) {
	assert(ps);

	SLCheckCapacity(ps);

	ps->a[ps->size] = x;
	ps->size++;
}

void SLPopBack(SL* ps) {
	assert(ps);
	assert(ps->size > 0);

	ps->size--;
}

void SLPushFront(SL* ps, SLDataType x) {
	assert(ps);

	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= 0) {
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;
	ps->size++;
}

void SLPopFront(SL* ps){
	assert(ps);
	assert(ps->size > 0);

	int begin = 0;
	while (begin < ps->size - 1) {
		ps->a[begin] = ps->a[begin + 1];
		begin++;
	}
	ps->size--;
}

void SLInsert(SL* ps, int pos, SLDataType x) {
	assert(ps);
	assert(pos >= 0);
	assert(pos <= ps->size);

	SLCheckCapacity(ps);
	int end = ps->size - 1;
	while (end >= pos) {
		ps->a[end + 1] = ps->a[end];
		end--;
	}

	ps->a[pos] = x;
	ps->size++;
}

void SLErase(SL* ps, int pos) {
	assert(ps);
	assert(ps->size >= pos);

	int ret = pos;
	while (ret < ps->size - 1) {
		ps->a[ret] = ps->a[ret + 1];
		ret++;
	}
	ps->size--;
}

int SLFind(SL* ps, SLDataType x) {
	int i = 0;
	while (i < ps->size) {
		if (ps->a[i] == x) {
			return i;
		}
		i++;
	}

	return -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
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

主函数

#include "SeqList.h"

void TestSeqList(){
	SL sl;
	SLInit(&sl);
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLPrint(&sl);

	SLInsert(&sl, 2, 7);
	SLPrint(&sl);

	int n = SLFind(&sl, 7);
	printf("%d\n", n);

	SLErase(&sl, 2);
	SLPrint(&sl);

	SLDestroy(&sl);
}
int main() {
	TestSeqList();

	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