概述
课程设计
joseph环
任务：编号是1,2,…,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。
#include <bits/stdc++.h>
using namespace std;
typedef struct Node
{
int key;
int num;
struct Node *next;
}Node,*Link;
void InitList(Link &L)
{
L=(Node *)malloc(sizeof(Node));
if(!L) exit(1);
L->key=0;
L->num=0;
L->next=L;
}
void Creater(int n,Link &L)
{
Link p,q;
q=L;
for(int i=1;i<=n;i++)
{
p=(Node *)malloc(sizeof(Node));
if(!p) exit(1);
printf("第%d人的密码是：",i);
scanf("%d",&p->key);
p->num=i;
L->next=p;
L=p;
}
L->next=q->next;
free(q);
}
int main()
{
Link L,p,q;
int n,x;
L=NULL;
InitList(L);
printf("请输入人数：n");
scanf("%d",&n);
printf("请输入初始密码：n");
scanf("%d",&x);
Creater(n,L);
p=L;
for(int i=1;i<=n;i++)
{
for(int j=1;j<x;j++)
p=p->next;
q=p->next;
x=q->key;
printf("%d ",q->num);
p->next=q->next;
free(q);
}
return 0;
}
停车场管理
停车场管理的算法描述如下：1）接受命令和车号，若是汽车要进停车场，先判断停车场栈是否满，若不满，则汽车入栈，否则汽车进入便道队列等候。2）若是汽车要离开停车场，为给汽车让路，将停车场栈上若干辆汽车入临时栈，等这辆车出停车场后，临时栈中的汽车出栈，在回到停车场栈，然后看便道队列是否为空，若不空则说明有汽车等候，从队头取出汽车号，让该车进入停车场栈。3）重复1），2）直到为退出命令（车号为0或负数）。
#include <bits/stdc++.h>
using namespace std;
stack<string >q1,q2;
queue<string >t;
char s[1007];
void watch()
{
printf(" ****************************************n");
printf(" * 欢迎使用停车场管理系统 *n");
printf(" ****************************************nnn");
}
void watch1()
{
printf("n请选择操作类型：n");
printf(" 1.车辆停入n");
printf(" 2.车辆离开n");
printf(" 3.查询停车场已停车辆（先后顺序）n");
printf(" 4.离开系统n");
}
int main()
{
watch();
printf("n请输入停车场容量：");
int m;
scanf("%d",&m);
while(1)
{
system("cls");
watch();
watch1();
int poi;
scanf("%d",&poi);
if(poi==4) return 0;
else if(poi==1)
{
printf("请输入车牌号：");
scanf("%s",s);
if(q1.size()==m)
{
printf("停车场已满，请进入候车区等候n");
t.push(s);
}
else
{
printf("该车已进入停车场n");
q1.push(s);
}
}
else if(poi==2)
{
printf("请输入车牌号：");
scanf("%s",s);
while(!q1.empty()&&q1.top()!=s)
{
q2.push(q1.top());
q1.pop();
}
if(q1.empty()) printf("对不起，停车场无此车辆n");
else
{
printf("车牌号 %s 的车已驶出n",s);
q1.pop();
}
while(!q2.empty())
{
q1.push(q2.top());
q2.pop();
}
while(!t.empty()&&q1.size()!=m)
{
q1.push(t.front());
cout<<"位于候车区的车号为 "<<t.front()<<" 的车已进入停车场"<<endl;
t.pop();
}
}
else if(poi==3)
{
if(q1.empty()) printf("停车场无车辆n");
while(!q1.empty())
{
q2.push(q1.top());
q1.pop();
}
while(!q2.empty())
{
q1.push(q2.top());
cout<<q2.top()<<endl;
q2.pop();
}
}
printf("请输入回车键继续n");
getchar();
getchar();
}
}
树与二叉树转换
树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。
#include <bits/stdc++.h>
#define ll long long;
using namespace std;
void menu(int &a)
{
printf(" 树与二叉树的转换系统n");
printf(" 1. 建树n");
printf(" 2. 树的前序遍历递归n");
printf(" 3. 树的后序遍历递归n");
printf(" 4. 树的前序遍历非递归n");
printf(" 5. 树的后序遍历非递归n");
printf(" 6. 树的层次递归n");
printf(" 7. 离开系统n");
printf("请输入操作类型: ");
scanf("%d",&a);
}
typedef struct Node
{
char data;
struct Node *lchild,*rchild;
}bsnode,*bstree;
typedef struct stack
{
bstree data[100];
int top;
} lstack;
typedef struct queue
{
bstree data[100];
int front,rear;
} lqueue;
void initstack(lstack &p)
{
p.top=-1;
}
void push(lstack &p,bstree q)
{
p.data[++p.top]=q;
}
void pop(lstack &p,bstree &q)
{
q=p.data[p.top--];
}
void initqueue(lqueue &p)
{
p.front=p.rear=0;
}
void inqueue(lqueue &p,bstree q)
{
p.data[p.rear++]=q;
}
void dequeue(lqueue &p,bstree &q)
{
q=p.data[p.front++];
}
void createtree(bstree &p)
{
char ch;
scanf("%c",&ch);
if(ch=='@')
{
p=NULL;
return ;
}
else
{
p=new bsnode;
p->data=ch;
createtree(p->lchild);
createtree(p->rchild);
}
}
void cz1(bstree p)
{
if(p)
{
printf("%c ",p->data);
cz1(p->lchild);
cz1(p->rchild);
}
else
return ;
}
void cz2(bstree p)
{
if(p)
{
cz2(p->lchild);
printf("%c ",p->data);
cz2(p->rchild);
}
else
return ;
}
void cz3(bstree p)
{
lstack s;
initstack(s);
while(p!=NULL||s.top!=-1)
{
while(p!=NULL)
{
push(s,p);
p=p->lchild;
}
if(s.top!=-1)
{
pop(s,p);
printf("%c ",p->data);
p=p->rchild;
}
}
}
void cz4(bstree p)
{
lstack s;
initstack(s);
while(p!=NULL||s.top!=-1)
{
while(p!=NULL)
{
push(s,p);
printf("%c ",p->data);
p=p->lchild;
}
if(s.top!=-1)
{
pop(s,p);
p=p->rchild;
}
}
}
void cz5(bstree p)
{
lqueue s;
bstree q;
initqueue(s);
if(p)
{
inqueue(s,p);
while(s.rear!=s.front)
{
dequeue(s,q);
printf("%c ",q->data);
if(q->lchild)
{
inqueue(s,q->lchild);
}
if(q->rchild)
{
inqueue(s,q->rchild);
}
}
}
}
int main()
{
bstree p;
int a=0;
while(1)
{
system("cls");
menu(a);
if(a==1)
{
getchar();
createtree(p);
printf("n树已经成功建立n");//ABD@F@@@CE@@@
}
else if(a==2) cz1(p);
else if(a==3) cz2(p);
else if(a==4) cz4(p);
else if(a==5) cz3(p);
else if(a==6) cz5(p);
else if(a==7) break;
else printf("输入指令错误，请重新输入n");
printf("请输入回车以继续n");
getchar();
getchar();
}
return 0;
}
##行车路线
小明和小芳出去乡村玩，小明负责开车，小芳来导航。
小芳将可能的道路分为大道和小道。大道比较好走，每走1公里小明会增加1的疲劳度。小道不好走，如果连续走小道，小明的疲劳值会快速增加，连续走s公里小明会增加s2的疲劳度。
例如：有5个路口，1号路口到2号路口为小道，2号路口到3号路口为小道，3号路口到4号路口为大道，4号路口到5号路口为小道，相邻路口之间的距离都是2公里。如果小明从1号路口到5号路口，则总疲劳值为(2+2)2+2+22=16+2+4=22。
现在小芳拿到了地图，请帮助她规划一个开车的路线，使得按这个路线开车小明的疲劳度最小。
输入格式
输入的第一行包含两个整数n, m，分别表示路口的数量和道路的数量。路口由1至n编号，小明需要开车从1号路口到n号路口。
接下来m行描述道路，每行包含四个整数t, a, b, c，表示一条类型为t，连接a与b两个路口，长度为c公里的双向道路。其中t为0表示大道，t为1表示小道。保证1号路口和n号路口是连通的。
输出格式
输出一个整数，表示最优路线下小明的疲劳度。
样例输入
6 7
1 1 2 3
1 2 3 2
0 1 3 30
0 3 4 20
0 4 5 30
1 3 5 6
1 5 6 1
样例输出
76
取自同学的代码，纯抄袭，自用
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505;
const ll inf=0x3f3f3f3f3f3f3f3f;
ll v[N][N],v0[N][N]; // 邻接矩阵 v 记录大路，v0 记录小路；
ll dis[N],dis0[N]; //dis 记录大路到达i点的距离 ，dis0 记录小路到达i点的距离
bool vis[N];
ll n,m,flag,c,a,b;
queue<int >q;
void spfa(int first)
{
memset(vis,false,sizeof(vis));
memset(dis0,inf,sizeof(dis0));
memset(dis,inf,sizeof(dis));
dis[first]=0;
dis0[first]=0; //起点
q.push(first);
vis[first]=true;
int u;
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=false;
for(int i=1; i<=n; i++)
{
if(v[u][i]+dis[u]<dis[i]) // 从大路走向大路，更新大路；
{
dis[i]=dis[u]+v[u][i];
if(!vis[i])
{
q.push(i);
vis[i]=true;
}
}
if(v[u][i]+dis0[u]<dis[i]) //从小路走向大路，更新大路；
{
dis[i]=dis0[u]+v[u][i];
if(!vis[i])
{
q.push(i);
vis[i]=true;
}
}
if(v0[u][i]!=inf) //当小路可以走
{
if(v0[u][i]*v0[u][i]+dis[u]<dis0[i]) //从大路走向小路，更新小路
{
dis0[i]=v0[u][i]*v0[u][i]+dis[u];
if(!vis[i])
{
q.push(i);
vis[i]=true;
}
}
}
}
}
}
int main()
{
scanf("%lld %lld",&n,&m);
memset(v,inf,sizeof(v));memset(v0,inf,sizeof(v0));//初始化
for(int i=1; i<=m; i++)
{
scanf("%lld %lld %lld %lld",&flag,&a,&b,&c);
if(flag&&c<v0[a][b]) v0[a][b]=v0[b][a]=c;
if(!flag&&c<v[a][b]) v[a][b]=v[b][a]=c;//去重边
}
for(int i=1; i<=n; i++) //floyd更新小路
{
for(int j=i+1; j<=n; j++)
{
for(int k=1; k<=n; k++)
{
if(k==i||k==j)
continue;
if(v0[i][k]+v0[k][j]<v0[i][j])
{
v0[i][j]=v0[i][k]+v0[k][j];
v0[j][i]=v0[i][j];
}
}
}
}
spfa(1);
printf("%lldn",min(dis0[n],dis[n]));
return 0;
}
二叉排序树与文件操作
#include <bits/stdc++.h>
using namespace std;
struct student
{
int num; //学号
int grade; //成绩
};
typedef student ElemType;
typedef struct BSTNode
{
ElemType data;
struct BSTNode *lchild;
struct BSTNode *rchild;
} BSTNode,*BST;
void in_BST(BST &T,int num,int cj)//插入
{
BST p;
p=new BSTNode;
p->data.num=num;
p->data.grade=cj;
p->lchild=p->rchild=NULL;
if(T==NULL)
T=p;
else
{
if(T->data.num>p->data.num)
in_BST(T->lchild,num,cj);
else
in_BST(T->rchild,num,cj);
}
}
void creat(BST &T,int n)//创建 按学号
{
T=new BSTNode;
T=NULL;
int cj;
int num;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&num,&cj);
in_BST(T,num,cj);
}
}
void zbl(BST T)//中序遍历
{
if(T)
{
zbl(T->lchild);
printf("%d %dn",T->data.num,T->data.grade);
zbl(T->rchild);
}
}
//结点数
int jiedianshu(BST T){
if(T==NULL)
return 0;
else
{
return jiedianshu(T->lchild)+jiedianshu(T->rchild)+1;
}
}
int search_val(BST T,int num)//查找学号为num的成绩
{
if(T!=NULL)
{
if(T->data.num==num)
return T->data.grade;
else if(T->data.num>num)
search_val(T->lchild,num);
else
search_val(T->rchild,num);
}
}
int depth(BST T)//二叉排序树深度
{
if(T==NULL)
return 0;
else
return max(depth(T->lchild),depth(T->rchild))+1;
}
int ans=0;
void yez(BST T)//叶子结点数
{
if(T->lchild==NULL&&T->rchild==NULL)
ans++;
else
{
if(T->lchild)
yez(T->lchild);
if(T->rchild)
yez(T->rchild);
}
}
void DeleteBSTree(BST &T,int t)//删除二叉排序树中元素
{
BST p,q,f,s;
p=T;
f=NULL;
while(p)
{
if(p->data.num==t)
break;
f=p;
if(p->data.num>t)
p=p->lchild;
else
p=p->rchild;
}
if(!p)
return;
q=p;
if((p->lchild)&&(p->rchild))
{
s=p->lchild;
while(s->rchild)
{
q=s;
s=s->rchild;
}
p->data.num=s->data.num;
if(q!=p)q->rchild=s->lchild;
else
q->lchild=s->lchild;
delete s;
return;
}
else if(!(p->lchild))
{
p=p->rchild;
}
else if(!(p->rchild))
p=p->lchild;
if(!f) T=p;
else if(q==f->lchild)
f->lchild=p;
else
f->rchild=p;
delete q;
}
void watch()
{
printf("1:中序遍历n");
printf("2:二叉树的深度n");
printf("3:输出所有节点数和叶子节点数n");
printf("4:删除一条学生记录n");
printf("5:查询一条学生记录n");
printf("如果要结束请输入0n");
printf("请输入一个数字选择功能n");
}
int main()
{
BST T;
int n;
printf("请输入n个结点，每个结点两个信息，学号，成绩n");
scanf("%d",&n);//学生的个数
creat(T,n);
while(1){
int tnt,xx;
getchar();
getchar();
system("cls");
watch();
scanf("%d",&tnt);
if(tnt==0)
break;
if(tnt==1){
zbl(T);//中序遍历
}
if(tnt==2)
printf("%dn",depth(T));//二叉树的深度
if(tnt==3){
printf("结点数:%dn",jiedianshu(T));
ans=0;
yez(T);
printf("叶子节点数:%dn",ans);
} //输出所有节点数和叶子节点数
if(tnt==4){
int xyy;
printf("请输入要删除学生的学号n");
scanf("%d",&xyy);
DeleteBSTree(T,xyy);
} //删除一条学生记录
if(tnt==5){
printf("请输入要查询学生的学号n");
scanf("%d",&xx);//查询一条学生记录
printf("%dn",search_val(T,xx));
}
}
return 0;
}
/*
7
100 10
102 50
101 20
104 70
103 100
106 60
105 80
*/
最后
以上就是无心曲奇为你收集整理的数据结构程序设计课程设计的全部内容，希望文章能够帮你解决数据结构程序设计课程设计所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复