9299.net
大学生考试网 让学习变简单
赞助商链接
当前位置:首页 >> 其它课程 >>

西电软件技术基础第二、三次上机大作业

西电软件技术基础第二、三次上机大作业


括号匹配
一、目的: 利用栈的运算编写一个程序,判断给定表达式中所含括号是否正确配对,如 果括号正确配对则返回值 1;否则返回值 0。 二、流程图:

开始

依次读入字符

否是
是否为(或{或[

是否为“#”

栈是否为空

是 否否是
该字符进栈 是否与栈顶匹配 Return 0 Return 0 栈顶元素出栈 Return 1



结束

三、 代码实现:

#include "stdafx.h" #include "stdio.h" #include "stdlib.h" #define maxsize 1024 typedef char datatype; typedef struct { datatype data[maxsize]; int Top; }SeqStack; int correct(); int push(SeqStack*,datatype& ); int pop(SeqStack*,datatype&); int empty(SeqStack*); int gettop(SeqStack*,datatype&); void initstack(SeqStack*&); void main () { int k=0; printf("请输入字符串(输入#结束):\n"); k=correct(); if(k) printf("括号正确配对"); else printf("括号不配对"); printf("\n"); } int correct() { int m,l,t; char x,y; datatype e; SeqStack*s; initstack(s); while((x=getchar())!='#') { m=0;l=0;t=0; if((x=='{')||(x=='[')||(x=='(')) push(s,x); else if((x=='}')||(x==']')||(x==')')) {

m=1; if(empty(s)) {t=1;break;} gettop(s,y); switch(y) { case '{' :if(x=='}') l=pop(s,e); case '[' :if(x==']') l=pop(s,e); case '(' :if(x==')') l=pop(s,e); break; } } if(m!=l)break; } if(!empty(s)||t) return 0; else return 1; } void initstack(SeqStack*&S)//构建空顺序栈 { S=(SeqStack*)malloc(sizeof(SeqStack)); S->Top=0; } int push(SeqStack*S,datatype&e)//顺序栈进栈 { if(S->Top>=maxsize-1) { printf("栈上溢"); return 0; } else {S->data[++S->Top]=e; return 1; } }

int gettop(SeqStack*S,datatype&e)//取栈顶 { if(empty(S)) { printf("栈下溢"); return 0; } else {e=S->data[S->Top]; return 1; } } int empty(SeqStack*S)//判断栈是否为空

{ }

if(S->Top<=0) return 1; else return 0;

int pop(SeqStack*S,datatype&e) { if(empty(S)) { printf("栈下溢"); return 0; } else { e=S->data[S->Top--]; return 1; } }

四、结果:

稀疏矩阵相加
一、目的: 掌握用三元组表示稀疏矩阵的原理,编写一个程序,实现两个稀疏矩阵相加,结果存放 在三元组表中。 二、流程图:
开始

K,l,e=0;

读入三元组表 A,B

A、B 中都有元素未被取到?





A 中第 k 个元素和 B 中第 l 个元素的行列 值均相同?

A 中元素已取完

否 否
第 k 个元素位于第 l 个元素之前?




将 B 中剩余元 素整体赋给 C 将 A 中剩余元 素整体赋给 C

将两个元素的和赋给 C 中 第 e 个元素并记录行列值

否 是
将第 k 个元素赋给 C 并记录其行列值 更新 k, l, e 的值, 进行新一轮赋值 将第 l 个元素赋给 C 并记录其行列值

结束

