搜索
实验名称顺序表的基本操作实验日期2019.9.23实验成绩1、实验目的：1．掌握线性表的顺序存储结构的表示和实现方法。2．掌握顺序表基本操作的算法实现。3．了解顺序表的应用。2、实验内容：编写一个程序，实现顺序表的各种基本运算（假设顺序表的元素类型为char），并在此基础上设计一个主程序完成如下功能：（1）初始化顺序表L；（2）依次采用尾插法插入a、b、c、d、e元素；（3）输出顺序表L；（4）输出顺序表L的长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第3个元素；（7）输出元素a的位置（8）在第4个元素位置上插入f元素（9）输出顺序表L；（10）删除L的第3个元素；（11）输出顺序表L；（12）释放顺序表L。3、核心算法或代码片段：核心算法：1．顺序表插入操作的基本步骤：要在顺序表中第i个数据元素之前插入一个数据元素x，首先要判断插入位置i是否合法，假设线性表的长为n，则i的合法值范围：1≤i≤n+1，若是合法位置，就再判断顺序表否满，如果满，则增加空间或结束操作，如果不满，则将第i个数据元素及其之后的所有数据元素都后移一个位置，此时第i个位置已经腾空，再将待插入的数据元素x插入到该位置上，最后将线性表的长增加1。2．顺序表删除操作的基本步骤：要删除顺序表中第i个数据元素，首先仍然要判断i的合法性，i的合法范围是1≤i≤n，若是合法位置，则将第i个数据元素之后的所有数据都前移一个位置，最将线性表长减1。3．顺序表查找操作的基本步骤：要在顺序表中查找一个给定值的数据元素则可以采用顺序查找的方法，从表中第1个数据元素开始依次将值与给定值进行比较，若相等则返回该数据元素在顺序表中的位置，否则返回0值。线性表的动态分配顺序存储结构—C语言实现#defineMaxSize50//存储空间的分配量TypedefcharElemType；Typedefstruct{ElemTypedata[MaxSize];intlength;//表长度（表中有多少个元素）}SqList;动态创建一个空顺序表的算法：voidInitList(SqList*&L)//初始化线性表{L=(SqList*)malloc(sizeof(SqList));//分配存放线性表的空间L-length=0;//置空线性表长度为0}线性表的插入：statusSqlist_insert(Sqlist&L,inti,Elemtypex)/*在顺序表L中第i个元素前插入新元素x*/{if(i1||iL.length+1)returnERROR;/*插入位置不正确则出错*/if(L.length=MAXLEN)returnOVERFLOW;/*顺序表L中已放满元素，再做插入操作则溢出*/for(j=L.length-1;j=i-1;j--)L.elem[j+1]=L.elem[j];/*将第i个元素及后续元素位置向后移一位*/L.elem[i-1]=x;/*在第i个元素位置处插入新元素x*/L.length++;/*顺序表L的长度加1*/returnOK;}线性表的删除：statusSqlist_delete(Sqlist&L,inti,Elemtype&e)/*在顺序表L中删除第i个元素*{if(i1||iL.length)returnERROR;/*删除位置不正确则出错*/for(j=i;j=L.length-1;j++)L.elem[j-1]=L.elem[j];/*将第i+1个元素及后继元素位置向前移一位*/L.length--;/*顺序表L的长度减1*/returnOK；}线性表元素的查找：intLocateElem(SqList*L,ElemTypee)//按元素值查找{inti=0;while(iL-length&&L-data[i]!=e)i++;//查找元素eif(i=L-length)//未找到时返回0return0;elsereturni+1;//找到后返回其逻辑序号}输出线性表：voidDispList(SqList*L)//输出线性表{inti;if(ListEmpty(L))return;for(i=0;iL-length;i++)printf(%c,L-data[i]);printf(\n);}输出线性表第i个元素的值：boolGetElem(SqList*L,inti,ElemType&e)//求线性表中某个数据元素值{if(i1||iL-length)returnfalse;//参数错误时返回falsee=L-data[i-1];//取元素值returntrue;//成功找到元素时返回true}代码：#includestdio.h#includemalloc.h#defineMaxSize50typedefcharElemType;typedefstruct{ElemTypedata[MaxSize];intlength;}SqList;voidInitList(SqList*&L);voidDestroyList(SqList*L);boolListEmpty(SqList*L);intListLength(SqList*L);voidDispList(SqList*L);boolGetElem(SqList*L,inti,ElemType&e);intLocateElem(SqList*L,ElemTypee);boolListInsert(SqList*&L,inti,ElemTypee);boolListDelete(SqList*&L,inti,ElemType&e);voidInitList(SqList*&L)//初始化线性表{L=(SqList*)malloc(sizeof(SqList));//分配存放线性表的空间L-length=0;//置空线性表长度为0}voidDestroyList(SqList*L)//销毁线性表{free(L);}boolListEmpty(SqList*L)//判线性表是否为空表{return(L-length==0);}intListLength(SqList*L)//求线性表的长度{return(L-length);}voidDispList(SqList*L)//输出线性表{inti;if(ListEmpty(L))return;for(i=0;iL-length;i++)printf(%c,L-data[i]);printf(\n);}boolGetElem(SqList*L,inti,ElemType&e)//求线性表中某个数据元素值{if(i1||iL-length)returnfalse;//参数错误时返回falsee=L-data[i-1];//取元素值returntrue;//成功找到元素时返回true}intLocateElem(SqList*L,ElemTypee)//按元素值查找{inti=0;while(iL-length&&L-data[i]!=e)i++;//查找元素eif(i=L-length)//未找到时返回0return0;elsereturni+1;//找到后返回其逻辑序号}boolListInsert(SqList*&L,inti,ElemTypee)//插入数据元素{intj;if(i1||iL-length+1)returnfalse;//参数错误时返回falsei--;//将顺序表逻辑序号转化为物理序号for(j=L-length;ji;j--)//将data[i]及后面元素后移一个位置L-data[j]=L-data[j-1];L-data[i]=e;//插入元素eL-length++;//顺序表长度增1returntrue;//成功插入返回true}boolListDelete(SqList*&L,inti,ElemType&e)//删除数据元素{intj;if(i1||iL-length)//参数错误时返回falsereturnfalse;i--;//将顺序表逻辑序号转化为物理序号e=L-data[i];for(j=i;jL-length-1;j++)//将data[i]之后的元素前移一个位置L-data[j]=L-data[j+1];L-length--;//顺序表长度减1returntrue;//成功删除返回true}voidmain(){SqList*L;ElemTypee;printf(顺序表的基本运算如下:\n);printf((1)初始化顺序表L\n);InitList(L);printf((2)依次采用尾插法插入a,b,c,d,e元素\n);ListInsert(L,1,'a');ListInsert(L,2,'b');ListInsert(L,3,'c');ListInsert(L,4,'d');ListInsert(L,5,'e');printf((3)输出顺序表L:);DispList(L);printf((4)顺序表L长度=%d\n,ListLength(L));printf((5)顺序表L为%s\n,(ListEmpty(L)?空:非空));GetElem(L,3,e);printf((6)顺序表L的第3个元素=%c\n,e);printf((7)元素a的位置=%d\n,LocateElem(L,'a'));printf((8)在第4个元素位置上插入f元素\n);ListInsert(L,4,'f');printf((9)输出顺序表L:);DispList(L);printf((10)删除L的第3个元素\n);ListDelete(L,3,e);printf((11)输出顺序表L:);DispList(L);printf((12)释放顺序表L\n);DestroyList(L);}4、实验结果分析及总结体会：实验结果：心得体会：通过本次实验，实现了数据结构在程序设计上的作用，了解了数据结构语言，加深了对c语言的认识掌并掌握了线性表的顺序存储结构的表示和实现方法，掌握顺序表基本操作的算法实现，同时了解了顺序表的应用。