这个实验三顺序表的实现历经了从前天下午开始在实验室研究标准答案到昨天上午开始写代码并且大概今天才调试成功也是一把鼻涕一把泪的
实验3、顺序表的基本操作 （6学时）
（1）实验目的
通过该实验，深入理解顺序表的逻辑结构、物理结构等概念，掌握顺序表基本操作的编程实现，注意顺序表插入、删除等操作过程中数据元素的移动现象，培养学生编写程序时，要考虑程序的强壮性，熟练掌握通过函数参数返回函数结果的办法。
（2）实验内容
编程实现顺序表下教材第二章定义的线性表的基本操作，最好用菜单形式对应各个操作，使其编程一个完整的小软件。
（3）参考界面
（3）验收/测试用例
通过菜单调用各个操作，测试点：
l 没有初始化前进行其他操作，程序是否能控制住；
l 初始化一个顺序表；
l 插入数据(位置， 数据)，要测插入位置不合法的情况（0,1）、（2,1），正确插入4个数据（1，2）、（1，1）、（3,3）；
l 显示顺序表中的数据，屏幕输出1， 2， 3；
l 判空，屏幕输出顺便表非空；
l 顺便表长度，屏幕输出3；
l 获取指定位置元素，要测指定位置在【1，3】范围之外的情况和之内的情况；
l 定位，输入：4， 输出：不存在，输入2，输出位置为2；
l 求直接前驱，要测求第一个元素的前驱、不存在顺序表中的元素的直接前驱，其他元素的直接前驱；
l 求直接后继，要测最后一个元素的后继、不存在顺序表中的元素的直接后继，其他元素的直接后继；
l 删除，要测位置在【1，3】范围之外的情况和之内的情况；
l 清空操作后再测长度；
l 销毁顺序表
16:22:33 第一次完成代码如下（但是有一个bug就是在32位 电脑上这个万能头文件不能使用）
1 #include<bits/stdc++.h> 2 #define LIST_INIT_SIZE 100 3 #define LISTINCREMENT 10 4 5 typedef int Status; 6 typedef int ElemType; 7 /* 8 typedef int status; 9 是个自定义类型的语句。 10 typedef用来定义类型的别名。 11 status i 就相当于 int i; 12 至于为什么叫status，原因可能为status的英文意思是状态，编程者想用int值表示一个状态，所以自定义一个类型。 13 这样status i;一看就知道变量i表示一个状态变量。 14 */ 15 typedef struct{ //给结构体起别名：SqList 16 ElemType *elem; //存储空间基址 17 int length; //当前长度 18 int listsize; //当前分配的存储容量（以sizeof（ElemType）为单位） 19 }SqList; 20 21 Status InitList(SqList &L); 22 Status DestroyList(SqList &L); 23 Status ClearList(SqList &L); 24 Status ListEmpty(SqList &L); 25 Status ListLength(SqList &L); 26 Status GetElem(SqList &L,int i,int *e); 27 Status PriorElem(SqList &L,int e,int *pre_e); 28 Status NextElem(SqList &L,int cur_e,int *pre_e); 29 Status ListInsert(SqList &L,int i,int e); 30 Status ListDelete(SqList &L,int i,int *e); 31 Status ListTraverse(SqList &L); 32 int main() 33 { 34 printf("1----初始化化一个线性表\n"); 35 printf("2----销毁线性表\n"); 36 printf("3----清空线性表\n"); 37 printf("4----判断线性表是否为空\n"); 38 printf("5----求线性表长度\n"); 39 printf("6----获取线性表指定 位置元素\n"); 40 printf("7----求前驱\n"); 41 printf("8----求后继\n"); 42 printf("9----在线性表指定位置插入元素\n"); 43 printf("10---删除线性表指定位置元素\n"); 44 printf("11---显示线性表\n"); 45 printf(" 退出，输入一个负数！\n"); 46 printf("请输入操作代码：\n"); 47 48 int n; 49 int count=0; 50 int dizhi; 51 int yuansu; 52 SqList L; 53 while(1) 54 { 55 printf("请输入功能指令："); 56 scanf("%d", &n); 57 if(n<1||n>11) 58 { 59 printf("没有此功能\n"); 60 break; 61 } 62 if(n==1) 63 count++; 64 if(count<1) 65 { 66 printf("请先初始化线性表（功能1）"); 67 continue; 68 } 69 switch(n) 70 { 71 case 1: 72 InitList(L); 73 break; 74 case 2: 75 DestroyList(L); 76 break; 77 case 3: 78 ClearList(L); 79 break; 80 case 4: 81 ListEmpty(L); 82 break; 83 case 5: 84 ListLength(L); 85 break; 86 case 6: 87 88 printf("请输入查找的位置"); 89 scanf("%d",&dizhi); 90 if(GetElem(L, dizhi, &yuansu)) 91 printf("第%d个元素为%d",dizhi,yuansu); 92 //获取元素为什么要再把yuansu给弄成空值？？？ 93 break; 94 case 7: 95 printf("请输入元素："); 96 scanf("%d",&dizhi); 97 if(PriorElem(L,dizhi, &yuansu)) 98 { 99 printf("你输入的元素的前驱为：%d\n",yuansu); 100 } 101 102 break; 103 case 8: 104 printf("请输入元素："); 105 scanf("%d",&dizhi); 106 if(PriorElem(L,dizhi, &yuansu)) 107 { 108 printf("你输入的元素的后继为：%d\n",yuansu); 109 } 110 111 break; 112 case 9: 113 printf("请输入插入位置：\n"); 114 scanf("%d", &dizhi); 115 printf("请输入插入元素: \n"); 116 scanf("%d", &yuansu); 117 ListInsert(L,dizhi,yuansu); 118 119 break; 120 case 10: 121 printf("请输入删除位置："); 122 scanf("%d",&dizhi); 123 if(ListDelete(L,dizhi,&yuansu)) 124 printf("你删除的数字为%d",yuansu); 125 126 break; 127 case 11: 128 ListTraverse(L); 129 break; 130 } 131 132 } 133 } 134 135 //构造一个空的线性表 136 Status InitList(SqList &L){ 137 L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); 138 if(!L.elem) exit(OVERFLOW); //存储分配失败 139 L.length = 0; //空表的长度为0 140 L.listsize = LIST_INIT_SIZE; //初始存储容量 141 return 1; 142 } 143 144 //销毁线性表 145 Status DestroyList(SqList &L){ 146 if(L.elem==NULL) 147 { 148 printf("线性表不存在"); 149 } 150 free(L.elem); 151 L.elem=NULL; 152 printf("销毁成功\n"); 153 154 } 155 156 //清空线性表 157 Status ClearList(SqList &L){ 158 if(L.elem==NULL) 159 { 160 printf("线性表不存在"); 161 } 162 L.length=0; 163 printf("线性表已清空"); 164 165 } 166 167 //判断线性表是否为空 168 Status ListEmpty(SqList &L){ 169 if(L.elem==NULL) 170 { 171 printf("线性表为空表"); 172 } 173 else 174 printf("线性表不为空"); 175 } 176 177 //求线性表长度 178 Status ListLength(SqList &L){ 179 if(L.elem==NULL) 180 { 181 printf("线性表为空表"); 182 } 183 printf("线性表长度为%d",L.length); 184 } 185 186 //获取线性表指定位置插入元素 187 Status GetElem(SqList &L,int i,int *e){ 188 if(L.elem==NULL) 189 { 190 printf("线性表为空表"); 191 return 0; 192 } 193 *e=L.elem[i-1]; 194 return 1; 195 } 196 197 //求前驱 198 Status PriorElem(SqList &L,int cur_e,int &pre_e){ 199 int i=0; 200 while(L.elem[i]!=cur_e&&i<L.length) 201 i++; 202 if(i<L.length) 203 { 204 if(i=0) 205 { 206 printf("首元素没有前驱"); 207 return 0; 208 } 209 pre_e=L.elem[i-1]; 210 return 1; 211 }else 212 printf("你输入的元素不存在"); 213 return 0; 214 215 216 } 217 218 //求后驱 219 Status NextElem(SqList &L,int cur_e,int &pre_e){ 220 int i=L.length-1; 221 while(L.elem[i]!=cur_e&&i>=0) 222 i--; 223 if(i>=0) 224 { 225 if(i=L.length-1) 226 { 227 printf("尾元素没有后驱"); 228 return 0; 229 } 230 pre_e=L.elem[i+1]; 231 return 1; 232 }else 233 printf("你输入的元素不存在"); 234 return 0; 235 236 237 } 238 239 //在线性表指定位置插入元素 240 Status ListInsert(SqList &L,int i,int e){ 241 int *p,*q,*newbase; 242 if(i<1||i>L.length+1) return 0; //i值不合法 243 if(L.length>=L.listsize){ 244 newbase=(ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType)); 245 if(!newbase) exit(OVERFLOW); //存储分配失败 246 L.elem = newbase; //新基址 247 L.listsize += LISTINCREMENT; //增加存储容量 248 } 249 q = &(L.elem[i-1]); //q为插入位置 250 for(p = &(L.elem[L.length-1]);p>=q;--p) //插入位置及之后的元素右移 251 *(p+1)=*p; 252 *q = e; //插入e 253 ++L.length; //表长加1 254 return 1; 255 } 256 257 //删除线性表指定位置元素 258 Status ListDelete(SqList &L,int i,int *e){ 259 //在顺序线性表L中删除第i个元素，并用e返回其值 260 //i的合法性为 1<=i<=ListLength 261 int pos; 262 if (i<1||i>L.length) 263 { 264 printf("指定的删除位置不合法，应该在1到%d之间!\n",L.length); 265 return 0; 266 } 267 *e=L.elem[i-1]; 268 for(pos=i-1;pos<L.length-1;pos++) 269 L.elem[pos]=L.elem[pos+1]; 270 L.length--; 271 printf("删除成功！"); 272 return 1; 273 } 274 275 //显示线性表 276 Status ListTraverse(SqList &L){ 277 if(L.elem==NULL) 278 { 279 printf("线性表为空表"); 280 return 0; 281 } 282 for(int i=0;i<L.length;i++) 283 printf("%d", L.elem[i]); 284 printf("\n"); 285 return 1; 286 287 } 288 289
