-
算法与数据结构课程设计
姓名:
学号:
实验
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