数据结构课程设计—顺序表的操作

1、学 号： 0121010340614 课 程 设 计课程名称数 据 结 构设计题目顺序表的操作学 院专业班级姓 名指导教师2011年6月19日课程设计任务书学生姓名： 专业班级： 指导教师： 工作单位： 计算机科学系 题 目: 顺序表的操作 初始条件：已知a，b和c为三个递增有序的线性表，现要求对a表作如下操作：删去那些既在b表中出现又在c表中出现的元素。（1） 各线性表采用顺序存储结构；（2） 题中任一线性表中的元素值可以相同。（3） 测试用例自己设计。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用a4纸打印（书写），并应包含如

2、下内容： 1、 问题描述简述题目要解决的问题是什么。2、 设计存储结构设计、主要算法设计（用类c语言或用框图描述）、测试用例设计；3、 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、 经验和体会（包括对算法改进的设想）5、 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出，6、 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。时间安排：1、第19周完成。2、6月22 日14：00到计算中心检查程序、交课程设计报告、源程序（cd盘）。指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月

3、日目 录1. 课程设计任务书12. 目录23.引言.34.问题描述.35.实验设计.3 1.设计要求3 2.设计要点3 3.算法设计思想4 4.主要算法设计45.测试用例设计56.调试报告7 1.对设计和编码的分析和讨论.7 2.程序运行结果.113.实验分析127.设计体会128.本科生课程设计成绩评定表.14一、引言数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机学科的核心课称，而且已成为其他理工专业的热门选修课。数据结构是一门专业选技术基础科。一方面，它要求我们学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法

4、的时间分析和空间分析的技术；另一方面，数据结构的学习过程也是复杂程序设计的训练过程，要求我们编写的程序结构清楚和正确易读，复合软件工程的规范，并培养我们的数据抽象能力。本次课程设计就是对数据结构中的顺序表的删除操作的应用。二、问题描述已知a，b和c为三个递增有序的线性表，现要求对a表作如下操作：删去那些既在b表中出现又在c表中出现的元素。要求：创建顺序表，实现对其中特殊元素的删除操作。主要解决的问题： 1、由于要用顺序表实现问题，因此，必须创建数组或结构体来实现对元素的存储； 2、为了删去a表中那些既在b表中出现又在c表中出现的元素，必须先对表b和表c进行比较，找出两个线性表共有的元素，再对表

5、a进行操作 3、利用辅助数组，将被删除的元素剔除，得到删除后的表a三、实验设计1.设计要求对顺序表编写实现上述操作的算法并上机编写代码，要求算法尽可能高效。在实验报告中分析算法的时间复杂度。2.设计要点a表中要删除的元素实际上就是在三个表中都存在的元素。注意这三个线性表都是递增有序的线性表！可以利用这一性质减少对线性表“扫描”的趟数。3.算法设计思想先从b和c中找出共有元素same，再从a中从当前位置开始，凡小于same的元素均保留，等于same的就跳过，大于same时就再找下一个same。4.主要算法设计1)顺序存储结构算法描述void sqlist_delete(sqlist&a, sql

6、ist b, sqlist c)i=0;j=0;m=0;/*i指示a中元素原来的位置，m为移动后的位置*/while(ia.length&jb.length&kc.length)if(b.elemjc.elemk)k+;elsesame= b.elemj;/*找到了相同元素same*/while(b.elemj=same)j+;while(c.elemk)=same)k+;/*j,k后移到新的元素*/while(ia.length&a.elemisame)a.elemm+=a.elemi+;/*需要保留的元素移动到新位置*/while( ia.length&a.elemi=same)i+;/*

7、else*/*while*/while(ia.length) a.elemm+=a.elemi+;/*a的剩余元素重新存储*/a.length=m;/*sqlist_delete*/5.测试用例设计#includeusing namespace std;int main() #define n 4 #define m 5 #define t 6int i,j,k,r,m,same; /*定义变量分别指向数组a,b,c*/int an,bm,ct; cout输入元素:endl;cout输入a的元素:endl; for (i=0;in;i+) cout第i+1ai;cout输入b的元素:endl;

8、 for (i=0;im;i+) cout第i+1bi;cout输入c的元素:endl; for (i=0;it;i+) cout第i+1ci; i=0;j=0;m=0;k=0; /*分别赋值为0，即指向数组的第一元素*/ while(in&jm&kt) if(bjck) k+; /用b中下一个元素和c中元素继续进行比较，否则c中元素同理 else same=bj; while(bj=same)j+; /当b中元素和c中元素一致时，b、c中元素继续向下一元素进行比较 while(ck=same)k+; while(in&aisame) /利用赋值语句实现对a中元素进行删除操作 am+=ai+;

