数据结构上机实验源代码.doc

数据结构上机实验源代码栈的应用十进制数转换为八进制数，逆序输出所输入的数实验代码：/stack.h，头文件class stackpublic:stack(); bool empty()const; bool full()const; error_code gettop(elementtype &x)const; error_code push(const elementtype x); error_code pop();private:int count;elementtype datamaxlen;stack:stack()count=0;bool stack:empty()constreturn count=0;bool stack:full()constreturn count=maxlen;error_code stack:gettop(elementtype &x)constif(empty()return underflow;elsex=datacount-1;return success;error_code stack:push(const elementtype x)if(full()return overflow;datacount=x;count+;return success;error_code stack:pop()if(empty()return underflow;count-;return success;/主程序#includeenum error_codeoverflow,underflow,success;typedef int elementtype;const int maxlen=20;#includestack.hvoid read_write() /逆序输出所输入的数stack s;int i;int n,x;coutn;for(i=1;i=n;i+)coutx;s.push(x);while(!s.empty()s.gettop(x);coutx ;s.pop();coutendl;void Dec_to_Ocx(int n) /十进制转换为八进制stack s1;int mod,x;while(n!=0)mod=n%8;s1.push(mod);n=n/8;coutthe ocx of the dec is:;while(!s1.empty()s1.gettop(x);coutx;s1.pop();coutendl;void main()int n;/read_write();coutn;Dec_to_Ocx(n);队列的应用打印n行杨辉三角实验代码：/queue.hclass queuepublic:queue() count=0; front=rear=0; bool empty() return count=0; bool full() return count=maxlen-1; error_code get_front(elementtype &x) if(empty()return underflow; x=data(front+1)%maxlen; return success; error_code append(const elementtype x) if(full()return overflow; rear=(rear+1)%maxlen; datarear=x; count+; return success; error_code serve() if(empty()return underflow; front=(front+1)%maxlen; count-; return success; private:int count;int front;int rear;int datamaxlen;/主程序#includeenum error_codeoverflow,underflow,success;typedef int elementtype;const int maxlen=20;#includequeue.hvoid out_number(int n) /打印前n行的杨辉三角int s1,s2;int i;int j;int k;queue q;for(i=1;i=(n-1)*2;i+)cout ;cout1 endl;q.append(1);for(i=2;i=n;i+)s1=0;for(k=1;k=(n-i)*2;k+)cout ;for(j=1;j=i-1;j+)q.get_front(s2);q.serve();couts1+s2 ;q.append(s1+s2);s1=s2;cout1 endl;q.append(1);void main()int n;coutn;out_number(n);单链表实验实验目的: 实验目的（1）理解线性表的链式存储结构。（2）熟练掌握动态链表结构及有关算法的设计。（3）根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。实验任务说明1：本次实验中的链表结构均为带头结点的单链表。说明2：为使实验程序简洁直观，下面的部分实验程序中将所需要的函数以调用库函数的形式给出，并假设将库函数放在程序文件“linklist.h”中，同时假设该库函数文件中定义了链表结构中的指针类型为link，结点类型为node，并定义了部分常用运算。 例如构建链表、以某种方式显示链表、从文件中读入一个链表、跟踪访问链表结点等。 各运算的名称较为直观，并有相应的注释，因而易于理解和实现。 读者在上机实验时，需要自己设计出所涉及到的库函数，或者将函数放在实验程序中，以方便实验程序的调试。如时间紧的话，也可到作者的网站下载以供参考（不完全相同）。编写算法实现下列问题的求解。求链表中第i个结点的指针（函数），若不存在，则返回NULL。实验测试数据基本要求：第一组数据：链表长度n10，i分别为5，n，0，n+1，n+2第二组数据：链表长度n=0，i分别为0，2在第i个结点前插入值为x的结点。实验测试数据基本要求：第一组数据：链表长度n10，x=100, i分别为5,n,n+1,0,1,n+2第二组数据：链表长度n=0，x=100，i=5删除链表中第i个元素结点。实验测试数据基本要求：第一组数据：链表长度n10，i分别为5,n,1,n+1,0 第二组数据：链表长度n=0， i=5在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。实验测试数据基本要求：链表元素为 （10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8将单链表中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。实验测试数据基本要求：第一组数据：链表元素为 （1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）第二组数据：链表元素为 （10,20,30,40,50,60,70,80,90,100）求两个递增有序链表L1和L2中的公共元素，并以同样方式连接成链表L3。实验测试数据基本要求： 第一组第一个链表元素为 （1，3，6，10，15，16，17，18，19，20）第二个链表元素为 （1，2，3，4，5，6，7，8，9，10，18，20，30）第二组第一个链表元素为 （1，3，6，10，15，16，17，18，19，20）第二个链表元素为 （2，4，5，7，8，9，12，22）第三组第一个链表元素为 （）第二个链表元素为 （1，2，3，4，5，6，7，8，9，10）实验代码:/linklist.henum error_codearrange_error,null,success;typedef struct nodeelementtype data; struct node *next;node;class listprivate:node *head;int count;public:list() /链表的初始化 head=new node; head-next=NULL; count=0; int length() /求链表的长度 return count; /*取链表中第i个节点的指针*/ node * locate(const int i) node *p=head; int j=0; if(ilength()return NULL; while(p!=NULL) if(j=i)return p; p=p-next; j+;return NULL; /*在第i节点之前插入数为x的节点*/ error_code insert(const int i,const elementtype x) node *p=head; int j=0; while(j!=i-1&p!=NULL) p=p-next; j+; if(icount+1)cout该位置前不能插入元素data=x; s-next=p-next; p-next=s; count+; cout插入成功！next; j+; if(ilength()cout此元素不存在next; p-next=u-next; count-; delete u; cout删除成功next; if(head-next-datax)node *u=new node; u-data=x; u-next=head-next; head-next=u; return success; while(p-next!=NULL) if(p-next-datax)node *u=new node; u-data=x; u-next=p-next; p-next=u; return success; p=p-next; node *u=new node; u-data=x; u-next=NULL; p-next=u; return success; /取链表头结点的地址node *gethead()return head;/输出链表中的所有元素error_code print()node *p=head-next;while(p!=NULL)coutdatanext;coutnext;while(p!=NULL)if(p-data)%2=1)node *u=new node;u-data=p-data;pa-next=u;pa=u;pa-next=NULL;if(p-data)%2=0)node *u=new node;u-data=p-data;pb-next=u;pb=u;pb-next=NULL;p=p-next;cout链表所有的奇数项为：endl;a.print();cout链表所有的偶数项为：next;pb=b.gethead()-next;rc=c.gethead();while(pa!=NULL&pb!=NULL)if(pa-datadata)pa=pa-next;else if(pa-datapb-data)pb=pb-next;elseu=new node;u-data=pa-data;rc-next=u;rc=u;c.count+;pa=pa-next;pb=pb-next;rc-next=NULL;cout两链表中的公共元素为：endl;c.print();/ 主程序#includetypedef int elementtype;#includelinklist.hvoid main()list a;list b;list c;int m;int n;int j;int i;int choice;elementtype temp;docout0，实验结束endl;cout1，实验要求1endl;cout2，实验要求2endl;cout3，实验要求3endl;cout4，实验要求4endl;cout5，实验要求5endl;cout6，实验要去6endl;cout请选择所要做的实验choice;switch(choice)case 0:cout实验结束endl;break;case 1:/*实验要求1cout请输入a链表的长度：m;for(j=1;j=m;j+)cout请输入元素的值temp;a.insert(j,temp);cout请输入i的值i;if(a.locate(i)!=NULL)cout链表第i个元素的值为：dataendl;else coutNULLendl;cout请输入i的值i;if(a.locate(i)!=NULL)cout链表第i个元素的值为：dataendl;else cout链表第i个元素的值为：NULLendl;cout请输入n的值n;for(j=0;j3;j+)if(a.locate(n+j)!=NULL)cout链表第n+j个元素的值为：dataendl;else cout链表第n+j个元素的值为：NULLendl;break;case 2:/*实验要求2cout请输入a链表的长度：m;for(j=1;j=m;j+)cout请输入元素的值temp;a.insert(j,temp);cout请输入x的值：temp;for(j=1;j=3;j+)cout请输入插入点的位置：i;a.insert(i,temp);cout请输入n的值：n;for(j=0;j3;j+)a.insert(n+j,temp);break;case 3:/*实验要求3cout请输入a链表的长度：m;for(j=1;j=m;j+)cout请输入元素的值temp;a.insert(j,temp);int n1;cout请输入要删除的元素的位置i;a.delete_element(i);cout请输入n的值n;a.delete_element(n);n1=n+1;cout请输入要删除的元素的位置i;a.delete_element(i);cout删除n+1位置的元素endl;a.delete_element(n1);cout请输入要删除的元素的位置i;a.delete_element(i);break;case 4:/*实验要求4cout请输入a链表的长度：m;for(j=1;j=m;j+)cout请输入元素的值temp;a.insert(j,temp);cout链表未插入前的，其中的只有：endl;a.print();for(j=1;j=4;j+)cout请输入要插入的元素x的值：temp;a.insert1(temp);cout插入后链表中的值为：endl;a.print();break;case 5:/*实验要求5cout请输入a链表的长度：m;for(j=1;j=m;j+)cout请输入元素的值temp;a.insert(j,temp);a.depart();break;case 6:/*实验要求6cout请输入a链表的长度：m;for(j=1;j=m;j+)cout请输入元素的值temp;a.insert(j,temp);cout请输入链表的长度：m;for(j=1;j=m;j+)cout请输入元素的值temp;b.insert(j,temp);erset(b,c);cout链表中的元素有：endl;b.print();cout链表中的元素有：endl;a.print();break;default:cout请选择正确的实验要求next=Head;Head-prior=Head;count=0;DLinkList:DLinkList()/析构函数，释放链表所占空间Node *p,*q;while(q-next!=Head) q=q-next; /定位q到尾结点？while(Head!=Head-next)/从头结点开始，依次释放结点p=Head;Head=Head-next;q-next=Head;Head-prior=q; delete p;count-;Head=NULL;/头结点指向空void DLinkList:CreateList(int n)/尾插法(正序)创建具有n个元素的双循环链表Node *p,*s;/设置工作指针。p指向尾结点p=Head;cout请依次输入n个元素值：endl;for(int i=1;is-data;/输入新建数据元素值s-next=p-next;/新结点链入表尾p-next=s;s-prior=p;Head-prior=s;p=s;count+;void DLinkList:ListDisplay()/显示链表Node *p;p=Head-next;int i=1;while(p!=Head)coutit;coutdatanext;i+;void DLinkList:symmetry()Node *p,*s;int i;p=Head-next;s=Head-prior;for(i=1;idata!=s-data)cout链表不对称next;s=s-prior;if(i=count/2+1)cout链表对称endl;/主程序#include/cout,cintypedef int T;#include dLinklist.hvoid main() /主函数int i;DLinkList L;/int choice; do/显示主菜单cout1-创建双循环链表n;cout2-判断链表是否对称n;cout3-显示链表n;cout4-退出n;coutchoice;switch(choice)case 1:/创建链表couti;/将创建的链表中数据元素的个数coutendl;L.CreateList(i);break;case 2:/判断链表是否为空L.symmetry();break;case 3:/显示表L.ListDisplay();coutendl;break;case 4:/退出cout结束运行endl;break;default:/coutInvalid choicen;break;while(choice!=4);/结束二叉树的试验试验要求:二叉树的构建,二叉树的前序,中序,后序遍历算法,查找替换树中的节点,交换一棵树的左右子树试验代码:#includeenum error_codesuccess;typedef char elementtype;typedef struct bnode elementtype data; struct bnode *lchild,*rchild;bnode, *bitree;class bitreprivate:bnode *root;void create(bitree &T);int high(bnode *T);void preorder(bnode *T);/先序遍历void inorder(bnode *T);/中序遍历void postorder(bnode *T);/后序遍历public: bnode * getroot()return root; void create()create(root); int high()return high(root); void preorder()preorder(root);/先序遍历void inorder()inorder(root);/中序遍历void postorder()postorder(root);/后序遍历 void search(bnode *T,char &num,bitree &m);/查找void jhuan(bnode * T,char &num,char &temp);/替换void jbitree(bnode *T,char &num);/交换一个节点的左右子树;void bitre:jbitree(bnode *T,char &num)/交换一个节点的左右子树if(T!=NULL)if(T-data=num)bnode *temp;temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;jbitree(T-lchild,num);jbitree(T-rchild,num);void bitre:jhuan(bnode *T,char &num,char &temp)/替换树中的元素if(T!=NULL)if(T-data=num)T-data=temp;cout交换成功lchild,num,temp);jhuan(T-rchild,num,temp);void bitre:search(bnode *T,char &num,bitree &m) /查找元素并返回该元素的地址 if(T!=NULL) if(T-data=num)m=T; search(T-lchild,num,m); search(T-rchild,num,m); int max(int m,int n) /求最大值return (m=n)?m:n;int bitre:high(bnode *T)if(T=NULL)return 0;else return max(high(T-lchild),high(T-rchild)+1; void bitre:create(bitree &T) /创建一颗二叉树char x; cinx; if ( x= . ) T = NULL; elseT = new bnode; T - data = x; create ( T - lchild ); create ( T - rchild ); void bitre:preorder(bnode *T)if(T!=NULL)coutdata;preorder(T-lchild);preorder(T-rchild);void bitre:inorder(bnode *T)if(T!=NULL)inorder(T-lchild);coutdata;inorder(T-rchild);void bitre:postorder(bnode *T)if(T!=NULL)postorder(T-lchild);postorder(T-rchild);coutdata;void main() char ch; char dh;bitre t;bitree a;cout请按先序序列输入二叉树中元素的值endl;t.create();cout树的先序序列为endl;t.preorder();coutendl; cout树的中序序列为endl;t.inorder();coutendl;cout树的后序序列为endl;t.postorder();coutendl;coutch; t.search(t.getroot(),ch,a);coutdataendl;cout请先后输入待交换的元素与交换的元素ch;cindh;t.jhuan(t.getroot(),ch,dh);cout请输入待交换节点的元素值ch;t.jbitree(t.getroot(),ch);t.preorder();coutendl;图的试验试验要求:图的构建,实现图的深度遍历算法与广度遍历算法,以及图的有关操作试验代码:/*-单链队列-*/linkqueue.h #ifndef LINKNODE#define LINKNODEtemplate struct LinkNodeT data;LinkNode *next;template class LinkedQueueprotected:LinkNode *front;LinkNode *rear;int length;public:LinkedQueue();LinkedQueue();void ClearQueue();bool IsEmpty() const;int GetLength() const;LinkNode* GetHead() const;/返回对头元素bool EnQueue(T &elem);bool DeQueue(T &receive);bool QueueTraverse(bool (*Visit)(T &elem);template LinkedQueue:LinkedQueue()front = new LinkNode;if(!front) return;rear = front;front-next = false;length=0;template LinkedQueue:LinkedQueue() ClearQueue();delete front;template void LinkedQueue:ClearQueue()/从队头清到队尾LinkNode *temp = front-next;while(front-next)front-next = temp-next;delete temp;temp = front-next;rear = front;length=0;template bool LinkedQueue:IsEmpty() constreturn (front=rear)?true:false;template int LinkedQueue:GetLength() constreturn length;template LinkNode* LinkedQueue:GetHead() constreturn front;template bool LinkedQueue:EnQueue(T &elem)LinkNode *temp = new LinkNode;if(!temp) return false;temp-data = elem; temp-next = false;rear-next = temp;rear = temp;+length;return true;template bool LinkedQueue:DeQueue(T &receive)if(front=rear) return false; LinkNode *temp = front-next;/指向队头元素receive = temp-data;front-next = temp-next;delete temp;if(!front-next) rear = front;-length;return true;template bool LinkedQueue:QueueTraverse(bool (*Visit)(T &elem) /从队头到队尾进行一次遍历 LinkNode *temp=front-next;while(temp)if(!Visit(temp-data)return false;temp = temp-next;return true;#endif/主程序/ 数组表示法#include iostream#include string#include iomanip#include LinkQueue.husing namespace std;#define MAX_VERTEX_NUM 20 /最大顶点数const int infinity = INT_MAX;struct ArcCellint adj; /对无权图有1，0表示是否相邻，对带权图，则为权值类型 char *info; /该弧的相关信息;template struct _MGraph T vexsMAX_VERTEX_NUM;/顶点表ArcCell arc