中国石油大学(北京)数据结构上机实验1

《数据结构》实验报告学号2015011512姓名胡明禹专业数学与应用数学时间2018.3.20一、实验题目实验1顺序表基本操作二、实验目的1.熟练掌握线性表的顺序存储方式下，基本操作的实现算法，巩固和体会顺序表操作特点；2.理解动态内存分配；3.通过本次实验，熟练掌握C语言中函数调用、参数传递、结构体类型的使用。三、算法设计分析（一）数据结构的定义数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。例如：1.初始化一个空的顺序表的函数；2.输入并赋值的函数；3.顺序表的展示函数；4.顺序表的插入函数；5.顺序表的删除函数；6.顺序表的查找函数7.销毁函数。其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能voidmain()（2）①初始化一个空的顺序表的函数StatusInitList_Sq(SqList&La){//构建一个新的的空的表La.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!La.elem)exit(OVERFLOW);//存储分配失败La.length=0;//空表长度为0La.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_Sq②输入并赋值的函数：StatusInitInput_Sq(SqList&La){system(cls);//清屏ElemTypee;ElemType*newbase;chara[1];//1个元素的数组printf(请输入:);scanf(%d,&e);La.elem[La.length]=e;//给元素进行赋值++La.length;//表长加一if(La.length=La.listsize)//当前存储空间已满，增加分配{newbase=(ElemType*)realloc(La.elem,(La.listsize+LISTINCREMENT)*sizeof(ElemType));if(newbase==NULL)exit(OVERFLOW);//存储分配失败La.elem=newbase;//新地址La.listsize+=LISTINCREMENT;//增加存储容量}printf(\n创建成功。\n);printf(\n是否继续创建(y或n)：);//一个一个得进行赋值，会在截图里有所体现scanf(%s,a);if(a[0]=='y')//如果是继续创建，返回调用赋值的函数InitInput_Sq(La);if(a[0]=='n')//如果不是继续创建，创建结束printf(\n新表创建完成。\n);returnOK;}③顺序表的展示函数：StatusListOutput_Sq(SqList&La)//展示顺序线性表的函数{system(cls);//清屏ElemTypei;chara[1];//1个元素的数组printf(线性表：\n);for(i=0;iLa.length;i++)//输出操作循环语句{printf(%d\t,La.elem[i]);}printf(\n是否重新操作(y或n)：);scanf(%s,&a);if(a[0]=='y')//条件判断语句printf(\n重新选择\n);if(a[0]=='n')exit(0);returnOK;}④顺序表的插入函数：StatusListInsert_Sq(SqList&La)//新元素插入的函数{system(cls);//清屏inti;ElemTypee;ElemType*newbase;ElemType*q,*p;printf(请输入插入位置，数字：\n);scanf(%d,%d,&i,&e);if(i1||iLa.length+1)returnERROR;//i值插入的位置不合法if(La.length=La.listsize)//当前存储空间已满，增加分配{newbase=(ElemType*)realloc(La.elem,(La.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败La.elem=newbase;//新基址La.listsize+=LISTINCREMENT;//增加存储容量}//ifq=&(La.elem[i-1]);//q为插入位置for(p=&(La.elem[La.length-1]);p=q;--p)//循环操作，插入位置及之后的元素右移*(p+1)=*p;*q=e;//插入e++La.length;//表长加一returnOK;}⑤顺序表的删除函数：StatusListDelete_Sq(SqList&La){//在顺序线性表中删除第i个元素，并用e返回其值system(cls);//清屏inti;ElemTypee;ElemType*q,*p;printf(请输入删除数据的位置：\n);scanf(%d,&i);if(i1||iLa.length)returnERROR;//i值位置删除得不合法p=&(La.elem[i-1]);//p为删除元素的位置e=*p;//被删除的元素的值赋给eq=La.elem+La.length-1;//表尾元素的位置for(++p;p=q;++p)*(p-1)=*p;//被删除元素之后的元素左移--La.length;//表长减一returnOK;}//ListDelete_Sq⑥：查找元素的函数：StatusLocateElem_Sq(SqList&La)//在顺序线性表L中查找第1个值与e满足compare()的元素的位序{system(cls);//清屏chara[2];ElemTypei=1;ElemTypee;printf(请输入查找数字：\n);scanf(%d,&e);while(i=La.length)//必须查找的位置要小于等于最后一个元素的位置{if(e==La.elem[i-1])//遍历查询{printf(\n该元素所在位置：%d,i);//找到，则返回其在L中的位序，否则返回0break;}++i;}if(iLa.length)//如果i大于表长printf(\n元素不存在！\n);printf(\n是否继续查询(y或者n)：);scanf(%s,&a);if(a[0]=='y')//条件判断语句LocateElem_Sq(La);if(a[0]=='n')//条件判断语句printf(\n查询结束\n);returnOK;}⑦销毁函数：voidDestroyList_Sq(SqList&La)//销毁顺序线性表{system(cls);//清屏chara[1];free(La.elem);//释放元素La.length=NULL;//表长为空La.listsize=LIST_INIT_SIZE;printf(已销毁！);printf(\n是否重新操作(y或n)：);scanf(%s,&a);if(a[0]=='y')//条件判断语句printf(\n重新选择\n);if(a[0]=='n')//条件判断语句exit(0);}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）（二）结果分析成功完成了题目所要求的插入，删除，查找等基本操作。五、实验总结附录实验程序代码(该部分请加注释)#includestdio.h#includestdlib.h#includemalloc.h#includestring.h#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT2//线性表存储空间的分配增量#defineMAX10000#defineOVERFLOW-2#defineOK1#defineERROR0typedefintElemType;//元素数据类型typedefintStatus;typedefstruct{ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;StatusInitList_Sq(SqList&La){//构建一个新的的空的表La.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!La.elem)exit(OVERFLOW);//存储分配失败La.length=0;//空表长度为0La.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_SqStatusInitInput_Sq(SqList&La){system(cls);//清屏ElemTypee;ElemType*newbase;chara[1];//1个元素的数组printf(请输入:);scanf(%d,&e);La.elem[La.length]=e;//给元素进行赋值++La.length;//表长加一if(La.length=La.listsize)//当前存储空间已满，增加分配{newbase=(ElemType*)realloc(La.elem,(La.listsize+LISTINCREMENT)*sizeof(ElemType));if(newbase==NULL)exit(OVERFLOW);//存储分配失败La.elem=newbase;//新地址La.listsize+=LISTINCREMENT;//增加存储容量}printf(\n创建成功。\n);printf(\n是否继续创建(y或n)：);//一个一个得进行赋值，会在截图里有所体现scanf(%s,a);if(a[0]=='y')//如果是继续创建，返回调用赋值的函数InitInput_Sq(La);if(a[0]=='n')//如果不是继续创建，创建结束printf(\n新表创建完成。\n);returnOK;}StatusListOutput_Sq(SqList&La)//展示顺序线性表的函数{system(cls);//清屏ElemTypei;chara[1];//1个元素的数组printf(线性表：\n);for(i=0;iLa.length;i++)//输出操作循环语句{printf(%d\t,La.elem[i]);}printf(\n是否重新操作(y或n)：);scanf(%s,&a);if(a[0]=='y')//条件判断语句printf(\n重新选择\n);if(a[0]=='n')exit(0);returnOK;}StatusListInsert_Sq(SqList&La)//新元素插入的函数{system(cls);//清屏inti;ElemTypee;ElemType*newbase;ElemType*q,*p;printf(请输入插入位置，数字：\n);scanf(%d,%d,&i,&e);if(i1||iLa.length+1)returnERROR;//i值插入的位置不合法if(La.length=La.listsize)//当前存储空间已满，增加分配{newbase=(ElemType*)realloc(La.elem,(La.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败La.elem=newbase;//新基址La.listsize+=LISTINCREMENT;//增加存储容量}//ifq=&(La.elem[i-1]);//q为插入位置for(p=&(La.elem[La.length-1])