数据结构算法实验内容与指导.doc

数据结构算法实验内容与指导

1、 实验目的：将书中常用算法编写成程序，上机调试，验证算法的正确性，同时理解数据结构对于软件开发的意义。同时又能复习C++语言的重点与难点，熟悉vc++6.0调试环境，掌握一个完整程序的构成，为今后软件设计打下基础。
2、 实验要求：熟练掌握c++面象对象的编程思想及vc++6.0上机调试环境。
3、 实验内容：
（1）线性表顺序存储（顺序表类）的插入、删除等操作的实现
（2）线性表链式存储（单链表类）的建立、插入、删除等操作的实现
（3）特殊线性表进栈、退栈操作的实现
（4）顺序查找及二分查找算法的实现
（5）常用的几种排序算法的实现
（6）二叉树的建立、遍历算法的实现
（7）图的邻接矩阵的建立，及遍历算法实现

实验一：线性表顺序存储（顺序表类）的插入、删除等操作的实现
//SeqList.h
class SeqList
{
protected:
DataType *list; //数组
int maxSize; //最大元素个数
int size; //当前元素个数
public:
SeqList(int max=0); //构造函数
~SeqList(void); //析构函数
int Size(void) const; //取当前数据元素个数
void Insert(const DataType& item, int i);//插入
DataType Delete(const int i); //删除
DataType GetData(int i) const; //取数据元素
};
SeqList::SeqList(int max) //构造函数
{
maxSize = max;
size = 0;
list = new DataType[maxSize];
}
SeqList::~SeqList(void) //析构函数
{
delete []list;
}
int SeqList::Size(void) const //取当前数据元素个数
{
return size;
}
void SeqList::Insert(const DataType& item, int i) //插入
//在指定位置i前插入一个数据元素item
{
if (size == maxSize)
{
cout << "顺序表已满无法插入！" << endl;
exit(0);
}
if(i < 0 || i > size) //参数正确与否判断
{
cout << "参数i越界出错!" << endl;
exit(0);
}
//从size-1至i逐个元素后移
for(int j = size; j > i; j--) list[j] = list[j-1];
list[i] = item; //在i位置插入item
size++; //当前元素个数加1
}
DataType SeqList::Delete(const int i) //删除
//删除指定位置i的数据元素，删除的元素由函数返回
{
if (size == 0)
{
cout << "顺序表已空无元素可删！" << endl;
exit(0);
}
if(i < 0 || i > size - 1) //参数正确与否判断
{
cout<<"参数i越界出错!"<<endl;
exit(0);
}
DataType x = list[i]; //取到要删除的元素
//从i+1至size-1逐个元素前移
for(int j = i;j < size-1; j++) list[j] = list[j+1];
size--; //当前元素个数减1
return x; //返回删除的元素
}
DataType SeqList::GetData(int i) const //取数据元素
//取位置i的数据元素，取到的数据元素由函数返回
{
if(i < 0 || i > size - 1) //参数正确与否判断
{
cout << "参数i越界出错!" << endl;
exit(0);
}
return list[i]; //返回取到的元素
}
//ExamTest1.cpp
#include <iostream.h>
#include <stdlib.h>
typedef int DataType; //定义具体问题元素的数据类型
#include "SeqList.h"
void main(void)
{
SeqList myList(100); //定义顺序表类对象myList
int n = 10, x;

for(int i = 0; i < n; i++) //在myList中顺序插入10个元素
{cout<< “请输入插入元素x的值”<<endl;
cin>>x;
mylist.Insert(x,i);
}
myList.Delete(4); //删除myList中数据元素5
for(i = 0; i < myList.Size(); i++) //依次取myList中的元素并显示
cout << myList.GetData(i) << " ";
}
分析讨论：
问题1：请分析上述主函数的功能及运行结果；
问题2:完成P41例2-2建立学生情况表实验。
//ExamTest2.cpp
#include <iostream.h>
#include <stdlib.h>
struct StudentType
{
long number; //学号数据项
char name[10]; //姓名数据项
char sex[3]; //性别数据项
int age; //年龄数据项
}; //结构体StudentType
typedef StudentType DataType; //定义DataType为StudentType数据类型
#include "SeqList.h" //包含顺序表文件

