01510800班 郭哲 学号:20080259
实验报告
01510800班
郭哲
学号:20080259
- 1 -
01510800班 郭哲 学号:20080259
实验名称:拓扑排序;
实验原理:利用拓扑排序的原理,读入图,并将图按照拓扑排序的顺序输出;
源代码如下:
#include "stdio.h"
#include "malloc.h"
#include "string.h"
#define MAX 100
#define OK 1
#define ERROR 0
typedef int Status;
#define N 7
typedef struct
{ int * base;
int front, rear;
} Queue;
Status InitQueue ( Queue * q )
{ q->base = (int *)malloc( MAX*sizeof(int) );
q->front = q->rear = 0;
return OK;
}
Status QueueEmpty ( Queue q )
{ return q.front == q.rear;}
Status EnQueue ( Queue * q, int e )
{
if ( (q->rear+1)%MAX==q->front ) return ERROR ;
q->base[q->rear] = e ;
q->rear = (q->rear+1)%MAX;
return OK;
}
Status DeQueue ( Queue * q, int * e )
{
if ( q->rear==q->front ) return ERROR ;
*e = q->base[q->front] ;
q->front = (q->front+1)%MAX;
return OK;
}
int indegree(char b[])
{
int i;
int x;
x=0;
for(i=0;i<N;i++)
x=x+b[i]-'0';
return x;
}
- 2 -
01510800班 郭哲 学号:20080259
int main()
{
FILE * fp;
char filename[20];
char a[N][N],b[N];
int Ru,c[N];
int i,j,k,ch,e,p;
int flag,pflag,temp1=0,temp=0;
Queue q;
InitQueue (&q);
for(i=0;i<N;i++)
c[i]=0;
printf ("Please enter filename:\n");
scanf ("%s",filename);
if ((fp=fopen (filename,"r"))==NULL)
{
printf("file open error.\n");
}
for(i=0;i<N;i++)
{ j=0;
while (j<N)
{
if ((ch=fgetc(fp))!=EOF&&(ch=='0'||ch=='1')) {
a[i][j]=ch;
j++;
}
}
}
for(j=0;j<N;j++)
{
for(i=0,k=0;i<N,k<N;i++,k++)
b[k]=a[i][j];
Ru=indegree(b);
if(Ru==0)
EnQueue ( &q, j+1 );
}
while(!QueueEmpty(q)&&p<N)
{
DeQueue ( &q, &e );
flag=1;temp=0;
while(flag&&temp<N)
{
if(e==c[temp])
flag=0;
temp++;
}
if(flag)
{
for(p=0;c[p]!=0&&p<N;p++) ;
c[p]=e;
- 3 -
01510800班 郭哲 学号:20080259
} } for(j=0;j<N&&flag;j++) { if(a[e-1][j]>'0') a[e-1][j]-=1; } for(j=0;j<N;j++) { for(i=0,k=0;i<N,k<N;i++,k++) b[k]=a[i][j]; Ru=indegree(b); if(Ru==0) { pflag=1,temp1=0; while( pflag&&temp1<N) { if(c[temp1]==j+1) pflag=0; temp1++; } if(pflag) EnQueue ( &q, j+1 ); } } } for(i=0;i<N;i++) printf("%4d",c[i]); printf("\n"); return 0;
测试输入的图为: ① →②→③→④→⑦
↓ ↓
⑥ ⑤
测试结果为:
Please enter filename:
1.txt
1 2 3 6 4 5 7 Press any key to continue
- 4 -
课程名称: 数据结构 实验名称: 实验十 内部排序 班 级: 102012 学生姓名: 学号:
指导教师评定: 签 名:
题目:编程分别实现快速排序算法、堆排序算法。
一、 需求分析
1. 用户可以根据自己的需求输入一个顺序表。
2. 通过利用快速排序法按非递减排序已有的顺序表。
3. 通过利用堆排序按非递减排序已有的顺序表。
4. 程序执行的命令包括:
(1)创建顺序表 (2)输出顺序表 (3)快速排序算法排序 (4) 堆排序算法排序
二、概要设计
⒈ 为实现上述算法,需要顺序表的抽象数据类型:
ADT sqlist {
数据对象D:D是具有相同特征的数据元素的集合。各数据元素均含有类型相同,可
唯一标识数据元素的关键字。
数据关系R:数据元素同属一个集合。
基本操作P:
Creatsqlist(&l)
操作结果:构造一个具有n个数据元素的顺序表l。
ListLength(L)
初始条件:线性表L已经存在
操作结果:返回L中数据元素的个数。
destroylist(&l)
初始条件:顺序表l存在。
操作结果:销毁顺序表l。
displaylist(l)
初始条件:顺序表l存在。
操作结果:显示顺序表l。
quicksort (&l)
初始条件:顺序表l存在。
操作结果:通过快速排序得到一个有序的顺序表l。
heapsort (&l)
初始条件:顺序表l存在。
操作结果:通过堆排序得到一个有序的顺序表l。
heapadjust (&l,s,m)
1
初始条件:顺序表l存在。
操作结果:调整h->r[s]的关键字,使h->r[s]成为一个大顶堆 partion (&l,&low,high)
初始条件:顺序表l存在。
操作结果:交换顺序表中子表r[low...high]的记录,使枢轴记录到
位,并返回其所在的位置。
}ADT sqlist
2. 本程序有三个模块:
⑴ 主程序模块
main(){
初始化;
{
接受命令;
显示结果;
}
}
⑵ 创建顺序表的模块:主要建立一个顺序表;
⑶快速排序模块:得到一个有序的顺序表;
(4)输出顺序表模块:显示已创建顺序表;
(5)堆排序模块:得到一个有序的顺序表。
三、详细设计
⒈元素类型,结点类型
typedef struct
{
int key;
}keytype;
typedef struct
{ keytype r[100];
int length;
}sqlist;
2.对抽象数据类型中的部分基本操作的伪码算法如下:
/*创建顺序表*/
void creat(sqlist *l)
{
int i,key;
printf("please intput it's length:");
scanf("%d",&l->length);
printf("\n\nplease intput %d data\n",l->length);
for(i=1;i<=l->length;i++)
{
scanf("%d",&key);
l->r[i].key=key;
2
}
}
/*交换顺序表中子表r[low...high]的记录,使枢轴记录到位,并返回其所在的位置*/ int partion(sqlist *l,int low,int high)
{ int pivotkey;
l->r[0]=l->r[low];
pivotkey=l->r[low].key;
while(low<high)
{ while(low<high&&l->r[high].key>=pivotkey)
--high;
l->r[low]=l->r[high];
while(low<high&&l->r[low].key<=pivotkey)
++low;
l->r[high]=l->r[low];
}
l->r[low]=l->r[0];
return low;
}
/*快速排序*/
void Qsort(sqlist *l,int low,int high)
{ int pivotloc;
if(low<high)
{ pivotloc=partion(l,low,high);
Qsort(l,low,pivotloc-1);
Qsort(l,pivotloc+1,high);
}
}
/*快速排序*/
void quicksort(sqlist *l)
{
Qsort(l,1,l->length);
}
/*显示顺序表*/
void display(sqlist *l)
{ int i;
for(i=1;i<=l->length;i++)
printf("%-4.2d",i);
printf("\n");
3
for(i=1;i<=2*l->length;i++)
printf("--");
printf("\n");
for(i=1;i<=l->length;i++)
printf("%-4.2d",l->r[i].key);
}
/*调整h->r[s]的关键字,使h->r[s]成为一个大顶堆*/ void heapadjust(sqlist *h,int s,int m)
{ keytype rc;
int j;
rc=h->r[s];
for(j=2*s;j<=m;j*=2)
{ if(j<m&&h->r[j].key<h->r[j+1].key) ++j;
if(rc.key>=h->r[j].key) break;
h->r[s]=h->r[j];
s=j;
}
h->r[s]=rc;
}
/*对顺序表h进行堆排序*/
void heapsort(sqlist *h)
{ keytype rc;int i;
for(i=h->length/2;i>0;--i)
heapadjust(h,i,h->length);
for(i=h->length;i>1;--i)
{ rc=h->r[1];
h->r[1]=h->r[i];
h->r[i]=rc;
heapadjust(h,1,i-1);
}
}
3.主函数和其他函数的伪码算法
/*主函数*/
void main()
{ sqlist t;int i;
creat(&t);
Qsort(&t,1,t.length);
4
printf("\n\n");
printf("quicksort means:\n");
display(&t);
heapsort(&t);
printf("\n");
printf("\nheapsort means:\n");
display(&t);
getch();
}
4 函数调用关系
main
heapadjust partion
四、调试分析
⒈开始的时候在编写快速排序算法的时候没有设置用子表的第一个记录作枢轴记录导致没
有得到正确的结果。
⒉在l->r[low]=l->r[high];语句进行交换时,写成l->r[low].key=l->r[high].key,一直
没有找到错误的地方,在看了参考资料后才发现是这里错了。
3. 算法的时空分析
各操作的算法时间复杂度比较合理
creat, partion,display为O(n) Qsort ,heapadjust,heapsort为 O(nlogn)
注:n为哈希表的长度。
5.本次实验采用数据抽象的程序设计方法,将程序化为三层次结构,设计时思路清晰,使
调试也较顺利,各模块有较好的可重用性。
五、用户手册
⒈ 本程序的运行环境为windows xp操作系统,并且在TC2.0中运行,执行文件为Exp10.c;
2. 进入演示程序后,完成编译,再点击超级工具集里的中文DOS环境运行选项,进入DOS
环境中,用户根据需求键入相应的数据,可以看到相应的结果。
六、测试结果
在dos下输入数据元素:
98 23 10 56 21 23 01 64 74 34
排序后的结果是:
01 10 21 23 23 34 56 64 74 98
则在dos界面输入如图所示:
5
七、附录:源程序
#include<stdio.h>
typedef struct
{
int key;
}keytype;
typedef struct
{ keytype r[100];
int length;
}sqlist;
/*创建顺序表*/
void creat(sqlist *l)
{
int i,key;
printf("please intput it's length:");
scanf("%d",&l->length);
printf("\n\nplease intput %d data\n",l->length);
for(i=1;i<=l->length;i++)
{
scanf("%d",&key);
l->r[i].key=key;
}
}
/*交换顺序表中子表r[low...high]的记录,使枢轴记录到位,并返回其所在的位置*/ int partion(sqlist *l,int low,int high)
{ int pivotkey;
l->r[0]=l->r[low];
pivotkey=l->r[low].key;
while(low<high)
{ while(low<high&&l->r[high].key>=pivotkey)
6
--high;
l->r[low]=l->r[high];
while(low<high&&l->r[low].key<=pivotkey) ++low;
l->r[high]=l->r[low];
}
l->r[low]=l->r[0];
return low;
}
/*快速排序*/
void Qsort(sqlist *l,int low,int high)
{ int pivotloc;
if(low<high)
{ pivotloc=partion(l,low,high);
Qsort(l,low,pivotloc-1);
Qsort(l,pivotloc+1,high);
}
}
/*显示顺序表*/
void display(sqlist *l)
{ int i;
for(i=1;i<=l->length;i++)
printf("%-4.2d",i);
printf("\n");
for(i=1;i<=2*l->length;i++)
printf("--");
printf("\n");
for(i=1;i<=l->length;i++)
printf("%-4.2d",l->r[i].key);
}
/*调整h->r[s]的关键字,使h->r[s]成为一个大顶堆*/ void heapadjust(sqlist *h,int s,int m)
{ keytype rc;
int j;
rc=h->r[s];
for(j=2*s;j<=m;j*=2)
{ if(j<m&&h->r[j].key<h->r[j+1].key) ++j;
if(rc.key>=h->r[j].key) break;
h->r[s]=h->r[j];
s=j;
}
h->r[s]=rc;
}
7
/*对顺序表h进行堆排序*/
void heapsort(sqlist *h)
{ keytype rc;int i;
for(i=h->length/2;i>0;--i) heapadjust(h,i,h->length); for(i=h->length;i>1;--i) { rc=h->r[1];
h->r[1]=h->r[i];
h->r[i]=rc;
heapadjust(h,1,i-1); }
}
/*主函数*/
void main()
{ sqlist t;int i;
creat(&t);
Qsort(&t,1,t.length);
printf("\n\n");
printf("quicksort means:\n"); display(&t);
heapsort(&t);
printf("\n");
printf("\nheapsort means:\n"); display(&t);
getch();
}
8
数据结构实验报告排序实验题目输入十个数从插入排序快速排序选择排序三类算法中各选一种编程实现实验所使用的数据结构内容及编程思路1插入…
数据结构课程设计报告实验五排序一需求分析本演示程序用C60编写完成各种排序的实现对输入的一组数字实现不同的排序方法对其由小到大顺序…
1实验要求实验目的学习实现对比各种排序算法掌握各种排序算法的优劣以及各种算法使用的情况实验内容使用简单数组实现下面各种排序算法并进…
实验八排序一实验目的1熟悉掌握教材中所介绍的几种排序方法2学会分析各种内排序算法的性能二实验内容1随机产生20位整数2输入序列编写…
数据结构实验报告实验四排序一需求分析一实验目的1掌握插入排序算法直接插入希尔排序2掌握交换排序算法冒泡排序快速排序3掌握选择排序算…
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名李威威准考证号所属地市焦作市实验地点焦作大学实验实训中心实验日期…
河南省高等教育自学考试实验报告册计算机及应用专业本科段数据结构姓名准考证号所属地市实验地点实验日期2实验总成绩指导教师签名实验单位…
1实验要求实验目的学习实现对比各种排序算法掌握各种排序算法的优劣以及各种算法使用的情况实验内容使用简单数组实现下面各种排序算法并进…
计算机科学与技术系实验报告专业名称计算机科学与技术课程名称数据结构与算法项目名称排序班级计科一班学号姓名实验日期格式要求实验报告注…
一实验目的1了解内排序都是在内存中进行的2为了提高数据的查找速度需要对数据进行排序3掌握内排序的方法二实验内容1设计一个程序exp…