西电《软件技术基础》上机大作业答案

说明

每个实验题目含有一个main函数和一些函数，与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目要求设计算法，补充函数定义，然后对程序进行编译、调试。

1

实验一 线性表

一、 实验目的

1．熟悉线性表的顺序和链式存储结构 2．掌握线性表的基本运算

3．能够利用线性表的基本运算完成线性表应用的运算

二、 实验内容

1．设有一个线性表E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ en , en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。（文件夹：顺序表逆置、单链表逆置）

2．已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。（文件夹：分解单链表）

实验二 栈和队列

一、 实验目的

1．熟悉栈和队列的顺序和链式存储结构 2．掌握栈和队列的基本运算

3．能够利用栈和队列的基本运算完成栈和队列应用的运算

二、 实验内容

1．设单链表中存放有n个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx是中心对称的字符串。（提示：将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。）（文件夹：判字符串中心对称）

2．假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。（文件夹：循环队列）

实验三 串

一、 实验目的

1． 熟悉串的顺序存储结构 2． 掌握串的基本运算及应用

二、 实验内容

1．串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。（文件夹：模式匹配）

2．若S是一个采用顺序结构存储的串，利用C的库函数strlen和strcpy（或strncpy）编写一算法void SteDelete(char*S,int I,int m)，要求从S中删除从第i个字符开始的连续m个字符。

2

若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾的字符均删除。（文件夹：删除子串）

实验四 数组

一、 实验目的

1．熟悉数组的结构

2．掌握矩阵的压缩存储

3．能够对数组和矩阵的压缩存储进行运算

二、 实验内容

1. 若在矩阵Am×n中存在一个元素A[i][j]，其满足A[i][j]是第i行元素中最小值，且又

是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Am

（文件夹：找马鞍点） ×n ，设计算法求出矩阵中所有马鞍点。

2. A和B是两个n×n阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储

存入一维数组A和B，编写一个算法计算对称矩阵A和B的乘积，结果存入二维数组C。（文件夹：对称矩阵相乘）

实验五 树

一、 实验目的

1．熟悉二叉树的链式存储结构

2．掌握二叉树的建立、深度优先递归遍历等算法 3．能够利用遍历算法实现一些应用

二、 实验内容

1．已知二叉树采用二叉链表存储结构，如果左、右子树非空，且左子树根结点大于右子树

根结点，则交换根结点的左、右子树。即按要求交换二叉树及子树的左、右子树。（文件夹：交换左右子树）

2．采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点

总数。（文件夹：统计二叉树结点）

实验六 图

一、 实验目的

1．熟悉图的邻接矩阵和邻接表的存储结构 2．熟悉图的邻接矩阵和邻接表的建立算法 3．掌握图的遍历算法

二、 实验内容

1． 无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。（文件夹：无向图邻接矩阵）

3

A B D E F C G H 实验七 排序

一、 实验目的

1．熟悉各种内部排序算法

2．能够编写程序显示排序过程中各趟排序的结果 3．能够编写一些排序的算法

二、 实验内容

1． 采用希尔排序方法对顺序表中的证型数据进行排序，设计希尔排序算法并显示每趟排序

的结果。（文件夹：希尔排序）

2． 编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序

的结果。（文件夹：双向起泡排序）

实验八 查找

一、 实验目的

1．熟悉线性表、二叉排序树和散列表的查找 2．能够编写一些查找的算法

二、 实验内容

1． 18个记录的关键字为22、12、13、8、9、20、33、42、44、38、24、48、60、58、74、

49、86、53，编写分块查找的算法进行查找。（文件夹：分块查找）

2． 编写一个判别给定的二叉树是否为二叉排序树的算法，设二叉树以二叉链表存储表示，

结点的数据域只存放正整数。（文件夹：判断二叉排序树）

附录：原代码

实验一：第1题（1） //顺序表逆置的程序代码 #include #include //顺序表结构类型定义 typedef char datatype;

4

const int maxsize=1024; typedef struct

{ datatype data[maxsize]; int last; }sequenlist;

void create(sequenlist*&); void print(sequenlist*); void invert(sequenlist*);

