数据结构线性表PPT.ppt

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

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

个元素的值 (7) (7) 定定位位查查找找LocateElem(L,e):LocateElem(L,e):返返回回L L中中第第1 1个个值值域域与与e e相相等等的的位位序序假假设设这这样样的元素不存在的元素不存在, ,那么返回值为那么返回值为0 0 (8) (8) 插插入入数数据据元元素素ListInsert(&L,i,e):ListInsert(&L,i,e):在在L L的的第第i(1≤i≤ListLength(L)+1)i(1≤i≤ListLength(L)+1)个个元元素素之之前前插入新的元素插入新的元素e,Le,L的长度增的长度增1 1 (9) (9) 删删除除数数据据元元素素ListDelete(&L,i,&e):ListDelete(&L,i,&e):删删 除除 L L的的 第第i(1≤i≤ListLength(L))i(1≤i≤ListLength(L))个个元元素素, ,并并用用e e返回其值返回其值,L,L的长度减的长度减1 1 例例 假假设设有有两两个个集集合合 A A 和和 B B 分分别别用用两两个个线线性性表表 LA LA 和和 LB LB 表表示示, ,即即线线性性表表中中的的数数据据元元素素即即为为集集合合中中的的成成员员。

编编写写一一个个算算法法求求一一个个新新的的集集合合C=A∪B,C=A∪B,即即将两个集合的并集放性表将两个集合的并集放性表LCLC中 解解: :本本算算法法思思想想是是: :先先初初始始化化线线性性表表LC,LC,将将LALA的的所所有有元元素素复复制制到到LCLC中中, ,然然后后扫扫描描线线性性表表LB,LB,假假设设LBLB的的当当前前元元素素不不在线性性表表LALA中中, ,那那么么将将其其插插入入到到LCLC中中算算法如下法如下: :void 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); for (i=1;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))。

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

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

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

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

 (4) 求线性表的长度求线性表的长度ListLength(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->data[i]);printf("\n"); }  本本算算法法中中根根本本运运算算为为forfor循循环环中中的的printfprintf语句语句, ,故时间复杂度为故时间复杂度为: : O(L->length) O(L->length)或或O(n)O(n) (6) 求某个数据元素值求某个数据元素值GetElem(L,i,e) 该该运运算算返返回回L中中第第 i(1≤i≤ListLength(L))个个元元素素的的值值,存放在存放在e中。

中 int GetElem(SqList *L,int i,ElemType &e) {if (i<1 || i>L->length) return 0;e=L->data[i-1];return 1; } 本算法的时间复杂度为本算法的时间复杂度为O(1)  (7) 按元素值查找按元素值查找LocateElem(L,e) 该该运运算算顺顺序序查查找找第第1个个值值域域与与e相相等等的的元元素素的的位位序序假假设这样的元素不存在设这样的元素不存在,那么返回值为那么返回值为0 int LocateElem(SqList *L, ElemType e) {int i=0;while (ilength && L->data[i]!=e) i++;if (i>=L->length) return 0;else return i+1; } 本本算算法法中中根根本本运运算算为为while循循环环中中的的i++语语句句,故时间复杂度为故时间复杂度为: O(L->length)或或O(n) (8) 插入数据元素插入数据元素ListInsert(L,i,e) 该该 运运 算算 在在 顺顺 序序 表表 L的的 第第 i个个 位位 置置(1≤i≤ListLength(L)+1)上插入新的元素上插入新的元素e。

思思路路：：如如果果i值值不不正正确确,那那么么显显示示相相应应错错误误信信息息；；否否那那么么将将顺顺序序表表原原来来第第i个个元元素素及及以以后后元元素素均均后后移移一一个个位位置置,腾腾出出一一个个空空位位置置插插入入新新元元素素,顺顺序表长度增序表长度增1 int ListInsert(SqList *&L,int i,ElemType e) { int j; if (i<1 || i>L->length+1)return 0; i--; /*将顺序表将顺序表逻辑位序逻辑位序转化为转化为elem下标即下标即物理位序物理位序*/ for (j=L->length;j>i;j--) L->data[j]=L->data[j-1]; /*将将data[i]及后面元素后移一个位置及后面元素后移一个位置*/ L->data[i]=e; L->length++; /*顺序表长度增顺序表长度增1*/ return 1; }a0…ai-1ai…an-1……逻辑位序　逻辑位序　1 　　　　　　　　i i+1 n MaxSize  对于本算法来说对于本算法来说,元素移动的次数不元素移动的次数不仅与表长仅与表长L.length=n有关有关,而且与插入位而且与插入位置置i有关有关:当当i=n+1时时,移动次数为移动次数为0；当；当i=1时时,移动次数为移动次数为n,到达最大值。

