实验一 线性表的操作
实验类型：验证性 实验要求：必修 实验学时： 2学时
一、实验目的：
参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。
二、实验要求：
1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1．设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：建立一个线性表，首先依次输人数据元素1，2，3，…，10，然后删除数据元素6，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过10个。
第一题源代码： #include using namespace std; template
//定义模板类SeqList cla SeqList { private: int length,x,j,data[10]; public: public: SeqList( )
//无参构造函数
{
length=0;
}
SeqList(T a[ ], int n)
//有参构造函数
{
for(int i=0;i
data[i]=a[i];
length=n; } ~SeqList( )
//析构函数为空
{
}
int Length( )
//求线性表的长度
{
return length; }
T Get(int i)
//按位查找，取线性表的第i个元素
{ } int Locate(T x )
//按值查找，求线性表中值为x的元素序号
{ } void Insert(int i, T x)
//在线性表中第i个位置插入值为x的元素
{ } T Delete(int i)
{
if(length==0)
throw\"下溢\";
if(ilength)
throw\"位置异常\";
x=data[i-1];
for(j=i;j
data[j-1]=data[j];
length--;
return x; } void PrintList( )
{
for(int i=0;i
cout
\";
cout
void main() { int n=10,a[10]={1,2,3,4,5,6,7,8,9,10}; SeqList theseqlist(a,n); cout
cout
//删除线性表的第i个元素
//注意此处j已经是元素所在的数组下标 //遍历线性表，按序号依次输出各元素
------------------------- 2．设计一个带头结点的单链表类，要求：
(1)带头结点单链表类的成员函数包括取数据元素个数、插入元素、删除所有值为k的元素、取数据元素。
(2)设计一个测试主函数，实际运行验证所设计循环单链表类的正确性。 第二题源代码： #include using namespace std; template
struct Node { T data; Node *next; }; /*****************************/ template cla LinkList { private:
Node *first;
//单链表头指针
int length; public:
LinkList()
{
first=new Node;
first->next=NULL;
}
LinkList(T a[],int n)
//建立n个节点的指针
{
Node *s;
first=new Node;
first->next=NULL;
//初始化一个空链表
for(int i=0;i
{
s=new Node;
s->data=a[i];
s->next=first->next;
first->next=s;
}
length=n;
}
~LinkList()
{
Node *p=first;
while(p)
{
Node *q;
q=p;
p=p->next;
delete q;
}
}
int Length();
//求单链表长度
T Get(int i);
//取单链表第i个节点元素值
int Locate(T x);
//求单链表值为x的元素序号
void Insert(int i,T x); //在单链表中第i个位置插入元素值x的节点
T Delete(int i);
//在单链表中删除第i个节点
void PrintList();
// 遍历单链表，按序号依次输出个元素 }; /********************************/ template int LinkList::Length() { return length; } /******************************/ template T LinkList::Get(int i) { int j; Node *p; p=first->next; j=1; while(p&& j
p=p->next;
j++; } if(!p)
throw \"位置\"; else
return p->data; } /***********************************/ template int LinkList::Locate(T x) { Node *p; p=first; for(int i=0;i
p=p->next;
if(p->data==x)
return i+1; } } /***********************************/ template void LinkList::Insert(int i,T x) { Node *p; int j; p=first; j=0; while(p&&j
p=p->next;
j++; } if(!p)
throw\"位置\"; else {
Node *s;
s=new Node;
s->data=x;
s->next=p->next;
p->next=s; } length++; } /**************************************/ template T LinkList::Delete(int i) { Node *p; int j; p=first; j=0; while(p&&j
p=p->next;
j++; } if(!p||!p->next)
throw\"位置\"; else {
Node *q;
q=new Node;
int x;
q=p->next;
x=q->data;
p->next=q->next;
delete q;
length--;
return x; }
} /*******************************************/ template void LinkList::PrintList()
// 遍历单链表，按序号依次输出个元素 { Node *p; p=first; for(int i=0;i
p=p->next;
coutdata)
int r[ ]={10,9,8,7,6,5,4,3,2,1};
LinkList a( r , 10 );
cout
a.PrintList();
cout
a.Insert(1,-2);
//执行插入操作;
a.Insert(2,-1);
a.Insert(3,0 );
cout
a.PrintList();
cout
a.Delete(1);
a.Delete(1);
a.Delete(1);
cout
a.PrintList();
cout
cout
cout
cout
//查找链表中第 5 个元素
cout
心得体会：
实验二 栈、队列、串的操作
实验类型：验证性 实验要求：必修 实验学时： 2学时
一、实验目的：
参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。
二、实验要求：
1、掌握栈、队列、串的特点。掌握特殊线性表的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1.堆栈类测试和应用问题。要求：
设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 第一题源代码： #include using namespace std; /********************************************************/ const int StackSize=10; template cla SeqStack { private:
T data[StackSize];
int top; public:
SeqStack()
{
top=-1;
}
~SeqStack()
{
}
void push(T x);
T pop();
T GetTop()
{
if(top!=-1)
return data[top];
}
bool Empty()
{
top=-1?(return 1):(return 0);
} };
template void SeqStack::push (T x) { if(top==StackSize-1)
throw \"上溢\"; top++; data[top]=x; } template T SeqStack::pop() { T x; if(top==-1)
throw \"下溢\"; x=data[top--]; return x; }
/****************************************************/ template struct Node { T data; Node *next; };
template cla LinkStack { private: Node *top; public: LinkStack() {
top=NULL; } ~LinkStack() {
while(top)
{
Node *p;
p=top->next;
delete top;
top=p;
}
} void push(T x); T pop(); T gettop() {
if(top!=NULL)
return top->data; } bool Empty() {
top==NULL?return 1:return 0; } };
template void LinkStack::push(T x) { Node *s; s=new Node;
//没有申请空间时 会出现错误！
s->data=x; s->next=top; top=s; } template T LinkStack::pop() { T x; Node *p; if(top==NULL)
throw \"下溢\"; x=top->data; p=top; top=top->next; delete p; return x; }
/******************************************************/ void main() { SeqStack aa; LinkStack bb;
for(int i=1;i
aa.push(i);
cout
int k=0;
k=aa.pop();
cout
\"; }
cout
for( i=1;i
bb.push(i);
cout
int j=0;
j=bb.pop();
cout
\"; } cout
2.队列类测试和应用问题。要求：
设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把 1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。
第二题源代码： #include #include using namespace std;
const int QueueSize=100;
/**************************************/ template cla CirQueue { public: T data[QueueSize];
int front, rear;
CirQueue( ) {
front=rear=0; }
~ CirQueue( ) {
}
void EnQueue(T x)
{
if ((rear+1) % QueueSize ==front)
throw \"上溢\";
rear=(rear+1) % QueueSize;
data[rear]=x;
} T GetQueue( )
{
if (rear==front) throw \"下溢\";
int i=(front+1) % QueueSize;
return data[i]; } T DeQueue( ) {
if (rear==front)
throw \"下溢\";
front=(front+1) % QueueSize;
return data[front];
} }; /*********************************************/ template struct Node { T data; Node *next; };
/*********************************************/ template cla LinkQueue { private: Node *front,*rear;
//队头队尾指针 public: LinkQueue();
~LinkQueue() { } void EnQueue(T x);
//将x入队
T DeQueue();
//将队头元素出队
T GetQueue()
{
if(front!=rear)
return front->next->data;
//取对头元素
} bool Empty()
//判断链队列是否为空
{
front==rear?return 1:return 0; } }; /***************************************/ template LinkQueue::LinkQueue() { Node *s; s=new Node; s->next=NULL;
//创建头结点s front=rear=s; } /***************************************/ template void LinkQueue::EnQueue(T x) { Node *s; s=new Node; s->data=x; s->next=NULL; rear->next=s; rear=s; } /***************************************/ template T LinkQueue::DeQueue() { Node *p; T x; if(rear==front)
throw\"下溢\"; p=front->next; x=p->data; front->next=p->next; if(p->next==NULL)
rear=front; delete p; return x; } /***********************************************/ void main() { CirQueue a; LinkQueue b; for(int i = 1 ; i
a.EnQueue(i);
b.EnQueue(i); } for( i = 1 ;i
int k,j(0) ;
k = a.DeQueue();
j=b.DeQueue();
cout
\"
心得体会：
实验三 多维数组和广义表的操作
实验类型：验证性 实验要求：必修 实验学时： 2学时
一、实验目的：参照给定的多维数组类和广义表类的程序样例，验证给出的多维数组和广义表的常见算法，并实现有关的操作。
二、实验要求：
1、掌握多维数组和广义表的特点。掌握它们的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1.设计函数建立一个n*n阶的对称矩阵。要求：
（1）实现将对称矩阵用一维数组存储输出。 （2）实现矩阵转置算法。 （3）实现魔方阵算法。
（4）设计一个测试例子，并编写主程序进行测试。
第一题源代码： 1.1 #include using namespace std; int a[10][10]; int save[100]; int main(){ int n,i,j; puts(\"输入矩阵的维数 N\"); cin >> n; for( i = 0 ;i
for( j =0 ; j
a[i][j] = rand() % 10 + 1;
a[j][i] = a[i][j];
}
for( i = 0 ;i
for( j = 0 ; j
cout
cout
}
puts(\"转化后: \") ;
int k = 0;
for( i = 0 ;i
for( j = 0 ; j
{
k = i * ( i + 1) / 2 + j;
save[k] = a[i][j]; k++; }
for(i = 0; i
cout
运行结果：
1.2 #include using namespace std; const int MaxTerm=100;
template
struct element { int row, col; T item ; };
struct SparseMatrix { element data[MaxTerm]; int mu, nu, tu; };
void Trans1(SparseMatrix A, SparseMatrix &B) { B.mu=A.nu; B.nu=A.mu; B.tu=A.tu; if (B.tu>0)
{
int pb = 0;
for (int col = 0; col
for(int pa = 0; pa
if (A.data[pa].col==col )
{
B.data[pb].row= A.data[pa].col ;
B.data[pb].col= A.data[pa].row ;
B.data[pb].item= A.data[pa].item;
pb++;
} } } int main() { int i; SparseMatrix AA,BB; puts(\"输入行数 列数 非零元素个数\"); cin >> AA.mu >> AA.nu >> AA.tu; puts(\"输入三元表:\");
//puts() 与 cout 一样
for( i = 0 ;i
cin >> AA.data[i].row ;
cin >> AA.data[i].col ;
cin >> AA.data[i].item ; } Trans1(AA,BB); puts(\"输出三元表í:\"); for( i = 0 ;i
cout
cout
cout
return 0; } 运行结果：
心得体会：
实验四 树和二叉树
实验类型：验证性 实验要求：必修 实验学时： 2学时
一、实验目的：
参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。
二、实验要求：
1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1．设计实现二叉树类，要求：
（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。
（2）实现二叉树层次遍历的非递归算法。
（3） 假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。 （4）编写求二叉树高度的函数 （5）编写一主函数来验证算法实现 第一题源代码：
#include using namespace std; template
struct BiNode { T data; BiNode *lchild,*rchild; };
template cla BiTree { private:
static int i;
BiNode * root;
void Creat(BiNode *&root)
{
char ch;
cin>>ch;
if (ch==\'#\') root=NULL;
else
{
root=new BiNode;
root->data=ch;
Creat(root->lchild);
Creat(root->rchild);
}
}
void Release(BiNode *root)
{
if(root!=NULL)
{
Release(root->lchild);
Release(root->rchild);
delete root;
}
}
//前序建立扩展二叉树 //建立一棵空树
//生成一个结点 //递归建立左子树 //递归建立右子树
void PreOrder(BiNode * root)
//前序遍历 { if(root==NULL)
return; else {
coutdata;
PreOrder(root->lchild);
PreOrder(root->rchild); }
} void InOrder(BiNode *root)
{ if(root==NULL)
return; else {
InOrder(root->lchild);
coutdata);
InOrder(root->rchild); } } void PostOrder(BiNode * root)
{ if(root==NULL)
return; else {
InOrder(root->lchild);
InOrder(root->rchild);
coutdata); } } void LevelOrder(BiNode* root) {
BiNode * Q[100];
int front = 0, rear = 0;
//中序遍历二叉树
//后序遍历二叉树
//采用顺序队列，并假定不会发生上溢
if (root==NULL)
return;
Q[++rear]=root;
while (front!=rear)
{
BiNode * q=Q[++front];
coutdata;
if (q->lchild!=NULL)
Q[++rear]=q->lchild;
if (q->rchild!=NULL)
Q[++rear]=q->rchild;
}
}
void showleaf(BiNode *root)
//显示叶子节点，并统计个数
{
if(root==NULL)
{
return;
}
else
{
if((root->lchild==NULL)&&(root->rchild==NULL))
{
coutdata;
i++;
}
else
{
showleaf(root->lchild);
showleaf(root->rchild);
}
}
}
int Depth(BiNode *root)
//算法求二叉树的深度
{
if (root==NULL)
return 0;
else
{
int hl= Depth(root->lchild);
int hr= Depth(root ->rchild);
if(hl>hr)
return hl+1;
else
return hr+1;
}
} public: BiTree() {
Creat(root);
}
BiTree(BiNode *root) { } ~BiTree() {
Release(root); }
void display() {
cout
PreOrder(root);
cout
cout
InOrder(root);
cout
cout
PostOrder(root);
cout
cout
LevelOrder(root);
cout
cout
showleaf(root);
\"; \"; \"; \"; \";
cout
cout
cout
\"
} }; template int BiTree::i=0;
void main() { cout AA; AA.display(); }
运行结果：