三、代码实现: #include"stdafx.h" #include<stdio.h> #include<stdlib.h> #define max 20 #define zero 0 typedef struct{ int i,j,v; //行、列、数值 }node; typedef struct{ node data[max]; int m,n,x; //稀疏矩阵行数、列数及非 0 元个数 }Spmatrix; Spmatrix * Setmatrix(){ //建三元组表 Spmatrix *S; S=(Spmatrix *)malloc(sizeof(Spmatrix)); printf("请输入矩阵行数、列数及非 0 元素个数:\n"); scanf("%d%d%d",&S->m,&S->n,&S->x); printf("建立三元组表:\n"); for(int n=0;n<S->x;n++) scanf("%d%d%d",&S->data[n].i,&S->data[n].j,&S->data[n].v); return S; } void Spmatrixout(Spmatrix *S){ //输出矩阵 int a,b,e; e=0; for(a=1;a<=S->m;a++){ for(b=1;b<=S->n;b++){ if(S->data[e].i==a&&S->data[e].j==b){ printf("%-5d",S->data[e].v); e++; } else printf("%-5d",zero); } printf("\n"); } } Spmatrix *Matrixadd(Spmatrix *A,Spmatrix *B) { //两稀疏矩阵相加 Spmatrix *C; C=(Spmatrix *)malloc(sizeof(Spmatrix)); if(A->m>=B->m) C->m=A->m; else C->m=B->m;

if(A->n>=B->n) C->n=A->n; else C->n=B->n; C->x=0; int temp; int k=0,l=0,e=0; while (k<A->x&&l<B->x) { if((A->data[k].i==B->data[l].i)&&(A->data[k].j==B->data[l].j)) {temp=A->data[k].v+B->data[l].v; if (!temp)//相加不为零,加入 C { C->data[e].i=A->data[k].i; C->data[e].j=A->data[k].j; C->data[e++].v=temp; } k++;l++; } if (((A->data[k].i==B->data[l].i)&&(A->data[k].j<B->data[l].j))||(A->dat a[k].i<B->data[l].i))//将 A 中三元组加入 C {C->data[e].i=A->data[k].i; C->data[e].j=A->data[k].j; C->data[e++].v=A->data[k].v; k++; } if (((A->data[k].i==B->data[l].i)&&(A->data[k].j>B->data[l].j))||(A->dat a[k].i>B->data[l].i))//将 B 中三元组加入 {C->data[e].i=B->data[l].i; C->data[e].j=B->data[l].j; C->data[e++].v=B->data[l].v; l++; } } while (k<A->x)//将 A 中剩余三元组加入 C {C->data[e].i=A->data[k].i; C->data[e].j=A->data[k].j; C->data[e++].v=A->data[k].v; k++; } while (l<B->x)//将 B 中剩余三元组加入 C {C->data[e].i=B->data[l].i; C->data[e].j=B->data[l].j; C->data[e++].v=B->data[l].v;

l++; } C->x=e-1; return C; }

void main() { Spmatrix *A,*B,*C; A=Setmatrix(); printf("稀疏矩阵 A:\n"); Spmatrixout(A); B=Setmatrix(); printf("稀疏矩阵 B:\n"); Spmatrixout(B); C=Matrixadd(A,B); printf("矩阵相加后稀疏矩阵 C:\n"); Spmatrixout(C); } 四、结果:

二叉树遍历
一、目的: 掌握二叉树遍历的原理,并使用中序遍历实现学生名字加虚字符的遍历。 二、流程图:

开始

读入字符串建立完全二叉树

从根结点开始, 按照先左孩子, 再中间 结点,然后右孩子的顺序遍历二叉树

遍历到的结点 是虚字符?




输出当前结点

已遍历整个二 叉树?
否 是

取下一个结点

结束

三、代码实现: #include "stdafx.h" #include "stdlib.h" #include "stdio.h" #define maxsize 1024; typedef char datatype; typedef struct node { datatype data; struct node *lchild,*rchild; }bitree; bitree *root; bitree *creat() { char ch; bitree *q[1024]; int front,rear; bitree *root,*s; root=NULL; front=1; rear=0; while((ch=getchar())!='#') { s=NULL; if(ch!='@') { s=(bitree*)malloc(sizeof(bitree)); s->data=ch; s->lchild=NULL; s->rchild=NULL; } rear++; q[rear]=s; if(rear==1) root=s; else{ if(s&&q[front]) if(rear%2==0) q[front]->lchild=s; else q[front]->rchild=s; if(rear%2==1) front++; } }

return root; } void inorder(bitree *p) { if(p!=NULL) { inorder(p->lchild); printf("%c",p->data); inorder(p->rchild); } } void main() { bitree *A; printf("请输入字符串: (输入“#”结束)\n"); A=creat(); inorder(A); printf("\n"); } 四结果:

