数据结构(第二版) 郑泳 方风波 第二章 线性表新.pptVIP

第二章 线性表 知识教学目标 线性表的逻辑结构 线性表的顺序存储结构及其基本操作 线性表的链式存储结构及其基本操作 循环单链表和双向链表 顺序表和链表的比较 线性表基本运算的时间复杂度 能力培养目标 单链表上的各种操作实现 单向循环链表的基本操作实现 顺序表上的插入、删除和查找运算 单链表上的插入、删除和查找运算 单向循环链表上查找等基本运算 双向链表的定义和运算特点 2.1 线性表及其逻辑结构 2.1.1 线性表的定义 线性表（Linear List）是一种线性数据结构，其特点是数据元素之间存在“一对一”的关系。在一个线性表中每个数据元素的类型都是相同的，即线性表是由同一数据类型的n（n=0）个数据元素的有限序列。 2.1.2 线性表的运算 1) 置空表 2) 求长度 3) 取表中第i个结点 4) 按值查找 5) 插入结点 6) 删除结点 7) 判空表 2.2 线性表的顺序存储 2.2.1 顺序表 用顺序存储方法存储的线性表称为线性表的顺序存储结构，简称为顺序表。它是将线性表中的结点按其逻辑次序依次存储在一组地址连续的存储单元中。 假设线性表L中初始结点a1的内存地址为LOC(a1)，而每个结点在计算机中占用c个存储单元，则第i个结点ai的地址LOC(ai)可通过以下公式计算： LOC(ai) = LOC(a1) + （i–1）* c 1≤i≤n 因此我们用结构体类型来定义顺序表。其定义如下： typedef int DataType； //DataType的类型可根据实际情况而定，这里假设为int ＃define MaxSize 100 //MaxSize顺序表可能的最大长度 typedef struct { DataType data[MaxSize]; //数组data用于存放表结点 int length; //变量length表示表的长度 }SeqList； 2.2.2 顺序表的基本操作 【算法2.1】 置空表InitList（L）。 顺序表的初始化操作，将顺序表的当前长度置为0。算法如下： void InitList (SeqList *L) { L-length=0; } 【算法2.2】 求长度LengthList（L）。 求顺序表中结点的个数。算法如下： int LengthList (SeqList *L) { return L-length; } 【算法2.3】 取结点GetNode（L，i）。 DataType GetNode (SeqList *L , int i) { if (i1) || (iL-length) return NULL; //i的值非法，返回空类型 else return L-data[i-1]; //返回第i个结点（下标是i-1）的值 } 【算法2.4】 判空表IsEmpty(L)。 int IsEmpty(SeqList *L) { if (L-length == 0) return TRUE; else return FALSE; } 1. 查找操作 【算法2.5】 顺序表结点的定位算法。 int LocateNode (SeqList *L , DataType x) { int i; for ( i=0; i L-length; i++ ) if ( L-data[i] == x ) return i; //返回x所在的下标 else return -1; //返回-1作为查找失败的标志 } 该算法的时间复杂度为O(n)。 2. 插入操作 【算法2.6】 顺序表插入结点算法。 int InsertList (SeqList *L , int i , DataType x) { int j; if ( L-length==MaxSize) //表满溢出 { printf(“顺序表已满！”); return (-1); } if (i1 || iL-length+1) //i为非法位置 { printf(“位置出错！”); return (0); } for (j=L-length ; j=i-1 ; j--) //结点依次后移 L-data[j+1]=L-data[j]; L-data[i-1]=x; L-length++; //表长增加1