1、算法与数据结构实验报告算法与数据结构实验报告学院：计算机与信息学院专业_实验一栈和队列实验目的：掌握栈和队列特点、逻辑结构和存储结构熟悉对栈和队列的一些基本操作和具体的函数定义.利用栈和队列的基本操作完成一定功能的程序.实验任务：1.给出顺序栈的类定义和函数实现,利用栈的基本操作完成十进制数N与其它d进制数的转换.如N=1357,d=8实验原理：将十进制数N转换为八进制时,采用的是除取余数法,即每次用8除N所得的余数作为八进制数的当前个位,将相除所得的商的整数部分作为新的N值重复上述计算,直到N为0为止.此时,将前面所得到的各余数反过来连接便得到最后的转换结果.程序清单：#include#in
2、cludeusing namespace std;typedef int DATA_TYPE;const int MAXLEN=100;enum error_codesuccess,overflow,underflow;class stackpublic:stack;bool emptyconst;error_code get_topconst;error_code push;error_code pop;bool fullconst;private:DATA_TYPE dataMAXLEN;int count;stack:stackcount=0;bool stack:emptyconstr
3、eturn count=0;error_code stack:get_topconstifemptyreturn underflow;elsex=datacount-1;return success;error_code stack:pushiffullreturn overflow;elsedatacount=x;count+;error_code stack:popifemptyreturn underflow;elsecount-;return success;bool stack:fullconstreturn count=MAXLEN;void mainstack S;int N,d
4、;cout请输入一个十进制数N和所需转换的进制dNd;ifcout输出转换结果:Nendl;whileS.push;N=N/d;cout输出转换结果:endl;while!S.emptyS.get_top;coutN;S.pop;coutendl;while!S.emptyS.get_top;coutx;S.pop;测试数据：N=1348 d=8运行结果：2.给出顺序队列的类定义和函数实现,并利用队列计算并打印杨辉三角的前n行的内容.实验原理：杨辉三角的规律是每行的第一和最后一个数是1,从第三行开始的其余的数是上一行对应位置的左右两个数之和.因此,可用上一行的数来求出对应位置的下一行内容.为此
5、,需要用队列来保存上一行的内容.每当由上一行的两个数求出下一行的一个数时,其中的前一个便需要删除,而新求出的数就要入队.程序清单：#include#includeusing namespace std;typedef int DATA_TYPE;const int MAXLEN=100;enum error_codesuccess,underflow,overflow;class queuepublic:queue;bool emptyconst;error_code get_frontconst; error_code append; error_code serve;bool fullco
6、nst;private:int front,rear;DATA_TYPE dataMAXLEN;queue:queuerear=0;front=0;bool queue:emptyconstreturn ;error_code queue:get_frontconst ifemptyreturn underflow;elsex=datafront%MAXLEN;return success;error_code queue:append iffullreturn overflow;elsedatarear%MAXLEN=x;rear+;error_code queue:serveifempty
7、return underflow;elsefront+;return success;bool queue:fullconstreturn%MAXLEN=front; void mainqueue Q;int num1,num2;int i=0;cout1endl;Q.append;num1=0;num2=1;fori=0;iint j=0;int k=0;num1=0;forj=0;jQ.get_front;Q.serve;coutnum1+num2 ;Q.append;num1=num2;cout1endl;Q.append;运行结果：3.给出链栈的类定义和函数实现,并设计程序完成如下功能
8、：读入一个有限大小的整数n,并读入n个数,然后按照与输入次序相反的次序输出各元素的值.实验原理：依次将栈中的元素出栈,因为栈的一个特点就是先进后出,这样,当将原栈为空时,输出与输入次序相反,从而实现了本题的要求.程序清单：#include#includeusing namespace std;typedef int DATA_TYPE;typedef struct LNodeDATA_TYPE data;LNode *next;LNode;enum error_coderange_error,success,underflowclass linkstackpublic:linkstack;li
9、nkstack;bool emptyconst;error_code push;error_code get_topconst;error_code pop;private:LNode *top;int count;DATA_TYPE data;linkstack:linkstacktop=NULL;count=0;bool linkstack:emptyconstreturn ;error_code linkstack:pushLNode *s=new LNode;s-data=x;s-next=top;top=s;count+;return success;error_code links
10、tack:get_topconstifemptyreturn underflow;elsex=top-data;return success;error_code linkstack:popifemptyreturn underflow;elseLNode *u=new LNode;u=top;top=top-next;delete u;count-;return success;linkstack:linkstackwhile!emptypop;void mainlinkstack L;int n;cout请任意输入一个整数n:n;forint i=1;iL.push;while!L.emp
11、tyL.get_top;couti ;L.pop;测试数据：n=9 i=1运行结果：实验二单链表实验目的：理解线性表的链式存储结构.熟练掌握动态链表结构与有关算法的设计.根据具体问题的需要,设计出合理的表示数据的链表结构,并设计相关算法.实验任务：1.在一个递增有序的链表L中插入一个值为x的元素,并保持其递增有序特性.实验数据：链表元素为10,20,30,40,50,60,70,80,90,100,x分别为25,85,110和8. 实验原理:给出了要插入的条件,但没有给定插入位置.因此,需要搜索满足这一条件的插入位置的前驱结点而不是序号.程序清单:#include using namespac
12、e std;enum error_code success, overflow, underflow, rangeerror;typedef int elementtype ;typedef struct LinkNode elementtype data; struct LinkNode *next; node; class listprivate: int count; node *head;public: list; list;public: error_code get_element const; node * get_head const return head; void cre
13、ate; void display; void insert1;list:list head = new node; head - next = NULL; count = 0;void list:create elementtype x; node *s,*rear; cin x; rear = head; while count +; s = new node; s - data = x; s - next=NULL; rear - next = s; rear = s; cin x; void list:display node *p; p=head-next; while coutda
14、tanext; coutendl;void list:insert node* u,*P; P=head; whilenext!=NULL & P-next-data P=P-next; ifnext=NULL|P-next-datax u=new node; u-data=x; u-next=P-next; P-next=u; count+; void main list L; elementtype x; L.create; L.display; cout请输入要插入的值xx; L.insert; L.display;运行结果：X=25X=85X=110X=82.将单链表中的奇数项和偶数项
15、结点分解开,并分别连成一个带头结点的单链表,然后再将这两个新链表同时输出在屏幕上,并保留原链表的显示结果,以便对照求解结果.实验测试数据：第一组数据：链表为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实验原理：依据题目的要求,需要再创建两个新链表来存储分离后的奇偶项,而奇偶项可以根据数字来控制,把他们取出来并重新连起来.程序清单：#include using namespace std;enum error_code success, overflow, underflow, rangeer
16、ror;typedef int elementtype ;typedef struct LinkNode elementtype data; struct LinkNode *next; node; class listprivate: int count; node *head;public: list; list;public: node * get_head const return head; void create; void display;list:list head = new node; head - next = NULL; count = 0;void list:crea
17、te elementtype x; node *s,*rear; cin x; rear = head; while count +; s = new node; s - data = x; s - next=NULL; rear - next = s; rear = s; cin x; void list:display node *p; p=head-next; while coutdatanext; coutendl;void divide node *PA,*PB,*PC,*s; PB=B.get_head; PC=C.get_head; PA = A.get_head - next;
18、 while ifdata%2!=0 s=new node; s-data=PA-data; PB-next = s; PB=s; PB-next=NULL; PA=PA-next; else s=new node; s-data=PA-data; PC-next = s; PC=s; PC-next=NULL; PA=PA-next; void main list L,L1,L2; L.create; divide; cout原链表：endl; L.display; cout偶链表：endl; L2.display; cout奇链表：endl; L1.display;实验结果：第一组数据：第
19、二组数据：1.求两个递增有序链表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实验原理：设置两个指针怕,pa,pb分别依次指示A,B表中的元素,其初始值分别为A.head-next和B.head-next.在pa,pb均非空时,根据其值的大小关系可能有如下三种情况.pa-data=pb-data:
20、搜索到公共元素,应在C表表尾插入一个结点,其值为pa-data,然后继续A表中下一个元素的搜索,即pa=pa-next,同时pb也往后移.pa-datapb-data:表明A表中这一元素可能在B表当前元素的后面,因此要往B表的后面搜索,故而执行pb=pb-next,然后继续搜索.pa-datadata:表明A中这一元素在B中不存在,因而执行pa=pa-next以继续对A表中下一个元素的判断.反复执行上述比较,直到pa,pb至少有一个为空为止.此时,剩余的非空部分没有所需要的公共元素,因而搜索结束.程序清单：#include#includeusing namespace std;typedef
21、struct snodeint data;struct snode *next;node;enum error_codearrange_error,success;class listpublic:list;void create2;int length const;error_code get_element const;error_code insert;error_code delete_element;node *locate const;node *get_headreturn head;void list:gongyouvoid print;private:int count;no
22、de *head;list:listhead=new node; head-next=NULL;count=0;void list:create2int x; node *p=head;node *s; coutx;whiles=new node; s-data=x;s-next=NULL; p-next=s;p=s; coutx;int list:length constreturn count;error_code list:get_element constint j=1; node *p=head-next;whilep=p-next; j+;ifreturn arrange_erro
23、r;x=p-data;return success;void list:gongyounode *p1=L1.head-next; node *p2=L2.head-next;node *p3=head; node *u;whileifdata=p2-datau=new node; u-data=p1-data; p3-next=u; p1=p1-next; p2=p2-next; p3=p3-next;elseifdatadatap1=p1-next;elsep2=p2-next;p3-next=NULL;node *list:locate constnode *p=head-next;whileifdata=xreturn p;p=p-next;return NULL;void list:dividenode *u; node *pa=head-next;node *pb=B.get_head; node *pc=C.get_head; fornextu=new node; u-data=pa-data;ifpb-next=u; pb=pb-next;else
