计算机软件基础实验报告

《计算机软件基础》实验报告《计算机软件基础》实验报告姓名：沈俊卫学号：1145533129班级：11电气1班专业：电气工程及其自动化学院：电气与信息工程学院2013年12月《计算机软件基础》实验报告-1-实验一线性表的插入和删除一、实验目的1.熟悉C++上机环境；2.掌握线性表的基本操作：查找、插入、删除等运算在链接存储结构上的运算。二、实验内容【任务一】阅读理解阅读后面的程序，并将其输入到计算机中，调试成功，运算出结果。这个程序中我们创建了一个整数类型的升序单，演示了单链表的创建、输出和删除操作。【任务二】完善功能构造函数node*insert(node*head,intnum)，实现把一个节点插入链表，仍保持链表上各节点的升序关系，并在主函数中完成对你所添加函数的测试。三、算法描述建立含有若干个元素的升序单链表，对其进行插入、删除等操作，并将结果在屏幕上输出。//实验一线性表#includestdafx.hconstintSIZE0=2;constintSTEP=1;structList{int*A,len,size;List(){A=(int*)malloc(SIZE0*sizeof(int));if(!A)exit(1);len=0;size=SIZE0;}~List(){delete[size]A;}intGetLen();voidOutput();intInsert(intloc,intx);intDelete(intloc,int&y);intGeti(intloc,int&y);List(int*p,intn);voidStraightInsertSort();voidBinaryInsertSort();voidBubbleSort();intPatation(intlow,intup);voidQuickSort(intlow,inthigh);voidSelectSort();voidShift_down(intheapsize,intindex);voidDeleteNodeofHeap(intheapsize,intindex);voidcreateHeap();《计算机软件基础》实验报告-2-voidHeapSort();voidShellInsert(intdk);voidShellSort(int*delta,intt);};List::List(int*p,intn){A=newint[n];for(inti=0;in;i++)A[i]=p[i];len=size=n;};//简单选择排序voidList::SelectSort(){inti,j,temp,max;for(i=len-1;i0;i--){max=0;for(j=1;j=i;j++)if(A[j]A[max])max=j;temp=A[i];A[i]=A[max];A[max]=temp;cout第len-i趟的结果为...\n;this-Output();coutendl;}}//将当前A[0]~A[heapsize-1]构成的完全二叉树中下标为index的结点A[index]//在其子树T中进行下移，使T成为大头堆O(log2(heapsize))voidList::Shift_down(intheapsize,intindex)//大头堆{intmax,temp,i=index,j=2*i+1;while(jheapsize){max=j;if(j+1heapsize&&A[j+1]A[j])max=j+1;//左右子树均存在if(A[i]A[max]){temp=A[i];A[i]=A[max];A[max]=temp;i=max;j=2*i+1;}elsebreak;}}//删除当前A[0]~A[heapsize-1]构成的大头堆中下标为index的结点A[index]，//将其与A[heapsize-1]交换，并将A[0]~A[heapsize-2]调整为大头堆《计算机软件基础》实验报告-3-voidList::DeleteNodeofHeap(intheapsize,intindex){inttemp=A[index];A[index]=A[heapsize-1];A[heapsize-1]=temp;Shift_down(heapsize-1,index);//coutdelete...\n;//this-Output();coutendl;};voidList::createHeap()//生成大头堆O(len){inti,j,max,temp;for(i=len/2-1;i=0;i--){max=j=2*i+1;if(j+1len&&A[j]A[j+1])max=j+1;if(A[i]A[max]){temp=A[i];A[i]=A[max];A[max]=temp;}}//coutcreateHeap()...\n;//this-Output();coutendl;};//堆排序O(len*log2(len))voidList::HeapSort(){inti;createHeap();for(i=len;i1;i--)DeleteNodeofHeap(i,0);};voidList::ShellInsert(intdk)//升序{inti,j,temp;for(i=dk;ilen;i++){temp=A[i];for(j=i-dk;j=0;j=j-dk){if(A[j]temp)A[j+dk]=A[j];elsebreak;};A[j+dk]=temp;};//this-Output();《计算机软件基础》实验报告-4-//coutendl;};voidList::ShellSort(int*delta,intt){intk;for(k=0;kt;k++)ShellInsert(delta[k]);};intList::Patation(intlow,intup)//划分，升序{intpivot,mid,temp;//先选择枢轴if(up-low1){mid=(low+up)/2;if(A[mid]A[up]&&A[mid]A[low]||A[mid]A[low]&&A[mid]A[up]){pivot=A[low];A[low]=A[mid];A[mid]=pivot;}elseif(A[up]A[mid]&&A[up]A[low]||A[up]A[low]&&A[up]A[mid]){pivot=A[low];A[low]=A[up];A[up]=pivot;}};//==========temp=A[low];//couttemp=tempendl;while(uplow){while(uplow){if(A[up]=temp)up--;else{A[low]=A[up];break;}};while(uplow){if(A[low]=temp)low++;else{A[up]=A[low];break;}};};//coutup=uplow=lowendl;A[up]=temp;//this-Output();return(up);}voidList::QuickSort(intlow,inthigh){《计算机软件基础》实验报告-5-intpivot;if(lowhigh){pivot=Patation(low,high);QuickSort(low,pivot-1);QuickSort(pivot+1,high);};};voidList::StraightInsertSort()//直接插入排序,升序{inti,j,temp;for(i=1;ilen;i++)//共len-1趟for(j=i;j0;j--)if(A[j]A[j-1]){temp=A[j];A[j]=A[j-1];A[j-1]=temp;}elsebreak;};voidList::BinaryInsertSort()//折半插入排序，升序{inti,j,low,up,mid,temp;for(i=1;ilen;i++){low=0;up=i-1;temp=A[i];while(up=low){mid=(low+up)/2;if(tempA[mid])up=mid-1;elselow=mid+1;};for(j=i-1;j=up+1;j--)A[j+1]=A[j];A[up+1]=temp;};};voidList::BubbleSort()//冒泡排序，升序{inti,j,temp,tag;for(i=len-1;i0;i--)//共len-1趟{tag=1;//逆序标志for(j=0;ji;j++)if(A[j]A[j+1]){temp=A[j];A[j]=A[j+1];A[j+1]=temp;tag=0;}if(tag)break;//本趟无逆序}《计算机软件基础》实验报告-6-};intList::GetLen(){return(len);}voidList::Output(){for(inti=0;ilen;i++){coutA[i]=A[i]'\x20';if((i+1)%5==0)coutendl;};coutendl;}intList::Geti(intloc,int&y){if(len==0)return(-1);if(loc0||loc=len)return(0);y=A[loc];return(1);}intList::Insert(intloc,intx){int*p,i;if(loc0||loclen)return(0);if(len==0){A[0]=x;len=len+1;return(1);};if(len==size){p=(int*)malloc((size+STEP)*sizeof(int));if(!p)return(-1);for(i=0;isize;i++)p[i]=A[i];delete[len]A;A=p;size=size+STEP;};for(i=len;iloc;i--)A[i]=A[i-1];A[loc]=x;len=len+1;return(1);}intList::Delete(intloc,int&y){inti;if(len==0)return(-1);if(loc0||loc=len)return(0);y=A[loc];《计算机软件基础》实验报告-7-for(i=loc+1;ilen;i++)A[i-1]=A[i];len=len-1;return(1);}voidmain(intargc,char*argv[]){intloc,value,ok,sel;charch='N';ListL1;intB[]={8,5,6,4,2,7,3,1};intdelta[]={3,2,1};ListL10(B,8);do{cout线性表抽象数据类型及其实现\n;cout1--输出线性表\n;cout2--插入一元素\n;cout3--删除一结点\n;cout4--求表的长度\n;cout5--取某位序元素\n;cout6--排序\n;cout66--排序(新插入的元素)\n;cout7--退出\n;cout请选择相应的功能（1~7）\n;cinsel;switch(sel){case1:L1.Output();break;case2:cout插入一元素合法位序为：0~L1.GetLen()endl;cout请输入位序和元素的值：\n;cinlocvalue;ok=L1.Insert(loc,value);if(ok==1)cout插入成功！\n;elseif(ok==0)cout