计算机软件技术基础上机报告.doc

软件开发技术实验指导书软件开发技术基础实验报告学院：自动化学院 班级：0831004班 学号：2010213157 姓名： 彭威威 目录n 软件开发技术基础1n 实验报告1n 实验一 线性表的操作（2学时）3n 实验二 栈的操作（3学时）7n 实验三 队列的操作（3学时）11n 实验四 树和二叉树的操作（3学时）18n 实验五 查找算法实现（2学时）22n 实验六 排序综合实验（3学时）26实验一 线性表的操作（2学时）班 级 0831004 学 号 2010213157 姓 名 彭威威 第 4 周 星 期 四1 、 2 节 成 绩 实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。二、实验要求：1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：1）建立一个线性表，首先依次输人整数数据元素（个数根据自己的需要键盘给定）2）删除指定位置的数据元素（指定元素位置通过键盘输入）再依次显示删除后的线性表中的数据元素。3）查找指定数据的数据元素（指定数据的大小通过键盘输入），若找到则显示位置，若没有找到就显示0。四、要求：1）采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。2）写出完整的程序并能调试通过即可五、实验原理：（1）线性表在顺序存储下的插入运算首先处理以下3种异常情况：当存储空间已满（n=m）时为“上溢”错误，不能进行插入，算法解释。 当in时认为在最后一个元素之后（第n+1个元素之前）插入。 当i1时认为在第一个元素之前插入。 从最后一个元素开始，直到第i个元素，其中每一个元素均往后一点一个位置。 最后将新元素插入到第i个位置，并将线性表的长度增加1。（2）线性表在顺序存储下的删除运算 首先出来以下2种异常情况： 当线性表为空（n=0）时为“上溢”错误，不能进行插入，算法结束。 当in时，认为在最后一个元素之后（第n+1个元素之前）插入。 从第i+1个元素开始，直到最后一个元素，其中每一个元素均一次往前移动一个 位置。 最后将线性表的长度减小1。（3）线性表在顺序存储下的查找运算将所要查找的数与线性表里面的数比较，当找到时输出其所在位置，否则输出0#includeusing namespace std;templateclass sq_LListprivate:int mm;int nn;T *v;public:sq_LList()mm=0;nn=0;return;sq_LList(int);void prt_sq_LList();void ins_sq_LList(int,T);int search_sq_LList(T);void del_sq_LList(int);/建立空顺序表templatesq_LList:sq_LList(int m)mm=m;v=new Tmm;nn=0;return;/顺序输出顺序表的长度和元素templatevoid sq_LList:prt_sq_LList()int i;coutnn=nnendl;for(i=0;inn;i+)coutviendl;return;/在顺序表的指定元素前插入元素templatevoid sq_LList:ins_sq_LList(int i,T b)int k;if(nn=mm)coutoverflow!nn)i=nn+1;if(i=i;k-)vk=vk-1;vi-1=b;nn=nn+1;return;/在顺序表中查找指定数据templateint sq_LList:search_sq_LList(T b)int i;for(i=0;inn;i+)if(vi=b)return i+1;return 0;/在顺序表中删除指定未指定的元素templatevoid 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;int main()int i,k,temp1,temp2,temp3;sq_LLists1(100);cout=endl;cout输入数据的个数k:k;cout=endl;cout输入k个整型数据元素:endl;for(i=1;itemp1;s1.ins_sq_LList(i,temp1);cout=endl;cout输出顺序表对象s1:endl;s1.prt_sq_LList();cout=endl;cout指定删除元素的位置:temp2;s1.del_sq_LList(temp2);cout再次输出顺序表对象s1:endl;s1.prt_sq_LList();cout=endl;cout输入要查找的数据:temp3;cout该数的位置为:s1.search_sq_LList(temp3)endl;return 0;实验二 栈的操作（3学时）班 级 0831004 学 号 2010213157 姓 名 彭威威 第 8 周 星 期 五7 、 8 节 成 绩 实验类型：验证性 实验要求：必修实验学时： 3学时一、实验目的：参照给定的栈类的程序样例，验证给出的栈的常见算法。二、实验要求：1、掌握栈的特点。掌握特殊线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 堆栈类测试和应用问题。要求： (1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为：依次把数据元素1,2,3,4,5入栈，然后出栈堆栈中的数据元素并在屏幕上显示。 (2)定义数据元素的数据类型为如下形式的结构体：typedef struct char taskname10;/任务名 int taskno;/任务号 DataType； 设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。四、要求1）栈的长度都由自己定；2）写出完整的程序并能调试通过即可。3)重点理解栈的算法思想，能够根据实际情况选择合适的存储结构。五、实验原理：链式堆栈类栈的初始化，即建立一个空栈的顺序存储空间入栈运算，是指在栈顶位置插入一个新元素退栈运算，即取出栈顶元素赋给一个指定的变量读栈顶元素，是指将栈顶元素赋给一个指定的变量链栈：#includeusing namespace std;templatestruct nodeT d;node *next;templateclass linked_Stackprivate:node *top;public:linked_Stack();void prt_linked_Stack();void ins_linked_Stack(T);int flag_linked_Stack();T del_linked_Stack();T read_linked_Stack();/链栈初始化templatelinked_Stack:linked_Stack()top=NULL;return;/检测链栈的状态templateint linked_Stack:flag_linked_Stack()if(top=0)return(0);return(1);/顺序输出栈中的元素templatevoid linked_Stack:prt_linked_Stack()node *p;p=top;if(p=NULL)coutStack empty!endl;return;docoutdnext;while(p!=NULL);return;/入栈templatevoid linked_Stack:ins_linked_Stack(T x)node *p;p=new node;p-d=x;p-next=top;top=p;return;/退栈templateT linked_Stack:del_linked_Stack()T y;node *q;if(top=NULL)coutStack empty!d;top=top-next;delete q;return(y);/读取栈顶元素templateT linked_Stack:read_linked_Stack()if(top=NULL)coutStack empty!d);int main()linked_Stacks;s.ins_linked_Stack(1);s.ins_linked_Stack(2);s.ins_linked_Stack(3);s.ins_linked_Stack(4);s.ins_linked_Stack(5);cout=endl;cout输出栈中的元素:endl;s.prt_linked_Stack();cout=endl;if(s.flag_linked_Stack()cout栈顶元素:s.read_linked_Stack()endl;if(s.flag_linked_Stack()cout退栈元素:s.del_linked_Stack()endl;if(s.flag_linked_Stack()cout退栈元素:s.del_linked_Stack()endl;if(s.flag_linked_Stack()cout退栈元素:s.del_linked_Stack()endl;cout=endl;cout再次输出栈中的元素:endl;s.prt_linked_Stack();return 0;实验三 队列的操作（3学时）班 级 0831004 学 号 2010213157 姓 名 彭威威 第 9 周 星 期 四9-11 节 成 绩 实验类型：验证性 实验要求：必修实验学时： 3学时一、实验目的：参照给定的队列类的程序样例，验证给出的队列的常见算法，并结合线性表类实现有关串的操作。二、实验要求：1、掌握队列、串的特点。掌握特殊线性表的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：队列类测试和应用问题。要求： 设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。四、要求：1）队列的长度都由自己定；2）写出完整的程序并能调试通过即可。3)重点理解队列和串的算法思想，能够根据实际情况选择合适的存储结构。 4)栈、队列的算法是后续实验的基础（树、图、查找、排序等）。五、实验原理：(1）、循环队列类 入队运算 首先判断循环队列是否满，当循环队列非空（算）且队尾指针等于排头指针时，说明循 环队列已满，不能进行入队运算。这种情况称为“上溢”，此时算法结束 然后敬爱那个队尾指针进一（rear=rear+1），并且置循环队列非空标志 最后将新元素插入到队尾指针指向的位置，并且置循环队列非空标志 退队运算 首先判断循环队列是否为空，当循环队列为空（s=0）时，不能进行腿肚运算。这种情况称为“下溢”，此时算法结束 然后将排头指针进一（front=front+1），并当front=m+1时置front=1 再将排头指针指向元素赋给指定的变量最后判断退队后循环队列是否为空。当front=rear时置循环队列空标志（s=0）(2）、带链队列 队列的初始化，建立一个空队列的顺序存储空间 入队运算，指在循环队列的队尾加入一个新元素 退队运算，在循环队列的派头位置退出一个元素并赋给指定的变量循环队列类：#includeusing namespace std;templateclass sq_Queueprivate:int mm;int front;int real;int s;T *q;public:sq_Queue(int);void prt_sq_Queue();void ins_sq_Queue(T);T del_sq_Queue();/建立空队列templatesq_Queue:sq_Queue(int m)mm=m;q=new Tmm;front=mm;real=mm;s=0;return;/输出排头与队尾指针以及队中的元素templatevoid sq_Queue:prt_sq_Queue()int i;coutfront=frontendl;coutreal=realendl;if(s=0)coutQueue emptyendl;return;i=front;doi=i+1;if(i=mm+1)i=1;coutqi-1endl;while(i!=real);return;/入队templatevoid sq_Queue:ins_sq_Queue(T x)if(s=1)&(real=front)coutQueue overflow!endl;return;real=real+1;if(real=mm+1)real=1;qreal-1=x;s=1;return;/退队templateT sq_Queue:del_sq_Queue()T y;if(s=0)coutQueue underflow!endl;return(0);front=front+1;if(front=mm+1)front=1;y=qfront-1;if(front=real)s=1;return(y);int main()sq_Queueq(5);cout=endl;cout输出排头与队尾指针以及队中的元素:endl;q.prt_sq_Queue();q.ins_sq_Queue(1);q.ins_sq_Queue(2);q.ins_sq_Queue(3);q.ins_sq_Queue(4);q.ins_sq_Queue(5);cout=endl;cout输出排头与队尾指针以及队中的元素:endl;q.prt_sq_Queue();cout=endl;cout输出退队元素:endl;coutq.del_sq_Queue()endl;coutq.del_sq_Queue()endl;coutq.del_sq_Queue()endl;cout=endl;cout再次输出排头与队尾指针以及队中的元素:endl;q.prt_sq_Queue();return 0;链式队列：#includeusing namespace std;templatestruct nodeT d;node *n;templateclass Qprivate:node*a;node*b;public:Q();void prt();int flag();void in(T);T del();/链队的初始化#includeusing namespace std;templatestruct nodeT d;node *n;templateclass Qprivate:node*a;node*b;public:Q();void prt();int flag();void in(T);T del();/链队的初始化templateQ:Q()a=NULL;b=NULL;return;/顺序输出队列中的元素templatevoid Q:prt()node*p;p=a;if(p=NULL)coutempty!endl;return;docoutdn;while(p!=NULL);return;/检测链队的状态templateint Q:flag()if(a=NULL)return(0);return(1);/入队templatevoid Q:in(T x)node*p;p=new node;p-d=x;p-n=NULL;if(b=NULL)a=p;elseb-n=p;b=p;return;/退队templateT Q:del()T y;node*q;if(a=NULL)coutempty!d;q=a;a=q-n;delete q;if(a=NULL)b=NULL;return(y);int main()Qq;q.in(1);q.in(2);q.in(3);q.in(4);q.in(5);cout=endl;cout输出带链队列中的元素:endl;q.prt();cout=endl;if(q.flag()cout输出退队元素:q.del()endl;if(q.flag()cout输出退队元素:q.del()endl;if(q.flag()cout输出退队元素:q.del()endl;cout=endl;cout再次输出带链队列中的元素:endl;q.prt();return 0;实验四 树和二叉树的操作（3学时）班 级 0831004 学 号 2010213157 姓 名 彭威威 第 10 周 星 期 日5-7 节 成 绩 实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。二、实验要求：1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1设计实现二叉树类，要求：（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。（2）实现二叉树层次遍历的非递归算法。 （3）编写一主函数来验证算法实现。 2. 假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。四、实验原理：（1）建立链式存储结构，输入给定二叉树及左右子树中的个结点值应按如下顺序：输入根结点值。若左子树不空，则输入左子树，否则输入一个结束符。若右子树不空，则输入右子树，否则输入一个结束符。（2）前序遍历是指：先访问根结点，然后遍历左子树，最后遍历右子树； 中序遍历是指：先遍历左子树，然后访问根结点，最后遍历右子树； 后序遍历是指：先遍历左子树，然后遍历右子树，最后访问根结点。（3）二叉树的前序遍历简单描述为： 访问根结点； 前序遍历左子树； 前序遍历右子树；（4）二叉树的中序遍历简单描述为： 中序遍历左子树； 访问根结点； 中序遍历遍历右子树； （5）二叉树的后序遍历的简单描述为： 后序遍历左子树 访问根结点； 后序遍历右子树；#includeusing namespace std;int i=0;templatestruct BT d;B *l;B *r;templateclass Trprivate:B *BT;public:Tr()BT=NULL;return;void cr(T);void in1();void in2();/生成二叉树templatevoid Tr:cr(T end)B *p;T x;cinx;if(x=end)return;p=new B;p-d=x;p-l=NULL;p-r=NULL;BT=p;Cr(p,1,end);Cr(p,2,end);return;templatestatic Cr(B *p,int k,T end)B*q;T x;cinx;if(x!=end)q=new B;q-d=x;q-l=NULL;q-r=NULL;if(k=1)p-l=q;if(k=2)p-r=q;Cr(q,1,end);Cr(q,2,end);return 0;/中序遍历templatevoid Tr:in1()B*p;p=BT;In1(p);coutendl;return;template static In1(B*p)if(p!=NULL)In1(p-l);coutdr);return 0;/中序遍历输出叶子templatevoid Tr:in2()B*p;p=BT;In2(p);coutendl;return;template static In2(B*p)if(p!=NULL)In2(p-l);In2(p-r);if(p-l=NULL)&(p-r=NULL)coutd ;i+;return 0;int main()Trb;cout=endl;cout输入各节点值(-1结束符):endl;b.cr(-1);cout=endl;cout中序序列:endl;b.in1();cout=endl;cout中序序列叶子:endl;b.in2();cout=endl;cout叶子数为:iendl;return 0;实验五 查找算法实现（2学时）班 级 0831004 学 号 2010213157 姓 名 彭威威 第 11 周 星 期 三7 、 8 节 成 绩 实验类型：验证性 实验要求：必修实验学时： 2学时一、实验目的：参照各种查找算法程序样例，验证给出的查找常见算法。 二、实验要求：1、掌握各种查找算法的特点，测试并验证查找的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容：1. 建立有序表，采用折半查找实现某一已知的关键字的查找。2利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。#includeusing namespace std;templateclass sprivate:int a;int b;T *v;public:s()a=0;b=0;return;s(int);int se(T);int in(T);void prt();/顺序表初始化templates:s(int c)a=c;v=new Ta;b=0;return;/查找指定的元素templateint s:se(T x)int i,j,k;i=1;j=b;while(ix)i=k+1;elsej=k-1;return(-1);/插入元素templateint s:in(T x)int k;if(a=b)coutoverflow!endl;return(-1);k=b;while(vk=0)vk+1=vk;k=k-1;vk+1=x;b=b+1;return(1);/顺序输出元素templatevoid s:prt()int i;for(i=0;ib;i+)coutviendl;return;int main()int i,n,m,p;ss1(10);cout=endl;cout顺序表s1从大到小输入7到1:endl;for(i=1;in;s1.in(n);cout=endl;cout第1次输出顺序表对象s1:endl;s1.prt();cout=endl;cout输入要查找的数:m;cout数的位置是:s1.se(m)endl;cout=endl;cout插入一个数:p;s1.in(p);cout=endl;cout第2次输出顺序表对象s1:endl;s1.prt();return 0;实验六 排序综合实验（3学时）班 级 0831004 学 号 2010213157 姓 名 彭威威 第 12 周 星 期 五7 、 8 节 成 绩 实验类型：综合性 实验要求：必修实验学时： 3学时一、实验目的：参照各种排序算法程序样例，验证给出的排序常见算法。 二、实验要求：1、掌握各种排序算法的特点，测试并验证排序的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 输入一组关键字序列分别实现下列排序: 1.实现简单选择排序、直接插入排序和冒泡排序。 2.实现希尔排序算法。 3.实现快速排序算法（取第一个记录或中间记录作为基准记录）。 4.快速排序的非递归算法。 把上述几种排序的算法编写成菜单，根据输入的数字不同执行对应的排序算法。#include#includeusing namespace std;/冒泡排序templatevoid 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=