数据结构介绍

《数据结构介绍》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构基础数据结构专门研究各种数据的表示、数据的类型以及他们之I'可关系的集合，其研究范围主要包括各种数据结构的性质，既它们的逻辑结构、物理结构以及施于其上的操作。数据结构分类如下：简单类型整型、实型、字符型、布尔型静态数据类型构造类型数组、记录、集合、字符串文件、指针动态数据类型线性类型线性表、栈、队列、链表、串非线性类型树、图线性表线性表(LinearList)是最常用且比较简单的一种数据结构，它是由有限个数据元素组成的有序集合，每个数据元素由一个或多个数据项组成。比如：26个英文字母的字

2、母表(A,B,C,……Z)是一个线性表，表中每个元素由单个字母字符组成数据项。线性表具有如下的结构特点：1•均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据长度。2.有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个“的数据元素，除了第一个和最后一个外,其它元素前面均只有一个前趋元素和后面均只有一个后继元素。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方

3、法。另外栈、队列和串也是线性表的特殊情况，又称为受限的线性结构。线性表的顺序存储结构有下列性质：假设线性表的每个元素占用L个存储单元,并以所占的第一个单元的存储地址b作为数据元素的起始位置，则线性表中第i+1个数据元素的存储位置loc(ai+l)和第i个数据元素的存储位置loc(ai)Z间应满足下列关系：loc(ai+1)=loc(ai)+Lloc(ai)=b+(i-l)L线性表的这种机内表示法称为线性表的顺序存储结构。也就是主元素在计算机内以“物理位相邻“来表示线性表中数据元素之间的关系。每一

4、个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。因此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。在Pascal语言中可用一维数组描述线性表的顺序存储结构。二、栈“栈”的应用很广泛，大家在PASCAL程序设计中，常遇的一种错误就是“栈”超界，那么,“栈”为何物呢？栈是只能在某一端插入和删除的特殊线性表。用桶堆积物品，先堆进来的压在底下，随后一件一件往堆。取走时，只能从上面一件一件取.

5、堆和取都在顶部进行，底部一般是不动的。栈就是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一堆称栈底。数据结构基础数据结构专门研究各种数据的表示、数据的类型以及他们之I'可关系的集合，其研究范围主要包括各种数据结构的性质，既它们的逻辑结构、物理结构以及施于其上的操作。数据结构分类如下：简单类型整型、实型、字符型、布尔型静态数据类型构造类型数组、记录、集合、字符串文件、指针动态数据类型线性类型线性表、栈、队列、链表、串非线性类型树、图线性表线性表(LinearList)是最常用且比较

6、简单的一种数据结构，它是由有限个数据元素组成的有序集合，每个数据元素由一个或多个数据项组成。比如：26个英文字母的字母表(A,B,C,……Z)是一个线性表，表中每个元素由单个字母字符组成数据项。线性表具有如下的结构特点：1•均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据长度。2.有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个“的数据元素，除了第一个和最后一个外,其它元素前面

7、均只有一个前趋元素和后面均只有一个后继元素。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。另外栈、队列和串也是线性表的特殊情况，又称为受限的线性结构。线性表的顺序存储结构有下列性质：假设线性表的每个元素占用L个存储单元,并以所占的第一个单元的存储地址b作为数据元素的起始位置，则线性表中第i+1个数据元素的存储位置loc(ai+l)和第i个数据元素的存储位置loc(ai)Z间应满足下列关系：loc(ai+1)=loc(ai)+Lloc(ai)=b+(i-l)L线性表的

8、这种机内表示法称为线性表的顺序存储结构。也就是主元素在计算机内以“物理位相邻“来表示线性表中数据元素之间的关系。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数。因此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。在Pascal语言中可用一维数组描述线性表的顺序存储结构。二、栈“栈”的应用很广泛，大家在PASCAL程序设计中，常遇的一种错误就是“栈”超界，那么,“栈”为何物呢？栈是只