邻接表转化为邻接矩阵
一、目的: 掌握邻接表和邻接矩阵的存储方式,编写程序实现邻接表向邻接矩阵的转换。 二、流程图:

开始

读入顶点和边的信息, 用 头插法建立邻接表

建立 n*n 的空邻接矩阵 (n 为顶点数目)

从邻接表的第 1 个顶点开始遍历整 个表,并在邻接矩阵中对应有边的 位置赋值 1,其余位置赋值 0

输出邻接矩阵

结束

三、代码实现: #include<stdio.h> #include<stdlib.h> #define max 20 #define digit 1 #define zero 0 typedef struct{ int num; char data;

}Vertex; typedef struct{ int n; //顶点数 int e; //弧数 Vertex vexs[max]; int edges[max][max]; }MGraph; typedef struct node{ int adjvex; node *nextarc; char info; }ARCNODE; //邻接表的结点结构 typedef struct{ char vexdata; ARCNODE *firstarc; }VEXNODE; //邻接表的表头结点 typedef struct{ int vexnum,arcnum; //顶点数、弧数 VEXNODE ve[max]; }ALGraph; //邻接表类型 ALGraph *Creat_alg(){ //创建邻接表 ALGraph *alg; int i,n,e,b,a; char ch; ARCNODE *AR; alg=(ALGraph *)malloc(sizeof(ALGraph)); printf("输入顶点数:"); scanf("%d",&n); printf("输入弧数:"); scanf("%d",&e); alg->vexnum=n; alg->arcnum=e; printf("输入顶点信息:\n"); for(i=0;i<n;i++){ scanf("%s",&ch); alg->ve[i].vexdata=ch; alg->ve[i].firstarc=NULL; } printf("输入弧的信息(弧的两端点):\n"); for(i=0;i<e;i++){ scanf("%d%d",&a,&b); AR=(ARCNODE *)malloc(sizeof(ARCNODE)); AR->adjvex=b; AR->info=alg->ve[b].vexdata;

AR->nextarc=alg->ve[a].firstarc; alg->ve[a].firstarc=AR; AR=(ARCNODE *)malloc(sizeof(ARCNODE)); AR->adjvex=a; AR->info=alg->ve[a].vexdata; AR->nextarc=alg->ve[b].firstarc; alg->ve[b].firstarc=AR; } return alg; } void ALGout(ALGraph *alg){ //邻接表输出 int i,n1; ARCNODE *p; VEXNODE *q; n1=alg->vexnum; for(i=0;i<n1;i++){ q=&alg->ve[i]; printf("%c",q->vexdata); p=q->firstarc; while(p!=NULL){ printf("─→"); printf("%c",p->info); p=p->nextarc; } printf("\n"); } } MGraph *ALG_change_MG(ALGraph *alg){ //将邻接表转换为邻接矩阵 MGraph *mg; int i,n1; mg=(MGraph *)malloc(sizeof(MGraph)); mg->n=alg->vexnum; mg->e=alg->arcnum; n1=mg->n; for(i=0;i<n1;i++){ mg->vexs[i].num=i; mg->vexs[i].data=alg->ve[i].vexdata; } ARCNODE *p; for(i=0;i<n1;i++){ p=alg->ve[i].firstarc; while(p!=NULL){ mg->edges[i][p->adjvex]=1; mg->edges[p->adjvex][i]=1;

p=p->nextarc; } } return mg; } void MGout(MGraph *mg){ //输出邻接矩阵 int i,j,k; k=mg->n; for(i=0;i<k;i++){ for(j=0;j<k;j++){ if(mg->edges[i][j]==1) printf("%-5d",digit); else printf("%-5d",zero); } printf("\n"); } } void main(){ MGraph *mg; ALGraph *alg; printf("建立无向图的邻接表:\n"); alg=Creat_alg(); printf("邻接表输出:\n"); ALGout(alg); mg=ALG_change_MG(alg); printf("邻接矩阵输出:\n"); MGout(mg); }

四、结果:



推荐相关:
网站首页 | 网站地图
All rights reserved Powered by 大学生考试网 9299.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com