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

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

1、实验目的：将书中常用算法编写成程序，上机调试，验证算法的正确性，同时理解数

据结构对于软件开发的意义。同时又能复习C++语言的重点与难点，熟悉VC++6.0调

试环境，掌握一个完整程序的构成，为今后软件设计打下基础。

2、实验要求：熟练掌握C++面象对象的编程思想及VC++6.0上机调试环境。

3、实验内容：

（1）线性表顺序存储（顺序表类）的插入、删除等操作的实现

（2）线性表链式存储（单链表类）的建立、插入、删除等操作的实现

（3）特殊线性表进栈、退栈操作的实现

（4）顺序查找及二分查找算法的实现

（5）常用的几种排序算法的实现

（6）二叉树的建立、遍历算法的实现

（7）图的邻接矩阵的建立，及遍历算法实现

实验一：线性表顺序存储(顺序表类)的插入、删除等操作的实现

//SeqList.h

classSeqList

protected:

DataType*list;〃数组

intmaxSize;〃最大元素个数

intsize;〃当前元素个数

public:

SeqList(intmax=0);〃构造函数

-SeqList(void);〃析构函数

intSize(void)const;//取当前数据元素个数

voidInsert(constDataType&item,inti);〃插入

DataTypeDelete(constinti);//删除

DataTypeGetData(inti)const;〃取数据元素

)；

SeqList::SeqList(intmax)〃构造函数

maxSize=max;

size=0;

list=newDataTypelmaxSizeJ;

SeqList::~SeqList(void)〃析构函数

deleteIJlist;

intSeqList::Size(void)const〃取当前数据元素个数

returnsize;

)

voidSeqList::Insert(constDataType&item,inti)〃插入

〃在指定位置i前插入一个数据元素item

{

if(size==maxSize)

cout«”顺序表己满无法插入！"<<endl;

exit(0);

if(i<0||i>size)〃参数正确与否判断

(

cout<<"参数i越界出错!"<<endl;

exit(O);

)

〃从size-1至i逐个元素后移

for(intj=size;j>i;j—)listfj]=listQ-1];

listfi]=item;〃在i位置插入item

size++;〃当前元素个数加I

)

DataTypeSeqList::Delete(constinti)〃删除

〃删除指定位置i的数据元素，删除的元素由函数返回

(

if(size==0)

(

cout<<"顺序表已空无元素可删！"<<endl;

exit(0);

}

if(i<O||i>size-1)〃参数正确与否判断

(

cout«"参数i越界出错!"《endl;

exit(O);

)

DataTypex=list[i];〃取到要删除的元素

〃从i+1至size-1逐个元素前移

for(inlj=i;j<size-1;j++)list[j]=list[j+l];

size-;〃当前元素个数减I

returnx;〃返回删除的元素

)

DataTypeSeqList::GetData(inti)const//取数据元素

〃取位置i的数据元素，取到的数据元素由函数返回