void main(void)
{
SeqList myList(100);
StudentType x[3] = {{2000001, "张三", "男", 20},
{2000002, "李四", "男", 21},
{2000003, "王五", "女", 22}};
int n = 3;
DataType s;
for(int i = 0; i < n; i++) //在myList中顺序插入n个元素
myList.Insert(x[i], i);
for(i = 0; i < myList.Size(); i++) //依次取myList中的元素并显示
{
s = myList.GetData(i);
cout << s.number << s.name << s.sex << s.age << endl;
}
}
实验二：线性表链式存储（单链表类）的建立、插入、删除等操作的实现
//LinList.h
template <class T>
class LinList; //前视定义,否则友元无法定义
template <class T> //模板类型为T
class ListNode
{
friend class LinList<T>; //定义类LinList<T>为友元
private:
ListNode<T> *next; //指向下一结点的指针
T data; //定义为公有成员方便使用
public:
//构造函数1,用于构造头结点
ListNode(ListNode<T> *ptrNext = NULL)
{next = ptrNext;}
//构造函数2,用于构造其他结点
ListNode(const T& item, ListNode<T> *ptrNext = NULL)
{data = item; next = ptrNext;}
~ListNode(void){} //析构函数
};
//单链表类的定义
template <class T>
class LinList
{
private:
ListNode<T> *head; //头指针
int size; //当前的数据元素个数
ListNode<T> *Index(int i); //定位
public:
LinList(void); //构造函数
~LinList(void); //析构函数
int ListSize(void) const; //取当前数据元素个数
void Insert(const T& item, int i); //前插
T Delete(int i); //删除
T GetData(int i); //取元素
};
//单链表类的实现
template <class T>
LinList<T>::LinList(void) //构造函数
{
head = new ListNode<T>(); //头指针指向头结点
size = 0; //size的初值为0
}
template <class T>
LinList<T>::~LinList(void) //析构函数
{ ListNode<T> *p, *q;
p = head; //p指向第一个结点
while(p != NULL) //循环释放结点空间直至初始化状态
{ q = p;
p = p->next;
delete q;
}
size = 0; //结点个数置为初始化值0
head = NULL;
}
template <class T>
ListNode<T> *LinList<T>::Index(int i) //定位
//返回指向第i个数据元素结点的指针
//参数i的取值范围为：-1≤i≤size-1；i=-1时返回头指针
{
if(i < -1 || i > size-1)
{
cout << "参数i越界出错！" << endl;
exit(0);
}
if(i == -1) return head; //i为-1时返回头指针head
ListNode<T> *p = head->next; //p指向第一个数据元素结点
int j = 0; //从0开始计数
while(p != NULL && j < i) //寻找第i个结点
{
p = p->next;
j++;
}
return p; //返回第i个结点的指针
}
template <class T>
int LinList<T>::ListSize(void) const //取当前数据元素个数并返回
{
return size;
}
template <class T>
void LinList<T>::Insert(const T& item, int i) //插入
//在第i个结点后插入一个元素值为item的新结点
//参数i的取值范围为：0≤i≤size
{
if(i < 0 || i > size)
{
cout << "参数i越界出错！" << endl;
exit(0);
}
ListNode<T> *p = Index(i - 1); //p为指向第i-1个结点的指针
//构造新结点p，p的data域值为item，next域值为 p->next
ListNode<T> *q = new ListNode<T>(item, p->next);
p->next = q; //新结点插入第i个结点前
size++; //元素个数加1
}
template <class T>
T LinList<T>::Delete(int i) //删除
//删除第i个数据元素并返回。参数i的取值范围为：0≤i≤size-1
{
if(size == 0)
{
cout << "链表已空无元素可删！" << endl;
exit(0);
}
if(i < 0 || i > size-1)
{
cout << "参数i越界出错！" << endl;
exit(0);
}
ListNode<T> *s, *p = Index(i - 1); //p为指向第i-1个结点指针
s = p->next; //s指向第i个结点
p->next = p->next->next; //第i个结点脱链
T x = s->data;
delete s; //释放第i个结点空间
size--; //结点个数减1
return x; //返回第i个结点的data域值
}
template <class T>
T LinList<T>::GetData(int i) //取数据元素
//取第i个数据元素并返回。参数i的取值范围为：0≤i≤size-1
{
if(i < 0 || i > size-1)
{
cout << "参数i越界出错！" << endl;
exit(0);
}
ListNode<T> *p = Index(i); //p指向第i个结点
return p->data;
}
//ExamTest3.cpp
#include <iostream.h>
#include <stdlib.h>
#include "LinList.h"
void main(void)
{
LinList<int> myList;
Int s[]={10,20,30,40,50,60,70,80,90,100},n=10;
Int temp;
For(int I=0;I<n;I++)
MyList.Insert(s[I],I);
MyList.Delete(4);
For(I=0;I<myList.Size();I++)
{
temp=myList.GetData(i);
cout<<temp<<” “;
}
}
问题1：请分析上述主函数的功能及运行结果；
实验三：各种排序算法的实验
//sort.h
#include <iostream.h>
#include <stdlib.h>
void InsertSort (DataType a[], int n)
//用直接插入法对a[0]--a[n-1]排序
{
int i, j;
DataType temp;
for(i=0; i<n-1; i++)
{
temp = a[i+1];
j = i;
while(j > -1 && temp.key <= a[j].key)
{
a[j+1] = a[j];
j--;
}
a[j+1] = temp;
}
}
void ShellSort (datatype a[], int n, int d[], int numOfD)
//用希尔排序法对记录a[0]--a[n-1]排序
//各组内采用直接插入法排序
{
int i, j, k, m, span;
datatype temp;

for(m = 0; m < numOfD; m++)
{
span = d[m];
for(k = 0; k < span; k++)
{
for(i = k; i < n-span; i = i+span)
{
temp = a[i+span];
j = i;
while(j > -1 && temp.key <= a[j].key)
{
a[j+span] = a[j];
j = j-span;
}
a[j+span] = temp;
}
}
}
}
void SelectSort(datatype a[], int n)
/*用直接选择排序法对a[0]--a[n-1]排序*/
{
int i, j, small;
datatype temp;

for(i=0; i < n-1; i++)
{
small = i;
for(j = i+1; j < n; j++)
if(a[j].key < a[small].key) small=j;

if(small != i)
{
temp = a[i];
a[i] = a[small];
a[small] = temp;
}
}
}
void BubbleSort(datatype a[], int n)
//用冒泡排序法对a[0]--a[n-1]排序
{
int i, j, flag=1;
datatype temp;

for(i = 1; i < n && flag == 1; i++)
{
flag = 0;
for(j = 0; j < n-i; j++)
{
if(a[j].key > a[j+1].key)
{
flag = 1;
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
void QuickSort(datatype a[], int low, int high)
//用递归方法对对象a[low]--a[high]进行快速排序
{
int i, j;
datatype temp;

i = low;
j = high;
temp = a[low];

while(i < j)
{
//在数组的右端扫描
while(i < j && temp.key <= a[j].key) j--;
if(i < j)
{
a[i] = a[j];
i++;
}

//在数组的左端扫描
while(i < j && a[i].key < temp.key) i++;
if(i < j)
{
a[j] = a[i];
j--;
}
}
a[i] = temp;

//对子对象数组进行递归快速排序
if(low < i) QuickSort(a, low, i-1);
if(i < high) QuickSort(a, j+1, high);
}
void Merge(DataType a[], int n, DataType swap[], int k)
//k为有序子数组的长度，一次二路归并排序后的有序子序列存于数组swap中
{
int m = 0, u1,l2,i,j,u2;

int l1 = 0; //第一个有序子数组下界为0
while(l1+k <= n-1)
{
l2 = l1 + k; //计算第二个有序子数组下界
u1 = l2 - 1; //计算第一个有序子数组上界
u2 = (l2+k-1 <= n-1)? l2+k-1: n-1;//计算第二个有序子数组上界

//两个有序子数组合并
for(i = l1, j = l2; i <= u1 && j <= u2; m++)
{
if(a[i].key <= a[j].key)
{
swap[m] = a[i];
i++;
}
else
{
swap[m]=a[j];
j++;
}
}

//子数组2已归并完，将子数组1中剩余的元素存放到数组swap中
while(i <= u1)
{
swap[m] = a[i];
m++;
i++;
}

//子数组1已归并完，将子数组2中剩余的元素存放到数组swap中
while(j <= u2)
{
swap[m] = a[j];
m++;
j++;
}

l1 = u2 + 1;
}

//将原始数组中只够一组的数据元素顺序存放到数组swap中
for(i = l1; i < n; i++, m++) swap[m] = a[i];
}

void MergeSort(DataType a[], int n)
{
int i, k = 1; //归并长度从1开始
DataType *swap = new DataType[n]; //申请动态数组空间

while(k < n)
{
Merge(a, n, swap, k); //调用归并函数Merge(a, n, swap, k)
for(i = 0; i < n; i++)
a[i] = swap[i]; //将元素从临时数组swap放回数组a中
k = 2 * k; //归并长度加倍
}
delete []swap; //释放动态数组空间
}
//exam.cpp
#include <iostream.h>
#include <stdlib.h>
#define N 8
typedef int KeyType;
struct DataType
{ KeyType key;
};
#include "Sort.h"
void main(void)
{ DataType test[8];
int d[N],I=0,p,cnt=0,low,high;
char c;
cout<<”请输入”<<N<<”个”<<endl;
for(I=0;I<N;I++)
cin>>test[I];
cout<<”请选择排序方式”<<endl;
cout<<”1-直接插入排序”<<endl;
cout<<”2-希尔排序”<<endl;
cout<<”3-直接选择排序”<<endl;
cout<<”4-冒泡排序”<<endl;
cout<<”5-快速排序”<<endl;
cout<<”6-归并排序”<<endl;
cout<<”0-退出”<<endl;
cin>>c;
switch( c)
{
case ‘1’: {InsertSort(test,N);break;}
case ‘2’:
{p=N;
while((p/2)!=1)
{ d[I]=p/2; cnt++;p=p/2;I++;}
d[I]=1;cnt++;
ShellSort(text,N,d,cnt);break;
}
case ‘3’:{SelectSort(test,N);break;}
case ‘4’:{BubbleSort(text,N);break;}
case ‘5’:{ low=0;high=N-1;
QuickSort(text,low,high); break;}
case ‘6’:{MergeSort(text,N);break;}
case ‘0’: {exit(0);break;}
}
}
16