void main() { sequenlist*L; create(L);//建立顺序表 print(L);//输出顺序表 invert(L);//调用顺序表逆值的函数 print(L);//输出顺序表 }

//建立顺序表

void create(sequenlist*&L) { L=(sequenlist*)malloc(sizeof(sequenlist)); L->last=0; char ch; while((ch=getchar())!='*') { L->last++; L->data[L->last]=ch; } }

//输出顺序表

void print(sequenlist*L) { for(int i=1;i<=L->last;i++) printf(\ printf(\}

//顺序表逆置

void invert(sequenlist*L) { int n=L->last/2; for(int i=1;i<=n;i++) { char temp=L->data[i]; L->data[i]=L->data[L->last-i+1]; L->data[L->last-i+1]=temp; }

5

}

实验一：第1题（2） //单链表逆置的程序代码 #include #include

//单链表结构类型定义 typedef char datatype; typedef struct node { datatype data; struct node *next; }linklist;

void create(linklist*&); void print(linklist *); void invert(linklist*); void main() { linklist*head; create(head); print(head); invert(head);//调用单链表逆置的函数 print(head); }

//采用尾插法建立具有头结点的单链表 void create(linklist*&head) { char ch; linklist *s,*r; head=(linklist*)malloc(sizeof(linklist)); r=head; while((ch=getchar())!='*') { s=(linklist*)malloc(sizeof(linklist)); s->data=ch; r->next=s; r=s; } r->next=NULL; }

//输出单链表

void print(linklist *head) { linklist*p=head->next; while(p!=NULL) { printf(\

6

p=p->next; } printf(\}

//单链表逆置

void invert(linklist*head) { linklist*p,*q,*r; p=head->next; q=p->next; while(q!=NULL) { r=q->next; q->next=p; p=q; q=r; } head->next->next=NULL; head->next=p; }

实验一：第2题

//分解单链表的程序代码 #include #include //链表结构类型定义 typedef char datatype; typedef struct node { datatype data; struct node *next; }linklist;

void create(linklist*&);

void resolve(linklist*,linklist*,linklist*,linklist*); void insert(linklist*,linklist*); void print1(linklist*); void print2(linklist*); void main()

{ linklist *head,*letter,*digit,*other; create(head); print1(head);

letter=(linklist*)malloc(sizeof(linklist));//建立3个空循环链表 letter->next=letter;

digit=(linklist*)malloc(sizeof(linklist)); digit->next=digit;

other=(linklist*)malloc(sizeof(linklist)); other->next=other;

resolve(head,letter,digit,other);//调用分解单链表的函数 print2(letter);//输出循环链表

7

print2(digit); print2(other); }

//建立单链表

void create(linklist*&head) { datatype x; linklist *s,*r;

head=new linklist; r=head;

while((x=getchar())!='$') { s=(linklist*)malloc(sizeof(linklist)); s->data=x; r->next=s; r=s; }

r->next=NULL; }

//在循环链表中插入

void insert(linklist*h,linklist*p) { linklist *q=h;

while(q->next!=h) q=q->next; q->next=p; p->next=h; }

//输出单链表

void print1(linklist*head) { linklist *p=head->next; while(p!=NULL)

{ printf(\ p=p->next; }

printf(\}

//输出循环链表

void print2(linklist*head) { linklist *p=head->next; while(p!=head) { printf(\ p=p->next; }

printf(\}

8

//按字母、数字、其它字符分解单链表

void resolve(linklist*head,linklist*letter,linklist*digit,linklist*other) { linklist *p;

while(head->next!=NULL) { p=head->next;

head->next=head->next->next; if((p->data>='A'&&p->data<='Z')||(p->data>='a'&&p->data<='z')) insert(letter,p);

else if(p->data>='0'&&p->data<='9') insert(digit,p); else insert(other,p); } }

void resolve(linklist*head,linklist*letter,linklist*digit,linklist*other) { linklist *p; p=head->next; while(p!=NULL) { if((p->data>='a'&&p->data<='z')||(p->data>='A'&&p->data<='Z')) insert(letter,p);

else if(p->data>='0'&&p->data<='9') insert(digit,p); else insert(other,p); p=p->next; } }

实验二：第1题

//判字符串中心对称的程序代码 #include #include #include

//定义单链表结构类型 typedef char datatype; typedef struct node { datatype data; struct node *next; }linklist;

//定义顺序栈结构类型 const int maxsize=40; typedef struct

{ datatype elements[maxsize]; int top; }stack;

void setnull(stack *&); int length(linklist*); void printlink(linklist*);

void create(linklist *&,datatype*); void push(stack*,datatype); datatype pop(stack*);

9

int symmetry(linklist*,stack*);//判字符串是否中心对称的函数声明

void main() { linklist *head;stack *s; datatype str[80]; gets(str); create(head,str); printlink(head); setnull(s); if(symmetry(head,s)) printf(\字符串\\\中心对称\\n\ else printf(\字符串\\\不是中心对称\\n\}

//栈初始化

void setnull(stack *&s) { s=(stack*)malloc(sizeof(stack)); s->top=-1; }

//求单链表长度

int length(linklist*head) { linklist *p=head->next; int n=0;

while(p!=NULL){ n++; p=p->next; } return n; }

//输出单链表

void printlink(linklist*head) { linklist *p=head->next; while(p!=NULL)

{ printf(\ p=p->next; }

printf(\}

//建立具有头结点的单链表

void create(linklist *&head,datatype*str) { datatype *p=str; linklist *s,*r;

head=(linklist*)malloc(sizeof(linklist)); r=head;

while(*p!='\\0') { s=(linklist*)malloc(sizeof(linklist)); s->data=*p;

10

r->next=s; r=s; p++; }

r->next=NULL; }

//顺序栈入栈

void push(stack*s,datatype e) { s->top++; s->elements[s->top]=e; }

//顺序栈出栈

datatype pop(stack*s) { datatype temp; s->top--; temp=s->elements[s->top+1]; return temp; }

//判字符串是否中心对称

int symmetry(linklist*head,stack*s) { int n=length(head)/2; linklist*p=head->next; datatype x; for(int i=0;idata); p=p->next; } if(length(head)%2==1) p=p->next; while(p!=NULL){ x=pop(s); if(x==p->data) p=p->next; else return 0; } return 1; }

实验二：第2题

//循环队列入队出队的程序代码 #include #include #include

//循环队列的结构类型定义 const int m=5;

11

typedef int datatype; typedef struct

{ datatype sequ[m]; int rear, quelen; }qu;

void setnull(qu*);

void enqueue(qu*, datatype); datatype *dequeue(qu*);

void main() { qu *sq;

datatype x, *p; int key;

sq=(qu*)malloc(sizeof(qu)); setnull(sq); do

{ printf(\ 2.Delete Queue -1.Quit:\ scanf(\ switch(key)

{ case 1: printf(\ enqueue(sq,x); break; case 2: p=dequeue(sq); if(p!=NULL) printf(\ break; case -1: exit(0); }

}while(1); }

//置空队

void setnull(qu *sq) { sq->rear=m-1; sq->quelen=0; }

//入队

void enqueue(qu *sq, datatype x)

{ if(sq->quelen==m) printf(\ else { sq->quelen++; sq->rear=(sq->rear+1)%m; sq->sequ[sq->rear]=x; } }

//出队

datatype *dequeue(qu *sq) { datatype *temp; if(sq->quelen==0) { printf(\

12

else { temp=(datatype*)malloc(sizeof(datatype)); sq->quelen--; *temp=sq->sequ[(sq->rear-sq->quelen+m)%m]; return (temp); } }

实验三：第1题

//模式匹配的程序代码 #include #include #include

//顺序串的结构类型定义 #define maxsize 100 typedef struct { char str[maxsize]; int len; }seqstring;

int Index(seqstring*, seqstring*);

void main() { seqstring*S,*subS; S=(seqstring*)malloc(sizeof(seqstring)); subS=(seqstring*)malloc(sizeof(seqstring)); printf(\输入串：\ S->len=strlen(S->str); printf(\输入子串：\ subS->len=strlen(subS->str); if(Index(S,subS)>0) printf(\匹配成功！\\n\ else printf(\匹配失败！\\n\}

//顺序串的朴素模式匹配

int Index(seqstring*S, seqstring*T) { int i=1,j=1; //位序从1开始 while(i<=S->len&&j<=T->len) if(S->str[i-1]==T->str[j-1])

{ i++; j++; } //继续比较后面的字符 else

{ i=i-j+2; j=1; } //本趟不匹配，设置下一趟匹配的起始位序 if(j>T->len) return(i-T->len); //匹配成功 else return(-1); //匹配不成功 }

实验三：第2题

//删除子串的程序代码

13

#include #include #include

//顺序串的结构类型定义 #define maxsize 100 typedef struct { char str[maxsize]; int len; }seqstring;

void strPut(seqstring*);

void strDelete(seqstring*,int,int); void main() { seqstring*S; int i,m; S=(seqstring*)malloc(sizeof(seqstring)); printf(\输入串：\ S->len=strlen(S->str); strPut(S); printf(\删除的开始位置:\ printf(\删除的字符个数:\ strDelete(S,i,m); strPut(S); }

//输出串

void strPut(seqstring*S) { int i; for(i=0;ilen;i++) printf(\ printf(\}

//删除子串

void strDelete(seqstring*S,int i,int m) { char temp[maxsize]; if(i<=S->len){ strncpy(temp,S->str,i-1); strcpy(temp+i-1,S->str+i+m-1); strcpy(S->str,temp); if(i<=S->len) if(i+m-1<=S->len) S->len=S->len-m; else S->len=S->len-i+1; } }

14

实验四：第1题 //找马鞍点程序代码 #include #include //数组的结构类型定义 const int m=3; const int n=3; typedef struct{ int A[m+1][n+1]; int max[m+1],min[n+1]; }array;

void minmax(array*);

void main() { array*pa=(array*)malloc(sizeof(array)); int i, j;

for (i=1;i<=m;i++) for (j=1;j<=n;j++)

scanf(\ minmax(pa); }

//找马鞍点

void minmax(array*p) { int i,j,have=0; for(i=1;i<=m;i++) { p->min[i]=p->A[i][1]; for(j=2;j<=n;j++) if(p->A[i][j]min[i]) p->min[i]=p->A[i][j]; }

for (j=0;jmax[j]=p->A[1][j]; for(i=2;i<=m;i++) if(p->A[i][j]>p->max[j]) p->max[j]=p->A[i][j]; }

for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(p->min[i]==p->max[j]) { printf(\ have=1; }

if(!have) printf(\矩阵中没有马鞍点！\\n\}

15

实验四：第2题

//对称矩阵相乘的程序代码 #include #include

//数组结构类型的定义.h const int n=3;

const int size=n*(n+1)/2; typedef int datatype; typedef struct{ datatype A[size],B[size],C[n][n]; }array;

void input(datatype[]); void output(datatype[][n]); void mult(array*);

void main() { array*pa; pa=(array*)malloc(sizeof(array)); printf(\以行为主序输入矩阵A的下三角:\\n\ input(pa->A);//以行为主序输入矩阵A的下三角 printf(\以行为主序输入矩阵B的下三角:\\n\ input(pa->B);//以行为主序输入矩阵B的下三角 mult(pa); output(pa->C);//输出矩阵C }

//对称矩阵的输入

void input(datatype x[]) { for(int i=0;i

//矩阵的输出

void output(datatype x[][n]) { for(int i=0;i

//对称矩阵相乘 void mult(array*p) { int i,j,k,t1,t2;

16

datatype s; for(i=0;i=k)t1=i*(i+1)/2+k; else t1=k*(k+1)/2+i; if(k>=j)t2=k*(k+1)/2+j; else t2=j*(j+1)/2+k; s=s+p->A[t1]*p->B[t2]; } p->C[i][j]=s; } }

实验五：第1题

//交换左右子树的程序代码 #include #include

//二叉链表的结构类型定义 const int maxsize=1024; typedef char datatype; typedef struct node { datatype data; struct node *lchild,*rchild; }bitree;

bitree*creattree();

void preorder(bitree*); void swap(bitree*);

void main() { bitree*pb; pb=creattree(); preorder(pb); printf(\ swap(pb); preorder(pb); printf(\}

//二叉树的建立 bitree*creattree() { char ch;

17

bitree*Q[maxsize]; int front,rear; bitree*root,*s; root=NULL; front=1;rear=0; printf(\按层次输入二叉树，虚结点输入'@'，以'#'结束输入：\\n\ 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 preorder(bitree*p) { if(p!=NULL) { printf(\ if(p->lchild!=NULL||p->rchild!=NULL) { printf(\ preorder(p->lchild); if(p->rchild!=NULL)printf(\ preorder(p->rchild); printf(\ } } }

//交换左右子树 void swap(bitree*p)

18

{ bitree*t; if(p!=NULL) { if(p->lchild!=NULL&&p->rchild!=NULL&&p->lchild->data>p->rchild->data) { t=p->lchild; p->lchild=p->rchild; p->rchild=t; } swap(p->lchild); swap(p->rchild); } }

实验五：第2题

//统计结点总数及叶子结点总数的程序代码 #include #include

//二叉链表的结构类型定义 const int maxsize=1024; typedef char datatype; typedef struct node { datatype data; struct node *lchild,*rchild; }bitree;

bitree*creattree();

void preorder(bitree*); int countnode(bitree*); int countleaf(bitree*);

void main() { bitree*root; int leafnum,nodenum; root=creattree(); printf(\删除子树之前的二叉树：\ preorder(root); printf(\

nodenum=countnode(root);

printf(\结点总数是：%d\\n\ leafnum=countleaf(root);

printf(\叶子结点总数是：%d\\n\}

//建立二叉树 bitree*creattree() {

19

datatype ch; bitree*Q[maxsize]; int front,rear; bitree*root,*s; root=NULL; front=1;rear=0; printf(\按层次输入结点值，虚结点输入'@'，以换行符结束：\ while((ch=getchar())!='\\n') { 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 preorder(bitree*p) { if(p!=NULL) { printf(\ if(p->lchild!=NULL||p->rchild!=NULL) { printf(\ preorder(p->lchild); if(p->rchild!=NULL) printf(\ preorder(p->rchild); printf(\ } } }

//统计结点个数

20

int countnode(bitree *p) { static int node =0; if(p!=NULL){ node=node+1; node = countnode(p->lchild); //统计左子树中结点个数 node=countnode(p->rchild); //统计右子树中结点个数 }

return node; }

//统计叶子结点个数 int countleaf(bitree *p) { 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

21

if(i==-1) break; dfsa(i); } }

//建立无向图邻接矩阵 void creatgraph() { int i,j,k; char ch; printf(\输入8个顶点的字符数据信息:\\n\ for(i=0;ivexs[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[]);

22

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);//输出排序后的记录表 }

//建立顺序表

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

23

r[j+h]=temp; }//组内直接插入法排序 print(r,N);//输出一趟的排序结果 k++; }while(h!=1); }

实验七：第2题

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

//顺序表结构类型定义 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(\

24

}

//双向起泡排序

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].keyr[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;

25

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

//分块查找

int blksearch(record r[],index idx[],keytype k,int n) { int i,low=0,high=n-1,mid,bh,find=0; //折半查找索引表 while(low<=high&&!find) { mid=(low+high)/2; if(kidx[mid].key)low=mid+1; else { high=mid-1; find=1; } } if(low

实验八：第2题

//判断二叉排序树的程序代码 #include #include

26

#include

//二叉链表的结构类型定义 const int maxsize=1024; typedef int keytype; typedef struct node { keytype key; struct node *lchild,*rchild; }bitree;

bitree*creattree();

void preorder(bitree*); void inorder(bitree*);

void main() { bitree*pb; pb=creattree(); preorder(pb); printf(\ inorder(pb); printf(\是二叉排序树！\\n\}

//二叉树的建立 bitree*creattree() { keytype x; bitree*Q[maxsize]; int front,rear; bitree*root,*s; root=NULL; front=1;rear=0; printf(\按层次输入二叉排序树的整型结点数据，0表示虚结点，-1表示结束：\\n\ scanf(\输入0表示虚结点，-1表示结束 while(x!=-1) { s=NULL; if(x!=0) { s=(bitree*)malloc(sizeof(bitree)); s->key=x; s->lchild=NULL; s->rchild=NULL; } rear++; Q[rear]=s; if(rear==1)root=s; else

27

{ if(s&&Q[front]) if(rear%2==0)Q[front]->lchild=s; else Q[front]->rchild=s; if(rear%2==1)front++; } scanf(\ } return root; }

//二叉树的输出

void preorder(bitree*p) { if(p!=NULL) { printf(\ if(p->lchild!=NULL||p->rchild!=NULL) { printf(\ preorder(p->lchild); if(p->rchild!=NULL) printf(\ preorder(p->rchild); printf(\ } } }

//判断二叉排序树 keytype k=-32768; void inorder(bitree*p) { if(p!=NULL) { inorder(p->lchild); if(p->key>k) k=p->key; else { printf(\不是二叉排序树！\\n\ exit(0); } inorder(p->rchild); } }

28

本文来源：https://www.bwwdw.com/article/h2gt.html