(

if(i<O||i>size-1)//参数正确与否判断

(

cout<<"参数i越界出错!"<<endl;

exit(O);

}

returnlist[i];〃返回取到的元素

//ExamTest1,cpp

#include<iostream.h>

#include<stdlib.h>

typedefintDataType;〃定义具体问题元素的数据类型

#include"SeqList.h"

voidinain(void)

(

SeqListmyList(lOO);〃定义顺序表类对象myList

intn=10,x;

for(inti=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>

structStudentType

(

longnumber;〃学号数据项

charnamefl01;〃姓名数据项

charsex13J;//性别数据项

intage;〃年龄数据项

);//结构体StudentType

typedefStudentTypeDataType;〃定义DataType为StudentType数据类型

#include"SeqList.h1'〃包含顺序表文件

voidmain(void)

SeqListmyList(lOO);

StudentTypex[3]={{2000001,“张三一男”,20},

{2000002,“李四“，“男”,21},

{2000003,“王五“，“女”,22}};

intn=3;

DataTypes;

for(inti=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.sex«s.age«endl;

实验二：线性表链式存储（单链表类）的建立、插入、删除等操作的实现

//LinList.h

template<classT>

classLinList;〃前视定义，否则友元无法定义

template<classT>〃模板类型为T

classListNode

friendclassLinList<T>;//定义类LinList<T>为友元

private:

ListNode<T>*next;〃指向下一结点的指针

Tdata;〃定义为公有成员方便使用

public:

〃构造函数1,用于构造头结点

ListNode(ListNode<T>*ptrNext=NULL)

{next=ptrNext;}

〃构造函数2,用于构造其他结点

ListNode(constT&item,ListNode<T>*ptrNext=NULL)

{data=item;next=ptrNext;)

-ListNode(void){)〃析构函数

);

〃单链表类的定义

template<classT>

classLinList

private:

ListNode<T>*head;〃头指针

intsize;〃当前的数据元素个数

ListNode<T>*Index(inti);〃定位

public:

LinList(void);〃构造函数

-LinList(void);〃析构函数

intListSize(void)const;〃取当前数据元素个数

voidInsert(constT&item,inti);//前插

TDelete(inti);〃删除

TGetData(inti);//取元素

）；

〃单链表类的实现

template<classT>

LinList<T>::LinList(void)〃构造函数

head=newListNode<T>();〃头指针指向头结点

size=0;//size的初值为0

)

template<classT>

LinList<T>::〜LinList(void)〃析构函数

{ListNode<T>*p,*q;

p=head;〃p指向第一个结点

while(p!=NULL)〃循环释放结点空间直至初始化状态

{q=p；

p=p->next;

deleteq;

)

size=0;〃结点个数置为初始化值0

head=NULL;

)

template<classT>

ListNode<T>*LinList<T>::Index(inti)//定位

〃返回指向第i个数据元素结点的指针

〃参数1的取值范围为：-1〈忘加6-1-=-1时返回头指针

if(i<-1||i>size-1)

(

cout«”参数i越界出错!«endl;

exit(O);

)

if(i==-1)returnhead;//i为-1时返回头指针head

ListNode<T>*p=head->next;〃p指向第一个数据元素结点

intj=0;〃从0开始计数

while(p!=NULL&&j<i)〃寻找第i个结点

(

p=p->next;

j++;

}

returnp;〃返回第i个结点的指针

)

template<classT>

intLinList<T>::ListSize(void)const〃取当前数据元素个数并返回

{

returnsize;

)

template<classT>

voidLinList<T>::Insert(constT&item,inti)〃插入

//在第i个结点后插入一个元素值为item的新结点

〃参数i的取值范围为：OWiWsize

(

if(i<0||i>size)

(

coutw”参数i越界出错！"«endl;

exit(O);

}

ListNode<T>*p=Index(i-1);//p为指向第i-1个结点的指针

〃构造新结点p,p的data域值为item,next域值为p->next

ListNode<T>*q=newListNode<T>(item,p->next);

p->next=q;〃新结点插入第i个结点前

size++;〃元素个数加1

)

template<classT>

TLinList<T>::Delete(inti)〃删除

//删除第i个数据元素并返回。参数i的取值范围为：0<iWsize-l

(

if(size==0)

(

coutvc”链表已空无元素可删！"<<endl;

exit(O);

)

if(i<0||i>size-1)

(

coutv<"参数i越界出错！n«endl;

exit(O);

)

ListNode<T>*s,*p=Index(i-1);//p为指向第i-1个结点指针

s=p->next;〃s指向第i个结点

p->next=p->next->next;〃第i个结点脱链

Tx=s->data;

deletes;〃释放第i个结点空间

size—;〃结点个数减1

returnx;〃返回第i个结点的data域值

)

template<classT>

TLinList<T>::GetData(inti)〃取数据元素

〃取第i个数据元素并返回。参数i的取值范围为：OWiWsize-1

if(i<0||i>size-1)

(

cout<<"参数i越界出错！"«endl;

exit(O);

)

ListNode<T>*p=Index(i);//p指向第i个结点

returnp->data;

//ExamTest3.cpp

#include<iostream.h>

#include<stdlib.h>

includenLinList.hH

voidmain(void)

{

LinList<int>myList;

Ints[]={10,20,30,40,50,60,70,80,90,100},n=10;

Inttemp;

For(intI=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>

voidInsertSort(DataTypea[],intn)

〃用直接插入法对a[0]-a[n・l]排序

(

inti,j;

DataTypetemp;

for(i=0;i<n-l;i++)

(

temp=a[i+l];

j=i；

while(j>-1&&temp.key<=a[j].key)

(

a[j+l]=a|j];

j-；

)

a[j+l]=temp;

voidShellSort(datatypea[],intn,intd[],intnumOfD)

〃用希尔排序法对记录排序

〃各组内采用直接插入法排序

(

inti,j,k,m,span;

datatypetemp;

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。>-1&&temp.key<=a[j].key)

a[j+span]=a[j];

j=j-span;

)

a[j+span]=temp;

)

)

)

)

voidSelectSort(datatypea[],intn)

/*用直接选择排序法对a⑼排序号

(

inti,j,small;

datatypetemp;

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]=afsmall];

a[small]=temp;

voidBubbleSort(datatypeaf],intn)

〃用冒泡排序法对a⑼-a[n-1]排序

(

intij,flag=l;

datatypetemp;

for(i=1;i<n&&flag==1;i++)

flag=0;

for(j=0;j<n-i;j++)

(

if(a[j].key>a[j+l].key)

{

flag=1;

temp=a[j];

a[j]=a[j+l];

a[j+l]=temp;

)

)

)

)

voidQuickSort(datatypea[],intlow,inthigh)

//用递归方法对对象a[low]--a[high]进行快速排序

(

inti,j;

datatypetemp;

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&&afil.key<temp.key)i++;

if(i<j)

(

a|j]=a[i];

a[i]=temp;

〃对子对象数组进行递归快速排序

if(low<i)QuickSort(a,low,i-1);

if(i<high)QuickSort(a,j+1,high);

)

voidMerge(DataTypea[],intn,DataTypeswap[],intk)

//k为有序子数组的长度，一次二路归并排序后的有序子序列存于数组swap中

(

intm=0,ul,12,i,j,u2;

int11=0;〃第一个有序子数组下界为0

while(ll+k<=n-1)

(

12=11+k;〃计算第二个有序子数组下界

ul=12-l;〃计算第一个有序子数组上界

u2=(12+k-l<=n-l)?12+k-l:n-l;〃计算第二个有序子数组上界

〃两个有序子数组合并

for(i=ll,j=12;i<=ul&&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)

swapfm]=a[i];

m++;

i++;

)

〃子数组1已归并完，将子数组2中剩余的元素存放到数组swap中

while(j<=u2)

(

swapfm]=a[j];

m++;

j++;

)

11=u2+1;

}

〃将原始数组中只够一组的数据元素顺序存放到数组swap中

for(i=11;i<n;i++,m++)swap[m]=a[i];

)

voidMergeSort(DataTypea[],intn)

(

inti