數據結構算法實驗內容與指導

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