线性表的顺序存储结构和实现

石家庄经济学院实验报告学院:数理学院专业：数学与应用数学班级:_班学号:XXXXXXXX姓名:XXXXXX信息工程学院计算机实验中心制实验题目：线性表的顺序存储结构和实现一、实验内容熟悉C语言的上机环境，掌握C语言的基本结构。会定义线性表的顺序存储结构。熟悉对顺序表的一些基本操作(建表、插入、删除等)和具体的函数定义。二、、实握顺序存储结构的特点掌握顺序存储结构的常见算法3、掌握顺序存储结构的特点，了解、掌握并实现顺序表的常用的基本算法。三、实验的内容及完成情况需求分析线性表的抽象数据类型ADT的描述及实现。本实验实现使用Visualc++6.0实现线性表顺序存储结构的表示及操作。具体实现要求：完成对线性表顺序存储结构的表示和实现。实现对线性表的建立和初始化。实现对线性表插入和删除部分元素。概要设计抽象数据类型线性表的定义：ADT{数据对象：D=(ailai^ElemSet,i=1,2,,n,n>0)数据关系：R1={<ai-i，ai>lai-i，aieD，i=2,......,n}基本操作：InitList_sq(&L)操作结果：构造一个空的线性表L。ListInsert_sq(&L,i,e)初始条件：线性表L已存在，1SVL.Length+1。操作结果：在L中第i个位置之前插入新的数据元素e,L的长度加1。ListDelete_sq(&L,i,&e)初始条件：线性表L已存在且非空，1SVL.Length。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。input()}ADT;详细设计抽象数据类型线性表顺序存储结构的表示和实现〃线性表结构类型#defineLIST_INIT_SIZE100//线性表存储空间的初始分量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{elemtype*elem;//存储空间基址intlength;//当前线性表的长度intlistsize;//当前分配的存储容量(以sizeof(elemtype)为单位)}sqlist;〃建立线性表StatusInitList_sq(sqlist&L){〃构造一个空的线性表L.elem=(elemtype*)malloc(LIST_INIT_SIZE*sizeof(elemtype));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_sq〃在线性表指定位置插入指定元素StatusListInsert_sq(sqlist&L,inti,inte){//在线性表L中第i个位置前插入新的元素e//i的合法值1<=i<=L.length+1if(i<1||i>L.length+1)returnERROR;//i值不合法if(L.length>=L.listsize)//当存储空间已满，增加分配{newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存储容量}q=&(L.elem[i-1]);//q为插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素后移*q=e;//插入e++L.length;//表长增加1returnOK;}//ListInsert_sq〃在线性表指定位置删除元素intStatusListDelete_sq(sqlist&L,inti,int&e){//在顺序表L中删除第i个元素，并用e返回其值//i的合法值为1v=iv=L.lengthif(i<1lli>L.length)returnERROR;//i值不合法p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;〃被删除元素复制给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q+1;++p)//被删除元素之后的元素前移*(p-1)=*p;--L.length;//线性表长度减1returnOK;}//ListDelete_sq主函数的伪码算法voidmain()//主函数{printf("\t\t》》》》》》》＞＞数据结构实验一＜＜《《《《《《《\n”);printf("\t\t*********线性表的顺序存储结构和实现***********\n")；do{menu();printf("\t\t★请按提示输入指令:")；scanf("%d”,&a);switch(a){〃调用各函数case1:input();break;case2:if(ListInsert_sq(L,i,e)==1)output();elseprintf("^插入位置不合法,请重新输入~\n");break;case3:if(ListDelete_sq(L,i,e)==1){output();printf("\t\t☆所删除元素为：%d\n",e);}elseprintf("^删除位置不合法，请重新输入~\n");break;case0:printf("\t\t^谢谢您的使用，再见(*A—人*)!\n");return;default:printf("\t\t☆输入有误,请重新输入(*人__a*)\n");}}while(a!=0);}调试分析调试过程中出现的问题未定义某些变量以及Status和elemtype的类型。某些变量的作用范围广，应定义为全局变量。定义与引用名称较长的变量时由于部分字母大小写不一致出现低级错误。程序执行界面有点乱，应在程序中设计好界面，增加程序执行界面的美感。经验和体会得到的经验：编写程序前应先了解算法，再把算法合理的编写成可操作的程序。一定要在程序中添加合理的说明语句，增加程序的可读性，也为检查程序正确与否提供方便。要多用输出语句输出程序执行时的提示性语句，增加程序的可操作性。合理的利用返回值检查程序的错误是快捷的方法，值得提倡。执行删除操作时，所删除元素后的元素全部前移，尝试将前移的元素个数+1即把后面的空值赋值给最后一个元素，节省了存储空间彻底完成了删除操作！得到的体会：多思考、多尝试能更好的完成程序的编写。算法是程序编写的灵魂，选择好算法有助于编写程序。编写程序时细心才能少出错！算法的时空分析和改进线性表的插入平均时间复杂度：T(n)=O(n/2);线性表的删除平均时间复杂度：T(n)=O((n-1)/2);

