数据结构第1次实验内容及报告书

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：线性表数据结构试验班级：计算机132学号：2013122753姓名：魏红云评语：评语：成绩：指导教师：批阅时间：年月日《数据结构》实验报告 -PAGE1-线性表实验报告要求1目的与要求:1）掌握线性表数据结构的基本概念和抽象数据类型描述；2）熟练掌握线性表数据结构的顺序和链式存储存表示；3）熟练掌握线性表顺序存储结构的基本操作算法实现；4）熟练掌握线性表的链式存储结构的基本操作算法实现;5）掌握线性表在实际问题中的应用和基本编程技巧;6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；7）按照报告格式和内容要求，认真书写实验报告，并在试验课后第三天（下周一以前）将编写好的实验报告电子文档（同学编写实验报告文件命名方式：姓名+学号+数据结构第X次实验报告）提交给学委，而后由学委统一打包（包文件名为：计算机13X班-数据结构第X次实验报告）和纸质报告（每班每次收5份，学委安排，保证每个同学至少提交一次）一起提交给老师。凡逾期不交报告者，不再单独接收，均做旷交处理；8）积极开展实验组组内交流和辅导，严禁复制和剽窃他人实验成果，一旦发现严肃处理；9）上实验课前，要求每个同学基本写好程序，并存储在自己的U盘上，用于实验课堂操作时调试和运行。凡不做准备，没有提前编写程序者，拒绝上机试验。2实验内容或题目（在一个程序中实现全部题目）一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入）的顺序存储结构（即顺序表），长度限定在25之内；2）打印/显示（遍历）该线性表（依次打印/显示出表中元素值）；3）在顺序表中查找第i个元素，并返回其值；4）在顺序表第i个元素之前插入一已知元素；5）在顺序表中删除第i个元素；6）求顺序表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。按照动态单链表结构实现如下算法：1）按照头插法或尾插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在10之内；2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中第i个结点之前插入一个新结点；6）在线性表中删除第i个结点；7）计算链表的长度。3实验步骤与源程序步骤：1：看清题目，理解题目2：分析方法，画大致流程图（用C++的方法，构造函数再调用）3：整合程序代码4：调试纠错再调试直至成功第一题源程序：#include"iostream.h"#defineMaxSize25typedefintDataType;classSeqList{DataTypelist[MaxSize];intlength;public:SeqList(){length=0;}voidSLCreat(intn);voidSLInsert(inti,DataTypex);voidSLDelete(inti);DataTypeSLGet(inti);DataTypeSLSum();intSLIsEmpty();voidSLPrint();};voidSeqList::SLCreat(intn){DataTypex;cout<<"请输入数据元素值:";for(inti=0;i<n;i++){cin>>x;list[i]=x;length++;}}voidSeqList::SLInsert(inti,DataTypex){intk;if(length>=MaxSize)cout<<"表已满,无法插入!"<<endl;elseif(i<0||i>length)cout<<"参数i不合理!"<<endl;else{for(k=length;k>i;k--){list[k]=list[k-1];}list[i]=list[i-1];list[i-1]=x;length++;}}voidSeqList::SLDelete(inti){intk;if(!SLIsEmpty())cout<<"表已空,无法删除!"<<endl;elseif(i<0||i>length)cout<<"参数i不合理!"<<endl;else{for(k=i-1;k<length;k++)list[k]=list[k+1];length--;}}DataTypeSeqList::SLGet(inti){if(i<0||i>length){cout<<"参数i不合理!"<<endl;return0;}elsereturnlist[i-1];}intSeqList::SLIsEmpty(){if(length<=0)return0;elsereturn1;}voidSeqList::SLPrint(){if(!SLIsEmpty())cout<<"空表!"<<endl;elsefor(inti=0;i<length;i++)cout<<list[i]<<"";cout<<endl;}DataTypeSeqList::SLSum(){intm=0;for(inti=0;i<length;i++){m=m+list[i];}returnm;}voidmain(){SeqListmylist;inti,n,flag=1,select;DataTypex;cout<<"1.建立线性表\n";cout<<"2.查找\n";cout<<"3.插入\n";cout<<"4.删除\n";cout<<"5.求和\n";cout<<"6.显示\n";cout<<"7.退出\n";while(flag){cout<<"请选择:";cin>>select;switch(select){case1:cout<<"请输入线性表长度:";cin>>n;mylist.SLCreat(n);cout<<"线性表为：";mylist.SLPrint();break;case2:cout<<"请输入位置i:";cin>>i;cout<<"第"<<i<<"个位置上的数值为:"<<mylist.SLGet(i)<<endl;break;case3:cout<<"请输入要插入元素的位置i和数值x:";cin>>i>>x;mylist.SLInsert(i,x);mylist.SLPrint();break;case4:cout<<"请输入要删除的数值的位置:";cin>>i;mylist.SLDelete(i);cout<<"删除后的线性表为:";mylist.SLPrint();break;case5:cout<<"求和的值："<<mylist.SLSum()<<endl;break;case6:cout<<"线性表为:";mylist.SLPrint();break;case7:flag=0;break;}}}第二题源程序：#include<iostream>#include<malloc.h>#defineFALSE0#defineTRUE1#defineOK1#defineERROR0#defineMaxSize10usingnamespacestd;typedefcharElemType;typedefstructNode{ElemTypedata;Node*next;}Node,*LinkList;intInitList_L(LinkList*L){*L=(LinkList)malloc(sizeof(Node));if(!L)exit(FALSE);(*L)->next=NULL;returnTRUE;}voidqcreate(LinkListL){Node*s;charc;intflag=1;while(flag){c=getchar();if(c!='$'){s=(Node*)malloc(sizeof(Node));s->data=c;s->next=L->next;L->next=s;}elseflag=0;}}voidlength(LinkListL){Node*p;p=L->next;intj=0;while(p!=NULL){p=p->next;j++;}printf("%d",j);printf("\n");}voidprintf(LinkListL){LinkListp;p=L;while(p->next!=NULL){ p=p->next;printf("%c",p->data); }printf("\n");}voidGet(LinkListL,inti){intj;Node*p;p=L;j=0;while((p->next!=NULL)&&(j<i)){p=p->next;j++;}if(i==j)printf("%c",p->data);elseprintf("NULL");printf("\n");}voidGetchar(LinkList&L){charn;cout<<"输入这个元素:";cin>>n;LinkListp;p=L;while(p->data!=n) {if(p->next==NULL)printf("FALSE");p=p->next; }printf("TRUE");}voidcins(LinkListL,inti,ElemTypex){Node*pre,*s;intk;pre=L;k=0;while(pre!=NULL&&k<i-1){pre=pre->next;k=k+1;}if(!pre){printf("插入位置不合理!");}s=(Node*)malloc(sizeof(Node));s->data=x;s->next=pre->next;pre->next=s;printf("插入成功!链表为：");}voiddel(LinkListL,inti){Node*pre,*r;intk;pre=L;k=0;while(pre->next!=NULL&&k<i-1){pre=pre->next;k=k+1;}if(!(pre->next)){printf("删除结点的位置i不合理!");}r=pre->next;pre->next=pre->next->next;free(r);printf("成功删除结点!链表为:");}voidmain(){LinkListL;InitList_L(&L);inte,i;charx;intflag=1;printf("请输入元素并以$结束：\n");qcreate(L);printf(L);while(flag){printf("请选择操作:");printf("\n");printf("1.插入");printf("\n");printf("2.删除");printf("\n");printf("3.查找");printf("\n");printf("4.求长");printf("\n");printf("5.是否能在表中找到与x相同的数值");printf("\n");printf("6.显示");printf("\n");printf("7.退出");cin>>