实验四.
稀疏矩阵的三元组顺序表示方法及基本操作的实现（建立、输出、转置）并实现一个主菜单来实现。
#include
#define maxsize 50
#define maxrow 10
#define maxcol 10
typedef struct {
int i,j;
int data;
}triple;
typedef struct {
triple elem[maxsize+1];
int mu,nu,tu;
}tsmatrix;
void createsmatrix (tsmatrix *t){
t=(tsmatrix*)malloc(sizeof(tsmatrix));
if(!t) exit(0); t->mu=0; t->nu=0; t->tu=0;
}
void transposesmatrix(tsmatrix m,tsmatrix*t){
int q=1,col,p;
t->mu=m.nu;t->nu=m.mu;t->tu=m.tu;
if(t->tu){
q=1;
for(col=1;col<=m.nu;col++)
for(p=1;p<=m.tu;++p)
if(m.elem[p].j==col){
t->elem[q].i=m.elem[p].j;
t->elem[q].j=m.elem[p].i;
t->elem[q].data=m.elem[p].data;
++q;
}
}
}
void scanftsmatrix(tsmatrix *t){
int count;
printf("enter the nums of matrix's rows:\n");
scanf("%d",&t->mu);
printf("enter the nums of matrix's columns:\n");
scanf("%d",&t->nu);
printf("enter the nums of matrix's datas:\n");
scanf("%d",&t->tu);
for(count=1;count<=t->tu;count++){
printf("enter the non-zero nums'row,column,data:\n");
scanf("%d%d%d",&t->elem[count].i,&t->elem[count].j,&t->elem[count].data); }
}
/*void printftsmatrix(tsmatrix*t){
int counter,col;
printf("the xishu juzheng is :\n");
for(counter=1;counter<=t->tu;){
for(col=1;col<=t->nu;col++){
if(t->elem[counter].j==col) {
printf("%d\t",t->elem[counter].data);
counter++;
if(t->elem[counter].i==t->elem[counter-1].i) ;
else if(col==t->nu) printf("\n");
else {for(col++;col<=t->nu;col++)printf("*\t");
printf("\n"); }
}
else printf("*\t");
}
}
}*/
void printftsmatrix(tsmatrix*t){
int counter,a[maxrow][maxcol]={0},row,col;
int*p;
p=&a;
printf("the sparse matrix is :\n");
for(counter=1;counter<=t->tu;counter++){
a[t->elem[counter].i-1][t->elem[counter].j-1]=t->elem[counter].data;
}
for(row=1;row<=t->mu;row++){
for(col=1;col<=t->nu;col++){
printf("%d\t",*p);
p++;
}
printf("\n");
p=p+maxcol-col+1;
}
}
void main(){
tsmatrix T,M;int x;char character/*zifu*/,n;
createsmatrix(&T);
scanftsmatrix(&T);
while(character!='#'){
printf("choice:1--transposesmatrix;2--printftsmatrix\n");
printf("enter the num for your choice\n");
scanf("%d",&x);
switch(x){
case 1:transposesmatrix(T,&M);
printftsmatrix(&M);
break;
case 2:printftsmatrix(&T);
break;
}
n=getchar();
printf("enter one char'#' for your choice to quit:\n");
scanf("%c",&character);
getch();
}
}
实验五树及二叉树实验
1)按先序次序输入二叉树中结点的值，建立一棵以二叉链表作存储结构的二叉树，后
按先序、中序、后序顺序分别遍历这棵二叉树。
2)编写一个求二叉树叶子结点数的算法。
3)交换左右孩子。
#include
#define NULL 0
typedef struct bitnode{
int data;
struct bitnode *lchild, *rchild;
}bitnode,*bitree;
void createbitree(bitree *t){
char ch,zifu;
scanf("%c",&ch);
zifu=getchar();
if(ch=='#') *t=NULL;
else{
if(!((*t)=(bitree)malloc(sizeof(bitnode)))) ;/* if(!(*t=(bitnode*)malloc(sizeof(bitnode)))) ;*/
(*t)->data=ch;
printf("enter the lchild\n");
createbitree(&((*t)->lchild));
printf("enter the rchild\n");
createbitree(&((*t)->rchild));
}
}
void preorder(bitree *t){
if(*t!=NULL){
printf("%c\t",(*t)->data);
preorder(&((*t)->lchild));
preorder(&((*t)->rchild));
}
}
void inorder(bitree *t){
if(*t!=NULL){
inorder(&((*t)->lchild));
printf("%c\t",(*t)->data);
inorder(&((*t)->rchild));
}
}
void postorder(bitree *t){
if(*t!=NULL){
postorder(&((*t)->lchild));
postorder(&((*t)->rchild));
printf("%c\t",(*t)->data);
}
}
int leafcount(bitree *t){
int num,num1,num2;
if(*t==NULL) num=0;
else if(((*t)->lchild==NULL)&&((*t)->rchild==NULL)) num=1;
else {
num1=leafcount(&(*t)->lchild);
num2=leafcount(&(*t)->rchild);
num=num1+num2;
}
return num;
}
void changeleaf(bitree *t){
bitree p,q;
if(*t!=NULL){
p=(*t)->rchild;
(*t)->rchild=(*t)->lchild;
(*t)->lchild=p;
changeleaf(&((*t)->lchild));
changeleaf(&((*t)->rchild));
}
}
void instruction(void)
{
printf("\nEnter your choice:\n"
"1 to preorder\n"
"2 to inorder\n"
"3 to postorder\n"
"4 to change the leaf\n"
"5 to leafcount\n"
"6 to end\n");
}
void main()
{
bitree t;
int choice;
printf("Enter the root of the tree\n");
createbitree(&t);
instruction();
scanf("%d",&choice);
while (choice!=6){
switch (choice){
case 1:
printf("The perorder of the tree is:\n");
preorder(&t);
instruction();
scanf("%d",&choice);
break;
case 2:
printf("The ororder is:\n");
inorder(&t);
instruction();
scanf("%d",&choice);
break;
case 3:
printf("The postorder is:\n");
postorder(&t);
instruction();
scanf("%d",&choice);
break;
case 5:
printf("The leafs is %d\n",leafcount(&t));
instruction();
scanf("%d",&choice);
break;
case 4:
changeleaf(&t);
printf("After change the tree is:\n");
preorder(&t);
instruction();
scanf("%d",&choice);
break;
default:
printf("Error\n");
break;
}
}
printf("End of run\n");
getch();
}
实验六
1)建立无向图和有向图的邻接矩阵存储，计算顶点的度，并按要求输出图的基本信
息。
2)建立有向图的邻接表存储表示，并根据存储计算顶点的出度和入度，然后按照要
求输出图的基本信息。
1）/*邻接矩阵存储*/
#include
#define infinity -
#define max_vertex_num 20
typedef enum{UDG=1,DG}graphkind;
typedef struct arccell{
char adj;
}arccell,adjmatrix[max_vertex_num][max_vertex_num];
typedef struct{
char vexs[max_vertex_num];
adjmatrix arcs;
int vexnum,arcnum;
graphkind kind;
}mgraph;
int locatevex(mgraph*g,char*arc1)
{ int i;
for(i=0;i
if(g->vexs[i]==*arc1)
return i;
}
void createDG(mgraph*g){
int i,j,k;char*tarc,*harc,zifu;
printf("enter the num for G's vexnum,arcnum,and graphkind:\n");
scanf("%d%d%d",&g->vexnum,&g->arcnum,&g->kind);
for(i=0;i
printf("enter the vex\n");
zifu=getchar();
scanf("%c",&g->vexs[i]);}
for(i=0;i
for(j=0;j
g->arcs[i][j].adj='0';}
}
for(k=0;k
zifu=getchar();
printf("enter one arc'vex\n");
scanf("%c",tarc);
zifu=getchar();
scanf("%c",harc);
i=locatevex(g,tarc);j=locatevex(g,harc);
g->arcs[i][j].adj='1';
}
}
void createUDG(mgraph*g){
int i,j,k,x,y;char*arc1,*arc2,zifu;
printf("enter the num for G's vexnum,arcnum,and graphkind:\n"); scanf("%d%d%d",&g->vexnum,&g->arcnum,&g->kind);
for(i=0;i
printf("enter the vex\n");
zifu=getchar();
scanf("%c",&g->vexs[i]);}
for(i=0;i
for(j=0;j
g->arcs[i][j].adj='0';
for(k=0;k
zifu=getchar();
printf("enter one arc'vex\n");
scanf("%c",arc1);
zifu=getchar();
scanf("%c",arc2);
x=locatevex(g,arc1);y=locatevex(g,arc2);
g->arcs[x][y].adj='1';
g->arcs[y][x].adj='1';}
}
void degree(mgraph*g){
int i,j,counter=0,sum=0;
if(g->kind==DG){
for(i=0;i
for(j=0;j
if(g->arcs[i][j].adj=='1')
counter++;}
printf("the outdegree of %c is %d\n",g->vexs[i],counter);
for(j=0;j
if(g->arcs[j][i].adj=='1')
counter++;}
printf("the degree of %c is %d\n",g->vexs[i],counter);
counter=0;
}
}
if(g->kind==UDG){
for(i=0;i
for(j=0;j
if(g->arcs[i][j].adj=='1')
sum++;
}
printf("the degree of %c is %d\n",g->vexs[i],sum);
sum=0;
}
}
}
void print(mgraph*g){
int i,j;
printf("the graph is \n");
for(i=0;i
printf("\t%c",g->vexs[i]);
}
printf("\n");
for(i=0;i
printf("%c\t",g->vexs[i]);
for(j=0;j
printf("%c\t",g->arcs[i][j].adj);}
printf("\n");
}
}
main(){
int k,m,n;mgraph G;char biao,sign;
while(biao!='#'){
printf("please make your chioce:1--createUDG;2--createDG\n");
scanf("%d",&k);
switch(k){
case 1:
createUDG(&G);
print(&G);
degree(&G);
break;
case 2:
createDG(&G);
print(&G);
degree(&G);
break;
}
sign=getchar();
printf("enter your choice'*' for quit\n");
scanf("%c",&biao);
}
getch();
}
2）
/*邻接表存储*/
#include
#define null 0
#define max_vertex_num 20
typedef enum{DG=1}graphkind;
typedef struct arcnode{
int adjvex;
struct arcnode *nextarc;
}arcnode;
/*顶点结点*/
typedef struct vnode{
char data;
arcnode *firstarc;
}vnode,adjlist[max_vertex_num];
typedef struct{
adjlist vertices;
int vexnum,arcnum;
graphkind kind;
}algraph;
void createDG(algraph*g){
int i,j;arcnode*p,*q;char over='h',biao;
printf("please enter num for G's vexnum,arcnum,kind:\n");
scanf("%d%d%d",&g->vexnum,&g->arcnum,&g->kind);
for(i=0;i
printf("enter the vex\n");
biao=getchar();
scanf("%c",&g->vertices[i].data);
g->vertices[i].firstarc=null;}
for(i=0;i
printf("please create the %d single link of %c\n",i+1,g->vertices[i].data);
over='h';
while(over!='*'){
if(g->vertices[i].firstarc==null){
printf("if the single link has no degree please input '*'\n");
biao=getchar();
scanf("%c",&over);
if(over=='*')
break;
else{
p=(arcnode*)malloc(sizeof(arcnode));
printf("enter the position of firstadjvex:\n");
scanf("%d",&p->adjvex);
g->vertices[i].firstarc=p;
p->nextarc=null;}
}
else {
q=(arcnode*)malloc(sizeof(arcnode));
printf("enter the position of nextadjvex:\n");
scanf("%d",&q->adjvex);
p->nextarc=q;
q->nextarc=null;}
printf("enter '*' to quit the single link because it has no dajvex\n");
biao=getchar();
scanf("%c",&over);
}
getch();
}
}
void outdegree(algraph*g){
int count=0,i; arcnode*ptr;
for(i=0;i
if(g->vertices[i].firstarc!=null){
count++;
ptr=g->vertices[i].firstarc;
for(;ptr->nextarc!=null;){
ptr=ptr->nextarc;
count++;}
printf("the outdegree of %c is %d\n",g->vertices[i].data,count);
count=0;}
else printf("the outdegree of %c is %d\n",g->vertices[i].data,count);
}
}
void indegree(algraph*g){
int count=0,i; arcnode*ptr;
for(i=0;i
if(g->vertices[i].firstarc!=null){
count++;
ptr=g->vertices[i].firstarc;
for(;ptr->nextarc!=null;){
ptr=ptr->nextarc;
count++;}
printf("the indegree of %c is %d\n",g->vertices[i].data,count);
count=0;}
else printf("the indegree of %c is %d\n",g->vertices[i].data,count);
}
}
void print(algraph*g){
int i; arcnode*ptr;
for(i=0;i
if(g->vertices[i].firstarc!=null){
printf("%c\t->",g->vertices[i].data);
ptr=g->vertices[i].firstarc;
for(;ptr->nextarc!=null;){
printf("%c\t->",g->vertices[ptr->adjvex].data);
ptr=ptr->nextarc;}
printf("%c",g->vertices[ptr->adjvex].data);
printf("\n");}
else printf("%c\n",g->vertices[i].data);
}
}
main(){
int m;algraph G;
printf("please create DG according to the turn of outdegree \n");
createDG(&G);
printf("the algraph is\n");
print(&G);
outdegree(&G);
printf("please create DG according to the turn of indegree \n");
createDG(&G);
printf("the algraph is\n");
print(&G);
indegree(&G);
getch();
}
实验七查找与排序实验
目的要求：
1)学生在实习中体会各种查找和内部排序算法的基本思想、适用场合，理解开发高效算
法的可能性和寻找、构造高效算法的方法。
实验内容：
1)实现二分查找算法，并计算相应的ASL。
2)实现插入排序或选择排序算法。