《计算机软件基础》实验报告姓名：***学号：**********班级：11电气1班专业：电气工程及其自动化学院：电气与信息工程学院2013年12月实验一线性表的插入和删除一、实验目的1.熟悉C++上机环境；2.掌握线性表的基本操作：查找、插入、删除等运算在链接存储结构上的运算。

二、实验内容【任务一】阅读理解阅读后面的程序，并将其输入到计算机中，调试成功，运算出结果。

这个程序中我们创建了一个整数类型的升序单，演示了单链表的创建、输出和删除操作。

【任务二】完善功能构造函数node *insert (node *head,int num)，实现把一个节点插入链表，仍保持链表上各节点的升序关系，并在主函数中完成对你所添加函数的测试。

三、算法描述建立含有若干个元素的升序单链表，对其进行插入、删除等操作，并将结果在屏幕上输出。

// 实验一线性表#include "stdafx.h"const int SIZE0=2;const int STEP=1;struct List{int *A,len,size;List(){A=(int *)malloc(SIZE0*sizeof(int));if(!A)exit(1);len=0;size=SIZE0;}~List(){delete[size]A;}int GetLen();void Output();int Insert(int loc,int x);int Delete(int loc,int &y);int Geti(int loc,int &y);List(int *p,int n);void StraightInsertSort();void BinaryInsertSort();void BubbleSort();int Patation(int low,int up);void QuickSort(int low,int high);void SelectSort();void Shift_down(int heapsize,int index);void DeleteNodeofHeap(int heapsize,int index);void createHeap();void HeapSort();void ShellInsert(int dk);void ShellSort(int *delta,int t);};List::List(int *p,int n){A=new int[n];for(int i=0;i<n;i++)A[i]=p[i];len=size=n;};//简单选择排序void List::SelectSort(){int i,j,temp,max;for(i=len-1;i>0;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();cout<<endl;}}//将当前A[0]~A[heapsize-1]构成的完全二叉树中下标为index的结点A[index] //在其子树T中进行下移，使T成为大头堆O(log2(heapsize))void List::Shift_down(int heapsize,int index)//大头堆{int max,temp,i=index,j=2*i+1;while(j<heapsize){max=j;if(j+1<heapsize && 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;}else break;}}//删除当前A[0]~A[heapsize-1]构成的大头堆中下标为index的结点A[index]，//将其与A[heapsize-1]交换，并将A[0]~A[heapsize-2]调整为大头堆void List::DeleteNodeofHeap(int heapsize,int index) {int temp=A[index];A[index]=A[heapsize-1];A[heapsize-1]=temp;Shift_down(heapsize-1,index);//cout<<"delete...\n";//this->Output();cout<<endl;};void List::createHeap() //生成大头堆O(len){int i,j,max,temp;for(i=len/2-1;i>=0;i--){max=j=2*i+1;if(j+1<len && A[j]<A[j+1])max=j+1;if(A[i]<A[max]){ temp=A[i];A[i]=A[max];A[max]=temp;} }//cout<<"createHeap()...\n";//this->Output();cout<<endl;};//堆排序O(len*log2(len))void List::HeapSort(){int i;createHeap();for(i=len;i>1;i--)DeleteNodeofHeap(i,0);};void List::ShellInsert(int dk)//升序{int i,j,temp;for(i=dk;i<len;i++){temp=A[i];for(j=i-dk;j>=0;j=j-dk){if(A[j]>temp)A[j+dk]=A[j];else break;};A[j+dk]=temp;};// this->Output();// cout<<endl;};void List::ShellSort(int *delta,int t){int k;for(k=0;k<t;k++)ShellInsert(delta[k]);};int List::Patation(int low,int up)//划分，升序{int pivot,mid,temp;//先选择枢轴if(up-low>1){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];//cout<<"temp="<<temp<<endl;while(up>low){while(up>low){if(A[up]>=temp) up--;else {A[low]=A[up];break;}};while(up>low){if(A[low]<=temp)low++;else {A[up]=A[low];break;}};};//cout<<"up="<<up<<"low="<<low<<endl;A[up]=temp;//this->Output();return(up);}void List::QuickSort(int low,int high){int pivot;if(low<high){pivot=Patation(low,high);QuickSort(low,pivot-1);QuickSort(pivot+1,high);};};void List::StraightInsertSort()//直接插入排序,升序{int i,j,temp;for(i=1;i<len;i++)//共len-1趟for(j=i;j>0;j--)if(A[j]<A[j-1]){temp=A[j];A[j]=A[j-1];A[j-1]=temp;}else break;};void List::BinaryInsertSort()//折半插入排序，升序{int i,j,low,up,mid,temp;for(i=1;i<len;i++){low=0;up=i-1;temp=A[i];while(up>=low){mid=(low+up)/2;if(temp<A[mid])up=mid-1;else low=mid+1;};for(j=i-1;j>=up+1;j--)A[j+1]=A[j];A[up+1]=temp;};};void List::BubbleSort()//冒泡排序，升序{int i,j,temp,tag;for(i=len-1;i>0;i--)//共len-1趟{tag=1;//逆序标志for(j=0;j<i;j++)if(A[j]>A[j+1]){temp=A[j];A[j]=A[j+1];A[j+1]=temp;tag=0;} if(tag)break;//本趟无逆序}};int List::GetLen(){return(len);}void List::Output(){for(int i=0;i<len;i++){ cout<<"A["<<i<<"]="<<A[i]<<'\x20';if((i+1)%5==0)cout<<endl;};cout<<endl;}int List::Geti(int loc,int &y){if(len==0)return(-1);if(loc<0||loc>=len)return(0);y=A[loc];return(1);}int List::Insert(int loc,int x){int *p,i;if(loc<0||loc>len)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;i<size;i++)p[i]=A[i];delete[len]A;A=p;size=size+STEP;};for(i=len;i>loc;i--)A[i]=A[i-1];A[loc]=x;len=len+1;return(1);}int List::Delete(int loc,int &y){int i;if(len==0)return(-1);if(loc<0||loc>=len)return(0);y=A[loc];for(i=loc+1;i<len;i++)A[i-1]=A[i];len=len-1;return(1);}void main(int argc, char* argv[]){int loc,value,ok,sel;char ch='N';List L1;int B[]={8,5,6,4,2,7,3,1};int delta[]={3,2,1};List L10(B,8);do{cout<<"线性表抽象数据类型及其实现\n";cout<<"1--输出线性表\n";cout<<"2--插入一元素\n";cout<<"3--删除一结点\n";cout<<"4--求表的长度\n";cout<<"5--取某位序元素\n";cout<<"6--排序\n";cout<<"66--排序(新插入的元素)\n";cout<<"7--退出\n";cout<<"请选择相应的功能（1~7）\n";cin>>sel;switch(sel){case 1:L1.Output();break;case 2:cout<<"插入一元素合法位序为：0 ~ "<<L1.GetLen()<<endl;cout<<"请输入位序和元素的值：\n";cin>>loc>>value;ok=L1.Insert(loc,value);if(ok==1)cout<<"插入成功！\n";else if(ok==0)cout<<"插入位序非法！\n";else cout<<"表满！\n";break;case 3:cout<<"删除一元素合法位序为：0~"<<L1.GetLen()-1<<endl;cout<<"请输入位序：\n";cin>>loc;ok=L1.Delete(loc,value);if(ok==1)cout<<"删除成功！删除结点的值="<<value<<endl;else if(ok==0)cout<<"删除位序非法！\n";else cout<<"表空！\n";break;case 4:cout<<"表的长度="<<L1.GetLen()<<endl;break;case 5:cout<<"取某一元素\n";cout<<"请输入位序：\n";cin>>loc;ok=L1.Geti(loc,value);if(ok==1)cout<<"第"<<loc<<"位序的值="<<value<<endl;else if(ok==0)cout<<"取值位序非法！\n";else cout<<"表空！\n";break;case 6:L10.StraightInsertSort();L10.Output();break;case 66:L1.StraightInsertSort();L1.Output();break;case 7:ch='Y';};}while(ch!='Y');}四、实验数据及截图图1在0位置插入10 图2插入位序非法图3继续插入元素图4输出线性表图5删除一元素后输出图6求表的长度图7取某一元素图8排序（原程序）图9 输出和排序新插入的元素（程序修改后）图10退出实验二栈抽象数据及实现一、实验目的1．掌握栈的数据类型描述、站的特点及栈的存储结构；2．掌握栈的基本运算及应用。