线性表的逻辑结构、顺序表示与链式表示.pptx

上节课要点回顾;数据结构课程的内容;近3周上课内容;线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最简单、最常用的是------;第2章 线性表;（a1, a2, … ai-1，ai, ai+1 ，…, an） ;例1 分析 26 个英文字母组成的英文表;线性表的抽象数据类型的定义： ADT List { 数据对象：D={ai | ai∈Elemset, i=1, 2,…, n, n≥0} 数据关系：R1={ai-1, ai | ai-1, ai∈D, i=2, …, n} 基本操作： InitList(L) 操作结果：构造一个空的线性表L DestroyList(L) 初始条件：线性表已存在 操作结果：销毁线性表L ;ClearList(L) 初始条件：线性表已存在 操作结果：置线性表L为空表 IsListEmpty(L) 初始条件：线性表已存在 操作结果：若线性表L为空表，则返回TRUE，否则返回FALSE ListLength(L) 初始条件：线性表已存在 操作结果：返回线性表L数据元素个数 GetElem(L, i, e) 初始条件：线性表已存在（1 ≤ i ≤ ListLenght(L)） 操作结果：用e返回线性表L中第i个数据元素的值;locateElem(L, e, compare()) 初始条件：线性表已存在, compare()是数据元素判定函数 操作结果：返回线性表L中第1个与e满足关系comare()的数据元素的位序 PriorElem(L, cur_e, pre_e) 初始条件：线性表已存在 操作结果：若cur_e是线性表L的数据元素，且不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义 NextElem(L, cur_e, next_e) 初始条件：线性表已存在 操作结果：若cur_e是线性表L的数据元素，且不是第最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义;ListTraverse(L, visit()) 初始条件：线性表已存在 操作结果：遍历线性表。依次对线性表L的每个数据元素调用visit()函数，一旦visit()失败，则操作失败 ListInsert(L, i, e) 初始条件：线性表已存在（1 ≤ i ≤ ListLenght(L)+1） 操作结果：在线性表L中第i个数据元素之前插入新元素e， L长度加1 ListDelete(L, i, e) 初始条件：线性表已存在（1≤ i ≤ListLenght(L)） 操作结果：删除线性表L中第i个数据元素，用e返回其值，L长度减1 }ADT List;上述是线性表抽象数据类型的定义，其中只是一些基本操作，另外可以更复杂。如将两个线性表合并等。复杂的操作可用基本操作实现。 例3：将两个非递减的表合成为一个非递减的表 void MergeList(List la, List lb, list lc) { InitList(lc); i=j=1; k=0; la_len=ListLength(la); lb_len=ListLength(lb);;while(i=la_len j=lb_len) { GetElem(la, i, ai); GetElem(lb, j, bj); if(ai=bj) { ListInsert (lc, ++k, ai); i++; } else { ListInsert (lc, ++k, bj); j++; } } while(i=la_len) { GetElem(la, i++, ai); ListInsert(lc, ++k, ai);} while(j=lb_len) { GetElem(lb, j++, bj); ListInsert(lc, ++k, bj);} };2.2 线性表的顺序表示和实现;2.2.1 顺序表的表示;线性表顺序存储特点：;线性表的顺序存储结构示意图;例4：一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是98，则Ｍ[３]的第一个字节的地址是;线性表的顺序存储结构定义（静态）;2.2.2 顺序表的实现（或操作）;1)插入:在线性表的第i个位置前插入一个元素, 使长度为n的线性表变为长度为n+1的线性表。;程序实现： Status ListInsert_Sq(SqList L, int i, ElemType x) { //在线性表L的第i个元素