王博华数据结构实验报告

更新时间：2023-12-25 13:26:02 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

王博华为推荐度：
相关推荐

软件中外132王博华实验二链表及其多项式相加

Time Limit: 3000MS

Memory Limit: 65536K Accepted: 471

Case Time Limit:1000MS

Total Submissions: 1127

Description

通过有序对输入多项式的各个项，利用单链表存储该一元多项式，并建立的2

个存储一元多项式的单链表，然后完成2个一元多项式的相加，并输出相加后的多项式。

Input

输入数据有多组，对于每组测试数据，第一行一个整数n，表示第一个多项式La的项数；接下来n行，每行表示多项式的一项，包含两个元素，表示系数和指数；接下来一个整数m，表示第二个多项式Lb的项数；接下来m行，每行表示多项式的一项，包含两个元素，表示系数和指数；两个多项式的输入都是按指数从小到大。（n,m<=1000）

Output

La与Lb相加之后的多项式。

按指数从小到大输出，每行一项，用空格把系数和指数分开。

Sample Input

3 1 2 2 3 3 4 3 4 3 2 5 4 6

Sample Output

1 2 6 3 3 4 2 5 4 6

Source

#include #include struct jiegou { int shu,zhishu; struct jiegou *next; } *a,*b,*c; void shuru() { jiegou *p,*q; int i,j,n,m,c,d; scanf(\

p=a=(struct jiegou *)malloc(sizeof(jiegou)); for(i=0;i

{ q=(struct jiegou *)malloc(sizeof(jiegou));

scanf(\p->next=NULL; scanf(\

p=b=(struct jiegou *)malloc(sizeof(jiegou));

for(i=0;i

scanf(\p->next=NULL; }

void jifa() { jiegou *p,*q; int e,d,i;

p=c=(struct jiegou *)malloc(sizeof(jiegou)); a=a->next; b=b->next; while(a!=NULL&&b!=NULL) { if(a->zhishu==b->zhishu) { e=a->shu+b->shu; if(e!=0)

{ q=(jiegou *)malloc(sizeof(jiegou));

p->next=q; p=q; p->shu=e; p->zhishu=a->zhishu;

} b=b->next; a=a->next; } else if(a->zhishuzhishu) { q=(jiegou *)malloc(sizeof(jiegou));

p->next=q; p=q; p->shu=a->shu; p->zhishu=a->zhishu; a=a->next; }

else { q=(jiegou *)malloc(sizeof(jiegou));

p->next=q; p=q; p->shu=b->shu; p->zhishu=b->zhishu; b=b->next; } }

while(a) { q=(jiegou *)malloc(sizeof(jiegou)); p->next=q; p=q; p->shu=a->shu; p->zhishu=a->zhishu; a=a->next; } while(b) { q=(jiegou *)malloc(sizeof(jiegou));

p->next=q; p=q; p->shu=b->shu; p->zhishu=b->zhishu; b=b->next; } p->next=NULL; } void shuchu() { jiegou *p; p=c->next;

while(p) { printf(\ int main () { shuru(); jifa(); shuchu(); }

实验三括号匹配判断算法

Time Limit: 3000MS

Memory Limit: 65536K Accepted: 474

Case Time Limit:1000MS

Total Submissions: 1025

Description

假设在表达式中（［］（））或［（［］［］）］等为正确的格式，［（］）

或（［（））或 (( )])均为不正确的格式。基于栈设计一个判断括号是否正确匹配的算法。

Input

输入数据有多组，每组测试数据一行，一个字符串，只包含 ‘[‘ ，’]’ ，’(‘ ，‘)’ 。

Output

对于每组测试数据，若括号匹配输出yes 否则输出 no。

Sample Input

[]()[] ([[]])[)

Sample Output

yes no

Source

#include #include typedef struct snode{ char data;

struct snode *next; }snode,*linkstack;

void initlinkstack(linkstack *); void linkstackpush(linkstack *,char); int linkstackpop(linkstack *);

int linkstackgettop(linkstack,char *); void matching(char str[]); int main()

{char str[8000]; while(gets(str)) {matching(str); }

return 0; }

void linkstackpush(linkstack *ls,char e)

{linkstack p=(linkstack)malloc(sizeof(snode)); p->data=e;p->next=*ls;*ls=p; }

int linkstackpop(linkstack *ls) {

linkstack p=*ls;

if(*ls==NULL) return 0; (*ls)=(*ls)->next; free(p);

return 1; }

int linkstackgettop(linkstack ls,char *e) {

if(ls==NULL) return 0; *e=ls->data;return 1; }

void initlinkstack(linkstack *ls) {

*ls=NULL; }

void matching(char str[]) {

linkstack s;int k,flag=1;char e; initlinkstack(&s);

for(k=0;str[k]!='\\0'&&flag;k++) {

if(str[k]!='('&&str[k]!=')'&&str[k]!='['&&str[k]!=']'&&str[k]!='{'&&str[k]!='}') continue;

switch(str[k]) {

case '(':case '[':case '{':linkstackpush(&s,str[k]);break; case ')': if(s!=NULL) {

linkstackgettop(s,&e);

if(e=='(') linkstackpop(&s); else flag=0; }

else flag=0; break; case ']': if(s!=NULL) {

linkstackgettop(s,&e);

if(e=='[') linkstackpop(&s); else flag=0; }

else flag=0; break; case '}': if(s!=NULL) {

3 0 5 3 0 1 0 4 1 3

Sample Output

0 1 2 0 1 2

0 1 3 4 2 0 1 4 3 2

Source

#include #include #define MAX 100 int visited[MAX]; typedef struct{ int arc[MAX][MAX];

int numVertexes,numEdges; }MGraph;

void creat(MGraph *G){ int i,j,k;

scanf(\ for(i=0;inumVertexes;i++) for(j=0;jnumVertexes;j++) G->arc[i][j]=0; for(k=0;knumEdges;k++){ scanf(\ G->arc[i][j]=G->arc[j][i]=1; } }

void dfs(MGraph *G,int i){ int j;

visited[i] = 1; printf(\

for(j=1;jnumVertexes;j++){ if(G->arc[i][j]==1 && visited[j]==0){

dfs(G,j); } } }

void DFS(MGraph *G){ int i;

for(i=0;inumVertexes;i++){ visited[i] = 0; }

for(i=0;inumVertexes;i++){ if(visited[i]==0){ dfs(G,i); } }

printf(\}

void BFS(MGraph *G){ int i,j,k;

for(i=0;inumVertexes;i++){ visited[i] = 0; }

for(k=0;knumVertexes;k++){ int Q[MAX],front=0,rear=0; if(visited[k]==0){ printf(\ visited[k]=1; rear=(rear+1)% MAX; i=k; Q[rear]=i; while(front!=rear){ front=(front+1)%MAX; i=Q[front]; for(j=0;jnumVertexes;j++) if(G->arc[i][j]==1 && !visited[j]) { printf(\ visited[j]=1; rear=(rear+1)%MAX; Q[rear]=j; } }

} else continue; }

printf(\}

int main(){

MGraph *Graph;

Graph= (MGraph*)malloc(sizeof(MGraph)); creat(Graph); DFS(Graph); BFS(Graph); printf(\}

实验十八 BST树的构建与应用

Time Limit: 3000MS

Memory Limit: 65536K Accepted: 232

Case Time Limit:1000MS

Total Submissions: 330

Description

实现BST查找及建立以及遍历算法，根据查询的数，建一颗BST树，初始树为