兰州大学数据结构课程设计3_数据结构课程设计全集
兰州大学数据结构课程设计3由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计全集”。
《数据结构》课程设计题目(程序实现采用C语言)
题目1：猴子选王（学时：3）
一堆猴子都有编号，编号是1，2，3...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。
要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。
题目2 ：字符逆转（学时：3）
从键盘读入一个字符串，把它存入一个链表（每个结点存储1个字符），并按相反的次序将字符串输出到显示屏。题目3 ：工资核算（学时：3）
设有一个单位的人员工资有如下信息：name、department、base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。题目4：满足条件的有序表生成（学时：3）
已知三个有序表A、B、C，它们皆由同一类元素构成，现要求对于表A作以下运算而获得有序表D：排出A中所有的既在B中又在C中出现的元素。另外该任务要求具有建立有序表功能以及输出有序表到屏幕的功能。题目5：一元多项式的减法（学时：6）
设有两个一元多项式A(x),B(x)，请完成运算A(x)+B(x)、A(x)-B(x)，要求多项式采用链表进行存储。另外该任务要求具有建立多项式链表以及输出多项式到屏幕的功能。题目6：床位分配（学时：6）
某客店有N个等级的房间，第k级客房有A（k）个，每个房间有B（k）个单人床，以菜单调用方式设计为单身旅客分配床位以及离店时收回床位的程序。要求分配成功时，印出旅客姓名、年龄、性别、到达日期、客房等级、房间号及床位号；分配不成功时，允许更改房间等级，若不更改等级，印出“满客”提示。题目7：文本文件单词的检索及计数（学时：6）
要求编程建立一个文本文件，每个单词不包括空格及跨行，单词由字符序列构成且区分大小写，完成以下功能：统计给定单词在文本文件中出现的总次数、检索输出某单词在文本文件中首次出现的行号及位置。
#include #include #include #include #define N 250 typedef struct Cstring
//定义结构体(字符长串）
{ char string[N];}Cstring;
typedef struct File //定义结构体（文件）{ Cstring filename[N];//文件数组
FILE *in, *out;
//文件指针（入/出）int line[N], filenum;//行编号，文件编号 }File;
typedef struct Line
//结构体（行）{ int pos[N],counter;//所在行号，计数器 }Line;
int Length(char* a)//函数（判断单词是否结束）返回单词长度 { int i=0;while(a[i]!=' '&&a[i]!='n')i++;return i;}
int Index(Cstring a,Cstring b,Line* l)//索引（字符总串，单词，要查找的字符总串第几行）{
int i,k,j,p=1,num=0;
l->counter=0;
Cstring temp;
while(p
{
i=1;
while(a.string[p]!=' '&&a.string[p]!=' '&&a.string[p]!=','&&a.string[p]!='.')//将字符总串的一个单词放到temp中，并没进行一次，num++
{
temp.string[i]=a.string[p];
i++;
p++;
}
temp.string[i]=' ';
temp.string[0]=Length(&(temp.string[1]));
num++;
k=1;
j=1;
if(temp.string[0]==b.string[0])
{
while(j
{
if(temp.string[k]==b.string[j])
{
k++;
j++;
}
else break;
}
}
if(j>b.string[0])//说明2个单词相同
{
l->pos[l->counter]=num;//该行第l->counter的单词所在位置(即该单词为该行第几个单词)
l->counter++;//行计数器加1
}
while(a.string[p]==' '||a.string[p]==','||a.string[p]=='.')
p++;
}
return 1;}
int Equal(Cstring a,Cstring b)//是否相同，相同返回1 {
int i=1,j=1;
if(a.string[0]!=b.string[0])
return 0;
while(i
{
if(a.string[i]==b.string[j])
{
i++;j++;
}
else return 0;
}
return 1;}
int CreateFile(File* F)//创建文件
{
Cstring s;
char c;
printf(“请输入文件名n”);
scanf(“%s”,&(F->filename[F->filenum].string[1]));//名字放置区
F->filename[F->filenum].string[0]=Length(&(F->filename[F->filenum].string[1]));//文件名字符串长度
if(!(F->in=fopen(&(F->filename[F->filenum].string[1]),“w”)))//以写的方式打开文件，文件指针 F->in
{
printf(“不能打开文件n”);
exit(0);
}
F->line[F->filenum]=0;//该文件行数初始为0
printf(“请输入文件内容(结束符为'#')n”);
while(gets(&(s.string[1])))//每次输一行时就会执行一次循环
{
s.string[0]=Length(&s.string[1]);
c=s.string[s.string[0]];
if(s.string[0]!=0)
{
if(c=='#')
s.string[s.string[0]]='n';
fputs(&(s.string[1]),F->in);//将所有字符存到文件中
fputc('n',F->in);//存入一个换行符
F->line[F->filenum]++;//该文件行数加1
}
if(c=='#')break;
}
fclose(F->in);//关闭文件
F->filenum++;//文件数组下标加1，指向下一个文件编号
return 1;}
int CountString(File* F)//计数 { Cstring b,a,s;int k,counter=0,line=0,i;Line l[N];
printf(“请输入检索的文件名:”);
scanf(“%s”,&(b.string[1]));
b.string[0]=Length(&(b.string[1]));
for(k=0;kfilenum;k++)
//找到该文件名
{
if(Equal(F->filename[k],b))break;
}
if(k==F->filenum){
printf(“文件不存在n”);
return 0;
}
if(!(F->out=fopen(&F->filename[k].string[1],“r”))){
printf(“不能打开文件n”);
exit(0);
} //找到了并能正常打开文件编号为k
printf(“请输入搜索的单词：”);
scanf(“%s”,&(s.string[1]));
s.string[0]=Length(&(s.string[1]));
while(lineline[k])//行数小于k文件的总行数
{
fgets(&(a.string[1]),N,F->out);//从文件中将内容读取到a地址处
a.string[0]=Length(&(a.string[1]));
Index(a,s,&l[line]);//索引
line++;//进入下一行
}
for(i=0;i
if(l[i].counter!=0)
counter+=l[i].counter;
}
printf(“文件中出现该单词的个数为：”);
printf(“%dn”,counter);
fclose(F->out);//关闭文件
return 1;}
int PotString(File* F)//单词定位 {
Cstring b,s,a;
Line l[N];
int k,line=0,i,j;
printf(“请输入检索的文件名:”);
scanf(“%s”,&(b.string[1]));
b.string[0]=Length(&(b.string[1]));
for(k=0;kfilenum;k++)
//找到该文件编号
{
if(Equal(F->filename[k],b))break;
}
if(k==F->filenum)
{
printf(“文件不存在n”);
return 0;
}
if(!(F->out=fopen(&(F->filename[k].string[1]),“r”)))
{
printf(“不能打开文件n”);
exit(0);
}
//找到了并能正常打开文件编号为k
printf(“请输入要定位的单词：”);
scanf(“%s”,&(s.string[1]));
s.string[0]=Length(&(s.string[1]));
while(lineline[k])//行数小于k文件的总行数
{
fgets(&(a.string[1]),N,F->out);//从文件中将内容读取到a地址处
a.string[0]=Length(&(a.string[1]));
Index(a,s,&l[line]);//索引
line++;
}
printf(“该单词首次出现的行号以及位置：n”);
for(i=0;i
{
if(l[i].counter>0)
{
printf(“行号：”);printf(“%-3d”,i+1);
printf(“所在位置：”);
for(j=0;j
{
printf(“第”);
printf(“%d”,l[i].pos[j]);
printf(“个单词 ”);
}
printf(“n”);
break;
}
}
return 1;}
void main(){
int i;
File F;
F.filenum=0;
printf(“-----------------文本文件单词的检索及计数-------------------n”);
printf(“n
1.创建文件n
3.单词定位n
4.退出n”);
printf(“请选择操作:n”);
while(scanf(“%d”,&i)&&i!=4)
{
switch(i){
case 1:CreateFile(&F);printf(“n请选择操作:n”);break;
case 2:{CountString(&F);printf(“n请选择操作:n”);break;}
case 3:{PotString(&F);printf(“n请选择操作:n”);break;}
default:printf(“n操作错误n”),i=4;}
} }
题目8：二叉树的遍历（学时：6）
2.单词计数n
二叉树以lson-rson链接方式存储，以菜单方式设计并完成功能任务：建立并存储树、输出前序遍历结果、输出中序遍历结果、输出后序遍历结果、交换左右子树、统计高度，其中对于中序、后序的遍历运算要求采用非递归方式。
#include #include #define M 100 typedef struct node//定义二叉树结点 { char data;struct node *lchild,*rchild;}BTNode;
BTNode *CreatBTree()//创建二叉树(先序递归){ char ch;BTNode *b;scanf(“%c”,&ch);if(ch=='#')//递归结束控制符
b=NULL;else {
b=(BTNode *)malloc(sizeof(BTNode));
b->data=ch;
b->lchild=CreatBTree();//递归先序建立左子树
b->rchild=CreatBTree();//递归先序建立右子树
} return b;} void PreOrder(BTNode *b)//递归先序遍历二叉树函数 {
if(b!=NULL)
{
printf(“%c ”,b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
} } void InOrder(BTNode *b)//非递归中序遍历二叉树函数 { BTNode *stack[M],*p;int top=-1;if(b!=NULL){
p=b;
while(top>-1||p!=NULL)
{
while(p!=NULL)//扫描p的所有左结点并入栈
{
top++;
stack[top]=p;
p=p->lchild;
}
if(top>-1)
{
p=stack[top];//出栈访问结点
top--;
printf(“%c ”,p->data);
p=p->rchild;//扫描p的右结点
}
}
printf(“n”);} } void PostOrder(BTNode *b)//非递归后序遍历二叉树函数 { BTNode *stack[M],*p;int sign,top=-1;if(b!=NULL){
do
{
while(b!=NULL)// b所有左结点入栈
{
top++;
stack[top]=b;
b=b->lchild;
}
p=NULL;// p指向栈顶前一个已访问结点
sign=1;
//置b为已访问
while(top!=-1 && sign)
{
b=stack[top];//取出栈顶结点
if(b->rchild==p)//右孩子不存在或右孩子已访问则访问b
{
printf(“%c ”,b->data);
top--;
p=b;//p指向被访问的结点
}
else
{
b=b->rchild;//b指向右孩子结点
sign=0;//置未访问标记
}
}
}while(top!=-1);
printf(“n”);} } void change(BTNode *b)
//左右子树交换(递归){ BTNode *r;r=(BTNode *)malloc(sizeof(BTNode));int f1=0,f2=0;if(b==0)return;
//树为空时，跳出
if(b->lchild){
change(b->lchild);
r->lchild=b->lchild;
f1++;
//有左子树，符号位不为空
}
if(b->rchild){
change(b->rchild);
r->rchild=b->rchild;
f2++;
//有右子树，符号位不为空
} if(f1==0)r->lchild=NULL;
//否则，给中间变量赋空值
if(f2==0)r->rchild=NULL;if(f1||f2){
b->rchild=r->lchild;
//左右子树交换
b->lchild=r->rchild;} } int max(int m,int n){ if(m>n)
return m;else return n;}
int count(BTNode *b)
//计算树高(递归){
if(b==NULL)
return 0;else return(1+max(count(b->lchild),count(b->rchild)));}
int main()
{
BTNode *root = NULL;
printf(“-----------------二叉树的遍历-----------------nn”);
printf(“请按先序递归顺序创建二叉树(结束符 #):n”);
root = CreatBTree();
printf(“n递归先序遍历结果:n”);
PreOrder(root);
printf(“n非递归中序遍历结果:n”);
InOrder(root);
printf(“非递归后序遍历结果:n”);
PostOrder(root);
printf(“n树高: %dn”,count(root));printf(“n左右子树交换位置:”);
change(root);
printf(“n递归先序遍历结果:n”);
PreOrder(root);
printf(“n非递归中序遍历结果:n”);
InOrder(root);
printf(“非递归后序遍历结果:n”);
PostOrder(root);
return 0;}
题目9：创建二叉排序树（学时：3）
二叉排序树以lson-rson链接方式存储，编写能够通过键盘输入建立二叉排序树，并在建立完立即在屏幕显示中序遍历结果的程序。
#include #include typedef struct node//定义二叉排序树结点 { char data;struct node *lson,*rson;}BTNode;
void Ins_Tree(BTNode *p,BTNode *d){ if(p->datadata){
if(p->rson==NULL)
p->rson=d;
else
Ins_Tree(p->rson,d);} else {
if(p->lson==NULL)
p->lson=d;
else
Ins_Tree(p->lson,d);
} }
void PreOrder(BTNode *p)//递归中序遍历二叉排序树函数 {
if(p!=NULL)
{
PreOrder(p->lson);
printf(“%c ”,p->data);
PreOrder(p->rson);
} }
void main(){ BTNode *head,*p,*b;char ch;head=(BTNode *)malloc(sizeof(BTNode));p=head;
printf(“------------------------创建二叉排序树----------------------nnn”);printf(“请逐个输入所需字符(以#结束):n”);scanf(“%c”,&ch);if(ch!='#'){
p->data=ch;
p->lson=NULL;
p->rson=NULL;} else return;scanf(“%c”,&ch);while(ch!='#'){
b=(BTNode *)malloc(sizeof(BTNode));
b->data=ch;
b->lson=NULL;
b->rson=NULL;
Ins_Tree(p,b);
scanf(“%c”,&ch);} printf(“n二叉排序树中序序列为:n”);
PreOrder(head);
printf(“n”);}
