数据结构实用教程（C语言版） 董凤服及算法 第2章 线性表

《数据结构实用教程（C语言版） 董凤服及算法 第2章 线性表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构实用教程（C语言版）中国水利水电出版社第2章线性表本章主要介绍下列内容线性表的定义和基本操作线性表的顺序存储结构线性表的链式存储结构线性表的应用举例本章目录2.1线性表的基本概念12.2顺序表22.3链表32.4线性表的应用举例42.5本章小结5结束2.1线性表的基本概念2.1.1线性表的定义2.1.2线性表的基本操作返回到总目录2.1.1线性表的定义1.线性表的定义线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，通常记为：（a1，a2，…ai-1，ai，ai+1，…an）其中n为表长，当n=0时称为空表。在线性表

2、中相邻元素之间存在着顺序关系。如对于元素ai而言，ai-1称为ai的直接前驱，ai+1称为ai的直接后继。返回到本节目录2.线性表的特点（1）有且仅有一个开始结点（a1），它没有直接前驱；（2）有且仅有一个终端结点（an），它没有直接后继；（3）除了开始结点和终端结点以外，其余的结点都有且仅有一个直接前驱和一个直接后继。2.1.1线性表的定义返回到本节目录2.1.2线性表的基本操作数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的。下面定义的线性表的基本操作仅是定义在逻辑结构上的，每一个操作的具体实现只有在确定

3、了线性表的存储结构之后才能完成。线性表的基本操作有：（1）初始化线性表InitList(L)。其作用是建立一个空表L（即建立线性表的构架，但不包含任何数据元素）。返回到本节目录（2）求线性表的长度GetLength(L)。其作用是返回线性表L的长度（即所含数据元素的个数）。（3）求线性表中第i个元素GetElem(L,i,x)。其作用是在1≤i≤GetLength(L)返回成功，并用x存储线性表L的第i个元素的值。（4）按值查找操作Locate(L,x)。在线性表L查找一个与给定值x相等的数据元素，其作用是若存在一个或多个与x相等的数据

4、元素，则返回的元素所在位置的最小值或地址值；否则返回0或NULL值。2.1.2线性表的基本操作返回到本节目录（5）插入操作InsElem(L,i,x)。其作用是在线性表L的第i个位置上插入一个值为x的新元素，使线性表L由（a1，a2，…ai-1，ai，ai+1，…an）变为（a1，a2，…ai-1，x，ai，ai+1，…an）。其中1≤i≤GetLength(L)+1。（6）删除操作DelElem(L,i,x)。其作用是删除线性表L的第i个位置的数据元素并用x将其存储，使线性表L由（a1，a2，…ai-1，ai，ai+1，…an）变为（

5、a1，a2，…ai-1，ai+1，…an）。其中1≤i≤GetLength(L)。（7）输出元素值DispList(L)。其作用是依次扫描线性表L，并输出各元素的值。2.1.2线性表的基本操作返回到本节目录2.2顺序表2.2.1顺序表2.2.2顺序表的基本操作实现返回到总目录1.顺序表的定义数据结构在内存中的表示通常有两种形式，即顺序存储表示和链式存储表示。线性表的顺序存储表示又称为顺序表。线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表的数据元素，我们把用这种存储形式存储的线性表称为顺序表。假设顺序表(a1，a2，…ai-1

6、，ai，ai+1，…an)，每个数据元素占用d个存储单元，则元素ai的存储位置为：Loc(ai)=Loc(a1)+(i-1)×d1≤i≤n2.2.1顺序表返回到本节目录其中，Loc(a1)是顺序表第一个元素a1的存储位置，通称为顺序表的起始地址。顺序存储结构示意图如图2-1所示。顺序表的存储特点：（1）顺序表的逻辑顺序和物理顺序是一致的。（2）顺序表中任意一个数据元素都可以随机存取，所以顺序表是一种随机存取的存储结构。2.2.1顺序表返回到本节目录2.顺序表的类型定义#defineMAXLEN100/*定义常量MAXLEN为100表示存

7、储空间总量*/#defineOK/*定义常量OK为1表示成功*/#defineERROR0/*定义常量ERROR为0表示失败*/#defineOVER-1/*定义常量OVER为-1表示结束*/typedefintElemType;/*定义ElemType为int类型*/typedefstruct/*顺序表存储类型*/{ElemTypedata[MAXLEN];/*存放线性表的数组*/intLength;/*Length是顺序表的长度*/}SeqList;2.2.1顺序表返回到本节目录2.2.2顺序表的基本操作实现1．顺序表的初始化顺序表

8、的初始化即构造一个空顺序表L，将表L的实际长度置0，算法描述见算法2.1。算法2.1voidInitList(SeqList*L){L->Length=0;             /*初始的化顺序表为空*