软件开发技术基础的实验报告.doc

软件开发技术基础实验报告软件开发技术基础实验报告 姓名： 学号： 班级： 实验一 线性表的操作（2学时）实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。二、实验要求：1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：1）建立一个线性表，首先依次输人整数数据元素（个数根据自己的需要键盘给定）2）删除指定位置的数据元素（指定元素位置通过键盘输入）再依次显示删除后的线性表中的数据元素。3）查找指定数据的数据元素（指定数据的大小通过键盘输入），若找到则显示位置，若没有找到就显示0。四、要求1）采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。2）写出完整的程序并能调试通过即可源程序如下：#include using namespace std;template class sq_LListprivate:int mm;int nn;T *v;public:sq_LList()mm=0;nn=0;return;sq_LList(int);void prt_sq_LList();int flag_sq_LList();void ins_sq_LList(int,T);void del_sq_LList(int); int search_sq_LList(T x);template sq_LList:sq_LList(int m)mm=m;v=new Tmm;nn=0;return;template void sq_LList:prt_sq_LList()int i;coutnn=nnendl;for(i=0;inn;i+)coutviendl;return;template int sq_LList:flag_sq_LList()if(nn=mm)return(-1);if(nn=0)return(0);return(1);template void sq_LList:ins_sq_LList(int i,T b)int k;if(nn=mm)coutoverflownn)i=nn+1;if(i=i;k-)vk=vk-1;vi-1=b;nn=nn+1;return;template void sq_LList:del_sq_LList(int i)int k;if(nn=0)coutunderflow!endl;return;if(inn)coutNot this element in the list!endl;return;for(k=i;knn;k+)vk-1=vk;nn=nn-1;return;template int sq_LList:search_sq_LList(T x)int i,j,k;i=1;j=nn;while(i=j)k=(i+j)/2;if(vk-1=x)cout你要查找的数现在的位置为:(k-1)x)j=k-1;else i=k+1;return(0);int main()int y;sq_LList a(100);cout第一次输出顺序表对象a:endl;a.prt_sq_LList();a.ins_sq_LList(1,1);a.ins_sq_LList(2,3);a.ins_sq_LList(3,5);a.ins_sq_LList(4,7);a.ins_sq_LList(5,9);a.ins_sq_LList(6,11);cout第二次输出顺序表对象a:endl;a.prt_sq_LList();a.del_sq_LList(2);cout第三次输出顺序表对象a:endl;a.prt_sq_LList();cout请输入要查找的数:y;coutendl;a.search_sq_LList(y);cout第四次输出顺序表对象a:endl;a.prt_sq_LList();return 0;运行结果如下：心得体会：1. 通过本次试验，我掌握了线性表的基本概念。2.通过本次试验，我懂得了如何建立一个顺序表，并能对顺序表进行基本的建立、插入、检测、删除以及查找的操作。3.本次试验我知道了线性表的顺序存储结构具有如下两个特点：（1） 线性表中所有元素所占的存储空间是连续的。（2） 线性表中各元素在存储空间中是按逻辑顺序依次存放的。实验二 栈、队列的操作实验目的：参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。实验内容：实验要求：1 掌握栈、队列、串的特点。掌握特殊线性表的常见算法。2 提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。3. 栈和队列的长度都由自己定；4. 写出完整的程序并能调试通过即可。5 重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。6 栈、队列的算法是后续实验的基础（树、图、查找、排序等）。实验原理：1. 堆栈类测试和应用问题。要求： 定义数据元素的数据类型为如下形式的结构体：typedef struct char taskname10;/任务名 int taskno;/任务号 DataType； 设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。2. 队列类测试和应用问题。要求： 设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。#includeusing namespace std;/stack-begin#define stacksize 5typedef struct char taskname10;/任务名 int taskno;/任务号DataType;class stackprivate:int top;DataType taskstacksize;public:bool init();bool empty();bool push(DataType d);bool pop(DataType &d);bool stack:init()top=0;int i;for(i=0;i0?false:true;bool stack:push(DataType d)if(top=stacksize) return false;strcpy(tasktop.taskname,d.taskname);tasktop.taskno=d.taskno;top+;return true;bool stack:pop(DataType &d)if(topnext=new queue_node(d);rear=rear-next;return true;bool queue:dequeue(int &d)if(front=rear) return false;queue_node *p=front-next;d=p-data;front-next=p-next;if(p=rear)rear=front;delete p;return true;/queue-end#define queuesize 10class sqqueueprivate:int * base;int front;int rear;public:bool init();bool enqueue(int d);bool dequeue(int &d);bool sqqueue:init()base=(int *)malloc(queuesize*sizeof(int);if(!base) return false;front=rear=0;return true;bool sqqueue:enqueue(int d)if(rear+1)%queuesize=front) return false;baserear=d;rear=(rear+1)%queuesize;return true;bool sqqueue:dequeue(int &d)if(front=rear) return false;d=basefront;front=(front+1)%queuesize;return true;void main()DataType dd5,tt;char tn=任务a;int i;for(i=0;i5;i+)strcpy(ddi.taskname,tn);tn4+;ddi.taskno=i+1;stack mystack;mystack.init();for(i=0;i5;i+)mystack.push(ddi);cout入栈完成，按回车键继续;getchar();while(mystack.pop(tt)couttt.taskname tt.tasknoendl;cout出栈完成，按回车键继续;getchar();queue myqueue;myqueue.init();for(i=0;i5;i+)myqueue.enqueue(i+1);cout链队入队完成，按回车键继续;getchar();for(;myqueue.dequeue(i);)coutiendl;cout链队出队完成，按回车键继续;getchar(); sqqueue mysqqueue;mysqqueue.init();for(i=0;i5;i+)mysqqueue.enqueue(i+1);cout循环队列入队完成，按回车键继续;getchar();for(;mysqqueue.dequeue(i);)coutiendl; cout循环队列出队完成，按回车键退出;getchar(); 实验步骤：实验结果：实验三 查找算法实现（2学时）实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照各种查找算法程序样例，验证给出的查找常见算法。 二、实验要求：1、掌握各种查找算法的特点，测试并验证查找的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：1. 建立有序表，采用折半查找实现某一已知的关键字的查找。2利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。源程序如下：#include using namespace std;template class sL_Listprivate:int mm;int nn;T *v;public:sL_List()mm=0;nn=0;return;sL_List(int);int search_sL_List(T);int insert_sL_List(int,T);void prt_sL_List();template sL_List:sL_List(int m)mm=m;v=new Tmm;nn=0;return;template int sL_List:search_sL_List(T x)int i,j,k;i=1;j=nn;while(ix)j=k-1;else i=k+1;return(-1);template int sL_List:insert_sL_List(int p,T x)if(nn=mm)cout溢出！x)vp+1=vp;p=p-1;vp+1=x;nn=nn+1;return(1);template void sL_List:prt_sL_List()int i;for(i=0;inn;i+)coutviendl;return;int main()int k,t,q,result;int a20=10,20,30,40,50,60,70,80;sL_Lists(20);for(k=0;k8;k+)s.insert_sL_List(k+1,ak);cout输出有序对象s:endl;s.prt_sL_List();cout请输入要查找的数:t;coutendl;cout你要查找的数在数组中的位置为:endl;result=s.search_sL_List(t);coutresultendl;cout请插入一个元素:q;coutendl;s.insert_sL_List(k+1,q);cout插入后有序表变为:endl;s.prt_sL_List();return 0;实验结果如下：心得体会：1. 通过这次试验，我知道了一些查找的基本方法，并且了解了折半查找的典型方法及技巧。2. 并且我掌握了利用折半法插入一个元素的方法。3. 常见问题在于在插入位置时，易混淆位置与数值的关系，以及c+中的一些基本定义方法易忘记。实验四 排序综合实验（3学时）实验类型：综合性 实验要求：必修实验学时： 3学时一、实验目的：参照各种排序算法程序样例，验证给出的排序常见算法。 二、实验要求：1、掌握各种排序算法的特点，测试并验证排序的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 输入一组关键字序列分别实现下列排序: 1.实现直接插入排序； 2.实现冒泡排序算法； 3.实现快速排序算法（取第一个记录或中间记录作为基准记录）；4.快速排序的非递归算法；5. 堆排序。 把上述几种排序的算法编写成菜单，根据输入的数字不同执行对应的排序算法。源程序如下：#include using namespace std;/实现简单插入排序template void insort(T p,int n)int j,k;T t;for(j=1;j=0)&(pkt)pk+1=pk;k=k-1;pk+1=t;return;/实现冒泡排序template void bub(T p,int n)int m,k,j,i;T d;k=0;m=n-1;while(km)j=m-1;m=0;for(i=k;ipi+1)d=pi;pi=pi+1;pi+1=d;m=i;j=k+1;k=0;for(i=m;i=j;i-)if(pi-1pi)d=pi;pi=pi-1;pi-1=d;k=i;return;/实现快速排序template void qck(T p,int n)int m,i;T *s;if(n10)i=split(p,n);qck(p,i);s=p+(i+1);m=n-(i+1);qck(s,m);elsebub(p,n);return;template static int split(T p,int n)int i,j,k,l;T t;i=0;j=n-1;k=(i+j)/2;if(pi=pj)&(pj=pk)l=j;else if(pi=pk)&(pk=pj)l=k;elsel=i;t=pl;pl=pi;while(i!=j)while(i=t)j=j-1;if(ij)pi=pj;i=i+1;while(ij)&(pi=t)i=i+1;if(ij)pj=pi;j=j-1;pi=t;return(i);/实现堆排序template void hap(T p,int n)int i,mm;T t;mm=n/2;for(i=mm-1;i=0;i-)sift(p,i,n-1);for(i=n-1;i=1;i-)t=p0;p0=pi;pi=t;sift(p,0,i-1);return;template static sift(T p,int i,int n)int j;T t;t=pi;j=2*(i