数据结构顺序表的实现的课程设计报告

塔里木大学课程设计第1页共10页前言1.1设计背景和意义1.1.1数据结构简介数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。1.1.2选择算法的原因在许多类型的程序的设计中数据结构的选择是一个基本的设计考虑因素。许多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。1.2设计的原理线性表是最常用的而且也是最简单的一种数据结构，线性表是N个数据元素的有限序列。例如26个英文元素的字母表：（A，B，C，D，···）。其数据结构的描述为：Linearlist=(D,R)其中：D={ai|ai属于D0,i=1,2,3,···}R={N},N={ai-1,ai|i=2,3,4,···}。本实验是以数组的形式把有序表存放在计算机内存的一个连续的区域内，这样便有：LOC(ai+1)=LOC(ai)+m。其中m是存放每个元素所占的内存字数。LOC(ai)=LO+m·(i-1)。其中LO是ai的地址，即首地址。工程概况2.1项目所用的时间从这个项目开始到结束总共历时7天。完成于2011年12月18日。2.2项目负责人李欢，男，计算机科学与技术14-4，学生。2.3项目指导人朱赖红，男，信息工程学院教师，讲师。塔里木大学课程设计第2页共10页正文顺序表是在计算机内存中以数组的形式保存的线性表,是指用一组地址连续的存储单元依次存储数据元素的线性结构。线性表采用顺序存储的方式存储就称之为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中3.1设计的目的和意义我们是计算机科学与技术专业的本科生，《数据结构》是我们重要的必修课程。当代社会学要大学培养出理论扎实，动手实践能力强的大学生。所以，本次课程设计的目的就在于通过一次实践性的活动加深对这门课程的理解，使我们在感性的认识上进一步升华为理性的认识。为后继课程的学习打下坚实的基础。马克思主义唯物辩证法认为，实践是连接客观实在和人主观意识的通道和桥梁。物质对意识的作用以及意识对物质的反作用都蕴含在实践活动当中。也就是，实践是检验真理的唯一标准。对这门课的学习状况的好坏，用一次课程设计便可以检验出来。而这，就是本次我们进行设计的意义之所在。3.2目的和总体方案顺序表存储位置是相邻连续的，可以随即访问的一种数据结构，一个顺序表在使用前必须指定起长度，一旦分配内存，则在使用中不可以动态的更改。他的优点是访问数据是比较方便，可以随即的访问表中的任何一个数据。目的：1、理解和掌握顺序表的结构类型定义方法。2、掌握建立顺序表的基本方法。3、掌握显示顺序表元素的基本方法。由于时间只有十天，故做了如下的计划安排，将这项工程分为两大部分：程序的设计和程序的调试。首先在程序的设计部分由分为几个步骤：第一步：查阅有关数据结构顺序表操作的资料，用一天的时间。第二步：设计这个项目的整体架构和算法。用一到两天的时间。第三步：选择一门程序设计语言进行算法的描述。两天的时间。其次，进行程序的调试。用一天。3.3设计方法和内容“工欲善其事，必先利其器”。有了总体方案后必须用一个事半功倍的设计方法来提高程序设计的效率。在这个项目的设计上，我选择了Ｃ语言作为算法的描述语言，因为Ｃ语言具有丰富的表达能力以及代码的高效性，并且有着良好的移植性和灵活性。同时，采用“自顶向下，个个击破”的程序设计思路和思想，充分运用Ｃ语言强大的功能。我将这个项目整体设分成了两个模块。一个是功能函数模块群，主要实现设计方案中的具体功能，是整个项目的执行部分；另一个是主函数模块，主要实现对数据流和控制流的控制，使整个项目的控制部分。这两大模块有机的结合共同构成了这个项目的全部面貌。3.3.1硬件环境塔里木大学课程设计第3页共10页微型计算机：联想台式品牌机中央处理器：Pentuim4主频：3.0GHz主存容量：512M硬盘容量：80G3.3.2软件环境WindowsXP操作系统MicrosoftNotePad记事本程序MicrosoftVisualC++编译器3.3.3设计流程图图3-1程序流程图3.3.4设计内容一、程序设计的基本算法介绍1、顺序表的存储特点是：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L1≤i≤n其中，L是元素占用存储单元的长度。3.4程序的设计思想和内容1顺序实现设计思路：我没有直接用数组的存储方式，而是采用连续分配内存的方式或者说我把数组实现的代码写了出来，没有直接用库里面的数组形式。每次分配的数量为常量LISTINCREASMENT。程序流程：新建一个顺序表（初始表长为7）→显示构建的表及表长→依次检验删除，插入检索功能并显示操作后的顺序表开始顺序表元素的插入元素的检索删除一个元素输出表和读表建立表长为7的顺序表SWICH语句塔里木大学课程设计第4页共10页3.4.1程序设计的初始运行环境这个项目是由主函数模块和功能函数模块组成的。其中主函数模块是项目的控制部分，很重要的一个作用就是对整个程序的初始化功能。在设计初始运行环境时，为了每一次栈操作后都可以进行对程序的初始化，采用了do…while循环语句构成一个无限循环，使得每一次栈操作之后都可以将程序初始化重新选择对栈的另一个操作，例如：选择2，将若干个数据压入栈中之后，程序便又回到了初始的界面，我们可以选择4进行出栈操作。代码如下：#includestdio.h#includeconio.h#includestdlib.h#includemalloc.h#includeiostream#defineLISTINCREASMENT2#defineLISTSIZE5typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}Sqlist;voidSqInitial(Sqlist*ps){ps-elem=(ElemType*)malloc(LISTSIZE*sizeof(ElemType));ps-length=0;ps-listsize=LISTSIZE;}voidListInsert(Sqlist*ps,inti,ElemTypee){if(i1)printf(ERROR!);if(ps-length=ps-listsize){ElemType*newbase=(ElemType*)realloc(ps-elem,(ps-listsize+LISTINCREASMENT)*sizeof(ElemType));ps-elem=newbase;ps-listsize+=LISTINCREASMENT;}ElemType*q=&(ps-elem[i-1]);ElemType*p;for(p=&(ps-elem[ps-length-1]);p=q;--p)塔里木大学课程设计第5页共10页*(p+1)=*p;*q=e;++ps-length;}voidListDelete(Sqlist*ps,inti,ElemTypee){if(i1||ips-length)printf(ERROR!);ElemType*p=&(ps-elem[i-1]);e=*p;ElemType*q=ps-length+ps-elem-1;for(++p;p=q;++p)*(p-1)=*p;--ps-length;}ElemTypeGetElem(Sqlist*ps,inti){if(i1||ips-length)printf(ERROR!);returnps-elem[i-1];}voidmain(){Sqlist*L;intt=1,d;L=newSqlist;SqInitial(L);printf(构建长度为7的顺序表。\n);for(t=1;t=7;t++){printf(Pleaseinputthe%dthlistelem:,t);scanf(%d,&d);ListInsert(L,t,d);}printf(表长：%d\n,L-length);for(t=1;t=L-length;t++)printf(%d,L-elem[t-1]);塔里木大学课程设计第6页共10页printf(\n删除的位置：);scanf(%d,&t);ListDelete(L,t,d);printf(删除元素的值：%d\n,d);printf(删除后的表：);for(t=1;t=L-length;t++)printf(%d,L-elem[t-1]);printf(\n要插入的位置);scanf(%d,&t);printf(要插入的值);scanf(%d,&d);ListInsert(L,t,d);printf(插入以后的表：);for(t=1;t=L-length;t++)printf(%d,L-elem[t-1]);printf(\n要检索的元素的位置：);scanf(%d,&t);d=GetElem(L,t);printf(该元素的值为：%d\n,d);}具体运行截面如下图：图3-2界面的循环初始化塔里木大学课程设计第7页共10页3.4.2顺序表的初始化具体代码如下:voidSqInitial(Sqlist*ps){ps-elem=(ElemType*)malloc(LISTSIZE*sizeof(ElemType));ps-length=0;ps-listsize=LISTSIZE;}3.4.3顺序表的插入构建长度为7的顺序表具体程序代码及运行后的界面如下：voidmain(){Sqlist*L;intt=1,d;L=newSqlist;SqInitial(L);printf(构建长度为7的顺序表。\n);for(t=1;t=7;t++)塔里木大学课程设计第8页共10页图3-3进栈操作3.4.4输出表长、读表具体操作代码如下：{printf(Pleaseinputthe%dthlistelem:,t);scanf(%d,&d);ListInsert(L,t,d);}printf(表长：%d\n,L-length);for(t=1;t=L-length;t++)printf(%d,L-elem[t-1]);图为两个数据的运行结果：图3-4栈元素的删除操作。3.4.顺序表的删除操作顺序表的删除的具体代码如下：printf(\n删除的位置：);scanf(%d,&t);ListDelete(L,t,d);printf(删除元素的值：%d\n,d);塔里木大学课程设计第9页共10页printf(删除后的表：);for(t=1;t=L-length;t++)printf(%d,L-elem[t-1]);图为删除元素与删除后的运行结果：3.5.元素的插入具体代码如下：printf(\n要插入的位置);scanf(%d,&t);printf(要插入的值);scanf(%d,&d);ListInsert(L,t,d);printf(插入以后的表：);for(t=1;t=L-length;t++)printf(%d,L-elem[t-1]);图为元素插入以及插入后的表：塔里木大学课程设计第10页共10页3.6.检索元素检索元素的具体代码如下：printf(\n要检索的元素的位置：);scanf(%d,&t);d=GetElem(L,t);printf(该元素的值为：%d\n,d);}图为检索元素后的运行：塔里木大学课程设计第11页共10页图3-5出栈操作3.5设计创新与关键技术这个课程设计是一个简单的设