2019.7.11数据结构-线性表顺序结构

  1 //========================= 头文件
  2 #include<iostream>
  3 #include<string>
  4 #include<cctype>
  5 #include<sstream>
  6 #include<vector>
  7 #include<iterator>
  8 using namespace std;
  9 //------------------------- 基础定义
 10 #define TRUE 1
 11 #define FALSE 0
 12 #define OK 1
 13 #define ERROR 0        //出错
 14 #define INFEASIBLE -1  //不可行
 15 typedef int Status;
 16 //------------------------- 线性表动态分配顺序存储结构
 17 #define LIST_INIT_SIZE 100
 18 #define LISTINCREMENT 10
 19 typedef struct {
 20     int* elem;         //存储地址
 21     int length;
 22     int listsize;
 23 }Sqlist;
 24 //------------------------- 线性表顺序表示和实现
 25 Status InitList(Sqlist &L) {
 26     L.elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));
 27     if (!L.elem)
 28         exit(OVERFLOW);
 29     L.length = 0;
 30     L.listsize = LIST_INIT_SIZE;
 31     return OK;
 32 }//构造一个空的线性表L。
 33 
 34 Status DestroyList(Sqlist &L) {
 35     L.elem = NULL;
 36     L.length =0;
 37     L.listsize =0;
 38     free(L.elem);
 39     return OK;
 40 }//销毁一个线性表。
 41 
 42 Status ClearList(Sqlist &L) {
 43     if (!L.elem)
 44         exit(OVERFLOW);
 45     free(L.elem);
 46     L.elem = (int *)malloc(LIST_INIT_SIZE * sizeof(int));
 47     if (!L.elem)
 48         exit(OVERFLOW);
 49     L.length = 0;
 50     L.listsize = LIST_INIT_SIZE;
 51     return OK;
 52 }//重置L为空表。
 53 
 54 Status ListEmpty(Sqlist L) {
 55     if (L.length == 0)
 56         return TRUE;
 57     return FALSE;
 58 }//判断是否为空表
 59 
 60 int ListLength(Sqlist L) {
 61     if (ListEmpty(L))
 62         return 0;
 63     return L.length;
 64 }//返回L中的元素个数
 65 
 66 void GetElem(Sqlist L, int i, int &e) {
 67     if (!L.elem)
 68         exit(OVERFLOW);
 69     if (i > ListLength(L) || i < 1)
 70         exit(ERROR);
 71     e = L.elem[i - 1];
 72 }//用e返回L中第i个元素的值。
 73 
 74 int LocateElem(Sqlist L, int e) {
 75     if (!L.elem)
 76         exit(OVERFLOW);
 77     for (int i = 0; i != L.length; ++i) {
 78         if (e == L.elem[i]) 
 79             return i+1;
 80     }
 81     return 0;
 82 }//返回L中第一个与e相等的元素的位置，没有返回0
 83 
 84 
 85 Status PriorElem(Sqlist L,int cur_e,int &pre_e) {
 86     if (!L.elem)
 87         exit(OVERFLOW);
 88     if (LocateElem(L, cur_e) && LocateElem(L, cur_e) > 1) {
 89         pre_e = L.elem[LocateElem(L, cur_e) - 2];
 90         return OK;
 91     }
 92     pre_e = NULL;
 93     return FALSE;
 94 }//用pre_e返回cur_e的前驱.
 95 
 96 Status NextElem(Sqlist L, int cur_e, int &next_e) {
 97     if (!L.elem)
 98         exit(OVERFLOW);
 99     if (LocateElem(L, cur_e) && LocateElem(L, cur_e) < L.length) {
100         next_e = L.elem[LocateElem(L, cur_e)];
101         return OK;
102     }
103     next_e = NULL;
104     return FALSE;
105 }//用next_e返回cur_e的后驱.
106 
107 Status ListInsert(Sqlist &L, int i, int e) {
108     if (!L.elem)
109         exit(OVERFLOW);
110     if (i<1 || i>ListLength(L)+1)
111         return ERROR;
112     if (L.length >= L.listsize) {
113         int* newbase = (int*)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(int));
114         if (!newbase)
115             exit(OVERFLOW);
116         L.elem = newbase;
117         L.listsize += LISTINCREMENT;
118     }
119     for (int n = L.length -1; n >=(i-1); --n) {
120         L.elem[n + 1] = L.elem[n];
121     }
122     L.elem[i-1] = e;
123     ++L.length;
124     return OK;
125 }//在第i个元素前插入e。
126 
127 Status DeleteElem(Sqlist &L,int i,int &e){
128     if (!L.elem||i<0||i>(L.length-1))
129         return ERROR;
130     e = L.elem[i];
131     for (int k = i; k < L.length - 1; ++k)
132         L.elem[k] = L.elem[k + 1];
133     return OK;
134 
135 }//删除下标为i的元素，用e返回值
136 
137 Status SortHTL(Sqlist &L) {
138     int max, change, n;
139     for (int m = 0; m != L.length; ++m) {
140         n = m;
141         max = L.elem[m];
142         for (int i = m+1; i != L.length; ++i) {
143             if (L.elem[i] > max) {
144                 max = L.elem[i];
145                 n = i;
146             }
147         }
148         change = L.elem[m];
149         L.elem[m] = L.elem[n];
150         L.elem[n] = change;
151     }
152     return OK;
153 }//从大到小排序
154 
155 Status SortLTH(Sqlist &L) {
156     int min, change, n;
157     for (int m = 0; m != L.length; ++m) {
158         n = m;
159         min = L.elem[m];
160         for (int i = m + 1; i != L.length; ++i) {
161             if (L.elem[i] < min) {
162                 min = L.elem[i];
163                 n = i;
164             }
165         }
166         change = L.elem[m];
167         L.elem[m] = L.elem[n];
168         L.elem[n] = change;
169     }
170     return OK;
171 }//从小到大排序
172 
173 Status ListPrint(Sqlist L) {
174     if (!L.elem)
175         exit(ERROR);
176     cout << "数组：";
177     for (int i = 0; i != L.length-1; ++i) {
178         cout << L.elem[i] << "、";
179     }
180     cout << L.elem[L.length - 1] << endl;
181     cout << "Length:" << L.length << "  ListSize:" << L.listsize << endl;
182     return OK;
183 }//打印数组L。
184 
185 Status MergeList(Sqlist L1, Sqlist L2, Sqlist &L3) {
186     
187     while ((L1.length + L2.length) > L3.listsize) {
188         L3.elem = (int*)realloc(L3.elem, (LISTINCREMENT + L3.listsize) * sizeof(int));
189         L3.listsize += LISTINCREMENT;
190     }
191     SortHTL(L1);
192     SortHTL(L2);
193     int m1 = 0;
194     int m2 = 0; 
195     while ( (m2 != L2.length ) ||(m1 != L1.length)) { 
196         if (L2.elem[m2] <L1.elem[m1]) {
197             ListInsert(L3, 0, L1.elem[m1]);
198             ++m1;
199         }
200         else {
201             ListInsert(L3, 0, L2.elem[m2]);
202             ++m2;
203         }
204             
205     }
206     if (m1 == L1.length-1) {        
207         for (m2; m2 != L2.length - 1; ++m2) {
208             ListInsert(L3, 0, L2.elem[m2]);
209         }
210     }
211     if (m2 == L2.length - 1) {
212         for (m1;m1 != L1.length - 1; ++m1) {
213             ListInsert(L3, 0, L1.elem[m2]);
214         }
215     }
216     L3.length = L1.length + L2.length;
217     return OK;
218 }//把L1、L2元素从小到大排列合并到L3里面
219 
220 Status ListPutin(Sqlist &L) {
221     int m=0;
222     while (cin >> m) {
223         if (m == -1)
224             break;
225         if (L.length >= L.listsize) {
226             L.elem = (int *)realloc(L.elem, (LISTINCREMENT + L.listsize) * sizeof(int));
227             L.listsize += LISTINCREMENT;
228         }
229         L.elem[L.length] = m;
230         ++L.length;
231     }
232     return OK;
233 }
234 
235 //=========================