2第二章线性表.ppt

第二章 线性表 2．1 线性表的定义及运算 2．1．1 线性表的定义及逻辑特征 2．1．2 线性表上运算的定义 2．1．3 线性表的存储结构 2．2 顺序表 2．2．1 顺序表的定义及表示 2．2．2 线性表运算在顺序表上的实现 2．2．3 顺序表应用举例 2．3 链表 2．3．1 链表的定义及形式 2．3．2 单链表 2．3．3 循环链表 2．3．4 双链表 *2．3．5 静态链表 2．3．6 单链表的应用举例 2．4 顺序表和链表的比较 回顾：数据的逻辑结构有两大类： （1）线性结构：经典的线性结构是线性表。 线性结构的逻辑特征是：有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点，也就是说结构中的数据元素间存在着一对一的相互关 （2）非线性结构：经典的非线性结构有树形结构和图形结构。 树形结构的逻辑特征是：有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点，也就是说结构中的数据元素间存在着一对多的层次关系。 图形结构的逻辑特征是：可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点，也就是说结构中的数据元素间存在着多对多的网状关系。 例:在表1.1中，八名学生按学号从小到大排列，形成一个线性结构。该线性结构的逻辑结构可用二元组表示为： L =（D，S），r1∈S D =｛01，02，03，04，05，06，07，08｝ r 1 =｛01，02，02，03，03，04，04，05， 05，06，06，07，07，08｝ 线性表可以用二元组表示为： linear_list =（D，S），r∈S， D =｛a1，a2，…，ai-1，ai，ai+1，…，an｝ r =｛ a1，a2， a2，a3，…， ai-1，ai ， ai，ai+1，…， an-1，an ｝ 线性表的逻辑结构图示 线性表的存储结构 顺序存储、链接存储、索引存储、散列存储，这四种方法都可以用来存储线性表。 顺序存储和链接存储是线性表最常用的两种存储方法。 线性表用顺序方式存储就称为顺序表。 线性表用链接方式存储就称为链表。 线性表上运算的定义 （1）线性表初始化initList（L）：构造一个空的线性表 （2）求线性表的长度lengthList（L）：返回线性表L中所含元素的个数。 （3）取第i个元素getElem（L，i）：当1≤i≤n，返回线性表L中第ｉ个元素的值。 （4）按值查找locateElem（L，x）：在表L中查找值为ｘ的数据元素，若找到，返回L中第一次出现的值为ｘ的那个元素的序号，称为查找成功；否则，返回一特殊值（0）表示查找失败。 （5）插入insertElem（L，i，x）：在线性表L的第ｉ个位置插入一个值为ｘ的新元素，这样使原序号为 i，i+1，…，ｎ的数据元素的序号变为i+1，i+2，…，n+1，插入后表长等于原表长加1，插入位置可以为1≤i≤n+1。 （6）删除操作deleteElem（L，i）：在线性表L中删除序号为ｉ的数据元素，删除后使序号为 i+1，i+2，…，n 的元素的序号变为 i，i+1，…，n-1，新表长等于原表长减１，删除位置可以为1≤i≤n。 2．2 顺序表 顺序表的定义及表示 顺序表（Sequential List）是采用顺序存储结构的线性表。也就是将线性表中逻辑上相邻的结点存储在物理上相邻的单元中，使得线性表的所有元素按逻辑次序依次存放到一组地址连续的存储空间内。可以借用数组来实现顺序表。 顺序表存储结构用Ｃ语言描述如下： #define MAXSIZE 1024 typedef int DataType; typedef struct { DataType data [ MAXSIZE ] ; int last; } SeqList; SeqList SL; 静态存储分配方式 Sealift *L =SL； L=(SeqList*)malloc(sizeof(SeqList));动态分配存储 在实际运算中顺序表L一般定义为SeqList类型的指针变量， 即：Sealift *L =SL； 用L来引用结构体SeqList类型变量的各个域的操作方式如下： 线性表的表长为： (*L)．last+1 或 L-last+1 线性表中第一个数据元素为： (*L)．data[0] 或 L-data[0] 最后一个元素表示为： (*L).data[(*L).last] 或 L-