纯C语言实现线性表

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #define MAXSIZE 100
  4 
  5 typedef int ElemType;
  6 
  7 typedef struct{
  8     ElemType data[MAXSIZE];
  9     int length;
 10 }SqList;
 11 
 12 SqList *InitList(SqList *L);//初始化
 13 void DestroyList(SqList *L);//销毁
 14 void ClearList(SqList *L);//清空列表
 15 int ListEmpty(SqList *L);//判空
 16 int ListLength(SqList *L);//返回线性表长度
 17 int GetElem(SqList *L, int i, ElemType *e);//获取第i个元素
 18 int LocateElem(SqList *L, ElemType e);//定位值为e的位置
 19 ElemType PriorElem(SqList *L, ElemType cur_e);//查找前驱
 20 ElemType NextElem(SqList *L, ElemType cur_e);//查找后继
 21 int ListInsert(SqList *L, int i, ElemType e);//插入元素
 22 int ListDelete(SqList *L, int i);//删除第i个元素
 23 int TraverseList(SqList *L);//遍历线性表
 24 
 25 //初始化线性表,返回头指针
 26 SqList* InitList(SqList *L){
 27     int x;
 28     int index = 0;
 29 
 30     L = (SqList *)malloc(sizeof(SqList));
 31     if(L){
 32         printf("输入到-1结束\n");
 33         while(1){
 34             scanf("%d", &x);
 35             if(x == -1){
 36                 printf("初始化成功\n");
 37                 break;
 38             };
 39             L->data[index++] = x;
 40         }
 41         L->length = index;
 42     }else{
 43         printf("空间不足,初始化失败\n");
 44     }
 45     return L;
 46 }
 47 
 48 //销毁线性表
 49 void DestroyList(SqList *L){
 50     free(L);
 51     printf("销毁成功\n");
 52 }
 53 
 54 //清空线性表
 55 void ClearList(SqList *L){
 56     int len = L->length;
 57     int i;
 58     for(i=0; i<len; i++){
 59         L->data[i] = 0;
 60     }
 61     printf("清空成功\n");
 62 }
 63 
 64 //判空，1为空,0不为空
 65 int ListEmpty(SqList *L){
 66     return (L->length == 0);
 67 }
 68 
 69 //返回线性表长度
 70 int ListLength(SqList *L){
 71     return L->length;
 72 }
 73 
 74 //获取第i个元素，返回是否获取的状态
 75 int GetElem(SqList *L, int i, ElemType *e){
 76     if(i<1 || i>L->length){
 77         printf("查找下标%d越界\n",i);
 78         return 0;
 79     }
 80     *e = L->data[i-1];
 81     printf("第%d个元素是%d\n", i, *e);
 82     return 1;
 83 }
 84 
 85 //返回第一个与e相同元素的位置，返回找寻到的下标
 86 int LocateElem(SqList *L, ElemType e){
 87     int i;
 88     for(i=0; i<L->length; i++){
 89         if(L->data[i] == e){
 90             printf("元素%d的位置是第%d个\n",e,i+1);
 91             return i+1;
 92         }
 93 
 94     }
 95     printf("%d, 查无此元素的下标\n", e);
 96     return 0;
 97 }
 98 //返回元素为e的前驱元素
 99 ElemType PriorElem(SqList *L, ElemType cur_e){
100     int idx = LocateElem(L, cur_e);
101     ElemType e;
102     if(!idx){
103         return 0;
104     }
105     if(idx == 1){
106         printf("第一个元素%d没有前驱\n", cur_e);
107         return 0;
108     }
109     GetElem(L, idx-1, &e);
110     printf("%d元素的前驱是%d\n",cur_e, e);
111     return e;
112 }
113 //返回元素e的后继元素
114 ElemType NextElem(SqList *L, ElemType cur_e){
115     int idx = LocateElem(L, cur_e);
116     ElemType e;
117     if(!idx){
118         return 0;
119     }
120     if(idx == L->length){
121         printf("最后一个元素%d没有后继\n", cur_e);
122         return 0;
123     }
124     GetElem(L, idx+1, &e);
125     printf("%d元素的后继是%d\n",cur_e, e);
126     return e;
127 }
128 //插入，返回是否插入成功的状态
129 int ListInsert(SqList *L, int i, ElemType e){
130     if(i<1 || i>L->length+1){
131         printf("插入位置有误\n");
132         return 0;
133     }
134     if(L->length == MAXSIZE){
135         printf("线性表已满无法插入新元素\n");
136         return 0;
137     }
138     int j;
139     for(j=L->length-1; j>=i-1; j--){
140         L->data[j+1] = L->data[j];
141     }
142     L->data[i-1] = e;
143     L->length++;
144     printf("插入成功\n");
145     return 1;
146 }
147 //删除第i个元素，返回是否删除成功的状态
148 int ListDelete(SqList *L, int i){
149     if(i<1 || i>L->length){
150         printf("删除位置有误\n");
151         return 0;
152     }
153     int j;
154     for(j=i; j<L->length; j++){
155         L->data[j-1] = L->data[j];
156     }
157     L->length--;
158     printf("删除成功\n");
159     return 1;
160 }
161 
162 //遍历线性表
163 int TraverseList(SqList *L){
164     if(L->length == 0){
165         printf("空表\n");
166         return 0;
167     }
168     if(L->length>MAXSIZE || L->length<-MAXSIZE){
169         printf("线性表已被摧毁或未初始化\n");
170         return 0;
171     }
172     int j;
173     for(j=0; j<L->length; j++){
174         printf("%d ", L->data[j]);
175     }
176     printf("\n");
177 }
178 
179 int main(void){
180     int idx;
181     int len;
182     ElemType e;
183     ElemType cur_e;
184     SqList *L = NULL;
185 
186     L = InitList(L);
187 
188 //    printf("线性表长度为%d\n",ListLength(L));
189 
190 //    //判空测试
191 //    if(ListEmpty(L))
192 //        printf("线性表空\n");
193 //    else
194 //        printf("线性表不为空\n");
195 
196 //    //获取元素测试
197 //    idx = 2;
198 //    GetElem(L, idx, &e);
199 //    GetElem(L, L->length+1, &e);
200 
201 //    //获取位置测试
202 //    LocateElem(L, 3);
203 
204 //    //获取前驱测试
205 //    cur_e = 4;
206 //    PriorElem(L, cur_e);
207 //    GetElem(L, 1, &cur_e);
208 //    PriorElem(L, cur_e);
209 
210 //    //插入测试
211 //    ListInsert(L, 1, 999);
212 //    TraverseList(L);
213 //    ListInsert(L, L->length+1, 999);
214 //    TraverseList(L);
215 
216 //    //删除测试
217 //    ListDelete(L, 1);
218 //    TraverseList(L);
219 
220 //    //清空测试
221 //    ClearList(L);
222 //    TraverseList(L);
223 
224 //    //摧毁测试
225 //    DestroyList(L);
226 //    TraverseList(L);
227     return 0;
228 }