顺序表的基本实现和存储结构数据结构顺序表课程设计.doc

1、目 录一.目的51、设计目的：52、试验目的：6二.实验环境7三.实验学时7四.实验内容7五.需求分析7六.概述81、顺序表的概述：82、.初始化操作：83、.求长度操作：94、.判空操作：95、.清空操作：106、取元素操作：107、按值查找操作：118、插入操作：129、删除操作：13七、实验步骤与源程序14八、程序测试结果18九、顺序表的优点和缺点191、顺序表的优点：202、顺序表的缺点：20十、总结20一.目的1、设计目的：数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算

2、法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。在当今信息时代，信息技术己成为当代知识经济的核心技术。我们时刻都在和数据打交道。比如人们在外出工作时找最短路径，在银行查询存款、通过互联网查新闻、以及远程教育报名等，所有这些都在与数据发生关系。实际上，现实世界中的实体经过抽象以后，就可以成为计算机上所处理的数据。数据结构课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于

3、数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：(1)、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；(2)、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；(3)、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；(4)、训练用系统的

4、观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2、试验目的： (1)、掌握线性表的顺序存储结构和链式存储结构； (2)、熟练掌握顺序表和链表基本算法的实现； (3)、掌握利用线性表数据结构解决实际问题的方法和基本技巧； (4)、按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）； (5)、按时提交实验报告18二.实验环境计算机、C语言程序设计环境。三.实验学时10学时，必做实验。四.实验内容1、实现顺序表的基本操作，线性表中数据元素类型为 结构体，成员包括学生的姓名、学号、若干课程的成绩（int型），按照顺序

5、存储结构实现如下算法： (1)、创建任意线性表，长度限定在100个学生信息之内； (2)、打印（遍历）该线性表（依次打印出表中元素值）； (3)、在线性表中查找第i个元素，并返回其值； (4)、在线性表中第i个元素之前插入一已知元素； (5)、在线性表中删除第i个元素；五.需求分析线性表的顺序存储结构是把线性表中所有数据元素，按照其逻辑顺序一次存储到计算机存储器中从指定位置开始的一块连续的存储空间中，数据元素间的存储（物理）位置即表示了它的逻辑位置。也就是说，逻辑上的第一个元素就存放在指定的第一个位置，逻辑上的第二个元素就存放在指定的空间的第二个元素，.依次类推。设线性表L=（a1,a2,a3

6、,.an）,假定L中的每个元素需占用K个存储单元，则在线性表存储结构中，L的第i+1个元素的存储地址Loc(ai+1)和第i个数据元素的存储地址loc（ai）之间满足下列关系： Loc(Ai+1)=Loc(Ai)+k一般地，线性表中第i个数据元素Ai的存储地址为： Loc(Ai)=Loc(Ai)+(i-1)*k (1=n)其中，Loc(Ai)为线性表的第一个元素A1的存储位置，通常又称作线性表的起始地址或基地址，n为线性表的表长。六.概述1、顺序表的概述：通常把使用顺序存储实现的线性表称为顺序表线性表的顺序存储结构是把线性表中所有数据元素，按照其逻辑顺序一次存储到计算机存储器中从指定位置开始的

