数据结构实验一线性表

实验报告实验一线性表实验目的：1. 理解线性表的逻辑结构特性；2. 熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；3. 熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；4•掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。

实验原理：线性表顺序存储结构下的基本算法；线性表链式存储结构下的基本算法；实验内容：2 - 21设计单循环链表，要求：(1 ) 单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。

(2 ) 设计一个测试主函数，实际运行验证所设计单循环链表的正确性。

2 — 22 .设计一个有序顺序表，要求：(1 ) 有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。

有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。

(2 ) 设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。

(3) 设计合并函数ListMerge ( L1,L2,L3 ),功能是把有序顺序表 L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。

并设计一个主函数，验证该合并函数的正确性。

程序代码：2－21 (1)头文件 LinList.h 如下：typedef struct node{DataType data;struct node *next;}SLNode;/* ( 1 )初始化 ListInitiate(SLNode * * head)*/void ListInitiate(SLNode * * head){ /* 如果有内存空间，申请头结点空间并使头指针 head 指向头结点 */if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1);(*head)->next=NULL; /* 置结束标记 NULL*/}/*(2) 求当前数据元素个数 ListLength(SLNode * head)*/int ListLength(SLNode * head){SLNode *p=head;int size=0;while(p->next!=head){p=p->next;size++;}return size;}/*(3) 插入 ListInsert(SLNode * head ， int i ， DataType x)*//* 在带头结点的单链表的第 i(0<=i<=size) 个结点前 *//* 插入一个存放数据元素 x 的结点。

数据结构实验一线性表的基本操作数据结构实验一线性表的基本操作实验一线性工作台的基本操作一、实验目的1.了解线性表的定义、特点及相关概念；2.了解线性表的顺序存储结构；3.掌握在计算机上调试线性表的基本方法。

2、实验条件1、pc机2.软件Visual C++III.实验原理线性表的顺序存储结构是用一组地址连续的存储单元依次存放线性表中的元素。

其实现手段是数组类型。

由于内存中的元素存放顺序与逻辑上的顺序相同，所以元素的地址就体现了逻辑关系，即物理相邻=逻辑相邻；在插入或者删除某一个元素时，其后的所有元素也要做相应的后移或者前移，即有可能要移动大量元素。

四、实验内容1.两个线性表La和LB分别代表两组a和B。

现在一组新的a=a∪ B为必填项，由序列表实现；2、对给定的两个集合能够进行合并，并给出合并结果；五、算法分析voidunion（list&la，listlb）{la_len=listlength（la）；lb_len=listlength （lb）；for（i=1；i<=lb_len；i++）{getelem（lb，i，e）；if(!locateelem(la,e,equal))listinsert(la,++la_len,e);}}//union六、完成项目实施#include#include#定义列表uuu初始大小100#定义增量10typedefstruct{int*elem;intlength;intlistsize;}sqlist;Intinitsqlist（SqList*l）//初始化{l->elem=(int*)malloc(list_init_size*sizeof(int));if(!l->elem)exit(0);l->length=0;l->listsize=list_init_size;return0;}intlistinsert_SQ（SqList*l，inti，int）//插入一个元素{int*P，*q；如果（I<1 | I>l->length+1）退出（0）；q=&（l->elem[I-1]）；for（P=&（l->elem[l->length-1]）；P>=q；--P）*（P+1）=P；*q=E；+l->length；return0；}voidadd(sqlist*l,inte)//添加到最后{listinsert_sq（l，l->length+1，e）；}voiddisp(sqlist*l){因蒂；for(i=0;ilength;i++)printf(\printf(\}intfind(sqlist*l,inte)//查找元素是否存在{inti，t=-1；for(i=0;ilength;i++)if(l->elem[i]==e){t=i;break;}returnt;}voidopt_1（SqList*La，SqList*lb）/（不保留相同的元素）{inti,j;对于（i=0；i长度；i++）{j=find（la，lb->elem[i]）；if（j=-1）listinert_sq （la，la->length+1，lb->elem[i]）；}intmain(){sqlistla,lb;initsqlist(&la);add(&la,1);add(&la,2);add(&la,5);add(&la ,7);initsqlist(&lb);add(&lb,2);add(&lb,4);add(&lb,7);add(&lb,9);disp(&la);disp (&lb);选择1（&la，&lb）；//操作（同一元素未保留）disp&LA；}结果截图：。

南京工程学院实验报告<班级>_<学号>_<实验X>.RAR文件形式交付指导老师。

一、实验目的1.熟悉上机环境，进一步掌握语言的结构特点。

2.掌握线性表的顺序存储结构的定义及实现。

3.掌握线性表的链式存储结构——单链表的定义及实现。

4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。

5.掌握线性表在链式存储结构——单链表中的各种基本操作。

二、实验内容1.顺序线性表的建立、插入及删除。

2.链式线性表的建立、插入及删除。

三、实验步骤1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。

2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。

3.建立一个带头结点的单链表，结点的值域为整型数据。

要求将用户输入的数据按尾插入法来建立相应单链表。

四、程序主要语句及作用程序1的主要代码(附简要注释)public struct sequenlist{public const int MAXSIZE=1024; /*最大值为1024*/public elemtype[] vec;public int len; /* 顺序表的长度 */public sequenlist( int n){vec=new elemtype[MAXSIZE ];len = n;}};class Program{static void Main(string[] args){sequenlist list1 = new sequenlist(5);for (int i = 0; i < 5; i++){list1.vec[i] = i;}for (int i = 0; i < 5; i++){Console.Write("{0}---", list1.vec[i]) ;}Console.WriteLine("\n");Console.WriteLine("表长：{0}\n",list1.len );Console.ReadKey();}}程序2的主要代码(附简要注释)public void insertlist(int i, int x){if (len >= MAXSIZE)throw new Exception("上溢"); /*长度大于最大值则抛出异常*/if (i < 1 || i > len + 1)throw new Exception("位置");/插入位置小于1或大于len+1则抛出插入位置错误的异常for (int j = len; j >= i; j--)vec[j] = vec[j - 1]; //注意第j个元素存在数组下标为j-1处vec[i - 1] = x;len++;}};class Program{static void Main(string[] args){sequenlist list2 = new sequenlist(7);list2.vec[0] = 21;list2.vec[1] = 23;list2.vec[2] = 14;list2.vec[3] = 5;list2.vec[4] = 56;list2.vec[5] = 17;list2.vec[6] = 31;Console.Write("请输入第i个位置插入元素：");int loc =Convert.ToInt32( Console.ReadLine());Console.Write("请输入第{0}个位置插入的元素：", loc);int ele = Convert.ToInt32(Console.ReadLine());Console.WriteLine("插入前的线性表：");for (int i = 0; i < list2.len ; i++){Console.Write("{0}---", list2.vec[i]);}Console.WriteLine("\n");list2.insertlist(loc, ele);Console.WriteLine("插入后的线性表：");for (int i = 0; i < list2.len ; i++){Console.Write("{0}---", list2.vec[i]);}Console.WriteLine("\n");Console.ReadKey();}}程序3的主要代码(附简要注释)class Node{private int num;public int Num{set { num = value; }/输入值get { return num; }/获得值}private Node next;public Node Next{set { next = value; }get { return next; }}}class Pp{static void Main(string[] args){Node head;Node tempNode, tempNode1;int i;head = new Node();Console.WriteLine("输入六项数据：\n");Console.Write("输入第1项数据:");head.Num = Convert.ToInt32(Console.ReadLine());head.Next = null;tempNode = head;for (i = 1; i < 6; i++){tempNode1 = new Node();Console.Write("输入第{0}项数据:",i+1);tempNode1.Num = Convert.ToInt32(Console.ReadLine());/插入项转换为整形数值 tempNode1.Next = null;tempNode.Next = tempNode1;tempNode = tempNode.Next;}Console.WriteLine("线性表:");tempNode = head;for (i = 0; i < 6; i++){Console.Write("{0}", tempNode.Num);if (i < 5){Console.Write("--");}tempNode = tempNode.Next;}Console.ReadKey();}}五、程序运行结果截图程序1程序2程序3六、收获，体会及问题(写得越详细、越个性化、越真实越好，否则我不知道你做这个实验的心路历程，也就无法充分地判断你是否是独立完成的这个实验、你是否在做这个实验时进行了认真仔细地思考、通过这个实验你是否在实践能力上得到了提高)这次试验刚开始做时完全不知道从哪下手，才刚上了几节课，对于线性表、链式表都不是理解的很透彻，不知道用哪个软件编写程序。

数据结构实验⼀-线性表实验⼀线性表⼀、实验⽬的1、深刻理解线性结构的特点，以及在计算机内的两种存储结构。

2、熟练掌握线性表的顺序存储结构和链式存储结构，及其它们的基本操作，重点掌握查找、插⼊和删除等操作。

⼆、实验要求1、认真阅读程序，将未完成的代码补全（红⾊部分）。

2、上机调试，并运⾏程序。

3、保存和截图程序的运⾏结果，并结合程序进⾏分析。

三、实验内容和基本原理1、实验1.1 顺序表的操作利⽤顺序表存储⽅式实现下列功能（见参考程序1）：1）通过键盘输⼊数据建⽴⼀个线性表，并输出该线性表。

如，依次输⼊元素25,21,46,90,12,98。

2）根据屏幕菜单的选择，进⾏数据的插⼊、删除和查找，并在插⼊或删除数据后，再输出线性表。

如，在第2个位置上插⼊元素43，然后输出顺序表。

删除顺序表第4个元素，输出改变的顺序表。

3）在屏幕菜单中选择0，结束程序的运⾏。

基本原理：在顺序表的第i个位置上插⼊⼀个元素时，必须先将线性表的第i个元素之后的所有元素依次后移⼀个位置，以便腾空⼀个位置，在把新元素插⼊到该位置。

当要删除第i个元素时，只需将第i个元素之后的所有元素前移⼀个位置。

程序代码（蓝⾊为补充的语句）：//* * * * * * * * * * * * * * * * * * * * * * * *//*PROGRAM :顺序结构的线性表 *//*CONTENT :建⽴,插⼊,删除,查找 *//*编程语⾔： Visual c++ 6.0 *//* * * * * * * * * * * * * * * * * * * * * *#include#include#define MAXSIZE 20typedef int ElemType; //数据元素的类型typedef struct{ElemType a[MAXSIZE];int length;}SqList; //顺序存储的结构体类型SqList a,b,c;//函数声明void creat_list(SqList *L);void out_list(SqList L);void insert_sq(SqList *L,int i,ElemType e); ElemType delete_sq(SqList *L,int i);int locat_sq(SqList L,ElemType e);//主函数void main(){int i,k,loc;ElemType e,x;char ch;do {printf("\n\n\n");printf("\n 吴肖遥20151681310131");printf("\n 1.建⽴线性表");printf("\n 2.插⼊元素");printf("\n 3.删除元素");printf("\n 4.查找元素");printf("\n 0.结束程序运⾏");printf("\n =====================");printf("\n 请输⼊要执⾏的操作: ");scanf("%d",&k);switch(k){case 1:{creat_list(&a);out_list(a);}break;case 2:{printf("\n请输⼊插⼊位置： ",a.length+1); scanf("%d",&i);printf("请输⼊要插⼊的元素值： ");scanf("%d",&e);insert_sq(&a,i,e);out_list(a);}break;case 3:{printf("\n请输⼊要删除元素的位置： ",a.length); scanf("%d",&i);x=delete_sq(&a,i);out_list(a);if(x!=-1)printf("\n删除的元素为：%d\n",x);else printf("要删除的元素不存在！");}break;case 4:{printf("\n请输⼊要查找的元素值：");scanf("%d",&e);loc=locat_sq(a,e);if(loc==-1)printf("\n未找到指定元素！");elseprintf("\n已找到，元素的位置是: %d ",loc);}break;}/*switch*/}while(k!=0);printf("\n 按回车键，返回...\n");ch=getchar();}/*main*///建⽴线性表void creat_list(SqList *L){int i;printf("请输⼊线性表的长度: ");scanf("%d",&L->length);for(i=0;ilength;i++){printf("数据 %d =",i);scanf("%d",&(L->a[i]));}}//输出线性表void out_list(SqList L){int i;for(i=0;i<=L.length-1;i++)printf("%10d",L.a[i]);}//在线性表的第i个位置插⼊元素evoid insert_sq(SqList *L,int i,ElemType e){int j;if(L->length==MAXSIZE)printf("线性表已满!\n");else {if(i<1||i>L->length+1)printf("输⼊位置错!\n");else {for(j=L->length-1;j>=i-1;j--)L->a[j+1]=L->a[j];L->a[j+1]=e;/*将未完成的代码补全,提⽰：此处添加⼀条语句，将被删除的元素值赋给e*/ L->length++;}}}//删除第i个元素，返回其值ElemType delete_sq(SqList *L,int i){ElemType x;int j;if(L->length==0)printf("空表!\n");else if(i<1||i>L->length){printf("输⼊位置错！\n");x=-1;}else{x=L->a[i-1];for(j=i;j<=L->length-1;j++)L->a[j-1]=L->a[j];/*将未完成的代码补全,提⽰：此处添加⼀条语句，将被删除元素之后的元素左移。

实验报告课程名称：数据结构实验名称：线性表班级：学生姓名：学号：指导教师评定：签名:题目：有两张非递增有序的线性学生表A，B，采用顺序存储结构，两张表合并用c表存，要求C为非递减有序的，然后删除C表中值相同的多余元素。

一、需求分析⒈本演示程序根据已有的两张表的信息，实现两张表的合并及删除值相同元素的操作，需要用户输入学生的信息。

⒉在演示过程序中，用户输入需要合并的顺序表，即可观看合并结果。

⒊程序执行的命令包括：（1）构造线性表A （2）构造线性表B （3）求两张表的并（4）删除C中值相同的元素二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT Stack {数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0}数据关系：R1={<a i-1,a i>|a i-1,a i∈D,i=2,…n≥0}基本操作:init(list *L)操作结果：构造一个空的线性表L。

ListLength(List *L)初始条件：线性表L已经存在操作结果：返回L中数据元素的个数。

GetElem(List L, int i, ElemType *e)初始条件：线性表L已经存在，1≤i≤ListLength(&L)操作结果：用e返回L中第i个数据元素的值。

EqualList(ElemType *e1,ElemType *e2)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项作为判定e1,e2是否相等的依据。

Less_EquaList(ElemType *e1,ElemType *e2)初始条件：数据元素e1,e2存在操作结果：以e1,e2中的姓名项(为字符串)的≤来判定e1,e2是否有≤的关系。

LocateElem(List *La,ElemType e,int type)初始条件：线性表La已经存在操作结果：判断La中是否有与e相同的元素。

MergeList(List *La,List *Lb,List *Lc)初始条件：非递减线性表La，Lb已经存在操作结果：合并La，Lb得到Lc，Lc仍按非递减有序排列。

数据结构实验报告（⼀）线性表的应⽤实验说明数据结构实验⼀ 线性表的实验——线性表的应⽤⼀、实验⽬的通过本实验使学⽣了解线性表的⼀种简单应⽤，熟悉线性表顺序存储与链式存储的特性，特别训练学⽣编程灵活控制链表的能⼒，为今后编程控制更为复杂的数据结构奠定基础。

⼆、实验内容1.⽤顺序表和链表分别分别编程实现教材中例⼦2-1与2-2。

要求：（1）只能⽤C语⾔编程实现；（2）完全保持书中算法2.1与算法2.2形式，不允许有任何变化，除⾮语法上不允许;所调⽤各函数参照书中19页的功能描述，其中函数名、参数个数及性质、函数功能必须与书中完全⼀致，不能有变化。

2.利⽤线性表表⽰⼀元多项式完成多项式的加、减、乘、求导、求值运算。

要求：（1）输⼊的⼀元多项式可以采⽤只输⼊各项的系数与指数这种简化的⽅式。

如对于多项式2x2+6x5，输⼊可为： 2,2 6,5 这样的简单形式。

（2）遇到有消项时应当处理，如2x2+6x5与3x2-6x5进⾏相加时，结果为5*x^2。

（3）当给定x的值时，能计算表达式相加或相减的结果。

（4）操作的结果放⼊⼀个新线性表中，原来的两个表达式存储表⽰不变，也可以不是产⽣新的线性表，⽽是将两上线性表合并为⼀个。

（5）要求程序功能模块划分合理（每个函数功能单⼀、可重⽤性好），使⽤空间尽可能少，算法尽可能⾼效。

实验报告1.实现功能描述使⽤线性表表⽰⼀元多项式完成多项式的加、减，乘，求导、求值运算。

2.⽅案⽐较与选择（1）因为使⽤的是线性表，所以主要⽅案有数组法和链表法。

（2）从时间复杂度来说，使⽤数组法更优；从空间复杂度来说，链表法更优。

因为数组法是指定好空间的，若式⼦⼤⼩超出设置⼤⼩，那程序必然出错；若式⼦⼤⼩⼩于设置⼤⼩，那就意味着有多余的空间被浪费了。

综合来讲，若计算式⼦较为庞⼤，使⽤链表法更佳；相反，若计算式⼦较⼩，数组法更佳。

3.设计算法描述（1）单个项式的数据存储使⽤了结构体，数组法是在⼀个结构体中定义两个⼀维数组；链表法是通过⼀个结构体作为⼀个节点，通过next指针连接起来。

数据结构实验报告实验名称：实验一线性表——题目1学生姓名：王海洋班级： 2018211107学号：2018210191日期： 2019年3月22日1.实验要求实验目的：熟练掌握线性表的基本操作，包括：创建、插入、删除、查找、输出、求长度、合并等运算，以及各类操作在顺序存储结构和链式存储结构上的实现。

实验内容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。

线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。

2.程序分析2.1 存储结构链表的具体存储表示为：①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）② 链表中结点的逻辑次序和物理次序不一定相同。

为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息（称为指针）链表的结点结构┌──┬──┐│data│next│└──┴──┘data 域--存放结点值的数据域next 域--存放结点的直接后继的地址（位置）的指针域（链域）地址 内存单元1000H头指针 1020H 1080H 10C0H2.2 关键算法分析1、关键算法：1：头插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。

将新结点加入链表中伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:s->next=front->next;d:front->next=s2：尾插法自然语言描述：a:在堆中建立新结点：b:将a[i]写入到新结点的数据域：c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:Node <T> * s=new Node <T>b:s->data=a[i]c:r->next=s;d:r=s3：析构/删除函数自然语言描述：a:新建立一个指针，指向头结点b:判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:Node <T> * p=frontb:while(p)c:front=pd:p=p->nexte:delete front4：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，直到p为空或者j等于1b1：p指向下一个结点b2：j加1c:若p为空，说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:Node <T> * p=front->next;j=1;b:while(p&&j!=1)b1:p=p->nextb2:j++c:if(!p) throw ”error”d:return p5：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点 b1：判断p 指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j的值加一c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:Node <T> * p=front->next;j=1;b:while(p)b1: if(p->next==x) return jp=p->nextj++c:return “error”6：插入函数自然语言描述：a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:Node <T> * s=new Node <T>;b:s-data=p->datac:s->next=p->nextd:p->next=se:p->data=x7：删除函数自然语言描述：a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述a:q=p->nextb:p->next=q->nextc:x=q->datad:delete q8：遍历打印函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空伪代码描述If front->next==NULLThrow ”an empty list ”Node<T>* temp=front->next;while(temp->next){ cout<<temp->data<<" ";temp=temp->next;}9：获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则return n e: 使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n 伪代码描述int n=0if ront->next==NULLn=0;else{ Node<T>* temp=front->next;while(temp->next)n++;temp=temp->next;}return n;2、代码详细分析：（1）从第一个结点开始，查找节点，使它的数据比x大，设p指向该结点：while (x>p->data) { p=p->next;}（2）新建一个节点s，把p的数据赋给s：s->data=p->data;（3）把s加到p后面：s->next=p->next; p->next=s;（4）p节点的数据用x替换：p->data=x;示意图如图所示3、关键算法的时间复杂度：O（1)3.程序运行结果程序截图4.总结1.调试时出现的问题及解决的方法：（1）刚开始时用NULL置空最后一个节点的指针域，发现调试时出现NULL未声明的情况。

