基础性实践环节(数据结构)实践报告.docx

重 庆 大 学基础性实践环节(数据结构)实践报告实践课程名称 数据结构与算法 开课 实 验 室 数学实验教学中心 学 院 数学与统计学院年 级 2009级 专 业 班 信息与计算科学01班学 生 姓 名 学 号 20092250 开 课 时 间 2011 至 2012 学年 第 一 学期总 成 绩教师签名实验一、单链表的基本操作一、实验目的1、掌握线性链表的操作特点，即指针是逻辑关系的映像。2、掌握动态产生单链表的方法。3、熟练掌握单链表的插入、删除操作特点，即指针赋值的先后次序。二、实验内容1、动态创建单链表2、实现线性表链式存储结构中元素的插入。3、实现线性表链式存储结构中元素的删除。三、具体要求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程序要求敏感，所以在编程过程中只有通过不断的修改，不断的尝试来克服遇到的很多错误和警告问题。在调试过程要有足够的耐心和发现错误的洞察力。五、完成情况和实验记录#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(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,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( %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 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(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-next=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) /显示链表所有元素 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、用顺序和链式存储结构分别实现栈的初始化、求长度、获取栈顶元素、压栈、出栈、判空、置空等操作，生成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=-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(1); for (int i=0;i=top;i+) newarrayi = elementsi; maxsize = maxsize +stackincreament; delete elements; elements = newarray;template void stack:push(const t&x) if (isfull()=true) overflowprocess(); elements+top = x;template int stack:pop()return elementstop-;template int stack:gettop()return elementstop;template void stack:print(stack& s)for(int i=s.top;i=0;i-)couts.elementsi ;coutendl;template void stack:meun()cout操作如下：endl;cout1-输出栈内元素(栈顶到栈尾）endl;cout2-元素进栈(单个元素）endl;cout3-元素出栈endl;cout4-读取栈顶元素endl;cout5-得到栈中元素个数endl;cout6-清空栈endl;cout0-退出endl;cout请输入操作：;void main() stack a(50); int choice,x; a.meun(); cinchoice; while(choice!=0) switch(choice) case 1: cout从栈顶到栈尾元素的输出为：endl; a.print(a); break; case 2: coutx; a.push(x); break; case 3: cout弹出的元素是：a.pop()endl; break; case 4: cout栈顶元素是：a.gettop()endl; break; case 5: cout栈中元素个数是：a.getsize()endl; break; case 6: cout清空栈的内容：endl; a.makeempty(); break; default: break; coutchoice; 链栈#include#include#include#includetypedef int stackelementtype;typedef struct linkstacknodestackelementtype data;struct linkstacknode *next;linkstacknode;typedef structstruct linkstacknode *top; /栈顶指针linkstack;void initstack(linkstack *s)/初始化链栈s-top=null;printf(n已经初始化链栈！n);void clearstack(linkstack *s)/链栈置空s-top=null;printf(n链栈被置空！n);void push(linkstack *s, stackelementtype x)/入栈linkstacknode *p;p=(linkstacknode *)malloc(sizeof(linkstacknode); /建立一个节点p-data=x;p-next=s-top; /由于是在栈顶push，所以要指向栈顶s-top=p; /插入stackelementtype pop(linkstack *s)/出栈stackelementtype x;linkstacknode *p;p=s-top; /指向栈顶if (s-top=0)printf(栈空，不能出栈！n);exit(-1);x=p-data; s-top=p-next; /当前的栈顶指向原栈的nextfree(p); /释放return x;stackelementtype gettop(linkstack *s)/取栈顶元素if (s-top=0)printf(链栈为空，无栈顶元素！n);exit(-1);return s-top-data;void disp(linkstack *s)/链栈的遍历printf(n当前链栈中的数据为：n);printf(=n);linkstacknode *p;p=s-top;while(p!=null) printf(t| %d |n,p-data); p=p-next;printf(=n);void main() int cord;int i,m,n,a;linkstack *s;s=(linkstack *)malloc(sizeof(linkstack);printf(= 链栈操作=n);printf(t 第一次使用必须初始化！n);do printf(n 操作 );printf(n 1： 初始化链栈 );printf(n 2： 入栈 );printf(n 3： 出栈 );printf(n 4： 取栈顶元素 );printf(n 5： 置空链栈 );printf(n 6： 结束程序运行 n);printf(n=n);printf(请输入您的选择(1,2,3,4,5,6);scanf(%d,&cord);printf(n);switch(cord)case 1:initstack(s);disp(s);break;case 2:printf(输入将要压入链栈的数据的个数：n=);scanf(%d,&n);printf(依次将%d个数据压入链栈：n,n);for(i=1;i=n;i+)printf(请输入第%d个数据：,i);scanf(%d,&a);push(s,a);disp(s);break;case 3:printf(n出栈操作开始!n);printf(输入将要出栈的数据个数：m=);scanf(%d,&m);for(i=1;i=m;i+)printf(n第%d次出栈的数据是：%d,i,pop(s);disp(s);break;case 4:printf(nn链栈的栈顶元素为：%dn,gettop(s);printf(n);break; case 5:clearstack(s);disp(s);break;case 6:exit(0);while (cord=6);链式存储的队列：#include #define maxsize 40 /队列的最大长度#define queueelementtype int#define true 1#define false 0typedef structqueueelementtype elementmaxsize; /队列的元素空间 int front; int rear ; seqqueue;void initqueue(seqqueue * q) /将*q初始化为一个空的循环队列 q-front=q-rear=0; void print(seqqueue *q)int w; if(q-frontrear)for(w=q-front;wrear;w+)printf(%4d,q-elementw);if(q-frontq-rear)for(w=q-front;welementw);for(w=0;wrear;w+)printf(%4d,q-elementw);int enterqueue(seqqueue *q, queueelementtype x)/将元素x入队 if(q-rear+1)%maxsize=q-front) /队列已经满了 return(false);q-elementq-rear=x;q-rear=(q-rear+1)%maxsize; /重新设置队尾指针print(q);return(true); /操作成功int deletequeue(seqqueue *q, queueelementtype * x) /删除队列的队头元素，用x返回其值 if(q-front=q-rear) /队列为空 return(false); *x=q-elementq-front; q-front=(q-front+1)%maxsize; /重新设置队头指针 return(true); /操作成功int choose()int d;printf(1:插入队尾元素n);printf(2:删除队头元素n);printf(n);scanf(%d,&d);return d;void main()seqqueue q;int i,f,m,x,n=0; initqueue(&q); /将*q初始化为一个空的循环队列 while(!n) switch(choose() case 1: printf(请输入你要插入的数字n); scanf(%d,&i); f=enterqueue(&q, i); if(f) printf(插入成功n); else printf(队列已满n); break; case 2: printf(删除队列的队头元素是：); m=deletequeue(&q, &x); if(m) printf(%dn,x); else printf(删除失败n); print(&q); break;default :n=1; 五、完成情况和实验记录在完成这个实验的过程中计较麻烦，程序的结构的优化比较重要，选用case语句进行编程，条理会比较清晰，在算法上没有太大的创新。只要将有用的算法进行编写就能够是现实例的应用了。六、实验结果顺序栈结果：链栈结果：队列实验结果：实验三、二叉树的遍历一、实验目的1、掌握二叉树的特点及其存储方式。2、掌握二叉树的创建。3、掌握二叉树遍历的基本方法：前序、中序、后序。二、实验内容1、用前序方法建立一棵二叉树。2、编写前序遍历、中序遍历、后序遍历二叉树的程序。三、具体要求1.二叉树的二叉链表存储结构类型 typedef struct bitnode datatype data; struct bitnode *lchild ,*rchild ; bitnode，*bitree;2.建立下图所示的二叉树cabefd3.编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列4.统计以上二叉树中叶子结点的个数四、完成情况和实验记录1、这个程序主要是了解算法本身，不同的遍历顺序的算法是有区别的，我们可以在遍历的同时统计叶子节点的个数，还有比较重要的一点是，叶子节点的输入形式，由于数字和字母都有对应的码符，所以不能用他们来终止输入，而用的是结束符#号。而且在运行程序的时候要注意输入的格式，而且要先自己画图，看能否构成一颗二叉树。五、程序清单#include #include #include #define null 0 typedef struct bitnode char data; struct bitnode *lchild,*rchild; bitnode,*bitree; bitree create(bitree t) char ch; ch=getchar(); if(ch=#) t=null; else if(!(t=(bitnode *)malloc(sizeof(bitnode) printf(error!); t-data=ch; t-lchild=create(t-lchild); t-rchild=create(t-rchild); return t; void preorder(bitree t) if(t) printf(%c,t-data); preorder(t-lchild); preorder(t-rchild); void inorder(bitree t) if(t) inorder(t-lchild); printf(%c,t-data); inorder(t-rchild); void postorder(bitree t) if(t) postorder(t-lchild); postorder(t-rchild); printf(%c,t-data); int sumleaf(bitree t) int sum=0,m,n; if(t) if(!t-lchild)&(!t-rchild) sum+; m=sumleaf(t-lchild); sum+=m; n=sumleaf(t-rchild); sum+=n; return sum; void main() bitree t; int sum; t=create(t); printf(前序遍历为：); preorder(t); printf(中序遍历为：); inorder(t); printf(后序遍历为：); postorder(t);sum=sumleaf(t); printf(叶子节点个数为：%d,sum);五、输入的数据及所得结果：实验四、折半查找和二叉排序树一、实验目的1、掌握查找的特点。2、掌握折半查找的基本思想及其算法。3、熟悉二叉排序树的特点，掌握二叉排序树的插入、删除操作。二、实验内容和具体要求1、设有关键字序列k= 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35 ，查找key=21和key=25的数据元素。2、根据关键字序列45、24、53、12、37、93构造二叉排序树，并完成删除关键字53和24的操作。三、具体要求1、折半查找1、从键盘输入上述8个整数5 ,14 ,18 ,21 ,23 ,29 ,31 ,35，存放在数组bub8中，并输出其值。2、从键盘输入21，查找是否存在该数据元素，若存在，则输出该数据元素在表中的位置，否则给出查找失败的信息。3、从键盘输入25，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。2、二叉排序树1、二叉排序树结点定义typedef struct bitnode / 结点结构 telemtype data; struct bitnode *lchild, *rchild; / 左右孩子指针 bitnode, *bitree;2、从键盘上输入六个整数45、24、53、12、37、9构造二叉排序树3、输出其中序遍历结果。4、删除数据元素24，输出其中序遍历结果。5、删除数据元素53，输出其中序遍历结果。三、完成情况和实验记录这道题相对来说在程序方面这边较简单一点，以数组的形式来进行折半查找，并进行插入和删除操作。四、程序清单折半查找：# include # define n 8main()int i,number,top,bott,mid,loca,an,flag=1,sign=1;char c;printf(请输入一个有序数组:n);scanf(%d,&a0);i=1;while(iai-1)i+;elseprintf(enter this data again:);printf(n);for(i=0;in;i+)printf(%4d,ai);printf(n);flag=1;while(flag)printf(请输入查找元素:);scanf(%d,&number);loca=0;top=0;bott=n-1;if(numberan-1)loca=-1;sign = 1;while(sign=1)&(top=bott)mid=(bott+top)/2;if(number=amid)loca=mid;printf(找到 %d,它的位置是 %d n,number,loca+1);sign=0;else if(numberamid)bott=mid-1;elsetop=mid+1;if(sign=1|loca=-1)printf(%d 不能被找到。n,number);printf(继续查找吗(y/n)?);scanf( %c,&c);if(c=n|c=n)flag=0;二叉排序树：#include#include#includetypedef int keytype;typedef struct tree/声明树的结构 struct tree *left; /存放左子树的指针struct tree *right; /存放又子树的指针keytype key; /存放节点的内容 bstnode, * bstree; /声明二叉树的链表bstree insertbst(bstree tptr,keytype key)/ 在二叉排序树中插入结点 /若二叉排序树tptr中没有关键字为key的结点，则插入，否则直接返回bstree f,p=tptr; /p的初值指向根结点while(p) /查找插入位置，循环结束时，p是空指针，f指向待插入结点的双亲if(p-key=key) /树中已有key，无须插入return tptr;f=p; /f保存当前查找的结点，即f是p的双亲p=(keykey)?p-left:p-right; p=(bstree )malloc(sizeof(bstnode); /生成新结点p-key=key; p-left=p-right=null;if(tptr=null) /原树为空，新插入的结点为新的根tptr=p;elseif(keykey)f-left=p;elsef-right=p;return tptr;bstree createbst()/建立二叉树 bstree t=null; /根结点keytype key;cinkey;while(key!=-1)t=insertbst(t,key);cinkey;return t;void inorder_btree(bstree root)/ 中序遍历打印二叉排序树bstree p=root;if(p!=null) inorder_btree(p-left );cout keyright );int searchbst(bstree t,keytype key)/查找if(key=t-key)return 1;if(t=null)return 0;if(keykey)return searchbst(t-left,key);elsereturn searchbst(t-right,key);bstree deletebst(bstree tptr,keytype key)/删除 bstree p,tmp,parent=null; p=tptr; while(p) if(p-key=key) break; parent=p; p=(keykey)?p-left:p-right; if(!p) return null; tmp=p; if(!p-right&!p-left) /*p的左右子树都为空*/ if(!parent) /要删根，须修改根指针 tptr=null; else if(p=parent-right) parent-right=null; else parent-left=null; free(p); else if(!p-right) /p的右子树为空，则重接p的左子树 p=p-left; if(!parent) /要删根，须修改根指针 tptr=p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(!p-left) /的左子树为空，则重接p的左子树 p=p-right; if(!parent) /要删根，须修改根指针 tptr=p; else if(tmp=parent-left) parent-left=p; else parent-right=p; free(tmp); else if(p-right&p-left) /p有左子树和右子树，用p的后继覆盖p然后删去后继 /另有方法：用p的前驱覆盖p然后删去前驱|合并p的左右子树 parent=p; /由于用覆盖法删根，则不必特殊考虑删根 p=p-right; while(p-left) parent=p; p=p-left; tmp-key=p-key; if(p=parent-left) parent-left=null; else parent-right=null; free(p); return tptr;int main()keytype key;int flag,test;char cmd;bstree root;docouttt c.创建一棵二叉排序树n;couttt e.结束本程序n;flag=0;doif(flag!=0)coutcmd;flag+; while(cmd!=c&cmd!=c&cmd!=e&cmd!=e);if(cmd=c|cmd=c)cout请输入你所要创建的二叉树的结点的值，以-1结束：n;root=createbst();doflag=0;coutnn中序遍历二叉树：endl; inorder_btree(root);coutendl;couttt输入 d 删除你想要删除的结点endl;doif(flag!=0)cout选择操作错误！请重新选择！n;fflush(stdin);scanf(%c,&cmd);flag+;while(cmd!=d&cmd!=d);switch(cmd)case d:case d:coutkey;root=deletebst(root,key); /注意必须将值传回根if(root=null)coutn对不起，你所删除的结点 key 不存在!n;elsecoutn成功删除结点 key ;break;while(cmd!=q&cmd!=q);while(cmd!=e&cmd!=e);return 0;六、实验结果1.折半查找2.二叉排序树：实验五、内部排序一、实验目的1、掌握排序的有关概念和特点。2、熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。3、关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。二、实验内容 设有关键字序列k= 12 , 45 , 21 , 12 , 30 , 2 , 68 , 33 ,试用各种排序算法进行排序。三、具体要求 1、从键盘输入上述8个整数，存放在数组quick8