福州大学数据结构实验报告-线性表

PAGEPAGE1福州大学数据结构实验报告-线性表第一篇：福州大学数据结构实验报告-线性表数据结构原理实验报告学号：姓名：线性表一、问题描述1.实现ADT表2.设表的Reverse运算将表中元素的次序反转。扩充用数组实现表的结构List，增加函数Reverse(L)，将表L中元素的次序反转，并要求就地实现Reverse运算。二、算法描述从i=0开始，将表中第N个元素与N-i-1个元素调换即可三、核心代码voidReverseList(ListL){ListItemtmp;inti;for(i=0;in/2;i++){}tmp=L->table[i];L->table[i]=L->table[L->n-1-i];L->table[L->n-1-i]=tmp;}四、运行结果第二篇：数据结构线性表实验报告实验报告课程名：数据结构实验名：线性表及其操作姓名：班级：学号：撰写时间：20XX.09.24一实验目的与要求1.掌握线性表的实现2.掌握线性表的基本操作的实现二实验内容•分别完成线性表的顺序表示及链式表示•在两种表示上,分别实现一些线性表的操作,至少应该包括–在第i个位置插入一个元素–删除第i个元素–返回线性表长–返回第i个元素的值三实验结果与分析#include#include//线性表链式表示structV//声明一个结构体类型structV{intvalue;structV*next;//定义结构体变量};voidPrintLink(structV*p)//定义一个结构体指针{while(p!=NULL)//只要指针指向的变量不为NULL；就会一直循环链表指向下一个结构体{printf(“%d,”,(*p).value);p=(*p).next;//指针指向下一个结构体}printf(“n”);}voidLink(){structV*head;head=(structV*)malloc(sizeof(structV));//开辟一个长度为size的内存(*head).value=-100;//表头为-100(*head).next=NULL;printf(“线性表链式表示n”);inti,n=10;structV*p=head;printf(“10个数据:n”);for(i=0;i(*p).next=(structV*)malloc(sizeof(structV));p=(*p).next;(*p).value=2*i;(*p).next=NULL;}PrintLink(head);//调用PrintLink函数printf(“删除第四个数据:n”);intk=4;p=head;for(i=1;ip=(*p).next;}structV*temp=(*p).next;//k表示插入和删除的位置(*p).next=(*temp).next;free(temp);PrintLink(head);printf(“插入第十个数据:n”);k=10;p=head;for(i=1;ip=(*p).next;}temp=(*p).next;(*p).next=(structV*)malloc(sizeof(structV));(*(*p).next).value=-99;(*(*p).next).next=temp;PrintLink(head);}//线性表顺序表示voidseq1(){inti,n=10,k=4;inta[10];//输出数组元素printf(“线性表顺序表示n”);for(i=0;ia[i]=i;}printf(“数组元素为:n”);for(i=0;iprintf(“%3d”,a[i]);}printf(“n”);//插入一个数组元素intm=n+1,j=12;//插入元素12intb[20XXfor(i=0;iif(i{b[i]=a[i];}elseif(i==k){b[i]=j;}else{b[i]=a[i-1];}}printf(“输出插入一个元素的数组:n”);for(i=0;i{if(i{c[i]=a[i];}else{c[i]=a[i+1];}}printf(“输出删除一个元素的数组:n”);for(i=0;iprintf(“数组元素为:n”);for(i=1;i<=a[0];i++){a[i]=i;}for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);}printf(“n”);//在k位置插入一个元素for(i=a[0];i>=k;i--){a[i+1]=a[i];}a[k]=-100;++a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);}printf(“n”);//在kfor(i=0;i>k;i++){a[i]=a[i+1];}a[k]=-1;a[0]=n;--a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);}printf(“n”);}intmain(intargc,char*argv[]){seq1();seq2();Link();return0;}图1：实验结果截图实验分析：已在程序中按规定格式标注。第三篇：数据结构--实验报告线性表的基本操作}(一)单链表的基本操作#includeusingnamespacestd;#definetrue1#definefalse0#defineok1#defineerror0#defineoverflow-2typedefintStatus;typedefintElemType;typedefstructLNode//存储结构{ElemTypedata;structLNode*next;}LNode,*LinkList;voidCreateList(LinkList&L,intn)//尾插法创建单链表{LinkListp;L=newLNode;L->next=NULL;//建立一个带头结点的单链表LinkListq=L;//使q指向表尾}StatusGetElem(LinkListL,inti,ElemType&e)//取第i个元素{LinkListp=L->next;intj=1;while(p&jnext++j;}for(inti=1;i<=n;i++){p=newLNode;cin>>p->data;p->next=NULL;q->next=p;q=p;}if(!p||j>i)returnerror;//第i个元素不存在e=p->data;returnok;}StatusLinkInsert(LinkList&L,inti,ElemTypee)//插入{LinkListp=L;intj=0;while(p&jnext++j;}//寻找第i-1个结点if(!p||j>i-1)returnerror;//i小于1或者大于表长加1LinkLists=newLNode;//生成新结点s->data=e;s->next=p->next;//插入L中p->next=s;returnok;}StatusListDelete(LinkList&L,inti,ElemType&e)//删除{LinkListp=L;LinkListq;intj=0;while(p->next&&jp=p->next;++j;}if(!(p->next)||j>i-1)returnerror;//删除位置不合理q=p->next;p->next=q->next;//删除并释放结点e=q->data;delete(q);returnok;}voidMergeList(LinkList&La,LinkList&Lb,LinkList&Lc){//合并两个顺序链表LinkListpa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=pa?pa:pb;delete(Lb);}voidshow(LinkListL)//{LinkListp;p=L->next;while(p){cout<data<”;p=p->next;}coutnext;}returni;}voidxiugai(LinkListL)//修改{inti,j=1;ElemTypek;ElemTypee,m;LinkListp=L->next;cout<i;GetElem(L,i,e);cout<<>k;while(p&jnext++j;}m=p->data;p->data=k;cout<<“修改后的单链表显示如下:”<>a;cout<<>b;cout<<>select;switch(select){case1:cout<<cin>>x;cout<<CreateList(list,x);break;case2:cout<<“单链表显示如下:”<show(list);break;case3:ints;cout<<“单链表的长度为:”<>x;while(x<0||x>Length(list,s)){cout<<>x;}GetElem(list,x,y);cout<<>x;while(x<0||x>Length(list,s)){cout<<>x;}cout<>y;LinkInsert(list,x,y);cout<<>x;while(x<0||x>Length(list,s)){cout<<>x;}cout<<ListDelete(list,x,y);}break;case8:hebing();break;case9:exit(0);break;default:cout<<四、测试结果1)顺序表的测试结果82)单链表的测试结果五、心得体会当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验报告。记得去年学习C++时，学了一个学期，程序设计用了三周，才完成的，这个实验报告居然要一周完成两个设计，觉得很难。但是现在一周过去了，我也写完了，自我感觉良好。通过这次写实验报告，我深切的理解了这门课的本质。刚开始学这门课时，当时还不清楚这门课程的目的，现在，我真正的理解了：数据结构像是身体的骨骼，而C++是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，抽象数据类型中列举了各种操作，而所用的C++语言，将各种操作描述出来构成算法。数据结构+算法=程序设计。在这次设计的过程中，我还遇到了，很多的问题。顺序表是按顺序存储的，用了一维数组来存储，又结合C++的程序设计，我又用了类，但是，在执行时出现了问题。后来问同学，指出我的错误，不过获益不少。我又重新整理思路，把顺序表的基本操作写好了。虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事情。单链表写起来简单多了，这个很快就搞定了。但是细节上出了问题。比如说，有些变量的重复定义，有些变量又没有定义，在调用函数，就直接复制过来，没有改参数……通过修改，我深刻理解到：细节决定成败，在以后，不管做任何事情都要认真，细心。这次的实验报告，让我受益匪浅，不仅有知识方面的，还有生活和精神上的。总之，我会继续我的兴趣编程，相信在编程的过程中，能不断的提高自己。第四篇：数据结构线性表试验报告线性表上机实习1、实验目的（1）熟悉将算法转换为程序代码的过程。（2）了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。（3）熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。（4）了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。（5）熟练掌握线性链表（单链表）的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。2、实验要求（1）熟悉顺序表的插入、删除和查找。（2）熟悉单链表的插入、删除和查找。3、实验内容:①顺序表（1）抽象数据类型定义typedefstruct{TypeDatadata[maxsize];//容量为maxsize的静态顺手表intn;//顺序表中的实际元素个数}SeqList;//静态顺序表的定义在本次实验中，首先建立一个空的静态顺序表，然后键盘输入数据存入表中，然后进入菜单选择界面，通过不同的数字输入，实现对顺序表，删除，插入，查找，显示等操作。（2）存储结构定义及算法思想在顺序表结构体的定义中，typedefintTypeData为整型，存储结构如下：for(n=0;ncout<<cin>>L.data[n];//顺序将数据存入顺序表}//其他存储与此类似，都是直接赋值与数组的某一位插入版块子函数：voidinsert(SeqList&L)//插入数据{inta,b,c,k;cout<<cin>>a>>b;if(b<=0||b>(L.n+1)){cout<<k=L.data[b-1];L.data[b-1]=a;c=L.n;L.n=L.n+1;while(c>b){L.data[c]=L.data[c-1];c--;//通过循环，实现插入位置后的数据挨个往后移动一位}L.data[b]=k;}顺序表的插入与删除操作类似，在插入与删除后，都要循环调整后面数组的每一位元素，同时记录数据元素的长度的标示符也要跟着改变。显示操作是通过循环实现表中第一个元素到最后一个元素的输出，查找操作是直接取数组中的查找位输出。（3）实验结果与分析②单链表（1）抽象数据类型定义typedefstructnode{DataTypedata;//链表的数据类型structnode*link;//链表的结点指针}linknode,*linklist;//定义了结构体linklode和结构体指针linklist在本次实验中，首先程序自己建立一个空的头结点，通过菜单的功能选择“添加链表数据”可自由添加链表的节点数及元素值。在菜单选择中，有“添加链数据”，“插入链表数据”，“删除链表数据”，“查找链表数据”和“显示链表数据”功能，选择不能的功能选择就能实现不同的操作。其中“添加链表数据”可反复批量输入链表数据。（2）存储结构定义及算法思想在单链表中，typedefintDataType;DataTypedata;定义链表存储数据位整型。存储结构如下：while(p->link!=NULL){p=p->link;k++;//首先找到单链表的最后结点（如果是只有头结点}的单链表则直接跳过），以便后面接着输入数据for(inti=0;i{cout<<//开辟新的结点空间并转化为linklist指针型cin>>q->data;q->link=p->link;//将前面一个结点的指向(及NULL)赋给新开辟的结点的指向p->link=q;//将插入点前面一个结点指向新开辟的的结点p=q;//将指明的最后一个一个结点向后移1位到最后一位，以便后面接着输入}删除结点子函数：voiddelate(linklist&l){//删除单链表数据linklistp;intm,n,i=0;cout<<cin>>m;p=l;//将头结点赋给转移指针pwhile(p&&i//查找删除结点的位置p=p->link;//当在单链表中间已查到删除结点或p=NULL时跳出循环i++;}if(p==NULL){//当p=NULL跳出循环时，表明链表中没有该结点cout<<}n=p->link->data;//找到删除接结点将数据取出并显示出来（找结点时是找的前一个结点）cout<<p->link=p->link->link;//将删除结点的前后结点链接起来}链表的删除，插入操作是类似的，要考虑到加入或减少一个结点后，前后结点的链接关系，以及删除或插入的是最后一个结点时，新空间的开辟与结点收尾等问题。其中删除功能的一部分就是查找功能，显示功能也是从链表的头结点遍历至最后一个，依次输出。（4）实验结果与分析③心得体会本次数据结构实习我收获颇丰，以前学过c语言与c++也有经常上机，但以往都是偏向于程序整体的算法设计，没有像这次的实习这样是着重在线性表，链表结构的算法设计上面。这次上机实习，让我更加熟练了结构体及结构体指针的用法，线性表的设计等等，同时在这次实习中，引用，指针，地址这三个的用法曾一度让我混淆，在查阅书籍后才得以解决，也希望老师在课堂上有时间时给我们详细讲解一下，指针，地址，引用三者的使用。附录：顺序表源代码:#includeusingnamespacestd;#definemaxsize50typedefintTypeData;typedefstruct{TypeDatadata[maxsize];intn;}SeqList;voidmakeSeq(SeqList&L)//据{intm,n,k;cout<<>m;for(n=0;n>L.data[n];}L.n=m;cout<<输入线性表数输出线性表数据voidinsert(SeqList&L)//插入数据{inta,b,c,k;cout<<>a>>b;if(b<=0||b>(L.n+1)){cout<wei;if(wei<1||wei>L.n){cout<<>a;if(a<=0||a>(L.n)){cout<<cout<<>xuanze;switch(xuanze){case1:insert(L);break;case2:delate(L);break;case3:find(L);break;case4:showSeq(L);break;default:break;}}}单链表源代码：#includeusingnamespacestd;typedefintDataType;typedefstructnode{DataTypedata;structnode*link;}linknode,*linklist;linklistchushihua(){linklistL;L=(linklist)malloc(sizeof(linknode));L->link=NULL;cout<<“开辟空间成功，头结点建立”<>a;linklistp,q;p=l;while(p->link!=NULL){p=p->link;k++;}for(inti=0;i>q->data;q->link=p->link;p->link=q;p=q;}}voidshow(linklistl){cout<<“链表数据为：”<data<link;}cout<>m;linklistp;p=l->link;while(p&ilinki++;}if(!p){cout<<“链表没有这么长,查找错误”<data<{linklistp,q;intm,n,i=0;cout<<>m>>n;p=l;while(p&ilinki++;}if(p==NULL){cout<<q=(linklist)malloc(sizeof(linknode));q->data=n;q->link=p->link;p->link=q;}voiddelate(linklist&l){linklistp;intm,n,i=0;cout<<>m;p=l;while(p&ilinki++;}if(p==NULL){cout<data;cout<link->link;}voidmain(){linklistL;intselect;L=chushihua();while(1){cout<<“请选择功能”<>select;switch(select){case1:shuru(L);break;case2:insert(L);break;case3:delate(L);break;case4:find(L);break;case5:show(L);break;default:break;}}}第五篇：数据结构实验报告二线性表的顺序存储实验报告二线性表的顺序存储班级：20XXXXX姓名：HoogLe学号：20XXXXXX专业：XXXX2858505197@一、实验目的：（1）掌握顺序表的基本操作的实现方法。（2）应用顺序表的基本算法实现集合A=AUB算法。（3）应用顺序表的基本算法实现两有序顺序表的归并算法。二、实验内容：1、线性表顺序存储结构的基本操作算法实现（要求采用类模板实现）[实现提示]（同时可参见教材p5822-p60页算法、ppt）函数、类名称等可自定义，部分变量请加上学号后3位。库函数载和常量定义：（代码）#includeusingnamespacestd;constintMaxSize=100;（1）顺序表存储结构的定义(类的声明)：（代码）template//定义模板类SeqListclassSeqList{public:SeqList();//无参构造函数SeqList(datatypea[],intn);//有参构造函数~SeqList(){};//析构函数为空intLength();//求线性表的长度datatypeGet(inti);//按位查找，取线性表的第i个元素intLocate(datatypeitem);//查找元素itemvoidInsert(inti,datatypeitem);//在第i个位置插入元素itemdatatypeDelete(inti);//删除线性表的第i个元素voiddisplay();//遍历线性表，按序号依次输出各元素private:datatypedata[MaxSize];//存放数据元素的数组intlength;//线性表的长度};（2）初始化顺序表算法实现（不带参数的构造函数）/**输入：无*前置条件：顺序表不存在*功能：构建一个顺序表*输出：无*后置条件：表长为0*/实现代码：templateSeqList::SeqList(){length=0;}（3）顺序表的建立算法（带参数的构造函数）/**输入：顺序表信息的数组形式a[],顺序表长度n*前置条件：顺序表不存在*功能：将数组a[]中元素建为长度为n的顺序表*输出：无*后置条件：构建一个顺序表*/实现代码：templateSeqList::SeqList(datatypea[],intn){if(n>MaxSize){cout<<data[i]=a[i];length=n;}（4）在顺序表的第i个位置前插入元素e算法/**输入：插入元素e,插入位置i*前置条件：顺序表存在，i要合法*功能：将元素e插入到顺序表中位置i处*输出：无*后置条件：顺序表插入新元素，表长加1*/实现代码：templatevoidSeqList::Insert(inti,datatypeitem){intj;if(length>=MaxSize){cout<<“溢出”<<“i不合法！”<=i;j--)data[j]=data[j-1];data[i-1]=item;length++;}（5）删除线性表中第i个元素算法/**输入：要删除元素位置i*前置条件：顺序表存在,i要合法*功能：删除顺序表中位置为i的元素*输出：无*后置条件：顺序表册除了一个元素，表长减1*/实现代码：templatedatatypeSeqList::Delete(inti){intitem,j;if(length==0){cout<<<“i不合法!”<for(j=i;jdata[j-1]=data[j];//注意数组下标从0记length--;returnitem;}（6）遍历线性表元素算法/**输入：无*前置条件：顺序表存在*功能：顺序表遍历*输出：输出所有元素*后置条件：无*/实现代码：templatevoidSeqList::display(){if(length==0){cout<<cout<（7）获得线性表长度算法/**输入：无*前置条件：顺序表存在*功能：输出顺序表长度*输出：顺序表长度*后置条件：无*/实现代码：templateintSeqList::Length(){returnLength;}（8）在顺序线性表中查找e值，返回该元素的位序算法/**输入：查询元素值e*前置条件：顺序表存在*功能：按值查找值的元素并输出位置*输出：查询元素的位置*后置条件：无*/实现代码：templateintSeqList::Locate(datatypeitem){for(inti=0;i//下标为i的元素等于item，返回其序号i+1return0;//查找失败}（9）获得顺序线性表第i个元素的值/**输入：查询元素位置i*前置条件：顺序表存在，i要合法*功能：按位查找位置为i的元素并输出值*输出：查询元素的值*后置条件：无*/实现代码：templatedatatypeSeqList::Get(inti){if(i<0||i>length){cout<<“i不合法!”<（10）判表空算法/**输入：无*前置条件：无*功能：判表是否为空*输出：为空返回1，不为空返回0*后置条件：无*/实现代码：templateboolSeqList::Empty(){if(length==0){return1;}else{return0;}}(11)求直接前驱结点算法/**输入：要查找的元素e，待存放前驱结点值e1*前置条件：无*功能：查找该元素的所在位置，获得其前驱所在位置。*输出：返回其前驱结点的位序。*后置条件：e1值为前驱结点的值*/实现代码：templateintSeqList::Pre(datatypeitem){intk=Locate(item)-1;if(k>0)returnk;else{cout<<return0;}}(12)求直接后继结点算法/**输入：要查找的元素e，待存放后继结点值e1*前置条件：无*功能：查找该元素的所在位置，获得其后继所在位置。*输出：返回其后继结点的位序。*后置条件：e1值为后继结点的值*/实现代码：templateintSeqList::Suc(datatypeitem){intk=Locate(item)+1;if(k>length){cout<<returnk;}}上机实现以上基本操作，写出main()程序：voidmain(){SeqListSeq;//创建if(Seq.Empty()){cout<<“线性表为空!”<}Seq.Insert(1,1);Seq.Insert(2,2);Seq.Insert(3,3);Seq.Insert(4,4);Seq.Insert(5,5);//插入元素操作cout<<cout<cout<<“2是第”<cout<<cout<<“线性表的长度为:”<Seq.Delete(3);//删除元素cout<<cout<cout<<cout<<cout<<要求对每个算法都加以测试，判断是否正确；并测试不同类型数据的操作。粘贴测试数据及运行结果：2、用以上基本操作算法，实现A=AUB算法。（利用函数模板实现）/**输入：集合A,集合B*前置条件：无*功能：实现A=AUB*输出：无*后置条件：A中添加了B中的元素。*/实现代码：templateSeqListSeqList::Add(SeqList&item){if(item.Empty())return*this;else{intk=item.Length();intnum=this->Length();for(inti=1;i<=k;i++){for(intj=