数据结构上机指导

数据结构》上机实验的目的和要求通过上机实验加深对课程内容的理解，增加感性认识，提高软件设计、编写及调试程序的能力。要求所编的程序能正确运行，并提交实验报告。实验报告的基本要求为：1、 需求分析：陈述程序设计的任务，强调程序要做什么，明确规定：（1） 输入的形式和输出值的范围；（2） 输出的形式；（3） 程序所能达到的功能；（4） 测试数据：包括正确的输入输出结果和错误的输入及输出结果。2、 概要设计：说明用到的数据结构定义、主程序的流程及各程序模块之间的调用关系。3、 详细设计：提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。4、 调试分析：（1） 调试过程中所遇到的问题及解决方法；（2） 算法的时空分析；（3） 经验与体会。5、 用户使用说明：说明如何使用你的程序，详细列出每一步操作步骤。6、 测试结果：列出对于给定的输入所产生的输出结果。若有可能，测试随输入规模的增长所用算法的实际运行时间的变化。实验一C卄程序设计基础一、目的：回顾C++程序设计的基本知识，掌握算法时间复杂性和空间复杂性分析。二、要求：掌握指针和函数调用的基本用法，为后续课程内容做准备。三、示例程序：#include<iostream>#include<cmath>usingnamespacestd;voidmain（）{inta[2][2]={1,2,3,4};intb[2][2]={2,1,4,5};intc[2][2]={0,0,0,0};inti,j,k;for（i=0;i<2;++i）for(j=0;j<2;++j)for(k=0;k<2;++k)c[i][j]+=a[i][k]*b[k][j];for(i=0;i<2;++i)for(j=0;j<2;++j)cout<<c[i][j]<<endl;}实验二线性表、链表程序设计一、目的：掌握线性、链表的基本算法及相关的时间性能分析。二、要求：建立线性表、链表，并对其进行插入、删除、查找以及销毁等基本操作。三、示例程序：#include<iostream.h>#include<stdlib.h>#include<conio.h>//consoleandportI/Odeclarations#definetrue1#definefalse0#defineok1#defineerror0#defineinfeasible-1#defineoverflow-2typedefintstatus;#defineListInitSize100//线性表存储空间的初始分配量#defineListSizeIncrement10//线性表存储空间的分配增量typedefcharElemType;usingnamespacestd;typedefstruct{ElemType*elem; //线性表存储空间基址intlength; //当前线性表长度intlistsize; 〃当前分配的线性表存储空间大小，(以sizeof(ElemType)为单位)intincrementsize;}Sqlist;//SqList：类型名statusInitList(Sqlist&L){L.elem=newElemType[ListInitSize];L.length=0;L.listsize=ListInitSize;L.incrementsize=ListSizeIncrement;returnok;}//销毁线性表LvoidDestroyList(Sqlist&L){if(L.elem)free(L.elem);//释放线性表占据的所有存储空间}〃清空线性表L,将线性表L重置为空表voidClearList(Sqlist&L){L.length=0; //将线性表的长度置为0}〃求线性表L的长度，返回L中元素的个数statusGetLength(Sqlist&L){return(L.length);}〃判断线性表L是否为空statusIsEmpty(Sqlist&L){if(L.length==0)returntrue;elsereturnfalse;}〃获取线性表L中的某个数据元素的内容statusGetElem(SqlistL,inti,ElemTypee){if(i<1||i>L.length)returnerror;〃判断i值是否合理，若不合理，返回errore=L.elem[i-l];〃数组中第i-1的单元存储着线性表中第i个数据元素的内容returnok;}〃获取线性表L中的某个数据元素的位序statusLocateElem(SqlistL,ElemTypee){inti;i=l;while(i<=L.length&&e!=L.elem[i-l])i++;if(i<=L.length)returni;elsereturn0;}〃在线性表中第i元素前插入新的元素e,L的长度增1statusInsertList(Sqlist&L,inti,ElemType&e){ElemType*newbase;//声明一个指向字符值的指针intj;if(i<1&&i>L.length+1)returnerror;if(L.length>=L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+ListSizeIncrement)*sizeof(ElemType));if(!newbase)return(overflow);L.elem=newbase;L.listsize+=ListSizeIncrement;}for(j=L.length;j>=i;j--)L.elem[j]=L.elem[j-1];L.elem[j-1]=e;++L.length;returnok;}voidInsert(Sqlist&L,constElemType&item){if(L.listsize==ListInitSize){cerr<<"Sqlistoverflow!"<<endl;exit(1);}for(inti=0;i<L.listsize;i++)if(item<L.elem[i])break;for(intj=L.listsize-1;j>i;j--)L.elem[j+1]=L.elem[j];L.elem[i]=item;L.length++;}〃删除L中的第i个元素，并用e返回其值，L的长度减1statusDeleteList(Sqlist&L,inti,ElemType&e){intj;if(i<1&&i>L.length||L.length<1)returnerror;e=L.elem[i-1];for(j=i;i<L.length;j++)L.elem[j-1]=L.elem[j];--L.length;returnok;}voidPrintList(Sqlist&L){ElemType*p;//声明一个指向字符值的指针inti=1;p=L.elem;while(i<=L.length){cout<<*(p+i-1)<<"";if(i%5==0)cout<<endl;i++;}cout<<endl;}voidmain(){ElemTypech;intnumber=1;inti;Sqlistla;InitList(la);cout<<"Createla,pleaseinputdata(0isover)\n";while(ch!='0'){InsertList(la,number++,ch);Insert(la,ch);cin>>ch;}for(i=1;i<5;i++)cout<<la.elem<<endl;PrintList(la);实验三队列、栈程序设计一、目的：掌握队列以及栈的基本算法及相关的时间性能分析。二、要求：建立队列以及栈，并对其进行插入、删除、查找以及销毁等基本操作三、示例程序：#include<iostream>#include<cmath>usingnamespacestd;#defineStackSize10#defineok1#defineerror0#defineElemTypeint//定义栈结构typedefstruct{ElemTypedata[StackSize];inttop;}SeqStack;//1、初始化栈voidinitstack(SeqStack&s){s.top=0;}//2、判断栈空intstackempty(SeqStack&s){return(s.top==0);}//3、判断栈满intstackfull(SeqStack&s){return(s.top==StackSize);}//4、进栈intpush(SeqStack&s,ElemTypex){if(stackfull(s))returnerror;//<<"stackoverflow";*/s.data[s.top++]=x;returnok;}//5、退栈intpop(SeqStack&s,ElemTypex){if(stackempty(s))returnerror;cout<<"stackunderflow";s.top--;x=s.data[s.top];cout<<x<<endl;returnok;}//6、取栈顶元素intstacktop(SeqStack&s){if(stackempty(s))returnerror;returns.data[s.top-1];}voidmain(){intn,x,w;SeqStacks;initstack(s);cout<<s.top<<endl;cin>>n;while(n){w=n%8;push(s,w);n=n/8;}while(!stackempty(s)){pop(s,x);x=s.data[s.top];cout<<w<<endl;cout<<x<<endl;}for(inti=3;i<0;i++)cout<<s.data[0]<<s.data[1]<<endl;实验四二叉树程序设计一、目的：掌握二叉树的基本算法及相关的时间性能分析。二、要求：建立二叉树，并对其进行先序、中序和后序等基本操作。三、示例程序：#include<iostream>#include<stdio.h>#include<stdlib.h>#include<new>#defineERROR0#defineOK1usingnamespacestd;typedefcharTElemType;typedefstructBinNode{TElemTypedata;structBinNode*lchild,*rchild;}BinNode,*BiTree;intpnt(TElemTypee){cout<<e<<endl;returnOK;}intCreateBiTree(BiTree&T){charch;cin>>ch;if(ch=='#')T=NULL;else{T=newBinNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);returnOK;}intPreOrderTraverse(BiTreeT,int(*Visit)(TElemTypee)){if(T){if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}intInOrderTraverse(BiTreeT,int(*Visit)(TElemTypee)){if(T){if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}intPostOrderTraverse(BiTreeT,int(*Visit)(TElemTypee)){if(T){ifPostOrderTraverse(T->lchild,Visit))ifPostOrderTraverse(T->rchild,Visit)()if((Visit(T->data))returnOK;returnERROR;}elsereturnOK;}voidmain(){BiTreeT;CreateBiTree(T);PreOrderTraverse(T,pnt);InOrderTraverse(T,pnt);PostOrderTraverse(T,pnt);四、实验内容1、 分析、理解程序。2、 调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求所有叶子及结点总数。五、实验报告要求1、 基本要求见第一页。2、 画出所设计的二叉树，以后序遍历算法为例，画出执行踪迹示意图。3、 给出实验结果。实验五拓扑排序算法一、目的：掌握拓扑排序的基本算法及相关的时间性能分析。二、 要求：建立邻接表，并对其进行拓扑排序分析。三、 示例程序：#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>#include<stack>usingnamespacestd;#defineMAX9999stack<int>mystack;intindegree[MAX];structnode{intadjvex;node*next;}adj[MAX];intCreate(nodeadj[],intn,intm)〃邻接表建表函数，n代表定点数，m代表边数{inti;node*p;for(i=1;i<=n;i++){adj[i].adjvex=i;adj[i].next=NULL;}for(i=1;i<=m;i++)coutvv"请输入第"vvivv"条边:";intu,v;cin>>u>>v;p=newnode;p->adjvex=v;p->next=adj[u].next;adj[u].next=p;}return1;}voidprint(intn)〃邻接表打印函数{inti;node*p;for(i=1;i<=n;i++){p=&adj[i];while(p!=NULL){cout<<p->adjvex<<'';p=p->next;}cout<<endl;}}voidtopsort(nodeadj[],intn){inti;node*p;memset(indegree,0,sizeof(indegree));for(i=1;i<=n;i++){p=adj[i].next;while(p!=NULL){indegree[p->adjvex]++;p=p->next;for(i=1;i<=n;i++){if(indegree[i]==0)mystack.push(i);}intcount=0;while(mystack.size()!=0){i=mystack.top();mystack.pop();cout<<i<<'';count++;for(p=adj[i].next;p!=NULL;p=p->next){intk=p->adjvex;indegree[k]--;if(indegree[k]==0)mystack.push(k);}}cout<<endl;if(countvn)coutvv"有回路"vvendl;}intmain(){intn;intm;coutvv"请输入顶点数及边数:"；cin>>n>>m;Create(adj,n,m);coutvv"输入的邻接表为:"vvendl;print(n);coutvv"拓扑排序结果为:"vvendl;topsort(adj,n);system("pause");return0;}四、实验内容1、 分析、理解程序。2、 调试程序，设计一邻接表，打印出拓扑排序的结果五、实验报告要求1、 基本要求见第一页。2、 画出所设计邻接表，画出拓扑排序执行踪迹示意图。3、 给出实验结果。实验六排序算法设计一、目的：掌握各种排序方法的基本思想、排序过程、算法实现，能进行时间和空间性能的分析，根据实际问题的特点和要求选择合适的排序方法。二、要求：实现直接排序、冒泡、直接选择、快速、堆、归并排序算法。比较各种算法的运行速度。三、示例程序：#include"iostream"usingnamespacestd;voidSelectSort(int*pData,intCount){intiTemp;intiPos;for(inti=0;i<Count-1;i++){iTemp=pData[i];iPos=i;for(intj=i+1;j<Count;j++){if(pData[j]<iTemp){iTemp=pData[j];iPos=j;}}pData[iPos]=pData[i];pData[i]=iTemp;}}voidmain(){intdata[]={10,9,8,7,6,5,4};SelectSort(data,7);for(inti=0;i<7;i++)cout<<data[i]<<"";cout<<"\n";}#include"iostream"usingnamespacestd;voidInsertSort(int*pData,intCount){intiTemp;intiPos;for(inti=1;i<Count;i++){iTemp=pData[i];iPos=i-1;while((iPos>=0)&&(iTemp<pData[iPos])){pData[iPos+1]=pData[iPos];iPos--;}pData[iPos+1]=iTemp;}}voidmain(){intdata[]={10,9,8,7,6,5,4};InsertSort(data,7);for(inti=0;i<7;i++)cout<<data[i]<<"";cout<<"\n";}#include"iostream"usingnamespacestd;template<classT>classdoit{private:intx,y;Ttemp;public:doit(T*in,intcount){for(y=0;y<count-1;y++){for(x=1;x<count-y;x++)if((*