线性表的操作算法实验报告

实验报告2013学年第一学期任课老师：课程名称数据结构班级学号姓名实验名称实验一线性表的操作算法实验时间实验环境VisualC++6.0

实验目的和内容要求实验一线性表的操作算法1．实验目的

用C/C++,Java程序实现课本中的有关算法，以达到对算法熟练的目的。2．实验内容

分别用数组和链表作为存储结构，实现线性表的插入、删除、查找、排序、合并等操作。实验过程记录（学生写出实验步骤及中间的结果与现象，在实验中做了什么，怎么做，发生的现象和中间结果）链表：在写主函数之前，先创建一个长度为n的链表typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;建立链表的函数框架，根据实验要求完善功能插入：intListInsert(LinkList&L,inti,inte){LinkListp=L;intj=0;while(p&&j<i-1){ p=p->next;++j;}if(!p||j>i-1)return0;LinkLists=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return1;}删除：intListDelete(LinkList&L,inti,int&e){LinkListp=L;intj=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)return0;LinkListq=p->next;p->next=q->next;e=q->data;free(q);cout<<"被删除的元素数据为"<<e<<"\n";return0;}查找：intGetElem(LinkList&L,inti,int&e){LinkListp=L->next;intj=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)return0;e=p->data;cout<<"该元素的值为"<<e<<"\n";return1;}排序：LinkListSort(LinkListL){ LinkListp,q; inttemp; for(p=L;p!=NULL;p=p->next) { for(q=p->next;q!=NULL;q=q->next) { if(p->data>q->data) { temp=q->data; q->data=p->data; p->data=temp; } } } returnL;}合并:voidMergeList_L(LinkList&L,LinkList&La,LinkList&Lb){LinkListp,pa,pb; p=L->next; pa=La->next; Lb=pb=L;//用L的头结点作为Lb的头结点 while(p&&pa){ if(p->data<=pa->data){ pb->next=p; pb=p; p=p->next; } else{ pb->next=pa; pb=pa; pa=pa->next; } } pb->next=p?p:pa; free(La);}完成函数框架后开始写主函数，先输入一个链表L，然后出现功能栏目，可供选择，此处应做一个循环，使其可不断对该链表L操作，用多支选择语句加上do…while循环。intmain(){LinkListL; intn,s,e,i,f,g,h; cout<<"输入链表长度n:"; cin>>n; cout<<"请输入L中的元素:"<<endl; CreateList(L,n); cout<<"输入的链表为:"<<""; LNode*q=L->next;while(q){cout<<q->data<<"";q=q->next;} cout<<endl; intchoice; cout<<"请选择功能:"<<endl; cout<<"1.插入元素"<<endl; cout<<"2.删除元素"<<endl; cout<<"3.查找元素"<<endl; cout<<"4.给元素排序"<<endl; cout<<"5.合并链表"<<endl; cout<<"0.退出程序"<<endl; cout<<"PS:若先排序再合并，可将得到新的排序后的合并链表。"<<endl; do{ cout<<endl; cout<<"请选择功能:"<<endl; cin>>choice; switch(choice) { case1: { cout<<"输入插入的位置:"; cin>>s;cout<<"输入插入的数据元素:"; cin>>e; ListInsert(L,s,e);cout<<"插入后的链表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case2: { cout<<"输入删除位置:"; cin>>g; ListDelete(L,g,h); cout<<"删除后的链表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case3: { cout<<"输入查找位置:"; cin>>i; GetElem(L,i,f); break; } case4: { LinkListp; Sort(L); cout<<"排序后的链表为:"<<endl; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case5: { LinkListLa,Lb; intm; cout<<"请输入另一个链表La的长度m:"; cin>>m; cout<<"请输入La中的元素:"<<endl; CreateList(La,m); cout<<"输入的链表La为:"<<""; LNode*q=La->next; while(q){ cout<<q->data<<""; q=q->next; } Sort(La);MergeList_L(L,La,Lb); cout<<endl;cout<<"合并后的链表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } } } while(choice!=0); return0;}数组：同理，代码附在报告后。实验结果分析与总结1、程序运行结果（请提供所完成的各道题运行结果界面截图）：2、在实验过程中遇到的问题与解决方法：问题有很多，比如局部变量与全局变量的声明，常常顾此失彼，此处概念仍然不清。数组的概念出从零开始的命名与使用者角度的转换也常常忘记，所以经常出现空出一位的表，那一位为系统随机赋值。还有便是在值的传递上，思路不甚明确，导致常常断开，不能调用函数后改变表的值。3、实验过程中的发现与收获，未解决或需进一步解决的问题：在循环嵌套方面还是有些害怕，不能一次调试成功，常常需要加减来改变。收获是学会了在写代码前画流程图来清晰思路，毕竟在算法这方面并不擅长，还需要更多的世间来适应并练习。指导老师评阅意见指导老师：年月日填写内容时，可把表格扩大。附：实验源程序代码顺序表（链表）：//线性表（链表）#include<stdio.h>#include"malloc.h"#include<iostream>usingnamespacestd;typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;//创建一个长度为n的链表voidCreateList(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(inti=n;i>0;--i){LinkListp=(LinkList)malloc(sizeof(LNode));cin>>p->data;p->next=L->next;L->next=p;}}//在链表L第i个元素之前插入元素eintListInsert(LinkList&L,inti,inte){LinkListp=L;intj=0;while(p&&j<i-1){ p=p->next;++j;}if(!p||j>i-1)return0;LinkLists=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return1;}//在链表L中删除第i个元素，并由e返回其值intListDelete(LinkList&L,inti,int&e){LinkListp=L;intj=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1)return0;LinkListq=p->next;p->next=q->next;e=q->data;free(q);cout<<"被删除的元素数据为"<<e<<"\n";return0;}//查找第i个元素,并由e返回其值intGetElem(LinkList&L,inti,int&e){LinkListp=L->next;intj=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)return0;e=p->data;cout<<"该元素的值为"<<e<<"\n";return1;}//让链表L中的元素按从小到大的顺序排列LinkListSort(LinkListL){ LinkListp,q; inttemp; for(p=L;p!=NULL;p=p->next) { for(q=p->next;q!=NULL;q=q->next) { if(p->data>q->data) { temp=q->data; q->data=p->data; p->data=temp; } } } returnL;}//归并L和La得到新的单链性表LbvoidMergeList_L(LinkList&L,LinkList&La,LinkList&Lb){LinkListp,pa,pb; p=L->next; pa=La->next; Lb=pb=L;//用L的头结点作为Lb的头结点 while(p&&pa){ if(p->data<=pa->data){ pb->next=p; pb=p; p=p->next; } else{ pb->next=pa; pb=pa; pa=pa->next; } } pb->next=p?p:pa; free(La);}intmain(){LinkListL; intn,s,e,i,f,g,h; cout<<"输入链表长度n:"; cin>>n; cout<<"请输入L中的元素:"<<endl; CreateList(L,n); cout<<"输入的链表为:"<<""; LNode*q=L->next;while(q){cout<<q->data<<"";q=q->next;} cout<<endl; intchoice; cout<<"请选择功能:"<<endl; cout<<"1.插入元素"<<endl; cout<<"2.删除元素"<<endl; cout<<"3.查找元素"<<endl; cout<<"4.给元素排序"<<endl; cout<<"5.合并链表"<<endl; cout<<"0.退出程序"<<endl; cout<<"PS:若先排序再合并，可将得到新的排序后的合并链表。"<<endl; do{ cout<<endl; cout<<"请选择功能:"<<endl; cin>>choice; switch(choice) { case1: { cout<<"输入插入的位置:"; cin>>s;cout<<"输入插入的数据元素:"; cin>>e; ListInsert(L,s,e);cout<<"插入后的链表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case2: { cout<<"输入删除位置:"; cin>>g; ListDelete(L,g,h); cout<<"删除后的链表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case3: { cout<<"输入查找位置:"; cin>>i; GetElem(L,i,f); break; } case4: { LinkListp; Sort(L); cout<<"排序后的链表为:"<<endl; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } case5: { LinkListLa,Lb; intm; cout<<"请输入另一个链表La的长度m:"; cin>>m; cout<<"请输入La中的元素:"<<endl; CreateList(La,m); cout<<"输入的链表La为:"<<""; LNode*q=La->next; while(q){ cout<<q->data<<""; q=q->next; } Sort(La);MergeList_L(L,La,Lb); cout<<endl;cout<<"合并后的链表:"<<"\n"; q=L->next; while(q){ cout<<q->data<<""; q=q->next; } break; } } } while(choice!=0); return0;}顺序表（数组）：//顺序表(数组).cpp//#include"stdafx.h"#include<stdio.h>#include"malloc.h"#include<iostream>usingnamespacestd;#defineLIST_INIT_SIZE100#defineLISTINCREMENT10structS{int*p;intlength;intlistsize;};//构造一个空的线性表LintInitList(S&L){L.p=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(!L.p)return0;L.length=0;L.listsize=LIST_INIT_SIZE;return1;}//在表中第i个位置之前插入新的元素eintListInsert(S&L,inti,inte){if(i<1||i>L.length+1)return0;if(L.length>=L.listsize){int*newbase=(int*)realloc(L.p,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase)return0; L.p=newbase; L.listsize+=LISTINCREMENT;}int*q=&(L.p[i-1]);for(int*y=&(L.p[L.length-1]);y>=q;--y)*(y+1)=*y;*q=e;++L.length;return1;}//在表中删除第i个元素，并用e返回其值intListDelete(S&L,inti,int&e){if((i<1)||(i>L.length))return0;int*k=&(L.p[i-1]);e=*k;int*q=L.p+L.length-1;for(++k;k<=q;++k)*(k-1)=*k;--L.length;return1;}//在表中查找某位置上的元素intGetElem(S&L,inti,int&e){if((i<1)||(i>L.length))return0;int*k=&(L.p[i-1]);e=*k;returne;}//给表中元素按从小到大的顺序排序/*SLSort(S&L){ int*p; intn,t; for(intj=0;j<n-1;j++){ for(intk=0;k<n-j-1;k++){ if(p[k]>p[k+1]){ t=p[k+1]; p[k+1]=p[k]; p[k]=t; } } } for(inti=0;i<n;i++) cout<<p[i]<<endl; returnL;}*///与另一个表La合并成为新的表Lb//voidMergeList_L(S&L,S&La,S&Lb){//}voidLSort(S&L){inta=L.p[0];for(inti=1;i<L.length;++i){if(L.p[i]<L.p[i-1]){L.p[0]=L.p[i];for(intj=i-1;L.p[0]<L.p[j];--j)L.p[j+1]=L.p[j];L.p[j+1]=L.p[0];}}L.p[0]=a;}Smerge(S&L,S&La){ structSLb;int*p=L.p;int*pa=La.p;Lb.length=L.length+La.length;int*pb=Lb.p=(int*)malloc(Lb.length*sizeof(int));int*p_last=p+L.length-1;int*pa_last=pa+La.length-1;while(p<=p_last&&pa<=pa_last){if(*p<=*pa)*pb++=*p++;else*pb++=*pa++;}while(p<=p_last)*pb++=*p++;while(pa<=pa_last)*pb++=*pa++;returnLb;}intmain(){intn; structSlist;InitList(list); cout<<"输入链表长度n:"; cin>>n; cout<<"请输入L中的元素:"<<endl; for(inti=0;i<=n-1;i++) {cin>>list.p[i]; list.length++; }; cout<<"输入的链表为:"<<endl; for(ints=0;s<=n-1;s++) { cout<<list.p[s]<<""; } cout<<endl; intchoice; cout<<"请选择功能:"<<endl; cout<<"1.插入元素"<<endl; cout<<"2.删除元素"<<endl; cout<<"3.查找元素"<<endl; cout<<"4.给元素排序"<<endl; cout<<"5.合并链表"<<endl; cout<<"0.退出程序"<<endl; do{ cout<<endl; cout<<"请选择功能:"<<endl;