算法设计基础实验

班级：

学号：

姓名：

实验一 线性表的应用

一、 实验要求

给定一线性表L=（15,25,05,36,78,85,23），写出顺序存储和链接存储结构下的插入、删除、排序操作的算法及程序。

二、实验代码

#include<iostream.h>

#include<stdlib.h>

typedef int ElemType;

struct List

{

ElemType *list;

int size;

int MaxSize;

};

bool InsertList(List &L,ElemType item,int pos)

{

if(pos<-1||pos>L.size+1)

{

cout<<"pos值无效！"<<endl; return false;

}

int i;

if(pos==0)

{

for(i=0;i<L.size;i++)

if(item<L.list[i]) break;

pos=i+1;

}

else if(pos==-1) pos=L.size+1;

if(L.size==L.MaxSize)

{ int k=sizeof(ElemType);

L.list=(ElemType*)realloc(L.list,2*L.MaxSize*k);

if(L.list==NULL)

{

cout<<"动态可分配存储空间用完，退出运行！"<<endl;

exit(1);

}

L.MaxSize=2*L.MaxSize;

}

for(i=L.size-1;i>=pos-1;i--)

L.list[i+1]=L.list[i];

L.list[pos-1]=item;

L.size++;

return true;

}

void SortList(List &L)

{

int i,j;

ElemType x;

for(i=1;i<L.size;i++)

{

x=L.list[i];

for(j=i-1;j>=0;j--)

if(x<L.list[j]) L.list[j+1]=L.list[j]; else break;

L.list[j+1]=x;

}

}

int LenthList(List &L)

{

return L.size;

}

void InitList(List &L)

{

L.MaxSize=10;

L.list=new ElemType[L.MaxSize];

if(L.list==NULL){

cout<<"动态可分配的储存空间用完，退出运行！"<<endl; exit(1);

}

L.size=0;

}

bool DeleteList(List &L,ElemType &item,int pos)

{

if(L.size==0)

{

cout<<"EMPETY LIST"<<endl;

return false;

}

if(pos<-1||pos>L.size)

{

cout<<"INCORRECT NUM"<<endl;

return false;

}

int i;

if(pos==0)

{

for(i=0;i<L.size;i++)

if(item==L.list[i]) break;

if(i==L.size) return false;

pos=i+1;

}

else if(pos==-1) pos=L.size;

item=L.list[pos-1];

for(i=pos;i<L.size;i++)

L.list[i-1]=L.list[i];

L.size--;

if(float(L.size)/L.MaxSize<0.4&&L.MaxSize>10) {

int k=sizeof(ElemType);

L.list=(ElemType*)realloc(L.list,L.MaxSize*k/2); L.MaxSize=L.MaxSize/2;

}

return true;

}

ElemType GetList(List &L,int pos)

{

if(pos<1||pos>L.size)

{

cerr<<"pos is out range!"<<endl;

exit(1);

}

return L.list[pos-1];

}

void ClearList(List &L)

{

if(L.list!=NULL)

{

delete []L.list;

L.list=NULL;

}

L.MaxSize=0;

L.size=0;

}

void TraverseList(List &L)

{

for(int i=0;i<L.size;i++)

cout<<L.list[i]<<' ';

cout<<endl;

}

bool EmptyList(List &L)

{

return L.size==0;

}

void main()

{

int a[7]={15,25,05,36,78,85,23};

int i;ElemType x;

List t;

InitList(t);

for(i=0;i<7;i++) InsertList(t,a[i],i+1); InsertList(t,25,3);InsertList(t,0,0);

cout<<GetList(t,4)<<' '<<GetList(t,5)<<endl; TraversetList(t);

cout<<"输入待删除的元素的值："; cin>>x;

if(DeleteList(t,x,0)) cout<<"删除成功！"<<endl; else cout<<"删除失败！"<<endl;

for(i=0;i<4;i++)

DeleteList(t,x,i+1);

TraversetList(t);

SortList(t);

cout<<"进行排序："<<endl;

TraversetList(t);

cout<<"按值插入，输入带插入元素的值："; cin>>x;

if(InsertList(t,x,0)) cout<<"插入成功！"<<endl; else cout<<"插入失败！"<<endl;

TraversetList(t);

cout<<"线性表长度："<<LenthList(t)<<endl;

if(EmptyList(t)) cout<<"线性表为空！"<<endl;

else cout<<"线性表不为空！"<<endl;

ClearList;

}

