资源描述：
《打印 软件开发技术基础 实验报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
《软件开发技术基础》实验总报告班级：0830902学号：09212666学生：唐海东2010年11月13日 《软件开发技术基础》实验报告实验名称：实验一线性表的操作班级0830902学号2009212666姓名唐海东第四周星期一、9—10节成绩实验目的：参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法实验内容：设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：1）建立一个线性表，首先依次输人整数数据元素（个数根据自己的需要键盘给定）2）删除指定位置的数据元素（指定元素位置通过键盘输入）再依次显示删除后的线性表中的数据元素。3）查找指定数据的数据元素（指定数据的大小通过键盘输入），若找到则显示位置，若没有找到就显示0。实验要求： （1）将程序输入计算机，编译运行。（2）程序的实际功能与上述所列功能不完全相符，调试程序，找出问题所在，并纠正。实验原理：⑴生成线性表：定义一维数组表示线性表的存储空间，动态申请存储空间建立长度为mm的空顺序表⑵向顺序表中插入数据元素：检测顺序表的状态，若表存储空间已满则提示上溢错误；若否，判断插入数据位置是否大于原来顺序表中最后一个数据位置，若真则默认在最后一个元素之后插入，若假判断插入位置是否小于原来顺序表中第一个位置，若真则默认在第一个位置插入，将指定位置处后面的所有元素从后之前分别后移一个位置，将要插入的数据元素插入到指定位置，表实际长度n加1⑶删除指定位置的数据元素：检测顺序表的状态，若表实际长度为0，则提示下溢错误，若指定位置小于1或大于表实际长度n，则提示没有该元素，若否，从指定位置起，其后元素顺次前移一个位置，表实际长度n减1⑷查找指定数据的数据元素：检测顺序表的状态，若表为空，则提示空表，若否，则顺序比较指定数据与表中数据大小，若相等，则返回表中数据位置，跳出循环；若直到表尾仍未找到与指定数据相匹配的表中元素，则提示表中无该元素显示0。 实验步骤：首先建立顺序表，依次向顺序表中输入数据元素，让顺序表实现删除功能，输入指定元素，让顺序表实现查找功能。实验结果：见源程序后附：源程序和输入对应数据以及对应输出结果。源程序：#includeusingnamespacestd;templateclasssq_List{private:intmm;intnn;T*v;public:sq_List(){mm=0;nn=0;return;}sq_List(int);voidprt_sq_List();intflag_sq_List();voidins_sq_List(int);voiddel_sq_List(int);intsch_sq_List(T);};templatesq_List::sq_List(intm){mm=m;v=newT[mm];nn=0;return;}templatevoidsq_List::prt_sq_List(){inti;cout<<"nn="<intsq_List::flag_sq_List() {if(nn==mm)return(-1);if(nn==0)return(0);return(1);}templatevoidsq_List::ins_sq_List(inti){intk;Tx;for(k=0;k>x;v[k]=x;nn++;}return;}templatevoidsq_List::del_sq_List(inti){intk;if(nn==0){cout<<"underflow!"<nn)){cout<<"Notthiselementinthelist!"<intsq_List::sch_sq_List(Tx){if(nn==0)cout<<"blanklist"<s(10);inti,j,x;cout<<"第1次输出表中对象:"<>i;s.ins_sq_List(i);cout<<"第2次输出表中对象:"<>j;for(intk=0;k>i;s.del_sq_List(i);}cout<<"第3次输出表中对象:"<>x;i=s.sch_sq_List(x);if(i==-1)cout<<"表中没有此元素!"<usingnamespacestd;typedefstruct{chartaskname[10];inttaskno;}DT;template classflag{private:intmm;inttop;T*DT_var;public:voidinput_flag();flag(int);voidpri_flag();intsearch_flag();voidins_flag(T);Tdel_flag();Tread_flag();};templateflag::flag(intm){mm=m;DT_var=newT[mm];top=0;return;}templatevoidflag::pri_flag(){inti;cout<<"top="<intflag::search_flag(){if(top==mm)return(-1);if(top==0)return(0);return(1);}templatevoidflag::ins_flag(Tx){if(top==mm){cout<<"上溢错误！"<Tflag::del_flag(){Ty;if(top==0){cout<<"下溢错误！"<Tflag::read_flag(){if(top==0){cout<<"栈为空！"<voidflag::input_flag(){inti;for(i=0;i<5;i++){cout<<"inputtaskname";cin>>DT_var[i].taskname;cout<<"inputtaskno";cin>>DT_var[i].taskno;top++;}}intmain(intargc,char*argv[]){flags(5); s.input_flag();cout<<"输出栈顶指针与栈中的元素："<usingnamespacestd;templateclasssq_Queue{private:intmm;intfront;intrear;ints; T*q;public:sq_Queue(int);voidprt_sq_Queue();intflag_sq_Queue();voidins_sq_Queue(T);Tdel_sq_Queue();};templatesq_Queue::sq_Queue(intm){mm=m;q=newT[mm];front=mm;rear=mm;s=0;return;}templatevoidsq_Queue::prt_sq_Queue(){inti;cout<<"front="<intsq_Queue::flag_sq_Queue(){if((s==1)&&(rear=front))return(-1);if(s==0)return(0);return(1);}templatevoidsq_Queue::ins_sq_Queue(Tx){if((s==1)&&(rear==front)){cout<<"Queue_overflow!"<Tsq_Queue::del_sq_Queue(){Ty;if(s==0){cout<<"Queue_underflow!"<q(5);cout<<"输出排头与队尾指针以及队中元素："<usingnamespacestd;templatestructnode{Td;node*next;};templateclasslinked_Queue{private:node*front;node*rear;public:linked_Queue();voidprt_linked_Queue();intflag_linked_Queue();voidins_linked_Queue(T);Tdel_linked_Queue();};templatelinked_Queue::linked_Queue(){front=NULL;rear=NULL;return; }templatevoidlinked_Queue::prt_linked_Queue(){node*p;p=front;if(p==NULL){cout<<"空队列！"<d<next;}while(p!=NULL);return;}templateintlinked_Queue::flag_linked_Queue(){if(front==NULL)return(0);return(1);}templatevoidlinked_Queue::ins_linked_Queue(Tx){node*p;p=newnode;p->d=x;p->next=NULL;if(rear==NULL)front=p;elserear->next=p;rear=p;return;}templateTlinked_Queue::del_linked_Queue(){Ty;node*q;if(front==NULL){cout<<"空队！"<d;q=front;front=q->next;deleteq;if(front==NULL)rear=NULL;return(y);} intmain(intargc,char*argv[]){linked_Queueq;q.ins_linked_Queue(1);q.ins_linked_Queue(2);q.ins_linked_Queue(3);q.ins_linked_Queue(4);q.ins_linked_Queue(5);cout<<"输出带链队列中的元素:"<#definestacksize10usingnamespacestd;templatetypedefstructsqstack/*栈的存储结构*/{intdata[stacksize];inttop;}SqStackTp;structLqueueTp/*队列的存储结构*/{intdata;LqueueTp*next;};/*typedefstructqueueptr{LqueueTp*front,*rear;}QueptrTp;*/templateclassQueue{private:intmm;inttop;T*data;public:Queue(int);intflag_Queue();voidins_Queue(T); voiddepart();Tdel_Queue();//Tread_Queue();};templateclasslinked_Que{private:LqueueTp*front;LqueueTp*rear;public:linked_Que();intflag_linked_Que();voidins_linked_Que(T);Tdel_linked_Que;};templatelinked_Que::linked_Que(){front=NULL;rear=NULL;return;}templateQueue::Queue(intm){mm=m;data=newSqStackTp[mm];top=0;return;}templateintQueue::flag_Queue(){if(top==mm)return(-1);if(top==0)return(0);return(1);}template intlinked_Que::flag_linked_Que(){if(front==NULL)return(0);return(1);}templatevoidQueue::ins_Queue(Tx){if(top==mm){cout<<"Stackoverflow!"<voidlinked_Que::ins_linked_Que(Tx){LqueueTp*p;p=newLqueueTp;p->data=x;p->next=NULL;if(rear==NULL)front=p;elserear->next=p;rear=p;return;}templateTQueue::del_Queue(){Ty;if(top==0){cout<<"Stackunderflow!"< Tlinked_Que::del_linked_Que(){Ty;LqueueTp*q;if(front==NULL){cout<<"NoList!"<data;q=front;front=q->next;deleteq;if(front==NULL)rear=NULL;return(y);}/*templateTQueue::read_Queue(){if(top==0){cout<<"Stackempty!"<voidpark(){Queues1(stacksize);linked_Ques2(stacksize);intx,i;cin>>x;if(x){i=s1.flag_Queue();if(i==1){s1.ins_Queue(x);}else{s2.ins_linked_Que(x);}}elsereturn;} templatevoidQueue::depart(){Queuep1(stacksize);Queuep2(stacksize);linked_Ques(stacksize);SqStackTp*p;p=newSqStackTp[mm];inti,x;for(i=0;is1(stacksize);//linked_Ques2(stacksize);chara;cin>>a;if(a=='A'){s1.park();cin>>a;}elseif(a=='B'){s1.depart();cin>>a;}return(0);心得体会：本程序中，栈采用顺序存储结构，队列用链式存储结构。设计起来比较方便，小心点就行。 《软件开发技术基础》实验报告实验名称：实验四树和二叉树的操作班级0830902学号2009212666姓名唐海东第八周星期一、9-11节成绩实验目的：参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。实验内容：1．设计实现二叉树类，要求：编写一个程序，输入二叉树的先序遍历序列，创建二叉链表，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息。2.假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计结点个数。实验要求：1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。实验原理：⑴输入二叉树的先序遍历：定义二叉树的左右节点，给二叉链表初始化BT=NULL，动态申请二叉树根节点p，通过递归调用给p增加左节点值和右节点值⑵前序遍历二叉树：首先判断二叉树是否为空，若为空，则返回；若否，先访问根节点，前序遍历左子树，前序遍历右子树，前序遍历左右子树时仍采用前序遍历的方法⑶中序遍历二叉树：首先判断二叉树是否为空，若为空，则返回；若否，先中序遍历左子树，访问根节点，中序遍历右子树，前序遍历左右子树时仍采用中序遍历的方法⑷后序遍历二叉树：首先判断二叉树是否为空，若为空，则返回；若否，先后序遍历左子树，后序遍历右子树，访问根节点，前序遍历左右子树时仍采用后序遍历的方法 ⑸输出二叉树的所有叶子节点：选择前或中、后序中的一种方法遍历二叉树，当其没有后件时即为叶子节点，输出相应的节点值⑹统计二叉树结点个数：任选一种遍历方式，统计所有节点数实验步骤：1.建立二叉树，输入二叉树的先序遍历，分别采用前、中、后序三种方式遍历二叉树。2.采用链式存储方式建立一个二叉树，统计其节点数并输出其叶子节点的数值。实验结果：见源程序后。附：源程序和输入对应数据以及对应输出结果。源程序如下：1：（编写一个程序，输入二叉树的先序遍历序列，创建二叉链表，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息。）#includeusingnamespacestd;templatestructBtnode{Td;Btnode*lchild;Btnode*rchild;};templateclassBinary_Tree{private:Btnode*BT;public:Binary_Tree(){BT=NULL;return;}voidcreat_Binary_Tree(T);voidpretrav_Binary_Tree();voidintrav_Binary_Tree();voidpostrav_Binary_Tree();};templatevoidBinary_Tree::creat_Binary_Tree(Tend){Btnode*p;Tx;cin>>x;if(x==end)return; p=newBtnode;p->d=x;p->lchild=NULL;p->rchild=NULL;BT=p;creat(p,1,end);creat(p,2,end);return;}templatestaticcreat(Btnode*p,intk,Tend){Btnode*q;Tx;cin>>x;if(x!=end){q=newBtnode;q->d=x;q->lchild=NULL;q->rchild=NULL;if(k==1)p->lchild=q;if(k==2)p->rchild=q;creat(q,1,end);creat(q,2,end);}return0;}templatevoidBinary_Tree::pretrav_Binary_Tree(){Btnode*p;p=BT;pretrav(p);cout<staticpretrav(Btnode*p){if(p!=NULL){cout<d<<"";pretrav(p->lchild);pretrav(p->rchild);}return0;}templatevoidBinary_Tree::intrav_Binary_Tree(){Btnode*p;p=BT;intrav(p); cout<staticintrav(Btnode*p){if(p!=NULL){intrav(p->lchild);cout<d<<"";intrav(p->rchild);}return0;}templatevoidBinary_Tree::postrav_Binary_Tree(){Btnode*p;p=BT;postrav(p);cout<staticpostrav(Btnode*p){if(p!=NULL){postrav(p->lchild);postrav(p->rchild);cout<d<<"";}return0;}intmain(intargc,char*argv[]){Binary_Treeb;cout<<"输入各结点值（－1为结束符值）："<usingnamespacestd;templatestructBtnode{Td;Btnode*lchild;Btnode*rchild;};templateclassBinary_Tree{private:Btnode*BT;public:Binary_Tree(){BT=NULL;return;}voidcreat_Binary_Tree(T);voidcount_Binary_Tree();};templatevoidBinary_Tree::creat_Binary_Tree(Tend){Btnode*p;Tx;cin>>x;if(x==end)return;p=newBtnode;p->d=x;p->lchild=NULL;p->rchild=NULL;BT=p;creat(p,1,end);creat(p,2,end);return;}templatestaticcreat(Btnode*p,intk,Tend) {Btnode*q;Tx;cin>>x;if(x!=end){q=newBtnode;q->d=x;q->lchild=NULL;q->rchild=NULL;if(k==1)p->lchild=q;if(k==2)p->rchild=q;creat(q,1,end);creat(q,2,end);}return0;}templatevoidBinary_Tree::count_Binary_Tree(){Btnode*p;intn;p=BT;n=count(p);cout<staticcount(Btnode*p){staticinti=0;if(p!=NULL){if((p->lchild==NULL)&&(p->rchild==NULL))cout<<"叶子节点为"<d<<"";else{count(p->lchild);count(p->rchild);}i++;}returni;}intmain(intargc,char*argv[]){Binary_Treeb;cout<<"输入各结点值（－1为结束符值）："<usingnamespacestd; templateclassSL_List{private:intmm;intnn;T*v;public:SL_List(){mm=0;nn=0;return;}SL_List(int);intsearch_SL_List(T);intinsert_SL_List(T);voidprt_SL_List();};templateSL_List::SL_List(intm){mm=m;v=newT[mm];nn=0;return;}templateintSL_List::search_SL_List(Tx){inti,j,k;i=1;j=nn;while(i<=j){k=(i+j)/2;if(v[k-1]==x)return(k-1);if(v[k-1]>x)j=k-1;elsei=k+1;}return(-1);}templateintSL_List::insert_SL_List(Ty){for(inti=0;i>x;while(v[k]>x){v[k+1]=v[k];k=k-1;}v[k+1]=x;nn=nn+1;}return(1);}templatevoidSL_List::prt_SL_List(){inti;cout<<"nn="<s(5);intx,a;cout<<"输入有序对象:";s.insert_SL_List(5);cout<<"输出有序对象s:"<>x;if((a=s.search_SL_List(x))!=-1){cout<usingnamespacestd; templateclassSL_List{private:intmm;intnn;T*v;public:SL_List(){mm=0;nn=0;return;}SL_List(int);intsearch_SL_List(T);intinsert_SL_List(T);intinput_SL_List(T);voidprt_SL_List();};templateSL_List::SL_List(intm){mm=m;v=newT[mm];nn=0;return;}templateintSL_List::input_SL_List(Ty){for(inti=0;i>x;while(v[k]>x){v[k+1]=v[k];k=k-1;}v[k+1]=x;nn=nn+1;}return(1);}templateintSL_List::insert_SL_List(Tx){intk; if(nn==mm){cout<<"上溢!"<x){v[k+1]=v[k];k=k-1;}v[k+1]=x;nn=nn+1;return(1);}templatevoidSL_List::prt_SL_List(){inti;cout<<"nn="<s(20);intx;cout<<"输入有序对象:";s.input_SL_List(5);cout<<"输出有序对象s:"<>x;s.insert_SL_List(x);cout<<"再次输出有序对象s:"<#includeusingnamespacestd;templatevoidinsort(Tp[],intn){intj,k;Tt;for(j=1;j=0)&&(p[k]>t)){p[k+1]=p[k];k=k-1;}p[k+1]=t;}return;}templatevoidbub(Tp[],intn){intm,k,j,i;Td;k=0;m=n-1; while(kp[i+1]){d=p[i];p[i]=p[i+1];p[i+1]=d;m=I;}j=k+1;k=0;for(i=m;i>=j;i--)if(p[i-1]>p[i]){d=p[i];p[i]=p[i-1];p[i-1]=d;k=i;}}return;}templatevoidqck(Tp[],intn){intm,i;T*s;if(n>10){i=splist(p,n);qck(p,i);s=p+(i+1);m=n-(i+1);qck(s,m);}return;}templatestaticintsplist(Tp[],intn){inti,j,k,l;Tt;i=0;j=n-1;k=(i+j)/2;if((p[i]>=p[j])&&(p[j]>=p[k]))l=k;elseif((p[i]>=p[k])&&(p[k]>=p[j]))l=k;elsel=i;t=p[l];p[l]=p[i];while(i!=j){ while((i=t))j=j-1;if(ivoidmerge(Tp[],intn){intm,k,j,low,high,mid;T*a;a=newT[n];m=1;while(mn)high=n;if(high>mid)merg(p,low,mid,high,a);}m=k;}deletea;return;}templatestaticmerg(Tp[],intlow,intmid,inthigh,Ta[]){inti,j,k; i=low;j=mid+1;k=low;while((i<=mid)&&(j<=high)){if(p[i-1]<=p[j-1]){a[k-1]=p[i-1];i=i+1;}else{a[k-1]=p[j-1];j=j+1;}k=k+1;}if(i<=mid)for(j=i;j<=mid;j++){a[k-1]=p[j-1];k=k+1;}elseif(j<=high)for(i=j;i<=high;i++){a[k-1]=p[i-1];k=k+1;}for(i=low;i<=high;i++)p[i-1]=a[i-1];return(0);}templatevoidhap(Tp[],intn){inti,mm;Tt;mm=n/2;for(i=mm-1;i>=0;i--)sift(p,i,n-1);for(i=n-1;i>=1;i--){t=p[0];p[0]=p[i];p[i]=t;sift(p,0,i-1);}return;}template staticsift(Tp[],inti,intn){intj;Tt;t=p[i];j=2*(i+1)-1;while(j<=n){if((jvoidprint(Tp[]){for(inti=0;i<10;i++){for(intj=0;j<5;j++)cout<>a;switch(a){case1:{insort(p+10,30);cout<<"直接插入排序法排序后的序列："<>a;}case2:{bub(p+10,30);cout<<"冒泡排序法排序后的序列："<>a;}case3:{qck(p+10,40);cout<<"快速排序法排序后的序列："<>a;}case4:{merge(p,50);cout<<"快速排序法(非递归)排序后的序列："<>a;}case5:{hap(p+10,40);cout<<"堆排序法排序后的序列："<>a;}default:{cout<<"输入错误，请重新选择：";cin>>a;}}return0;}运行结果1如下： 运行结果2如下： 运行结果3如下： 运行结果4如下： 运行结果5如下： 运行结果6：心得体会：这个程序要求输入一组关键字序列分别实现下列排序:实现直接插入排序；实现冒泡排序算法；实现快速排序算法（取第一个记录或中间记录作为基准记录）；快速排序的非递归算法；堆排序。把上述几种排序的算法编写成菜单，根据输入的数字不同执行对应的排序算法。 掌握各种排序算法的特点，测试并验证排序的常见算法。这个程序比较多，是我和同学一起输入的。在调试阶段也向老师请教关于选择的问题。总之这次实验获得了很多知识。
