计算机软件上机实验报告

计算机软件技术基础上机实验报告实验一线性表的插入与删除实验内容创建了一个整数类型的升序单链表，演示单链表的创建，输出和删除操作。构造函数node*insert(node*head,intnum)，实现把一个结点插入链表，仍保持链表上各结点的升序关系。思路插入：在第i(1≤i≤n)个元素之前插入—个新元素，将从第i个到第n个元素之间的全部元素依次向后移动一个位置。删除：删除顺序表中的第i个元素(1≤in)，则将引起顺序表中数据元素的移动。这时需要将顺序表中第i+1位置到第n个位置之间的元素依次向前移动一个位置，从而覆盖掉第i个位置上的原有存储内容。程序代码#includeiostream.htypedefstructnode1{intdata;node1*next;}node;node*insert(node*head,intnum){node*s=newnode;s-data=num;s-next=NULL;if(head==NULL)head=s;else{node*p1,*p;p1=p=head;while(p!=NULL&&p-datanum){p1=p;p=p-next;}p1-next=s;s-next=p;}returnhead;}node*find(node*head,intk){node*p=0;p=head;inti=1;if(k==1)returnhead;else{while(p!=NULL&&ik){p=p-next;i++;}returnp;}}//建立一条有序链表node*create_sort(void){node*p1,*head=0;inta;cout建立一条有序链表，请输入数据，以-1结束：;cina;while(a!=-1){p1=newnode;p1-data=a;head=insert(head,a);cina;}returnhead;}//输出链表上各个结点的值voidprint(constnode*head){constnode*p;p=head;cout链表上各个结点的数据为：\n;while(p!=NULL){coutp-data'\t';p=p-next;}cout'\n';}//删除链表上具有指定值的一个结点node*delete_one_node(node*head,intnum){node*p1,*p2;if(head==NULL){cout链表为空，无结点可删！\n;returnNULL;}if(head-data==num){p1=head;head=head-next;deletep1;cout删除了一个结点!\n;}else{p2=p1=head;while(p2-data!=num&&p2-next!=NULL){p1=p2;p2=p2-next;}if(p2-data==num){p1-next=p2-next;deletep2;cout删除了一个结点！\n;}elsecoutnum链表上没找到要删除的结点！\n;}returnhead;}//释放链表的结点空间node*deletechain(node*h){node*p1;while(h){p1=h;h=h-next;deletep1;}cout已释放链表的结点空间！\n;returnh;}//求链表的结点数intcount(node*head){intn;node*p;p=head;n=0;while(p!=NULL){n=n+1;p=p-next;}returnn;}//删除链表上第K个结点node*delete_k_node(node*head,intk){intj=1;node*p,*p1;if(head==NULL){cout链表为空，无结点可删！\n;returnNULL;}p=head;if(k==1){p=head;head=head-next;deletep;cout删除了第一个结点！\n;}else{p=find(head,k-1);//查找第k-1个结点，并由p指针指向该结点if(p-next!=NULL){p1=p-next;p-next=p1-next;deletep1;cout删除了第k个结点！\n;}}returnhead;}voidmain(void){node*head;intnum;intk;head=create_sort();print(head);cout结点数：count(head)\n;cout输入要删除结点上的序号！\n;cinnum;head=delete_k_node(head,num);print(head);cout输入要删除结点上的整数！;cinnum;head=delete_one_node(head,num);print(head);head=deletechain(head);cout输入要插入的整数！\n;cinnum;head=insert(head,num);print(head);}调试结果插入算法的时间复杂度：O(n)=n/2删除算法的时间复杂度：O(n)=(n-1)/2实验二栈与队实验内容设车辆厂生产了硬座车厢和软座车厢共n节（混合在一起），要求用顺序栈的五种运算是所有的硬座车厢排列到软座车厢的前面。思路把硬座车厢代号放入栈H，再把软座车厢代号放入栈S，然后先一个一个取栈H的元素，并放入栈s，再取栈S的元素，并放入栈s。这样，就能把所有的硬座车厢排列到软座车厢的前面。程序代码#includeiostream.h#defineelemtypecharconstintmaxlen=20;structseqstack{elemtypestack[maxlen];inttop;};//初始化栈voidinistack(seqstack&s){s.top=0;}//进栈voidpush(seqstack&s,elemtypex){if(s.top==maxlen-1)coutoverflow;else{s.top++;s.stack[s.top]=x;}}//出栈voidpop(seqstack&s){if(s.top==0)coutunderflow;else{s.top--;}}//取栈顶元素elemtypegettop(seqstacks){if(s.top==0){coutunderflow;return0;}elsereturns.stack[s.top];}//判断空栈intempty(seqstacks){if(s.top==0)return1;elsereturn0;}//打印栈内容voidprtstack(seqstack&s){inti;for(i=1;i=s.top;i++){couts.stack[i]endl;}}voidmain(void){intn,i;elemtypex;seqstacks_H;seqstacks_S;inistack(s_H);inistack(s_S);cout请输入车厢数：;cinn;cout请输入n节车厢代号（H代表硬座车厢，S代表软座车厢）;/***********以下为自己编写的代码************/if(nmaxlen){cout车厢数目太多;return;}for(i=1;i=n;i++){cinx;if(x=='H')push(s_H,x);elseif(x=='S')push(s_S,x);}prtstack(s_H);prtstack(s_S);}调试结果时间复杂度为n实验四二叉树的遍历与应用实验内容建立二叉链表，并用递归实现二叉树的先序，中序，后序三种遍历。思路中序遍历与后序遍历同前序遍历都是一个递归的过程。中序遍历：先遍历左子树,访问根结点,再遍历右子树，直到二叉树为空时退出。后序遍历：先遍历左子树，再遍历右子树，再访问根节点，直到二叉树为空时退出。程序代码#includeiostream.htypedefstructbitree1{chardata;bitree1*lchild;bitree1*rchild;}bitree;bitree*CreatBiTree(){bitree*T;charch;cinch;if(ch==',')returnNULL;else{T=newbitree;T-data=ch;T-lchild=CreatBiTree();T-rchild=CreatBiTree();returnT;}}//voidpreorder(bitree*root){bitree*p;p=root;if(p!=NULL){coutp-data;preorder(p-lchild);preorder(p-rchild);}}//中序遍历voidinorder(bitree*root){bitree*p;p=root;if(p!=NULL){inorder(p-lchild);coutp-data;inorder(p-rchild);}}//后序遍历voidpostorder(bitree*root){bitree*p;p=root;if(p!=NULL){postorder(p-lchild);postorder(p-rchild);coutp-data;}}voidmain(void){bitree*root;cout建立一棵二叉树根为rootendl;root=CreatBiTree();cout先序遍历结果为:;preorder(root);coutendl中序遍历结果为:;inorder(root);coutendl后序遍历结果为:;postorder(root);coutendl;调试结果输入：ABDHIEJKCFL000G00前序遍历：ABDHIEJKCFLG中序遍历：HDIBJEKALFCG后序遍历：HIDJKEBLFGCA时间复杂度：O(n)实验六查找实验内容用线性探查法和拉链法建立哈希表，并在哈希表中查找关键字k。建立有序表，完成二分查找。思路线性探查法把表长为m的哈希表看作是环形表，若发生地址冲突的位置地址为d，则依次探查d+1,d+2,...,m-1,直到找到一个空闲的位置为止。其开放定地址公式为：di=(h(key)+i)%mi=1,2,...,m-1查找关键字，查找成功返回该记录在哈希表中的地址，查找失败返回-1.拉链法是将哈希地址相同的关键字的记录链接到同一个单链表中。查找关键字，查找成功返回指向该结点的指针，查找失败返回NULL。程序代码#includeiostream.hconstintm=13;//m代表哈希表长度constintn=10;//n代表关键字个数intr[n+1];structlnode//定义拉链法的链表{intdata;lnode*next;};//构造hash函数intH(intk){returnk%m;}//用线性探查法建立哈希表HT，表长为m，表中元素个数为nvoidcreat1(intHT[m],intn){inti,j;intk;for(i=0;im;i++)HT[i]=NULL;for(i=1;i=n;i++){k=r[i];//r[i]作为一个关键字j=H(k);//H(k)为哈希函数while(HT[j]!=NULL)j=(j+1)%m;//发生冲突时，查找空闲位置HT[j]=k;}}//在线性探查法的哈希表HT中查找关键字k，查找成功返回该记录在哈希表中地址，查找失败返回-1。intfind1(intHT[m],intk){inti,d=0,found=0;i=H(k);while(found!=1&&d=m){if(HT[(i+d)%m]==k)fou