7、一块连续的存储空间中，数据元素间的存储（物理）位置即表示了它的逻辑位置。2、.初始化操作： 在程序中，使用SqList类型用如下语句定义顺序表L： 此时，L实际上只是一个机构体变量，其有3个分量base、length及listSize，但这 3个分量并没有确切的值，并且base仅为一个指针量，还没有与之对应的顺序表所需的存储空间。因此在使用顺序表L时，首先应对其进行初始化。所以此初始化操作的作用就是从内存中申请一块可共使用顺序表L使用的大小为InitSize的存储空间。并使L成为一个空表（将其长度 赋值为0）顺序表的初始化操作算法见下：void initlist(sqlist *l,int i

8、nitsize) l-base=(int *)malloc(initsize * sizeof(int);if(l-base=NULL)return -2;l-length=0;l-listsize=initsize;return 1;3、.求长度操作： 顺序表L的length分量的值即为其长度。该操作的实现算法见下：int listlength(sqlist l)return l-length;4、.判空操作：判断顺序表L是否为空即判断其length分量的值是否为0.该操作的实现算法见下：status lengthisempty(sqlist l)if(!l-length)return 1e

9、lse return 05、.清空操作： 将顺序表L清空，只需将length值为0即可。该操作的实现算法见下：void clearlist(sqlist &l)l-length=0;6、取元素操作：当顺序表L非空时，数组下标为i-1的元素即为其第i个元素。该操作算法见下：status getelem(sqlist l,int i,lelemtype &e)if(!l-length)return 0;e=l-basei-1;return 1;7、按值查找操作：该操作用来在顺序表L中查找死一个与给定的数据元素e值相等的元素，并返回其位序。所以可从L中的第一个元素（下标为0的元素）开始一次与e进行比

10、较，若某个元素与e相等则返回其位序（下标加1）。若未找到与e相等的元素，因为顺序表中位序最小为1因此可返回0表示查找失败。顺序表的按值查找操作算法见下：int locateelem(sqlist l,lelemtype e)int i=0;while(ilength & *(l-base+i)!=e)i+;if(ilength)return i+1;else return 0;8、插入操作：在线性表L的第i个位置插入一个新的元素e，则原来的第i个元素变为第i+1个，原来的第i+1个元素就变为第i+2依次类推。该操作算法见下：void insertlist(sqlist *l,int i,int

11、 e)lelemtype *newbase; int j;if(i1 | ilength+1)printf(不合理);return 0;if(l-length=l-listsize)printf(满表);return 0;for(j=l-length-1;j=i-1;j-)l-basej+1=l-basej;l-basei-1=e;l-length+;return 1; 9、删除操作：该操作作用于删除顺序表L的第i（0i=ListLength(L)）个数据元素并用e返回其值.时原来的长度为n的顺序表变成长度为n-1.该操作算法见下:void deletelist(sqlist *l,int i

12、) int j;if(il-length-1)printf(不合理);return 0;if(l-length=0)printf(空表);return 0;for(j=1;jbasej=l-basej+1;l-length-;return 1;七、实验步骤与源程序#include #define listspaceincr 10typedef structint *base;int length;int listsize;sqlist;void initlist(sqlist *l,int initsize) l-base=(sqlist*)malloc(sizeof(sqlist);if(!

13、l-base)return;l-length=0;l-listsize=initsize;void creatlist(sqlist *l)int i;for(i=0;ilength;i+)scanf(%d,&l-basei);void print(sqlist *l) int i;for(i=0;ilength;i+)printf(%6d,l-basei);void insertlist(sqlist *l,int i,int e)int *newbase;int j;if(il-length+1)return 0;if(l-length=l-listsize)newbase=(int*)r

14、ealloc(l-base,(l-listsize+listspaceincr) *sizeof(int);if(!newbase)return -2;l-base=newbase;l-listsize+=listspaceincr;for(j=l-length-1;j=i-1;j-)l-basej+1=l-basej;l-basei-1=e;l-length+;return 1;void deletelist(sqlist *l,int i)int j;if(il-length)return 0;for(j=i;jlength;j+)l-basej-1=l-basej;l-length-;r

15、eturn 1; void main()int flag=1,a,i,e,n,j;sqlist l;while(flag)printf(ntt1:初始化ntt2:建立顺序表ntt3:输出顺序表ntt4:在顺序表中插入元素ntt5:在顺序表中删除元素ntt:其他退出n);printf(ntt请选择:);scanf(%d,&a);switch(a) case 1: printf(n请输入初始化空间的大小:); scanf(%d,&n); initlist(&l,n); break; case 2: printf(n请输入顺序表的元素个数:); scanf(%d,&l.length); creatl

16、ist(&l); break; case 3:print(&l); break; case 4:printf(n请输入插入的位置与插入的元素:); scanf(%d%d,&i,&e); insertlist(&l,i,e); break; case 5:printf(n请输入删除的位置:); scanf(%d,&j); deletelist(&l,j); break; default :flag=0;八、程序测试结果选择“从文件读取信息”，程序将从文件读取信息，如果读取失败（不存在该信息文件），则结束，如果读取成功，则输出读取成功的提示信息， 九、顺序表的优点和缺点1、顺序表的优点：(1)、实

17、现方法简单,各种高级语言中都有数组,容易实现;(2)、访问元素的速度快,因为在顺序表中逻辑张相邻的两个元素在存储位置上也必定相邻,所以只要知道了第一个元素的地址,其他任何一个元素的地址都可以通过简单的计算求的,故可实现随即存取,即顺序表L的第i个元素即为L.basei-1.2、顺序表的缺点：(1)、需占用连续的空间.存储要求高,不能利用小块存储区;(2)、由于在顺序表中逻辑上相邻的两个元素在存储位置上也必定相邻,所以在进行插入和删除操作的时候,需要进行大量的元素移动操作,影响了算法的效率.十、总结由于本课题中的许多知识点都没有学过都要靠自己到课外的资料中去查找。在用的时候难免出现这样那样的错误

18、。如开始设计出来的菜单不是预想的那样，而是总个窗中出现混乱。解决的这个问题的办法是调整。一个系统的菜单和提示信息非常重要。如果没有这些用户根本不知道怎么用你设计的这个系统。在设计的调试过程中也无法顺利的完成调试工作。有了一个清晰简单的菜单和一些提示信息这后，调试过程完成的非常顺利。回顾起此次课程设计，至今我仍感慨颇多，的确，从拿到题目到完成整个 编程，从理论到实践，虽然只有几天，但可以学到很多的东西，不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说结构体通过这次课程设计之后，一定把以前所学过的知识本次课程设计结束了，对于我的影响很大。我通过这次实践学到了许多知识。学到了设计一个简单的系统。要注意哪些方面。也使我知道自己哪些方面做得还不够。