数据结构实验报告1

实验名称：数据结构实验

学号：4558568 姓名：鹅鹅鹅

指导老师：鹅鹅鹅

计算机与信息学院

实验1线性表的抽象数据类型的实现

 实验目的

1. 按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；  实验环境

计算机、C语言程序设计环境

 实验学时

4学时，必做实验。  实验内容

① 直接排序和希尔排序 ② 冒泡排序和快速排序 ③ 选择排序和堆排序  实验步骤

先给出重点部分的流程图（不是整个程序，是部分），然后把编写的代码贴上来（注意要编辑下，不要直接放这里）  测试数据与实验结果

可把程序运行每个重要步骤截图贴这里

 小结

可写自己实验的体会，不能雷同，后果自负

通过实验，使我更加透彻地认识到排序的重要性； 实验总的来讲，并不难，但是C的调试很麻烦，我想我还是好好练习一下C语言吧。通过实验，让我认识到C语言中结构和指针的重要性。编程语言中嵌套的思想很重要，结构里面还可以套结构。 附录： #include\"stdio.h\" #define TRUE 1 #define FALSE 0 #define N 100

typedef struct Node { int elem[N]; int last; }List;

typedef int status;

//----------------------------------------------------------- status Initlast(List *a) { a->last=0; return TRUE; }

status input(List *a) { int i=1; printf(\"\\n请输入数据(数据总数小于100,且以100作为结束符):\"); scanf(\"%d\ while(a->elem[i++]!=100) {

a->last++; scanf(\"%d\ } return TRUE; }

status search(List *a,int b) { int low=1,high=a->last,mid=0; while(low<=high) { mid=(low+high)/2; if(b==a->elem[mid]) return mid; else if(belem[mid]) high=mid-1; else low=mid+1; } return TRUE;

}//-------------------------------------------------------------------- int pass(List *a,int low,int high) { int x=a->elem[low],left=low,right=high; while(leftelem[right]>=x) right--; if(leftelem[left]=a->elem[right]; left++; } while(leftelem[left]<=x) left++; if(leftelem[right]=a->elem[left]; right--; } } a->elem[left]=x; return left; }

void sort(List *a,int low,int high)//快速排序 { int mid; if(lowstatus put(List *a) { int i; for(i=1;i<=a->last;i++) printf(\"%6d\ printf(\"\\n\"); return TRUE; }

void bubble(List *a)//冒泡排序 { int i=0,j=0,n=a->last,m,flag=1; for(i=1;ielem[j]>a->elem[j+1]) { flag=1; m=a->elem[j]; a->elem[j]=a->elem[j+1]; a->elem[j+1]=m; } } }

void Insert(List *a)//直接插入排序 { int i=0,j=0; for(i=2;i<=a->last;i++) { a->elem[0]=a->elem[i]; j=i-1; while(a->elem[0]elem[j]) { a->elem[j+1]=a->elem[j];

j=j-1; } a->elem[j+1]=a->elem[0]; } }

void ShellInsert(List *a)//希尔排序 { int n=a->last,delta; for(delta=5;delta>0;delta--) { int j,i; for(i=1+delta;i<=n;i++) if(a->elem[i]elem[i-delta]) { a->elem[0]=a->elem[i]; for(j=i-delta;j>0&&a->elem[0]elem[j];j-=delta) a->elem[j+delta]=a->elem[j]; a->elem[j+delta]=a->elem[0]; } } }

void SelectSort(List *a)//选择排序 { int n,j,i,k,x; n=a->last; for(i=1;ielem[j]elem[k]) k=j; if(k!=i) { x=a->elem[i]; a->elem[i]=a->elem[k]; a->elem[k]=x; } } }

void onscreen() { printf(\"----------排序方法--------\\n\"); printf(\"--0.退出 --\\n\"); printf(\"--1.插入排序 --\\n\");

printf(\"--2.希尔排序 --\\n\"); printf(\"--3.选择排序 --\\n\"); printf(\"--4.快速排序 --\\n\"); printf(\"--5.冒泡排序 --\\n\"); printf(\"--6.折半查找 --\\n\"); printf(\"--------------------------\\n\"); }

void Switch() { List a; int i=0,low,high,b=0,j=0,n; printf(\"初始化顺序表:\\n\"); i=Initlast(&a); i=input(&a); printf(\"\\n表内元素原始序列为:\"); i=put(&a); onscreen(); printf(\"\\n请选择操作:\"); scanf(\"%d\ while(n) { switch(n) { case 1: printf(\"\\n表内元素经插入排序后的序列为:\"); Insert(&a); i=put(&a); break; case 2: printf(\"\\n表内元素经希尔排序后的序列为:\"); ShellInsert(&a); i=put(&a); break; case 3: printf(\"\\n表内元素经选择排序后的序列为:\"); SelectSort(&a); i=put(&a); break; case 4: low=1; high=a.last; sort(&a,low,high);//快速排序 printf(\"\\n表内元素经快速排序后的序列为:\"); i=put(&a);

break; case 5: bubble(&a); printf(\"\\n表内元素冒泡速排序后的序列为:\"); i=put(&a); break; case 6: printf(\"请输入要查找的数:\"); scanf(\"%d\ j=search(&a,b); printf(\"数的位置为:%d\\n\ break; } //printf(\"\\n\"); onscreen(); printf(\"\\n请选择操作:\"); scanf(\"%d\ } }

void main() { Switch(); }