代碼已經放在Gitee上，需要可以小伙伴可以去看看
線性表和順序表
線性表
線性表（linear list）是n個具有相同特性的數據元素的有限序列，這是我們廣泛使用的數據結構。
線性表在邏輯上是線性結構，也就說是連續的一條直線。但是在物理結構上并不一定是連續的，線性表在物理上存儲時，通常以數組和鏈式結構的形式存儲。
常見的線性表：順序表、鏈表、棧、隊列、字符串…
順序表
順序表是用一段物理地址連續的存儲單元依次存儲數據元素的線性結構，一般情況下采用數組存儲。在數組上完成數據的增刪查改。
一般可以分為：
- 靜態順序表：使用定長數組來存儲元素
- 動態順序表：使用動態開辟的數組來儲存元素
靜態順序表
|
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
|
//定義靜態數組的大小，方便后續修改#define MAX_SIZE 50//重命名數組的數據類型，方便后續修改typedef int SLDataType;//定義結構體//成員變量為數組和記錄當前數據個數的變量//重命名結構體數據類型，方便書寫typedef struct SeqList { SLDataType arr[MAX_SIZE]; int size;}SL;//-----------------------------------------------------------------------------//以下是一些常見的接口的聲明//順序表初始化//利用結構體類型創建一個靜態順序表變量后，可以對其進行初始化void SLInit(SL* psl);//打印順序表//把順序表的值按照先后順序打印出來void SLPrint(SL* psl);//檢查順序表是否已滿//每次進行加入數據的操作的時候需要先檢查是否已經滿了，如果滿了就不能夠插入了void SLCheck(SL* psl);//順序表的尾插//在順序表的尾部在插入一個元素//由于是數組加入數據很方便，直接使用數組下標就可以訪問到void SLPushBack(SL* psl, SLDataType data);//順序表的尾刪//刪除順序表尾部的數據void SLPopBack(SL* psl);//順序表的頭插//在順序表的開頭加入一個數據void SLPushFront(SL* psl, SLDataType data);//順序表的頭刪//把順序表第一位數據刪除void SLPopFront(SL* psl);//順序表查找某個數據//查找順序表中是否存在某個數據，如果有就返回對應的下標//如果找不到就返回-1int SLFind(SL* psl, SLDataType x);//順序表在pos位置插入x//在指定下標位置插入數據x，原來x位置的數據以及后面的數據往后移動void SLInsert(SL* psl, size_t pos, SLDataType x);//順序表刪除在pos位置的數據void SLErase(SL* psl, size_t pos);//順序表某一位置數據的修改void SLModify(SL* psl, size_t pos, SLDataType x); |
以下是這些接口的具體實現
|
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
|
//順序表初始化void SLInit(SL* psl) { psl->arr[0] = 0;//此處只能初始化一個元素 psl->size = 0;}//打印順序表void SLPrint(SL* psl) { int i = 0; if (psl->size) { for (i = 0; i < psl->size; i++) { //輸出格式，記得根據SLDataTyped的類型來修改 printf("%d ", psl->arr[i]); } printf("\n"); } else { printf("Null\n"); }}/*//檢查順序表是否已滿void SLCheck(SL* psl) { if (psl->size == MAX_SIZE) { printf("順序表已滿，無法進行后續操作"); }}*///順序表的尾插void SLPushBack(SL* psl, SLDataType data) { //插入數據要先檢查空間是否已滿 //實現方法一不夠好 /* if (psl->size == MAX_SIZE) { printf("空間已滿\n"); return; } else { psl->arr[psl->size] = data; psl->size++; }*/ //實現方法二，簡單明了 assert(psl->size != MAX_SIZE); psl->arr[psl->size] = data; psl->size++;}//順序表的尾刪void SLPopBack(SL* psl) { //判斷是否還有元素可以刪除 assert(psl->size); psl->size--;}//順序表的頭插void SLPushFront(SL* psl, SLDataType data) { assert(psl->size != MAX_SIZE); //src用來后移數據 int src = psl->size; while (src >= 1) { psl->arr[src] = psl->arr[src - 1]; src--; } psl->arr[src] = data; psl->size++;}//順序表的頭刪void SLPopFront(SL* psl) { //判斷是否還有數據可以刪除 assert(psl->size); int src = 0; while (src < psl->size - 1) { psl->arr[src] = psl->arr[src + 1]; src++; } psl->size--;}//順序表查找某個數據int SLFind(SL* psl, SLDataType x) { int i = 0; for (i = 0; i < psl->size; i++) { if (psl->arr[i] == x) { //找到了就返回該數據在順序表中的位置 return i; } } //找不到就返回-1 return -1;}//順序表在pos位置插入xvoid SLInsert(SL* psl, size_t pos, SLDataType x) { assert(psl->size < MAX_SIZE); assert(pos >= 0 && pos <= psl->size);//pos=0或者pos=size的時候，相當于頭插，尾插 int end = psl->size; while (end > pos) { psl->arr[end] = psl->arr[end - 1]; end--; } psl->arr[pos] = x; psl->size++;}//順序表刪除在pos位置的數據void SLErase(SL* psl, size_t pos) { assert(psl->size); assert(pos >= 0 && pos < psl->size); int start = pos + 1; while (start < psl->size) { psl->arr[start - 1] = psl->arr[start]; start++; } psl->size--;}//順序表某一位置數據的修改void SLModify(SL* psl, size_t pos, SLDataType x) { assert(psl->size); assert(pos >= 0 && pos < psl->size); psl->arr[pos] = x;} |
上面代碼的測試，我放在了Gitee上，需要的小伙伴可以參考一下
動態順序表
靜態順序表只適用于確定知道需要存多少數據的場景。靜態順序表的定長數組導致N定大了，空間開多了浪費，開少了不夠用。所以現實中基本都是使用動態順序表，根據需要動態的分配空間大小，所以下面我們實現動態順序表。
|
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
|
//重命名SL的數據類型，方便后續修改typedef int SLDataType;//定義結構體//成員變量為指向動態順序表的指針，數據的個數，順序表的容量//capacity用來管理數組的總大小，如果size與capacity相等了，就表示數組已經滿了需要擴容//重定義結構體類型名稱，方便操作typedef struct SeqList { SLDataType* p; int size; int capacity;}SL;//----------------------------------------------------------------------//一下是一些常用的接口，與靜態順序表差不多//SL初始化void SLInit(SL* ps);//SL空間檢查//如若size與capacity相等表示數組已經滿了，需要擴容void SLCheckCapacity(SL* ps);//SL打印void SLPrint(SL* ps);//SL銷毀//因為數組是動態開辟的，所以在最后不使用的數組的時候要釋放空間void SLDestory(SL* ps);//SL尾插void SLPushBack(SL* ps,SLDataType x);//SL尾刪void SLPopBack(SL* ps);//SL頭插void SLPushFront(SL* ps, SLDataType x);//SL頭刪void SLPopFront(SL* ps);//SL查找某個數據//如果能找到，返回該數據在順序表中下標int SLFind(SL* ps, SLDataType x);//SL在pos位置插入xvoid SLInsert(SL* ps, size_t pos, SLDataType x);//SL刪除pos位置的值void SLErase(SL* ps, size_t pos);//SL修改某一位置的數據void SLModity(SL* ps, size_t pos, SLDataType x); |
以下是具體的實現
|
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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
|
//動態順序表的實現#include"DynamicSeqList.h"//SL初始化void SLInit(SL* ps) { ps->p = NULL; ps->capacity = 0; ps->size = 0;}//SL空間檢查void SLCheckCapacity(SL* ps) { if (ps->size == ps->capacity) { ps->capacity = (ps->capacity == 0) ? 5 : 2 * ps->capacity; SLDataType* tmp = (SLDataType*)realloc(ps->p, (ps->capacity) * sizeof(SLDataType)); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } ps->p = tmp; }}//SL打印void SLPrint(SL* ps) { if (ps->size == 0) { printf("順序表為空\n"); } else { int i = 0; for (i = 0; i < ps->size; i++) { //打印格式記得根據SLDataType的類型來修改 printf("%d ", ps->p[i]); } printf("\n"); }}//SL銷毀//這里并沒有完全銷毀結構體s，只是把成員變量都賦值為0void SLDestory(SL* ps) { free(ps->p); ps->p = NULL; ps->size = ps->capacity = 0;}//SL尾插void SLPushBack(SL* ps, SLDataType x) { SLCheckCapacity(ps); ps->p[ps->size] = x; ps->size++;}//SL尾刪void SLPopBack(SL* ps) { //刪除數據需要判斷一下順序表是否為空 assert(ps->size > 0); ps->size--;}//SL頭插void SLPushFront(SL* ps, SLDataType x) { SLCheckCapacity(ps); int end = ps->size; while (end > 0) { ps->p[end] = ps->p[end - 1]; end--; } ps->p[end] = x; ps->size++;}//SL頭刪void SLPopFront(SL* ps) { //刪除數據需要判斷一下順序表是否為空 assert(ps->size > 0); int start = 0; while (start < ps->size - 1) { ps->p[start] = ps->p[start + 1]; start++; } ps->size--;}//SL查找某個數據int SLFind(SL* ps, SLDataType x) { //需要判斷順序表是否為空，可以用assert，也可以用if判斷 assert(ps->size); int i = 0; for (i = 0; i < ps->size; i++) { if (x == ps->p[i]) { return i; } } return -1;}//SL在pos位置插入x//當pos為0或者pos為size時，相當于頭插、尾插void SLInsert(SL* ps, size_t pos, SLDataType x) { SLCheckCapacity(ps); assert(pos >= 0 && pos <= ps->size); int end = ps->size; while (end > pos) { ps->p[end] = ps->p[end - 1]; end--; } ps->p[end] = x; ps->size++;}//SL刪除pos位置的值void SLErase(SL* ps, size_t pos) { //判斷要刪除的位置是否在size之內 assert(pos >= 0 && pos < ps->size); int start = pos + 1; while (start < ps->size) { ps->p[start - 1] = ps->p[start]; start++; } ps->size--;}//SL修改某一位置的數據void SLModity(SL* ps, size_t pos, SLDataType x) { //判斷要修改的位置是否在size之內 assert(pos >= 0 && pos < ps->size); ps->p[pos] = x;} |
同樣的，我自己寫的一些小測試也在Gitee上，需要的小伙伴可以去看看
到此這篇關于C語言 數據結構之數組模擬實現順序表流程詳解的文章就介紹到這了,更多相關數組模擬實現順序表內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/weixin_61021362/article/details/121411921
