关键词不能为空

当前您在: 主页 > 英语 >

算法与数据结构课程设计

作者:高考题库网
来源:https://www.bjmy2z.cn/gaokao
2021-01-25 09:38
tags:

-

2021年1月25日发(作者:galante)

算法与数据结构课程设计








姓名:

学号:


实验
1
设计循环单链表的结点结构,
并按要求处理
函数和过程

void fun(Node *head,int *len)
{
if(head==null)
return
Node *p=head;
while(p!=null)
{





p=p->next;




//
输出节点中的数据

printf(




//
节点数加
1



*len++;
}
}

实验
2
设有
n
个人围坐成一圈,按要求报数,每次
淘汰一 个,知道所有人淘汰。试用数据结构
表示出来

#include
#include
intn,s,m,out,a[100];















/*n
为所有人数,
out
为出局的人
*/
voidjosegh( );
void main()
{
int i;
printf (
printf (
printf (
for (i = 1; i <=n; i++)














/*
定义数组
a[100],
按顺序赋值

*/
a[i] = i;
while (n != 0)
josegh ( );
system(
}
void josegh ( )












/*
每当出局一个人,
n

1
,数组重新排列
*/
{
out = s + m - 1;
while (out > n)
out-= n;
printf (
n--;
s=out;
while (out <= n)
a[out++] = a[out+1];
}

实验
3
设单链表中存放
n
个字符,
试用栈判断该字
符串是否对称,如
xyzzyx


#include
#include
#include
#define LEN sizeof(struct node)
#define MAX 147
struct node
{

char cc;

struct node *next;
};
int judge(struct node *head,intlen)
{

struct node *top,*p1,*p2;

top = NULL;

p1 = head->next;

for(int i = 0 i
{


p2 = (struct node *)malloc(LEN);


p2->cc = p1->cc;


p2->next = top;


top = p2;


p1 = p1->next;

}

if(len%2 == 1)


p1 = p1->next;

p2 = top;

for(i = 0 i
{


if(p2->cc != p1->cc)



break;


top = p2->next;


p1 = p1->next;


p2 = top;

}

if(!top)



return 1;

else


return 0;
}

int main()
{

int n=0;

charstr[MAX];

struct node *head,*p;

head = p = (struct node *)malloc(LEN);

head->next = p->next = NULL;

















}

printf(
亲、请输入一个字符串:
n
gets(str);
intlen = strlen(str);
while(n {

p = (struct node *)malloc(LEN);

p->cc = str[n];

p->next = head->next;

head->next = p;

n++;
}
int flag = judge(head,len);
if(flag)

printf(
是一个回文
!n
else

printf(
不是一个回文
!n
return 0;
实验
4
对给定任意图建立邻接表并输出,
实现图的
广度优先遍历

#include
//#include
#define INFINITY 32767
#define MAX_VEX 20 //
最大顶点个数

#define QUEUE_SIZE (MAX_VEX+1) //
队列长度

using namespace std;
bool *visited;

//
访问标志数组

//
图的邻接矩阵存储结构

typedefstruct{


char *vexs; //
顶点向量

int arcs[MAX_VEX][MAX_VEX]; //
邻接矩阵

intvexnum,arcnum; //
图的当前顶点数和弧数

}Graph;
//
队列类

class Queue{
public:
voidInitQueue(){
base=(int *)malloc(QUEUE_SIZE*sizeof(int));
front=rear=0;


}
voidEnQueue(int e){
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE;


}
voidDeQueue(int&e){




e=base[front];
front=(front+1)%QUEUE_SIZE;


}
public:
int *base;
int front;
int rear;
};
//

G
中查找元素
c
的位置

int Locate(Graph G,char c){
for(int i=0;i<;i++)
if([i]==c) return i;
return -1;
}
//
创建无向网

voidCreateUDN(Graph &G){
int i,j,w,s1,s2;
chara,b,temp;
printf(
输入顶点数和弧数
:
scanf(


temp=getchar(); //
接收回车

=(char *)malloc(*sizeof(char)); //
分配顶点数目

printf(
输入
%d
个顶点
.n


for(i=0;i<;i++){ //
初始化顶点

printf(
输入顶点
%d:
scanf(




temp=getchar(); //
接收回车



}


for(i=0;i<;i++) //
初始化邻接矩阵

for(j=0;j<;j++)
[i][j]=INFINITY;
printf(
输入
%d
条弧
.n


for(i=0;i<;i++){ //
初始化弧

printf(
输入弧
%d:
scanf(
输入一条边依附的顶点和权值





temp=getchar(); //
接收回车





s1=Locate(G,a);




s2=Locate(G,b);
[s1][s2]=[s2][s1]=w;


}
}
//

G
中顶点
k
的第一个邻接顶点

intFirstVex(Graph G,int k){


if(k>=0 && k<){ //k
合理

for(int i=0;i<;i++)
if([k][i]!=INFINITY) return i;


}
return -1;
}
//
G
中顶点
i
的第
j
个邻接顶点的下一个邻接顶点

intNextVex(Graph G,inti,int j){


if(i>=0 && i<&& j>=0 && j<){ //i,j
合理

for(int k=j+1;k<;k++)
if([i][k]!=INFINITY) return k;


}
return -1;
}
//
深度优先遍历

void DFS(Graph G,int k){
int i;


if(k==-1){ //
第一次执行
DFS

,k

-1
for(i=0;i<;i++)
if(!visited[i]) DFS(G,i); //
对尚未访问的顶点调用
DFS


}
else{
visited[k]=true;
printf(
访问第
k
个顶点

for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //

k
的尚未访问的邻接顶点
i
递归调用
DFS


}
}
//
广度优先遍历

void BFS(Graph G){
int k;


Queue Q; //
辅助队列
Q
eue();
for(int i=0;i<;i++)
if(!visited[i]){ //i
尚未访问

visited[i]=true;
printf(
e(i); //i
入列

while(!=){
e(k); //
队头元素出列并置为
k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w

k
的尚未访问的邻接顶点

visited[w]=true;
printf(
e(w);










}






}




}
}
//
主函数

void main(){
int i;


Graph G;
CreateUDN(G);
visited=(bool *)malloc(*sizeof(bool));

printf(
广度优先遍历
:
for(i=0;i<;i++)
visited[i]=false;
DFS(G,-1);
printf(
深度优先遍历
:
for(i=0;i<;i++)
visited[i]=false;
BFS(G);
printf(
程序结束
.n
}

实验
5
建立二叉树,实现先序、中序遍历,输出结


#include
#include
#define STACK_INIT_SIZE

10




//
栈的初始长度

#define STACKINCREMENT

5





//
栈的追加长度

typedefstructbitree{
char data;
structbitree *lchild,*rchild;






}bitree;










//
二叉树结点定义

typedefstruct {
bitree **base;
bitree **top;
intstacksize;






}sqstack;






//
链栈结点定义
top
栈顶


base
栈底且栈元素是指向二叉树结点的
二级指针

//
建立一个空栈

intinitstack(sqstack *s)
{s->base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //
栈底指向开辟空间

if(!s->base) exit(1);

















//
抛出异常


s->top=s->base;





















//
栈顶
=
栈尾表示栈空


s->stacksize=STACK_INIT_SIZE;










//
栈长度为开辟空间大小

return 1;
}
//
进栈

int push(sqstack *s,bitree *e)













{if(s->top-s->base>=s->stacksize)


//
如果栈满追加开辟空间




{s->base=(bitree *)realloc (s->base,(s->stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s->base) exit(1);




//
抛出异常


s->top=s->base+s->stacksize;




//
感觉这一句没用

s->stacksize+=STACKINCREMENT;}





*(s->top)=e;s->top++;







//
进栈栈顶后移

return 1;

}

-


-


-


-


-


-


-


-



本文更新与2021-01-25 09:38,由作者提供,不代表本网站立场,转载请注明出处:https://www.bjmy2z.cn/gaokao/565145.html

算法与数据结构课程设计的相关文章