实验 1 线性表及其应用实验性质：验证性实验学时：2 学时一、实验目的1. 掌握线性表的顺序存储结构在计算机的表示方法及其基本操作的实现；2. 掌握线性表的链式存储结构在计算机的表示方法及其基本操作的实现；3. 能够利用线性表结构对实际问题进行分析建模，利用计算机求解二、实验预备知识1•复习C/C++语言相关知识(如：结构体的定义、typedef的使用、函数的定义、调用 及参数传递方式)；2•阅读并掌握顺序表与链表的类型定义及其查找、插入、删除等基本操作三、实验内容1. 理解并分别用顺序表、链表的操作运行下列程序：#include using namespace std;#include "Status.h"typedef int ElemType;#i nclude "SqList.h" 〃用 #i nclude "Li nkList.h"替换void main(){SqList L; 〃用 LinkList L;替换，与#include "LinkList.h"配合int n,i;ElemType e;InitList(L);cout<<"\nL=";ListTraverse(L);coutvv"\n请设置将向线性表L中输入的元素个数：";cin>>n;CreateList(L,n);coutvv"\nL=";ListTraverse(L);coutvv"\nL 的表长为： "vvListLength(L)vvendl;coutvv"\n 请输入想要获取的元素位序： ";cin>>i;if(GetElem(L,i,e)) coutvv"\n 第"vvivv"个元素为："vvevve ndl;else coutvv"\n 第"vvivv"个元素不存在！ "vvendl;coutvv"\n 请输入要查找的元素： ";cin>>e;if(i=LocateElem(L,e)) coutvv"\n 元素"vvevv"的位置为："vvivvendl;else coutvv"\n 元素"vvevv"不存在！ "vvendl;cout<<"\n 请输入插入位置和所插入元素："; cin>>i>>e;if(ListInsert(L,i,e)){coutvv"\nL=";ListTraverse(L);}else coutvv"\n 插入操作失败！ "vvendl;coutvv"\n 请输入被删元素的位置：";cin>>i;if(ListDelete(L,i,e)) coutvv"\n 被删元素为："vvevvendl;else coutvv"\n 删除操作失败！ "vvendl;coutvv"\nL=";ListTraverse(L);}本题目说明：(1) 头文件Status.h的内容如下：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;(2) 头文件SqList.h (内容包括顺序表的结构定义及基本操作实现)。
3) 头文件LinkList.h (内容包括链表的结构定义及基本操作实现)4) 顺序表中基本操作的补充：• CreateList(&L,n)：向顺序表 L 中输入 n 个元素(OWnWMAXSIZE) Status CreateList(SqList &L,int n){int i;if(!L.elem||nvO||n>MAXSIZE) return ERROR;coutvv"\n 请输入"vvnvv"个元素："；for(i=1;iv=n;i++)cin>>L.elem[i-1]; 〃可以用随机函数rand()自动生成L.length=n; return OK;}• ListTraverse(L)：以线性表的记录形式遍历输出顺序表L,例如：(a1,a2,…, ai,・・・a n)void ListTraverse(SqList L){int i;cout<<'(';for(i=1;i<=L.length;i++)cout<
3.(任选题)已知有两个多项式P(x)和Q(x),基于链表设计算法实现P(x)+Q(x)运 算,而且不重新开辟存储空间实验 2 栈和队列的实现实验性质：验证性实验学时：2 学时一、实验目的1. 掌握栈的特点、在计算机中的存储表示方法及其基本操作的实现；2. 掌握队列的特点、在计算机中的存储表示方法及其基本操作的实现；3. 能够利用栈和队列求解一些常见问题二、实验预备知识1. 阅读并掌握顺序栈、链栈两种存储方法的类型定义及其压栈、弹栈等基本操作2. 阅读并掌握循环队列、链队列两种存储方法的类型定义及其入队、出队等基本操作三、实验内容1. 理解并用顺序栈操作运行下列程序：#include using namespace std;#include "Status.h"typedef int ElemType;#include "SqStack.h"void main(){SqStack S;ElemType e;InitStack(S);Push(S,2);Push(S,4);Push(S,6);Push(S,8);cout<<"\n 由栈底至栈顶的元素为：";StackTraverse(S);coutvv"\n 栈的长度为："vvStackLength(S)vvendl;GetTop(S,e);coutvv"\n 栈顶元素为： "vvevvendl;Pop(S,e);coutvv"\n 由栈底至栈顶的元素为： ";StackTraverse(S);coutvv"\n 栈的长度为： "vvStackLength(S)vvendl;GetTop(S,e);coutvv"\n 栈顶元素为： "vvevvendl;}2. 理解并用循环队列、链队列操作运行下列程序：#include viostream>using namespace std;#include "Status.h" typedef int ElemType;#include "SqQueue.h"void main(){SqQueue Q;ElemType e;InitQueue(Q);EnQueue(Q,1);EnQueue(Q,3);EnQueue(Q,5);EnQueue(Q,7);GetHead(Q,e);coutvv"\n 队头元素为："vvevvendl;cout<<"\n 队列中从队头至队尾的元素为： ";QueueTraverse(Q);coutvv"\n 队列的长度为： "vvQueueLength(Q)vvendl; DeQueue(Q,e);coutvv"\n 出队的元素为： "vvevvendl;coutvv"\n 出队操作完成之后队列中从队头至队尾的元素为： ";QueueTraverse(Q);coutvv"\n 队列的长度为： "vvQueueLength(Q)vvendl;} 本题目说明：(1) 头文件Status.h的内容同实验1。
2) 头文件SqStack.h (内容包括顺序栈的结构定义及基本操作实现)3) 头文件SqQueue.h (内容包括循环队列的结构定义及基本操作实现)4) 顺序栈中基本操作的补充：• StackTraverse(S):从栈底到栈顶依次对S的每个数据元素进行访问void StackTraverse(SqStack S){ElemType *p;p=S.base; while(p!=S.top){cout<<*p++<<" ";} cout<
实验 3 树和二叉树实验性质：验证性实验学时：4 学时一、实验目的4. 掌握二叉树的特点、在计算机中的存储表示方法及其基本操作的实现；5. 能够利用二叉树求解一些常见问题二、实验预备知识3. 阅读并掌握二叉树二叉链表存储方法的类型定义及其创建、遍历等基本操作4. 阅读并掌握赫夫曼树的创建、赫夫曼编码的求得等基本操作三、实验内容1. 理解并用二叉链表的操作运行下列程序：#include using namespace std;#include "Status.h"typedef char ElemType;#include "BiTree.h"void main(){BiTree T;CreateBiTree(T);cou t〈〈""二叉树的深度为：""〈〈Dep th(T)〈〈endl;cou t〈〈""二叉树中结点个数为：""〈〈NodeCoun t(T)〈〈endl;cou t〈〈""二叉树中叶子结点个数为：""〈〈LeavesNodeCoun t(T)〈〈endl;cou t〈〈""先序遍历：""；PreOrderTraverse(T);cout〈〈""\n 中序遍历：""；InOrderTraverse(T);cout〈〈""\n 后序遍历：""；PostOrderTraverse(T);cout〈〈endl;}本题目说明：(1)头文件 Status.h 的内容同实验1。
2)头文件BiTree.h (内容包括二叉树的二叉链表中结点的结构定义及二叉链表 基本操作的实现) 3 )基本操作的补充：LeavesNodeCoun t(T)：二叉树中叶子结点的个数int LeavesNodeCount(BiTree T){if(!T) return 0;else if(!T->lchild&&!T->rchild) return 1;else return LeavesNodeCount(T->lchild)+LeavesNodeCount(T->rchild); }2. 已知某系统在通信联络中只可能出现8种字符，其概率分别为0.。