線性表——順序存儲結構，線性存儲結構
一）聲明
新手上路。如果有不對的，不合理的地方，編碼風格，算法思路有待改進的地方，還請各位大神多多指點。
二）簡介
本文中采用動態開辟內存的方法建立線性表，實現順序表的基本操作。
此代碼思路比較簡單，畢竟只是簡單的原理，沒有具體的應用，僅僅作為入門學習的積累。
三）具體實現分析如下：
3.1）頭文件定義如下：
![]()
1 #ifndef LinearList_SqList_h
2 #define LinearList_SqList_h
3
4 #include <stdio.h>
5 #include <stdlib.h>
6
7 #define OK 1
8 #define ERROR 0
9
10 #define LIST_INIT_SIZE 100
11 #define SIZE_INCREMENT 10
12
13 typedef int Status;
14 typedef int ElemType;
15
16 typedef struct {
17 ElemType *pElem;
18 int nLength;
19 int nListSize;
20 }SqList;
21
22
23 void InitSqList(SqList *L);
24 Status InsertSqList(SqList *L, int nIndex, ElemType eValue);
25 Status AssignSqList(SqList *L);
26 Status DeleteSqList(SqList *L, int nIndex, ElemType *pValue);
27 Status ClearSqList(SqList *L);
28 Status DestroySqList(SqList *L);
29 Status LocateElem(SqList L, ElemType nValue);
30 Status PrintSqList(SqList L);
31
32 #endif
SqList.h
3.2）具體實現：
3.2.1）基本原則：
a）函數參數中，只要傳遞的是指針，函數內必須首先校驗指針是否為空。
b）如果要對順序表進行修改，那麼必須進行地址傳遞，而不是值傳遞。
c）malloc申請的內存，一定要用free釋放，並且釋放之後，置指針為空，防止出現也指針。
3.2.2）具體代碼思路：
a、InitSqList
動態申請空間，依此對順序表的成員賦值。
b、InsertSqList （此處允許對空表進行插入）
思路：校驗指針參數——》校驗插入點——》校驗順序表是否已初始化——》校驗順序表是否已滿——》遍歷順序表，找到插入點——》移動元素——》插入——》同時表長增加；
分析：其實真正的插入就是一行代碼，但是為了保證插入後不影響其他元素的使用，必須移動元素；為了保證程序的健壯性，必須增加很多校驗過程；
重點在於下標的計算。
2.1參數校驗：指針是否為空；插入點是否非法
2.2順序表校驗：順序表是否已初始化；對於插入而言，順序表是否已滿；
2.3當所有的校驗完畢之後，尋找正確插入點，移動元素（從表尾向待插入點方向遍歷），最後插入，增加表長；
（2.4）關於空表是否允許插入的問題：根據不同的需求和功能設定。如果不允許對空表插入，可以多加一層校驗功能即可；（此處允許空表插入）
c、DeleteSqList （基本原理類似於Insert）
思路：校驗指針參數——》校驗刪除點——》校驗順序表是否初始化——》校驗順序表是否為空——》遍歷順序表，尋找刪除點——》移動元素——》刪除——》同時表長自減；
分析：刪除元素就是不斷的移動元素，采用覆蓋原理即可（從刪除點向表尾方向遍歷）。關鍵是下標的計算。
d、DestroySqList
思路：校驗指針參數——》校驗順序表是否初始化——》釋放申請的內存——》同時設置順序表相關參數。
分析：重點在於參數的校驗和free過後的指針應該置空。
3.3）具體代碼如下：
![]()
1 #include "SqList.h"
2
3 void InitSqList(SqList *L) {
4 if (NULL == L) {
5 printf("Error parament.");
6 return ;
7 }
8
9 L->pElem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(SqList));
10 if (NULL == L->pElem) {
11 printf("Error:Out of memory.");
12 return ;
13 }
14
15 L->nLength = 0;
16 L->nListSize = LIST_INIT_SIZE;
17 }
18
19
20 //Insert element to sqlist
21 Status InsertSqList(SqList *L, int nIndex, ElemType eValue) {
22 if (NULL == L) {
23 printf("Error parament.");
24 return ERROR;
25 }
26
27 if (NULL == L->pElem) {
28 printf("Error: The list is not initiated.");
29 return ERROR;
30 }
31
32 if (nIndex < 1 || nIndex > L->nLength + 1) {
33 printf("Error: Invalid insert point.");
34 return ERROR;
35 }
36
37 ElemType *pNewBase;
38 if (L->nLength >= L->nListSize) {
39 pNewBase = (ElemType*)realloc(L->pElem, (LIST_INIT_SIZE + SIZE_INCREMENT) * sizeof(ElemType));
40 if (NULL == pNewBase) {
41 printf("Error:Out of memory.");
42 return OK;
43 }
44 //here can also write with 'else'.
45 //Logically no problem. But it takes effort to write the else and '{}'. Efficiently not good choice
46 L->pElem = pNewBase;
47 L->nListSize += SIZE_INCREMENT;
48 }
49
50 ElemType *pInsert, *pLast;
51 pInsert = L->pElem + nIndex - 1;
52 pLast = L->pElem + L->nLength - 1;
53
54
55 while (pLast >= pInsert) {
56 *(pLast + 1) = *pLast;
57 pLast--;
58 }
59
60 *pInsert = eValue;
61 ++L->nLength;
62
63 return OK;
64 }
65
66 //Assign sqlist
67 Status AssignSqList(SqList *L) {
68 if (NULL == L) {
69 printf("Error parament.");
70 return ERROR;
71 }
72
73 if (NULL == L->pElem) {
74 printf("Error:The list is not initiated.");
75 return ERROR;
76 }
77
78 int nLength, nValue;
79 printf("Input the length:");
80 scanf("%d", &nLength);
81
82 for (int i = 1; i <= nLength; i++) {
83 printf("Input the value:");
84 scanf("%d", &nValue);
85
86 InsertSqList(L, i, nValue);
87 }
88
89 return OK;
90 }
91
92 //delete element from sqlist
93 Status DeleteSqList(SqList *L, int nIndex, ElemType *pValue) {
94 if (NULL == L || NULL == pValue) {
95 printf("Error parament.");
96 return ERROR;
97 }
98
99 if (NULL == L->pElem) {
100 printf("Error:The list is not initiated.");
101 return ERROR;
102 }
103
104 if (L->nLength <= 0) {
105 printf("Error:The list is empty.Can't delete.");
106 return ERROR;
107 }
108
109 if (nIndex < 1 || nIndex > L->nLength) {
110 printf("Error:Invalid delete index.");
111 return ERROR;
112 }
113
114 ElemType *pDelete, *pLast;
115 pDelete = L->pElem + nIndex - 1;
116 pLast = L->pElem + L->nLength - 1;
117
118 *pValue = *pDelete;
119 for (pDelete++; pDelete <= pLast; pDelete++) {
120 *(pDelete - 1) = *pDelete;
121 }
122
123 --L->nLength;
124
125 return OK;
126 }
127
128 //clear sqlist
129 Status ClearSqList(SqList *L) {
130 if (NULL == L) {
131 printf("Error parament.");
132 return ERROR;
133 }
134
135 if (NULL == L->pElem) {
136 printf("Error: The list is not initiated.");
137 return ERROR;
138 }
139
140 L->nLength = 0;
141
142 return OK;
143 }
144
145 //destroy sqlist
146 Status DestroySqList(SqList *L) {
147 if (NULL == L) {
148 printf("Error parament.");
149 return ERROR;
150 }
151
152 if (NULL == L->pElem) {
153 printf("Error:The list is not initiated.");
154 return ERROR;
155 }
156
157 free(L->pElem);
158 L->pElem = NULL;
159 L->nLength = 0;
160 L->nListSize = 0;
161
162 return OK;
163 }
164
165 //locate element from sqlist
166 Status LocateElem(SqList L, ElemType nValue) {
167 if (NULL == L.pElem) {
168 printf("Error:The list is not initiated.");
169 return ERROR;
170 }
171
172 if (L.nLength <= 0) {
173 printf("Error:The list is empty.");
174 return ERROR;
175 }
176
177 int nIndex;
178 ElemType *pLocate = L.pElem;
179
180 for (nIndex = 1; nIndex <= L.nLength; nIndex++) {
181 if (nValue == *pLocate) {
182 printf("Located succeeded.");
183 return nIndex;
184 }
185 pLocate++;
186 }
187
188 return ERROR;
189 }
190
191
192 //Print sqlist
193 Status PrintSqList(SqList L) {
194 if (NULL == L.pElem) {
195 printf("Error:The list is not initiated.");
196 return ERROR;
197 }
198
199 if (L.nLength <= 0) {
200 printf("The list is empty.");
201 return ERROR;
202 }
203
204 printf("The list is as follows:");
205 for (int i = 1; i <= L.nLength; i++) {
206 printf("%d ", *L.pElem);
207 L.pElem++;
208 }
209
210 printf("\n");
211 return OK;
212 }
SqList.c
