第3章数据结构——线性表

《第3章数据结构——线性表》由会员分享，可在线阅读，更多相关《第3章数据结构——线性表（79页珍藏版）》请在文档大全上搜索。

1、第三章第三章 线性表线性表DS应用实践 线性表的概念 双向链表 循环链表 线性表的顺序存储 单向链表 线性结构特点线性结构特点在数据元素的非空有限集中在数据元素的非空有限集中 存在唯一的一个被称作“第一个”的数据元素 存在唯一的一个被称作“最后一个”的数据元素 除第一个外，集合中的每个数据元素均只有一个前驱 除最后一个外，集合中的每个数据元素均只有一个后继3.1 线性表的概念线性表的概念niaaaa,21如例 英文字母表（A,B,C,.Z)是一个线性表 定义：一个线性表是n个数据元素的有限序列3.1.1线性表的定义线性表的定义3.1 线性表的概念线性表的概念 特征： 元素个数n表长度，n=0空

2、表 1in时ai的直接前驱是ai-1，a1无直接前驱ai的直接后继是ai+1，an无直接后继 元素同构，且不能出现缺项3.1.1 线性表的定义线性表的定义3.1.2 线性表的抽象数据类型描述线性表的抽象数据类型描述ADT List 数据对象：D ai | ai ElemType, i=1,2,.,n, n0 数据关系：R |ai-1 ,aiD, i=2,.,n 基本操作： （详见下页） ADT List 基本操作InitList(SqList *L )/线性表的初始化，即构造一个空的线性表LDestroyList(SqList &L )/释放线性表L占用的内存空间ListEmpty(S

3、qList L )/判断线性表L是否为空表ListLength(SqList L ) /求线性表的长度，返回L中元素个数GetElem(SqList L, int i, DataType *e) /求线性表L中第i(1in)个元素的值 基本操作LocateElem(SqList L, DataType e) /返回L中第1个与e满足关系的数据元素位序ListTraverse(SqList L) /依次对线性表L的每个元素进行遍历ClearList(SqList *L ) /将线性表L重置为空表PutElem(SqList L,int i, DataType *e ) /给线性表L中第i个元素赋

4、值ListInsert(SqList *L, int i, DataType e ) /在线性表L的第i个元素之前插入新的元素eListDelete(SqList *L, int i, DataType *e) /删除L的第i个元素，并用e返回其值，L的长度减1 基本操作CreateListHead(SqList *L, int n) /用头插法建立带表头结点的单链线性表LCreateListTail(SqList *L, int n) /用尾插法建立带表头结点的单链线性表L定义：用一组地址连续的存储单元存放一个线性表叫定义：用一组地址连续的存储单元存放一个线性表叫元素地址计算方法元素地址计算

5、方法 LOC(ai+1)=LOC(ai)+d LOC(ai)=LOC(a1)+(i-1)*dd 一个元素占用的存储单元个数LOC(ai)线性表第i个元素的地址3.2 线性表的顺序存储线性表的顺序存储特点：特点： 实现逻辑上相邻实现逻辑上相邻物理地址相邻物理地址相邻 实现随机存取实现随机存取实现：可用C语言的一维数组实现在C语言中，线性表的顺序存储的类型定义如下：typedef int DataType; / DataType类型根据实际情 况而定，这里假设为int#define MAXSIZE 100 / MAXSIZE可根据实际 情况而定 typedef structDataType dat

6、aMAXSIZE; int length; SqList;图3.1 线性表的顺序存储结构 a1a2an01n-112n内存V数组下标元素序号M-1typedef int DataType; #define MAXSIZE 100例 typedef struct DataType dataMAXSIZE int length;SqList;备用空间数据元素不是简单类型时,可定义结构体数组3.2.2顺序表的基本运算顺序表的基本运算 1.线性表的初始化int InitList(SqList *L) L.length=0; /空表，长度为空表，长度为0 return OK; 3.2.2顺序表的基本运算

7、顺序表的基本运算 2.释放线性表void DestroyList(SqList &L) if (L-data) free(L-data); /释放线性表占据的所释放线性表占据的所有存储空间有存储空间 3.2.2顺序表的基本运算顺序表的基本运算 3.判断线性表是否为空表int ListEmpty(SqList L) if (L.length=0) return TRUE; if (L.length!=0) return FALSE; 3.2.2顺序表的基本运算顺序表的基本运算 4.求线性表的长度int ListLength(SqList L) return (L.length); 3.2

8、.2顺序表的基本运算顺序表的基本运算 5.求线性表中第i个元素的值int GetElem(SqList L,int i,DataType *e) if (iL.length) return ERROR; /判断判断i值是否合理，若不合值是否合理，若不合理，返回理，返回ERROR *e=L.datai-1; /数组中第数组中第i-1的单元存储着线的单元存储着线性表中第性表中第i个数据元素的内容个数据元素的内容 return OK; 3.2.2顺序表的基本运算顺序表的基本运算 6.返回线性表中第1个与e满足关系的数据元素位序int LocateElem(SqList L, DataType e)

9、int i; for (i=1; i=L.length; +i) if (e = L.datai-1) return i; return FALSE 3.2.2顺序表的基本运算顺序表的基本运算 7.遍历线性表void ListTraverse(SqList L) int i; for (i=i; ilength=0; /将线性表的长度置为将线性表的长度置为0 3.2.2顺序表的基本运算顺序表的基本运算 9.给线性表中第i个元素赋值int PutElem(SqList L,int i,DataType *e) if (iL.length) return ERROR; /判断判断i值是否合理，若不

10、合值是否合理，若不合理，返回理，返回ERROR L.datai-1=*e; /数组中第数组中第i-1的单元存储着线的单元存储着线性表中第性表中第i个数据元素的内容个数据元素的内容 return OK; v定义：线性表的插入是指在第定义：线性表的插入是指在第i（1 1 i i n+1 n+1）个个元素之前插入一个新的数据元素元素之前插入一个新的数据元素x，使长度为使长度为n的的线性表线性表变成变成长度为长度为n+1的线性表的线性表niiaaaaa,1,21niiaaxaaa,1,21 需将第i至第n共（n-i+1)个元素后移3.2.2顺序表的基本运算顺序表的基本运算 10.插入 数据元素数据元素

11、ai-1和和 ai 的逻辑关系发生了变化。在线性表的逻辑关系发生了变化。在线性表的顺序存储结构中，由于逻辑上相邻的数据元素在物理的顺序存储结构中，由于逻辑上相邻的数据元素在物理上也是相邻的，因此，除非上也是相邻的，因此，除非i = n + 1，否则必须移动元，否则必须移动元素才能反映这个逻辑关系的变化。素才能反映这个逻辑关系的变化。图图3.2 线性表插入前后的状况内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1内存a1a2aiai+1an01i-1V数组下标n-1in12i元素序号i+1nn+1an-1xint ListInsert(SqList *L,i