《数据结构》 课程设计报告
课程名称： 课程设计题目：姓
名：
院系： 专
业： 年
级： 学
号： 指导教师： 《数据结构》课程设计 约瑟夫环
俞晓沁 计算机学院
计算机科学与技术
大二
0905120
4王立波
2011年5月22日
1、课程设计的目的
（1） 熟练使用C++语言编写程序，解决实际问题；
（2） 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （3） 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （4） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
2、需求分析
1、任务：编号是1，2，„„,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
要求：利用不带表头结点的单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。
2、测试数据
m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？
3、课程设计报告内容
概要设计
（1）在分析题目要求的基础上，我首先设计了一个节点的结构体 struct LNode { int xuhao; int data; LNode *next; };
//存储每个人的信息（序号，密码）以及下个人的信息 （2）然后构造了类LinkList cla LinkList { public:
LinkList();
void Make_L(int n);
void GetXuhao(int m,int n); private:
LNode *tail;
};
（3）基本操作
Void LinkList::LinkList();
//构造函数
Void LinkList::Make_L(int n); //建立单向循环链表
Void LinkList::GetXuhao(int m,int n); //按照出列顺序输出各个人的编号 (4)主函数
初始化
输入人数n, 上限数m以及每个人的密码.
L.Make_L(n);
L.GetXuhao(m,n);
4、总结
一、这次课程设计的心得体会通过实践我的收获如下：
巩固和加深了对线性表两种存储结构—顺序存储和链式存储的理解，提高了综合运用本章节所学知识的能力。
二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：
1、认真上好专业课，牢固掌握课本中的基本知识。
2、写程序时多思考，克服不愿触碰不懂地方的障碍，完善知识结构。
3、写程序要严谨，多写备注，方便检查。
4、在课余时间多翻阅课外相关书籍，多看程序，吸取别人程序中好的方法，熟悉后多加利用。
5、程序清单：
#include using namespace std; struct LNode
{ int xuhao; int data;
LNode *next; }; cla LinkList { public:
LinkList(); void Make_L(int n); void GetXuhao(int m,int n); private:
};
LinkList::LinkList()
{ tail=new LNode; tail->next=NULL;
} void LinkList::Make_L(int n) {
} LNode *p,*q; if(n!=0) {
} tail->xuhao=1; cin>>tail->data; q=tail; for(int i=2;i
} tail->next=q; p=new LNode; cin>>p->data; p->xuhao=i; tail->next=p; tail=p;
LNode *tail; void LinkList:: GetXuhao(int m,int n){
} int main() {
int m,n;
LinkList L;
cout
cin>>n;
cout>m; cout
j=0; while(j
} p=p->next; ++j; cout next->xuhaonext->data; q=p->next; p->next=q->next; delete q; }
system(\"pause\");
return 0; }
6、参考文献
[1] 万健 主编 数据结构实用教程（C++版）——电子工业出版社.[2]网上搜索相关程序作为参考
7、程序运行结果
《数据结构》 课程设计报告
课程名称： 课程设计题目：姓
名：
院系： 专
业： 年
级： 学
号： 指导教师： 《数据结构》课程设计 魔王语言解释
俞晓沁 计算机学院
计算机科学与技术
大二
0905120
4王立波
2011年5月22日
1.课程设计的目的
（5） 熟练使用C++语言编写程序，解决实际问题；
（6） 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （7） 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （8） 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
2.需求分析
1、[问题描述] 有一个魔王总是使用自己的一种非常精练而又抽象的语言讲话，没有人能听得懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：
（1） α －> β1β2„βm （2）（θδ1δ2„δn)－>θδnθδn－1„ θδ1θ
在这两种形式中，从左到右均表示解释。试写一个魔王语言的解释系统，把他的话解释成人能听得懂的话。 [基本要求] 用下述两条具体规则和上述规则形式（2）实现。设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。魔王语言可含人的词汇。
（1）B －> tAdA （2）A －> sae [测试数据] B(ehnxgz)B解释成tsaedsaeezegexenehetsaedsae 若将小写字母与汉字建立下表所示的对应关系，则魔王说的话是：“天上一只鹅地上一只鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一只鹅地上一只鹅”。 [小写字母与汉字对应关系] t d s a e z g x n h 天 地 上 一只 鹅 追 赶 下 蛋 恨
3、课程设计报告内容
概要设计
（1）建立了一个结构体，用来定义栈
struct SeqStack
{
char elem[Stack_Size];
int top; }; （2）基本操作
void InitStack(SeqStack *s) //构建栈
void Push(SeqStack *s,char x)
//入栈 void Pop(SeqStack *s,char *x)
//出栈
int Empty(SeqStack *s)
//判栈是否为空
（3）主函数
定义所需的栈并初始化
输入要翻译的魔王语言，入栈s
将tAdA入栈B，将sae入栈A
翻译魔王语言:while(Empty(&s))
{
…..
if(ch==\'B\') {…}
else if(ch==\'A\') {…}
else if(ch==\')\') {…}
else Push(&r,ch);
}
输出翻译后的结果
选择是否继续翻译为汉语: 输入1 - 输出翻译后的汉语，然后结束程序
输入0 - 结束程序
4、总结
一、这次课程设计的心得体会通过实践我的收获如下：
巩固和加深了对栈的理解，熟练地掌握了栈的运用（栈的初始化，判栈空，入栈，出栈等）。
二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：
1、认真上好专业课，牢固掌握课本中的基本知识。
2、写程序时多思考，克服不愿触碰不懂地方的障碍，完善知识结构。
3、写程序要严谨，多写备注，方便检查。
4、在课余时间多翻阅课外相关书籍，多看程序，吸取别人程序中好的方法，熟悉后多加利用。
5、程序清单：
#include #define Stack_Size 100 using namespace std;
struct SeqStack
//定义栈 {
char elem[Stack_Size];
int top; };
void InitStack(SeqStack *s) //构建栈 {
s->top=-1; }
void Push(SeqStack *s,char x)
//入栈 {
if(s->top==Stack_Size-1)
cout
else
{
s->top++; s->elem[s->top]=x;
} }
void Pop(SeqStack *s,char *x)
//出栈 {
if(s->top==-1)
cout
else
{
*x=s->elem[s->top];
s->top--;
} } int Empty(SeqStack *s)
//判栈是否为空 {
if(s->top==-1)
return(0);
else
return(1); }
void main() {
SeqStack B,A,s,B1,A1,r,M,R;
//定义栈
char ch,ch1,ch2,x;
char aa[100];
int n;
InitStack(&B);InitStack(&A);InitStack(&s);InitStack(&r);InitStack(&M);
//对定义的栈初始化
cout
//输入要翻译的魔王语言
cin>>aa;
Push(&B,\'t\');Push(&B,\'A\');Push(&B,\'d\');Push(&B,\'A\');
//进栈B→tAdA
Push(&A,\'s\');Push(&A,\'a\');Push(&A,\'e\');
//进栈A→sae
for(int i=0;aa[i]!=\'\\0\';i++)
//将输入的魔王语言进栈s
Push(&s,aa[i]);
while(Empty(&s))
{
Pop(&s,&ch);
//将栈s的栈顶提取出来赋值给ch
if(ch==\'B\')
{
B1=B;
//将栈B赋值给栈B1
while(Empty(&B1))
{
Pop(&B1,&ch1);
//B1不为空栈，则将栈B1的栈顶提取出来赋值给ch1
if(ch1==\'A\')
{
A1=A;
//将栈A赋值给栈A1
while(Empty(&A1))
{
Pop(&A1,&ch2);
//将栈A1的栈顶提取出来赋值给ch2
Push(&r,ch2);//ch2进栈r
}
}
else Push(&r,ch1);
//ch1不等于A的话，ch1进栈r
}
}
else if(ch==\'A\')
{
A1=A;
//ch=A的话，将栈A赋值给栈A1
while(Empty(&A1))
{
Pop(&A1,&ch2);//将栈A1的栈顶提取出来赋值给ch2
Push(&r,ch2);//ch2进栈r
}
}
else if(ch==\')\')
{
Pop(&s,&ch2);//将栈s的栈顶提取出来赋值给ch2
while(ch2!=\'(\')
{
Push(&M,ch2);
Pop(&s,&ch2);
}
Pop(&M,&ch2);//将栈M的栈顶提取出来赋值给ch2
x=ch2;
while(Empty(&M))
{
Push(&r,x);
//x保持不变，被多次压入r
Pop(&M,&ch2);
Push(&r,ch2);
}
Push(&r,x);
}
else Push(&r,ch);
}
cout
//输出翻译的结果 R=r;
while(Empty(&r))
{
Pop(&r,&ch);
cout
}
cout
cin>>n;
if(n==1)
{
cout
while(Empty(&R))
{
Pop(&R,&ch);
if(ch==\'t\')
cout
else if(ch==\'d\') cout
else if(ch==\'s\') cout
//将魔王语言进一
else if(ch==\'a\') cout
else if(ch==\'e\') cout
else if(ch==\'z\') cout
else if(ch==\'g\') cout
else if(ch==\'x\') cout
else if(ch==\'n\') cout
else if(ch==\'h\') cout
} cout
}
system(\"pause\"); }
6、参考文献
[1] 万健 主编 数据结构实用教程（C++版）——电子工业出版社.[2]网上搜索相关程序作为参考
7、程序运行结果：
《数据结构》 课程设计报告
课程名称： 课程设计题目：姓
名：
院系： 专
业： 年
级： 学
号： 指导教师：
《数据结构》课程设计
kruskal算法实现最小生成树问题
俞晓沁 计算机学院
计算机科学与技术
大二
0905120
4王立波
2011年5月22日
1．课程设计的目的
（9） 熟练使用C++语言编写程序，解决实际问题；
（10）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； （11）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； （12）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
2.需求分析
1、[基本要求] kruskal算法实现最小生成树问题
2、[测试数据]
2
7
3
6
4
5
1
5 2
4
6
2
2
2
1
3、课程设计报告内容
概要设计
（1） 首先我先建立了一个类Tree，用来存储输入图的信息
cla Tree
{ public :
Tree(){}
int Check(int parent[],int n);
void Order();
void BuildGraph();
void BuildTree();
void Display(); private:
int n,m;
int edgenum,nodenum; //边的数量，顶点的数量
int p[X];
//上一个父结点
int eB[X],eE[X],eR[X][X];
//边包括（eB:起点，eE:终点 eR:权植）
}; （2）基本操作：
void Tree:: BuildGraph()
//输入图(各边及权值) void Tree:: Order()
//按权值递增的顺序进行排序 void Tree:: BuildTree() void Tree::Display ()
//输出结果
（3）主函数
Tree t1;
t1.BuildGraph(); t1.Order(); t1.BuildTree(); t1.Display ();
4、总结
一、这次课程设计的心得体会通过实践我的收获如下：
巩固和加深了对最小生成树的理解，并且掌握了用kruskal算法实现最小生成树问题。
二、根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：
1、认真上好专业课，牢固掌握课本中的基本知识。
2、写程序时多思考，克服不愿触碰不懂地方的障碍，完善知识结构。
3、写程序要严谨，多写备注，方便检查。
4、在课余时间多翻阅课外相关书籍，多看程序，吸取别人程序中好的方法，熟悉后多加利用。
5、程序清单：
#include using namespace std; const int X=20;
cla Tree
{ public : Tree(){} int Check(int parent[],int n); void Order(); void BuildGraph(); void BuildTree(); void Display(); private:
int n,m;
int edgenum,nodenum; //边的数量，顶点的数量
int p[X];//上一个父结点
int eB[X],eE[X],eR[X][X];//边包括（eB:起点，eE:终点 eR:权植） };
void Tree:: BuildGraph()
//输入图(各边及权值) {
int i,n,m,k=1;
cout
cin>>nodenum;
cin>>edgenum;
for (i=1;i
{
cout
cin>>n;
cout
cin>>m;
cout\"
cout
cin>>eR[n][m];
eB[k]=n;
eE[k]=m;
k++; } }
void Tree:: Order()
//按权值递增的顺序进行排序
{
int i,j; //数组中的位置
int temp;
int b1,b2,e1,e2; //顶点数
for (i=1;i
{
for (j=1+i;j
{
b1=eB[i];
e1=eE[i];
b2=eB[j];
e2=eE[j];
if(eR[b1][e1]>eR[b2][e2])
{
temp=eB[i];
eB[i]=eB[j];
eB[j]=temp;
temp=eE[i];
eE[i]=eE[j];
eE[j]=temp;
}
}
}
}
void Tree:: BuildTree() {
for(int i=1;i
{
p[i]=0;
} }
int Tree:: Check(int p[],int n) {
while ( p[n] > 0)
{
n = p[n];
}
return n; }
void Tree::Display ()
//输出结果
{
cout
for (int i=1;i
{
n = Check(p, eB[i]);
m = Check(p, eE[i]);
if(n!=m)
{
cout\"
p[m]=n;
}
} }
void main() { Tree t1; t1.BuildGraph(); t1.Order(); t1.BuildTree(); t1.Display (); system(\"pause\"); }
6、参考文献
[1] 万健 主编 数据结构实用教程（C++版）——电子工业出版社.[2]网上搜索相关程序作为参考
7、程序运行结果