三、 实验结果

四、实验感悟

这次试验从某种程度上提高了我的编程能力，同时代码的书写也是要特别的认真细心，不然就需要很繁杂的调试工作。并且也从中学习到，顺序存储结构下的线性表的存储空间不便于扩充，线性表的顺序存储结构对存储空间不便于动态分配。

实验二 二叉树的遍历

一、 实验要求

给定一二叉树T，写出其前序遍历、中序遍历、后序遍历的算法及程序。

二、 实验目的

动手编写代码，并调试，完成实验要求

三、 实验代码及调试

#include<iostream.h>

#include<stdlib.h>

typedef char ElemType;

struct BTreeNode

{

};

void PreOrder(BTreeNode* BT)

{

}

if(BT!=NULL) { } cout<<BT->data<<' '; PreOrder(BT->left); PreOrder(BT->right); ElemType data; BTreeNode*left; BTreeNode*right;

void InOrder(BTreeNode *BT)

{

}

void PostOrder(BTreeNode *BT) {

}

void PrintBTree(BTreeNode*BT) {

}

void CreatBTree(BTreeNode*& BT,char*a) {

const int MaxSize=10; BTreeNode*s[MaxSize]; int top=-1; BT=NULL; if(BT!=NULL) { } cout<<BT->data; if(BT->left!=NULL||BT->right!=NULL) { } cout<<'('; PrintBTree(BT->left); if(BT->right!=NULL) cout<<','; PrintBTree(BT->right); cout<<')'; if(BT!=NULL) { } PostOrder(BT->left); PostOrder(BT->right); cout<<BT->data<<' '; if(BT!=NULL) { } InOrder(BT->left); cout<<BT->data<<' '; InOrder(BT->right);

}

BTreeNode *p; int k; int i=0; while(a[i]) { } switch (a[i]){ case ' ': case '(': if(top==MaxSize-1){ } cout<<"栈空间太小，请增加MaxSize的值!"<<endl; exit(1); break; top++;s[top]=p;k=1; break; case ')': } if(top==-1) { } top--;break; k=2;break; p=new BTreeNode; p->data=a[i];p->left=p->right=NULL; if(BT==NULL) BT=p; else{ if(k==1) s[top]->left=p; else s[top]->right=p; } cout<<"二叉树广义表字符串错！"<<endl;exit(1); case ',': default: i++;

void InitBTree(BTreeNode*& BT) {

} BT=NULL;

void main()

{

} BTreeNode* bt; InitBTree(bt); char b[50]; cout<<"输入二叉树用广义表表示的字符串："<<endl; cin.getline(b,sizeof(b)); CreatBTree(bt,b); PrintBTree(bt); cout<<endl; cout<<"前序:";PreOrder(bt); cout<<endl; cout<<"中序:";InOrder(bt); cout<<endl; cout<<"后序:";PostOrder(bt); cout<<endl;

四、 实验结果

五、 实验感悟

通过学习数据结构，发现数据结构包括线性结构、树形结构、图状结构或网状结构。线性结构包括线性表、栈、队列、串、数组、广义表等，栈和队列是操作受限的线性表，串的数据对象约束为字符集，数组和广义表是对线性表的扩展：表中的数据元素本身也是一个数据结构。除了线性表以外，栈是重点，因为栈和递归紧密相连，递归是程序设计中很重要的一种工具。树状结构中的重点自然是二叉树和哈弗曼树了。

