《软件技术基础》实验指导（含答案）(5)

{ static int leaf =0; if(p!=NULL){ leaf = countleaf( p->lchild ); //统计左子树中叶子结点个数 if ((p->lchild==NULL)&&(p->rchild==NULL)) leaf=leaf+1; leaf=countleaf(p->rchild); //统计右子树中叶子结点个数 }

return leaf; }

实验六：第1题

//无向图邻接矩阵搜索遍历的程序代码 #include

//图的邻接矩阵类型定义 const int n=8; const int e=10;

typedef char vextype; typedef int adjtype; typedef struct { vextype vexs[n]; adjtype arcs[n][n]; }graph;

graph*g=new graph; void creatgraph(); void dfsa(int); int visited[n];

void main() { creatgraph(); int i; while(1) { for(i=0;i

//建立无向图邻接矩阵 void creatgraph() { int i,j,k; char ch; printf(输入8个顶点的字符数据信息:\n for(i=0;i

 

21

if((ch=getchar())!='\n') g->vexs[i]=ch; for(i=0;iarcs[i][j]=0; printf(输入10条边的起、终点i,j:\n for(k=0;karcs[i][j]=g->arcs[j][i]=1; } }

//深度优先搜索遍历 void dfsa(int i) { int j; printf( visited[i]=1; for(j=0;jarcs[i][j]==1&&visited[j]==0)dfsa(j); }

实验七：第1题

//希尔排序的程序代码 #include

//顺序表结构类型定义 typedef int datatype; typedef struct{ int key; datatype data; }rectype;

const int N=10; const int D1=5;

void create(rectype[],int); void print(rectype[],int);

void shellsort(rectype[],int[]);

void main() {

rectype r[N+D1];//D1个元素存放监视哨，N个元素存放记录 int d[3]={5,3,1};//设置3趟的增量 create(r,N);//建立存放记录的顺序表 printf(排序前的数据： print(r,N);//输出排序前的记录表 shellsort(r,d);//希尔排序 printf(排序后的数据： print(r,N);//输出排序后的记录表 }

 

22

 

//建立顺序表

void create(rectype r[],int n) { printf(输入10个整型数： for(int i=0;i

//输出顺序表

void print(rectype r[],int n) { for(int i=0;i

//希尔排序

void shellsort(rectype r[],int d[]) { int i,j,k,h; rectype temp; int maxint=32767; for(i=0;i

实验七：第2题

//双向起泡排序的程序代码 #include #include #include

 

23

//顺序表结构类型定义 typedef int datatype; typedef struct{ int key; datatype data; }sequenlist;

void create(sequenlist[],int); void print(sequenlist[],int);

void dbubblesort(sequenlist[],int);

void main() { const int n=10; sequenlist r[n+1]; create(r,n); printf(排序前的数据： print(r,n); dbubblesort(r,n); printf(排序后的数据： print(r,n); }

//建立顺序表

void create(sequenlist r[],int n) { srand(time(0)); for(int i=1;i<=n;i++) r[i].key=rand()?; }

//输出顺序表

void print(sequenlist r[],int n) { for(int i=1;i<=n;i++) printf( printf(}

//双向起泡排序

void dbubblesort(sequenlist r[],int n) { int i=1,j,noswap=1; sequenlist temp; while(noswap){ noswap=0; for(j=n-i+1;j>=i+1;j--) if(r[j].key

 

24

noswap=1; temp=r[j]; r[j]=r[j-1]; r[j-1]=temp; } for(j=i+1;j<=n-i;j++) if(r[j].key>r[j+1].key) { noswap=1; temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; } for(int k=1;k<=n;k++) printf( printf( i++; } }

实验八：第1题

//分块查找的程序代码 #include //类型定义

typedef int keytype; typedef struct { keytype key; int low,high; }index;

typedef struct { keytype key; }record;

const int recN=18; const int idxN=3;

int blksearch(record[],index[],keytype,int); void main() { record r[recN]={22,12,13,8,9,20,33,42,44,38,24,48,60,58,74,49,86,53}; index idx[idxN]={{22,0,5},{48,6,11},{86,12,17}}; keytype key; int loc,i; printf(待查找的记录关键字表：\n for(i=0;i

 

25