《数据结构线性表PPT.》由会员分享，可在线阅读，更多相关《数据结构线性表PPT.（107页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,2.1 线性表的基本概念,2.2 线性表的顺序存储,2.3 线性表的链式存储,2.4 线性表的应用,本章小结,2.5 有序表,2.1 线性表的基本概念,2.1.1 线性表的定义,2.1.2 线性表的运算,2.1.1 线性表的定义 线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n0。 当n=0时,表示线性表是一个空表,即表中不包含任何元素。设序列中第i(i表示位序)个元素为ai(1in)。 线性表的一般表示为: (a1,a2,ai,ai+1,an),其中a1为第一个元素,又称做表头元素,a2为第二个元素,an为最后一个元素,又称做
2、表尾元素。 例如,在线性表 (1,4,3,2,8,10) 中,1为表头元素,10为表尾元素。,2.1.2 线性表的运算 线性表的基本运算如下: (1) 初始化线性表InitList(i=lenb;i+) GetElem(LB,i,e); /*取LB中第i个数据元素赋给e*/ if (!LocateElem(LA,e) ListInsert(LC,+lenc,e); /*LA中不存在和e相同者,则插入到LC中*/ ,由于LocateElem(LA,e)运算的时间复杂度为O(ListLength(LA),所以本算法的时间复杂度为: O(ListLength(LA)*ListLength(LB)。,
3、2.2 线性表的顺序存储,2.2.1 线性表的顺序存储顺序表,2.2.2 顺序表基本运算的实现,2.2.1 线性表的顺序存储顺序表 线性表的顺序存储结构就是:把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。 这样,线性表中第一个元素的存储位置就是指定的存储位置,第i+1个元素(1in-1)的存储位置紧接在第i个元素的存储位置的后面。 线性表 逻辑结构 顺序表 存储结构,假定线性表的元素类型为ElemType,则每个元素所占用存储空间大小(即字节数)为sizeof(ElemType),整个线性表所占用存储空间的大小为: n*sizeof(Ele
4、mType) 其中,n表示线性表的长度。,顺序表示意图,在定义一个线性表的顺序存储类型时,需要定义一个数组来存储线线表中的所有元素和定义一个整型变量来存储线性表的长度。 假定数组用dataMaxSize表示,长度整型变量用length表示,并采用结构体类型表示,则元素类型为通用类型标识符ElemType的线性表的顺序存储类型可描述如下:,typedef struct ElemType dataMaxSize; int length; SqList; /*顺序表类型*/ 其中,data成员存放元素,length成员存放线性表的实际长度。 说明：由于C/C+中数组的下标从0开始，线性表的第i个元素
5、ai存放顺序表的第i-1位置上。为了清楚，将ai在逻辑序列中的位置称为逻辑位序，在顺序表中的位置称为物理位序。,2.2.2 顺序表基本运算的实现,一旦采用顺序表存储结构,我们就可以用C/C+语言实现线性表的各种基本运算。为了方便,假设ElemType为char类型,使用如下自定义类型语句: typedef char ElemType;,1. 建立顺序表 其方法是将给定的含有n个元素的数组的每个元素依次放入到顺序表中，并将n赋给顺序表的长度成员。算法如下： void CreateList(SqList * ,2. 顺序表基本运算算法 (1) 初始化线性表InitList(L) 该运算的结果是构造
6、一个空的线性表L。实际上只需将length成员设置为0即可。 void InitList(SqList * 本算法的时间复杂度为O(1)。,顺序表,L,(2) 销毁线性表DestroyList(L) 该运算的结果是释放线性表L占用的内存空间。 void DestroyList(SqList * 本算法的时间复杂度为O(1)。,(3) 判定是否为空表ListEmpty(L) 该运算返回一个值表示L是否为空表。若L为空表,则返回1,否则返回0。 int ListEmpty(SqList *L) return(L-length=0); 本算法的时间复杂度为O(1)。,(4) 求线性表的长度ListL
7、ength(L) 该运算返回顺序表L的长度。实际上只需返回length成员的值即可。 int ListLength(SqList *L) return(L-length); 本算法的时间复杂度为O(1)。,(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); ,本算法中基本运算为for循环中的printf语句,故时间复杂度为: O(L-le
8、ngth)或O(n),(6) 求某个数据元素值GetElem(L,i,e) 该运算返回L中第 i(1iListLength(L)个元素的值,存放在e中。 int GetElem(SqList *L,int i,ElemType 本算法的时间复杂度为O(1)。,(7) 按元素值查找LocateElem(L,e) 该运算顺序查找第1个值域与e相等的元素的位序。若这样的元素不存在,则返回值为0。 int LocateElem(SqList *L, ElemType e) int i=0; while (ilength ,本算法中基本运算为while循环中的i+语句,故时间复杂度为: O(L-leng
9、th)或O(n),(8) 插入数据元素ListInsert(L,i,e) 该运算在顺序表L的第i个位置(1iListLength(L)+1)上插入新的元素e。 思路：如果i值不正确,则显示相应错误信息；否则将顺序表原来第i个元素及以后元素均后移一个位置,腾出一个空位置插入新元素,顺序表长度增1。,int ListInsert(SqList * ,逻辑位序1 i i+1 n MaxSize,对于本算法来说,元素移动的次数不仅与表长L.length=n有关,而且与插入位置i有关:当i=n+1时,移动次数为0；当i=1时,移动次数为n,达到最大值。在线性表sq中共有n+1个可以插入元素的地方。假设p
10、i(= )是在第i个位置上插入一个元素的概率,则在长度为n的线性表中插入一个元素时所需移动元素的平均次数为: 因此插入算法的平均时间复杂度为O(n)。,(9) 删除数据元素ListDelete(L,i,e) 删除顺序表L中的第i(1iListLength(L)个元素。 思路：如果i值不正确,则显示相应错误信息；否则将线性表第i个元素以后元素均向前移动一个位置,这样覆盖了原来的第i个元素,达到删除该元素的目的,最后顺序表长度减1。,int ListDelete(SqList * ,逻辑位序1 i i+1 n MaxSize,对于本算法来说,元素移动的次数也与表长n和删除元素的位置i有关:当i=n
11、时,移动次数为0；当i=1时,移动次数为n-1。在线性表sq中共有n个元素可以被删除。假设pi(pi= )是删除第i个位置上元素的概率,则在长度为n的线性表中删除一个元素时所需移动元素的平均次数为: = 因此删除算法的平均时间复杂度为O(n)。,例2.2 设计一个算法,将x插入到一个有序(从小到大排序)的线性表(顺序存储结构即顺序表)的适当位置上,并保持线性表的有序性。 解:先通过比较在顺序表L中找到存放x的位置i,然后将x插入到L.datai中,最后将顺序表的长度增1。,void Insert(SqList * ,查找插入位置,元素后移一个位置,逻辑位序1 i i+1 n MaxSize,例
12、2.3 设计一个算法,将两个元素有序(从小到大)的顺序表合并成一个有序顺序表。 求解思路:将两个顺序表进行二路归并。,归并到顺序表r中 k记录r中元素个数 1(i=0) 2(j=0) 将1(i=1)插入r(k=1) 3(i=1) 2(j=0) 将2(j=1)插入r(k=2) 3(i=1) 4(j=1) 将3(i=2)插入r(k=3) 5(i=2) 4(j=1) 将4(j=2)插入r(k=4) 5(i=2) 10(j=2) 将5(j=3)插入r(k=5) 将q中余下元素插入r中。,顺序表p：135,i,顺序表q：241020,j,顺序表r：1,k,SqList *merge(SqList *p,
13、 SqList *q) SqList *r; int i=0,j=0,k=0; r=(SqList *)malloc(sizeof(SqList); while (ilength ,while (ilength) r-datak=p-datai; i+;k+; while (jlength) r-datak=q-dataj; j+;k+; r-length=k; /*或p-length+q-length*/ return(r); ,例2.4 已知长度为n的线性表A采用顺序存储结构,编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法,该算法删除线性表中所有值为item的数据元素。 解:用k
14、记录顺序表A中等于item的元素个数,边扫描A边统计k,并将不为item的元素前移k个位置,最后修改A的长度。对应的算法如下:,void delnode1(SqList /*顺序表A的长度等于k*/ ,算法1：类似于建顺序表,void delnode2(SqList /*顺序表A的长度递减*/ ,算法2,上述算法中只有一个while循环,时间复杂度为O(n)。算法中只用了i,k两个临时变量,空间复杂度为O(1)。,2.3 线性表的链式存储,2.3.1 线性表的链式存储链表,2.3.2 单链表基本运算的实现,2.3.3 双链表,2.3.4 循环链表,2.3.5 静态链表,2.3.1 线性表的链式
15、存储链表 在链式存储中,每个存储结点不仅包含有所存元素本身的信息(称之为数据域),而且包含有元素之间逻辑关系的信息,即前驱结点包含有后继结点的地址信息,这称为指针域,这样可以通过前驱结点的指针域方便地找到后继结点的位置,提高数据查找速度。 一般地,每个结点有一个或多个这样的指针域。若一个结点中的某个指针域不需要任何结点,则仅它的值为空,用常量NULL表示。,由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素,即数据元素之间是一对一的逻辑关系,所以当进行链式存储时,一种最简单也最常用的方法是: 在每个结点中除包含有数据域外,只设置一个指针域,用以指向其后继结点,这样构成的链接表称为线性单向
16、链接表,简称单链表；,带头结点单链表示意图,在线性表的链式存储中,为了便于插入和删除算法的实现,每个链表带有一个头结点,并通过头结点的指针惟一标识该链表。,在单链表中,由于每个结点只包含有一个指向后继结点的指针,所以当访问过一个结点后,只能接着访问它的后继结点,而无法访问它的前驱结点。,另一种可以采用的方法是:在每个结点中除包含有数值域外,设置有两个指针域,分别用以指向其前驱结点和后继结点,这样构成的链接表称之为线性双向链接表,简称双链表。,带头结点的双链表示意图,在双链表中,由于每个结点既包含有一个指向后继结点的指针,又包含有一个指向前驱结点的指针,所以当访问过一个结点后,既可以依次向后访问每一个结点,也可以依次向前访问每一个结点。,双链表的特点,