学习算法的目的是利用算法解决实际问题。会写课本上已有的算

法之后，可以借其思想进行扩展，逐步提高编程能力。比如数值转换，括号匹配的检验，检验平衡二叉树等。

实验三 拓扑排序

一、 实验要求

请按照书中介绍的拓扑排序算法，完成P303页第5题（一二本学生做此实验内容）。或者完成图的深度优先搜索遍历和广度优先搜索遍历。

二、实验目的

通过拓扑排序代码的编写，完成图的深度优先搜索遍历和广度优先搜索遍历。

三、 实验代码

#include<iostream.h>

#include<stdlib.h>

#include<strstrea.h>

const int MaxVertexNum=20;

typedef int WeightType;

struct edgenode

{

int adjvex;

WeightType weight;

edgenode *next;

};

typedef edgenode *adjlist[MaxVertexNum];

void Toposport(adjlist GL,int n);

void InitAdjoin(adjlist GL)

{

} for(int i=0;i<MaxVertexNum;i++) GL[i]=NULL;

void CreatAdjoin(adjlist GL,int n,char *s,int k1,int k2) {

}

else{

do{ } sin>>c1>>i>>c2>>j>>c3>>w; p=new edgenode; p->adjvex=j;p->weight=w; p->next=GL[i]; GL[i]=p; if(k1==0) { p=new edgenode; p->adjvex=i;p->weight=w; istrstream sin(s); char c1,c2,c3; int i,j; WeightType w; edgenode *p; sin>>c1; if(k2==0) { do{ if(k1==0){ p=new edgenode; p->adjvex=j;p->weight=1; p->next=GL[j]; GL[i]=p; } sin>>c1>>i>>c2>>j>>c3; p=new edgenode; p->adjvex=j;p->weight=1; p->next=GL[j]; GL[i]=p; sin>>c1; }while(c1==','); p->next=GL[j]; } sin>>c1; GL[j]=p;

}

}

while(c1==',');

void main()

{

}

void Toposport(adjlist GL, int n) {

int i,j,k,top,m=0; edgenode*p; int*d=new int[n]; for(i=0;i<n;n++) d[i]=0; for(i=0;i<n;n++) { } top=-1; for(i=0;i<n;i++) if(d[i]==0) { d[i]=top; top=i;} while(top!=-1) { j=top; top=d[top]; cout<<j<<' '; m++; p=GL[i]; while(p!=NULL) { } j=p->adjvex; d[j]++; p=p->next; int n,k1,k2; cin>>n; cout<<"输入图的有无向和有无权的选择（0为无，非零为有）："; cin>>k1>>k2; adjlist g1; InitAdjoin(g1); cout<<"输入图的边集"; char *a=new char[100]; cin>>a; CreatAdjoin(g1,n,a,k1,k2); //Cripath(g1,n); cout<<"输入待处理的顶点数："; Toposport(g1,n);

} } p=GL[j]; while(p!=NULL) { k=p->adjvex; d[k]--; if(d[k]==0) } { d[k]=top;top=k; } p=p->next; cout<<endl; if(m<n) cout<<"The netwok has a cycle!"<<endl; delete []d;

四、 实验结果显示

五、 实验感悟

通过本次试验，了解了关于拓扑排序的方法和步骤：

（1）在图中选一个没有前趋的顶点并输出之

（2）删除该顶点及由它发出的各边，直到图中不存在没有前趋的顶点为止。 若图中存在回路，拓扑排序无法进行。

网采用邻接矩阵A表示,若a[i，j]=1，表示活动i先于j，a[i，j]=0，表示活动i与j不存在先后关系。

（1）计算各顶点的入度 ；

（2）找入度为零的点输出之，删除该点，且与该点关联各点的

入度减1 ；

（3）若所有顶点都输出完毕。

实验四 排序

一、 实验要求