删除操作将后面元素前移，未彻底删除最后的元素，浪费了一定的存储空间。改进：可将线性表的顺序存储结构调整为链式存储结构。将前移的元素个数+1即把后面的空值赋值给最后一个元素，节省存储空间。用户使用说明打开可执行程序，即Visualc++6.0环境下，参照用户选择界面提示即可使用本程序测试结果程序具体执行如下：运行程序，进入操作界面:初始化线性表元素:'E:相习程序\Debu淫序4.ex初始化线性表元素:'E:相习程序\Debu淫序4.exe".指兀的内A表表表』刖土土.生II?入后3sf>主tXH淤241元3241IIF1CM353-HA-7.-螫籀表一葛表豪一刁身生玄舟旨丸-兀素

顶初人元实现插入操作:39:39::为EE元XS示要BK3:i二.〔后9ssf请请2务值素一璧兀素~y叉元一«/\表插表一ay实现删除操作:演示操作完毕，退出程序!按提示语句执行即可!，插入和删除均可以多次操作附录源程序如下：#include<stdio.h>//头文件#include<stdlib.h>#include<malloc.h>100//线性表存储空间的初始分量10//100//线性表存储空间的初始分量10//线性表存储空间的分配增量-2//宏定义1//宏定义0//宏定义#defineLISTINCREMENT#defineOVERFLOW#defineOK#defineERRORelemtype;//类型定义Status;elemtype;//类型定义Status;typedefinttypedefstruct{*elem;//存储空间基址length;//当前线性表的长度*elem;//存储空间基址length;//当前线性表的长度listsize;//当前分配的存储容量(以sizeof(elemtype)为单位)}sqlist;int*p,*q;//定义全局变量intn,i,e,a;//定义全局变量sqlistL;//定义结构体L//自定义函数的声明StatusInitList_sq(sqlist&L);//建表StatusListInsert_sq(sqlist&L,inti,inte);//插入兀素函数StatusListDelete_sq(sqlist&L,inti,int&e);//删除元素函数voidmenu();//菜单函数voidinput();//初始化线性表的函数voidoutput();//显示线性表元素的函数voidmain()//i函数printf("\t\t》》》》》》》＞＞数据结构实验一＜＜《《《《《《《\n”);printf("\t\t*********线性表的顺序存储结构和实现***********\n")；do{menu();printf("\t\t★请按提示输入指令:，scanf("%d”,&a);switch(a){//调用各函数case1:input();break;case2:if(ListInsert_sq(L,i,e)==1)output();elseprintf("☆插入位置不合法，请重新输入~\n");break;case3:if(ListDelete_sq(L,i,e)==1){output();printf("\t\t☆所删除元素为：%d\n",e);}elseprintf("^删除位置不合法，请重新输入〜\n");break;case0:printf("\t\t☆谢谢您的使用，再见(*人__人*)!\n");return;default:printf("\t\t☆输入有误,请重新输入(*人—人*)\n");}}while(a!=0);}StatusInitList_sq(sqlist&L){〃构造一个空的线性表L.elem=(elemtype*)malloc(LIST_INIT_SIZE*sizeof(elemtype));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_sqStatusListInsert_sq(sqlist&L,inti,inte){//在线性表L中第i个位置前插入新的元素e//i的合法值1v=iv=L.length+1int*newbase;printf("\t\t☆请输入要插入的位置：，scanf("%d",&i);printf("\t\t☆请输入要插入的元素：，scanf("%d",&e);if(i＜1lli＞L.length+1)returnERROR;//i值不合法if(L.length＞=L.listsize)//当存储空间已满，增加分配{newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(OVERFLOW);//存储分配失败L.elem=newbase;//新基址L.listsize+=LISTINCREMENT;//增加存储容量}q=&(L.elem[i-1]);//q为插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)//插入位置及之后的元素后移*(p+1)=*p;*q=e;//插入e++L.length;//表长增加1returnOK;}//ListInsert_sqStatusListDelete_sq(sqlist&L,inti,int&e){//在顺序表L中删除第i个元素，并用e返回其值//i的合法值为1v=iv=L.lengthprintf("\t\t☆请输入要删除的位置：，scanf("%d”,&i);if(iv1lli>L.length)returnERROR;//i值不合法p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;〃被删除元素复制给eq=L.elem+L.length-1;//表尾元素的位置for(++p;pv=q+1;++p)//被删除元素之后的元素前移*(p-1)=*p;--L.length;//线性表长度减1returnOK;}//ListDelete_sqvoidmenu(){〃菜单函数printf("\t\t=============请按提示输入指令================\n");TOC\o"1-5"\h\zprintf("\t\t>1输入线性表初始值\n");printf("\t\t>2向线性表插入元素\n");printf("\t\t>3删除线性表元素\n");printf("\t\t>0退出系统\n");}//menuvoidinput(){〃初始化线性表元素if(InitList_sq(L)!=1){printf("☆分配存储空间失败!