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

1说明每个实验题目含有一个 main 函数和一些函数，与实验题目相关的基本运算的函数定义和 main 函数定义的代码在附录以及对应的文件夹中给出，供上机实验参考使用。对于每个题目，只需要根据题目要求设计算法，补充函数定义，然后对程序进行编译、调试。2实验一 线性表一、 实验目的1熟悉线性表的顺序和链式存储结构2掌握线性表的基本运算3能够利用线性表的基本运算完成线性表应用的运算二、 实验内容1设有一个线性表 E=e1, e2, , en-1, en，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表 E= en , en-1 , , e2 , e1 ，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。 （文件夹：顺序表逆置、单链表逆置）2已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符） ，试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。 （文件夹：分解单链表）实验二 栈和队列一、 实验目的1熟悉栈和队列的顺序和链式存储结构2掌握栈和队列的基本运算3能够利用栈和队列的基本运算完成栈和队列应用的运算二、 实验内容1设单链表中存放有 n 个字符，试编写算法，判断该字符串是否有中心对称的关系，例如xyzzyx 是中心对称的字符串。 （提示：将单链表中的一半字符先依次进栈，然后依次出栈与单链表中的另一半字符进行比较。 ） （文件夹：判字符串中心对称）2假设以数组 sequm存放循环队列的元素，同时设变量 rear 和 quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示：队空的条件：sq-quelen=0；队满的条件：sq-quelen=m。 （文件夹：循环队列）实验三 串一、 实验目的1 熟悉串的顺序存储结构2 掌握串的基本运算及应用二、 实验内容1串采用顺序存储结构，编写朴素模式匹配算法，查找在串中是否存在给定的子串。 （文件夹：模式匹配）2若 S 是一个采用顺序结构存储的串，利用 C 的库函数 strlen 和 strcpy（或 strncpy）编写3一算法 void SteDelete(char*S,int I,int m)，要求从 S 中删除从第 i 个字符开始的连续 m 个字符。若 istrlen(S) ，则没有字符被删除；若 i+mstrlen(S) ，则将 S 中从位置 i 开始直至末尾的字符均删除。 （文件夹：删除 子串）实验四 数组一、 实验目的1熟悉数组的结构2掌握矩阵的压缩存储3能够对数组和矩阵的压缩存储进行运算二、 实验内容1. 若在矩阵 Amn中存在一个元素 Aij，其满足 Aij是第 i 行元素中最小值，且又是第 j 列元素中最大值，则称此元素为该矩阵的一个马鞍点。用二维数组存储矩阵Amn ，设计算法求出矩阵中所有马鞍点。 （文件夹：找马鞍点）2. A 和 B 是两个 nn 阶的对称矩阵，以行为主序输入对称矩阵的下三角元素，压缩存储存入一维数组 A 和 B，编写一个算法计算对称矩阵 A 和 B 的乘积，结果存入二维数组 C。 （文件夹：对称矩阵相乘 ）实验五 树一、 实验目的1熟悉二叉树的链式存储结构2掌握二叉树的建立、深度优先递归遍历等算法3能够利用遍历算法实现一些应用二、 实验内容1已知二叉树采用二叉链表存储结构，如果左、右子树非空，且左子树根结点大于右子树根结点，则交换根结点的左、右子树。即按要求交换二叉树及子树的左、右子树。（文件夹：交换 左右子树）2采用二叉链表结构存储一棵二叉树，编写一个算法统计该二叉树中结点总数及叶子结点总数。 （文件夹：统计二叉树结点）实验六 图一、 实验目的1熟悉图的邻接矩阵和邻接表的存储结构2熟悉图的邻接矩阵和邻接表的建立算法3掌握图的遍历算法二、 实验内容1 无向图采用邻接矩阵存储，编写深度优先搜索遍历算法，从不同的顶点出发对无向图进行遍历。 （文件夹：无向图邻 接矩阵）4实验七 排序一、 实验目的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#includeB CAD E F GH5/顺序表结构类型定义typedef char datatype;const int maxsize=1024;typedef struct datatype datamaxsize;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-last=0;char ch;while(ch=getchar()!=*) L-last+;L-dataL-last=ch;/输出顺序表void print(sequenlist*L)for(int i=1;ilast;i+)printf(“%2c“,L-datai);printf(“n“);/顺序表逆置void invert(sequenlist*L)int n=L-last/2;for(int i=1;idatai;L-datai=L-dataL-last-i+1;6L-dataL-last-i+1=temp;实验一：第 1 题（2）/单链表逆置的程序代码#include#include/单链表结构类型定义typedef char datatype;typedef struct nodedatatype 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*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)7printf(“%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#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;8resolve(head,letter,digit,other);/调用分解单链表的函数print2(letter);/输出循环链表print2(digit);print2(other);/建立单链表void create(linklist*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“);9/按字母、数字、其它字符分解单链表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=Awhile(p!=NULL) if(p-data=a实验二：第 1 题/判字符串中心对称的程序代码#include#include#include/定义单链表结构类型typedef char datatype;typedef struct node datatype data;struct node *next;linklist;/定义顺序栈结构类型const int maxsize=40;typedef struct datatype elementsmaxsize;int top;stack;void setnull(stack *int length(linklist*);void printlink(linklist*);void create(linklist *10void push(stack*,datatype);datatype pop(stack*);int symmetry(linklist*,stack*);/判字符串是否中心对称的函数声明void main()linklist *head;stack *s;datatype str80;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-top=-1;/求单链表长度int length(linklist*head) link