《基础性实践环节(数据结构)实践报告.docx》由会员分享，可在线阅读，更多相关《基础性实践环节(数据结构)实践报告.docx（42页珍藏版）》请在金锄头文库上搜索。
1、重 庆 大 学基础性实践环节(数据结构)实践报告实践课程名称 数据结构与算法 开课 实 验 室 数学实验教学中心 学 院 数学与统计学院年 级 2009级 专 业 班 信息与计算科学01班学 生 姓 名 学 号 20092250 开 课 时 间 2011 至 2012 学年 第 一 学期总 成 绩教师签名实验一、单链表的基本操作一、实验目的1、掌握线性链表的操作特点，即指针是逻辑关系的映像。2、掌握动态产生单链表的方法。3、熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。二、实验内容1、动态创建单链表2、实现线性表链式存储结构中元素的插入。3、实现线性表链式存储结构中元素的删除。三、
2、具体要求1、单链表的存储结构定义typedef struct lnode elemtype data; / 数据域 struct lnode *next; / 指针域 lnode, *linklist;2、从键盘上依次输入21、18、30、75、42、56，逆序创建单链表，并输出单链表中的各元素值。3、分别在单链表的第3个位置和第9个位置插入67和10，给出插入成功或失败的信息，并输出单链表中的各元素值。4、删除单链表中的第6个数据元素和第8个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值。四、完成情况和实验记录1、由于程序要求的操作很多，而且c程序要求敏感，所以在编程过程中只有
3、通过不断的修改，不断的尝试来克服遇到的很多错误和警告问题。在调试过程要有足够的耐心和发现错误的洞察力。五、完成情况和实验记录#include#include#include #include #define len sizeof(lnode) /定义len为一个节点的长度enum boolfalse,true; /定义bool型typedef struct nodeint data; /数据域 struct node *next;/指向下一个节点的指针lnode,*linklist;void creatlist(linklist &,int); /生成一个单链表bool listinsert(
4、linklist &,int,int); /在单链表中插入一个元素bool listdelete(linklist &,int,int); /在单链表中删除一个元素void listprint(linklist); /显示单链表所有元素void main()linklist l; bool temp; int num,loc,flag=1,ch; char j; /程序说明 printf(单链表的基本操作。n); printf(可以进行逆置，插入，删除等操作。n); printf(请输入初始时链表长度:); /输入生成单链表时的元素个数 scanf(%d,&num); creatlist(l,
5、num); /生成单链表 listprint(l); while(flag) printf(请选择:n); printf(1.显示所有元素n); /显示链表元素 printf(2.插入一个元素n); /插入链表元素 printf(3.删除一个元素n); /删除链表元素 printf(0.退出程序 n); /退出 scanf( %c,&j); switch(j) case 1:listprint(l); break; case 2:printf(请输入数据和要插入的位置-1:n);printf(格式：数据，位置；例如:12,3，（即把12插入到第3个位置之后，即第4个位置）n); scanf(
6、%d,%d,&ch,&loc); /输入要插入的元素和要插入的位置 temp=listinsert(l,loc,ch); /插入 if(temp=false) printf(插入失败!n); /插入失败 else printf(插入成功!n); /成功插入 listprint(l); break; case 3:printf(请输入要删除的元素所在位置-1：（输入2，即删除的是第3个元素）:); scanf(%d,&loc); /输入要删除的节点的位置 temp=listdelete(l,loc,ch); /删除 if(temp=false)printf(删除失败!n); /删除失败 else
7、 printf(成功删除了一个元素:%dn,ch); /删除成功，显示该元素 listprint(l); break; default:flag=0;printf(程序结束，按任意键退出!n); getchar();void creatlist(linklist &v,int n)/生成一个带头结点的有n个元素的单链表 int i; linklist p; v=(linklist)malloc(len); /生成头结点 v-next=null; printf(请输入%d个数据：例如：1 2 3n,n); getchar(); for(i=n;i0;-i) p=(linklist)malloc(
8、len); /生成新结点 scanf(%d,&p-data); p-next=v-next; v-next=p; bool listinsert(linklist &v,int i,int e)/在单链表的第i各位置插入元素e，成功返回true，失败返回false linklist p,s; int j=0; p=v; while(p&jnext; j; /查找第i-1个元素的位置 if(!p|ji) return false; /没有找到 s=(linklist)malloc(len); /生成一个新结点 s-data=e; s-next=p-next; /将新结点插入到单链表中 p-nex
9、t=s; return true;bool listdelete(linklist &v,int i,int e)/在单链表中删除第i个元素，成功删除返回true，并用e返回该元素值，失败返回false linklist p,q; int j=0; p=v; while(p-next&jnext; j; if(!(p-next)|ji) return false; /查找失败 q=p-next;p-next=q-next; /删除该元素 e=q-data; /e取得该元素值 free(q); /释放该元素空间 return true;void listprint(linklist v) /显示
10、链表所有元素 linklist q; q=v-next; printf(逆置输出链表所有元素:); while(q!=null) printf(%d ,q-data);q=q-next; printf(n);六、所输入的数据及相应的运行结果实验二 栈、队列算法设计一、实验目的1、 熟悉栈这种特殊线性结构的特性；2、 熟练掌握栈在顺序存储结构和链表存储结构下的基本运算；3、 熟悉队列这种特殊线性结构的特性；4、 熟练掌握队列在链表存储结构下的基本运算。二、实验内容1、动态创建栈和队列2、实现实现栈和队列中元素的插入。3、实现实现栈和队列中元素的的删除。三、具体要求1、用顺序和链式存储结构分别实现
11、栈的初始化、求长度、获取栈顶元素、压栈、出栈、判空、置空等操作，生成sqstack.h文件和linkstack.h文件；编写main函数调用。四、程序清单顺序栈#include#include#includeconst int stackincreament=20;const int maxsize=50;template class stackpublic:stack(int sz=50);stack() deleteelements;void push(const t& x);int pop(); int gettop();bool isempty() const return (top=
12、-1)?true:false;bool isfull() const return (top=maxsize-1)?true:false;int getsize() const return top 1;void makeempty() top=-1;void print(stack& s);void meun();private:t *elements;int top;int maxsize;void overflowprocess();template stack:stack(int sz):top(-1),maxsize(sz)elements=new tmaxsize;assert(elements!=null);template void stack:overflowprocess() t *newarray = new tmaxsize stackincreament; if (newarray=null) cerr存储分配失败!endl; exit(