数据结构课程设计报告.docx
《数据结构课程设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计报告.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构课程设计报告
数据结构课程设计
题目一：
约瑟夫环
题目二：
可变长顺序表设计
班级：
软件1303
姓名：
学期：
2014-2015学年第二学期
题目一：
约瑟夫环
问题描述：
编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持一个密码（正整数）。
一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。
试设计一个程序求出出列顺序。
基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。
基本要求：
1.用不带头结点单循环链表方法设计；
2.键盘输入总人数、初始报数上限值m及个人密码；
3.按照出列顺序输各人的编号。
测试数据：
m的初始值为7,n为5，各人密码依次为1，3，5，7，9。
正确出列顺序应为2，5，4，1，3
4.算法思想：
是用不带头结点单循环链表存储每个人的密码，链表长度为n，由用户键入m,n,key完成出列计算。
模块划分：
main函数完成全部内容
数据结构：
单循环链表
源程序：
#include"stdio.h"
#include"malloc.h"
structnode
{
intno;
intcode;
node*next;
};
intmain（）
{
intm,n,i,j;
node*p,*q,*first;
printf（"*************约瑟夫环*************\n\n"）;
printf（"请输入m的初始值m:
"）;
scanf（"%d",&m）;
printf（"\n请输入人数n:
"）;
scanf（"%d",&n）;
printf（"\n"）;
for（i=1;i<=n;i++）
{
if（i==1）
{
first=p=（node*）malloc（sizeof（node））;
if（p==0）
return0;
}
else
{
q=（node*）malloc（sizeof（node））;
if（q==0）
return0;
p->next=q;
p=q;
}
printf（"第%d个人的key为:
",i）;
scanf（"%d",&p->code）;
p->no=i;
}
p->next=first;
p=first;
printf（"\n\n*************出列*************\n\n"）;
for（j=1;j<=n;j++）
{
for（i=1;inext）;
m=p->code;
printf（"%d",p->no）;
p->no=p->next->no;
p->code=p->next->code;
q=p->next;
p->next=p->next->next;
free（q）;
}
printf（"\n\n完毕\n"）;
return0;
}
测试情况：
题目二：
可变长顺序表设计
问题描述：
编写一个函数，实现用键盘输入顺序表的元素进行建立顺序表的操作。
然后依次调用初始化、求数据元素个数，插入、删除和取数据元素并输出新的顺序表。
基本要求：
（1）使用动态数组结构。
（2）顺序表的操作包括：
初始化、求数据元素个数、插入、删除、取数据元素，编写每个操作的函数。
（3）设计一个测试主函数。
测试数据：
以随机输入的元素为原始数据
算法思想：
可变长顺序表的设计，主要是利用动态数组结构的设计方法。
动态数组是指用动态内存分配方法定义的数组，他中的元素的个数是在用户申请动态数组空间时才确定
的。
此外，用键盘输入顺序表的元素，进行建立顺序表。
依次调用初始化、求数据元素个数，插入、删除和取数据元素并输出新的顺序表。
模块划分：
Main.c文件。
Main.c文件包括以下函数：
初始化，求数据元素个数，插入，删除，取数据元素。
voidInitiate（SeqList*s,intmax）函数：
其功能是用于顺序表的初始化。
intListLength（SeqList*L）函数：
其功能是用于求顺序表的数据元素个数。
intInsert（SeqList*s）函数：
其功能是用于顺序表的插入。
intDelete（SeqList*s）函数：
其功能是用于顺序表的删除。
intgetdata（SeqList*s）函数：
其功能是用于函数的获取元素
voidmain（）函数：
主函数。
其功能建立顺序表并调用以上函数实现问题要求。
数据结构：
1.顺序表结构体定义：
typedefstruct
{int*str;
intLength;
}SeqList;
2.动态数组动态申请空间：
s->str=（int*）malloc（sizeof（int）*max）;
源程序：
#include
#include
#include
typedefstruct
{
int*str;
intLength;
}SeqList;
voidmain（）
{
voidInitiate（SeqList*s,intmax）;//函数声明
intListLength（SeqList*s）;
intInsert（SeqList*s）;
intDelete（SeqList*s）;
intGetdata（SeqList*s）;
voidPrint（SeqList*s,int）;
SeqListL;
intx,max;
printf（"+++++++++++++++++可变长顺序表设计+++++++++++++++\n"）;
printf（"\n请输入创建顺序表的长度:
"）;
scanf（"%d",&max）;
printf（"请输入创建的顺序表的值:
"）;
Initiate（&L,max）;
printf（"\n"）;
printf（"++++++++++++++++++++++++++++++++++++++++++++++++\n"）;
printf（"+功能选项+\n"）;
printf（"+1.数据元素个数2.数据元素插入+\n"）;
printf（"+3.数据元素删除4.取数据元素+\n"）;
printf（"+0.退出+\n"）;
printf（"++++++++++++++++++++++++++++++++++++++++++++++++\n"）;
way:
printf（"\n输入序号选择程序功能:
"）;
scanf（"%d",&x）;
if（x==1）
{
printf（"数据元素个数是：
%d\n",ListLength（&L））;
gotoway;
}
if（x==2）
{
Insert（&L）;
gotoway;
}
if（x==3）
{
Delete（&L）;
gotoway;
}
if（x==4）
{
Getdata（&L）;
gotoway;
}
if（x==0）
printf（"\n\n谢谢使用!
\n\n"）;
}
voidInitiate（SeqList*s,intmax）//初始化顺序表
{
inti,x;
s->str=（int*）malloc（sizeof（int）*max）;//动态申请空间
s->Length=max;
for（i=0;i{
scanf（"%d",&x）;
s->str[i]=x;
}
}
intListLength（SeqList*L）//元素个数
{
returnL->Length;
}
intInsert（SeqList*s）//插入
{
inti,j,x;
printf（"请输入要插入的位置及数据:
"）;
scanf（"%d%d",&j,&x）;
if（j<0||j>s->Length+1）
{
printf（"参数不合法!
\n"）;
return0;
}
else
{
realloc（s->str,（s->Length+1）*sizeof（int））;//新结点申请空间
for（i=s->Length-1;i>=j-1;i--）
{
s->str[i+1]=s->str[i];
}
s->str[j-1]=x;
s->Length++;
printf（"新的顺序表是：
"）;
for（i=0;iLength;i++）
printf（"%d",s->str[i]）;
printf（"\n"）;
return1;
}
}
voidPrint（SeqList*s,intmax）//顺序表
{
inti;
for（i=0;i{
printf（"%d",s->str[i]）;
}
}
intDelete（SeqList*s）//删除
{
inti,j,x;
printf（"请输入要删除数据的位置：
"）;
scanf（"%d",&j）;
if（j<0||j>s->Length）
{
printf（"参数不合法!
\n"）;
return0;
}
x=s->str[j-1];
for（i=j;iLength;i++）
{
s->str[i-1]=s->str[i];
}
s->Length--;
printf（"删除的数据为:
%d\n",x）;
printf（"新的顺序表为:
"）;
for（i=0;iLength;i++）
printf（"%d",s->str[i]）;
printf（"\n"）;
return1;
}
intGetdata（SeqList*s）//取数据元素
{
intj,x;
printf（"请输入要获取元素的位置:
"）;
scanf（"%d",&j）;
if（j<=0||j>s->Length）
{
printf（"参数不合法!
\n"）;
return0;
}
else
{
x=s->str[j-1];
printf（"获取的元素为:
%d\n",x）;
return1;
}
}
测试情况：
个人总结：
在这次课程设计中，我收获了很多单从课本上不能学到的知识，以及经验，这对我对数据结构这门课程的认识与理解有很大的帮助。
升级会员 