1、 掌握线性表的结构特征，以及链式存储结构的特点及程序设计方法；掌握构造链表的基本方法；掌握链表的插入、删除和查找等算法的设计方法。【实验内容】1把线性表的顺序存储和链表存储的数据插入、删除运算其中某项进行程序实现。建议实现键盘输入数据以实现程序的通用性。编写应用程序，实现可以对一个数组进行初始化，并用键盘进行输入；对数组进行遍历，然后输出数组里面的值；实现对数组数据的插入，里面涉及数据的移动，计数；对数组数据的修改，先提供所修改数据所在数组的位置；求表长的长度，返回数组的长度；对数组进行数据的反转，用for循环对数组两边进行数据的交换。2定义链式存储结构；编写建立链表的函数， 编写遍历链表的函
2、数； 编写在链表中进行插入的函数； 编写在链表中进行删除元素的函数； 编写带菜单的测试主函数并上机运行；打印出运行结果，并结合程序运行结果进行分析。【注意事项】1.开发语言：使用C+。2.可以自己增加其他功能。【顺序表的实验分析、说明过程、部分代码】 1对于数组数据的初始化时，要进行传参数，调用函数create（int number）；传入参数number，它是记录数组储存多少个数据，然后用for循环从键盘输入数据读取到数组当中，返回success；returninfo create（int number） count=number; printf（请依次输入数据（用空格隔开）：n）; for
3、（int i=0;idate; dataarrayi=date; return success; 2对于数组的遍历显示而言，先对数组的元素数量是否为空进行判断，是空时返回underflow；不为空时，用for循环对数组进行遍历，输出数组的值，返回success；returninfo traverse（void） /遍历顺序表中的所有元素 if（empty（） return underflow; /空表的处理顺序表中的全部数据为: n cout 第i+1数据为：dataarrayiendl;3插入一个元素，先对数组进行判断是否为空，如果为空返回underflow；然后对传入的位置进行判断，是否越
4、界，如果越界则返回range_error;在对数据进行移动的时候要从后面进行移动把前面一个数据移动到后面，然后往前走，继续前面的步骤，到达所在位置数据移动完成以后，对所在位置进行数据的赋值，然后count加一，返回success。returninfo insert（int position,int &item） /插入一个元素 if（empty（） return underflow; if（positioncount+1） return range_error; int i=position-1; for（int j=count;jposition;j-） dataarrayj=dataarr
5、ayj-1; dataarrayposition-1=item; count+;4对数组中的数据元素进行删除时，先对数组进行判断是否为空，如果为空返回underflow；如果上述情况没有的话，对数组里面的数据元素进行移动，这次是从要删除的位置进行数据移动，把后面的数据元素往前移动，依次往后进行，计数的count减一，然后返回success。returninfo remove（int position） /删除一个元素count） if（i+1=count） count-; else for（; dataarrayi=dataarrayi+1;5对数组中的数据进行反转，先对数组进行判断是否为空，
6、如果为空返回underflow；对数组元素的个数计算出中点，然后利用for循环，对数组与中点对称的数据元素进行互换（就像纸折叠对齐一样），但对算法而言，主要是利用数组长度的中间值，然后利用中间变量i与count-1-i，进行数组的反转，完成以后，返回success。returninfo invertlist（void） /顺序表所有数据反转 int halfpos,tempdata; halfpos=count/2;/计算出中点halfpos; tempdata=dataarrayi; dataarrayi=dataarraycount-1-i; dataarraycount-1-i=temp
7、data;【链表的实验分析、说明过程、部分代码】1先对链表进行初始化，建立一个头结点数据为空，指针域为空，count计数为0；void initList（） headp=new struct node ;/申请头结点空间 headp-next=NULL; /尾指针指向空，即NULL count=0; /计数器清零2删除指定位置的数据：提供的参数为位置position，先对链表进行判断是否为空，如果为空返回underflow；如果符合上述条件，则用for循环将指针指到指定的位置处（主要为followp=searchp，searchp=searchp-next;），然后将指针的next复制给前一个
8、指针的next，释放当前指针所指的内存，返回returnvalue枚举型，判断操作是否成功。returninfo remove（int position） /删除指定位置的结点0|positioncount） node *searchp=headp-next ,*followp=headp; for（int i=1; i followp-next=searchp- free（searchp）; count-; /返回删除成功信息3插入数据到链表的指定位置将入口参数（位置）position传到函数里面，先对链表进行判断是否为空，如果为空返回underflow；如果符合上述条件，则用for循环将s
9、earch指针移动到指定的位置，然后向系统申请空间，完成以后往数据区添加数据，添加完成以后，进行挂链，把search的next赋值给新增加的next，然后把新增加的地址赋值给search，然后对count加一，我这里要指出的是对向系统申请空间的时候，要注意申请空间失败的情况，如果失败则返回fail，出口参数:返回returnvalue枚举型，判断操作是否成功。returninfo insert（int position,int item） /在指定位置插入信息count+1） node *searchp=headp;position & struct node *newnodep; /定义两个
10、指针，便于后面的挂链 newnodep=new struct node;/申请空间,此处对于申请失败并没有处理 newnodep-data=item; /把数组中的数据存入链表的结点next = searchp- /开始挂链 searchp-next=newnodep; /搜索指针searchp指向当前最后一个结点 /计数器加1 /返回插入成功信息4对链表进行遍历全部数据，它没有入口参数，先进行链表是否为空进行判断，是空时则返回underflow;，如果不为空时则定义一个变量，进行赋值，将头节点的next赋值给定义的指针变量search，用while，进行遍历，符合条件值为search不等于空
11、，循环的内容为输出search所指向的数据，然后search等于它的下一个地址。然后返回returnvalue枚举型，判断操作是否成功。returninfo traverse（） /遍历全部数据 coutdata followp=NULL; while（searchp! exchangep=followp; searchp=searchp- followp-next=exchangep;next=followp;【画图显示】【线性表】【链表】【实验小结】 （总结本次实验的重难点及心得、体会、收获）体会：在线性表中访问数据元素是很快的。它的缺点也正因为它是连续的一块内存空间。所以，如果往中间添加
12、或在中间删除一个元素。都要移动其他的元素。如：我在最前面加入一个元素：0.则1，2，3都要往后移一位；或，我将1删除，则2，3都要往前移一位；估算一下运算时间：在第一个元素处添加，要移动所有的元素。花费的时间是添加元素的时间 X 加上移动其他元素的时间：N，在最后面加元素不需要移动任何元素。时间仅为添加元素的时间： X .所以添加元素要的平均时间是 （N + 2X）/2；删除操作和添加操作是一样的；所以，当改变线性表长度的时间，它会在移动元素上花费大量的时间。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保
13、持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。作为一般规律，若线性表需频繁查找却很少进行插入和删除操作，或其操作和“数据元素在线性表中的位置”密切相关时，宜采用顺序表作为存储结构；若线性表需频繁进行插入和删除操作时，则宜采用链表做存储结构。作为一般规律，当线性表中元素个数变化较大或者未知时，最好使用链表现；而如果用户事先知道线性表的大致长度，而且只是读取数据，移动数据很少，这样使用顺序表的空间效率会更高。总之，线性表的顺序实现和链表实现各有其优缺点，不能笼统地说哪种实现更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的实现方法。缺点：我的程序中，基本功能都能实现的，但对于一些具体细节的判断还有一些欠缺，例如当数组数据要移出的时候，经常会忘记对计数器进行减一；还有对挂链，删除的时候经常还要想一会时间，才能反应过来，然后将程序敲上去，就其原因就是编程的次数太少了，对一些基本的语句都不是十分的熟悉。【实验运行结果截图】【链表截图】