性表到达最大值性表sq中共有中共有n+1个可以插入元素的地方假个可以插入元素的地方假设设pi(= )是在第是在第i个位置上插入一个元个位置上插入一个元素的概率素的概率,那么在长度为那么在长度为n的线性表中插的线性表中插入一个元素时所需移动元素的平均次数入一个元素时所需移动元素的平均次数为为: 因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n) (9) 删除数据元素删除数据元素ListDelete(L,i,e) 删删除除顺顺序序表表L中中的的第第i(1≤i≤ListLength(L))个个元元素 思思路路：：如如果果i值值不不正正确确,那那么么显显示示相相应应错错误误信信息息；；否否那那么么将将线线性性表表第第i个个元元素素以以后后元元素素均均向向前前移移动动一一个个位位置置,这这样样覆覆盖盖了了原原来来的的第第i个个元元素素,到到达达删删除除该该元素的目的元素的目的,最后顺序表长度减最后顺序表长度减1int ListDelete(SqList *&L,int i,ElemType &e){ int j; if (i<1 || i>L->length)return 0; i--; /*将顺序表逻辑位序转化为将顺序表逻辑位序转化为elem下标即物理位序下标即物理位序*/ e=L->data[i]; for (j=i;jlength-1;j++) L->data[j]=L->data[j+1]; /*将将data[i]之后的元素后前移一个位置之后的元素后前移一个位置*/ L->length--;/*顺序表长度减顺序表长度减1*/ return 1;}a0…ai-1ai…an-1……逻辑位序　逻辑位序　1 　　　　　　　　i i+1 n MaxSize  对于本算法来说对于本算法来说, ,元素移动的次数也元素移动的次数也与表长与表长n n和删除元素的位置和删除元素的位置i i有关有关: :当当i=ni=n时时, ,移动次数为移动次数为0 0；当；当i=1i=1时时, ,移动次数为移动次数为n-1n-1。

性表性表sqsq中共有中共有n n个元素可以被个元素可以被删除假设删除假设pi(pi= )pi(pi= )是删除第是删除第i i个位个位置上元素的概率置上元素的概率, ,那么在长度为那么在长度为n n的线性的线性表中删除一个元素时所需移动元素的平表中删除一个元素时所需移动元素的平均次数为均次数为: : = = 因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O(n)O(n) 例例 设设计计一一个个算算法法, ,将将x x插插入入到到一一个个有有序序( (从从小小到到大大排排序序) )的的线线性性表表( (顺顺序序存存储储结结构构即即顺顺序序表表) )的的适适当当位位置置上上, ,并保持线性表的有序性并保持线性表的有序性 解解: :先先通通过过比比较较在在顺顺序序表表L L中中找找到到存存放放x x的的位位置置i,i,然然后后将将x x插插入入到到L.data[i]L.data[i]中中, ,最最后后将将顺顺序序表表的的长长度度增增1 1 void Insert(SqList *&L,ElemType x) { int i=0,j; while (ilength && L->data[i]length-1;j>=i;j--) L->data[j+1]=L->data[j]; L->data[i]=x; L->length++; }查找插入位置查找插入位置元素后移一个位置元素后移一个位置a0…ai-1ai…an-1……逻辑位序　逻辑位序　1 　　　　　　　　i i+1 n MaxSize  　　例例 　　设设计计一一个个算算法法,将将两两个个元元素素有有序序(从从小小到到大大)的顺序表合并成一个有序顺序表。

的顺序表合并成一个有序顺序表 　　 求解思路求解思路:将两个顺序表进行二路归并将两个顺序表进行二路归并 　归并到顺序表　归并到顺序表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：：1　　　　3　　　　5i顺序表顺序表q：：2　　　　4　　　　10　　　　20j顺序表顺序表r：：1　　kSqList *merge(SqList *p, SqList *q){ SqList *r; int i=0,j=0,k=0; r=(SqList *)malloc(sizeof(SqList)); while (ilength && jlength) { if (p->data[i] data[j]) { r-> data[k]=p-> data[i]; i++;k++; } else { r-> data[k]=q-> data[j]; j++;k++; } }while (ilength) { r->data[k]=p->data[i]; i++;k++; } while (jlength) { r->data[k]=q->data[j]; j++;k++; } r->length=k; /*或或p->length+q->length*/ return(r);} 例例 长长度度为为n的的线线性性表表A采采用用顺顺序序存存储储结结构构,编编写写一一个个时时间间复复杂杂度度为为O(n)、、空空间间复复杂杂度度为为O(1)的的算算法法,该该算算法法删删除除线线性性表表中中所所有有值值为为item的数据元素。

