数据结构概念及顺序表

《数据结构概念及顺序表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构概念及顺序表西安交通大学计教中心ctec.xjtu.edu.cn2.1数据结构基本概念1．数据（data）数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。2．数据元素（dataelement）数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位数据结构（datastructure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。这三个方面的关系为：数据的逻辑结构独立于计算机，是数据本身所固

2、有的存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。数据结构基本类型线性结构——通迅录、成绩单、花名册树形结构——电子字典、家谱、目录图状结构——交通线路、通信网络数据结构中常用的存贮结构(1)顺序存贮所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。(2)链式存贮所有元素存放在可以不连续的存贮单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。(3)索引存贮（略）(4)散列存贮（略）算法（algorithm）通俗地讲，算法就是

3、一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：（1）输入：具有0个或多个输入的外界量（算法开始前的初始量）（2）输出：至少产生一个输出，它们是算法执行完后的结果。（3）有穷性：每条指令的执行次数必须是有限的。（4）确定性：每条指令的含义都必须明确，无二义性。（5）可行性：每条指令的执行时间都是有限的。1．时间复杂度一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。数据结构中数据元素个数n称为问题的规模，当n不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数量级

4、来衡量。例如：for(i=1;i<=n;i++)for(j=1;j<=i;j++)d[i][j]=data[i][j]+1;算法分析O(n2)2．空间复杂度与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。2.2线性数据结构线性表是由有限个同类型的数据元素组成的有序序列，一般记作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一个直接前趋ai-1和一个直接后继ai+1。a1无前趋，an无后继。线性表的存储结构主要有顺序存储结构和链式存储结构两种。顺序表采用

5、顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。假定元素a1的物理地址是Loc(a1)，每个元素占d个存储单元，则第i个元素的存储位置为：Loc(ai)=Loc(a1)+(i-1)*dlength=nmaxsize01i-2i-1in-1a2…ai-1aiai+1a1…an顺序表类描述constintMAXSIZE=100;//顺序表最大允许长度classSeqList{public:ElemTypedata[MAXSIZE];//存储数据的数组intlength;//顺序表当前长度SeqList(){le

6、ngth=0;}//构造函数voidClearList(){length=0;}//将顺序表置为空表//判断顺序表是否为空表boolIsListEmpty(){returnlength==0;}(下页continue….)(接上页)//判断顺序表是否为满boolIsListFull(){returnlength==MAXSIZE;}//在表中删除第i个元素voidListDelete(inti);//在表中第i个位置插入新元素xvoidListInsert(inti,ElemTypex);intFind(ElemTypex);//在表中查找元素};（1）ElemType代表数组的某种类型。

7、（2）length表示线性表当前长度，初始长度为0（空表），最大不超过maxsize。顺序表的主要算法（1）在表中第i个位置插入新元素x算法实现的主要步骤是：①判断插入位置的合理性以及表是否已满。②从最后一个元素开始依次向前，将每个元素向后移动一个位置，直到第i个元素为止。③向空出的第i个位置存入新元素x。④最后还要将线性表长度加一。voidSeqList::ListInsert(inti,ElemTypex){if(