9、 while(in&ai=same) i+; /当a中有b与c中同时出现的元素时，跳过该元素，将下一元素赋到辅助数组中 cout删除符合条件的元素的集合a为:endl; /*输出删除元素后的数组a*/ for (r=0;rm;r+)coutar=arendl; return 0;四、调试报告 1.对设计和编码的分析和讨论 第一次缩写编码如下：#include using namespace std;int main() int a100,b100,c100,i,j,n,m,p,t; /设置count实现对两个数组元素是否相同进行判断coutn;for(i=0;in;i+) cout输入集合la

10、的第i+1ai;for(i=0;in;i+)coutai=aiendl; /输出a的各个元素coutm;for(i=0;im;i+) cout输入集合lb的第i+1bi; /输入b的元素个数和其元素并打印数组bfor(i=0;im;i+)coutbi=biendl;coutp;for(i=0;ip;i+) cout输入集合lc的第i+1ci; for(i=0;ip;i+)coutci=ciendl; /输入c的元素个数和其元素并打印数组cfor(j=0;jm;j+)for(i=0;in;i+)if(ai!=bj) continue; /如果bj在a中没有相同的元素，跳出本次循环else /如果

11、两个数组有不一样的元素，将其中一个集合的元素存入到a中for(t=i;tn-1;t+) /否则依次用从第i元素后的元素覆盖之前的元素coutat;at=at+1;n-;for(j=0;jp;j+) /用已经和b数组比较后的集合a继续和c集合进行比较， /并删除其中相同的元素for(i=0;in;i+)if(ai!=cj) continue; /同上elsefor(t=i;tn-1;t+) /同上coutat;at=at+1;n-; cout删除后的集合为:endl;for(i=0;in;i+)coutaiendl; /打印合并后的集合return 0;该程序初写实觉得很简单，没有什么难度，但写

12、完之后检查时却发现了问题：1.没有看清楚题意,删除了不符合条件的元素;2.我没有利用题目中已经限定好的条件：非递减排列,导致算法的规模大幅度增加(约为n*m+n*p)，之后反复考虑，充分审题，最终采用一次遍历的方式来找到即在b和c中都出现的元素，将时间复杂度降低为o(n),大大节省了程序运行时间，保证了程序的正确性。2.程序运行结果 程序运行是屏幕显示：输入元素: 此时输入三组测试数据，数据间用空格隔开：2 3 4 5回车3 4 5 6 7回车4 5 6 7 8 9回车 程序输出结果：a0=2，a1=3，即删除了数组a中即在b和c中都出现的元素，分析知实验结果正确。程序调试屏幕截图3实验分析（

13、1）因为顺序存储结构中a，b，c中的元素都是递增有序的，所以先通过遍历b和c找到它们共同的元素，然后再查找该元素是否也存在于a中，存在则删除；否则再查找b和c中的下一个相同元素。(2)在顺序存储结构中，仅采用一次遍历的方式来找到即在b和c中都出现的元素，故时间复杂度为o(n)。五、设计体会通过这次课程设计，我不仅提高了自己的编程能力，而且让我学会了编写一个程序应该如何去做才能是程序更加完善，让我懂得写程序时应该戒骄戒躁，要仔细阅读题目利用更为简洁的方法解决问题。其次，从其中我学会了编写程序的比较好的方法就是要分析好题目、设计好程序的整体结构、设计算法并列出所需函数、逐个编写函数的代码、和完善美

14、观函数。通过这次编程，我深深体会到了算法的重要性，算法的好坏直接影响到了程序编写的难易与效率。刚拿到顺序表的操作题目时，心中暗自窃喜，感觉题目不难，比起其他停车场管理系统、图书馆管理系统等题目，我需要写的代码并不会太繁杂，而且只需要加几个循环比较语句就可以了。然而在实际编写程序的时候，发现并不是那么简单，当然，还要考虑其他各个方面的问题，并非只是加几个程序语句就可以完成的。此次课程设计让我的设计能力和调试改错能力大大地增强了，这为我的编程过程节省了不少的时间，更加了解了几种顺序表元素的比较方法；还有就是在设计之前要分析好所编软件或系统的实用价值与发展前景，看看它是否值得去实现。最后就是这次课程设计让我