计算机软件专业技术基础上机编程

计算机软件技术基础上机编程

————————————————————————————————作者：————————————————————————————————日期：

计算机软件技术基础上机编程

上机题一：线性表

1.建立单向链表；表长任意；

2.可交互输出单链表中的内容；

3.编写算法计算出自己所建单链表的长度并输出；

4.输出自己所建立单链表中的第K个结点，并将剩余结点输出；

5.将单链表倒排并输出结果

#include

#include

typedef int datatype;

typedef struct node

{ datatype data;

struct node *next;

}linklist;

linklist*Creatlist() //建立链表//

{ int x;

linklist *h, *s;

h=NULL;

printf("\n please input the date end with 0:\n");

printf("\n Input data:");

scanf("%d",&x);

while(x!=0)

{ s=malloc(sizeof(linklist));

s->data=x;

s->next=h;

h=s;

printf("\n Input data:");

scanf("%d",&x);

}

return h;

}

void Putlist(linklist *h) //输出单链表中的内容// { linklist *s;

s=h;

while(s!=NULL)

{ printf("%4d",s->data);

s=s->next;

}

}

int Long(linklist *h) //计算链表的长度// { int i=0;

linklist *s;

s=h;

while(s!=NULL)

{ i++;

s=s->next;

}

return(i);

}

void Delete(linklist *h,int k) //删除链表中第k个结点// { int i=0;

linklist *p1,*p2;

p1=h;

if(k==1) { h=h->next;free(p1);}

else

{

while(i

{

i++;

p2=p1;

p1=p1->next;

}

p2->next=p1->next;

free(p1);

}

}

linklist *Nixu(linklist *h) //逆序输出链表// { linklist *r,*q,*p;

r=h;

p=r->next;

q=p->next;

if(h==NULL)

printf("the linklist is empty\n"); / /空表//

while(q!=NULL&&h!=NULL)

{p->next=r;

r=p;

p=q;

q=q->next;

}

h->next=NULL;

p->next=r;

return(p); //返回根结点// }

main()

{ int k,x;

linklist *h;

do //输出菜单// { printf("\nqing shu ru ming ling:\n");

printf("1.jian li lian biao;\n");

printf("2.shu chu lian biao zhong de nei rong;\n");

printf("3.shu chu lian biao de chang du;\n");

printf("4.shan chu di K ge jie dian;\n");

printf("5.jiang lian biao dao xu bing shu chu;\n");

printf("6.tui chu cheng xu;\n");

printf("qing shu ru 1--6 de shu zi:\n");

scanf("%d",&x);

if(x<1||x>6) printf("error!\n");

else

switch(x)

{ case 1:h=Creatlist();break;

case 2:Putlist(h);break;

case 3:printf("lian biao de chang du shi %d",Long(h));break;

case 4:printf("Input the node you want to delete:\n");

scanf("%d",&k);

Delete(h,k);Putlist(h);break;

case 5:h=Nixu(h);Putlist(h);break;

case 6:exit(0);break; //退出程序// }

}

while(1);

}

退出程序；

上机题二：二叉树

1.动态交互建立二叉树，结点个数任意；

2.分别用DLR,LDR,LRD三种方式对二叉树进行遍历并输出结果；

3.计算二叉树中结点个数并输出；

4.计算二叉树深度并输出

源程序：

#include "stdio.h"

#include "malloc.h"

struct TreeNode

{ int data;

struct TreeNode *Lchild ;

struct TreeNode *Rchild;

};

struct TreeNode *create( ) // 用于建立二叉树的子函数//

{ struct TreeNode *T;

int a;

scanf("%d",&a);

if (a==0) return NULL;

else // 动态建立二叉树// { T=(struct TreeNode *)malloc(sizeof(struct TreeNode));

T->data=a; // 建立根结点//

T->Lchild=create( ); // 递归建立左子树//

T->Rchild=create( ); // 递归建立右子树//

}

return (T);

}

void Pre (struct TreeNode *T) // 用于进行先序遍历的子函数//

{ if (T!= NULL)

{ printf ("%5d",T->data); // 访问根结点//

Pre (T->Lchild); // 递归访问左子树//

Pre (T->Rchild); // 递归访问右子树//

}

}

void Mid(struct TreeNode *T) // 用于进行中序遍历的子函数//

{

if ( T != NULL)

{ Mid (T->Lchild); // 递归访问左子树//

printf("%5d",T->data); // 访问根结点

Mid (T->Rchild); // 递归访问右子树// }

}

void Post (struct TreeNode *T) // 用于进行后序遍历的子函数//

{ if ( T != NULL)

{ Post (T->Lchild); // 递归访问左子树//

Post (T->Rchild); // 递归访问右子树//

printf("%5d",T->data);

}

}

void visit(struct TreeNode *T) // 用于访问二叉树的子函数//

{ printf("the result of DLR:"); Pre(T);

printf("\n");

printf("the result of LDR:"); Mid(T);

printf("\n");

printf("the result of LRD:"); Post(T);

printf("\n");

}

int leaf(struct TreeNode *T) // 用于计算叶子结点的子函数//

{ int a,b;

if(T==NULL) return (0);

else if(T->Lchild==NULL&&T->Rchild==NULL) // 判断该结点是叶子结点//

return (1);

else

{ a=leaf(T->Lchild); // 递归计算左子树上叶子数// b=leaf(T->Rchild); // 递归计算右子树上叶子数//

return (a+b+1);

}

}

int max(int x,int y) // 用于取两数的较大值的子函数// { if(x>y) return (x);

else return (y);

int deep(struct TreeNode *T) // 用于计算二叉树深度的子函数//

{ int k=0;

if(T==NULL) return (0);

else if(T->Lchild==NULL&&T->Rchild==NULL)// 该结点有孩子，深度增加1 //

return (1);

else return (1+max(deep(T->Lchild),deep(T->Rchild)));// 递归求取树的深度//

}

main()

{ int m,n,p;

struct TreeNode *T;

printf("create a tree\n");

T=create(); // 建立二叉树// printf("1.visit the tree\n"); // 打印菜单//

printf("2.putout the total number of node\n");

printf("3.putout the depth of the tree\n");

printf("4.exit\n");

while(1)

{ printf("\nplease input 1-4: "); // 完成菜单的相应功能//

scanf("%d",&m);

if(m==1) visit(T);

if(m==2) {n=leaf(T); printf("the total number of leaves in the tree is %d\n",n);}

if(m==3) if(m==3) {p=deep(T); printf("the depth of the tree is %d\n",p);}

if(m==4) break;

}

}

调试结果：

create a tree

1 0

2 5 0 4 0 6 8 96 0 0 0 56 85 0 0 69 0 0 0 2 5 0 0 0

1.visit the tree

2.putout the total number of node

3.putout the depth of the tree

4.exit

please input 1-4: the total number of leaves in the tree is 10

please input 1-4:

please input 1-4:

please input 1-4:

please input 1-4:

please input 1-4: 1

the result of DLR: 1 2 5 4 6 8 96 56 85 69

the result of LDR: 1 5 4 96 8 6 85 56 69 2

the result of LRD: 96 8 85 69 56 6 4 5 2 1

please input 1-4: 2

the total number of leaves in the tree is 10

please input 1-4: 3