scanf("%d",&a[i]);
//创建链表
CreatLinkList(&L,PN);
//报数删人,输出结果
printf("Result:
\n");
deldata(&L,PN,a);
}
2.设计2前缀算术表达式转换及表达式计算
一、需求分析
1.问题描述:
算术表达式与二叉树之间存在着对应关系,编写把以前缀形式输入的合法算术表达式转换为中缀表达式,再转换为后缀表达式,并求表达式的值。
2.具体目标包括:
(1)把前缀表达式转换为中缀表达式;
(2)输出中缀表达式;
(3)把中缀表达式转换为后缀表达式;
(4)利用栈结构实现后缀表达式的求值;
3.定义栈的抽象数据类型:
ADTStack{
数据对象:
D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}
数据关系:
R1={|ai-1,ai∈D,i=2,...,n}
基本操作:
InitStack(SqStack*S)
Push(SqStack*S,SNodeETypee)
Pop(SqStack*S,SNodeEType*e)
StackEmpty(SqStack*S)
}ADTStack
二、概要设计
1、程序包括两部分
(1)结点类型
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
typedefstructNode
{SNodeETypedata;
structNode*next;
}SElemType;
typedefstructStack
{SElemType*base;
SElemType*top;
}SqStack;
typedefstructQNode{//队列
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
(2)基本操作的实现(见附:
主要源代码)
2、主要模块
三、详细设计(含主要算法的流程图)
1、删除栈顶元素并返回其值的算法
intPop(SqStack*S,SNodeEType*e)
int*e1;
if(S->top==S->base)
returnERROR;
*e=S->top->data;
e1=S->top;
S->top=S->top->next;
free(e1);
returnOK;}
2、BiTreeCreatBiTree(BiTreeT)
{//按前缀形式输入算术表达式,构造二叉链表表示的二叉树T
charch;scanf("%c",&ch);
switch(ch)
{
case'+':
;
case'-':
;
case'*':
;
case'/':
if(!
(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
T->lchild=(BiTNode*)malloc(sizeof(BiTNode));
T->rchild=(BiTNode*)malloc(sizeof(BiTNode));
T->lchild=CreatBiTree(T->lchild);
T->rchild=CreatBiTree(T->rchild);break;
default:
if(!
(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
T->lchild=NULL;
T->rchild=NULL;
}
returnT;
}
实现流程图:
四、运行结果及分析
五、总结
1、调试过程中遇到的问题:
在调试过程中,插入新结点时,结点指针指的位置不对,导致添加后的二叉树不符合;在输出二叉树时由于输出算法错误导致输出不正确,经过网上找了一些材料,最后输出正确。
2、编写程序时必须注意一些细小的问题,对临界问题考虑全面,养成良好的编程习惯。
熟练掌握算术表达式与二叉树的性质与算法,巩固算术表达式之间的转换算法以及后序遍历的递归算法实现树的输出算法。
附:
主要源代码
#include
#include
#include
#defineMAXSIZE100
#defineTElemTypechar
#defineQElemTypechar
#defineSNodeETypefloat
#defineOK1
#defineOVERFLOW0
#defineTRUE1
#defineFALSE0
#defineERROR0
#definestatusint
typedefstructBiTNode
{
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode,*BiTree;
typedefstructNode
{SNodeETypedata;
structNode*next;
}SElemType;
typedefstructStack
{SElemType*base;
SElemType*top;
}SqStack;
typedefstructQNode
{
QElemTypedata;
structQNode*next;
}QNode,*QueuePtr;
typedefstruct
{
QueuePtrfront;
QueuePtrrear;
}LinkQueue;
statusInitQueue(LinkQueue*Q)
{//构造一个空队列Q
if(!
(Q->rear=(QueuePtr)malloc(sizeof(QNode))))
exit(OVERFLOW);
Q->front=Q->rear;
Q->front->next=NULL;
returnOK;}
statusEnQueue(LinkQueue*Q,QElemTypee)
{//插入以e为Q的新的队尾元素
QueuePtrp;
if(!
(p=(QueuePtr)malloc(sizeof(QNode))))
exit(OVERFLOW);
p->data=e;p->next=NULL;
Q->rear->next=p;Q->rear=p;
returnOK;
}
statusDeQueue(LinkQueue*Q,QElemType*e)
{//删除Q的队头元素,用e返回其值
QueuePtrp;
p=Q->front->next;*e=p->data;
Q->front->next=p->next;
if(Q->rear==p)Q->rear=Q->front;
free(p);
returnOK;
}
statusInitStack(SqStack*S)
{//构造一个空栈S
S->base=(SElemType*)malloc(sizeof(SElemType));
if(!
S->base)
exit(OVERFLOW);//存储分配失败
S->top=S->base;
returnOK;
}//InitStack
voidPush(SqStack*S,SNodeETypee)
{//插入元素e为新的栈顶元素
SElemType*e1;
e1=(SElemType*)malloc(sizeof(SElemType));
e1->next=S->top;e1->data=e;S->top=e1;}//Push
statusPop(SqStack*S,SNodeEType*e)
{//若栈不空,则删除S的栈顶元素,用e返回其值,并返回OK,否则返回ERROR
SElemType*e1;
if(S->top==S->base)
returnERROR;
*e=S->top->data;
e1=S->top;
S->top=S->top->next;
free(e1);
returnOK;
}
statusStackEmpty(SqStack*S)
{//判断栈S是否为空,若不空返回TRUE,否者返回FALSE
if(S->top==S->base)
returnTRUE;
else
returnFALSE;
}
BiTreeCreatBiTree(BiTreeT)
{//按前缀形式输入算术表达式
//构造二叉链表表示的二叉树T
charch;
scanf("%c",&ch);
switch(ch)
{
case'+':
;
case'-':
;
case'*':
;
case'/':
if(!
(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
T->lchild=(BiTNode*)malloc(sizeof(BiTNode));
T->rchild=(BiTNode*)malloc(sizeof(BiTNode));
T->lchild=CreatBiTree(T->lchild);
T->rchild=CreatBiTree(T->rchild);
break;
default:
if(!
(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;T->lchild=NULL;
T->rchild=NULL;
};returnT;
}
statusInOrderT(BiTreeT)
{//中序遍历二叉树
if(T){InOrderT(T->lchild);
printf("%c",T->data);
InOrderT(T->rchild);
}
returnOK;
}
statusAfterOrderT(BiTreeT,LinkQueue*Q)
{
chare;//后序遍历二叉树
if(T){AfterOrderT(T->lchild,Q);
AfterOrderT(T->rchild,Q);
printf("%c",T->data);e=T->data;
EnQueue(Q,e);
}returnOK;
}
statusJisuan(SNodeEType*e1,SNodeETypee2,charch)
{switch(ch)
{
case'+':
*e1=*e1+e2;break;
case'-':
*e1=e2-*e1;break;
case'*':
*e1=*e1*e2;break;
case'/':
*e1=e2/(*e1);break;
}
returnOK;
}
statusOper(LinkQueue*Q)
{SqStack*S;charch;intsag=1;
SNodeETypee1,e2,e;
if(!
(S=(SqStack*)malloc(sizeof(SqStack))))
exit(OVERFLOW);
while(Q->front!
=Q->rear)
{DeQueue(Q,&ch);
switch(ch)
{case'+':
;
case'-':
;
case'*':
;
case'/':
Pop(S,&e1);Pop(S,&e2);
Jisuan(&e1,e2,ch);
Push(S,e1);break;
default:
if(sag==1)
{printf("(有几个变量?
按行输入)为变量赋值:
");sag=0;}
scanf("%f",&e);Push(S,e);}}Pop(S,&e1);
printf("结果为:
%3f\n",e1);returnOK;}
voidmain()
{BiTNode*T;LinkQueue*Q;
Q=(LinkQueue*)malloc(sizeof(LinkQueue));
InitQueue(Q);
T=(BiTNode*)malloc(sizeof(BiTNode));
T->lchild=NULL;T->rchild=NULL;
printf("按前缀形式输入算术表达式\n");
printf("请输入前缀表达式:
");
T->lchild=CreatBiTree(T->lchild);
printf("中序表达式:
");
InOrderT(T->lchild);printf("\n");
printf("后序表达式:
");
AfterOrderT(T->lchild,Q);
printf("\n");Oper(Q);}
3.设计3矩阵乘法和加法算法的应用
一、需求分析
1.问题描述:
设A=,给定A上的关系R为R={,,,},求R的传递闭包。
2.具体目标:
设定一个关系R(矩阵),执行本程序,自动求出R的传递闭包。
二、概要设计
1.函数功能在main函数中实现。
函数调用关系:
在Main()中调用work(),实现程序的主要功能。
intmain(intargc,char*argv[])
{
intR[10][10];
intn,i,j;
printf("请输入关系矩阵的维数\n");
scanf("%d",&n);
printf("请输入关系矩阵R\n");
for(i=0;ifor(j=0;jscanf("%d",&R[i][j]);
}
}
work(R,n);
return0;
}
2.算法描述:
在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。
R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。
一般用B表示定义在具有n个元素的集合X上关系R的n×n二值矩阵,则传递闭包的矩阵B+=B+B2+B3+……+(B)n 式中矩阵运算时所有乘法都用逻辑与代替,所有加法都用逻辑或代替。
上式中的操作次序为B,B(B),B(BB),B(BBB),以此类推。
所以在运算的每一步我们只需简单地把现有结果乘以B,完成矩阵的n次乘法即可。
三、详细设计
1.主程序(实现主要功能)
intmain(intargc,char*argv[])
{
intR[10][10];
intn,i,j;
printf("请输入关系矩阵的维数\n");
scanf("%d",&n);
printf("请输入关系矩阵R\n");
for(i=0;ifor(j=0;jscanf("%d",&R[i][j]);
}
}
work(R,n);
return0;
}
2.voidwork(intR[10][10],intn)
{
求矩阵R[][]的传递闭包;
将输入的矩阵R赋值给矩阵M;
用M的行乘以R的列得到Rn,并将Rn赋值给M;
最后将R1R2R3R4…….Rn相加的结果赋给R;
将矩阵R[][]中非0元素置换为1;
输出传递闭包;
}
四、运行结果及分析
正确的运行结果:
五、总结
编写程序过程中,由于对矩阵相乘的性质和算法掌握不牢固,所以在程序运行遇到了一些问题。
在集合X上的二元关系R的传递闭包是包含R的X上的最小的传递关系。
R的传递闭包在数字图像处理的图像和视觉基础、图的连通性描述等方面都是基本概念。
这些都是本实验设计所需的一些基本知识,但是由于学习是掌握不牢固,拿到题目时只能先巩固基础知识,这样就花费了不少时间。
附:
主要源代码
//#include"stdafx.h"
#include"stdio.h"
#include"stdlib.h"
voidwork(intR[10][10],intn){//求矩阵R[][]的传递闭包
inti,j,k,m;
intM[10][10];
inta=0;
for(i=0;ifor(j=0;jM[i][j]=R[i][j];
}
for(m=1;mfor(i=0;i