数据结构实验报告(共34页).doc

精选优质文档-倾情为你奉上数据结构实验报告姓名： 学号： 专业： 班 级： 指导教师： 实验时间： 实验地点： （实验题目）1. 实验内容和要求 实验一 顺序表实验实验要求1、顺序表结构定义，算法的实现以库文件方式实现，库文件名统一为seqList.h；2、实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；3、程序有适当的注释。实验任务 编写算法实现下列问题的求解。<1>求顺序表中第i个元素（函数），若不存在，报错。实验测试数据基本要求：第一组数据：顺序表长度n10，i分别为5，n，0，n+1，n+2第二组数据：顺序表长度n=0，i分别为0，2<2>在第i个结点前插入值为x的结点。实验测试数据基本要求：第一组数据：顺序表长度n10，x=100, i分别为5,n,n+1,0,1,n+2第二组数据：顺序表长度n=0，x=100，i=5<3>删除顺序表中第i个元素结点。实验测试数据基本要求：第一组数据：顺序表长度n10，i分别为5,n,1,n+1,0 第二组数据：顺序表长度n=0， i=5<4>在一个递增有序的顺序表L中插入一个值为x的元素，并保持其递增有序特性。实验测试数据基本要求：顺序表元素为 （10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8<5>将顺序表中的奇数项和偶数项结点分解开（元素值为奇数、偶数），分别放入新的顺序表中，然后原表和新表元素同时输出到屏幕上，以便对照求解结果。实验测试数据基本要求：第一组数据：顺序表元素为 （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）<6>求两个递增有序顺序表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） 实验二 单链表实验实验要求1、本次实验中的链表结构均为带头结点的单链表；2、链表结构定义，算法实现放入库文件“linkList.h”；3、运算和变量命名直观易懂，并有相应的注释。实验任务 编写算法实现下列问题的求解。<1>求链表中第i个结点的指针（函数），若不存在，则返回NULL。实验测试数据基本要求：第一组数据：链表长度n10，i分别为5，n，0，n+1，n+2第二组数据：链表长度n=0，i分别为0，2<2>在第i个结点前插入值为x的结点。实验测试数据基本要求：第一组数据：链表长度n10，x=100, i分别为5,n,n+1,0,1,n+2第二组数据：链表长度n=0，x=100，i=5<3>删除链表中第i个元素结点。实验测试数据基本要求：第一组数据：链表长度n10，i分别为5,n,1,n+1,0 第二组数据：链表长度n=0， i=5<4>在一个递增有序的链表L中插入一个值为x的元素，并保持其递增有序特性。实验测试数据基本要求：链表元素为 （10,20,30,40,50,60,70,80,90,100）,x分别为25，85，110和8<5>将单链表中的奇数项和偶数项结点分解开（元素值为奇数、偶数），申请2个头结点，把分开的奇数项和偶数项分别链接到这2个头结点上，然后再将这两个新链表同时输出在屏幕上，并保留原链表的显示结果，以便对照求解结果。实验测试数据基本要求：第一组数据：链表元素为 （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）<6>求两个递增有序链表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） 实验三 链栈实验实验要求1、本次实验中，链栈使用带头结点的单链表实现。2、链栈结构定义，算法实现全部放入库函数“linkStack.h”中；3、各运算和变量命名直观易懂，并有相应的注释。实验任务 编写算法实现下列问题的求解。<1>初始化一个链栈。<2>判断是否空栈。<3>入栈第一组数据：10，13，5，8，20，55第二组数据：a, b, c, d, e, f, g<4>取栈顶元素<5>出栈<6>将10进制数转换为16进制数第一组数据：4第二组数据：11第三组数据：254第四组数据：1357 实验四 循环队列实验实验要求1、本次实验中，队列使用顺序结构循环队列；2、结构定义和运算实验放入库文件“seqQueue.h”中；3、各运算和变量命名直观易懂，并有相应的注释。实验任务 编写算法实现下列问题的求解。<1>初始化一个队列。<2>判断是否队空。<3>判断是否队满。设队列最大长度：MaxLen=100第一组数据：入队n个元素，判断队满第二组数据：用循环方式将1到99，99个元素入队，判队满<4>入队第一组数据：4，7，8，12，20，50第二组数据：a,b,c,d,f,g<5>出队<6>取队头元素<7>求当前队列中元素个数<8>编写算法实现初始化空循环队列；当键盘输入奇数时，此奇数入队；当键盘输入偶数时，队头出队；当键盘输入0时，算法退出；每当键盘输入后，输出当前队列中的所有元素。2. 实验目的 实验一 顺序表实验1、理解线性表的顺序存储结构。2、熟练掌握顺序表的有关算法设计。3、根据具体问题的需要，设计出合理的表示数据的顺序结构，并设计相关算法。 实验二 单链表实验实验目的1、理解线性表的链式存储结构。2、熟练掌握单链表结构及有关算法的设计。3、根据具体问题的需要，设计出合理的表示数据的链表结构，并设计相关算法。 实验三 链栈实验实验目的1、掌握栈的基本概念。2、掌握链栈的建立、入栈和出栈等方法。3、根据具体问题的需要，设计出合理的表示数据的结构，并设计相关算法。 实验四 循环队列实验 实验目的1、掌握队列的基本概念。2、掌握循环队列的建立、入队和出队等方法。3、根据具体问题的需要，设计出合理的表示数据的结构，并设计相关算法。3. 数据结构设计采用带头结点的链表结构设计4. 算法设计 实验一 顺序表实验<1>#include "stdafx.h"#include "iostream.h"#include "seqList.h"void GetElement(seqList L,int i,elementType x)if(getElement(L,i,x)cout<<"L中第"<<i<<"个元素是："<<x<<endl;else cout<<"输入序号超出顺序表L范围。"<<endl;void main(int argc, char* argv) seqList L;int i;elementType x; initialList(&L); /初始化顺序表 CreateSeqList( L);cout<<"请输入要查找的序号"<<endl;cin>>i;GetElement( L,i, x);<2>#include "stdafx.h"#include "iostream.h"#include "seqList.h"void InsertData(seqList *L, elementType x, int m)int k,i;k=listInsert( L, x, m);if (k=0)cout<<"表满"<<endl;else if (k=1)cout<<"插入序号错误"<<endl;else cout<<"插入后的顺序表为"<<endl;for(i=0;i<L->listLen;i+)cout<<L->datai<<" "cout<<endl;void main (int argc, char* argv)seqList L; int m,i;elementType x; initialList(&L); CreateSeqList( L);cout<<"请输入要插入的序号"<<endl;cin>>m; cout<<"请输入插入的元素值"<<endl;cin>>x; cout<<"插入前的顺序表为："<<endl; for(i=0;i<L.listLen;i+)cout<<L.datai<<" "cout<<endl;InsertData(&L, x, m);<3>#include "stdafx.h"#include "iostream.h"#include "seqList.h"void DeleteData(seqList *L,int m)int k,i;k=listDelete(L,m);if(k=0)cout<<"空表"<<endl;else if(k=1)cout<<"删除的序号超出范围"<<endl;else for(i=0;i<L->listLen;i+)cout<<L->datai<<" "cout<<endl;void main(int argc, char* argv) seqList L;int m,i; initialList(&L); CreateSeqList( L);cout<<"请输入删除的序号"<<endl; cin>>m;cout<<"原顺序表为："<<endl;for(i=0;i<L.listLen;i+)cout<<L.datai<<" "cout<<endl;cout<<"删除后的顺序表是："<<endl;DeleteData(&L, m); <4>#include"stdafx.h"#include"iostream.h"#include"seqList.h"void OrderInsert(seqList &L,elementType x)int i=L.listLen-1;if(i>=MaxLen-1) cout<<"序号超出范围"<<endl;elsewhile(i>=0&&L.datai>x)L.datai+1=L.datai;i-;L.datai+1=x;L.listLen+;void main()seqList L;int i;elementType x;initialList(&L);CreateSeqList( L);cout<<"原递增顺序表为"<<endl;for(i=0;i<L.listLen;i+)cout<<L.datai<<" "cout<<endl;cout<<"请输入插入的元素"<<endl;cin>>x;OrderInsert(L,x); cout<<"插入后的递增顺序表为："<<endl; for(i=0;i<L.listLen;i+)cout<<L.datai<<" "cout<<endl;<5>#include"stdafx.h"#include"iostream.h"#include"seqList.h"void SeperateData(seqList &L)seqList O,J;int i,m=0,n=0;for(i=0;i<L.listLen;i+)if(L.datai%2=0) O.datam+=L.datai;else J.datan+=L.datai;cout<<"偶数值顺序表为"<<endl;for(i=0;i<m;i+)cout<<O.datai<<" "cout<<endl; cout<<"奇数值顺序表为"<<endl; for(i=0;i<n;i+)cout<<J.datai<<" "cout<<endl;void main()int i;seqList L;initialList(&L);CreateSeqList(L);cout<<"原顺序表为"<<endl;for(i=0;i<L.listLen;i+)cout<<L.datai<<" "cout<<endl;SeperateData(L);<6>#include"stdafx.h"#include"iostream.h"#include"seqList.h"void PublicData(seqList &L1,seqList &L2,seqList &L3)int i1=0,i2=0,i3=0,i;while(i1<L1.listLen&&i2<L2.listLen)if(L1.datai1=L2.datai2)L3.datai3+=L1.datai1+;i2+;else if(L1.datai1>L2.datai2)i2+;elsei1+;L3.listLen=i3;for(i=0;i<L3.listLen;i+)cout<<L3.datai<<" "cout<<endl;void main()int i;seqList L1,L2,L3;initialList(&L1);initialList(&L2);initialList(&L3);cout<<"请输入第一个递增顺序表的元素"<<endl;CreateSeqList( L1);cout<<"请输入第二个递增顺序表的元素"<<endl; CreateSeqList( L2);cout<<"第一个顺序表为："<<endl;for(i=0;i<L1.listLen;i+)cout<<L1.datai<<" "cout<<endl; cout<<"第二个顺序表为："<<endl;for(i=0;i<L2.listLen;i+)cout<<L2.datai<<" "cout<<endl;cout<<"公共元素为："<<endl;PublicData(L1,L2,L3); 实验二 单链表实验<1>#include"linkedList.h"void main() node *L,*p; int i; initialList(*& L); createListR( *& L ); cout<<"请输入要查找的元素节点序号"<<endl; cin>>i; p=getElement(L, i); cout<<"第"<<i<<"个节点的指针 p="<<p<<endl; <2>#include"linkedList.h"void InsertData(node *L,elementType x, int i)node *p;bool Q; Q=listInsert( L, i, x ); if(Q=true) /打印链表 cout<<"插入后的链表为："<<endl; p=L->next; while(p) cout<<p->data<<" " p=p->next; cout<<endl; else cout<<"插入位置 i不对"<<endl; void main()node *L,*p;elementType x;int i; createListR( *& L ); cout<<"原链表为："<<endl; p=L->next; while(p) cout<<p->data<<" " p=p->next; cout<<endl; cout<<"请输入要插入的元素值"<<endl;cin>>x;cout<<"请输入要插入的位置"<<endl;cin>>i; InsertData(L, x, i);<3>#include"linkedList.h"void DeleteData(node *L,int i)node *p;bool Q=listDelete( L, i);if(Q=true)cout<<"删除后的链表为："<<endl;p=L->next;while(p)cout<<p->data<<" "p=p->next;cout<<endl;else cout<<"删除节点错误"<<endl;void main() node *L,*p; int i; createListR( *& L ); cout<<"原链表为："<<endl; p=L->next;while(p)cout<<p->data<<" "p=p->next;cout<<endl;cout<<"请输入要删除的节点序号："<<endl; cin>>i; DeleteData(L,i);<4>#include"linkedList.h"void OrderInsert(node *L,elementType x)node *u,*p=L;while(p->next!=NULL&&p->next->data<x)p=p->next;if(p->next=NULL|p->next->data>x)u=new node;/产生节点，此步骤不可少u->data=x;u->next=p->next;p->next=u;p=L->next;while(p!=NULL)cout<<p->data<<" "p=p->next;cout<<endl;void main() elementType x; node *p; node *L;createListR( *& L );cout<<"输出原递增有序的链表"<<endl;p=L->next;while(p)cout<<p->data<<" "p=p->next;cout<<endl;cout<<"输入插入的数字"<<endl;cin>>x;cout<<"输出插入后的递增有序表"<<endl;OrderInsert(L,x);<5>#include "linkedList.h"void PrintList(node *L)node *p; p=L->next;while(p)cout<<p->data<<" "p=p->next;cout<<endl;void SeperateData(node *L,node *&J,node *&O)node *p,*Rj,*Ro,*u,*t;J=new node;O=new node;Rj=J;Ro=O;p=L->next;while(p)if(p->data%2=0)u=new node;u->data=p->data;Ro->next=u;Ro=u;else t=new node;t->data=p->data;Rj->next=t;Rj=t;Ro->next=NULL;Rj->next=NULL; p=p->next; void main()node *L,*J,*O;cout<<"创建一个链表"<<endl; createListR( *& L ); cout<<"所创建的链表为"<<endl; PrintList(L);SeperateData( L, *&J, *&O);cout<<"奇数结点组成的链表为"<<endl;PrintList(J);cout<<"偶数结点组成的链表为"<<endl;PrintList(O);<6>#include"linkedList.h"void PrintList(node *L)node *p; p=L->next;while(p)cout<<p->data<<" "p=p->next;cout<<endl;void PublicData(node *A,node *B,node *&C)node *pa,*pb,*Rc,*u;C=new node;Rc=C;pa=A->next;pb=B->next;while(pa!=NULL&&pb!=NULL)if(pa->data<pb->data)pa=pa->next;else if(pb->data>pb->data)pb=pb->next;elseu=new node;u->data=pa->data;Rc->next=u;Rc=u;pa=pa->next;pb=pb->next;Rc->next=NULL;void main()node *A,*B,*C;cout<<"创建第一个链表"<<endl; createListR( *&A ); cout<<"创建第二个链表"<<endl; createListR( *&B); cout<<"打印第一个链表:"<<endl; PrintList(A); cout<<"打印第二个链表"<<endl; PrintList(B);PublicData(A,B,*&C);cout<<"打印公共元素组成的链表"<<endl;PrintList(*&C); 实验三 链栈实验/ alltest.cpp : Defines the entry point for the console application./#include "stdafx.h"#include "iostream.h"#include "linkStack.h"int main(int argc, char* argv) node* H, *L, *P,*q; elementType y;initialstack(L);/初始化 if(stackEmpty(L) cout<<"空栈"<<endl; else cout<<"栈不空"<<endl; cout<<"尾插法创建带头结点的单链表>>"<<endl;/以“666”作为结束元素输入条件，用引用参数返回链表 pushstack( L ); H=L->next;/H为头指针cout<<"入栈元素顺序为："P=L->next;while(P)cout<<P->data<<","P=P->next;cout<<endl; popstack(H);L->next=H;cout<<"出栈后元素顺序为："P=H;while(P)cout<<P->data<<","P=P->next;cout<<endl; if(stacktop(H,q) y=q->data;cout<<"栈顶元素"<<y<<endl; destroyList(L);return 0;/ Tentosixteen.cpp : Defines the entry point for the console application./#include "stdafx.h"#include "iostream.h"#include ".linkStack.h"int main(int argc, char* argv) node *p,*L,*H;initialstack(L);int M,x;char a,b,c,d,e,f; cout<<"输入一个10进制数:"cin>>M;Tentosixteen(&M,L); H=L->next; cout<<"入栈元素顺序为："p=L->next;while(p)cout<<p->data<<","p=p->next;cout<<endl; popstack(H);L->next=H;cout<<"输出一个16进制数:OX" p=H; while(p) x=p->data; switch(x) case 97: cout<<"A" break; case 98: cout<<"B" break; case 99: cout<<"C" break; case 100: cout<<"D" break; case 101: cout<<"E" break; case 102: cout<<"F" break; default: cout<<x;p=p->next;cout<<endl;destroyList(L);return 0; 实验四 循环队列实验<1>-<7>#include ".stdafx.h"#include ".seqQueue.h"int main(int argc, char* argv)seqQueue Q;elementType x;int i; cout<<"1. 初始化顺序循环队列"<<endl;initQueue(&Q);cout<<"2. 判断空队列"<<endl;if(queueEmpty(Q)cout<<"当前队列空！"<<endl;elsecout<<"当前队列非空！"<<endl;cout<<" 3.循环入队"<<endl;for(i=1;i<=99;i+)enQueue(&Q, i); /循环入队/打印当前队列中元素，从头至尾cout<<"当前队列中元素（从头至尾）:"i=Q.front+1;while(i<=Q.rear)cout<<Q.datai<<", "i+;cout<<endl;cout<<"4. 判队满"<<endl;if(queueFull(Q)cout<<"当前队满！"<<endl;elsecout<<"当前队列不满！"<<endl;cout<<"5. 取队头元素"<<endl;queueFront(Q, x);cout<<"当前队头元素: x="<<x<<endl;cout<<"6. 出队（删除）"<<endl;outQueue(&Q);/打印当前队列中元素，从头至尾cout<<"出队后队列中元素（从头至尾）:"<<endl;i=Q.front+1;while(i<=Q.rear)cout<<Q.datai<<", "i+;cout<<endl;cout<<"7.判断当前队列中的元素个数"<<endl;cout<<i-1<<endl;return 0;<8>#include"seqQueue.h"void main() seqQueue Q;elementType x,y;int i; initQueue(&Q);/初始化空队列cout<<"输入x"<<endl;cin>>x;while(x!=0)int n=x%2;if(n)enQueue(&Q, x);/当x是奇数时，入队if(n!=0) queueFront(Q, y);cout<<"当前队头元素: y="<<y<<endl; /打印当前队列中元素，从头至尾cout<<"出队后队列中元素（从头至尾）:"<<endl;i=Q.front+1;while(i<=Q.rear)cout<<Q.datai<<", "i+;cout<<endl;/键盘继续输入cout<<"输入x"<<endl;cin>>x;5. 运行和测试 实验一 顺序表实验<1><2><3><4><5><6> 实验二 单链表实验<1><2><3><4><5><6> 实验三 链栈实验 实验四 循环队列实验<1>-<7>6. 总结和心得 首先呢，先要感谢敬爱的张老师，说实话您是我在大学里遇到的不多的几个让我感到特别和蔼可亲的老师之一，您给我们上课时总是面带笑容，讲解内容也特别的细致，而且还会教给我们许多其他的东西，可以说我对数据结构这门课的兴趣很大程度是您给予我的。虽然您很少点名，但您可以翻看一下，每次点名我都到了。您的课我确实每次都来了，不是因为怕您点名，而是真的喜欢