的数据元素 解解:用用k记记录录顺顺序序表表A中中等等于于item的的元元素素个个数数,边边扫扫描描A边边统统计计k,并并将将不不为为item的的元元素素前前移移k个个位位置置,最最后后修修改改A的的长长度度对对应应的的算算法法如如下下:void delnode1(SqList &A,ElemType item){ int k=0,i; /*k记录值不等于记录值不等于item的元素个数的元素个数*/ for (i=0;i

算算法法中中只只用用了了i,k两两个个临临时时变变量量,空空间间复复杂杂度度为为O(1)2.3 2.3 线性表的链式存储线性表的链式存储 2.3.1 线性表的链式存储线性表的链式存储—链表链表2.3.2 单链表根本运算的实现单链表根本运算的实现 2.3.3 双链表双链表2.3.4 循环链表循环链表2.3.5 静态链表静态链表2.3.1 2.3.1 线性表的链式存储线性表的链式存储——链表链表 在链式存储中在链式存储中, ,每个存储结点不仅包含有所存元每个存储结点不仅包含有所存元素本身的信息素本身的信息( (称之为数据域称之为数据域),),而且包含有元素之间而且包含有元素之间逻辑关系的信息逻辑关系的信息, ,即前驱结点包含有后继结点的地址即前驱结点包含有后继结点的地址信息信息, ,这称为指针域这称为指针域, ,这样可以通过前驱结点的指针这样可以通过前驱结点的指针域方便地找到后继结点的位置域方便地找到后继结点的位置, ,提高数据查找速度提高数据查找速度 一般地一般地, ,每个结点有一个或多个这样的指针每个结点有一个或多个这样的指针域假设一个结点中的某个指针域不需要任何结点域。

假设一个结点中的某个指针域不需要任何结点, ,那么仅它的值为空那么仅它的值为空, ,用常量用常量NULLNULL表示 由由于于顺顺序序表表中中的的每每个个元元素素至至多多只只有有一一个个前前驱驱元元素素和和一一个个后后继继元元素素,即即数数据据元元素素之之间间是是一一对对一一的的逻逻辑辑关关系系,所所以以当当进进行行链链式式存存储储时时,一一种种最最简简单单也也最最常常用用的的方方法是法是: 在在每每个个结结点点中中除除包包含含有有数数据据域域外外,只只设设置置一一个个指指针针域域,用用以以指指向向其其后后继继结结点点,这这样样构构成成的的链链接接表表称称为为线线性性单向链接表单向链接表,简称简称单链表单链表；； 带头结点单链表示意图带头结点单链表示意图 性表的链式存储中性表的链式存储中,为了便于插入和删除算法为了便于插入和删除算法的实现的实现,每个链表带有一个头结点每个链表带有一个头结点,并通过头结点的指并通过头结点的指针惟一标识该链表针惟一标识该链表  在在单单链链表表中中, ,由由于于每每个个结结点点只只包包含含有有一一个个指指向向后后继继结结点点的的指指针针, ,所所以以当当访访问问过过一一个个结结点点后后, ,只只能能接接着着访问它的后继结点访问它的后继结点, ,而无法访问它的前驱结点。

而无法访问它的前驱结点  另另一一种种可可以以采采用用的的方方法法是是:在在每每个个结结点点中中除除包包含含有有数数值值域域外外,设设置置有有两两个个指指针针域域,分分别别用用以以指指向向其其前前驱驱结结点点和和后后继继结结点点,这这样样构构成成的的链链接接表表称称之之为为线线性性双向链接表双向链接表,简称简称双链表双链表带头结点的双链表示意图带头结点的双链表示意图 在在双双链链表表中中, ,由由于于每每个个结结点点既既包包含含有有一一个个指指向向后后继继结结点点的的指指针针, ,又又包包含含有有一一个个指指向向前前驱驱结结点点的的指指针针, ,所所以以当当访访问问过过一一个个结结点点后后, ,既既可可以以依依次次向向后后访访问问每每一一个个结结点点, ,也可以依次向前访问每一个结点也可以依次向前访问每一个结点双链表的特点双链表的特点 在单链表中在单链表中,假定每个结点类型用假定每个结点类型用LinkList表示表示,它它应包括存储元素的数据域应包括存储元素的数据域,这里用这里用data表示表示,其类型用其类型用通用类型标识符通用类型标识符ElemType表示表示,还包括存储后继元素还包括存储后继元素位置的指针域位置的指针域,这里用这里用next表示。

表示 LinkList类型的定义如下类型的定义如下: typedef struct LNode /*定义单链表结点类型定义单链表结点类型*/ { ElemType data; struct LNode *next; /*指向后继结点指向后继结点*/ } LinkList;2.3.2 2.3.2 单链表根本运算的实现单链表根本运算的实现 1. 建立单链表建立单链表 先先考考虑虑如如何何建建立立单单链链表表假假设设我我们们通通过过一一个个含含有有n个个数数据据的的数数组组来来建建立立单单链链表表建建立立单单链链表表的的常常用用方法有如下两种方法有如下两种: (1) 头插法建表头插法建表 该方法从一个空表开始该方法从一个空表开始,读取字符数组读取字符数组a中的字中的字符符,生成新结点生成新结点,将读取的数据存放到新结点的数据将读取的数据存放到新结点的数据域中域中,然后将新结点插入到当前链表的表头上然后将新结点插入到当前链表的表头上,直到直到结束为止采用头插法建表的算法如下结束为止采用头插法建表的算法如下: void CreateListF(LinkList *&L,ElemType a[],int n) { LinkList *s;int i; L=(LinkList *)malloc(sizeof(LinkList)); /*创立头结点创立头结点*/ L->next=NULL; for (i=0;idata=a[i]; s->next=L->next; /*将将*s插在原开始结点之前插在原开始结点之前,头结点之后头结点之后*/ L->next=s; } }adc bi=0 i=1 i=2 i=3∧ ∧head采用头插法建立单链表的过程采用头插法建立单链表的过程heada∧ ∧headda∧ ∧headcda∧ ∧headbcda∧ ∧第第1 1步步: :建头结点建头结点第第2 2步步:i:i＝＝0,0,新建新建a a结点结点, ,插入到头结点之后插入到头结点之后第第3 3步步:i:i＝＝1,1,新建新建d d结点结点, ,插入到头结点之后插入到头结点之后第第4 4步步:i:i＝＝2,2,新建新建c c结点结点, ,插入到头结点之后插入到头结点之后第第5 5步步:i:i＝＝3,3,新建新建b b结点结点, ,插入到头结点之后插入到头结点之后 (2) 尾插法建表尾插法建表 头头插插法法建建立立链链表表虽虽然然算算法法简简单单,但但生生成成的的链链表表中中结结点点的的次次序序和和原原数数组组元元素素的的顺顺序序相相反反。

假假设设希希望望两两者者次次序序一一致致,可可采采用用尾尾插插法法建建立立该该方方法法是是将将新新结结点点插插到到当当前前链链表表的的表表尾尾上上,为为此此必必须须增增加加一一个个尾尾指指针针r,使使其其始始终终指指向向当当前前链链表表的的尾尾结结点点采采用用尾尾插法建表的算法如下插法建表的算法如下: void CreateListR(LinkList *&L,ElemType a[],int n) { LinkList *s,*r;int i; L=(LinkList *)malloc(sizeof(LinkList)); /*创立头结点创立头结点*/ r=L; /*r始终指向终端结点始终指向终端结点,开始时指向头结点开始时指向头结点*/ for (i=0;idata=a[i];r->next=s; /*将将*s插入插入*r之后之后*/ r=s; } r->next=NULL;/*终端结点终端结点next域置为域置为NULL*/ }bcdai=0 i=1 i=2 i=3head头结点头结点adcb∧ ∧b采用尾插法建立单链表的过程采用尾插法建立单链表的过程2. 插入结点运算插入结点运算 插插入入运运算算是是将将值值为为x的的新新结结点点插插入入到到单单链链表表的的第第i个个结结点点的的位位置置上上。

先先在在单单链链表表中中找找到到第第i-1个结点个结点,再在其后插入新结点再在其后插入新结点 单链表插入结点的过程如以下图所示单链表插入结点的过程如以下图所示插入结点示意图插入结点示意图 3. 删除结点运算删除结点运算 删删除除运运算算是是将将单单链链表表的的第第i个个结结点点删删去去先先在在单单链链表表中中找找到到第第i-1个个结结点点,再再删删除除其其后后的的结结点点删删除除单链表结点的过程如以下图所示单链表结点的过程如以下图所示删除结点示意图删除结点示意图 4. 线性表根本运算实现线性表根本运算实现 (1) 初始化线性表初始化线性表InitList(L) 该运算建立一个空的单链表该运算建立一个空的单链表,即创立一个头结点即创立一个头结点 void InitList(LinkList *&L) {L=(LinkList *)malloc(sizeof(LinkList)); /*创创立立头结点头结点*/L->next=NULL; } (2) 销毁线性表销毁线性表DestroyList(L) 释释放放单单链链表表L占占用用的的内内存存空空间间。

即即逐逐一一释释放放全全部部结结点点的空间 void DestroyList(LinkList *&L) {LinkList *p=L,*q=p->next;while (q!=NULL){ free(p); p=q;q=p->next;}free(p); } (3) 判线性表是否为空表判线性表是否为空表ListEmpty(L) 假假设设单单链链表表L没没有有数数据据结结点点,那那么么返返回回真真,否否那那么么返返回假 int ListEmpty(LinkList *L) {return(L->next==NULL); } (4) 求线性表的长度求线性表的长度ListLength(L) 返回单链表返回单链表L中数据结点的个数中数据结点的个数 int ListLength(LinkList *L) {LinkList *p=L;int i=0;while (p->next!=NULL){ i++; p=p->next;}return(i); }  (5) 输出线性表输出线性表DispList(L) 逐逐一一扫扫描描单单链链表表L的的每每个个数数据据结结点点,并并显显示示各各结结点点的的data域值。

域值 void DispList(LinkList *L) {LinkList *p=L->next;while (p!=NULL){ printf("%c",p->data); p=p->next;}printf("\n"); } (6)求求 线线 性性 表表 L中中 指指 定定 位位 置置 的的 某某 个个 数数 据据 元元 素素GetElem(L,i,&e) 思思路路：：在在单单链链表表L中中从从头头开开始始找找到到第第 i个个结结点点,假假设存在第设存在第i个数据结点个数据结点,那么将其那么将其data域值赋给变量域值赋给变量e int GetElem(LinkList *L,int i,ElemType &e) {int j=0;LinkList *p=L;while (jnext;}if (p==NULL) return 0; /*不存在第不存在第i个数据结点个数据结点*/else /*存在第存在第i个数据结点个数据结点*/{ e=p->data; return 1;} } (7) 按元素值查找按元素值查找LocateElem(L,e) 思思路路：：在在单单链链表表L中中从从头头开开始始找找第第1个个值值域域与与e相相等等的的结点结点,假设存在这样的结点假设存在这样的结点,那么返回位置那么返回位置,否那么返回否那么返回0。

int LocateElem(LinkList *L,ElemType e) {LinkList *p=L->next;int n=1;while (p!=NULL && p->data!=e){ p=p->next; n++; }if (p==NULL) return(0);else return(n); } (8) 插入数据元素插入数据元素ListInsert(&L,i,e) 思思路路：：先先在在单单链链表表L中中找找到到第第i-1个个结结点点*p,假假设设存存在在这样的结点这样的结点,将值为将值为e的结点的结点*s插入到其后插入到其后 int ListInsert(LinkList *&L,int i,ElemType e) { int j=0; LinkList *p=L,*s; while (jnext; }if (p==NULL) return 0; /*未找到位序为i-1的结点*/else /*找到位序为i-1的结点*p*/{ s=(LinkList *)malloc(sizeof(LinkList));/*创立新结点*s*/ s->data=e; s->next=p->next; /*将*s插入到*p之后*/ p->next=s; return 1;}} (9) 删除数据元素删除数据元素ListDelete(&L,i,&e) 思思路路：：先先在在单单链链表表L中中找找到到第第i-1个个结结点点*p,假假设设存存在在这样的结点这样的结点,且也存在后继结点且也存在后继结点,那么删除该后继结点。

那么删除该后继结点 int ListDelete(LinkList *&L,int i,ElemType &e) { int j=0;LinkList *p=L,*q;while (jnext;}if (p==NULL) return 0; /*未找到位序为未找到位序为i-1的结点的结点*/else/*找到位序为找到位序为i-1的结点的结点*p*/{ q=p->next; /*q指向要删除的结点指向要删除的结点*/ if (q==NULL) return 0; /*假设不存在第假设不存在第i个结点个结点,返回返回0*/ p->next=q->next; /*从单链表中删除从单链表中删除*q结点结点*/ free(q); /*释放释放*q结点结点*/ return 1;} } 例例 设设C={a1,b1,a2,b2,…,an,bn}为为一一线线性性表表,采采用用带带头头结结点点的的hc单单链链表表存存放放,编编写写一一个个算算法法,将将其其拆分为两个线性表拆分为两个线性表,使得使得: A={a1,a2,…,an},B={b1,b2,…,bn}  解解: 设设拆拆分分后后的的两两个个线线性性表表都都用用带带头头结结点点的的单链表存放。

单链表存放 先先建建立立两两个个头头结结点点*ha和和*hb,它它们们用用于于存存放放拆拆分分后后的的线线性性表表A和和B,ra和和rb分分别别指指向向这这两两个个单单链链表表的的表表尾尾,用用p指指针针扫扫描描单单链链表表hc,将将当当前前结结点点*p链链到到ha未未尾尾,p沿沿next域域下下移移一一个个结结点点,假假设设不不为为空空,那那么么当当前前结结点点*p链链到到hb未未尾尾,p沿沿next域域下下移移一一个个结结点点,如如此此这这样样,直直到到p为为空空最最后后将将两两个个尾结点的尾结点的next域置空 对应算法如下对应算法如下: void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) { LinkList *p=hc->next,*ra,*rb; ha=hc; /*ha的头结点利用的头结点利用hc的头结点的头结点*/ ra=ha; /*ra始终指向始终指向ha的末尾结点的末尾结点*/ hb=(LinkList *)malloc(sizeof(LinkList)); /*创立创立hb头结点头结点*/ rb=hb; /*rb始终指向始终指向hb的末尾结点的末尾结点*/ while (p!=NULL) { ra->next=p;ra=p; /*将将*p链到链到ha单链表未尾单链表未尾*/ p=p->next; if (p!=NULL) { rb->next=p; rb=p; /*将将*p链到链到hb单链表未尾单链表未尾*/ p=p->next; } } ra->next=rb->next=NULL; /*两个尾结点的两个尾结点的next域置空域置空*/} 本本算算法法实实际际上上是是采采用用尾尾插插法法建建立立两两个个新新表表。

所所以以, ,尾尾插插法法建建表表算算法法是是很很多多类类似似习习题题的根底！的根底！ 例例 有有一一个个带带头头结结点点的的单单链链表表head,head,其其ElemTypeElemType类类型型为为char,char,设设计计一一个个算算法法使使其其元元素递增有序素递增有序 解解: :假假设设原原单单链链表表中中有有一一个个或或以以上上的的数数据据结结点点, ,先先构构造造只只含含一一个个数数据据结结点点的的有有序序表表( (只只含含一一个个数数据据结结点点的的单单链链表表一一定定是是有有序序表表) ) 扫扫 描描 原原 单单 链链 表表 余余 下下 的的 结结 点点 *p(*p(直直 到到p==NULLp==NULL为为止止),),在在有有序序表表中中通通过过比比较较找找插插入入*p*p的的前前驱驱结结点点*q,*q,然然后后将将*p*p插插入入到到*q*q之之后后( (这里实际上采用的是直接插入排序方法这里实际上采用的是直接插入排序方法) )  void Sort(LinkList *&head) {LinkList *p=head->next,*q,*r;if (p!=NULL) /*head有一个或以上的数据结点有一个或以上的数据结点*/{ r=p->next; /*r保存保存*p结点后继结点的指针结点后继结点的指针*/ p->next=NULL; /*构造只含一个数据结点的有序表构造只含一个数据结点的有序表*/ p=r; while (p!=NULL) { r=p->next; /*r保存保存*p结点后继结点的指针结点后继结点的指针*/ q=head; while (q->next!=NULL && q->next->datadata) q=q->next; /*在有序表中找插入在有序表中找插入*p的前驱结点的前驱结点*q*/ p->next=q->next; /*将将*p插入到插入到*q之后之后*/ q->next=p; p=r; /*扫描原单链表余下的结点扫描原单链表余下的结点*/ } } } 2.3.3 2.3.3 双链表双链表 对对于于双双链链表表,采采用用类类似似于于单单链链表表的的类类型型定定义义,其其DLinkList类型的定义如下类型的定义如下: typedef struct DNode /*定义双链表结点类型定义双链表结点类型*/ {ElemType data; struct DNode *prior; /*指向前驱结点指向前驱结点*/struct DNode *next; /*指向后继结点指向后继结点*/ } DLinkList; 在双链表中在双链表中, ,有些操作如求长度、取元素值和查有些操作如求长度、取元素值和查找元素等操作算法与单链表中相应算法是相同的找元素等操作算法与单链表中相应算法是相同的, ,这这里不多讨论。

但在单链表中里不多讨论但在单链表中, ,进行结点插入和删除时进行结点插入和删除时涉及到前后结点的一个指针域的变化而在双链表涉及到前后结点的一个指针域的变化而在双链表中中, ,结点的插入和删除操作涉及到前后结点的两个指结点的插入和删除操作涉及到前后结点的两个指针域的变化针域的变化双链表中插入结点示意图双链表中插入结点示意图 归纳起来归纳起来,在双链表中在双链表中p所指的结点之后插入所指的结点之后插入一个一个*s结点其操作语句描述为结点其操作语句描述为: s->next=p->next;/*将将*s插入到插入到*p之后之后*/ p->next->prior=s; s->prior=p; p->next=s;删除结点示意图删除结点示意图 在在 双双 链链 表表中中删删除除一一个个结结点点的的过过程程如如右右图图所所示示: 归纳起来归纳起来, ,删除双链表删除双链表L L中中* *p p结点的后续结点结点的后续结点其操作语句描述为其操作语句描述为: : p->next=q->next; q->next->prior=p;2.3.4 2.3.4 循环链表循环链表 循环链表循环链表是另一种形式的链式存储结构。

它的是另一种形式的链式存储结构它的特点是表中最后一个结点的指针域不再是空特点是表中最后一个结点的指针域不再是空, ,而是而是指向表头结点指向表头结点, ,整个链表形成一个环由此整个链表形成一个环由此, ,从表中从表中任一结点出发均可找到链表中其他结点任一结点出发均可找到链表中其他结点  带头结点的循环单链表和循环双链表的示意图带头结点的循环单链表和循环双链表的示意图 例例 　　编编写写出出判判断断带带头头结结点点的的双双向向循循环环链链表表L是否对称相等的算法是否对称相等的算法 解解:p从从左左向向右右扫扫描描L,q从从右右向向左左扫扫描描L,假假设设对对应应数数据据结结点点的的data域域不不相相等等,那那么么退退出出循循环环,否否那那么么继继续续比比较较,直直到到p与与q相相等等或或p的的下下一一个结点为个结点为*q为止对应算法如下为止对应算法如下:int Equeal(DLinkList *L){ int same=1; DLinkList *p=L->next; /*p指向第一个数据结点指向第一个数据结点*/ DLinkList *q=L->prior; /*q指向最后数据结点指向最后数据结点*/ while (same==1) if (p->data!=q->data) same=0; else { if (p==q) break; /*数据结点为奇数的情况数据结点为奇数的情况*/ q=q->prior; if (p==q) break; /*数据结点为偶数的情况数据结点为偶数的情况*/ p=p->next; } return same;}2.3.5 2.3.5 静态链表静态链表 静态链表借用一维数组来描述线性链表。

数组静态链表借用一维数组来描述线性链表数组中的一个分量表示一个结点中的一个分量表示一个结点, ,同时使用游标同时使用游标( (指示器指示器curcur即为伪指针即为伪指针) )代替指针以指示结点在数组中的相对位置代替指针以指示结点在数组中的相对位置数组中的第数组中的第0 0个分量可以看成头结点个分量可以看成头结点, ,其指针域指示静其指针域指示静态链表的第一个结点态链表的第一个结点 这种存储结构仍然需要预先分配一个较大空这种存储结构仍然需要预先分配一个较大空间间, ,但是在进行线性表的插入和删除操作时不需要移动但是在进行线性表的插入和删除操作时不需要移动元素元素, ,仅需要修改仅需要修改““指针〞指针〞, ,因此仍然具有链式存储结因此仍然具有链式存储结构的主要优点构的主要优点 以下图给出了一个静态链表的例如图以下图给出了一个静态链表的例如图(a)是一个修改之前的静态链表是一个修改之前的静态链表,图图(b)是删除数据是删除数据元素元素“陈华〞之后的静态链表陈华〞之后的静态链表,图图(c)插入数据元插入数据元素素“王华〞之后的静态链表王华〞之后的静态链表,图中用阴影表示修图中用阴影表示修改的游标。

改的游标 2.4 2.4 线性表的应用线性表的应用 计算任意两个表的简单自然连接过程讨论线性计算任意两个表的简单自然连接过程讨论线性表的应用假设有两个表表的应用假设有两个表A和和B,分别是分别是m1行、行、n1列列和和m2行、行、n2列列,它们简单自然连接结果它们简单自然连接结果C=A B,其其中中i表示表表示表A中列号中列号,j表示表表示表B中的列号中的列号,C为为A和和B的的笛卡儿积中满足指定连接条件的所有记录组笛卡儿积中满足指定连接条件的所有记录组,该连接该连接条件为表条件为表A的第的第i列与表列与表B的第的第j列相等例如列相等例如:i=j C=A B的计算结果如下的计算结果如下: 3=1 由由于于每每个个表表的的行行数数不不确确定定,为为此此,用用单单链链表表作作为为表表的的存存储储结结构构,每每行行作作为为一一个个数数据据结结点点另另外外,每每行行中中的的数数据据个个数数也也是是不不确确定定的的,但但由由于于提提供供随随机机查查找找行行中中的的数数据据,所所以以每每行行的的数数据据采采用用顺顺序序存存储储结结构构,这这里里用用长长度度为为MaxCol的的数数组组存存储储每每行行的的数数据据。

因因此此,该该单单链链表表中数据结点类型定义如下中数据结点类型定义如下: #define MaxCol 10/*最大列数最大列数*/ typedef struct Node1/*定义数据结点类型定义数据结点类型*/ { ElemType data[MaxCol]; struct Node1 *next; /*指向后继数据结点指向后继数据结点*/ } DList; 另另外外,需需要要指指定定每每个个表表的的行行数数和和列列数数,为为此此将将单单链链表表的头结点类型定义如下的头结点类型定义如下: typedef struct Node2 /*定义头结点类型定义头结点类型*/ { int Row,Col;/*行数和列数行数和列数*/ DList *next;/*指向第一个数据结点指向第一个数据结点*/ } HList; 采采用用尾尾插插法法建建表表方方法法创创立立单单链链表表,用用户户先先输输入入表表的的行行数数和和列列数数,然然后后输输入入各各行行的的数数据据,为为了了简简便便,假假设设表表中中数据为数据为int型型,因此定义因此定义: typedef int ElemType; 对应的建表算法如下对应的建表算法如下:void create(HList *&h){ int i,j; DList *r,*s; h=(HList *)malloc(sizeof(HList));h->next=NULL; printf("表的行数表的行数,列数列数:"); scanf("%d%d",&h->Row,&h->Col); for (i=0;iRow;i++) { printf(" 第第%d行行:",i+1); s=(DList *)malloc(sizeof(DList)); for (j=0;jCol;j++) scanf("%d",&s->data[j]); if (h->next==NULL) h->next=s; else r->next=s; r=s; /*r始终指向最后一个数据结点始终指向最后一个数据结点*/ } r->next=NULL;} 采用尾插法建表采用尾插法建表对应的输出表的算法如下对应的输出表的算法如下:void display(HList *h){ int j; DList *p=h->next; while (p!=NULL) { for (j=0;jCol;j++) printf("%4d",p->data[j]); printf("\n"); p=p->next; }}  为了实现两个表为了实现两个表h1和和h2的简单自然连接的简单自然连接,先要输入两个表连接的列序号先要输入两个表连接的列序号f1和和f2,然后然后扫描单链表扫描单链表h1,对于对于h1的每个结点的每个结点,从头至尾从头至尾扫描单链表扫描单链表h2,假设自然连接条件成立假设自然连接条件成立,即即h1的当前结点的当前结点*p和和h2的当前结点的当前结点*q满足满足: p->data[f1-1]==q->data[f2-1]那么在新建单链表那么在新建单链表h中添加一个新结点。

中添加一个新结点 新建的单链表新建的单链表h也是采用尾插法建表方也是采用尾插法建表方法创立的法创立的 实现两个表实现两个表h1和和h2的简单自然连接并生的简单自然连接并生成结果成结果h的算法如下的算法如下:void link(HList *h1,HList *h2,HList *&h){ int f1,f2,i;DList *p=h1->next,*q,*s,*r; printf("连接字段是连接字段是:第第1个表位序个表位序,第第2个表位序个表位序:"); scanf("%d%d",&f1,&f2); h=(HList *)malloc(sizeof(HList)); h->Row=0; h->Col=h1->Col+h2->Col; h->next=NULL; while (p!=NULL) { q=h2->next; while (q!=NULL) { if (p->data[f1-1]==q->data[f2-1]) /*对应字段值相等对应字段值相等*/ { s=(DList *)malloc(sizeof(DList)); /*创立一个数据结点创立一个数据结点*/for (i=0;iCol;i++) /*复制表复制表1的当前行的当前行*/ s->data[i]=p->data[i];for (i=0;iCol;i++) s->data[h1->Col+i]=q->data[i];/*复复制制表表2的的当当前前行行*/ if (h->next==NULL) h->next=s;else r->next=s;r=s; /*r始终指向最后数据结点始终指向最后数据结点*/h->Row++; /*表行数增表行数增1*/ } q=q->next; /*表表2下移一个记录下移一个记录*/ } p=p->next; /*表表1下移一个记录下移一个记录*/ } r->next=NULL;/*表尾结点表尾结点next域置空域置空*/ } 尾插法建表尾插法建表2.5 2.5 有序表有序表 所谓所谓有序表有序表,是指这样的线性表是指这样的线性表,其中所有元素其中所有元素以递增或递减方式排列以递增或递减方式排列,并规定有序表中不存在元并规定有序表中不存在元素值相同的元素。

在这里仍以顺序表进行存储素值相同的元素在这里仍以顺序表进行存储 其中只有其中只有ListInsert()根本运算与前面的根本运算与前面的顺序表对应的运算有所差异顺序表对应的运算有所差异,其余都是相同其余都是相同的有序表的的有序表的ListInsert()运算对应的算法运算对应的算法如下如下:  int ListInsert(SqList &L,ElemType e) {int i=0,j;while (ii;j--) /*将将data[i]及后面元素后移一个位置及后面元素后移一个位置*/L.data[j]=L.data[j-1];L.data[i]=e;L.length++;/*顺序表长度增顺序表长度增1*/ return 1; } 注意：这里用的不是注意：这里用的不是顺序表指针，直接就顺序表指针，直接就是顺序表是顺序表本章小结本章小结本章的根本学习要点如下本章的根本学习要点如下: : (1) (1) 理解线性表的逻辑结构特性。

理解线性表的逻辑结构特性 (2) (2) 深入掌握线性表的两种存储方法深入掌握线性表的两种存储方法, ,即即顺序表和链表体会这两种存储结构之间的差顺序表和链表体会这两种存储结构之间的差异 (3) (3) 重点掌握顺序表和链表上各种根本重点掌握顺序表和链表上各种根本运算的实现运算的实现 (4) (4) 综合运用线性表这种数据结构解决综合运用线性表这种数据结构解决一些复杂的实际问题一些复杂的实际问题。