哈尔滨工程大学 实 验 报 告
线性表对应元素相加 实 验 名 称：________________________________ 班 级：________________________________ 学 号：________________________________ 姓 名：________________________________ 实 验 时 间：________________________________ 成 绩：________________________________ 指 导 教 师：________________________________
实验室名称： 自动控制实验教学中心 哈尔滨工程大学
1．实验名称：线性表对应元素相加
2．实验目的：
1、掌握线性表的顺序存储方式
2、熟练掌握对线性表元素的基本操作
3．实验内容
编写程序，将两个线性表中对应元素相加，线性表的长度要求可变，且不同；从键盘输入线性表的每个元素；和放在第三个线性表中，并显示。线性表可用顺序存储（数组）实现，也可用链式结构。
4．实验环境：
微机，vc6.0
5．实验设计过程
6．实验结果分析
1.程序实现了将两个线性表对应元素相加并存储到第三个线性表中。
2.程序利用线性表这一数据结构解决问题，通过本实验体会到了线性表的逻辑结构、存储结构和操作的深刻含义。初步体会了线性表的应用需求。
3.1）在实验过程中，出现了XXXX情况，经过算法分析和代码检查，发现XXX存在问题，通过增加XX指令或调整算法，解决了xxx问题；2）XXXXXXYYY；
4.通过本次实验，对算法设计、程序编写规范化XXX等问题有了一定的体会。
哈尔滨工程大学 实 验 报 告
栈空间共享 实 验 名 称：________________________________ 班 级：________________________________ 学 号：________________________________ 姓 名：________________________________ 实 验 时 间：________________________________ 成 绩：________________________________ 指 导 教 师：________________________________
实验室名称： 自动控制实验教学中心 哈尔滨工程大学
1．实验名称：栈空间共享
2．实验目的：
1、理解栈类型的定义和操作特点，应注意栈空和栈满的判断条件
2、理解栈空间共享的思想，掌握其实现方法
3．实验内容
编写程序，分别建两个堆栈，要求共享一连续空间（数组），输入一整数序列，将奇数和偶数分别存放在两个栈中，栈满后打印。
4．实验环境：
微机，vc6.0软件
5．实验设计过程
6．实验结果
程序实现了将奇数存放在top1所指示的栈中，偶数存放在top2所指示的栈中，实现栈空间共享
哈尔滨工程大学
实 验 报 告
求树高 实 验 名 称：________________________________
班 级：________________________________ 学 号：________________________________ 姓 名：________________________________ 实 验 时 间：________________________________ 成 绩：________________________________ 指 导 教 师：________________________________
实验室名称： 自动控制实验教学中心
哈尔滨工程大学
1．实验名称：求树高
2．实验目的：
1、理解二叉树的结构特性、性质、存储结构的特点
2、掌握求二叉树树高的算法
3．实验内容
设计一链式结构类型，用来存储二叉树，建立二叉树，涉及算法并依据算法编写程序求二叉树的树高
4．实验环境：
微机，tc,vc6.0软件
6．实验结果
程序实现了对链式存储结构的二叉树的树高的求取
哈尔滨工程大学
实 验 报 告
图的入度和出度 实 验 名 称：________________________________
班 级：________________________________ 学 号：________________________________ 姓 名：________________________________ 实 验 时 间：________________________________ 成 绩：________________________________ 指 导 教 师：________________________________
实验室名称： 自动控制实验教学中心
哈尔滨工程大学
1．实验名称：图的入度和出度
2．实验目的：
1、理解图的入度、出度等概念，掌握图的存储结构及算法实现
2、掌握求有向图的入度和出度的算法
3．实验内容
采用邻接矩阵存储图，用二维数组实现，每个数组元素为1表示从一顶点到另一顶点有边（弧）存在，为零表示两个顶点不相邻；从键盘输入图的全部信息；依据算法编写程序计算含有5个顶点的有向图的入度和出度
4．实验环境：
微机，tc,vc6.0软件
5．实验设计过程
6．实验结果
程序实现了对有向图的邻接矩阵存储方式的入度和出度的计算
第二篇：《软件技术基础》实验指导(含答案)
说明
每个实验题目含有一个main函数和一些函数，与实验题目相关的基本运算的函数定义和main函数定义的代码在附录以及对应的文件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目要求设计算法，补充函数定义，然后对程序进行编译、调试。
实验一 线性表
一、 实验目的
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个字符。若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． 无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。（文件夹：无向图邻接矩阵）
实验七 排序
一、 实验目的
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<stdio.h>
#include<malloc.h>
//顺序表结构类型定义
typedef char datatype;
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("%2c",L->data[i]);
printf("\n");
}
//顺序表逆置
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;
}
}
实验一：第1题（2）
//单链表逆置的程序代码
#include<malloc.h>
#include<stdio.h>
//单链表结构类型定义
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("%2c",p->data);
p=p->next;
}
printf("\n");
}
//单链表逆置
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<stdio.h>
#include<malloc.h>
//链表结构类型定义
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);//输出循环链表
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("%c",p->data);
p=p->next;
}
printf("\n");
}
//输出循环链表
void print2(linklist*head)
{ linklist *p=head->next;
while(p!=head)
{
printf("%c",p->data);
p=p->next;
}
printf("\n");
}
//按字母、数字、其它字符分解单链表
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);
}
}
实验二：第1题
//判字符串中心对称的程序代码
#include<stdio.h>
#include<malloc.h>
#include<string.h>
//定义单链表结构类型
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*);
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("字符串\"%s\"中心对称\n",str);
else printf("字符串\"%s\"不是中心对称\n",str);
}
//栈初始化
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("%c",p->data);
p=p->next;
}
printf("\n");
}
//建立具有头结点的单链表
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;
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;i<n;i++){
push(s,p->data);
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<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//循环队列的结构类型定义
const int m=5;
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("1.Enter Queue 2.Delete Queue -1.Quit:");
scanf("%d",&key);
switch(key)
{ case 1: printf("Enter the Data:"); scanf("%d",&x);
enqueue(sq,x); break;
case 2: p=dequeue(sq);
if(p!=NULL) printf("%d\n",*p);
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("queue is full\n");
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("queue is empty\n"); return NULL;}
else { temp=(datatype*)malloc(sizeof(datatype));
sq->quelen--;
*temp=sq->sequ[(sq->rear-sq->quelen+m)%m];
return (temp);
}
}
实验三：第1题
//模式匹配的程序代码
#include<stdio.h>
#include<string.h>
#include<malloc.h>
//顺序串的结构类型定义
#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("输入串："); gets(S->str);
S->len=strlen(S->str);
printf("输入子串："); gets(subS->str);
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题
//删除子串的程序代码
#include<stdio.h>
#include<string.h>
#include<malloc.h>
//顺序串的结构类型定义
#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("输入串："); gets(S->str);
S->len=strlen(S->str);
strPut(S);
printf("删除的开始位置:");scanf("%d",&i);
printf("删除的字符个数:");scanf("%d",&m);
strDelete(S,i,m);
strPut(S);
}
//输出串
void strPut(seqstring*S)
{
int i;
for(i=0;i<S->len;i++)
printf("%c",S->str[i]);
printf("\n");
}
//删除子串
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;
}
}
实验四：第1题
//找马鞍点程序代码
#include<stdio.h>
#include<malloc.h>
//数组的结构类型定义
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("%d",&pa->A[i][j]);
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]<p->min[i]) p->min[i]=p->A[i][j];
}
for (j=0;j<n;j++)
{
p->max[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("%d,%d,%d\n",i,j,p->A[i][j]);
have=1;
}
if(!have) printf("矩阵中没有马鞍点！\n");
}
实验四：第2题
//对称矩阵相乘的程序代码
#include<stdio.h>
#include<malloc.h>
//数组结构类型的定义.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<size;i++)
scanf("%d",&x[i]);
}
//矩阵的输出
void output(datatype x[][n])
{
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
printf("%5d",x[i][j]);
printf("\n");
}
}
//对称矩阵相乘
void mult(array*p)
{
int i,j,k,t1,t2;
datatype s;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
s=0;
for(k=0;k<n;k++)
{
if(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<stdio.h>
#include<malloc.h>
//二叉链表的结构类型定义
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("\n");
swap(pb);
preorder(pb);
printf("\n");
}
//二叉树的建立
bitree*creattree()
{
char ch;
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("%c",p->data);
if(p->lchild!=NULL||p->rchild!=NULL)
{
printf("(");
preorder(p->lchild);
if(p->rchild!=NULL)printf(",");
preorder(p->rchild);
printf(")");
}
}
}
//交换左右子树
void swap(bitree*p)
{
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<stdio.h>
#include<malloc.h>
//二叉链表的结构类型定义
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("\n");
nodenum=countnode(root);
printf("结点总数是：%d\n",nodenum);
leafnum=countleaf(root);
printf("叶子结点总数是：%d\n",leafnum);
}
//建立二叉树
bitree*creattree()
{
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("%c",p->data);
if(p->lchild!=NULL||p->rchild!=NULL)
{
printf("(");
preorder(p->lchild);
if(p->rchild!=NULL) printf(",");
preorder(p->rchild);
printf(")");
}
}
}
//统计结点个数
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<stdio.h>
//图的邻接矩阵类型定义
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<n;i++)
visited[i]=0;
printf("输入出发点序号（0-7），输入-1结束：");
scanf("%d",&i);
if(i==-1) break;
dfsa(i);
}
}
//建立无向图邻接矩阵
void creatgraph()
{
int i,j,k;
char ch;
printf("输入8个顶点的字符数据信息:\n");
for(i=0;i<n;i++)
if((ch=getchar())!='\n') g->vexs[i]=ch;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
g->arcs[i][j]=0;
printf("输入10条边的起、终点i,j:\n");
for(k=0;k<e;k++)
{
scanf("%d,%d",&i,&j); //顶点序号从0开始
g->arcs[i][j]=g->arcs[j][i]=1;
}
}
//深度优先搜索遍历
void dfsa(int i)
{
int j;
printf("Node:%c\n",g->vexs[i]);
visited[i]=1;
for(j=0;j<n;j++)
if(g->arcs[i][j]==1&&visited[j]==0)dfsa(j);
}
实验七：第1题
//希尔排序的程序代码
#include<stdio.h>
//顺序表结构类型定义
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);//输出排序后的记录表
}
//建立顺序表
void create(rectype r[],int n)
{
printf("输入10个整型数：");
for(int i=0;i<n;i++)
scanf("%d",&r[D1+i].key);
}
//输出顺序表
void print(rectype r[],int n)
{
for(int i=0;i<n;i++)
printf("%5d",r[D1+i].key);
printf("\n");
}
//希尔排序
void shellsort(rectype r[],int d[])
{
int i,j,k,h;
rectype temp;
int maxint=32767;
for(i=0;i<D1;i++)
r[i].key=-maxint;//设置T个监视哨
k=0;
do{
h=d[k];//取一趟的增量
for(i=h+D1;i<N+D1;i++)
{
temp=r[i];
j=i-h;
while(temp.key<r[j].key)
{
r[j+h]=r[j];
j=j-h;
}
r[j+h]=temp;
}//组内直接插入法排序
print(r,N);//输出一趟的排序结果
k++;
}while(h!=1);
}
实验七：第2题
//双向起泡排序的程序代码
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
//顺序表结构类型定义
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()%90;
}
//输出顺序表
void print(sequenlist r[],int n)
{
for(int i=1;i<=n;i++)
printf("%5d",r[i].key);
printf("\n");
}
//双向起泡排序
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<r[j-1].key)
{
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("%5d",r[k].key);
printf("\n");
i++;
}
}
实验八：第1题
//分块查找的程序代码
#include<stdio.h>
//类型定义
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<recN;i++)
printf("%5d",r[i]);
printf("\n");
printf("输入所要查找记录的关键字：");
scanf("%d",&key);
loc=blksearch(r,idx,key,idxN);
if(loc!=-1) printf("查找到，是第%d个记录。\n",loc+1);
else printf("记录查找不到！\n");
}
//分块查找
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(k<idx[mid].key)high=mid-1;
else if(k>idx[mid].key)low=mid+1;
else
{
high=mid-1;
find=1;
}
}
if(low<n)
{
i=idx[low].low;//块的起始地址
bh=idx[low].high;//块的终止地址
}
//块内顺序查找
while(i<bh&&r[i].key!=k)i++;
if(r[i].key!=k)i=-1;
return i;
}
实验八：第2题
//判断二叉排序树的程序代码
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//二叉链表的结构类型定义
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("\n");
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("%d",&x);//输入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
{
if(s&&Q[front])
if(rear%2==0)Q[front]->lchild=s;
else Q[front]->rchild=s;
if(rear%2==1)front++;
}
scanf("%d",&x);;
}
return root;
}
//二叉树的输出
void preorder(bitree*p)
{
if(p!=NULL)
{
printf("%d",p->key);
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);
}
}