《数据结构线性表PPT》由会员分享，可在线阅读，更多相关《数据结构线性表PPT（108页珍藏版）》请在金锄头文库上搜索。
1、第第2 2章章 线性表线性表 2.1 2.1 线性表的基本概念线性表的基本概念 2.2 2.2 线性表的顺序存储线性表的顺序存储2.3 2.3 线性表的链式存储线性表的链式存储2.4 2.4 线性表的应用线性表的应用 本章小结本章小结 2.5 2.5 有序表有序表 数据结构线性表PPT2.1 2.1 线性表的基本概念线性表的基本概念 2.1.1 线性表的定义线性表的定义2.1.2 线性表的运算线性表的运算数据结构线性表PPT2.1.1 2.1.1 线性表的定义线性表的定义 线性表是具有相同特性的数据元素的一个有线性表是具有相同特性的数据元素的一个有限序列。限序列。该序列中所含元素的个数叫做线性
2、表的该序列中所含元素的个数叫做线性表的长度长度,用用n表示表示,n0。 当当n=0时时,表示线性表是一个空表表示线性表是一个空表,即表中不包即表中不包含任何元素。设序列中第含任何元素。设序列中第i(i表示位序表示位序)个元素为个元素为ai(1in)。 线性表的一般表示为线性表的一般表示为: (a1,a2,ai,ai+1,an)数据结构线性表PPT 其其中中a1为为第第一一个个元元素素,又又称称做做表表头头元元素素,a2为为第第二二个个元元素素,an为为最最后后一一个个元元素素,又又称称做做表表尾尾元元素。素。 例如例如,在线性表在线性表 (1,4,3,2,8,10)中中,1为表头元素为表头元素
3、,10为表尾元素。为表尾元素。数据结构线性表PPT2.1.2 2.1.2 线性表的运算线性表的运算 线性表的基本运算如下线性表的基本运算如下: (1) 初初始始化化线线性性表表InitList(&L):构构造造一一个个空空的的线线性性表表L。 (2) 销销毁毁线线性性表表DestroyList(&L):释释放放线线性性表表L占占用用的内存空间。的内存空间。数据结构线性表PPT (3) 判判线线性性表表是是否否为为空空表表ListEmpty(L):若若L为为空空表表,则返回真则返回真,否则返回假。否则返回假。 (4) 求求线线性性表表的的长长度度ListLength(L):返返回回L中中元元素素
4、个数。个数。 (5) 输输出出线线性性表表DispList(L):当当线线性性表表L不不为为空空时时,顺序显示顺序显示L中各结点的值域。中各结点的值域。 (6) 求求线线性性表表L中中指指定定位位置置的的某某个个数数据据元元素素GetElem(L,i,&e):用用e返返回回L中中第第 i(1iListLength(L)个元素的值。个元素的值。数据结构线性表PPT (7) 定定位位查查找找LocateElem(L,e):返返回回L中中第第1个个值值域域与与e相相等等的的位位序序。若若这这样样的的元元素素不不存存在在,则则返返回回值值为为0。 (8) 插插入入数数据据元元素素ListInsert(
5、&L,i,e):在在L的的第第i(1iListLength(L)+1)个个元元素素之之前前插插入入新新的的元元素素e,L的长度增的长度增1。 (9) 删除数据元素删除数据元素ListDelete(&L,i,&e):删除删除L的第的第i(1iListLength(L)个元素个元素,并用并用e返回其值返回其值,L的长的长度减度减1。数据结构线性表PPT 例例2.1 假假设设有有两两个个集集合合 A 和和 B 分分别别用用两两个个线线性性表表 LA 和和 LB 表表示示,即即线线性性表表中中的的数数据据元元素素即即为为集集合合中中的的成成员员。编编写写一一个个算算法法求求一一个个新新的的集集合合C=
6、AB,即将两个集合的并集放在线性表即将两个集合的并集放在线性表LC中。中。 解解:本算法思想是本算法思想是:先初始化线性表先初始化线性表LC,将将LA的的所有元素复制到所有元素复制到LC中中,然后扫描线性表然后扫描线性表LB,若若LB的的当前元素不在线性表当前元素不在线性表LA中中,则将其插入到则将其插入到LC中。算中。算法如下法如下:数据结构线性表PPTvoid unionList(List LA,List LB,List &LC) int lena,lenc,i; ElemType e; InitList(LC); for (i=1;i=ListLength(LA);i+) /*将将LA的
7、所有元素插入到的所有元素插入到Lc中中*/ GetElem(LA,i,e); ListInsert(LC,i,e); lena=ListLength(LA); /*求线性表的长度求线性表的长度*/ lenB=ListLength(LB); 数据结构线性表PPTfor (i=1;i=lenb;i+) GetElem(LB,i,e);/*取取LB中第中第i个数据元素赋给个数据元素赋给e*/ if (!LocateElem(LA,e) ListInsert(LC,+lenc,e); /*LA中不存在和中不存在和e相同者相同者,则插入到则插入到LC中中*/ 数据结构线性表PPT 由由 于于 Locat
8、eElem(LA,e)运运 算算 的的 时时 间间 复复 杂杂 度度 为为O(ListLength(LA),所以本算法的时间复杂度为所以本算法的时间复杂度为: O(ListLength(LA)*ListLength(LB)。数据结构线性表PPT2.2 2.2 线性表的顺序存储线性表的顺序存储2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表2.2.2 顺序表基本运算的实现顺序表基本运算的实现数据结构线性表PPT2.2.1 2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表 线性表的顺序存储结构就是线性表的顺序存储结构就是:把线性表中的所把线性表中的所有元素按照其逻辑顺序依次存储到从
9、计算机存储有元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。器中指定存储位置开始的一块连续的存储空间中。 这样这样,线性表中第一个元素的存储位置就是指线性表中第一个元素的存储位置就是指定的存储位置定的存储位置,第第i+1个元素个元素(1in-1)的存储的存储位置紧接在第位置紧接在第i i个元素的存储位置的后面。个元素的存储位置的后面。线性表线性表 逻辑结构逻辑结构顺序顺序表表 存储结构存储结构数据结构线性表PPT 假定线性表的元素类型为假定线性表的元素类型为ElemType,则每个元则每个元素所占用存储空间大小素所占用存储空间大小(即字节数即字节数)为为si
10、zeof(ElemType),整个线性表所占用存储空间的大小整个线性表所占用存储空间的大小为为: n*sizeof(ElemType)其中其中,n表示线性表的长度。表示线性表的长度。数据结构线性表PPT顺序表示意图顺序表示意图数据结构线性表PPT 在在定定义义一一个个线线性性表表的的顺顺序序存存储储类类型型时时,需需要要定定义义一一个个数数组组来来存存储储线线线线表表中中的的所所有有元元素素和和定定义义一一个个整整型变量来存储线性表的长度。型变量来存储线性表的长度。 假假定定数数组组用用dataMaxSize表表示示,长长度度整整型型变变量量用用length表表示示,并并采采用用结结构构体体类
11、类型型表表示示,则则元元素素类类型型为为通通用用类类型型标标识识符符ElemType的的线线性性表表的的顺顺序序存存储储类类型型可可描述如下描述如下: :数据结构线性表PPT typedef struct ElemType dataMaxSize; int length; SqList; /*/*顺序表类型顺序表类型*/*/ 其中其中,data成员存放元素成员存放元素,length成员存放线性表成员存放线性表的实际长度。的实际长度。 说明：由于说明：由于C/C+C/C+中数组的下标从中数组的下标从0 0开始，线性表的第开始，线性表的第i i个元素个元素a ai i存放顺序表的第存放顺序表的第i
12、-1i-1位置上。为了清楚，将位置上。为了清楚，将a ai i在逻辑在逻辑序列中的位置称为序列中的位置称为逻辑位序逻辑位序，在顺序表中的位置称为，在顺序表中的位置称为物理位物理位序序。数据结构线性表PPT2.2.2 2.2.2 顺序表基本运算的实现顺序表基本运算的实现 一旦采用顺序表存储结构一旦采用顺序表存储结构,我们就可以用我们就可以用C/C+语言实现线性表的各种基本运算。为了方语言实现线性表的各种基本运算。为了方便便,假设假设ElemType为为char类型类型,使用如下自定义类使用如下自定义类型语句型语句: typedef char ElemType;数据结构线性表PPT1. 建立顺序表
13、建立顺序表其方法是将给定的含有其方法是将给定的含有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;数据结构线性表PPT2. 顺序表基本运算算法顺序表基本运算算法(1) 初始化线性表初始化线性表InitList(L) 该该
14、运运算算的的结结果果是是构构造造一一个个空空的的线线性性表表L。实实际际上上只只需需将将length成员设置为成员设置为0即可。即可。 void InitList(SqList *&L) /引用型指针引用型指针 L=(SqList *)malloc(sizeof(SqList); /*分配存放线性表的空间分配存放线性表的空间*/ L-length=0; 本算法的时间复杂度为本算法的时间复杂度为O(1)。顺序表L数据结构线性表PPT (2) 销毁线性表销毁线性表DestroyList(L) 该运算的结果是释放线性表该运算的结果是释放线性表L占用的内存空间。占用的内存空间。 void Destro
15、yList(SqList *&L) free(L); 本算法的时间复杂度为本算法的时间复杂度为O(1)。 数据结构线性表PPT (3) 判定是否为空表判定是否为空表ListEmpty(L) 该该运运算算返返回回一一个个值值表表示示L是是否否为为空空表表。若若L为为空空表表,则返回则返回1,否则返回否则返回0。 int ListEmpty(SqList *L) return(L-length=0); 本算法的时间复杂度为本算法的时间复杂度为O(1)。数据结构线性表PPT (4) 求线性表的长度求线性表的长度ListLength(L) 该该运运算算返返回回顺顺序序表表L的的长长度度。实实际际上上只
16、只需需返返回回length成员的值即可。成员的值即可。 int ListLength(SqList *L) return(L-length); 本算法的时间复杂度为本算法的时间复杂度为O(1)。数据结构线性表PPT (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); 数据结构线性表PPT 本本
17、算算法法中中基基本本运运算算为为for循循环环中中的的printf语语句句,故时间复杂度为故时间复杂度为: O(L-length)或或O(n)数据结构线性表PPT (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(1)。 数据结构线性表PPT (7)
18、 按元素值查找按元素值查找LocateElem(L,e) 该该运运算算顺顺序序查查找找第第1个个值值域域与与e相相等等的的元元素素的的位位序序。若若这样的元素不存在这样的元素不存在,则返回值为则返回值为0。 int LocateElem(SqList *L, ElemType e) int i=0;while (ilength & L-datai!=e) i+;if (i=L-length)return 0;else return i+1; 数据结构线性表PPT 本本算算法法中中基基本本运运算算为为while循循环环中中的的i+语语句句,故故时间复杂度为时间复杂度为: O(L-length)或
19、或O(n)数据结构线性表PPT (8) 插入数据元素插入数据元素ListInsert(L,i,e) 该该 运运 算算 在在 顺顺 序序 表表 L的的 第第 i个个 位位 置置(1iListLength(L)+1)上插入新的元素上插入新的元素e。 思思路路：如如果果i值值不不正正确确,则则显显示示相相应应错错误误信信息息；否否则则将将顺顺序序表表原原来来第第i个个元元素素及及以以后后元元素素均均后后移移一一个个位位置置,腾腾出出一一个个空空位位置置插插入入新新元元素素,顺顺序序表表长度增长度增1。数据结构线性表PPT int ListInsert(SqList *&L,int i,ElemTyp
20、e e) int j; if (iL-length+1)return 0; i-; /*将顺序表将顺序表逻辑位序逻辑位序转化为转化为elem下标即下标即物理位序物理位序*/ for (j=L-length;ji;j-) L-dataj=L-dataj-1; /*将将datai及后面元素后移一个位置及后面元素后移一个位置*/ L-datai=e; L-length+; /*顺序表长度增顺序表长度增1*/ return 1; a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize 数据结构线性表PPT 对于本算法来说对于本算法来说,元素移动的次数不仅与表长元素移动的次数不仅与表
21、长L.length=n有关有关,而且与插入位置而且与插入位置i有关有关:当当i=n+1时时,移动次数为移动次数为0；当；当i=1时时,移动次数为移动次数为n,达到最大值。达到最大值。在线性表在线性表sq中共有中共有n+1个可以插入元素的地方。假设个可以插入元素的地方。假设pi(= )是在第是在第i个位置上插入一个元素的概率个位置上插入一个元素的概率,则则在长度为在长度为n的线性表中插入一个元素时所需移动元素的线性表中插入一个元素时所需移动元素的平均次数为的平均次数为: 因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n)。数据结构线性表PPT (9) 删除数据元素删除数据元素L
22、istDelete(L,i,e) 删删除除顺顺序序表表L中中的的第第i(1iListLength(L)个个元元素。素。 思思路路：如如果果i值值不不正正确确,则则显显示示相相应应错错误误信信息息；否否则则将将线线性性表表第第i个个元元素素以以后后元元素素均均向向前前移移动动一一个个位位置置,这这样样覆覆盖盖了了原原来来的的第第i个个元元素素,达达到到删删除除该该元元素的目的素的目的,最后顺序表长度减最后顺序表长度减1。数据结构线性表PPTint ListDelete(SqList *&L,int i,ElemType &e) int j; if (iL-length)return 0; i-;
23、 /*将顺序表逻辑位序转化为将顺序表逻辑位序转化为elem下标即物理位序下标即物理位序*/ e=L-datai; for (j=i;jlength-1;j+) L-dataj=L-dataj+1; /*将将datai之后的元素后前移一个位置之后的元素后前移一个位置*/ L-length-;/*顺序表长度减顺序表长度减1*/ return 1;a0ai-1aian-1逻辑位序逻辑位序1 i i+1 n MaxSize 数据结构线性表PPT 对于本算法来说对于本算法来说,元素移动的次数也与表长元素移动的次数也与表长n和和删除元素的位置删除元素的位置i有关有关:当当i=n时时,移动次数为移动次数为0
24、；当；当i=1时时,移动次数为移动次数为n-1。在线性表。在线性表sq中共有中共有n个元素可以个元素可以被删除。假设被删除。假设pi(pi= )是删除第是删除第i个位置上元素的概个位置上元素的概率率,则在长度为则在长度为n的线性表中删除一个元素时所需移的线性表中删除一个元素时所需移动元素的平均次数为动元素的平均次数为: = 因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O(n)。数据结构线性表PPT 例例2.2 设设计计一一个个算算法法,将将x插插入入到到一一个个有有序序(从从小小到到大大排排序序)的的线线性性表表(顺顺序序存存储储结结构构即即顺顺序表序表)的适当位置上的适当位置
25、上,并保持线性表的有序性。并保持线性表的有序性。 解解:先先通通过过比比较较在在顺顺序序表表L中中找找到到存存放放x的的位位置置i,然然后后将将x插插入入到到L.datai中中,最最后后将将顺顺序序表表的的长度增长度增1。数据结构线性表PPT void Insert(SqList *&L,ElemType x) int i=0,j; while (ilength & L-datailength-1;j=i;j-) L-dataj+1=L-dataj; L-datai=x; L-length+; 查找插入位置查找插入位置元素后移一个位置元素后移一个位置a0ai-1aian-1逻辑位序逻辑位序1
26、i i+1 n MaxSize 数据结构线性表PPT 例例2.3 设设计计一一个个算算法法,将将两两个个元元素素有有序序(从从小到大小到大)的顺序表合并成一个有序顺序表。的顺序表合并成一个有序顺序表。 求解思路求解思路:将两个顺序表进行二路归并。将两个顺序表进行二路归并。 数据结构线性表PPT归并到顺序表归并到顺序表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
27、)插入插入r(k=4) 5(i=2) 10(j=2) 将将5(j=3)插入插入r(k=5) 将将q中余下元素插入中余下元素插入r中。中。 顺序表顺序表p：135i顺序表顺序表q：241020j顺序表顺序表r：1k数据结构线性表PPTSqList *merge(SqList *p, SqList *q) SqList *r; int i=0,j=0,k=0; r=(SqList *)malloc(sizeof(SqList); while (ilength & jlength) if (p-datai dataj) r- datak=p- datai; i+;k+; else r- datak=
28、q- dataj; j+;k+; 数据结构线性表PPTwhile (ilength) r-datak=p-datai; i+;k+; while (jlength) r-datak=q-dataj; j+;k+; r-length=k; /*或或p-length+q-length*/ return(r);数据结构线性表PPT 例例2.4 已已知知长长度度为为n的的线线性性表表A采采用用顺顺序序存存储储结结构构,编编写写一一个个时时间间复复杂杂度度为为O(n)、空空间间复复杂杂度度为为O(1)的的算算法法,该该算算法法删删除除线线性性表表中中所所有有值值为为item的的数数据元素。据元素。 解解
29、:用用k记记录录顺顺序序表表A中中等等于于item的的元元素素个个数数,边边扫扫描描A边边统统计计k,并并将将不不为为item的的元元素素前前移移k个个位位置置,最后修改最后修改A的长度。对应的算法如下的长度。对应的算法如下:数据结构线性表PPTvoid delnode1(SqList &A,ElemType item) int k=0,i; /*k记录值不等于记录值不等于item的元素个数的元素个数*/ for (i=0;iA.length;i+) if (A.datai!=item) A.datak=A.datai; k+; /*不等于不等于item的元素增的元素增1*/ A.length
30、=k; /*顺序表顺序表A的长度等于的长度等于k*/算法算法1：类似于：类似于建顺序表建顺序表数据结构线性表PPTvoid delnode2(SqList &A,ElemType item) int k=0,i=0; /*k记录值等于记录值等于item的元素个数的元素个数*/ while (inext=NULL; for (i=0;idata=ai; s-next=L-next; /*将将*s插在原开始结点之前插在原开始结点之前,头结点之后头结点之后*/ L-next=s; 数据结构线性表PPTadc bi=0 i=1 i=2 i=3head采用头插法建立单链表的过程采用头插法建立单链表的过程
31、headaheaddaheadcdaheadbcda第第1 1步步: :建头结点建头结点第第2 2步步:i:i0,0,新建新建a a结点结点, ,插入到头结点之后插入到头结点之后第第3 3步步:i:i1,1,新建新建d d结点结点, ,插入到头结点之后插入到头结点之后第第4 4步步:i:i2,2,新建新建c c结点结点, ,插入到头结点之后插入到头结点之后第第5 5步步:i:i3,3,新建新建b b结点结点, ,插入到头结点之后插入到头结点之后数据结构线性表PPT (2) 尾插法建表尾插法建表 头插法建立链表虽然算法简单头插法建立链表虽然算法简单, ,但生成的链表但生成的链表中结点的次序和原数
32、组元素的顺序相反。若希望中结点的次序和原数组元素的顺序相反。若希望两者次序一致两者次序一致, ,可采用尾插法建立。该方法是将可采用尾插法建立。该方法是将新结点插到当前链表的表尾上新结点插到当前链表的表尾上, ,为此必须增加一为此必须增加一个尾指针个尾指针r,r,使其始终指向当前链表的尾结点。采使其始终指向当前链表的尾结点。采用尾插法建表的算法如下用尾插法建表的算法如下: :数据结构线性表PPT void CreateListR(LinkList *&L,ElemType a,int n) LinkList *s,*r;int i; L=(LinkList *)malloc(sizeof(Lin
33、kList); /*创建头结点创建头结点*/ r=L; /*r始终指向终端结点始终指向终端结点,开始时指向头结点开始时指向头结点*/ for (i=0;idata=ai;r-next=s; /*将将*s插入插入*r之后之后*/ r=s; r-next=NULL;/*终端结点终端结点next域置为域置为NULL*/ 数据结构线性表PPTbcdai=0 i=1 i=2 i=3head头结点头结点adcbb采用尾插法建立单链表的过程采用尾插法建立单链表的过程数据结构线性表PPT2. 插入结点运算插入结点运算 插插入入运运算算是是将将值值为为x的的新新结结点点插插入入到到单单链链表表的的第第i个个结结
34、点点的的位位置置上上。先先在在单单链链表表中中找找到到第第i-1个结点个结点,再在其后插入新结点。再在其后插入新结点。 单链表插入结点的过程如下图所示。单链表插入结点的过程如下图所示。数据结构线性表PPT插入结点示意图插入结点示意图数据结构线性表PPT 3. 删除结点运算删除结点运算 删除运算是将单链表的第删除运算是将单链表的第i个结点删去。先在单个结点删去。先在单链表中找到第链表中找到第i-1个结点个结点,再删除其后的结点。删再删除其后的结点。删除单链表结点的过程如下图所示。除单链表结点的过程如下图所示。数据结构线性表PPT删除结点示意图删除结点示意图数据结构线性表PPT 4. 线性表基本运
35、算实现线性表基本运算实现 (1) 初始化线性表初始化线性表InitList(L) 该运算建立一个空的单链表该运算建立一个空的单链表,即创建一个头结点。即创建一个头结点。 void InitList(LinkList *&L) L=(LinkList *)malloc(sizeof(LinkList); /*创建头结点创建头结点*/L-next=NULL; 数据结构线性表PPT (2) 销毁线性表销毁线性表DestroyList(L) 释释放放单单链链表表L占占用用的的内内存存空空间间。即即逐逐一一释释放放全全部部结结点点的空间。的空间。 void DestroyList(LinkList *&
36、L) LinkList *p=L,*q=p-next;while (q!=NULL) free(p); p=q;q=p-next;free(p); 数据结构线性表PPT (3) 判线性表是否为空表判线性表是否为空表ListEmpty(L) 若单链表若单链表L没有数据结点没有数据结点,则返回真则返回真,否则返回假。否则返回假。 int ListEmpty(LinkList *L) return(L-next=NULL); 数据结构线性表PPT (4) 求线性表的长度求线性表的长度ListLength(L) 返回单链表返回单链表L中数据结点的个数。中数据结点的个数。 int ListLength(
37、LinkList *L) LinkList *p=L;int i=0;while (p-next!=NULL) i+; p=p-next;return(i); 数据结构线性表PPT (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); 数据结构线性表PPT (6)求求 线线 性性 表表 L
38、中中 指指 定定 位位 置置 的的 某某 个个 数数 据据 元元 素素GetElem(L,i,&e) 思思路路：在在单单链链表表L中中从从头头开开始始找找到到第第 i个个结结点点,若若存在第存在第i个数据结点个数据结点,则将其则将其data域值赋给变量域值赋给变量e。数据结构线性表PPT 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-d
39、ata; return 1; 数据结构线性表PPT (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); 数据结构线性表P
40、PT (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; 数据结构线性表PPTif (p=NULL) return 0; /*未找到位序为未找到位序为i-1的结点的结点*/else/*找到位序为找到位序为i-1的结点的结点*p*/ s=(Link
41、List *)malloc(sizeof(LinkList);/*创建新结点创建新结点*s*/ s-data=e; s-next=p-next; /*将将*s插入到插入到*p之后之后*/ p-next=s; return 1;数据结构线性表PPT (9) 删除数据元素删除数据元素ListDelete(&L,i,&e) 思思路路：先先在在单单链链表表L L中中找找到到第第i-1i-1个个结结点点*p,*p,若若存存在在这这样的结点样的结点, ,且也存在后继结点且也存在后继结点, ,则删除该后继结点。则删除该后继结点。 int ListDelete(LinkList *&L,int i,ElemT
42、ype &e) int j=0;LinkList *p=L,*q;while (jnext;数据结构线性表PPTif (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; 数据结构线性表PPT
43、例例2.5 设设C=a1,b1,a2,b2,an,bn为为一一线线性性表表,采采用用带带头头结结点点的的hc单单链链表表存存放放,编编写写一一个个算算法法,将其拆分为两个线性表将其拆分为两个线性表,使得使得: A=a1,a2,an,B=b1,b2,bn 数据结构线性表PPT 解解: 设设拆拆分分后后的的两两个个线线性性表表都都用用带带头头结结点点的的单单链链表存放。表存放。 先先建建立立两两个个头头结结点点*ha和和*hb,它它们们用用于于存存放放拆拆分分后后的的线线性性表表A和和B,ra和和rb分分别别指指向向这这两两个个单单链链表表的的表表尾尾,用用p指指针针扫扫描描单单链链表表hc,将将
44、当当前前结结点点*p链链到到ha未未尾尾,p沿沿next域域下下移移一一个个结结点点,若若不不为为空空,则则当当前前结结点点*p链链到到hb未未尾尾,p沿沿next域域下下移移一一个个结结点点,如如此此这这样样,直直到到p为为空空。最后将两个尾结点的最后将两个尾结点的next域置空。域置空。 对应算法如下对应算法如下:数据结构线性表PPT void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) LinkList *p=hc-next,*ra,*rb; ha=hc; /*ha的头结点利用的头结点利用hc的头结点的头结点*/ ra=ha; /*ra
45、始终指向始终指向ha的末尾结点的末尾结点*/ hb=(LinkList *)malloc(sizeof(LinkList); /*创建创建hb头结点头结点*/ rb=hb; /*rb始终指向始终指向hb的末尾结点的末尾结点*/数据结构线性表PPT 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域置空域
46、置空*/数据结构线性表PPT 本本算算法法实实际际上上是是采采用用尾尾插插法法建建立立两两个个新新表表。所以所以, ,尾插法建表算法是很多类似习题的基础！尾插法建表算法是很多类似习题的基础！数据结构线性表PPT 例例 2.6 有有 一一 个个 带带 头头 结结 点点 的的 单单 链链 表表 head,其其ElemType类类型型为为char,设设计计一一个个算算法法使使其其元元素素递递增增有序。有序。 解解: :若若原原单单链链表表中中有有一一个个或或以以上上的的数数据据结结点点, ,先先构构造造只只含含一一个个数数据据结结点点的的有有序序表表( (只只含含一一个个数数据据结结点点的的单单链链
47、表表一一定定是是有有序序表表) )。扫扫描描原原单单链链表表余余下下的的结结点点*p(*p(直直到到p=NULLp=NULL为为止止),),在在有有序序表表中中通通过过比比较较找找插插入入*p*p的的前前驱驱结结点点*q,*q,然然后后将将*p*p插插入入到到*q*q之之后后( (这里实际上采用的是直接插入排序方法这里实际上采用的是直接插入排序方法) )。 数据结构线性表PPT void Sort(LinkList *&head) LinkList *p=head-next,*q,*r;if (p!=NULL) /*head有一个或以上的数据结点有一个或以上的数据结点*/ r=p-next;
48、/*r保存保存*p结点后继结点的指针结点后继结点的指针*/ p-next=NULL; /*构造只含一个数据结点的有序表构造只含一个数据结点的有序表*/ p=r; while (p!=NULL) r=p-next; /*r保存保存*p结点后继结点的指针结点后继结点的指针*/数据结构线性表PPT 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; /*扫描原单链表余下
49、的结点扫描原单链表余下的结点*/ 数据结构线性表PPT2.3.3 2.3.3 双链表双链表 对对于于双双链链表表,采采用用类类似似于于单单链链表表的的类类型型定定义义,其其DLinkList类型的定义如下类型的定义如下: typedef struct DNode /*定义双链表结点类型定义双链表结点类型*/ ElemType data; struct DNode *prior; /*指向前驱结点指向前驱结点*/struct DNode *next; /*指向后继结点指向后继结点*/ DLinkList;数据结构线性表PPT 在双链表中在双链表中, ,有些操作如求长度、取元素值和查有些操作如求长
50、度、取元素值和查找元素等操作算法与单链表中相应算法是相同的找元素等操作算法与单链表中相应算法是相同的, ,这这里不多讨论。但在单链表中里不多讨论。但在单链表中, ,进行结点插入和删除时进行结点插入和删除时涉及到前后结点的一个指针域的变化。而在双链表涉及到前后结点的一个指针域的变化。而在双链表中中, ,结点的插入和删除操作涉及到前后结点的两个指结点的插入和删除操作涉及到前后结点的两个指针域的变化。针域的变化。数据结构线性表PPT双链表中插入结点示意图双链表中插入结点示意图数据结构线性表PPT 归纳起来归纳起来,在双链表中在双链表中p所指的结点之后插入所指的结点之后插入一个一个*s结点。其操作语句
51、描述为结点。其操作语句描述为: s-next=p-next;/*将将*s插入到插入到*p之后之后*/ p-next-prior=s; s-prior=p; p-next=s;数据结构线性表PPT删除结点示意图删除结点示意图 在在 双双 链链 表表中中删删除除一一个个结结点点的的过过程程如如右右图图所所示示:数据结构线性表PPT 归纳起来归纳起来, ,删除双链表删除双链表L L中中*p*p结点的后续结点。结点的后续结点。其操作语句描述为其操作语句描述为: : p-next=q-next; q-next-prior=p;数据结构线性表PPT2.3.4 2.3.4 循环链表循环链表 循环链表循环链表
52、是另一种形式的链式存储结构。它的是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是空特点是表中最后一个结点的指针域不再是空, ,而是而是指向表头结点指向表头结点, ,整个链表形成一个环。由此整个链表形成一个环。由此, ,从表中从表中任一结点出发均可找到链表中其他结点。任一结点出发均可找到链表中其他结点。 数据结构线性表PPT 带头结点的循环单链表和循环双链表的示意图带头结点的循环单链表和循环双链表的示意图数据结构线性表PPT 例例2.7 编编写写出出判判断断带带头头结结点点的的双双向向循循环环链链表表L是是否对称相等的算法。否对称相等的算法。 解解:p从从左左向向右右扫扫描描
53、L,q从从右右向向左左扫扫描描L,若若对对应应数数据据结结点点的的data域域不不相相等等,则则退退出出循循环环,否否则则继继续续比比较较,直直到到p与与q相相等等或或p的的下下一一个个结结点点为为*q为为止止。对对应应算算法如下法如下:数据结构线性表PPTint 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; el
54、se if (p=q) break; /*数据结点为奇数的情况数据结点为奇数的情况*/ q=q-prior; if (p=q) break; /*数据结点为偶数的情况数据结点为偶数的情况*/ p=p-next; return same;数据结构线性表PPT2.3.5 2.3.5 静态链表静态链表 静态链表借用一维数组来描述线性链表。数组中静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点的一个分量表示一个结点,同时使用同时使用游标游标(指示器指示器cur即即为为伪指针伪指针)代替指针以指示结点在数组中的相对位置。代替指针以指示结点在数组中的相对位置。数组中的第数组中的第0个分量可
55、以看成头结点个分量可以看成头结点,其指针域指示静其指针域指示静态链表的第一个结点。态链表的第一个结点。 这种存储结构仍然需要预先分配一个较大空间这种存储结构仍然需要预先分配一个较大空间,但是在进行线性表的插入和删除操作时不需要移动元但是在进行线性表的插入和删除操作时不需要移动元素素,仅需要修改仅需要修改“指针指针”,因此仍然具有链式存储结构因此仍然具有链式存储结构的主要优点。的主要优点。数据结构线性表PPT 下图给出了一个静态链表的示例。图下图给出了一个静态链表的示例。图(a)是一个修改之前是一个修改之前的静态链表的静态链表,图图(b)是删除数据元素是删除数据元素“陈华陈华”之后的静态链表之后
56、的静态链表,图图(c)插入数据元素插入数据元素“王华王华”之后的静态链表之后的静态链表,图中用阴影表示图中用阴影表示修改的游标。修改的游标。 数据结构线性表PPT2.4 2.4 线性表的应用线性表的应用 计算任意两个表的简单自然连接过程讨论线性计算任意两个表的简单自然连接过程讨论线性表的应用。假设有两个表表的应用。假设有两个表A和和B,分别是分别是m1行、行、n1列列和和m2行、行、n2列列,它们简单自然连接结果它们简单自然连接结果C=A B,其其中中i表示表表示表A中列号中列号,j表示表表示表B中的列号中的列号,C为为A和和B的的笛卡儿积中满足指定连接条件的所有记录组笛卡儿积中满足指定连接条
57、件的所有记录组,该连该连接条件为表接条件为表A的第的第i列与表列与表B的第的第j列相等。例如列相等。例如:i=j数据结构线性表PPT C=A B的计算结果如下的计算结果如下: 3=1数据结构线性表PPT 由由于于每每个个表表的的行行数数不不确确定定,为为此此,用用单单链链表表作作为为表表的的存存储储结结构构,每每行行作作为为一一个个数数据据结结点点。另另外外,每每行行中中的的数数据据个个数数也也是是不不确确定定的的,但但由由于于提提供供随随机机查查找找行行中中的的数数据据,所所以以每每行行的的数数据据采采用用顺顺序序存存储储结结构构,这这里里用用长长度度为为MaxCol的的数数组组存存储储每每
58、行行的的数数据据。因因此此,该该单单链表中数据结点类型定义如下链表中数据结点类型定义如下: #define MaxCol 10/*最大列数最大列数*/ typedef struct Node1/*定义数据结点类型定义数据结点类型*/ ElemType dataMaxCol; struct Node1 *next; /*指向后继数据结点指向后继数据结点*/ DList;数据结构线性表PPT 另另外外,需需要要指指定定每每个个表表的的行行数数和和列列数数,为为此此将将单单链链表的头结点类型定义如下表的头结点类型定义如下: typedef struct Node2/*定义头结点类型定义头结点类型*/
59、 int Row,Col;/*行数和列数行数和列数*/ DList *next;/*指向第一个数据结点指向第一个数据结点*/ HList; 采采用用尾尾插插法法建建表表方方法法创创建建单单链链表表,用用户户先先输输入入表表的的行行数数和和列列数数,然然后后输输入入各各行行的的数数据据,为为了了简简便便,假假设设表表中数据为中数据为int型型,因此定义因此定义: typedef int ElemType; 对应的建表算法如下对应的建表算法如下:数据结构线性表PPTvoid create(HList *&h) int i,j; DList *r,*s; h=(HList *)malloc(size
60、of(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-dataj); if (h-next=NULL) h-next=s; else r-next=s; r=s; /*r始终指向最后一个数据结点始终指向最后一个数据结点*/ r-next=NULL; 采用尾插法建表采用尾插法建表数据结构线性表PPT对
61、应的输出表的算法如下对应的输出表的算法如下:void display(HList *h) int j; DList *p=h-next; while (p!=NULL) for (j=0;jCol;j+) printf(%4d,p-dataj); printf(n); p=p-next; 数据结构线性表PPT 为了实现两个表为了实现两个表h1和和h2的简单自然连接的简单自然连接,先要先要输入两个表连接的列序号输入两个表连接的列序号f1和和f2,然后扫描单链表然后扫描单链表h1,对于对于h1的每个结点的每个结点,从头至尾扫描单链表从头至尾扫描单链表h2,若若自然连接条件成立自然连接条件成立,即即
62、h1的当前结点的当前结点*p和和h2的当的当前结点前结点*q满足满足: p-dataf1-1=q-dataf2-1则在新建单链表则在新建单链表h中添加一个新结点。中添加一个新结点。 新建的单链表新建的单链表h也是采用尾插法建表方法创建也是采用尾插法建表方法创建的。的。 实现两个表实现两个表h1和和h2的简单自然连接并生成结的简单自然连接并生成结果果h的算法如下的算法如下:数据结构线性表PPTvoid link(HList *h1,HList *h2,HList *&h) int f1,f2,i;DList *p=h1-next,*q,*s,*r; printf(连接字段是连接字段是:第第1个表
63、位序个表位序,第第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;数据结构线性表PPT while (q!=NULL) if (p-dataf1-1=q-dataf2-1) /*对应字段值相等对应字段值相等*/ s=(DList *)malloc(sizeof(DList); /*创建一个数据结点创建一个数据结点*/for (i=0;iCol;i+) /*复制表复制表1的当
64、前行的当前行*/ s-datai=p-datai;for (i=0;iCol;i+) s-datah1-Col+i=q-datai;/*复复制制表表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域置空域置空*/ 尾插法建表尾插法建表数据结构线性表PPT2.5 2.5
65、 有序表有序表 所谓所谓有序表有序表,是指这样的线性表是指这样的线性表,其中所有元素其中所有元素以递增或递减方式排列以递增或递减方式排列,并规定有序表中不存在元并规定有序表中不存在元素值相同的元素。在这里仍以顺序表进行存储。素值相同的元素。在这里仍以顺序表进行存储。 其中只有其中只有ListInsert()基本运算与前面的顺序表基本运算与前面的顺序表对应的运算有所差异对应的运算有所差异,其余都是相同的。有序表其余都是相同的。有序表的的ListInsert()运算对应的算法如下运算对应的算法如下: 数据结构线性表PPT int ListInsert(SqList &L,ElemType e) i
66、nt i=0,j;while (iL.length & L.dataii;j-) /*将将datai及后面元素后移一个位置及后面元素后移一个位置*/L.dataj=L.dataj-1;L.datai=e;L.length+;/*顺序表长度增顺序表长度增1*/ return 1; 注意：这里用的不是注意：这里用的不是顺序表指针，直接就顺序表指针，直接就是顺序表是顺序表数据结构线性表PPT本章小结本章小结本章的基本学习要点如下本章的基本学习要点如下: (1) 理解线性表的逻辑结构特性。理解线性表的逻辑结构特性。 (2) 深深入入掌掌握握线线性性表表的的两两种种存存储储方方法法,即即顺顺序序表表和和链表。体会这两种存储结构之间的差异。链表。体会这两种存储结构之间的差异。 (3) 重点掌握顺序表和链表上各种基本运算的实现。重点掌握顺序表和链表上各种基本运算的实现。 (4) 综综合合运运用用线线性性表表这这种种数数据据结结构构解解决决一一些些复复杂杂的的实际问题。实际问题。数据结构线性表PPT此课件下载可自行编辑修改，供参考！此课件下载可自行编辑修改，供参考！感谢你的支持，我们会努力做得更好！感谢你的支持，我们会努力做得更好！
