《数据结构》（C语言版）严蔚敏著 - 数据结构实验指导

《数据结构》实验指导及报告书

/ 学年 第 学期

姓 名：______________ 学 号：______________ 班 级：______________ 指导教师：______________

数学与统计学院

2011

1

预备实验 C语言的函数数组指针结构体知识

一、实验目的

1、复习C语言中函数、数组、指针、结构体与共用体等的概念。 2、熟悉利用C语言进行程序设计的一般方法。

二、实验预习

说明以下C语言中的概念 1、 函数：

2、 数组：

3、指针：

4、结构体

5、共用体

三、实验内容和要求

1、调试程序：输出100以内所有的素数（用函数实现）。 #include

int isprime(int n){ /*判断一个数是否为素数*/ int m; for(m=2;m*m<=n;m++)

if(n%m==0) return 0; return 1;

}

int main(){ /*输出100以内所有素数*/

int i; printf(\for(i=2;i<100;i++)

if(isprime(i)==1) printf(\return 0;

}

运行结果：

2、 调试程序：对一维数组中的元素进行逆序排列。 #include #define N 10 int main(){

2

int a[N]={0,1,2,3,4,5,6,7,8,9},i,temp;

printf(\for(i=0;i

temp=a[i]; a[i]=a[N-i-1]; a[N-i-1]=temp;

printf(\for(i=0;i

return 0; }

运行结果：

3、 调试程序：在二维数组中，若某一位置上的元素在该行中最大，而在该列中最小，则该元素即为该二维数组的一个鞍点。要求从键盘上输入一个二维数组，当鞍点存在时，把鞍点找出来。 #include

#define M 3 #define N 4 int main(){ int a[M][N],i,j,k; printf(\请输入二维数组的数据：\\n\

for(i=0;i

for(j=0;j

for(j=0;j

for(i=0;i

/*找出第i行的最大值*/

if(a[i][j]>a[i][k]) k=j;

for(j=0;j

if(a[j][k]

/*在第i行找到鞍点*/

break; if(j==M)

printf(\

3

}

return 0; }

运行结果：

4、 调试程序：利用指针输出二维数组的元素。 #include int main(){

int a[3][4]={1,3,5,7,9,11,13,15,17,19,21,23}; int *p;

for(p=a[0];p

printf(\

return 0; }

运行结果：

5、 调试程序：设有一个教师与学生通用的表格，教师的数据有姓名、年龄、职业、教研室四项，学生有姓名、年龄、专业、班级四项，编程输入人员的数据，再以表格输出。 #include

#define N 10 struct student{ char name[8]; /*姓名*/ int age; /*年龄*/ char job; /*职业或专业，用s或t表示学生或教师*/

union {

int class;

/*班级*/

char office[10]; /*教研室*/ }depa;

}stu[N]; int main(){

int i; int n;

printf(“\\n请输入人员数(<10):\\n”); scanf(“%d”,&n); for(i=0;i

scanf(\if(stu[i].job==’s’) scanf(\

4

else

scanf(\ } printf(“name age job class/office”); for(i=0;i

if(stu[i].job==’s’)

printf(\

else printf(\

}

}

输入的数据：2 Wang 19 s 99061 Li 36 t computer 运行结果：

四、实验小结

五、教师评语

5

int main(){

SqStack ss;

printf(\ CreateStack(&ss);

printf(\ PrintStack(&ss); return 0;

} ? 算法分析：输入元素序列1 2 3 4 5，为什么输出序列为5 4 3 2 1？体现了栈的什么

特性？

2、在第1题的程序中，编写一个十进制转换为二进制的数制转换算法函数（要求利用栈来实现），并验证其正确性。 ? 实现代码

?

验证

3、阅读并运行程序，并分析程序功能。 #include #include #include #define M 20

#define elemtype char typedef struct {

elemtype stack[M]; int top; }

stacknode;

void init(stacknode *st);

void push(stacknode *st,elemtype x); void pop(stacknode *st);

16

void init(stacknode *st) {

st->top=0; }

void push(stacknode *st,elemtype x) {

if(st->top==M)

printf(\ else {

st->top=st->top+1; st->stack[st->top]=x; } }

void pop(stacknode *st) {

if(st->top>0) st->top--;

else printf(“Stack is Empty!\\n”); }

int main() {

char s[M]; int i;

stacknode *sp;

printf(\ sp=malloc(sizeof(stacknode)); init(sp);

printf(\ gets(s);

for(i=0;i

if(s[i]=='(')

push(sp,s[i]); if(s[i]==')') pop(sp); }

if(sp->top==0)

printf(\ else

printf(\ return 0; }

? ? ? ? ?

输入：2+((c-d)*6-(f-7)*a)/6 运行结果：

输入：a-((c-d)*6-(s/3-x)/2 运行结果： 程序的基本功能：

17

以下为选做实验：

4、设计算法，将一个表达式转换为后缀表达式，并按照后缀表达式进行计算，得出表达式得结果。 ? 实现代码

5、假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点（不设队头指针），试编写相应的置空队列、入队列、出队列的算法。 实现代码：

四、实验小结

五、教师评语

18

实验三 串的模式匹配

一、实验目的

1、了解串的基本概念

2、掌握串的模式匹配算法的实现

二、实验预习

说明以下概念 1、模式匹配：

2、BF算法：

3、KMP算法：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果。 #include #include #define MAXSIZE 100 typedef struct{

char data[MAXSIZE]; int length; }SqString;

int strCompare(SqString *s1,SqString *s2); /*串的比较*/

void show_strCompare();

void strSub(SqString *s,int start,int sublen,SqString *sub); /*求子串*/

void show_subString();

int strCompare(SqString *s1,SqString *s2){ int i; }

void show_strCompare(){ SqString s1,s2; int k;

printf(\

19

for(i=0;ilength&&ilength;i++) if(s1->data[i]!=s2->data[i])

return s1->data[i]-s2->data[i]; return s1->length-s2->length;

printf(\ gets(s1.data);

s1.length=strlen(s1.data); printf(\ gets(s2.data);

s2.length=strlen(s2.data);

if((k=strCompare(&s1,&s2))==0) printf(\ else if(k<0)

printf(\ else

printf(\

printf(\}

void strSub(SqString *s,int start,int sublen,SqString *sub){

int i;

if(start<1||start>s->length||sublen>s->length-start+1){ sub->length=0; }

for(i=0;i

sub->data[i]=s->data[start+i-1]; sub->length=sublen; }

void show_subString(){ SqString s,sub;

int start,sublen,i;

printf(\ printf(\ gets(s.data);

s.length=strlen(s.data); printf(\ scanf(\

printf(\ scanf(\

strSub(&s,start,sublen,&sub); if(sub.length==0) printf(\ else{

printf(\ for(i=0;i

printf(\ }

printf(\

20

}

int main(){ int n; do {

printf(\ printf(\ printf(\ printf(\ printf(\ scanf(\ getchar();

switch(n){

case 1:show_strCompare();break; case 2:show_subString();break; default:n=0;break; }

}while(n); return 0; }

?

运行程序

输入： 1

student students

2

Computer Data Stuctures 10 4

运行结果：

2、实现串的模式匹配算法。补充下面程序，实现串的BF和KMP算法。 #include #include #define MAXSIZE 100 typedef struct{

char data[MAXSIZE]; int length;

}SqString;

int index_bf(SqString *s,SqString *t,int start);

21

void getNext(SqString *t,int next[]);

int index_kmp(SqString *s,SqString *t,int start,int next[]); void show_index();

int index_bf(SqString *s,SqString *t,int start){

补充代码..... }

void getNext(SqString *t,int next[]){ int i=0,j=-1; next[0]=-1;

while(ilength){

if((j==-1)||(t->data[i]==t->data[j])){

i++;j++;next[i]=j; }else

j=next[j]; } }

int index_kmp(SqString *s,SqString *t,int start,int next[]){ 补充代码..... }

void show_index(){ SqString s,t;

int k,next[MAXSIZE]={0},i;

printf(\ printf(\

22

gets(s.data);

s.length=strlen(s.data); printf(\ gets(t.data);

t.length=strlen(t.data);

printf(\ scanf(\

printf(\ getNext(&t,next); printf(\ printf(\ for(i=0;i

printf(\ printf(\}

int main(){

show_index(); return 0;

}

输入：

abcaabbabcabaacbacba abcabaa 1

运行结果：

四、实验小结

五、教师评语

23

实验四 二叉树

一、实验目的

1、掌握二叉树的基本特性

2、掌握二叉树的先序、中序、后序的递归遍历算法 3、理解二叉树的先序、中序、后序的非递归遍历算法

4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性

二、实验预习

说明以下概念 1、二叉树：

2、递归遍历：

3、 非递归遍历：

4、层序遍历：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。 #include #include #define MAX 20

typedef struct BTNode{ /*节点结构声明*/ char data ; /*节点数据*/

struct BTNode *lchild;

struct BTNode *rchild ; /*指针*/

}*BiTree;

void createBiTree(BiTree *t){ /* 先序遍历创建二叉树*/ char s;

BiTree q;

printf(\s=getche();

if(s=='#'){*t=NULL; return;}

q=(BiTree)malloc(sizeof(struct BTNode));

if(q==NULL){printf(\q->data=s;

*t=q;

createBiTree(&q->lchild); /*递归建立左子树*/ createBiTree(&q->rchild); /*递归建立右子树*/

24

}

void PreOrder(BiTree p){ /* 先序遍历二叉树*/ if ( p!= NULL ) {

printf(\ PreOrder( p->lchild ) ; PreOrder( p->rchild) ; } }

void InOrder(BiTree p){ /* 中序遍历二叉树*/ if( p!= NULL ) {

InOrder( p->lchild ) ; printf(\ InOrder( p->rchild) ; } }

void PostOrder(BiTree p){ /* 后序遍历二叉树*/ if ( p!= NULL ) {

PostOrder( p->lchild ) ; PostOrder( p->rchild) ; printf(\

} }

void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/ BiTree stack[MAX],q; int top=0,i;

for(i=0;i

while(q!=NULL){

printf(\

if(q->rchild!=NULL) stack[top++]=q->rchild; if(q->lchild!=NULL) q=q->lchild; else

if(top>0) q=stack[--top]; else q=NULL; } }

void release(BiTree t){ /*释放二叉树空间*/ if(t!=NULL){

release(t->lchild); release(t->rchild); free(t);

25

for(i=0;i

int main() {

graph ga;

int i,j;

createGraph(&ga);

printf(\无向图的邻接矩阵：\\n\

for(i=0;i

for(j=0;j

printf(\ printf(\ }

init_visit(); tdfs(&ga); init_visit(); tbfs(&ga); return 0;

}

? 根据右图的结构验证实验，输入： ABCDEFGH# 0,1 0,2 0,5 1,3 1,4 2,5 2,6 3,7 4,7 -1,-1 ?

2、阅读并运行下面程序，补充拓扑排序算法。 #include #include #define N 20

运行结果：

1 0 B 4 E 7 H A C 2 F 5 G 6

3 D 31

typedef struct edgenode{ /*图的邻接表：邻接链表结点*/ int adjvex; /*顶点序号*/

struct edgenode *next; /*下一个结点的指针*/ }edgenode;

typedef struct vnode{ /*图的邻接表：邻接表*/ char data; /*顶点信息*/

int ind; /*顶点入度*/

struct edgenode *link; /*指向邻接链表指针*/ }vnode;

void createGraph_list(vnode adjlist[],int *p)； /*建立有向图的邻接表*/ void topSort(vnode g[],int n)； /*拓扑排序*/

void createGraph_list(vnode adjlist[],int *p){ /*建立有向图的邻接表*/ int i,j,n,e; char v;

edgenode *s; i=0;n=0;e=0;

printf(\输入顶点序列(以#结束)：\\n\ while((v=getchar())!='#')

{

adjlist[i].data=v; /*读入顶点信息*/ adjlist[i].link=NULL; adjlist[i].ind=0; i++; }

n=i; *p=n;

/*建立邻接链表*/

printf(\请输入弧的信息(i=-1结束)：i,j:\\n\ scanf(\

while(i!=-1){

s=(struct edgenode*)malloc(sizeof(edgenode)); s->adjvex=j;

s->next=adjlist[i].link; adjlist[i].link=s;

adjlist[j].ind++; /*顶点j的入度加1*/ e++;

scanf(\ }

printf(\邻接表:\

for(i=0;i

printf(\

32

s=adjlist[i].link;

while(s!=NULL){

printf(\ s=s->next; } } }

void topSort(vnode g[],int n){ /*拓扑排序*/ }

int main(){

vnode adjlist[N]; int n,*p; p=&n;

createGraph_list(adjlist,p); return 0;

}

? 根据输入，输出有向图的拓扑排序序列。并画出有向图。输入: ABCDEF# 0,1 1,2 2,3 4,1 4,5 -1,-1 ?

运行结果：

33

3、阅读并运行下面程序。

#include #define N 20 #define TRUE 1

#define INF 32766 /*邻接矩阵中的无穷大元素*/ #define INFIN 32767 /*比无穷大元素大的数*/

typedef struct { /*图的邻接矩阵*/ int vexnum,arcnum; char vexs[N]; int arcs[N][N]; }

graph;

void createGraph_w(graph *g,int flag); void prim(graph *g,int u); void dijkstra(graph g,int v); void showprim(); void showdij();

/*建带权图的邻接矩阵,若flag为1则为无向图，flag为0为有向图*/ void createGraph_w(graph *g,int flag) {

int i,j,w; char v;

g->vexnum=0;

g->arcnum=0; i=0;

printf(\输入顶点序列(以#结束)：\\n\ while((v=getchar())!='#') {

g->vexs[i]=v; /*读入顶点信息*/ i++; }

g->vexnum=i;

for(i=0;i<6;i++) /*邻接矩阵初始化*/ for(j=0;j<6;j++)

g->arcs[i][j]=INF;

printf(\输入边的信息：\\n\

scanf(\读入边(i,j,w)*/ while(i!=-1) /*读入i为－1时结束*/ {

g->arcs[i][j]=w;

34

if(flag==1)

g->arcs[j][i]=w;

scanf(\ } }

void prim(graph *g,int u)/*出发顶点u*/ {

int lowcost[N],closest[N],i,j,k,min;

for(i=0;ivexnum;i++) /*求其他顶点到出发顶点u的权*/ {

lowcost[i]=g->arcs[u][i]; closest[i]=u; }

lowcost[u]=0;

for(i=1;ivexnum;i++) /*循环求最小生成树中的各条边*/ { min=INFIN;

for(j=0;jvexnum;j++) /*选择得到一条代价最小的边*/ if(lowcost[j]!=0&&lowcost[j]

min=lowcost[j];

k=j; }

printf(\/*输出该边*/

lowcost[k]=0; /*顶点k纳入最小生成树 */

for(j=0;jvexnum;j++) /*求其他顶点到顶点k 的权*/ if(g->arcs[k][j]!=0&&g->arcs[k][j]

lowcost[j]=g->arcs[k][j]; closest[j]=k; } } }

void printPath(graph g,int startVex,int EndVex) {

int stack[N],top=0; /*堆栈*/ int i,k,j;

int flag[N]; /*输出路径顶点标志*/ k=EndVex;

for (i=0;i

35

printf(\

flag[j]=1;

stack[top++]=k;

while (top>0) /*找j到k的路径*/ {

for (i=0;i

if (path[k][i]==1 && flag[i]==0) /*j到k的路径含有i顶点*/ {

if (g.arcs[j][i]!=INF ) /*j到i的路径含有中间顶点*/ {

printf(\ /*输出j到k的路径的顶点i*/ flag[i]=1; j=i;

k=stack[--top]; break; } else

{

if (i!=k) stack[top++]=i; /*break;*/ } } } }

void dijkstra(graph g,int v){ /*dijkstra算法求单源最短路径*/ int path[N][N],dist[N],s[N]; int mindis,i,j,u,k;

for(i=0;i

for(j=0;j

dist[v]=0; s[v]=1;

for(i=0,u=1;i

for(j=0;j

36

if(s[j]==0)

if(dist[j]

mindis=dist[j]; }

s[u]=1;

for(j=0;j

if((s[j]==0)&&dist[u]+g.arcs[u][j]

printf(\顶点%c->到各顶点的最短路径\\n\ for(i=0;i

printf(\顶点%c->顶点%c：\ if(dist[i]==INF||dist[i]==0) printf(\无路径\

else{

printf(\

printf(\经过顶点：\

printPath(g,v,i); /*输出v到i的路径*/ } } }

void showprim()/*最小生成树prim算法演示*/ {

graph ga;

createGraph_w(&ga,1); prim(&ga,0); }

void showdij(){ /*dijstra算法演示*/ graph ga;

createGraph_w(&ga,0); dijkstra(ga,0); }

int main(){

showprim(); /*prim算法演示*/ getchar();

showdij(); /*dijstra算法演示*/

37

return 0;

}

? 下面的输入分别验证prim算法和dijstra算法。输入实例的第一部分为无向图，求

其最小生成树；输入的第二部分为有向图，求其最短路径。 最小生成树 最短路径

ABCDEF# 0,1,6 0,2,1 0,3,5 1,2,5 1,4,3 2,3,5 2,4,6 2,5,4 3,5,2 4,5,6 -1,-1,-1 ? 运行结果：（并画出两个图）

最小生成树

四、实验小结

五、教师评语

ABCDEF# 0,2,10 0,5,100 0,4,30 1,2,5 2,3,50 3,4,20 3,5,10 4,3,20 4,5,60 -1,-1,-1

最短路径

38

实验六 查找

一、实验目的

1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。

3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。

二、实验预习

说明以下概念 1、顺序查找：

2、折半查找：

3、哈希函数：

4、冲突及处理：

三、实验内容和要求

1. 静态查找表技术

依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题：

查找表1 ： { 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 } ，查找key = 41 查找表2 ： {12 ，76 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 } ，查找key =35 查找key=41的算法： 比较次数： 查找key=35的算法： 比较次数：

?

顺序查找算法算法实现代码

39

?

折半查找算法算法实现代码

2、哈希表的构造与查找

/* 采用开放地址法构造哈希表*/ #include #include #define MAXSIZE 25 #define P 13

#define OK 1 #define ERROR 0

#define DUPLICATE -1 #define TRUE 1

#define FALSE 0

typedef struct{ /*哈希表元素结构*/ int key; /*关键字值*/

int flag; /*是否存放元素*/ }ElemType;

typedef struct {

ElemType data[MAXSIZE];

int count; /*元素个数*/ int sizeindex; /*当前哈希表容量*/ }HashTable;

int d1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}; /*线性探测序列*/

int d2[15]={0,1,-1,2*2,-2*2,3*3,-3*3,4*4,-4*4,5*5,-5*5,6*6,-6*6,7*7,-7*7}; /*二次探测序列*/

void dataset(int ds[],int *len);

int InsertHash(HashTable *H,int e,int d[]);

int CreateHash(HashTable *H,int ds[],int len,int d[]); int SearchHash(HashTable *H, int e,int d[]);

40

void menu();

/*输入查找表*/

void dataset(int ds[],int *len){ int n,m; n=0;

printf(\查找表输入：\

while(scanf(\以输入一个非整数作为结束*/ ds[n]=m; n++; } *len=n; }

/*计算哈希地址，插入哈希表*/

int InsertHash(HashTable *H,int e,int d[]){ int k,i=1; k=e%P;

while(H->data[k].flag==TRUE||k<0){ k=(e%P+d[i])%MAXSIZE;i++; if(i>=15)

return ERROR; }

H->data[k].key=e;

H->data[k].flag=TRUE; H->count++; return OK; }

/*构造哈希表*/

int CreateHash(HashTable *H,int ds[],int len,int d[]){ int i;

for(i=0;i

if(SearchHash(H,ds[i],d)!=-1) return DUPLICATE; InsertHash(H,ds[i],d); if(H->count>=MAXSIZE) return ERROR; }

return OK; }

/*初始化哈希表*/

void InitHash(HashTable *H){ int i;

for(i=0;idata[i].key=0;

H->data[i].flag=FALSE;

41

}

}

/*在哈希表中查找*/

int SearchHash(HashTable *H, int e,int d[]){ int k,i=1;

k=e%P;

while(H->data[k].key!=e){ k=(e%P+d[i])%MAXSIZE;i++; if(i>=15) return -1; }

return k; }

/*演示菜单*/

void menu(){

int choice;int *p;

HashTable h;

h.count=0;h.sizeindex=MAXSIZE; int a[MAXSIZE]={0};

int i,n,e;

dataset(a,&n); /*建立查找表*/

getchar(); printf(\ do{

printf(\哈希查找演示----\\n\ printf(\线性探测构造哈希表\\n\ printf(\二分探测构造哈希表\\n\ printf(\退出\\n\ printf(\输入选择：\ scanf(\ if(choice==1) p=d1;

else if(choice==2) p=d2; else

return;

InitHash(&h); /*初始化哈希表*/

if(!(i=CreateHash(&h,a,n,p))) /*构造哈希表*/ printf(\哈希表构造失败！\\n\ else if(i==DUPLICATE)

printf(\哈希表具有重复关键字！\\n\ else{

printf(\哈希表：\\n\ for(i=0;i

42

printf(\

printf(\哈希查找\\n输入要查找的key值：\ getchar();

scanf(\

if((i=SearchHash(&h,e,p))==-1) printf(\未找到\\n\ else

printf(\在哈希表中下标为%d\\n\ }

getchar(); }while(1); }

int main(){ menu(); return 0;

}

输入查找表为：19 14 23 1 68 20 84 27 55 11 10 79（注意以输入一个非整数结束）。 运行结果： 1)线性探测散列： 哈希表形态：

84在哈希表中的位置: 2）二次探测散列： 哈希表形态：

84在哈希表中的位置：

四、实验小结

五、教师评语

43

实验七 排序

一、实验目的

1、掌握内部排序的基本算法；

2、分析比较内部排序算法的效率。

二、实验预习

说明以下概念 1、简单排序：

2、希尔排序：

3、快速排序：

4、堆排序：

三、实验内容和要求

1. 运行下面程序： #include #include #define MAX 50

int slist[MAX]; /*待排序序列*/

void insertSort(int list[], int n); void createList(int list[], int *n); void printList(int list[], int n);

void heapAdjust(int list[], int u, int v); void heapSort(int list[], int n);

/*直接插入排序*/

void insertSort(int list[], int n) {

int i = 1, j = 0, node = 0, count = 1; printf(\对序列进行直接插入排序：\\n\printf(\初始序列为：\printList(list, n); for(i = 2; i <= n; i++) {

node = list[i]; j = i - 1;

while(j >= 0 && node < list[j])

44

}

}

{

list[j+1] = list[j]; --j; }

list[j+1] = node;

printf(\第%d次排序结果：\printList(list, n);

/*堆排序*/

void heapAdjust(int list[], int u, int v) {

int i = u, j , temp = list[i]; j = 2 * i; while (j <= v) { }

if(j < v && list[j] < list[j+1]) j++; /*若右孩子较大，则把j修改为右孩子的下标*/ if(temp < list[j]) {

list[i] = list[j]; /*将list[j]调到父亲的位置上*/

i = j; j = 2 * i; /*修改i和j的值，以便继续向下筛选*/ } else

break; /*筛选完成，终止循环*/

list[i] = temp; /*被筛结点的值放入最终位置*/ }

void heapSort(int list[], int n) {

int i = 0, temp = 0, count = 1; printf(\对序列进行堆排序：\\n\printf(\初始序列为：\printList(list, n);

for (i = n / 2; i > 0; i--)

heapAdjust(list, i, n); /*建立初始堆*/ printf(\建立的初始堆为：\printList(list, n); for(i = n ; i > 1; i--) {/*循环，完成堆排序*/

temp = list[1]; list[1] = list[i];

list[i] = temp; /*将第一个元素同当前区间内最后一个元素对换*/

45

}

}

heapAdjust(list, 1 , i-1); /*筛选出list[1]结点*/ printf(\第%d次排序结果：\printList(list, n);

/*生成待排序序列*/

void createList(int list[], int *n) {

int i = 1,a;

printf(\请输入待排序序列(长度小于50,以输入一个字符结束):\\n\ while(scanf(\ {

list[i] = a; i++; }

*n=i-1; getchar(); }

/*输出排序结果*/

void printList(int list[], int n) {

int i = 1;

for(; i <= n; i++) { printf(\

if(i % 10 ==0 && i != 0) printf(\

}

printf(\}

int main() {

int choice=1,length; while(choice!=0) {

printf(\

printf(\内部排序算法演示程序 *****\\n\printf(\直接插入排序 \\n\printf(\堆排序 \\n\printf(\退出\\n\printf(\请选择：\scanf(\getchar();

46

switch(choice)

{

case 1: { createList(slist, &length);

insertSort(slist, length); break;

} case 2:

{ }

createList(slist, &length); heapSort(slist, length); break;

default:choice=0; }

printf(\ }

return 0;

}

输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束） 1）直接插入排序运行结果（写出每一趟的状态）：

2）堆排序运行结果（写出每一趟的状态）：

2、在1题中补充希尔排序算法。 算法代码：

47

输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束） 运行结果（写出每一趟的状态）：

3、在1题中补充快速排序算法。 算法代码：

输入待排序序列：49 38 65 97 13 27 49（以输入一个字符作为结束） 运行结果（写出每一趟的状态）：

四、实验小结

请比较各个排序算法的性能。

五、教师评语

48

本文来源：https://www.bwwdw.com/article/929t.html