数据结构-第二章.pdf

数据结构第二章线性表的基本概念和实现 数据结构是计算机科学中的一门重要学科，涉及到计算机存储和处理数据的方式和方法。本章节主要介绍了数据结构的基本概念，包括线性表的定义、线性表的顺序存储结构和链式存储结构，以及线性表的基本操作。 一、线性表的基本概念 线性表是一种最常见、最简单的一种线性结构。线性表是n个具有相同特性的数据元素的有限序列。线性表的数学定义是Linear_list =（D，R），其中，D={ai|ai∈DO，i=1，2，…，n} DO为一个数据对象，R={（ai-1,ai）|ai-1,ai∈D, i=2,…,n}。 线性表的基本特点是：在数据元素的非空有限集中，存在唯一的被称做“第一个”的数据元素；存在唯一的被称做“最后一个”的数据元素；除第一个之外，集合中每个数据元素均只有一个前驱；除最后一个之外，集合中每个数据元素均只有一个后继。 二、线性表的顺序存储结构 线性表的顺序存储结构是指将线性表中的元素按照其逻辑排列的顺序依次存放在一组地址连续的存储单元（一维数组）中。这种结构称为顺序表。 顺序表的特点是：数据元素的逻辑顺序和物理上的存储顺序完全一致，不必额外考虑对数据元素关系的存储。实现随机存取（访问数据元素的效率很高）。可用C/C++语言的一维数组实现。 三、链式存储结构 链式存储结构是另一种实现线性表的方法。链式存储结构是指将每个数据元素存储在一个独立的存储单元中，并使用指针将这些存储单元连接起来，形成一个链表。 四、线性表的基本操作 线性表的基本操作包括： 1. 初始化InitList(&L)---创建一个新的空表 2. 销毁DestroyList(&L)---存在->不存在 3. 置空表ClearList(&L)---线性表->空集 4. 求长度ListLength(L) 5. 取元素GetElem(L ,i,&e)---按序号查找 6. 定位函数LocateElem(L, x)---找出第一个与x相同值的位置 7. 插入ListInsert(&L, x, i) 8. 删除ListDelete(&L, i) 9. 其它操作：求前驱、后继元素、遍历表 这些基本操作是实现更多复杂操作的基础，如算法2.1、2.2等。 本章节主要介绍了线性表的基本概念、顺序存储结构和链式存储结构，以及线性表的基本操作。这些基础知识是学习更高级的数据结构和算法的前提。