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