数据结构课程设计
说明书
学 院： 信息科学与工程学院
班 级： 软件11-3
完成人：姓名：张金旺 学号：1101051831
指导教师： 贾瑞生
山 东 科 技 大 学
20##年12月27日
课 程 设 计 任 务 书
一、课程设计题目： 数据结构（c语言）实验报告
二、课程设计应解决的主要问题：
（1） 约瑟夫环
（2） 马踏棋盘
（3） 稀疏矩阵运算器
（4） 教学计划编制问题
（5） 哈希表设计
（
三、任务发出日期： 20##-9-20 课程设计完成日期： 20##-1-16
指导教师对课程设计的评价
成绩：
指导教师签字：
年 月 日
目 录
1 约瑟夫环……………………………………………………5
1.1需求分析…………………………………………………………5
1.2概要设计…………………………………………………………5
1.3详细设计…………………………………………………………5
1.4调试分析…………………………………………………………9
1.5 用户手册…………………………………………………………9
1.6运行结果…………………………………………………………9
1.7实验心得…………………………………………………………10
1.8参考书籍…………………………………………………………10
2 马踏棋盘…………………………………………………………11
2.1需求分析…………………………………………………………11
2.2概要设计…………………………………………………………11
2.3详细设计…………………………………………………………12
2.4调试分析…………………………………………………………20
2.5用户手册…………………………………………………………20
2.6运行结果…………………………………………………………20
2.7实验心得…………………………………………………………21
2.8参考书籍…………………………………………………………22
3 稀疏矩阵……………………………………………………………23
3.1需求分析…………………………………………………………23
3.2概要设计…………………………………………………………23
3.3详细设计…………………………………………………………24
3.4调试分析…………………………………………………………39
3.5用户手册…………………………………………………………40
3.6运行结果…………………………………………………………40
3.7实验心得…………………………………………………………41
3.8参考书籍…………………………………………………………41
4 教学计划编制问题………………………………………………43
4.1需求分析…………………………………………………………43
4.2概要设计…………………………………………………………44
4.3详细设计…………………………………………………………44
4.4调试分析…………………………………………………………55
4.5用户手册…………………………………………………………55
4.6运行结果…………………………………………………………55
4.7实验心得…………………………………………………………57
4.8参考书籍…………………………………………………………58
5 哈希表设计………………………………………………………59
5.1需求分析…………………………………………………………59
5.2概要设计…………………………………………………………59
5.3详细设计…………………………………………………………62
5.4调试分析…………………………………………………………71
5.5用户手册…………………………………………………………72
5.6运行结果…………………………………………………………72
5.7实验心得…………………………………………………………73
5.8参考书籍…………………………………………………………74
实习一约瑟夫环
一、需求分析
1． 本演示程序中，人数n应为任意的，首先应输入一个值赋给初始报数上限m，程序应能自动保存出列人的序号和将出列的人所持的密码赋给m，再次作为报数上限，如此循环，直至所有人都出列为止。
2． 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应数据（即每个人所持的密码），每个人的序号由程序自动分配。
3． 程序执行的命令包括：
（1）构造链表；（2）输入数据；（3）执行报数，储存出列人的序号，删除出列人的信息以及把出列人的密码赋给m；（4）结束。
4． 测试数据
n＝7，7个人的密码依次为：3，1，7，2，4，8，4，首先m值为6，则这正确的出列顺序为6，1，4，7，2，3，5。
二、概要设计
为了实现上述操作，应以单向循环链表为存储结构。
1、基本操作：
Creat( );
操作结果：构造空链表，若成功就初始化每个人的相关信息
Delet();
操作结果：释放指向出列的人的结点，并重新报数
2． 本程序包含三个模块：
（1） 主程序模块；
（2） 构造链表并输入每个人信息模块；
（3） 释放结点模块；
三、详细设计
1． 元素类型，结点类型和指针类型：
typedef struct node
{
int key;
int num;
struct node *next;
}LNode, *LinkList;
2、 每个模块的分析：
（1）构造链表并输入每个人信息模块；
LinkList Creat(int n) //构造循环链表
{
int i;
LinkList p, q, h;
h=(LinkList)malloc(sizeof(LNode)); //设置头结点
scanf("%d",&h->key); //将第一个人的信息放在头结点中
h->num=1;
q=h; //构造剩余节点
for(i=2;i<=n;i++)
{
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->key);
p->num=i;
q->next=p;
p->next=NULL; //插入
q=p;
}
q->next=h;
return h;
}
（2）.释放结点模块；
void Delet(LinkList h, int n, int m)
{
int i;
LinkList p,q;
q=h;
while(q->next!=h) q=q->next; //使q指向n号的人
while(n)
{
for(i=1;i<m;i++) //使q指向报m-1的人
q=q->next;
p=q->next; //p为报m的人
printf("%d ",p->num);
m=p->key; //获取新m值
q->next=p->next; //删除p节点
free(p);
n--;
}
}
(3)主程序模块
void main()
{
int n, m;
LinkList h;
printf("请输入总人数(n<=30)：n=");
scanf("%d",&n);
printf("请输入初始报数上限值：m=");
scanf("%d",&m);
printf("请分别输入%d个人的密码(用空格隔开)：",n);
h=Creat(n);
printf("出列顺序为：");
Delet(h, n, m);
printf("\n");
}
（4） 完整原代码
#include "stdlib.h"
#include "stdio.h"
typedef struct node
{
int key;
int num;
struct node *next;
}LNode, *LinkList;
LinkList Creat(int n) //构造循环链表
{
int i;
LinkList p, q, h;
h=(LinkList)malloc(sizeof(LNode)); //设置头结点
scanf("%d",&h->key); //将第一个人的信息放在头结点中
h->num=1;
q=h; //构造剩余节点
for(i=2;i<=n;i++)
{
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->key);
p->num=i;
q->next=p;
p->next=NULL; //插入
q=p;
}
q->next=h;
return h;
}
void Delet(LinkList h, int n, int m)
{
int i;
LinkList p,q;
q=h;
while(q->next!=h) q=q->next; //使q指向n号的人
while(n)
{
for(i=1;i<m;i++) //使q指向报m-1的人
q=q->next;
p=q->next; //p为报m的人
printf("%d ",p->num);
m=p->key; //获取新m值
q->next=p->next; //删除p节点
free(p);
n--;
}
}
void main()
{
int n, m;
LinkList h;
printf("请输入总人数(n<=30)：n=");
scanf("%d",&n);
printf("请输入初始报数上限值：m=");
scanf("%d",&m);
printf("请分别输入%d个人的密码(用空格隔开)：",n);
h=Creat(n);
printf("出列顺序为：");
Delet(h, n, m);
printf("\n");
}
四、调试分析
在执行报数输出函数时，报到该结点时应从到循环链表从单循环链表删除，使p指针继续指向下一个结点。但在运行时出现错误，通过调试知道要从链表上删除一个结点后应释放该结点空间即在函数中应填上free(p); p=q->next;
五、用户手册
（1）本程序的运行环境为vc6
（2）进入程序后会依次提示信息
请输入总人数（n<30）
请输入初始报数上限值
请分别输入7个人的密码（注意：用空格隔开）
六、课程设计总结
做这次数据结构实验不仅让我对这段时间内所学的知识有了更好的理解而且对自己的编程能力也有所提高。发现在解决问题的过程中还有很多不会的地方在编程和写报告的过程中曾多次遇到各种各样的问题发现自己的编程能力亟待提高。通过与同学们的交流以及自己思考最终得到解决并顺利完成了此次作业
七、测试结果
当输入m＝6，n＝7，每个人所持密码一次为：3，1，7，2，4，8，4时，则输出正确的出列顺序为：6，1，4，7，2，3，5。
八、参考书目
（1）数据结构，汤文兵，华东理工大学出版社
（2） 数据结构——习题与解析，李春葆，清华大学出版社
（3） C语言课程设计案例精编，郭翠英，中国水利出版社
（4）数据结构（c语言版） 严蔚敏 吴伟民 编著 清华大学出版社
实习二马踏棋盘
一、 需求分析
1.将马随机放在国际象棋的8×8棋盘Board[8][8]的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，…，64依次填入一个8×8的方阵，输出之。
2. 演示程序以用户与计算机交互方式执行，即在计算机终端上显示"提示信息"之后，由用户在键盘上输入演示程序中规定的运算命令；设计思路按照顺时针顺序，每次产生一个新的位置点，并验证此位置点的可用性，需要考虑的问题包括是否超出棋盘和此点已经走过与否，如新位置点可用，并执行下一步，每次按照上一位置点生成新位置点。如下一个位置点走不下去，进行回溯。
二、 概要设计
（1）、顺序栈的抽象数据类型定义：
ADT Stack{
数据对象：D={ai| ai∈（0，1，…，9），i=0,1，2，…，n，n≥0}
数据关系：R={< ai-1, ai >| ai-1, ai∈D,i=1,2，…，n}
} ADT Stack
（2）本程序包含三个模块：
1、主程序模块：
void main(){
定义变量；
接受命令；
处理命令；
退出；
}
2、起始坐标函数模块——马儿在棋盘上的起始位置；
3、探寻路径函数模块——马儿每个方向进行尝试，直到试完整个棋盘；
4、输出路径函数模块——输出马儿行走的路径；
各模块之间的调用关系：
输入的初始位置是否正确
否
是
三、详细设计
（1）、定义头文件和预定义
#include<stdio.h>
#define MAXSIZE 100
#define N 8
（2）、数据类型定义
int board[8][8]; //定义棋盘
int Htry1[8]={1,-1,-2,2,2,1,-1,-2};
/*存储马各个出口位置相对当前位置行下标的增量数组*/
int Htry2[8]={2,-2,1,1,-1,-2,2,-1};
/*存储马各个出口位置相对当前位置列下标的增量数组*/
struct Stack{ //定义栈类型
int i; //行坐标
int j; //列坐标
int director; //存储方向
}stack[MAXSIZE]; //定义一个栈数组
int top=-1; //栈指针
（3）、函数声明
void InitLocation(int xi,int yi); //马儿在棋盘上的起始位置坐标
int TryPath(int i,int j); //马儿每个方向进行尝试，直到试完整个棋盘
void Display(); //输出马儿行走的路径
（4）、起始坐标函数模块
void InitLocation(int xi,int yi)
{
int x,y; //定义棋盘的横纵坐标变量
top++; //栈指针指向第一个栈首
stack[top].i=xi; //将起始位置的横坐标进栈
stack[top].j=yi; //将起始位置的纵坐标进栈
stack[top].director=-1; //将起始位置的尝试方向赋初值
board[xi][yi]=top+1; //标记棋盘
x=stack[top].i; //将起始位置的横坐标赋给棋盘的横坐标
y=stack[top].j; //将起始位置的纵坐标赋给棋盘的纵坐标
if(TryPath(x,y)) //调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返回0
Display(); //输出马儿的行走路径
else
printf("无解");
}
（5）、探寻路径函数模块
int TryPath(int i,int j)
{
int find,director,number,min; //定义几个临时变量
int i1,j1,h,k,s; //定义几个临时变量
int a[8],b1[8],b2[8],d[8]; //定义几个临时数组
while(top>-1) //栈不空时循环
{
for(h=0;h<8;h++) //用数组a[8]记录当前位置的下一个位置的可行路径的条数
{
number=0;
i=stack[top].i+Htry1[h];
j=stack[top].j+Htry2[h];
b1[h]=i;
b2[h]=j;
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置
{
for(k=0;k<8;k++)
{
i1=b1[h]+Htry1[k];
j1=b2[h]+Htry2[k];
if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8)
//如果找到下一位置
number++; //记录条数
}
a[h]=number; //将条数存入数组a[8]中
}
}
for(h=0;h<8;h++) //根据可行路径条数小到大按下表排序放入数组d[8]中
{
min=9;
for(k=0;k<8;k++)
if(min>a[k])
{
min=a[k];
d[h]=k; //将下表存入数组d[8]中
s=k;
}
a[s]=9;
}
director=stack[top].director;
if(top>=63) //如果走完整个棋盘返回1
return (1);
find=0; //表示没有找到下一个位置
for(h=director+1;h<8;h++) //向八个方向进行探寻
{
i=stack[top].i+Htry1[d[h]];
j=stack[top].j+Htry2[d[h]];
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8) //如果找到下一位置
{
find=1; //表示找到下一个位置
break;
}
}
if(find==1) //如果找到下一个位置进栈
{
stack[top].director=director; //存储栈结点的方向
top++; //栈指针前移进栈
stack[top].i=i;
stack[top].j=j;
stack[top].director=-1; //重新初始化下一栈结点的尝试方向
board[i][j]=top+1; //标记棋盘
}
else //否则退栈
{
board[stack[top].i][stack[top].j]=0; //清除棋盘的标记
top--; //栈指针前移退栈
}
}
return (0);
}
（6）输出路径函数模块
void Display()
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("\t%d ",board[i][j]); //输出马儿在棋盘上走过的路径
printf("\n\n");
}
printf("\n");
}
（5）主程序模块
void main()
{
int i,j;
int x,y;
for(i=0;i<N;i++) //初始化棋盘
for(j=0;j<N;j++)
board[i][j]=0;
for(;;)
{
printf("Please input importpoint(1<=x<=8 and 1<=y<=8)\n");
printf("Input x = ");
scanf("%d",&x); //输入起始位置的横坐标
printf("Input y = ");
scanf("%d",&y); //输入起始位置的纵坐标
if(x>=1&&x<=8&&y>=1&&y<=8)break;
printf("Your input is worng!!!\n");
}
printf("begin with %d board:\n\n", 8*(x-1)+y);
InitLocation(x-1,y-1); //调用起始坐标函数
}
（6）源代码
#include<stdio.h>
#define N 8
#define MAXSIZE 100
int board[N][N]; //定义棋盘
int Htry1[8]={1,-1,-2,2,2,1,-1,-2}; /*存储马各个出口位置相对当前位置行下标的增量数组*/
int Htry2[8]={2,-2,1,1,-1,-2,2,-1}; /*存储马各个出口位置相对当前位置列下标的增量数组*/
struct Stack{
int i;
int j;
int director;
}stack[MAXSIZE];
int top=-1;
void InitLocation(int xi,int yi);//马儿在棋盘上的起始位置坐标
int TryPath(int i,int j); //马儿每个方向进行尝试，直到试完整个棋盘
void Display(); //输出马儿行走的路径
void InitLocation(int xi,int yi)//起始坐标函数
{
int x,y;
top++;
stack[top].i=xi;
stack[top].j=yi;
stack[top].director=-1;
board[xi][yi]=top+1;
x=stack[top].i;
y=stack[top].j;
if(TryPath(x,y))
Display();
else printf("无解");
}
int TryPath(int i,int j)
{
int find,director,number,min,i1,j1,h,k,s;
int a[8],b1[8],b2[8],d[8];
while(top>-1)
{
for(h=0;h<8;h++)//用数组a[8]记录当前位置的下一个位置的可行路径的条数
{
number=0;
i=stack[top].i+Htry1[h];
j=stack[top].j+Htry2[h];
b1[h]=i;
b2[h]=j;
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)
{
for(k=0;k<8;k++)
{
i1=b1[h]+Htry1[k];
j1=b2[h]+Htry2[k];
if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8)
number++;
}
a[h]=number;
}
}
for(h=0;h<8;h++)//根据可行路径条数小到大按下表排序放入数组d[8]中
{
min=9;
for(k=0;k<8;k++)
if(min>a[k])
{
min=a[k];
d[h]=k;
s=k;
}
a[s]=9;
}
director=stack[top].director;
if(top>=63)
return (1);
find=0;
for(h=director+1;h<8;h++)//向八个方向进行探寻
{
i=stack[top].i+Htry1[d[h]];
j=stack[top].j+Htry2[d[h]];
if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)
{
find=1;
break;
}
}
if(find==1)//如果找到下一个位置进栈
{
stack[top].director=director;
top++;
stack[top].i=i;
stack[top].j=j;
stack[top].director=-1;
board[i][j]=top+1;
}
else //否则退栈
{
board[stack[top].i][stack[top].j]=0;
top--;
}
}
return (0);
}
void Display() //输出马儿行走路径函数
{
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
printf("\t%d ",board[i][j]);//输出马儿在棋盘上走过的路径
printf("\n\n");
}
printf("\n");
}
void main()
{
int i,j;
int x,y;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
board[i][j]=0;
for(;;)
{
printf("Please input importpoint(1<=x<=8 and 1<=y<=8)\n");
printf("Input x = ");//输入起始位置的横坐标
scanf("%d",&x);
printf("Input y = ");//输入起始位置的纵坐标
scanf("%d",&y);
if(x>=1&&x<=8&&y>=1&&y<=8)break;
printf("Your input is worng!!!\n");
}
printf("begin with %d board:\n\n", 8*(x-1)+y);
InitLocation(x-1,y-1);//调用起始坐标函数
}
四、调试分析
1. 本次实验的主要目的是在于掌握和理解栈的特性和它的应用。在编制该程序中遇到了很多问题。首先，在开始刚编制程序的时候遇到的问题是，程序编译都通不过，主要在一些细节的问题上，还有在程序的返回值在刚开始时也没有正确返回。经过编译慢慢调试，编译都能通过，没有错误和警告。
2. 本程序的模块划分比较合理,仅用四个模块实现马踏棋盘的实现，先写出原始棋盘，以便对照，再初始棋盘再用贪心算法，如果每下一步的路点可行，直接打印出结果；增加其效率。
3. 算法的时空分析
1）由于采用贪心算法从而使算法的时间复杂度大大减少了算法的难度及算法的空间复杂度，大大提高了效率，节省了大量的时间。
2）本程序用最少的程序实现这一复杂的代码，因为用到它中的捷径筛选法从而避免了多次重复运算保证程序的顺利进行。
3)因为采用贪心算法，使每走下步时都多考虑一步，使走法不用回溯，使得程序顺利，且有效率。
五、用户说明
1、本程序的运行环境为DOS操作系统，执行文件为：mataqipan.exe
2、测试数据自行制定一个马的初始位置（x,y）,(1<<x,y<<8)
六、运行结果
结果1：
结果2：
七、实验体会
通过本次实验的编写，能够掌握栈的性质以及它的应用。这次实验花了很多时间才完成，其实本应该早完成的，在检查的过程中有多多少少修改完美了一下，不过算法思想却没有改变。这个程序也让我头疼了几次，就是运行速度很慢，要等很久才能输出结果，这样的话很占内存资源，而且CPU的使用记录也很高，主要是它需要的运算太多，所以CPU 使用记录也是很高的。虽然我也参考了一些优化的算法，可以找到最优路进走，但是这些最优算法都和栈的应用失去了联系，本次的实验主要目的就是要了解栈，所以不用栈来写该程序就失去了该实验的意义。
在该程序的编制过程中留下了一些思考的问题，就是马儿从一个起点位置开始探寻，最后马儿探寻成功的路径会不会是不只一条路径，可能还有多条路径，由于时间和精力的限制没有去深究，但是这应该值的思考的。
在用顺序栈来实现该程序之前，也尝试过用链栈来做，但是发现如果用链栈来做的话，在存储调用的时候不是很方便，或许用链栈来做应该是对自己的一种挑战。尽管没有用链栈做不过，用顺寻栈来做在编制该程序中也收获不小。
八、参考书籍
（1）数据结构，汤文兵，华东理工大学出版社
（2） 数据结构——习题与解析，李春葆，清华大学出版社
（3） C语言课程设计案例精编，郭翠英，中国水利出版社
（4）数据结构（c语言版） 严蔚敏 吴伟民 编著 清华大学出版社
实习三
稀疏矩阵运算器
一、需求分析
1、 本程序实现两个稀疏矩阵相加、相减和相乘的运算。要求输入形式采用三元组表示，而运算结果的矩阵则以通常的阵式形式列出，并且矩阵的行列数均不超过20。在要求运算后程序需要对矩阵是否可进行此运算做出判别，若不合法程序会做出相应处理。
2、 本演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中需要的相关信息及命令。运算处理结果显示在其后。
3、 程序要求输入的数据以及执行的命令包括：
a) 输入合法两个矩阵（三元组形式）；
b) 计算出两个矩阵的和，差，积；
c) 打印出结果。
4、 测试数据
a) ┌ 10 0 0 ┐ ┌ 0 0 0 ┐ ┌ 10 0 0 ┐
│ 0 0 9 │ + │ 0 0 -1│ = │ 0 0 8 │
└ -1 0 0 ┘ └ 1 0 -3 ┘ └ 0 0 -3 ┘
b） ┌ 10 0 ┐ ┌ 0 0 ┐ ┌ 10 0 ┐
│ 0 9 │ - │ 0 -1 │ = │ 0 10 │
└ -1 0 ┘ └ 1 -3 ┘ └ -2 3 ┘
c） ┌ 4 -3 0 0 1 ┐ ┌ 3 0 0 ┐ ┌ 0 -6 0 ┐
│ 0 0 0 8 0 │× │ 4 2 0 │ = │ 8 0 0 │
│ 0 0 1 0 0 │ │ 0 1 0 │ │ 0 1 0 │
└ 0 0 0 0 70 ┘ │ 1 0 0 │ └ 0 0 0 ┘
└ 0 0 0 ┘
二、概要设计
1、定义稀疏矩阵的抽象数据类型
ADT SparseMatrix{
数据类型：D = {aij | i = 1，2，……，m；j = 1，2，……，n
aij∈int，m，n分别表示为矩阵的行数和列数}
数据关系：R = {Row，Col}
Row = {<ai,j，ai,j+1> | 1 <= i <= m，1 <= j <= n -1}
Col = {<ai,j，ai+1,j> | 1 <= I <= m -1，I <= j <= n}
基本操作：
Input(TSMatrix *M)
操作结果：输入矩阵。
Output(TSMatrix *M)
操作结果：输出稀疏矩阵。
1） AddSMatrix(A, B)
初始条件：稀疏矩阵A，B已知，并且行数列数对应相等。
操作结果：求稀疏矩阵的和 A + B，并把结果保存在操作此函数的对象矩阵中。
2） SubSMatrix(A, B)
初始条件：稀疏矩阵A，B已知，并且行数列数对应相等。
操作结果：求稀疏矩阵的和 A – B，并把结果保存在操作此函数的对象稀疏矩阵中。
3） MultSMatrix(A, B)
初始条件：稀疏矩阵A，B已知，并且A的列数等于B的行数。
操作结果：求稀疏矩阵的乘积 A×B，并把结果保存在操作此函数的对象稀疏矩阵中。
（4）jishu(TSMatrix *M)
操作结果; 找出矩阵各行的第一个非零元的个数
} ADT SparseMatrix
2、本程序包括两大模块
1) void main()
{
初始化；
接受命令；
处理命令；
}
2) 稀疏矩阵模块——实现稀疏矩阵的抽象数据类型
各模块之间的调用关系：
主程序模块 ——> 稀疏矩阵模块
三、 详细设计
（1）、稀疏矩阵的全称变量及节点类型
# define MAXSIZE 12500 //非零元个数最大值
# define MAXRC 100
# define OK 1
# define ERROR 0
typedef struct{
int row,col; //非零元的行标和列标
int e;
}Triple;
typedef struct{
Triple data[MAXSIZE+1]; //非零元三元组表，data[0]
int rpos[MAXRC+1];
int rnum[20];
int mu,nu,tu; //矩阵的行数，列数，非零元个数
}TSMatrix;
（2）输入矩阵
int Input(TSMatrix *M) //输入矩阵
{
int k;
printf("输入行数:\n");
scanf("%d",&M->mu);
printf("输入列数:\n");
scanf("%d",&M->nu);
printf("输入非零元个数:\n");
scanf("%d",&M->tu);
if(M->mu<=0||M->nu<=0||M->tu>MAXSIZE+1) //输入错误
return ERROR;
else
{
for(k=1;k<=M->tu;k++)
{
printf("请输入元素，格式为：行数 列数 元素\n");
scanf("%d %d %d",&M->data[k].row,&M->data[k].col,&M->data[k].e);
}
return OK;
}
}
（3）输出矩阵
void Output(TSMatrix *M)
{
int a[21][21]={0};
int i,j,k,m,n;
for(k=1;k<=M->tu;k++)
{
m=M->data[k].row;
n=M->data[k].col;
a[m][n]=M->data[k].e;
}
for(i=1;i<=M->mu;i++)
{
for(j=1;j<=M->nu;j++)
printf("%5d",a[i][j]);
printf("\n");
}
}
（4）求采用三元组顺序表存储表示的稀疏矩阵M和N的和,结果赋给矩阵Q
int AddSMatrix(TSMatrix *M,TSMatrix *N,TSMatrix *Q) {
int i,j,p,q,x=0,y=0;
if((M->mu<=0)||(M->nu<=0)||(M->tu<=0)||(N->mu<=0)||(N->nu<=0)||(N->tu<=0))
return ERROR;
if(M->mu!=N->mu||M->nu!=N->nu)
return ERROR;
Q->mu=M->mu;
Q->nu=M->nu;
Q->tu=0;
for(i=1;i<=Q->mu;i++)
{
for(j=1;j<=Q->nu;j++)
{
for(p=1;p<=M->tu;p++)
{
if((i==M->data[p].row)&&(j==M->data[p].col))
{
x=M->data[p].e;
break;
}
else
x=0;
}//for p
for(q=1;q<=N->tu;q++)
{
if((i==N->data[q].row)&&(j==N->data[q].col))
{
y=N->data[q].e;
break;
}
else
y=0;
}//for q
if((x+y)!=0)
{
Q->data[Q->tu+1].row=i;
Q->data[Q->tu+1].col=j;
Q->data[Q->tu+1].e=x+y;
Q->tu++;
}//if
}//for j
}//for i
return OK;
}
（5）//求采用三元组顺序表存储表示的稀疏矩阵M和N的差,结果赋给矩阵Q
int SubMatrix(TSMatrix *M,TSMatrix *N,TSMatrix *Q)//求采用三元组顺序表存储表示的稀疏矩阵M和N的差,结果赋给矩阵Q
{
int i,j,p,q,x=0,y=0;
if((M->mu<=0)||(M->nu<=0)||(M->tu<=0)||(N->mu<=0)||(N->nu<=0)||(N->tu<=0))
return ERROR;
if(M->mu!=N->mu||M->nu!=N->nu)
return ERROR;
Q->mu=M->mu;
Q->nu=M->nu;
Q->tu=0;
for(i=1;i<=Q->mu;i++)
{
for(j=1;j<=Q->nu;j++)
{
for(p=1;p<=M->tu;p++)
{
if((i==M->data[p].row)&&(j==M->data[p].col))
{
x=M->data[p].e;
break;
}
else
x=0;
}//for p
for(q=1;q<=N->tu;q++)
{
if((i==N->data[q].row)&&(j==N->data[q].col))
{
y=N->data[q].e;
break;
}
else
y=0;
}//for q
if((x+y)!=0)
{
Q->data[Q->tu+1].row=i;
Q->data[Q->tu+1].col=j;
Q->data[Q->tu+1].e=x-y;
Q->tu++;
}//if
}//for j
}//for i
return OK;
}
（6）找出矩阵各行的第一个非零元的个数
int jishu(TSMatrix *M)
{ //找出矩阵各行的第一个非零元的个数
int arow,k=1;
M->rpos[1]=1;
for(arow=1;arow<=M->mu;++arow){
M->rnum[arow]=0;
while(M->data[k].row==arow){M->rnum[arow]++;k++;}
M->rpos[arow+1]=M->rpos[arow]+M->rnum[arow];}
return OK;
}
（7）求采用三元组顺序表存储表示的稀疏矩阵M和N的积,结果赋给矩阵Q
int Multiplication(TSMatrix *M,TSMatrix *N,TSMatrix *Q) {
int arow,tp,p,brow,t,q,ccol;
int ctemp[100]={0};
if(M->nu!=N->mu)
return ERROR;
Q->mu=M->mu;
Q->nu=N->nu;
Q->tu=0;
jishu(M);
jishu(N);
if (M->tu*N->tu != 0)
{
for (arow=1; arow<=M->mu; ++arow)
{
ctemp [arow]= 0; // 当前行各元素累加器清零
for(ccol=1;ccol<=20;ccol++)ctemp[ccol]=0;
Q->rpos[arow] = Q->tu+1;
if (arow<M->mu)
tp=M->rpos[arow+1];
else
tp=M->tu+1;
for (p=M->rpos[arow]; p<tp;++p)
{ //对当前行中每一个非零元
brow=M->data[p].col;
if (brow < N->mu )
t = N->rpos[brow+1];
else
t = N->tu+1;
for (q=N->rpos[brow]; q< t; ++q)
{
ccol = N->data[q].col; // 乘积元素在Q中列号
ctemp[ccol] += M->data[p].e * N->data[q].e;
} // for q
} // 求得Q中第arow行的非零元
for (ccol=1; ccol<=Q->nu; ++ccol)
if (ctemp[ccol])
{
if (++Q->tu > MAXSIZE)
return ERROR;
Q->data[Q->tu].row = arow;
Q->data[Q->tu].col =ccol;
Q->data[Q->tu].e = ctemp[ccol];
} // if
} // for arow
} // if
return OK;
} // Multiplication
（8）主程序模块
void main()
{
TSMatrix *A,*B,*C;
char c;
A=(TSMatrix *)malloc(sizeof(TSMatrix));
B=(TSMatrix *)malloc(sizeof(TSMatrix));
C=(TSMatrix *)malloc(sizeof(TSMatrix));
printf("如做加法，请输入+，如做减法，请输入-，如做乘法，请输入*。");
//getchar();
scanf("%c",&c);
if(c=='+')
{
printf("输入A矩阵\n");
Input(A);
printf("矩阵A为：\n");
Output(A);
printf("输入B矩阵\n");
Input(B);
printf("矩阵B为：\n");
Output(B);
AddSMatrix(A,B,C);
printf("A+B=\n");
Output(C);
}
if(c=='-')
{
printf("输入A矩阵\n");
Input(A);
printf("矩阵A为：\n");
Output(A);
printf("输入B矩阵\n");
Input(B);
printf("矩阵B为：\n");
Output(B);
SubMatrix(A,B,C);
printf("A-B=\n");
Output(C);
}
if(c=='*')
{
printf("输入A矩阵\n");
Input(A);
printf("矩阵A为：\n");
Output(A);
printf("输入B矩阵\n");
Input(B);
printf("矩阵B为：\n");
Output(B);
Multiplication(A,B,C);
printf("A*B=\n");
Output(C);
}
}
（9）程序源代码
# include <stdio.h>
#include <iostream.h>
# include <stdlib.h>
# define MAXSIZE 12500 //非零元个数最大值
# define MAXRC 100
# define OK 1
# define ERROR 0
typedef struct{
int row,col; //非零元的行标和列标
int e;
}Triple;
typedef struct{
Triple data[MAXSIZE+1]; //非零元三元组表，data[0]
int rpos[MAXRC+1];
int rnum[20];
int mu,nu,tu; //矩阵的行数，列数，非零元个数
}TSMatrix;
int Input(TSMatrix *M) //输入矩阵
{
int k;
printf("输入行数:\n");
scanf("%d",&M->mu);
printf("输入列数:\n");
scanf("%d",&M->nu);
printf("输入非零元个数:\n");
scanf("%d",&M->tu);
if(M->mu<=0||M->nu<=0||M->tu>MAXSIZE+1) //输入错误
return ERROR;
else
{
for(k=1;k<=M->tu;k++)
{
printf("请输入元素，格式为：行数 列数 元素\n");
scanf("%d %d %d",&M->data[k].row,&M->data[k].col,&M->data[k].e);
}
return OK;
}
}
void Output(TSMatrix *M)
{
int a[21][21]={0};
int i,j,k,m,n;
for(k=1;k<=M->tu;k++)
{
m=M->data[k].row;
n=M->data[k].col;
a[m][n]=M->data[k].e;
}
for(i=1;i<=M->mu;i++)
{
for(j=1;j<=M->nu;j++)
printf("%5d",a[i][j]);
printf("\n");
}
}
int AddSMatrix(TSMatrix *M,TSMatrix *N,TSMatrix *Q)//求采用三元组顺序表存储表示的稀疏矩阵M和N的和,结果赋给矩阵Q
{
int i,j,p,q,x=0,y=0;
if((M->mu<=0)||(M->nu<=0)||(M->tu<=0)||(N->mu<=0)||(N->nu<=0)||(N->tu<=0))
return ERROR;
if(M->mu!=N->mu||M->nu!=N->nu)
return ERROR;
Q->mu=M->mu;
Q->nu=M->nu;
Q->tu=0;
for(i=1;i<=Q->mu;i++)
{
for(j=1;j<=Q->nu;j++)
{
for(p=1;p<=M->tu;p++)
{
if((i==M->data[p].row)&&(j==M->data[p].col))
{
x=M->data[p].e;
break;
}
else
x=0;
}//for p
for(q=1;q<=N->tu;q++)
{
if((i==N->data[q].row)&&(j==N->data[q].col))
{
y=N->data[q].e;
break;
}
else
y=0;
}//for q
if((x+y)!=0)
{
Q->data[Q->tu+1].row=i;
Q->data[Q->tu+1].col=j;
Q->data[Q->tu+1].e=x+y;
Q->tu++;
}//if
}//for j
}//for i
return OK;
}
int SubMatrix(TSMatrix *M,TSMatrix *N,TSMatrix *Q)//求采用三元组顺序表存储表示的稀疏矩阵M和N的差,结果赋给矩阵Q
{
int i,j,p,q,x=0,y=0;
if((M->mu<=0)||(M->nu<=0)||(M->tu<=0)||(N->mu<=0)||(N->nu<=0)||(N->tu<=0))
return ERROR;
if(M->mu!=N->mu||M->nu!=N->nu)
return ERROR;
Q->mu=M->mu;
Q->nu=M->nu;
Q->tu=0;
for(i=1;i<=Q->mu;i++)
{
for(j=1;j<=Q->nu;j++)
{
for(p=1;p<=M->tu;p++)
{
if((i==M->data[p].row)&&(j==M->data[p].col))
{
x=M->data[p].e;
break;
}
else
x=0;
}//for p
for(q=1;q<=N->tu;q++)
{
if((i==N->data[q].row)&&(j==N->data[q].col))
{
y=N->data[q].e;
break;
}
else
y=0;
}//for q
if((x+y)!=0)
{
Q->data[Q->tu+1].row=i;
Q->data[Q->tu+1].col=j;
Q->data[Q->tu+1].e=x-y;
Q->tu++;
}//if
}//for j
}//for i
return OK;
}
int jishu(TSMatrix *M)
{ //找出矩阵各行的第一个非零元的个数
int arow,k=1;
M->rpos[1]=1;
for(arow=1;arow<=M->mu;++arow){
M->rnum[arow]=0;
while(M->data[k].row==arow){M->rnum[arow]++;k++;}
M->rpos[arow+1]=M->rpos[arow]+M->rnum[arow];}
return OK;
}
int Multiplication(TSMatrix *M,TSMatrix *N,TSMatrix *Q) //求采用三元组顺序表存储表示的稀疏矩阵M和N的积,结果赋给矩阵Q
{
int arow,tp,p,brow,t,q,ccol;
int ctemp[100]={0};
if(M->nu!=N->mu)
return ERROR;
Q->mu=M->mu;
Q->nu=N->nu;
Q->tu=0;
jishu(M);
jishu(N);
if (M->tu*N->tu != 0)
{
for (arow=1; arow<=M->mu; ++arow)
{
ctemp [arow]= 0; // 当前行各元素累加器清零
for(ccol=1;ccol<=20;ccol++)ctemp[ccol]=0;
Q->rpos[arow] = Q->tu+1;
if (arow<M->mu)
tp=M->rpos[arow+1];
else
tp=M->tu+1;
for (p=M->rpos[arow]; p<tp;++p)
{ //对当前行中每一个非零元
brow=M->data[p].col;
if (brow < N->mu )
t = N->rpos[brow+1];
else
t = N->tu+1;
for (q=N->rpos[brow]; q< t; ++q)
{
ccol = N->data[q].col; // 乘积元素在Q中列号
ctemp[ccol] += M->data[p].e * N->data[q].e;
} // for q
} // 求得Q中第arow行的非零元
for (ccol=1; ccol<=Q->nu; ++ccol)
if (ctemp[ccol])
{
if (++Q->tu > MAXSIZE)
return ERROR;
Q->data[Q->tu].row = arow;
Q->data[Q->tu].col =ccol;
Q->data[Q->tu].e = ctemp[ccol];
} // if
} // for arow
} // if
return OK;
} // Multiplication
void main()
{
TSMatrix *A,*B,*C;
char c;
A=(TSMatrix *)malloc(sizeof(TSMatrix));
B=(TSMatrix *)malloc(sizeof(TSMatrix));
C=(TSMatrix *)malloc(sizeof(TSMatrix));
printf("如做加法，请输入+，如做减法，请输入-，如做乘法，请输入*。");
//getchar();
scanf("%c",&c);
if(c=='+')
{
printf("输入A矩阵\n");
Input(A);
printf("矩阵A为：\n");
Output(A);
printf("输入B矩阵\n");
Input(B);
printf("矩阵B为：\n");
Output(B);
AddSMatrix(A,B,C);
printf("A+B=\n");
Output(C);
}
if(c=='-')
{
printf("输入A矩阵\n");
Input(A);
printf("矩阵A为：\n");
Output(A);
printf("输入B矩阵\n");
Input(B);
printf("矩阵B为：\n");
Output(B);
SubMatrix(A,B,C);
printf("A-B=\n");
Output(C);
}
if(c=='*')
{
printf("输入A矩阵\n");
Input(A);
printf("矩阵A为：\n");
Output(A);
printf("输入B矩阵\n");
Input(B);
printf("矩阵B为：\n");
Output(B);
Multiplication(A,B,C);
printf("A*B=\n");
Output(C);
}
}
四、调试分析
1） 程序采用二维数组来模拟矩阵的加减乘算法，相对于十字链表来说比较容易实现，而且不易出错，而且在操作方面也比较容易实现，故舍弃十字链表的模拟。
2） 程序出错时，反映出来是步骤混乱，经过调试发现是使用标准库里的scanf函数造成的，由于scanf是不带缓存的标准输入，故在读入字符之前使用会使字符读入出现错误。解决方法：在scanf函数中的格式项里添加格式“%*c”，吸收回车或者空格。
五、用户手册
1、本程序采用dos操作系统，编程软件为vc6
2、进入演示程序后用户只要按照提示输入信息即可。
六、运行结果
1、进入界面进行选择
2、选择“+”
3、分别输入A矩阵和B矩阵得出结果
七、总结与体会
通过这次实验，我明白了稀疏矩阵三元组顺序，以及实现的一些方法，实现了课本上的矩阵转置和快速转置的算法。基本理解了矩阵的压缩存储，为以后程序的编写打下了坚实的基础，同时在代码的书写中也巩固了C语言的语法知识和书写的规范性。
八、参考书籍
（1）数据结构，汤文兵，华东理工大学出版社
（2） 数据结构——习题与解析，李春葆，清华大学出版社
（3） C语言课程设计案例精编，郭翠英，中国水利出版社
（4）数据结构 （c语言） 严蔚敏 吴伟民 编著 清华大学出版社
实习四
教学计划编制问题
一、需求分析
1．设计内容：
1）问题描述
大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
2）基本要求
a.输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。
b.允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
c.若根据给定的条件问题无解，则报告适当的信息；否则，将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
3）测试数据
学期总数：6；
学分上限：10；
该专业共开设课数：12
课程号：从C01到C12；
学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。
先修关系如下图：
二、概要设计
1、程序的模块组成
LocateVex（）：图的邻接表存储的基本操作
CreateGraph（）：构造生成树
Display（）：输出图的邻接矩阵
FindInDegree（）：求顶点的入度
InitStack（）：构造一个空栈
ClearStack（）：清空栈
StackEmpty（）：判断是否为空栈
Pop（）：出栈
Push（）：入栈
TopologicalSort（）：输出G顶点的拓扑排序结果
2模块的层次结构及调用关系
三、详细设计
1采用C语言定义相关的数据类型。
其中包括字符常量，整型，字符型，字符串型，typedef 定义的类型，结构体型，单链表节点类型，结构体数组。
2主要函数
（1）.LocateVex（）：图的邻接表存储的基本操作。由初始条件: 图G存在,u和G中顶点有相同特征转而进行判断，若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
图CreateGraph（） 图Display（）
（2）.CreateGraph（）：构造生成图。采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)。
（3）.Display（）：输出图的邻接矩阵。采用循环设置输出图的邻接矩阵。
（4）.FindInDegree（）：求顶点的入度。
图FindInDegree（） 图InitStack（）
（5）.InitStack（）：构造一个空栈。
（6）.ClearStack（）：清空栈。
（7）.StackEmpty（）：判断栈是否为空。若栈S为空栈，则返回TRUE，否则返回FALSE。
(8）Pop（）：出栈。若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。
(9)Push（）：入栈。插入元素e为新的栈顶元素。
(10).TopologicalSort（）：输出G顶点的拓扑排序结果。有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, 否则返回ERROR
3.主函数
void main()
{ ALGraph f;
printf("教学计划编制问题的数据模型为拓扑排序AOV-网结构。\n");
printf("以下为教学计划编制问题的求解过程:\n");
printf("请输入学期总数:");
scanf("%d",&xqzs);
printf("请输入学期的学分上限:");
scanf("%d",&xfsx);
CreateGraph(&f);
Display(f);
TopologicalSort(f);
}
4程序源代码
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()52
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSE
#define MAX_NAME 10
/* 顶点字符串的最大长度*/
#define MAXCLASS 100
int Z=0;
int X=0;
int xqzs,q=1,xfsx;
typedef int InfoType;
typedef char VertexType[MAX_NAME]; /* 字符串类型*/
/* 图的邻接表存储表示*/
#define MAX_VERTEX_NUM 100
typedef enum{DG}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct ArcNode
{
int adjvex; /* 该弧所指向的顶点的位置*/
struct ArcNode *nextarc; /* 指向下一条弧的指针*/
InfoType *info; /* 网的权值指针）*/
}ArcNode; /* 表结点*/
typedef struct
{
VertexType data; /* 顶点信息*/
ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的指针*/
}VNode,AdjList[MAX_VERTEX_NUM]; /* 头结点*/
typedef struct
{
AdjList vertices,verticestwo;
int vexnum,arcnum; /* 图的当前顶点数和弧数*/
int kind; /* 图的种类标志*/
}ALGraph;
/* 图的邻接表存储的基本操作*/
int LocateVex(ALGraph G,VertexType u)
{ /* 初始条件: 图G存在,u和G中顶点有相同特征*/
/* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
Status CreateGraph(ALGraph *G)
{ /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图) */
int i,j,k;
VertexType va,vb;
ArcNode *p;
printf("请输入教学计划的课程数: ");
scanf("%d",&(*G).vexnum);
printf("请输入拓扑排序所形成的课程先修关系的边数: ");
scanf("%d",&(*G).arcnum);
printf("请输入%d个课程的代表值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量*/
{ scanf("%s",(*G).vertices[i].data);
(*G).vertices[i].firstarc=NULL;
}
printf("请输入%d个课程的学分值(<%d个字符):\n",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i) /* 构造顶点向量*/
{scanf("%s",(*G).verticestwo[i].data);
}
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<(*G).arcnum;++k) /* 构造表结点链表*/
{ scanf("%s%s",va,vb);
i=LocateVex(*G,va); /* 弧尾*/
j=LocateVex(*G,vb); /* 弧头*/
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
p->info=NULL; /* 图*/
p->nextarc=(*G).vertices[i].firstarc; /* 插在表头*/
(*G).vertices[i].firstarc=p;
}
return OK;
}
void Display(ALGraph G)
{ /* 输出图的邻接矩阵G */
int i;
ArcNode *p;
switch(G.kind)
{case DG: printf("有向图\n");
}
printf("%d个顶点：\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
printf("%s ",G.vertices[i].data);
printf("\n%d条弧(边):\n",G.arcnum);
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{printf("%s→%s ",G.vertices[i].data,G.vertices[p->adjvex].data);
p=p->nextarc;
}
printf("\n");
}
}
void FindInDegree(ALGraph G,int indegree[])
{ /* 求顶点的入度，算法调用*/
int i;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
indegree[i]=0; /* 赋初值*/
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{ indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
typedef int SElemType; /* 栈类型*/
/*栈的顺序存储表示*/
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/
#define STACKINCREMENT 2 /* 存储空间分配增量*/
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针*/
int stacksize; /* 当前已分配的存储空间，以元素为单位*/
}SqStack; /* 顺序栈*/
/* 顺序栈的基本操作*/
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败*/
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
void ClearStack(SqStack *S) //清空栈的操作
{
S->top=S->base;
}
Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}
Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素*/
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间*/
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof
(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败*/
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
typedef int pathone[MAXCLASS];
typedef int pathtwo[MAXCLASS];
Status TopologicalSort(ALGraph G)
{ /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */
/* 否则返回ERROR。*/
int i,k,j=0,count,indegree[MAX_VERTEX_NUM];
bool has=false;
SqStack S;
pathone a;
pathtwo b;
ArcNode *p;
FindInDegree(G,indegree); /* 对各顶点求入度indegree[0..vernum-1] */
InitStack(&S); /* 初始化栈*/
for(i=0;i<G.vexnum;++i) /* 建零入度顶点栈S */
if(!indegree[i])
{ Push(&S,i);
//cout<<*G.vertices[i].data<<endl;
}
/* 入度为者进栈*/
count=0; /* 对输出顶点计数*/
while(!StackEmpty(S))
{ /* 栈不空*/
Pop(&S,&i);
a[i]=*G.vertices[i].data;
b[i]=*G.verticestwo[i].data;
printf("课程%s→学分%s ",G.vertices[i].data,G.verticestwo[i].data);
/* 输出i号顶点并计数*/
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{ /* 对i号顶点的每个邻接点的入度减*/
k=p->adjvex;
if(!(--indegree[k])) /* 若入度减为,则入栈*/
{Push(&S,k);
//cout<<*G.vertices[i].data<<endl;
}
}
}
if(count<G.vexnum)
{printf("此有向图有回路\n");
return ERROR;
}
else
{printf("为一个拓扑序列。\n");
has=true;
}
FindInDegree(G,indegree); /* 对各顶点求入度indegree[0..vernum-1] */
ClearStack(&S);
cout<<"======================课程计划如下==============================="<<endl;
int qq=1; //学期数
int xxf;
while(qq<=xqzs)
{
int result[20];
int rtop=0;
int nn=0;
//int ccount=0;
// 学期学分计算
xxf=0;
for(i=0;i<G.vexnum;++i) /* 建零入度顶点栈S */
{ if(0==indegree[i])
{
Push(&S,i);
}
}
while(!StackEmpty(S))
{
int bb;
Pop(&S,&i);
bb=atoi(G.verticestwo[i].data);
xxf=xxf+bb;
if(xxf>xfsx)
{
break;
}
indegree[i]--;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{ /* 对i号顶点的每个邻接点的入度减*/
k=p->adjvex;
indegree[k]--;
/* if(!(--indegree[k])) 若入度减为,则入栈
{
Push(&S,k);
}*/
}
result[rtop]=i;
rtop++;
}
cout<<"第"<<qq<<"个"<<"学期的课程为："<<endl;
for(nn=0;nn<rtop;nn++)
{
cout<<"课程"<<G.vertices[result[nn]].data<<endl;
}
qq++;
}
return OK;
}
void main()
{ ALGraph f;
printf("教学计划编制问题的数据模型为拓扑排序AOV-网结构。\n");
printf("以下为教学计划编制问题的求解过程:\n");
printf("请输入学期总数:");
scanf("%d",&xqzs);
printf("请输入学期的学分上限:");
scanf("%d",&xfsx);
CreateGraph(&f);
Display(f);
TopologicalSort(f);
}
四、调试分析
由于程序十分的复杂，遇到了很多常见的语法错误，及逻辑错误。这需要我们不断的调试分析。符号的格式之类，指针的用法，判断输入输出的条件都是十分容易出错的地方。在逐条排除，向同学老师请教后，程序终于得以完成。这让我明白了，解决问题，要细心认真，集思广益，这样才能把问题解决。
五、用户手册
（1）本程序运行环境为dos操作系统，编译软件为vc6
（2）可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程号与课程号之间的对应关系。
（3）
输入学期总数，学分上限，课程数，先修关系边数，课程代表符号，相对学分值
六、测试结果
七、实验心得
这次实验，我进行了大量的资料查阅，包括向老师请求帮助解释题目要求，对所学知识进行复习。通过这些努力，我对算法有了更深入的理解，对编程的步骤，有了具体的体会。通过和同学的广泛交流，我体会到了合作的必要性及合作的优势。更重要的是，这个课题完全脱胎于实际问题，让我对计算机行业，充满了信心和自豪。
以往我们学的计算机知识一般停留在理论上，这让我们不太理解计算机的应用和前景，而较少注重我们对算法的实践锻炼。而这一次的实习既需要我们去联系理论，又需要我们去实践方法，很多东西看上去都学过，但是和实际联系才知道变通的艰难。纸上得来终觉浅，这是我这次实习的最大收获。这次的实验让我们知道该如何跨过实际和理论之间的鸿沟。
这次实习，我认识到了以下几个方面。
第一就是要合作。不懂的问题一定要向同学，老师请教。这样才能集思广益，有利于问题的解决。也能够让自己节省时间，有效率的完成工作。齐心协力完成这个程序，互相帮助，这是我们同做课题的同学的共同体会。
第二就是要细心。程序的编制难免会出现错误，不能一次成功，出现错误后，一定要认真细心耐心的排查，这样千锤百炼，程序才能完成。在浮躁的时候能够静下心来思考，是极其重要的。
第三就是要学习。学习网上已经有的类似程序，学习他们的方法与思想。这样，才能最快的了解问题，得到启迪。
这两个星期的课程设计，让我受益匪浅。它不只对我们专业知识进行了加强，还锻炼了我们的思维能力，合作的精神，是我们理论与实际想结合。这些都是在书本上难以学习到的。这些弥足珍贵的经验和记忆，使我对我的未来从事的工作充满了信心，而最终程序的运行成功使我得到了莫大的满足。在日后的学习中，我会更加重视知识的积累，学好算法，为成为一名优秀的计算机专业人才努力。
八、参考书籍
（1）数据结构，汤文兵，华东理工大学出版社
（2） 数据结构——习题与解析，李春葆，清华大学出版社
（3） C语言课程设计案例精编，郭翠英，中国水利出版社
（4）数据结构（c语言） 严蔚敏 吴伟民 编著 清华大学出版社
实习五哈希表设计
一、需求分析
1 问题描述
针对自己的班集体中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。
2 基本要求
假设人名为中国姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。构造哈希函数，用链表法处理冲突。
. 测试数据
读取熟悉的30个人的姓名作测试。
二、概要设计
1、数据类型、数据元素的定义
#define MAX_NUM 26 //最大数据笔数
#define PRIME 23 //MAX_NUM的质数
#define NOTEXISTED NULL
/*定义数据结构*/
typedef struct Person
{
long id;
char name[21];
struct Person *link;
} Student;
2、本程序包括如下功能模块
哈希函数模块，冲突处理模块，哈希表初始化模块，哈希表创建模块，哈希表显示模块，按关键字查找模块，插入模块，删除模块和主程序模块。
3、ADT HashTable {
数据对象：D1={ai|ai∈elem[MAXSIZE],i=0,1,2,…,0≦n≦MAXSIZE }
elem [MAXSIZE]是哈希表中关键字的集合，MAXSIZE为哈希表长。}
D2={ai|ai∈elemflag[MAXSIZE]是哈希表中有无关键字的标志的集合，MAXSIZE为哈希表长。}
基本操作：
Hash(key)
初始条件：数据元素关键字key已存在
操作结果：根据哈希函数计算相应地址，并返回此地址。
InitialHash(HashTable &H)
初始条件：哈希表H已存在
操作结果：初始化哈希表把elem[MAXSIZE]、elemflag[MAXSIZE]和count分别置0。
SearchHash(HashTable &H,int k)
初始条件：哈希表H已存在
操作结果：在开放定址哈希表H中查找关键字为k的元素，若查找成功，并返回SUCCESS；否则返回UNSUCCESS。
InsertHash(HashTable &H,int e)
初始条件：哈希表H已存在
操作结果：查找不成功时插入数据元素e到开放定址哈希表H中，并返回SUCCESS；否则输出已有此数！插入失败！并返回UNSUCCESS。
CreateHash(HashTable &H)
操作结果：构造哈希表。
PrintHash(HashTable H)
初始条件：哈希表H已存在
操作结果：将哈希表存储状态显示输出。
DeleteHash(HashTable &H,int e)
初始条件：哈希表H已存在
操作结果：若通过哈希函数找到相应的位置并且此位置的elemflag[MAXSIZE]==1，删除相应位置的数据元素的关键字并把elemflag[MAXSIZE]==2，否则，输出无此数的提示语。
三、详细设计
1显示信息函数，从哈希表一一查找是否有节点存在
void show() {
int i;
Student *ptr;
puts("学号 姓名");
puts("------------------------");
for ( i = 0; i < MAX_NUM;i++ )
{
if ( Hashtab[i] != NULL )//表不为空，则将整个表显示出来
{
ptr = Hashtab[i];
while (ptr)
{
printf("%-5ld %15s\n",ptr->id,ptr->name);
ptr = ptr->link;
}
}
}
getchar();getchar();
system("cls");
menu();
}
2输入信息函数
void insert() {
Student *newnode;
int index;
newnode = ( Student *)malloc(sizeof(Student)); //输入记录
newnode->link = NULL;
printf("输入学号: ");
scanf("%ld",&newnode->id);
printf("输入名字: ");
scanf("%s",newnode->name);
index = Hash(newnode->name); //利用哈希函数求得记录地址
if ( Hashtab[index] == NULL ) //判断该链表是否为空，若为空则建立链表
{
Hashtab[index] = newnode;
printf("信息成功录入！\n");
getchar();getchar(); //接收回车
system("cls");
menu();
}
else
{
if ((search(Hashtab[index],newnode)) == NOTEXISTED) //调用search函数
{
newnode->link = Hashtab[index];
Hashtab[index] = newnode;
printf("信息成功录入！\n");
getchar();getchar();
system("cls");
menu();
}
else
printf("记录已存在！\n");
getchar();getchar();
system("cls");
menu();
}
}
3查询函数
void query() //查询节点函数
{
Student *query_node;
long index;
query_node = (Student *)malloc(sizeof(Student));
printf("输入姓名 : ");
scanf("%s",&query_node->name);
index = Hash(query_node->name);
query_node = search(Hashtab[index],query_node); //查找节点函数
if ( query_node == NOTEXISTED )
printf("记录不存在！\n");
else
{
printf("学号: %ld 姓名 : %s\n",
query_node->id,query_node->name);
getchar();getchar();
system("cls");
menu();
}
}
4主函数及其他伪代码
void main()
{
int i;
for ( i = 0; i< MAX_NUM; i++) //初始化哈希链表
Hashtab[i] = NULL;
menu(); //调用显示选择菜单函数
}
void menu() //选择菜单函数
{
char *menu_prompt =
" 学号查询哈希表\n"
" ********************************************\n"
" 【1】 输入信息\n"
" 【2】 显示信息\n"
" 【3】 查找\n"
" 【4】 退出\n"
" ********************************************\n"
"\n"
"选择您需要的功能 : ";
printf("%s",menu_prompt);
switch (getchar())
{
case '1' :
insert();
break;
case '2' :
show();
break;
case '3' :
query();
break;
case '4' :
puts("谢谢使用！ ^_^");
break;
default :
puts("Invalid choice !!");
}
}
int Hash(char str[]) //哈希函数，除留取余
{
long val=0;
char p[20],*p1;
strcpy(p,str);
p1=p;
while(*p1!='\0')
val=val+*p1++; //将字符串中的所有字符对应的ASCII值相加
return(val%MAX_NUM);
}
Student *search(Student *linklist,Student *Node) //search函数，如找到节点则返回指向该节点的指针
{
Student *ptr = linklist;
while (ptr->name != Node->name && ptr->link != NULL)
ptr = ptr->link;
if ( ptr == NULL )
return NOTEXISTED;
else
return ptr;
}
5源代码
/*哈希法：使用链地址法解决冲突*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <ctype.h>
#include <string.h>
#define MAX_NUM 26 //最大数据笔数
#define PRIME 23 //MAX_NUM的质数
#define NOTEXISTED NULL
/*定义数据结构*/
typedef struct Person
{
long id;
char name[21];
struct Person *link;
} Student;
/*建立哈希链表*/
Student *Hashtab[MAX_NUM];
/*函数原形声明*/
int Hash(char str[]); //哈希函数
void insert(); //输入信息函数
Student *search(Student *,Student *); //查找函数
void query(); //查询节点函数
void show(); //显示信息函数
void menu(); //选择菜单函数
void main()
{
int i;
for ( i = 0; i< MAX_NUM; i++) //初始化哈希链表
Hashtab[i] = NULL;
menu(); //调用显示选择菜单函数
}
void menu() //选择菜单函数
{
char *menu_prompt =
" 学号查询哈希表\n"
" ********************************************\n"
" 【1】 输入信息\n"
" 【2】 显示信息\n"
" 【3】 查找\n"
" 【4】 退出\n"
" ********************************************\n"
"\n"
"选择您需要的功能 : ";
printf("%s",menu_prompt);
switch (getchar())
{
case '1' :
insert();
break;
case '2' :
show();
break;
case '3' :
query();
break;
case '4' :
puts("谢谢使用！ ^_^");
break;
default :
puts("Invalid choice !!");
}
}
int Hash(char str[]) //哈希函数，除留取余
{
long val=0;
char p[20],*p1;
strcpy(p,str);
p1=p;
while(*p1!='\0')
val=val+*p1++; //将字符串中的所有字符对应的ASCII值相加
return(val%MAX_NUM);
}
void insert() //输入信息函数
{
Student *newnode;
int index;
newnode = ( Student *)malloc(sizeof(Student)); //输入记录
newnode->link = NULL;
printf("输入学号: ");
scanf("%ld",&newnode->id);
printf("输入名字: ");
scanf("%s",newnode->name);
index = Hash(newnode->name); //利用哈希函数求得记录地址
if ( Hashtab[index] == NULL ) //判断该链表是否为空，若为空则建立链表
{
Hashtab[index] = newnode;
printf("信息成功录入！\n");
getchar();getchar(); //接收回车
system("cls");
menu();
}
else
{
if ((search(Hashtab[index],newnode)) == NOTEXISTED) //调用search函数
{
newnode->link = Hashtab[index];
Hashtab[index] = newnode;
printf("信息成功录入！\n");
getchar();getchar();
system("cls");
menu();
}
else
printf("记录已存在！\n");
getchar();getchar();
system("cls");
menu();
}
}
Student *search(Student *linklist,Student *Node) //search函数，如找到节点则返回指向该节点的指针
{
Student *ptr = linklist;
while (ptr->name != Node->name && ptr->link != NULL)
ptr = ptr->link;
if ( ptr == NULL )
return NOTEXISTED;
else
return ptr;
}
void query() //查询节点函数
{
Student *query_node;
long index;
query_node = (Student *)malloc(sizeof(Student));
printf("输入姓名 : ");
scanf("%s",&query_node->name);
index = Hash(query_node->name);
query_node = search(Hashtab[index],query_node); //查找节点函数
if ( query_node == NOTEXISTED )
printf("记录不存在！\n");
else
{
printf("学号: %ld 姓名 : %s\n",
query_node->id,query_node->name);
getchar();getchar();
system("cls");
menu();
}
}
void show() //显示信息函数，从哈希表一一查找是否有节点存在
{
int i;
Student *ptr;
puts("学号 姓名");
puts("------------------------");
for ( i = 0; i < MAX_NUM;i++ )
{
if ( Hashtab[i] != NULL )//表不为空，则将整个表显示出来
{
ptr = Hashtab[i];
while (ptr)
{
printf("%-5ld %15s\n",ptr->id,ptr->name);
ptr = ptr->link;
}
}
}
getchar();getchar();
system("cls");
menu();
}
四、调试分析
首先，仔细研究了《数据结构》课程中关于hash表（即散列表）的内容。散列表的缺点就是容易出现冲突（也叫碰撞），两个关键字可能映射到同一个槽中，然后就产生了冲突，解决冲突的方法有很多种，例如，分离链接法，就把散列到同一个槽中的所有元素都放在一个链表中，如果，槽 j 中有一个指针，它指向所有散列到j的元素构成的链表的头；如果不存在这样的元素，则j中为NULL。书本上介绍的是开地址法和链表法。通过对网上及各种资料的学习，了解了线性探测法、平方探测法等方法。本程序按照要求，使用了链表的方法解决冲突。深深体会到了hash表法对于查找数据方面的极大的优越性。对数据结构课程的重要性有了新的体会。
其次，在程序调试过程中，对于回车键的接收方面，经过调试、修改、调试，确定“getchar();”的个数。对于理论与实践的结合，有新的体会。每段程序只有真正运行了才具有生命，才被赋予了精神。每一次的调试运行，就是丰富程序价值的过程，很有意义的一件事。
五、用户手册
1、本程序运行环境为dos操作系统
2进入系统后，即显示选择界面，用户可根据自己需求自行选择
六、测试结果
1、输入信息
2、显示信息
3查找
4退出
七、实验心得
经过这次课程设计的学习，让我明白了编写程序的思路是很重要的。在你编写一个程序之前，如果你的脑袋里面没有思路，根本就不可能编出好的程序。就算能编出程序来，相信编出的程序的逻辑性也不会很强，因为你是想到什么就编什么，不系统。因此在我们编程序之前一定要做好充分的准备，首先要理清自己的思路，然后再将思路分划成几个模块，一块一块的编写，最后再将所有的模块联系起来，组成一个完整的程序。在上机实验之前，最好将程序编写好在草稿纸上，这样在编译的时候也比较有效率。
其实在这次课程设计的过程中，我也遇到了很多难题。在种种的困难中，我明白了耐心在编写程序时的重要性。如果你没有耐心就肯定编不出好的程序，特别是在调试的过程中。我们初次写的程序在电脑上调试的时候也许会出项几百个错误，这时候我们应该耐心的检查出错的地方和原因，并予以改正。而不是抱怨自己写的程序太烂错误太多，就此放弃。相信再强的人也不可能一次就能编译成功，总会有一些问题出现。其实只要有耐心，你就会发现，在你修改了一个错误之后，其它有的错误也会跟着消失，所以在编译的时候一定要有耐心。
这段时间的课程设计，我也认识到数据结构是一门比较难的课程，需要花很多的时间去练习和实践。要想把这门课程学好学精不是一件容易的事，但是相信事在人为，只要肯下功夫就一定能学好。总的来说，这次程序设计让我获益匪浅，相信在以后的学习生活中我也能从中获得启发
八、参考书籍
（1）数据结构，汤文兵，华东理工大学出版社
（2） 数据结构——习题与解析，李春葆，清华大学出版社
（3） C语言课程设计案例精编，郭翠英，中国水利出版社
（4）、数据结构（c语言版） 严蔚敏 吴伟民 编著 清华大学出版社