您好,欢迎访问三七文档
当前位置:首页 > 电子/通信 > 综合/其它 > 数据结构实验报告(合工大)
数据结构实验报告实验一:栈和队列实验目的:掌握栈和队列特点、逻辑结构和存储结构熟悉对栈和队列的一些基本操作和具体的函数定义。利用栈和队列的基本操作完成一定功能的程序。实验任务1.给出顺序栈的类定义和函数实现,利用栈的基本操作完成十进制数N与其它d进制数的转换。(如N=1357,d=8)实验原理:将十进制数N转换为八进制时,采用的是“除取余数法”,即每次用8除N所得的余数作为八进制数的当前个位,将相除所得的商的整数部分作为新的N值重复上述计算,直到N为0为止。此时,将前面所得到的各余数反过来连接便得到最后的转换结果。程序清单#includeiostream#includecstdlibusingnamespacestd;typedefintDATA_TYPE;constintMAXLEN=100;enumerror_code{success,overflow,underflow};classstack{public:stack();boolempty()const;error_codeget_top(DATA_TYPE&x)const;error_codepush(constDATA_TYPEx);error_codepop();boolfull()const;private:DATA_TYPEdata[MAXLEN];intcount;};stack::stack(){count=0;}boolstack::empty()const{returncount==0;}error_codestack::get_top(DATA_TYPE&x)const{if(empty())returnunderflow;else{x=data[count-1];returnsuccess;}}error_codestack::push(constDATA_TYPEx){if(full())returnoverflow;else{data[count]=x;count++;}}error_codestack::pop(){if(empty())returnunderflow;else{count--;returnsuccess;}}boolstack::full()const{returncount==MAXLEN;}voidmain(){stackS;intN,d;cout请输入一个十进制数N和所需转换的进制dendl;cinNd;if(N==0){cout输出转换结果:Nendl;}while(N){S.push(N%d);N=N/d;}cout输出转换结果:endl;while(!S.empty()){S.get_top(N);coutN;S.pop();}coutendl;}while(!S.empty()){S.get_top(x);coutx;S.pop();}}测试数据:N=1348d=8运行结果:2.给出顺序队列的类定义和函数实现,并利用队列计算并打印杨辉三角的前n行的内容。(n=8)实验原理:杨辉三角的规律是每行的第一和最后一个数是1,从第三行开始的其余的数是上一行对应位置的左右两个数之和。因此,可用上一行的数来求出对应位置的下一行内容。为此,需要用队列来保存上一行的内容。每当由上一行的两个数求出下一行的一个数时,其中的前一个便需要删除,而新求出的数就要入队。程序清单:#includeiostream#includecstdlibusingnamespacestd;typedefintDATA_TYPE;constintMAXLEN=100;enumerror_code{success,underflow,overflow};classqueue{public:queue();boolempty()const;error_codeget_front(DATA_TYPE&x)const;error_codeappend(constDATA_TYPEx);error_codeserve();boolfull()const;private:intfront,rear;DATA_TYPEdata[MAXLEN];};queue::queue(){rear=0;front=0;}boolqueue::empty()const{return(front%MAXLEN==rear%MAXLEN);}error_codequeue::get_front(DATA_TYPE&x)const{if(empty())returnunderflow;else{x=data[front%MAXLEN];returnsuccess;}}error_codequeue::append(constDATA_TYPEx){if(full())returnoverflow;else{data[rear%MAXLEN]=x;rear++;}}error_codequeue::serve(){if(empty())returnunderflow;else{front++;returnsuccess;}}boolqueue::full()const{return((rear+1)%MAXLEN==front);}voidmain(){queueQ;intnum1,num2;inti=0;cout1endl;Q.append(1);num1=0;num2=1;for(i=0;i=7;i++){intj=0;intk=0;num1=0;for(j=0;j=i;j++){Q.get_front(num2);Q.serve();coutnum1+num2;Q.append(num1+num2);num1=num2;}cout1endl;Q.append(1);}}运行结果:3.给出链栈的类定义和函数实现,并设计程序完成如下功能:读入一个有限大小的整数n,并读入n个数,然后按照与输入次序相反的次序输出各元素的值。实验原理:依次将栈中的元素出栈,因为栈的一个特点就是先进后出,。这样,当将原栈为空时,输出与输入次序相反,从而实现了本题的要求。程序清单:#includeiostream#includecstdlibusingnamespacestd;typedefintDATA_TYPE;typedefstructLNode{DATA_TYPEdata;LNode*next;}LNode;enumerror_code{range_error,success,underflow};classlinkstack{public:linkstack();~linkstack();boolempty()const;error_codepush(constDATA_TYPEx);error_codeget_top(DATA_TYPE&x)const;error_codepop();private:LNode*top;intcount;DATA_TYPEdata;};linkstack::linkstack(){top=NULL;count=0;}boollinkstack::empty()const{return(count==0);}error_codelinkstack::push(constDATA_TYPEx){LNode*s=newLNode;s-data=x;s-next=top;top=s;count++;returnsuccess;}error_codelinkstack::get_top(DATA_TYPE&x)const{if(empty())returnunderflow;else{x=top-data;returnsuccess;}}error_codelinkstack::pop(){if(empty())returnunderflow;else{LNode*u=newLNode;u=top;top=top-next;deleteu;count--;returnsuccess;}}linkstack::~linkstack(){while(!empty()){pop();}}voidmain(){linkstackL;intn;cout请任意输入一个整数n:endl;cinn;for(inti=1;i=n;i++){L.push(i);}while(!L.empty()){L.get_top(i);couti;L.pop();}}测试数据:n=9i=1运行结果:实验二:单链表实验目的:理解线性表的链式存储结构。熟练掌握动态链表结构及有关算法的设计。根据具体问题的需要,设计出合理的表示数据的链表结构,并设计相关算法。实验任务:在一个递增有序的链表L中插入一个值为x的元素,并保持其递增有序特性。1.实验数据:链表元素为(10,20,30,40,50,60,70,80,90,100),x分别为25,85,110和8。实验原理:给出了要插入的条件,但没有给定插入位置。因此,需要搜索满足这一条件的插入位置的前驱结点而不是序号。程序清单:#includeiostream#includecstdlibusingnamespacestd;typedefstructsnode{intdata;structsnode*next;}node;enumerror_code{arrange_error,success};classlist{public:list();voidcreate2();intlength()const;error_codeget_element(constinti,int&x)const;error_codeinsert(constint&x);error_codedelete_element(constinti);node*locate(constintx)const;node*get_head(){returnhead;}voidprint();private:intcount;node*head;};list::list(){head=newnode;head-next=NULL;count=0;}voidlist::create2(){intx;node*p=head;node*s;cout输入一个值:;cinx;while(x!=-1){s=newnode;s-data=x;s-next=NULL;p-next=s;p=s;cout输入一个值:;cinx;}}intlist::length()const{returncount;}error_codelist::get_element(constinti,int&x)const{intj=1;node*p=head-next;while(p!=NULL&&j!=i){p=p-next;j++;}if(p==NULL)returnarrange_error;x=p-data;returnsuccess;}node*list::locate(constintx)const{node*p=head-next;while(p!=NULL){if(p-data==x)returnp;p=p-next;}returnNULL;}error_codelist::insert(constint&x){node*s;node*q=head;node*p=head-next;while(p!=NULL&&p-datax){q=p;p=p-next;}if(p==NULL){s=newnode;s-data=x;s-next=NULL;q-next=s;count++;}else{s=newnode;s-data=x;s-next=q-next;q-next=s;count++;}returnsuccess;}error_c
本文标题:数据结构实验报告(合工大)
链接地址:https://www.777doc.com/doc-1814204 .html