数据结构实验报告实验四

数据结构实验报告第四次实验学号：20111060067姓名：段文龙专业：计科一、实验目的一、实验目的：1.加深对逻辑结构和物理结构（存储结构）的了解，理解基本操作的意义是定义在逻辑结构上，基本操作的实现是在存储结构上2.掌握线性表（逻辑结构）的一种实现方式：顺序映象。3.基于顺序映象实现一些基本操作4.实现有序线性表的归并。5.删除线性表中某个序号的元素二、实验内容：1．数据元素是结构体，从键盘输入结构体，结构体包含2个域：name,score。2.实现Initlist;orderandshowList;ListLength;GetElem;ListInsert;ListDelete;这几个基本操作3.通过调用基本操作实现MergeList。测试数据是按分数有序,归并后按分数有序。第1个线性表：zhao90;qiang85;sun61;li53第2个线性表：zhou94;wu81;zhen722.删除归并后线性表中的第5个元素；三、算法描述（给出自然语言描述的算法）1.初值化ListA、ListB,并构造一个空的线性表ListC，且线性表中的数据元素包含name和score两个域，并且显示ListA，ListB2.依次比较ListA和ListB中数据元素的score值，较大者插入ListC，直到ListA和ListB其中一个线性表中所有的数据元素全部插入到ListC后停止比较。3将另一个线性表剩余所有数据元素插入ListC，并显示线性表ListC。4.删除ListC线性表中的第5个数据元素，然后显示线性表ListC。四、详细设计（画流程图）另一个线性表剩余所有元素插入线性表ListC较大者进入ListC线性表YesNo比较List另一个线性表剩余所有元素插入线性表ListC较大者进入ListC线性表YesNo比较ListA和ListB中未插入线性表ListC的数据元素的score值ListA或ListB是否为空比较ListA和ListB的数据元素的score值初始化初始化ListA和ListB，并构造空的线性表ListC。然后显示ListA和ListB。显示ListC线性表删除List显示ListC线性表删除ListC线性表中的第5个数据元素，然后显示ListC线性表五、程序代码#include<stdio.h>#include<stdlib.h>#defineok1#defineerror0#defineOVERFLOW-2typedefstructstudent{ charname[10]; intscore;}ElemType;typedefintstatus;#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}Sqlist;statusInitlist(Sqlist&L);voidorderandshowList(SqlistL);intListLength(SqlistL);statusGetElem(SqlistL,inti,ElemType&e);statusListInsert(Sqlist&L,inti,ElemTypee);statusMergeList(SqlistLa,SqlistLb,Sqlist&Lc);statusListDelete(Sqlist&L,inti,ElemType&e);main(){SqlistListA,ListB,ListC;inti;ElemTypee;printf("初始化第1个线性表!\n");if(!Initlist(ListA))return(0);printf("初始化第2个线性表!\n");if(!Initlist(ListB))return(0);printf("初始化第3个线性表为空表!\n");if(!Initlist(ListC))return(0);printf("要归并的线性表是下面两个：\n");orderandshowList(ListA);orderandshowList(ListB);if(!MergeList(ListA,ListB,ListC))return(1);printf("归并后的线性表是：\n");orderandshowList(ListC);printf("请输入第3个表中要删除元素的序号:");scanf("%d",&i);if(!ListDelete(ListC,i,e))return(1);orderandshowList(ListC);return(1);}statusInitlist(Sqlist&s){inti,n;s.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!s.elem)exit(-1);printf("请输入存入数组中的元素个数（最多%d个）：",LIST_INIT_SIZE);scanf("%d",&n);if(n>LIST_INIT_SIZE)return(error);for(i=0;i<n;i++){printf("请输入第%d个学生的信息（姓名，成绩）:",i+1);scanf("%s%d",&s.elem[i].name,&s.elem[i].score);}s.length=n;s.listsize=LIST_INIT_SIZE;returnok;}voidorderandshowList(SqlistL){inti;printf("这个线性表是:");for(i=0;i<L.length;i++)printf("%s%d；",L.elem[i].name,L.elem[i].score);printf("\n");return;}intListLength(SqlistL){return(L.length);}statusGetElem(SqlistL,inti,ElemType&e){if(i<1||i>L.length)return(error);e=L.elem[i-1];return(ok);}statusListInsert(Sqlist&L,inti,ElemTypee){ElemType*newbase,*p,*q;if(i<1||i>L.length+1)returnerror;if(L.length==L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=L.listsize+LISTINCREMENT;}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnok;}statusMergeList(SqlistLa,SqlistLb,Sqlist&Lc){inti,j,k,La_len,Lb_len;ElemTypeai,bj;i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=La_len)&&(j<=Lb_len)){if(!GetElem(La,i,ai))return(error);if(!GetElem(Lb,j,bj))return(error);if(ai.score>=bj.score){if(!ListInsert(Lc,++k,ai))return(error);++i;}else{if(!ListInsert(Lc,++k,bj))return(error);++j;}}while(i<=La_len){if(!GetElem(La,i++,ai))return(error);if(!ListInsert(Lc,++k,ai))return(error);}while(j<=Lb_len){if(!GetElem(Lb,j++,bj))return(error);if(!ListInsert(Lc,++k,bj))return(error);}return(ok);}statusListDelete(Sqlist&L,inti,ElemType&e){ElemType*p,*q;if(i<1||i>L.length)returnerror;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.