|
实验目的：用c语言实现顺序表的基本操作，切实感受一下线性表的顺序表示和实现，真正深刻系统的理解线性表的作用，在实践上，掌握使用实验设备的技能技巧和程序的调试方法。最好能很好的运用顺序表来帮助实现一些实际小项目。 基本操作： 1. 从键盘输入n个整数，填入顺序表 2. 输出顺序表至屏幕 3. 查找值为某个整数的元素的位序 4. 在顺序表中插入一个元素 5. 删除顺序表中某个整数元素 6. 逆序排列顺序表中的数据元素 7. 删除相同元素 8. 给顺序表排序
实验内容： 因为想让程序变得整洁，我把函数和定义部分放在一个SqList.h的头文件里，Sqlist.c文件里面只包含main函数和菜单函数。 本实验是参照严蔚敏的C语言版《数据结构》一书实践的
函数部分: 1. 首先认真理解书上用类C给出的线性表的定义（算法2.2），用C语言实现如下： typedef struct { int *data; int length; int size; }SqList; 说明： 其中length记录顺序表实际存储长度，size记录此顺序表的最大存储长度。 data的类型就是你要存入顺序表的类型。
2. 参照书上算法2.2，写出一个构造空线性表L的函数：InitList()，用C语言实现如下： int InitList(SqList *L) //构造空线性表 { L->data = (int *)malloc(N*sizeof(int)); if(!L->data) return 0; L->length = 0; L->size = N; return 1; } 说明： 因为构造线性表这个函数是要对传入对象操作的，所以只能用return或者传入指针型引用参数这两种方法实现对传入对象的操作，我选择了后者，接下来的函数里也是一样的。
3. 为了能打印输出所构造的线性表，单独写了一个打印函数：ShowList()，用C语言实现如下： int ShowList(SqList *L) //查看 { int i; if(L->length==0) {printf("列表为空！\n"); return 0;} for(i=1;i<=L->length;i++) { if(i%5==1) printf("\n");//每输出5个数据一换行 printf("%-5d",L->data[i-1]); } printf("\n"); return 1; } 说明： 里面加了每输出5个数据一换行的打印方法； 函数里面用到了以前数组的表示方法L->data[i-1]，说明我们定义的线性表其实就是数组的另一种表示方法。
4. 实现查找的操作，参照算法2.5，用C语言实现如下： int LocateList(SqList *L,int e) //查找 { int i=1,*p; p=L->data; for(;i<=L->length ;p++,i++) if(*p == e) break; if(i<=L->length) return i; else return 0; } 说明： 这函数仅仅实现了查找一个数在线性表的位置而已，还可以改变第一个if语句来实现更为复杂的查找。 函数是使用return来返回位置数据的。
5. 实现插入操作，参照算法2.3，用C语言实现如下： int InsertList(SqList *L,int i,int e) //插入 { int *q,*p,*newbase; if(i<1 || i>L->length+1) {printf("你的插入位置输入有误！"); return 0;} if(L->length >= L->size) //顺序表空间不够，再次分配内存 { newbase=(int *)realloc(L->data,(L->length+M)*sizeof(int)); if(!newbase) {printf("扩展列表失败！");return 0;} L->data = newbase; L->size = L->size + M; } q = &(L->data[i-1]); p = &(L->data[L->length-1]); for(; p>=q ;--p) *(p+1)=*p; *q=e; L->length++; return 1; } 说明： 函数有一个判断顺序表空间的步骤运用了realloc函数； 插入过程用到了两个定位指针p,q； 插入过程是先把插入位置以后的数据全部后移一位空出插入位置来放插入元素； 注意将length++；
6. 实现删除操作，参照算法2.4，用C语言实现如下： int DeleteList(SqList *L,int i) //删除 { int *p,*q; if(i<1 || i>L->length+1) {printf("你的删除位置输入有误！"); return 0;} p = &(L->data[i-1]); q = &(L->data[L->length-1]); for(p++; p<=q ;p++) *(p-1) = *p; L->length--; return 1; } 说明： 删除过程和插入相反，直接将要删除位置以后的数据全部前移一位就实现了删除操作； 注意length--；
7. 实现逆序操作，用C语言实现如下： void ChangeList(SqList *L) // 逆序 { int *p,*q,cup,i; for(i=0;i<=L->length-1-i;i++) { p = &(L->data[i]); q = &(L->data[L->length-1-i]); {cup=*p;*p=*q;*q=cup;} } } 说明： 这里由于没有必要返回值，所以我定义了一个空类型的逆序函数； 实现过程就是把前后对称的两个元素交换，直到计数器i大于length的一半后结束。
8. 实现顺序表中相同元素只留一个的操作，就是调用删除函数将相同元素删除即可。 这里最重要的是找到相同元素，我没有单独写一个函数，直接是在menu()函数里面实现的 方法如下： for(i=1;i<=L->length;i++) for(j=i+1;j<=L->length;j++) if(L->data[j-1]==L->data[i-1]) DeleteList(L,j); 说明：运用了两成循环来查找相同元素。
9. 实现对顺序表元素进行排序，用C语言实现如下： void SortList(SqList *L) //冒泡排序 { int i,j,cup; for(i=L->length-1;i>=0;i--) { for(j=0;j<i;j++) { if(L->data[j]>L->data[j+1]) { cup=L->data[j];L->data[j]=L->data[j+1];L->data[j+1]=cup; } } } } 说明： 我使用了冒泡排序，这是我目前最熟悉的一个排序方法，当然还有很多排序方法。
10.实现尾插法创建顺序表, 用C语言实现如下： int CreateList(LinkList L,int n) //尾插法 { int ShowList(LinkList L); int i; char m; LinkList p,s,q; if(L->next!=NULL) { loop:printf("链表已存在，是否放弃当前链表创建新链表？(y/n)"); m=getchar(); if(m=='y') { for(p=L,q=L->next;q->next!=NULL;) { p=q; q=q->next; free(p); } free(q); L->next=NULL;//重新初始化 CreateList(L,n); return 1;}//覆盖已有链表 if(m=='n') return 0; else goto loop; } L->next = NULL; p=L; for(i=0;i<n;i++) { system("cls"); //清屏函数,只是为了界面简洁 s=(LinkList) malloc (sizeof(LNode)); ShowList(L); printf("开始输入第%d个数：",i+1); scanf("%d",&s->data); s->next = NULL; p->next = s; p = s; } return 1; } 说明: 此函数能覆盖掉以前的顺序表,带有选择,使用了gotoloop语句,有一定的容错性
菜单部分: 我自己写了一个小的菜单界面,只是为了让程序更简洁,更容易使用,这一部分代码比较多,重复的代码很多就不全部放上来了。以下就是我菜单函数的一部分: void menu(LinkList L,int m) { int i,e,data[N]; char s='r',w='y'; if(m==-1) { loop:system("cls"); printf(" Welcome to vell001!!!\n\n"); printf("1. 从键盘输入N个整数，创建新链表\n"); printf("2. 输出链表至屏幕\n"); printf("3. 查找值为某个整数的元素的位序\n"); printf("4. 在链表中插入一个元素\n"); printf("5. 删除链表中某个元素\n"); printf("6. 逆序排列链表表中的数据元素\n"); printf("7. 合并相同元素\n"); printf("8. 给顺序表排序\n"); printf("9. 统计链表中的某个元素的个数\n"); printf("0. 退出\n"); printf("\n你选择："); scanf("%d",&m); if(m<-1||m>9) goto loop; }
if(m==1) { while(s=='r') { system("cls"); CreateList(L,N); //调用创建顺序表函数 loop1:system("cls"); ShowList(L); printf("\n重新开始 请按'R'键\n返回menu 请按'M'键\n直接退出 请按'Q'键\n"); s=getch(); if(s=='r') continue; if(s=='m') {menu(L,-1); break;} if(s=='q') {menu(L,0); break;} else goto loop1; } } 。 。 。 if(m==0) //退出时秀一下,呵呵 { system("cls"); printf("\n\n\n\n 谢谢使用！！！\n\n\n vell001"); Sleep(1000); } } 最后的main函数 int main(void) { LinkList L; L=(LinkList) malloc (sizeof(LNode));//给L分配一个内存; L->next=NULL; //初始化一下 menu(L,-1); //直接调用menu函数运行 } 实验步骤: 1. 先熟系书上的算法,做到脱离书本能把整个算法回忆一遍 2. 按顺序一个一个函数用C语言写出来,注意要做到一个函数写完立马做一下测试,这样就不容易出现一团糟的代码了...还有记得加注释 3. 最后整理一下代码,让自己的代码变得更整洁,更易懂. 实验总结： 在创建链表时这边遇到过一个小问题,刚开始的时候没有给L分配内存,使得创建顺序表时出错了,因为上面我用到了" if(L->next!=NULL)"这个判断,所以必须先给L分配内存,所以我在main函数里加了个初始化。由于以前用的是DEVC++这个编译软件,调试功能不是很强,这个错误纠结了我几个小时,这件事我明显感觉到编程的严谨性了，最后程序完美运行真的很激动。。。 |
|
|
来自： 昵称16859867 > 《算法》
Vell001.zip 
