数据结构线性表PPT（完整版）课件.ppt

第第2 2章章 线性表线性表 2.1 2.1 线性表的基本概念线性表的基本概念 2.2 2.2 线性表的顺序存储线性表的顺序存储2.3 2.3 线性表的链式存储线性表的链式存储2.4 2.4 线性表的应用线性表的应用 本章小结本章小结 2.5 2.5 有序表有序表 最新.课件12.1 2.1 线性表的基本概念线性表的基本概念 2.1.1 线性表的定义线性表的定义2.1.2 线性表的运算线性表的运算最新.课件22.1.1 2.1.1 线性表的定义线性表的定义 线性表是具有相同特性的数据元素的一个有线性表是具有相同特性的数据元素的一个有限序列该序列中所含元素的个数叫做线性表的该序列中所含元素的个数叫做线性表的长度长度,用用n表示表示,n0 当当n=0时时,表示线性表是一个空表表示线性表是一个空表,即表中不包即表中不包含任何元素设序列中第含任何元素设序列中第i(i表示位序表示位序)个元素为个元素为ai(1in) 线性表的一般表示为线性表的一般表示为: (a1,a2,ai,ai+1,an)最新.课件3 其其中中a1为为第第一一个个元元素素,又又称称做做表表头头元元素素,a2为为第第二二个个元元素素,an为为最最后后一一个个元元素素,又又称称做做表表尾尾元元素。

