73数据结构实验报告

1桂林航天工业学院实验报告系（部）：计算机科学与工程系课程名称:数据结构专业班级:计算机应用技术1班学号:20150703Z0144学生姓名:农小艺完成日期：2016年12月22日2实验一实验名称线性表的顺序存储实验日期实验目的1.掌握线性表的顺序存储结构。2.能熟练利用顺序存储结构实现线性表的基本操作。3.能熟练掌握线性表创建、插入、删除、查找和显示线性表中元素等基本操作。实验内容1．建立含有不少于3个元素的顺序表，并将结果在屏幕上输出。2.对刚建立的顺序表实现插入、删除、查找，并将结果在屏幕上输出。3．设计一个选择式菜单。算法描述：#includestdio.h#includemalloc.h#defineMAXSIZE200//线性表允许的最大长度#definedatatypeinttypedefstruct//定义线性表的结构{datatypedata[MAXSIZE];//表示线性表（a1，a2，….,an）intlast;//last表示线性表的实际长度}SeqList;/*线性表初始化：Init_List(L)初始条件：表L不存在操作结果：构造一个空的线性表*/SeqList*init_SeqList(){SeqList*L;L=(SeqList*)malloc(sizeof(SeqList));L-last=-1;returnL;}/*插入操作：Insert_List(L,i,x)初始条件：线性表L存在，插入位置正确(1=i=n+1,ｎ为插入前的表长)。操作结果：在线性表L的第i个位置上插入一个值为x的新元素，这样使原序号为i,i+1,...,n的数据元素的序号变为i+1,i+2,...,n+1，插入后表长=原表长+1。*/intInsert_SeqList(SeqList*L,inti,datatypex){intj;if(L-last==MAXSIZE-1){printf(空间满);return0;}3elseif(i1||iL-last+2){printf(位置错误);return0;}for(j=L-last;j=i-1;j--){L-data[j+1]=L-data[j];}L-data[i-1]=x;L-last++;return1;}/*删除操作：Delete_List(L,i)初始条件：线性表L存在，1=i=n。操作结果：在线性表L中删除序号为i的数据元素，删除后使序号为i+1,i+2,...,n的元素变为序号为i,i+1,...,n-1，删除后新表长＝原表长－１。*/intDelete_SeqList(SeqList*L,inti){intj;if(i1||iL-last+1){printf(元素不存在);return0;}for(j=i;j=L-last;j++){L-data[j-1]=L-data[j];}L-last--;return1;}/*按值查找：Locate_List(L,x)，ｘ是给定的一个数据元素。初始条件：线性表L存在操作结果：在表L中查找值为ｘ的数据元素，其结果返回在L中首次出现的值为ｘ的那个元素的序号或地址，称为查找成功;否则，在L中未找到值为ｘ的数据元素，返回一特殊值表示查找失败。*/intLocation_SeqList(SeqList*L,datatypex){inty=0;4while(y=L-last&&L-data[y]!=x)y++;if(yL-last)return-1;elsereturny;}voidprint(SeqList*L)//打印线性表{inti;for(i=0;i=L-last;i++)printf(%d,,L-data[i]);printf(\n);}voidmain(){SeqList*L;inti,j,k;datatypex;do{printf(\n\n\n\n);printf(\t\t\t线性表子系统\n);printf(\t\t*******************************\n);printf(\t\t*1----初始化表*\n);printf(\t\t*2----插入*\n);printf(\t\t*3----删除*\n);printf(\t\t*4----查找*\n);printf(\t\t*5----显示*\n);printf(\t\t*0----返回*\n);printf(\t\t*******************************\n);printf(\t\t请选择菜单项(0－5)：);scanf(%d,&k);getchar();switch(k){case1:L=init_SeqList();//初始化线性表break;case2://在线性表第i位置处插入值为X的元素printf(\n请输入插入的位置i和数据X(输入格式：i,X):);scanf(%d,%d,&i,&x);j=Insert_SeqList(L,i,x);break;case3://删除线性表中值为X的元素5printf(\n请输入要删除元素的位置i:);scanf(%d,&i);j=Delete_SeqList(L,i);if(j==1)printf(删除成功!!);elseprintf(删除失败!!);break;case4://查找线性表中元素值为x的位置printf(\n请输入要查找的数值X:);scanf(%d,&x);j=Location_SeqList(L,x);if(j!=-1){print(L);printf(中值为X所在的位置是%d,j);}elseprintf(线性表中无此元素!!\n);break;case5://输出线性表printf(\n线性表的顺序存储为：);print(L);}}while(k!=0);}运行结果6实验人员实验地点教师评语优良中及格不及格批改日期7实验二实验名称线性表的链式存储实验日期实验目的1.掌握线性表的链式存储结构。2.能熟练利用链式存储结构实现线性表的基本操作。3.能熟练掌握链式存储结构中算法的实现。实验内容1.用头插法或尾插法建立带头结点的单链表，并在屏幕上输出显示此链表。2.实现单链表上的插入、删除、修改、查找、计数等操作，并将结果在屏幕上输出。3．设计一个选择式菜单。算法描述：#includestdio.h#includemalloc.h#definedatatypeinttypedefstructnode{datatypedata;//链表的数据域structnode*next;//链表的指针域}LNode,*LinkList;LinkListCreat_LinkList1()//头插入法建立单链表算法{datatypec;LinkListhead;LNode*p,*r;head=(LNode*)malloc(sizeof(LNode));r=head;printf(请输入数据);scanf(%d,&c);while(c!=0){p=(LNode*)malloc(sizeof(LNode));p-data=c;r-next=p;r=p;scanf(%d,&c);}r-next=NULL;returnhead;}8/*按序号查找Get_Linklist(L,i)在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/LNode*Get_LinkList(LinkListL,inti){intj;LNode*p;p=L;j=0;while(p-next&&ji){p=p-next;j++;}if(i==j){returnp;}elsereturnNULL;}/*插入运算Insert_LinkList(L,i,x)在单链表L的第i个位置上插入值为x的元素*/intInsert_LinkList(LinkListL,inti,datatypex){LNode*p,*q;intj;p=L;j=0;while(p-next&&ji-1){p=p-next;++j;}if(p==NULL){printf(位置错误);return0;}else{9q=(LNode*)malloc(sizeof(LNode));q-data=x;q-next=p-next;p-next=q;return1;}}/*删除运算：Del_LinkList(L,i)删除单链表L上的第i个数据结点*/intDel_LinkList(LinkListL,inti){LNode*p,*q;intj;p=L;j=0;while(p-next&&ji-1){p=p-next;++j;}if(!(p-next)){return0;}else{q=p-next;p-next=q-next;free(q);return1;}}voidprint(LinkListL)//输出单链表{LNode*p=L;while(p-next!=NULL){printf(%d-,p-data);//输出表中非最后一个元素p=p-next;}10printf(%d\n,p-data);//输出表中最后一个元素}voidmain(){LinkListH;inti,j,k;datatypex;do{printf(\n\n\n\n);printf(\t\t\t链表子系统\n);printf(\t\t*******************************\n);printf(\t\t*1----建表*\n);printf(\t\t*2----插入*\n);printf(\t\t*3----删除*\n);printf(\t\t*4----查找*\n);printf(\t\t*5----显示*\n);printf(\t\t*0----返回*\n);printf(\t\t*******************************\n);printf(\t\t请选择菜单项(0－5)：);scanf(%d,&k);getchar();if(k==1)H=Creat_LinkList1();//用头插入法建立单链表elseif(k==2)//在线性表第i位置处插入值为X的元素{printf(\n请输入插入的位置i和数据X(输入格式：i,X):);scanf(%d,%d,&i,&x);j=Insert_LinkList(H,i,x);}elseif(k==3){printf(\n请输入要删除元素的位置i:);scanf(%d,&i);j=Del_LinkList(H,i);if(j==1)printf(删除成功!!);elseprintf(删除失败!!);}elseif(k==4)//查找线性表中元素值为x的位置{printf(\n请输入要查找的序号i:);scanf(%d,&i);LNode*p;11p=Get_LinkList(H,i);if(p!=NULL){print(H);printf(中序号为i的地址是%d,p);}elseprintf(链表中无此序号!!\n);}elseif(k==5)//输出链表{printf(\n表的存储顺序为：);print(H);}}while(k!=0);}运行结果12实验人员实验地点教师评语优良中及格不及格批改日期实验三实验名称栈的应用实验日期实验目的1.掌握栈的数据类型描述及栈的特点。2.掌握栈的顺序和链式两种存储结构的特点及算法描述。3.掌握栈的5种基本运算及算法在两种不同存储结构上的实现。实验内容1．编写链式栈进栈、出栈、显示栈中全部元素的程序。2．将一个正整数n转换成R进制，要求用顺序栈的来实现。3．用switch语句设计一个选择式菜单，以菜单方式执行上述操作。算法描述：#includestdio.h#includemalloc.htypedefintdatatype;typedefstructnode//定义链式栈结构{datatypedata;struct