实验一：线性表的顺序存储结构实验学时：2实验类型：验证一、实验目的：1. 熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；二、实验内容：1．输入一组整型数据，建立顺序表。

2．实现该线性表的删除。

3、实现该线性表的插入。

4．实现线性表中数据的显示。

5．实现线性表数据的查找和定位5、编写一个主函数,调试上述算法。

三、实验原理、方法和手段1.根据实验内容编程，上机调试、得出正确的运行程序。

2. 编译运行程序，观察运行情况和输出结果。

3. 写出实验报告（包括源程序和运行结果）。

四、实验条件运行Visual c++的微机一台五、实验步骤（程序清单）：（一）、程序代码：#include"stdafx.h"#include<iostream>usingnamespace std;typedefint elemtype;struct list{elemtype *p;int size;int maxsize;};void buildlist(list &a,int b)/*建立顺序表*/{if(b<=0){cout<<"数据有误" <<endl;}a.p=new elemtype[b];if(a.p==NULL){cout<<"动态可分配的空间用完，退出运行!"<<endl;}a.size=0;a.maxsize=b;}void clearlist(list &a)/*清空线性表*/{if(a.p!=NULL){delete []a.p;a.p=NULL;}a.maxsize =0;a.size=0;}bool insertlist(list &a,int pos,elemtype b)/*向线性表中按给定的位置插入一个元素*/ {int i;if(pos<=0||pos-1>a.size){cout<<"位置无效" <<endl;returnfalse;}if(a.maxsize<=a.size){a.p=(elemtype*)realloc(a.p,2*a.maxsize *sizeof(b));a.maxsize=2*a.maxsize;}for( i=a.size;i>=pos;i--)a.p[i]=a.p[i-1];a.p[i]=b;a.size++;returntrue;}bool deletelist(list &a,int pos)/*向线性表中按给定的位置删除一个元素*/{if(a.size==0){cout<<"线性表为空，删除无效！"<<endl;returnfalse;}if(pos<=0||pos>a.size){cout<<"位置无效" <<endl;returnfalse;}for(int i=pos-1;i<a.size-1;i++)a.p[i]=a.p[i+1];a.size--;if(float(a.size)<a.maxsize*0.4&&a.maxsize>10){a.p=(elemtype*)realloc(a.p,a.maxsize*0.5*sizeof(*(a.p)));a.maxsize=a.maxsize*0.5;}returntrue;}bool getlist(list a,int pos,elemtype &item)/*得到线性表中指定位置的元素*/{if(pos<=0||pos>a.size){cout<<"位置无效" <<endl;returnfalse;}item=a.p[pos-1];returntrue;}int findlist(list a,elemtype b)/*从线性表中查找具有给定值的第个元素*/{for(int i=0;i<a.size;i++)if(a.p[i]==b)return i+1;return 0;}void display(list a)/*线性表中数据的显示*/{cout<<"顺序表元素个数为："<<a.size <<endl<<"所占内存单元为："<<a.maxsize*sizeof(*(a.p)) <<"字节"<<endl<<"数据为：";for(int i=0;i<a.size;i++)cout<<a.p[i]<<" ";cout<<endl;}void main(){list L;int i=10;int pos;elemtype a,b,c;buildlist(L,5);for(int j=0;j<10;j++){insertlist(L,j+1,i);i--;}display(L);cout<<endl;cout<<"一、插入操作："<<endl;cout<<"位置：";cin>>pos;cout<<"数据：";cin>>a;if(insertlist(L,pos,a))cout<<"插入成功"<<endl;elsecout<<"插入失败"<<endl;display(L);cout<<endl;cout<<"二、删除操作："<<endl;cout<<"位置：";cin>>pos;if(deletelist(L,pos))cout<<"删除成功"<<endl;elsecout<<"删除失败"<<endl;display(L);cout<<endl;cout<<"三、定位操作："<<endl;cout<<"位置：";cin>>pos;if(getlist(L,pos,b))cout<<"该位置数据为"<<b<<endl;elsecout<<"定位失败"<<endl;cout<<"四、查找操作："<<endl;cout<<"数据：";cin>>c;if(findlist(L,c))cout<<"线性表中第一个等于该数据的位置为"<<findlist(L,c)<<endl; elsecout<<"线性表中没有等于该数据的元素"<<endl;clearlist(L);}（二）、程序运行结果六、实验分析与总结：通过本次实验，我发现了自己身上很多的不足：1.不知道什么时候才需要将函数的返回类型弄成bool类型；2.在编写函数体的时候，对排除非法情况考虑不周；3.对申请、追加及删除动态空间的语法不熟悉；4.没有思路对算法进行优化，例如，不知道怎样将所申请的动态空间适当缩小或放大。