2017西电电院软件技术基础上机大作业答案.

2.
实验五
树
3
一、实验目的
1．熟悉二叉树的链式存储结构 2．掌握二叉树的建立、深度优先递归遍历等算法 3．能够利用遍历算法实现一些应用
二、实验内容
1．已知二叉树采用二叉链表存储结构，如果左、右子树非空，且左子树根结点大于右子树 根结点，则交换根结点的左、右子树。即按要求交换二叉树及子树的左、右子树。 （文 件夹：交换左右子树） 2．采用二叉链表结构存储一棵二叉树， 编写一个算法统计该二叉树中结点总数及叶子结点 总数。 （文件夹：统计二叉树结点）
实验四
数组
一、实验目的
1．熟悉数组的结构 2．掌握矩阵的压缩存储 3．能够对数组和矩阵的压缩存储进行运算
二、实验内容
1. 若在矩阵 Am×n 中存在一个元素 A[i][j]，其满足 A[i][j]是第 i 行元素中最小值，且又 是第 j 列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵 Am （文件夹：找马鞍点） ×n ，设计算法求出矩阵中所有马鞍点。 A 和 B 是两个 n×n 阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储 存入一维数组 A 和 B，编写一个算法计算对称矩阵 A 和 B 的乘积，结果存入二维数组 C。 （文件夹：对称矩阵相乘）
1．熟悉各种内部排序算法 2．能够编写程序显示排序过程中各趟排序的结果 3．能够编写一些排序的算法
二、实验内容
4
1． 采用希尔排序方法对顺序表中的证型数据进行排序，设计希尔排序算法并显示每趟排序 的结果。 （文件夹：希尔排序） 2． 编写一个双向起泡的排序算法，即在排序过程中交替改变扫描方向，同时显示各趟排序 的结果。 （文件夹：双向起泡排序）
2
2．假设以数组 sequ[m]存放循环队列的元素，同时设变量 rear 和 quelen 分别指示循环队列 中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。 提示：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m。 （文件夹：循环队列） 思路 5：队列的入操作是从尾部，出操作仕从头部，当入队列时，用数组存放循环队列的元 素， 需要判断当对尾越过数组上界时， 需要变成数组的下界， 当出队列时， 从队列头部开始， 根据队尾部和队列长度得到队列的头部， 同时考虑越过数组下界的问题， 从而改变成数组的 上界。
实验三
串
一、 实验目的
1． 熟悉串的顺序存储结构 2． 掌握串的基本运算及应用
二、 实验内容
1．串采用顺序存储结构， 编写朴素模式匹配算法， 查找在串中是否存在给定的子串。 （文件 夹：模式匹配） 思路 6：朴素模式匹配对于字串和子串逐个字符进行匹配，在某一位置如果该字符与子串中 的字符不相等时，那么进行回溯，子串到开始位置，字串到下一位置重新开始遍历，直到遍 历结束，判断在该字串中是否存在给定的子串。 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 开始直至末尾的 字符均删除。 （文件夹：删除子串） 思路 7：调用字符串函数在第 i 个字符删除，定义一个临时变量 temp,先将 S 中的 0 至 i-1 字 符全部复制到 temp 中，然后衔接 i+m-1 之后的字符串全部复制到 temp 中，最后将 temp 的 值重新复制到 S 中。
6
} //采用尾插法建立具有头结点的单链表 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 题
7
//分解单链表的程序代码 #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;
实验二
栈和队列
一、实验目的
1．熟悉栈和队列的顺序和链式存储结构 2．掌握栈和队列的基本运算 3．能够利用栈和队列的基本运算完成栈和队列应用的运算
二、实验内容
1．设单链表中存放有 n 个字符，试编写算法，判断该字符串是否有中心对称的关系，例如 xyzzyx 是中心对称的字符串。 （提示：将单链表中的一半字符先依次进栈，然后依次出 栈与单链表中的另一半字符进行比较。 ） （文件夹：判字符串中心对称） 思路 4：设置一个栈结果，将单链表中的元素逐个添加到栈中，入栈操作，栈有先进后出的 特点，因此栈底元素对应链表的第一个元素，栈顶元素对应链表的最后一个元素，刚好是链 表的逆置， 不断的出栈得到当前的栈顶元素与链表对应的元素进行比较， 如果有一俩个值不 相等的话，那么就可以判断该字符串是否具有中心对称关系。
实验六
图
一、实验目的
1．熟悉图的邻接矩阵和邻接表的存储结构 2．熟悉图的邻接矩阵和邻接表的建立算法 3．掌握图的遍历算法
二、实验内容
1． 无向图采用邻接矩阵存储， 编写深度优先搜索遍历算法， 从不同的顶点出发对无向图进 行遍历。 （文件夹百度文库无向图邻接矩阵）
A B D E F C G
H
实验七
排序
一、实验目的
实验八
查找
一、实验目的
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;
二、
实验内容
1．设有一个线性表 E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列次 序颠倒过来，成为逆线性表 E’={ en , en-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间， 并且用顺序表和单链表两种方法表示，分别用两个程序来完成。 （文件夹：顺序表逆置、 单链表逆置） 思路 1：对于顺序表，使用一个结构体，结构体中包含一个数组，来储存顺序表里的信息， 同时还有一个表示位置的变量来储存该顺序表的当前位置，便于循环遍历，在交换的时候， 其本质上只是使得该顺序表上的 DATA 实现逆序，在顺序表中等于对于数组的内容实现交 换逆序。 思路 2：对于线性表，使用结构体，包含 data，用来储存线性表里该节点的信息，同时还有 一个 nest 指针用于指向下一个节点，在计算机内部根据地址指向实现一个链表结构，当实 现该线性表逆序的时候， 我们先对该线性表进行循环遍历得到该线性表中节点的个数， 然后 从头开始遍历把线性表中每个节点的 data 都存储在一个数组里面，对于数组中的元素实现 逆序交换， 得到一个逆序后的数组然后循环遍历线性表对于线性表的每一个元素逐个重新赋 值，实现线性表的逆置。 2．已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字 和其他字符） ， 试编写算法构造三个以循环链表表示的线性表， 使每个表中只含有同一类 的字符，且利用原表中的结点空间，头结点可另辟空间。 （文件夹：分解单链表） 思路 3：根据每个对应的字符的值进行判断，如果该字符的值在“a”-“z”或者在“A”-“Z” 之间的话，那么就插入字符循环链表中，如果在“0”-“9”之间，就插入到数字循环链表 中，如果都不是，就插入到 other 循环链表中，对于单链表中的每一个节点逐个判断。
说明
每个实验题目含有一个 main 函数和一些函数，与实验题目相关 的基本运算的函数定义和 main 函数定义的代码在附录以及对应的文 件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目 要求设计算法，补充函数定义，然后对程序进行编译、调试。
1
实验一
一、
线性表
实验目的
1．熟悉线性表的顺序和链式存储结构 2．掌握线性表的基本运算 3．能够利用线性表的基本运算完成线性表应用的运算
5
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);