数据结构实验报告十—教学计划编制问题5篇

第一篇：数据结构实验报告十—教学计划编制问题

问题描述：

若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课时其先修课程已经被安排）。

基本要求：

（1）输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先修课的课程号。

（2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。

一、需求分析：

本程序需要基于图的基本操作来实现

二、概要设计：

抽象数据类型：

为实现上述功能需建立一个结点类，线性表类，图类。

算法的基本思想：

1、图的构建：

建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长度）。

2、Topsort算法：

先计算每个点的入度，保存在数组中。找到第一个入度为0的点，将该点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于输入顶点的个数，说明该图存在环。程序的流程

程序由三个模块组成：

输入模块：读入图的信息（顶点和边，用线性表进行存储）。处理模块：topsort算法。输出模块：将结果输出。

三、详细设计

算法的具体步骤： class Node{//结点类 public: string node;int position;//位置 Node* next;bool visit;//是否被访问

Node(){visit=false;next=NULL;position=0;node=' ';} };class Line{ //线性表类 public: int num;Node* head;Node* rear;Node* fence;Line(){num=0;head=fence=rear=new Node();} void insert(int v,string ch){ //插入元素

Node* current=new Node();

current->node=ch;

current->position=v;

fence->next=current;

fence=current;

num++;} };class Graph{ //图类 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点

string ch;

for(int i=0;i

cout<<“请输入顶点”<

cin>>ch;

line[i].head->node=ch;

line[i].head->position=i;

} } void pushEdge(){ //读入边

string ch1,ch2;

int pos1,pos2;

for(int i=0;i

{

cout<<“请输入边”<

cin>>ch1>>ch2;

for(int j=0;j

if(line[j].head->node==ch1)

pos1=j;//找到该字母对应的位置

if(line[j].head->node==ch2){

pos2=line[j].head->position;

break;

}

line[pos1].insert(pos2,ch2);

} } void topsort(){ //拓扑排序

int i;

int *d=new int[numVertex];

for(i=0;i

d[i]=0;//数组初始化

for(i=0;i

Node* p=line[i].head;

while(p->next!=NULL){

d[p->next->position]++;//计算每个点的入度

p=p->next;

}

} int top=-1,m=0,j,k;

for(i=0;i

if(d[i]==0){

d[i]=top;//找到第一个入度为0的点

top=i;

}

while(top!=-1){ j=top;top=d[top];

cout<node<<“ ”;m++;

Node* p=line[j].head;

while(p->next!=NULL){

k=p->next->position;

d[k]--;//当起点被删除，时后面的点的入度-1

if(d[k]==0){

d[k]=top;

top=k;

}

p=p->next;

}

} cout<

cout<<“网络存在回路”<>n>>m;Graph G(n,m);G.pushVertex();G.pushEdge();G.topsort();system(“pause”);return 0;}

四、调试分析

略。

五、测试结果

本实验的测试结果截图如下：

注：此处由于不会用文件流输入和输出，故在命令提示符上直接进行输入。

六、用户使用说明（可选）

1、本程序的运行环境为windows 操作系统，执行文件为Untitled1.exe 2、运行程序时

提示输入数据并且输入数据然后回车就可以继续输入相应数据，最后即可得到结果。

七、实验心得（可选）

1、本实验是在图的遍历问题的基础上做的，图的构建大部分是采用图的遍历问题中的代码（不过要将结点类中的char改为string型），自己另外写了topsort函数，就完成了整个程序。

2、topsort函数中一开始采用的方法是找到一个入度为0的点，完成相应的操作后，重新进行搜索，后来改进代码，先搜索入度为0的点后面连接的点，这样减少了算法复杂度。

附录（实验代码）：

#include #include using namespace std;class Node{//结点类 public: string node;int position;//位置 Node* next;bool visit;//是否被访问

Node* current=new Node();

current->node=ch;

current->position=v;

fence->next=current;

fence=current;

num++;} };class Graph{ //图类 private: int numVertex;int numEdge;Line* line;public: Graph(int v,int e){numVertex=v;numEdge=e;line =new Line[v];} void pushVertex(){ //读入点

string ch;

for(int i=0;i

cout<<“请输入顶点”<

cin>>ch;

line[i].head->node=ch;

line[i].head->position=i;

} } void pushEdge(){ //读入边

string ch1,ch2;

int pos1,pos2;

for(int i=0;i

{

cout<<“请输入边”<

cin>>ch1>>ch2;

for(int j=0;j

if(line[j].head->node==ch1)

pos1=j;//找到该字母对应的位置

if(line[j].head->node==ch2){

pos2=line[j].head->position;

break;

}

line[pos1].insert(pos2,ch2);

} } void topsort(){ //拓扑排序

int i;

int *d=new int[numVertex];

for(i=0;i

d[i]=0;//数组初始化

for(i=0;i

Node* p=line[i].head;

while(p->next!=NULL){

d[p->next->position]++;//计算每个点的入度

p=p->next;

}

} int top=-1,m=0,j,k;

for(i=0;i

if(d[i]==0){

d[i]=top;//找到第一个入度为0的点

top=i;

}

while(top!=-1){ j=top;top=d[top];

cout<node<<“ ”;m++;

Node* p=line[j].head;

while(p->next!=NULL){

k=p->next->position;

d[k]--;//当起点被删除，时后面的点的入度-1

if(d[k]==0){

d[k]=top;

top=k;

}

p=p->next;

}

} cout<

cout<<“网络存在回路”<>n>>m;Graph G(n,m);G.pushVertex();G.pushEdge();G.topsort();system(“pause”);return 0;}

第二篇：数据结构迷宫问题实验报告

《数据结构与算法设计》

迷宫问题实验报告

——实验二

专业：物联网工程班级：物联网1班学号：15180118 姓名：刘沛航

一、实验目的

本程序是利用非递归的方法求出一条走出迷宫的路径，并将路径输出。首先由用户输入一组二维数组来组成迷宫，确认后程序自动运行，当迷宫有完整路径可以通过时，以0和1所组成的迷宫形式输出，标记所走过的路径结束程序；当迷宫无路径时，提示输入错误结束程序。

二、实验内容

用一个m*m长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序对于任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

三、程序设计

1、概要设计

（1）设定栈的抽象数据类型定义

ADT Stack{

数据对象：D={ai|ai属于CharSet，i=1、2…n，n>=0} 数据关系：R={|ai-1,ai属于D，i=2,3,…n} 基本操作： InitStack(&S)

操作结果：构造一个空栈 Push（&S，e）

初始条件：栈已经存在

操作结果：将e所指向的数据加入到栈s中 Pop（&S,&e）

初始条件：栈已经存在

操作结果：若栈不为空，用e返回栈顶元素，并删除栈顶元素 Getpop（&S，&e）

初始条件：栈已经存在

操作结果：若栈不为空，用e返回栈顶元 StackEmpty(&S)

初始条件：栈已经存在

操作结果：判断栈是否为空。若栈为空，返回1，否则返回0 Destroy(&S)

初始条件：栈已经存在操作结果：销毁栈s }ADT Stack

（2）设定迷宫的抽象数据类型定义

ADT yanshu{

数据对象：D={ai,j|ai,j属于{‘ ’、‘*’、‘@’、‘#’},0<=i<=M,0<=j<=N} 数据关系：R={ROW,COL}

ROW={|ai-1,j,ai,j属于D，i=1,2,…M,j=0,1,…N} COL={|ai,j-1,ai,j属于D,i=0,1,…M，j=1,2,…N} 基本操作：

InitMaze(MazeType &maze, int a[][COL], int row, int col){

初始条件：二维数组int a[][COL],已经存在，其中第1至第m-1行，每行自第1到第n-1列的元素已经值，并以值0表示障碍，值1表示通路。

操作结果：构造迷宫的整形数组，以空白表示通路，字符‘0’表示障碍

在迷宫四周加上一圈障碍

MazePath（&maze）{

初始条件：迷宫maze已被赋值

操作结果：若迷宫maze中存在一条通路，则按如下规定改变maze的状态；以字符‘*’表示路径上的位置。字符‘@’表示‘死胡同’；否则迷宫的状态不变 }

PrintMaze（M）{ 初始条件：迷宫M已存在操作结果：以字符形式输出迷宫 }

}ADTmaze

（3）本程序包括三个模块

a、主程序模块 void main(){ 初始化；构造迷宫；迷宫求解；迷宫输出； }

b、栈模块——实现栈的抽象数据类型 c、迷宫模块——实现迷宫的抽象数据类型

2、详细设计

（1）坐标位置类型：

typedef struct{ int row;//迷宫中的行 int col;//......的列

}PosType;//坐标

（2）迷宫类型：

typedef struct{ int m,n;int arr[RANGE][RANGE];}MazeType;//迷宫类型

void InitMaze(MazeType &maze, int a[][COL], int row, int col)//设置迷宫的初值，包括边缘一圈的值

Bool MazePath(MazeType &maze,PosType start, PosType end)//求解迷宫maze中，从入口start到出口end的一条路径 //若存在，则返回true，否则返回false Void PrintMaze（MazeType maze）//将迷宫打印出来

（3）栈类型：

typedef struct{ int step;//当前位置在路径上的“序号” PosType seat;//当前的坐标位置

DirectiveType di;//往下一个坐标位置的方向 }SElemType;//栈的元素类型

typedef struct{ SElemType *base;SElemType *top;int stacksize;}SqStack;栈的基本操作设置如下： Void InitStack（SqStack & S）

//初始化，设S为空栈（S.top=NUL）Void DestroyStack(Stack &S)//销毁栈S，并释放空间

Void ClearStack（SqStack & S）//将栈S清空

Int StackLength（SqStack &S）//返回栈S的长度

Status StackEmpty（SqStack &S）？、若S为空栈（S.top==NULL），则返回TRUE，否则返回FALSE Statue GetTop（SqStack &S，SElemType e）

//r若栈S不空，则以e待会栈顶元素并返回TRUE，否则返回FALSE Statue Pop(SqStack&S，SElemType e)//若分配空间成功，则在S的栈顶插入新的栈顶元素s并返回TRUE //否则栈不变，并返回FALSE Statue Push(SqStack&S，SElemType &e)//若分配空间程控，则删除栈顶并以e带回其值，则返回TRUE //否则返回FALSE Void StackTraverse（SqStack &S，Status）（*Visit）（SElemType e））//从栈顶依次对S中的每个节点调用函数Visit 4求迷宫路径的伪码算法：

Status MazePath(MazeType &maze,PosType start, PosType end){ //求解迷宫maze中,从入口start到出口end的一条路径 InitStack(s);PosType curpos = start;int curstep = 1;//探索第一部 do{ if(Pass(maze,curpos)){ //如果当前位置可以通过,即是未曾走到的通道块 FootPrint(maze,curpos);//留下足迹

e = CreateSElem(curstep,curpos,1);//创建元素 Push(s,e);if(PosEquare(curpos,end))return TRUE;curpos =NextPos(curpos,1);//获得下一节点:当前位置的东邻 curstep++;//探索下一步 }else{ //当前位置不能通过 if(!StackEmpty(s)){ Pop(s,e);while(e.di==4 &&!StackEmpty(s)){ MarkPrint(maze,e.seat);Pop(s,e);//留下不能通过的标记,并退回步 } if(e.di<4){ e.di++;Push(s,e);//换一个方向探索

curpos = NextPos(e.seat,e.di);//设定当前位置是该方向上的相块 }//if }//if }//else }while(!StackEmpty(s));return FALSE;} //MazePath

四、程序调试分析

1.首先呢，想自己读入数据的，回来发现那样，很麻烦，所以还是事先定义一个迷宫。

2.栈的元素类型一开始有点迷惑，后来就解决了

3.本题中三个主要算法；InitMaze，MazePath和PrintMaze的时间复杂度均为O（m*n）本题的空间复杂度也是O（m*n）

五、用户使用说明

1．本程序运行在windows系列的操作系统下，执行文件为：Maze_Test.exe。

六、程序运行结果

1.建立迷宫： 2．通过1功能建立8*8的迷宫后，通过2功能继续建立迷宫内部：

通过建立自己设定单元数目建立迷宫内墙。3．通过3功能观察已建立的迷宫结构：

4．通过4功能确立迷宫起点和终点：

（此处像我们随机选择4,4和2,7分别为起点终点）

5．执行5功能，判断是否有路径走出迷宫：

这种情况无法走出迷宫。

我们再次观察图像设4,4和1,6分别为起点终点，再运行5功能。

观察到可以成功解开迷宫步数从1依次开始。

七、程序清单

#include #include #include #include // 迷宫坐标位置类型 typedef struct { int x;int y;}PosType;// 行值

// 列值

#define MAXLENGTH 25 // 设迷宫的最大行列为25

typedef int MazeType[MAXLENGTH][MAXLENGTH];// 迷宫数组[行][列]

typedef struct // 栈的元素类型

{ int ord;// 通道块在路径上的＂序号＂

PosType seat;// 通道块在迷宫中的＂坐标位置＂

int di;// 从此通道块走向下一通道块的＂方向＂(0～3表示东～北)}SElemType;

// 全局变量

MazeType m;// 迷宫数组

int curstep=1;// 当前足迹,初值为1

#define STACK_INIT_SIZE 10 // 存储空间初始分配量

#define STACKINCREMENT 2 // 存储空间分配增量

// 栈的顺序存储表示

typedef struct SqStack { SElemType *base;// 在栈构造之前和销毁之后，base的值为NULL

SElemType *top;

int stacksize;

// 构造一个空栈S int InitStack(SqStack *S){ // 为栈底分配一个指定大小的存储空间

(*S).base =(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)

(*S).top =(*S).base;

return 1;

// 栈底与栈顶相同表示一个空栈

(*S).stacksize = STACK_INIT_SIZE;exit(0);}SqStack;// 顺序栈

// 栈顶指针

// 当前已分配的存储空间，以元素为单位 }

// 若栈S为空栈（栈顶与栈底相同的），则返回1，否则返回0。int StackEmpty(SqStack S){ if(S.top == S.base)

else

}

// 插入元素e为新的栈顶元素。int Push(SqStack *S, SElemType e){ if((*S).top-(*S).base >=(*S).stacksize)// 栈满，追加存储空间

{

} *((*S).top)++=e;return 1;} // 若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0。int Pop(SqStack *S,SElemType *e){ if((*S).top ==(*S).base)

左

return 1;} // 定义墙元素值为0,可通过路径为1,不能通过路径为-1,通过路径为足迹 // 当迷宫m的b点的序号为1(可通过路径)，return 1;否则，return 0。int Pass(PosType b){

if(m[b.x][b.y]==1)

else return 0;return 1;return 0;*e = *--(*S).top;

// 这个等式的++ * 优先级相同，但是它们的运算方式，是自右向

(*S).base =(SElemType *)realloc((*S).base ，(*S).top =(*S).base+(*S).stacksize;(*S).stacksize += STACKINCREMENT;((*S).stacksize + STACKINCREMENT)* sizeof(SElemType));exit(0);if(!(*S).base)return 0;return 1;}

void FootPrint(PosType a)

// 使迷宫m的a点的序号变为足迹(curstep)，表示经过 { m[a.x][a.y]=curstep;}

// 根据当前位置及移动方向，返回下一位置

PosType NextPos(PosType c,int di){ PosType direc[4]={{0,1},{1,0},{0,-1},{-1,0}};// {行增量,列增量}

// 移动方向,依次为东南西北

c.x+=direc[di].x;c.y+=direc[di].y;return c;}

// 使迷宫m的b点的序号变为-1(不能通过的路径)void MarkPrint(PosType b){

m[b.x][b.y]=-1;} // 若迷宫maze中存在从入口start到出口end的通道，则求得一条

// 存放在栈中(从栈底到栈顶)，并返回1；否则返回0 int MazePath(PosType start,PosType end){

SqStack S;PosType curpos;SElemType e;

InitStack(&S);curpos=start;do {

if(Pass(curpos)){// 当前位置可以通过，即是未曾走到过的通道块

FootPrint(curpos);// 留下足迹

e.ord=curstep;e.seat.x=curpos.x;e.seat.y=curpos.y;e.di=0;Push(&S,e);// 入栈当前位置及状态

curstep++;// 足迹加1

if(curpos.x==end.x&&curpos.y==end.y)// 到达终点(出口)

} else return 1;curpos=NextPos(curpos,e.di);{// 当前位置不能通过

} if(!StackEmpty(S)){

} Pop(&S,&e);// 退栈到前一位置

curstep--;while(e.di==3&&!StackEmpty(S))// 前一位置处于最后一个方向(北){

} if(e.di<3)// 没到最后一个方向(北){

}

e.di++;// 换下一个方向探索

Push(&S,e);curstep++;// 设定当前位置是该新方向上的相邻块 curpos=NextPos(e.seat,e.di);

MarkPrint(e.seat);// 留下不能通过的标记(-1)Pop(&S,&e);// 退回一步

curstep--;}while(!StackEmpty(S));return 0;}

// 输出迷宫的结构

void Print(int x,int y){

int i,j;

for(i=0;i

} }

void main(){ PosType begin,end;int i,j,x,y,x1,y1,n,k;for(j=0;j

//清屏函数

printf(“***************************************************nnn”);printf(“

1请输入迷宫的行数,列数n”);printf(“

2请输入迷宫内墙单元数n”);printf(“

3迷宫结构如下n”);printf(“

4输入迷宫的起点和终点n”);printf(“

5输出结果n”);printf(“

0退出n”);printf(“nn请选择

”);scanf(“%d”,&n);switch(n){ case 1:{

printf(“请输入迷宫的行数,列数(包括外墙)：(空格隔开)”);

scanf(“%d%d”, &x, &y);

for(j=1;j

{

for(i=1;i

for(j=1;j

// 迷宫左边列的周边即左边墙

m[j][y-1]=0;// 迷宫右边列的周边即右边墙

for(i=0;i

// 迷宫上面行的周边即上边墙

m[x-1][i]=0;// 迷宫下面行的周边即下边墙

物

联

网

班

-15180118-刘沛

航

}

}break;

case 2:

{printf(“请输入迷宫内墙单元数：”);

scanf(“%d”,&j);

printf(“请依次输入迷宫内墙每个单元的行数,列数：(空格隔开)n”);

for(i=1;i<=j;i++)

{ scanf(“%d%d”,&x1,&y1);

} m[x1][y1]=0;

}break;

case 3:{ Print(x,y);printf(“刘沛航建立的迷宫，定义墙元素值为0,可通过路径为1，输入0退出”);scanf(“%d”,&k);}break;

case 4:{ printf(“请输入起点的行数,列数：（空格隔开）”);

scanf(“%d%d”,&begin.x,&begin.y);

printf(“请输入终点的行数,列数：（空格隔开）”);

scanf(“%d%d”,&end.x,&end.y);}break;

case 5:{

if(MazePath(begin,end))// 求得一条通路

{

} else printf(“此迷宫没有从入口到出口的路径，谢谢使用刘沛航的程序n”);printf(“输入0退出”);scanf(“%d”,&k);}break;} }while(n!=0);} printf(“此迷宫从入口到出口的一条路径如下，谢谢使用刘沛航的程序:n”);Print(x,y);// 输出此通路

第三篇：数据结构实验报告

注意：实验结束后提交一份实验报告电子文档

电子文档命名为“学号+姓名”，如：E01214058宋思怡

《数据结构》实验报告

（一）学号：姓名：专业年级：

实验名称：线性表

实验日期：2014年4月14日

实验目的：

1、熟悉线性表的定义及其顺序和链式存储结构；

2、熟练掌握线性表在顺序存储结构上实现基本操作的方法；

3、熟练掌握在各种链表结构中实现线性表基本操作的方法；

4、掌握用 C/C++语言调试程序的基本方法。

实验内容：

一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能：

（1）初始化顺序表L；

（2）依次在L尾部插入元素-1,21,13,24,8；

（3）输出顺序表L；

（4）输出顺序表L长度；

（5）判断顺序表L是否为空；

（6）输出顺序表L的第3个元素；

（7）输出元素24的位置；

（8）在L的第4个元素前插入元素0；

（9）输出顺序表L；

（10）删除L的第5个元素；

（11）输出顺序表L。

源代码

调试分析（给出运行结果界面）

二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：

„„„„

小结或讨论:

（1）实验中遇到的问题和解决方法

（2）实验中没有解决的问题

（3）体会和提高

第四篇：数据结构实验报告

南京信息工程大学实验（实习）报告

实验（实习）名称数据结构实验（实习）日期 2011-11-2得分指导教师周素萍

系公共管理系专业信息管理与信息系统年级10级班次1姓名常玲学号2010230700

3实验一顺序表的基本操作及C语言实现

【实验目的】

1、顺序表的基本操作及 C 语言实现

【实验要求】

1、用 C 语言建立自己的线性表结构的程序库，实现顺序表的基本操作。

2、对线性表表示的集合，集合数据由用户从键盘输入（数据类型为整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并的结果存储在一个新的线性表集合中，并输出。

【实验内容】

1、根据教材定义的顺序表机构，用 C 语言实现顺序表结构的创建、插入、删除、查找等操作；

2、利用上述顺序表操作实现如下程序：建立两个顺序表表示的集合（集合中无重

复的元素），并求这样的两个集合的并。

【实验结果】

[实验数据、结果、遇到的问题及解决]

一． Status InsertOrderList(SqList &va,ElemType x)

{

}

二． Status DeleteK(SqList &a,int i,int k)

{//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x

}

//注意i的编号从0开始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK;

三．// 将合并逆置后的结果放在C表中，并删除B表

Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C)

{

LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驱指针 // 保存pb的前驱指针 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data

data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa;

}

} pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb;

顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。

优点：简单，数据元素的提取速度快；

缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n）

求两个集合的并集

该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。

第五篇：数据结构实验报告

实验报告4 排序

一、实验目的

1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。

2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。

3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。

二、实验要求及内容

要求编写的程序所能实现的功能包括：

1、从键盘输入要排序的一组元素的总个数

2、从键盘依次输入要排序的元素值

3、对输入的元素进行快速排序

4、对输入的元素进行折半插入排序

三、实验代码及相关注释

#include using namespace std;#include “malloc.h”

typedef struct { int key;}RedType;

typedef struct { RedType r[100];int length;}SqList;

//1 快速排序的结构体

typedef struct {

int data[100];

int last;}Sequenlist;//2 折半插入排序的结构体

int Partition(SqList &L, int low, int high)

//1 寻找基准

{

L.r[0]=L.r[low];//子表的第一个记录作基准对象

int pivotkey = L.r[low].key;//基准对象关键字 while(low

while(low= pivotkey)--high;

L.r[low] = L.r[high];//小于基准对象的移到区间的左侧

while(low

L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 }

L.r[low] = L.r[0];return low;}

void QuickSort(SqList &L, int low, int high)

//1 快速排序 { //在序列low-high中递归地进行快速排序

if(low < high)

{

int pivotloc= Partition(L, low, high);

//寻找基准

QuickSort(L, low, pivotloc-1);//对左序列同样递归处理

QuickSort(L, pivotloc+1, high);//对右序列同样递归处理

} }

Sequenlist *Sqlset()

//2 输入要折半插入排序的一组元素

{

Sequenlist *L;

int i;

L=(Sequenlist *)malloc(sizeof(Sequenlist));

L->last=0;

cout<<“请输入要排序的所有元素的总个数：”;

cin>>i;

cout<

cout<<“请依次输入所有元素的值：”;

if(i>0)

{

for(L->last=1;L->last<=i;L->last++)

cin>>L->data[L->last];

L->last--;

}

return(L);}

middlesort(Sequenlist *L)

//2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){

L->data[0]=L->data[i];

low=1;

high=i-1;

while(low<=high)

{

mid=(low+high)/2;

if(L->data[0]data[mid])

high=mid-1;//插入点在前半区

else

low=mid+1;//插入点在后半区

}

for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移

L->data[high+1]=L->data[0];//插入 } return 0;}

int main(){ gg: cout<<“请选择功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout<

if(m==1){ SqList L;int n;cout<<“请输入要排序的所有元素的总个数：”;cin>>n;cout<

cin>>L.r[i].key;

} cout<

QuickSort(L,1,L.length);

for(int j=1;j<=L.length;j++)

{

cout<

}

cout<

}

if(m==2){

Sequenlist *L;

int i;

L=Sqlset();

cout<

middlesort(L);

cout<<“折半插入排序后为：”;

for(i=1;i<=L->last;i++)

{

cout<data[i]<<“ ”;

}

cout<

goto gg;}

if(m==3){

exit(0);

cout<

四、重要函数功能说明

1、Sequenlist *Sqlset()

输入要折半插入排序的一组元素

2、int Partition(SqList &L, int low, int high)

寻找快速排序的基准

3、void QuickSort(SqList &L, int low, int high)

快速排序

4、middlesort(Sequenlist *L)

折半插入排序

五、程序运行结果

下图仅为分别排序一次，可多次排序，后面有相关截图：

六、实验中遇到的问题、解决及体会

1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。

运行程序错误截图：

2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。

修改程序前两个运行结果截图

（两个程序，调试运行两次，每次只能进行一次排序）

1、快速排序程序运行结果截图：

2、折半插入排序程序结果截图：

程序重要模块修改截图：

修改程序后运行截图：

（一个程序，调试运行一次，可多次进行不同序列的不同排序）

数据结构实验报告十—教学计划编制问题5篇

相关范文推荐