算法与数据结构实验报告

算法与数据结构实验报告学院：计算机与信息学院专业班级：姓名：学号：实验一栈和队列实验目的：掌握栈和队列特点、逻辑结构和存储结构熟悉对栈和队列的一些基本操作和具体的函数定义。利用栈和队列的基本操作完成一定功能的程序。实验任务：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)constif(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,underflowclasslinkstack{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运行结果：实验二单链表实验目的：理解线性表的链式存储结构。熟练掌握动态链表结构及有关算法的设计。根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。实验任务：1.在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。实验数据：链表元素为（10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8。实验原理:给出了要插入的条件，但没有给定插入位置。因此，需要搜索满足这一条件的插入位置的前驱结点而不是序号。程序清单:#includeiostreamusingnamespacestd;enumerror_code{success,overflow,underflow,rangeerror};typedefintelementtype;typedefstructLinkNode{elementtypedata;structLinkNode*next;}node;classlist{private:intcount;node*head;public:list();~list(){};public:error_codeget_element(constinti,elementtype&x)const;node*get_head()const{returnhead;}voidcreate();voiddisplay();voidinsert1(elementtypex);};list::list(){head=newnode;head-next=NULL;count=0;}voidlist::create(){elementtypex;node*s,*rear;cinx;rear=head;while(x!=-9999){count++;s=newnode;s-data=x;s-next=NULL;rear-next=s;rear=s;cinx;}}voidlist::display(){node*p;p=head-next;while(p!=NULL){coutp-data;p=p-next;}coutendl;}voidlist::insert(elementtypex){node*u,*P;P=head;while(P-next!=NULL&&P-next-datax)P=P-next;if(P-next==NULL||P-next-datax){u=newnode;u-data=x;u-next=P-next;P-next=u;count++;}}voidmain(){listL;elementtypex;L.create();L.display();cout请输入要插入的值xendl;cinx;L.insert(x);L.display();}运行结果：X=25X=85X=110X=82.将单链表Ｌ中的奇数项和偶数项结点分解开，并分别连成一个带头结点的单链表，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。实验测试数据：第一组数据：链表为（1,2,3,4,5,6,7,8,9,10,20,30,40,50,60）第二组数据：链表为（10,20,30,40,50,60,70,8