熟练掌握图的直接插入排序、简单选择排序、堆排序、快速排序、气泡排序。

二、实验目的

通过读写排序的算法程序，熟练编写代码的思想，并掌握排序的原理。

三、 实验代码及调试

#include<iostream.h>

#include<stdlib.h>

#define ElemType int

#define LEN 10

//#define RANDOM_MAX 65536

void InsertSort(ElemType A[],int n)

{

}

}

void SelectSort(ElemType A[],int n)

{

ElemType x; int i,j,k; for(i=1;i<=n-1;i++) ElemType x; int i,j; for(i=1;i<n;i++){ x=A[i]; for(j=i-1;j>=0;j--) if(x<A[j]) A[j+1]=A[j]; else break; A[j+1]=x;

} { } k=i-1; for(j=i;j<=n-1;j++) { } if(k!=i-1) { } x=A[i-1];A[i-1]=A[k];A[k]=x; if(A[j]<A[k]) k=j;

void Sift(ElemType A[],int n,int i) {

}

void HeapSort(ElemType A[],int n) {

}

void BubbleSort(ElemType A[],int n) {

ElemType x; ElemType x; int i; for(i=n/2-1;i>=0;i--) Sift(A,n,i); for(i=1;i<=n-1;i++) { } x=A[0];A[0]=A[n-i];A[n-i]=x; Sift(A,n-i,0); ElemType x=A[i]; int j; j=2*i+1; while(j<=n-1) { } A[i]=x; if(j<n-1&&A[j]<A[j+1]) j++; if(x<A[j]) { } else break; A[i]=A[j];i=j;j=2*i+1;

}

int i,j,flag; for(i=1;i<n-1;i++) { } flag=0; for(j=n-1;j>=i;j--) { } if(flag==0) return; if(A[j]<A[j-1]) { } x=A[j-1];A[j-1]=A[j];A[j]=x; flag=1;

void QuickSort(ElemType A[],int s,int t) {

}

void create_source(int a[])

{

int i; for(i=0;i<LEN;i++) { float temp=(rand()/(3000+1))*10; a[i]=temp; int i=s+1,j=t; ElemType x=A[s]; while(i<=j) { } if(s!=j) {A[s]=A[j];A[j]=x;} if(s<j-1) QuickSort(A,s,j-1); if(j+1<t) QuickSort(A,j+1,t); while(A[i]<=x&&i<=j) while(A[j]>=x&&j>=i) if(i<j) { } ElemType temp=A[i]; A[i]=A[j]; A[j]=temp; i++;j--; i++; j--;

}

} //a[i]=rand();

void show(int a[]) {

}

void main() {

int a[LEN]; create_source(a); cout<<"新建数组："<<endl; show(a); cout<<"冒泡排序："<<endl; BubbleSort(a,LEN); show(a); create_source(a); cout<<"新建数组："<<endl; show(a); cout<<"堆排序："<<endl; HeapSort(a,LEN); show(a); create_source(a); cout<<"新建数组："<<endl; show(a); cout<<"快速排序："<<endl; QuickSort(a,0,LEN); show(a); create_source(a); cout<<"新建数组："<<endl; show(a); cout<<"插入排序："<<endl; InsertSort(a,LEN); show(a); create_source(a); cout<<"新建数组："<<endl; show(a); int i; for(i=0;i<LEN;i++) { } cout<<endl; cout<<a[i]<<' ';

}

cout<<"选择排序："<<endl; SelectSort(a,LEN); show(a);

四、 实验结果

五、 实验感悟

通过本次实验，了解了各种算法的计算复杂度以及计算原理，本实验课本上只有算法的程序，没有相应的主函数，和随机生成一列数字的函数题，所以需要自己独立的编写程序代码，这不仅能够锻炼个人的编程能力，也需要查阅相应的资料。发现问题和解决问题的能力。总的来说这次实验带给我的影响相对来说较大。