素 例如例如,性表性表 (1,4,3,2,8,10)中中,1为表头元素为表头元素,10为表尾元素为表尾元素最新.课件42.1.2 2.1.2 线性表的运算线性表的运算 线性表的基本运算如下线性表的基本运算如下: (1) 初初始始化化线线性性表表InitList(&L):构构造造一一个个空空的的线线性性表表L (2) 销销毁毁线线性性表表DestroyList(&L):释释放放线线性性表表L占占用用的内存空间的内存空间最新.课件5 (3) 判判线线性性表表是是否否为为空空表表ListEmpty(L):若若L为为空空表表,则返回真则返回真,否则返回假否则返回假 (4) 求求线线性性表表的的长长度度ListLength(L):返返回回L中中元元素素个数 (5) 输输出出线线性性表表DispList(L):当当线线性性表表L不不为为空空时时,顺序显示顺序显示L中各结点的值域中各结点的值域 (6) 求求线线性性表表L中中指指定定位位置置的的某某个个数数据据元元素素GetElem(L,i,&e):用用e返返回回L中中第第 i(1iListLength(L)个元素的值个元素的值最新.课件6 (7) 定定位位查查找找LocateElem(L,e):返返回回L中中第第1个个值值域域与与e相等的位序。

若这样的元素不存在相等的位序若这样的元素不存在,则返回值为则返回值为0 (8) 插插入入数数据据元元素素ListInsert(&L,i,e):在在L的的第第i(1iListLength(L)+1)个个元元素素之之前前插插入入新新的的元元素素e,L的长度增的长度增1 (9) 删除数据元素删除数据元素ListDelete(&L,i,&e):删除删除L的第的第i(1iListLength(L)个元素个元素,并用并用e返回其值返回其值,L的长度的长度减减1最新.课件7 例例2.1 假假设设有有两两个个集集合合 A 和和 B 分分别别用用两两个个线线性性表表 LA 和和 LB 表表示示,即即线线性性表表中中的的数数据据元元素素即即为为集集合合中中的的成成员员编编写写一一个个算算法法求求一一个个新新的的集集合合C=AB,即将两个集合的并集放性表即将两个集合的并集放性表LC中 解解:本算法思想是本算法思想是:先初始化线性表先初始化线性表LC,将将LA的所的所有元素复制到有元素复制到LC中中,然后扫描线性表然后扫描线性表LB,若若LB的当的当前元素不性表前元素不性表LA中中,则将其插入到则将其插入到LC中。

算法中算法如下如下:最新.课件8void unionList(List LA,List LB,List &LC) int lena,lenc,i; ElemType e; InitList(LC); for (i=1;i=ListLength(LA);i+) /*将将LA的所有元素插入到的所有元素插入到Lc中中*/ GetElem(LA,i,e); ListInsert(LC,i,e); lena=ListLength(LA); /*求线性表的长度求线性表的长度*/ lenB=ListLength(LB); 最新.课件9for (i=1;i=lenb;i+) GetElem(LB,i,e);/*取取LB中第中第i个数据元素赋给个数据元素赋给e*/ if (!LocateElem(LA,e) ListInsert(LC,+lenc,e); /*LA中不存在和中不存在和e相同者相同者,则插入到则插入到LC中中*/ 最新.课件10 由由 于于 LocateElem(LA,e)运运 算算 的的 时时 间间 复复 杂杂 度度 为为O(ListLength(LA),所以本算法的时间复杂度为所以本算法的时间复杂度为: O(ListLength(LA)*ListLength(LB)。

最新.课件112.2 2.2 线性表的顺序存储线性表的顺序存储2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表2.2.2 顺序表基本运算的实现顺序表基本运算的实现最新.课件122.2.1 2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表 线性表的顺序存储结构就是线性表的顺序存储结构就是:把线性表中的所把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中器中指定存储位置开始的一块连续的存储空间中 这样这样,线性表中第一个元素的存储位置就是指线性表中第一个元素的存储位置就是指定的存储位置定的存储位置,第第i+1个元素个元素(1in-1)的存储的存储位置位置紧接在第紧接在第i i个元素的存储位置的后面个元素的存储位置的后面线性表线性表 逻辑结构逻辑结构顺序顺序表表 存储结构存储结构最新.课件13 假定线性表的元素类型为假定线性表的元素类型为ElemType,则每个元则每个元素所占用存储空间大小素所占用存储空间大小(即字节数即字节数)为为sizeof(ElemType),整个线性表所占用存储空间的大小整个线性表所占用存储空间的大小为为: n*sizeof(ElemType)其中其中,n表示线性表的长度。

表示线性表的长度最新.课件14顺序表示意图顺序表示意图最新.课件15 在在定定义义一一个个线线性性表表的的顺顺序序存存储储类类型型时时,需需要要定定义义一一个个数数组组来来存存储储线线线线表表中中的的所所有有元元素素和和定定义义一一个个整整型变量来存储线性表的长度型变量来存储线性表的长度 假假定定数数组组用用dataMaxSize表表示示,长长度度整整型型变变量量用用length表表示示,并并采采用用结结构构体体类类型型表表示示,则则元元素素类类型型为为通通用用类类型型标标识识符符ElemType的的线线性性表表的的顺顺序序存存储储类类型型可可描述如下描述如下: :最新.课件16 typedef struct ElemType dataMaxSize; int length; SqList; /*/*顺序表类型顺序表类型* */ / 其中其中,data成员存放元素成员存放元素,length成员存放线性表的成员存放线性表的实际长度实际长度 说明：由于说明：由于C/C+C/C+中数组的下标从中数组的下标从0 0开始，线性表的第开始，线性表的第i i个元素个元素a ai i存放顺序表的第存放顺序表的第i-1i-1位置上。

为了清楚，将位置上为了清楚，将a ai i在逻辑在逻辑序列中的位置称为序列中的位置称为逻辑位序逻辑位序，在顺序表中的位置称为，在顺序表中的位置称为物理位物理位序序最新.课件172.2.2 2.2.2 顺序表基本运算的实现顺序表基本运算的实现 一旦采用顺序表存储结构一旦采用顺序表存储结构,我们就可以用我们就可以用C/C+语言实现线性表的各种基本运算为了方便语言实现线性表的各种基本运算为了方便,假设假设ElemType为为char类型类型,使用如下自定义类型语句使用如下自定义类型语句: typedef char ElemType;最新.课件181. 建立顺序表建立顺序表其方法是将给定的含有其方法是将给定的含有n个元素的数组的每个元素的数组的每个元素依次放入到顺序表中，并将个元素依次放入到顺序表中，并将n赋给顺序表赋给顺序表的长度成员算法如下：的长度成员算法如下： void CreateList(SqList *&L,ElemType a,int n) /*建立顺序表建立顺序表*/ int i; L=(SqList *)malloc(sizeof(SqList); for (i=0;idatai=ai; L-length=n;最新.课件192. 顺序表基本运算算法顺序表基本运算算法(1) 初始化线性表初始化线性表InitList(L) 该该运运算算的的结结果果是是构构造造一一个个空空的的线线性性表表L。

实实际际上上只只需需将将length成员设置为成员设置为0即可 void InitList(SqList *&L) /引用型指针引用型指针 L=(SqList *)malloc(sizeof(SqList); /*分配存放线性表的空间分配存放线性表的空间*/ L-length=0; 本算法的时间复杂度为本算法的时间复杂度为O(1)顺序表L最新.课件20 (2) 销毁线性表销毁线性表DestroyList(L) 该运算的结果是释放线性表该运算的结果是释放线性表L占用的内存空间占用的内存空间 void DestroyList(SqList *&L) free(L); 本算法的时间复杂度为本算法的时间复杂度为O(1) 最新.课件21 (3) 判定是否为空表判定是否为空表ListEmpty(L) 该该运运算算返返回回一一个个值值表表示示L是是否否为为空空表表若若L为为空空表表,则返回则返回1,否则返回否则返回0 int ListEmpty(SqList *L) return(L-length=0); 本算法的时间复杂度为本算法的时间复杂度为O(1)最新.课件22 (4) 求线性表的长度求线性表的长度ListLength(L) 该该运运算算返返回回顺顺序序表表L的的长长度度。

实实际际上上只只需需返返回回length成员的值即可成员的值即可 int ListLength(SqList *L) return(L-length); 本算法的时间复杂度为本算法的时间复杂度为O(1)最新.课件23 (5) 输出线性表输出线性表DispList(L) 该该运运算算当当线线性性表表L不不为为空空时时,顺顺序序显显示示L中中各各元元素素的的值 void DispList(SqList *L) int i;if (ListEmpty(L) return;for (i=0;ilength;i+)printf(%c,L-datai);printf(n); 最新.课件24 本本算算法法中中基基本本运运算算为为for循循环环中中的的printf语语句句,故故时间复杂度为时间复杂度为: O(L-length)或或O(n)最新.课件25 (6) 求某个数据元素值求某个数据元素值GetElem(L,i,e) 该该运运算算返返回回L中中第第 i(1iListLength(L)个个元元素素的的值值,存放在存放在e中 int GetElem(SqList *L,int i,ElemType &e) if (iL-length) return 0;e=L-datai-1;return 1; 本算法的时间复杂度为本算法的时间复杂度为O。