第2章线性表课件.ppt

第第2 2章章 线性表线性表 2.1 2.1 线性表的基本概念线性表的基本概念 2.2 2.2 线性表的顺序存储线性表的顺序存储2.3 2.3 线性表的链式存储线性表的链式存储2.4 2.4 线性表的应用线性表的应用 本章小结本章小结 2.1 2.1 线性表的基本概念线性表的基本概念 2.1.1 线性表的定义线性表的定义2.1.2 线性表的运算线性表的运算2.1.1 2.1.1 线性表的定义线性表的定义 线性表是由零个或多个具有相同特性的数据线性表是由零个或多个具有相同特性的数据元素组成的一个有限序列。元素组成的一个有限序列。该序列中所含元素的该序列中所含元素的个数叫做线性表的长度个数叫做线性表的长度,用用n表示表示,n0。 当当n=0时时,表示线性表是一个空表表示线性表是一个空表,即表中不包即表中不包含任何元素。设序列中第含任何元素。设序列中第i (i表示位序表示位序)个元素为个元素为ai(1in)。 线性表的一般表示为线性表的一般表示为: (a1,a2,ai,ai+1,an) 其中其中a1为第一个元素为第一个元素,又称做表头元素又称做表头元素, a2为第为第二个元素二个元素, an为最后一个元素为最后一个元素,又称做表尾元素。又称做表尾元素。 例如例如,在线性表在线性表 (1,4,3,2,8,10)中中, 1为表头元素为表头元素,10为表尾元素。为表尾元素。二元组表示二元组表示List=(D,R)D=ai|ai Elemset, i=1,2,n, n=0R=| ai-1, ai D , i=2,3,n, n=0 2.1.2 2.1.2 线性表的运算线性表的运算 线性表的基本运算如下线性表的基本运算如下: (1)初始化线性表初始化线性表InitList(&L): 构造一个空的线性构造一个空的线性表表L。 (2)销毁线性表销毁线性表DestroyList(&L):释放线性表释放线性表L占用占用的内存空间。的内存空间。 (3)判线性表是否为空表判线性表是否为空表ListEmpty(L):若若L为空表为空表,则返回真则返回真,否则返回假。否则返回假。 (4)求线性表的长度求线性表的长度ListLength(L):返回返回L中元素个中元素个数。数。 (5)输出线性表输出线性表DispList(L):当线性表当线性表L不为空时不为空时,顺序显示顺序显示L中各结点的值域。中各结点的值域。 (6)求线性表求线性表L中指定位置的某个数据元素中指定位置的某个数据元素GetElem(L,i, &e):用用e返回返回L中第中第 i(1iListLength(L)个元素的值。个元素的值。 (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。例例1 在线性表在线性表La中删除所有值为中删除所有值为x的结点。的结点。例例2 假设有两个集合假设有两个集合 A 和和 B 分别用两个线性表分别用两个线性表 LA 和和 LB 表示表示,即线性表中的数据元素即为集合中的成即线性表中的数据元素即为集合中的成员。编写一个算法求一个新的集合员。编写一个算法求一个新的集合AB。 本算法思想本算法思想:先初始化线性表先初始化线性表LC,将将LA的所有的所有元素复制到元素复制到LC中中,然后扫描线性表然后扫描线性表LB,若若LB的当前的当前元素不在线性表元素不在线性表LA中中,则将其插入到则将其插入到LC中。算法如中。算法如下下:void unionList(List &LA,List LB） /将所有在将所有在Lb中但不在中但不在La中的元素插入到中的元素插入到LaLa_len=listlength(La); Lb_len=listlength(Lb);/求表的长度求表的长度 for (i=1;i=Lb_len;i+) GetElem(Lb,i,e);/取取lb中第中第i个元素到个元素到e中中 if(!LocateElem(La,e) ListInsert(Lc,i,e); /union2.2 2.2 线性表的顺序存储线性表的顺序存储2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表2.2.2 顺序表基本运算的实现顺序表基本运算的实现2.2.1 2.2.1 线性表的顺序存储线性表的顺序存储顺序表顺序表 线性表的顺序存储结构就是线性表的顺序存储结构就是:把线性表中的所有把线性表中的所有元素按照其逻辑顺序依次存储到从计算机存储器元素按照其逻辑顺序依次存储到从计算机存储器中指定存储位置开始的一块连续的存储空间中。中指定存储位置开始的一块连续的存储空间中。 这样这样, 线性表中第一个元素的存储位置就是指线性表中第一个元素的存储位置就是指定的存储位置定的存储位置, 第第i+1个元素个元素(1in-1)的存储的存储位置紧位置紧接在第接在第i i个元素的存储位置的后面。个元素的存储位置的后面。 用一组地址连续的存储单元依次存储用一组地址连续的存储单元依次存储线性表中的元素，以元素在计算机内物线性表中的元素，以元素在计算机内物理地址相邻表示线性表中数据元素之间理地址相邻表示线性表中数据元素之间的逻辑关系的逻辑关系。 假定线性表的元素类型为假定线性表的元素类型为ElemType,则每个元素则每个元素所占用存储空间大小所占用存储空间大小(即字节数即字节数)为为sizeof(ElemType),整个线性表所占用存储空间的大小为整个线性表所占用存储空间的大小为: n*sizeof(ElemType)其中其中,n表示线性表的长度。表示线性表的长度。 a a1 1 LOC(A) 0 a a2 2 LOC(A)+sizeof(ElemType) 1 线性表存储空间线性表存储空间 存储地址存储地址 下标位置下标位置 a ai i LOC(A)+(i-1)*sizeof(ElemType) i-1 a an n LOC(A)+(n-1)*sizeof(ElemType) n-1 LOC(A)+(MaxSize-1)*sizeof(ElemType) MaxSize-1 顺序表示意图顺序表示意图 Loc(ai+1)=Loc(ai)+l Loc(ai)=Loc(a1)+(i-1)*l 线性表的顺序存储结构是一种线性表的顺序存储结构是一种随机存取随机存取的的存储结构。存储结构。 描述：描述：/define LIST_Init_Size 100/define LISTINCREMENT 10Typedef Struct ElemType *elem; /存储空间基地址存储空间基地址 int length; /有效长度有效长度 int listsize；/分配的容量分配的容量SqList;2.2.2 2.2.2 顺序表基本运算的实现顺序表基本运算的实现 一旦采用顺序表存储结构一旦采用顺序表存储结构,我们就可以用我们就可以用C/C+语言实现线性表的各种基本运算。为了方便语言实现线性表的各种基本运算。为了方便,假设假设数据类型为数据类型为ElemType。 (1)初始化线性表初始化线性表InitList(L) 该运算的结果是构造一个空的线性表该运算的结果是构造一个空的线性表L。实际上只。实际上只需将需将length成员设置为成员设置为0即可。即可。Status InitList(SqList &L) /构造一个空的线性表构造一个空的线性表LL.elem=(ElemType*)malloc(LIST_Init_Size*sizeof(ElenType); if (!L.elem) exit (overflow); / 存储分配失败存储分配失败 L.length=0; L.listsize=LIST_Init_Size; return(OK); /InitList_Sq本算法的时间复杂度为本算法的时间复杂度为O(1)。 (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) if (ListEmpty(L) return;for (i=0;iL.length;i+)printf(%c,L.elemi);printf(n); 本算法中基本运算为本算法中基本运算为for循环中的循环中的printf语句语句,故时间复杂度为故时间复杂度为: O(L.length)或或O(n) (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.elemi-1;return 1; 本算法的时间复杂度为本算法的时间复杂度为O(1)。 (7)按元素值查找按元素值查找LocateElem(L,e) 该运算顺序查找第该运算顺序查找第1个值域与个值域与e相等的元素的相等的元素的位序位序。若这样的元素不存在若这样的元素不存在,则返回值为则返回值为0。 int LocateElem(SqList L, ElemType e) i=0;while (i=L.length)return 0;else return i+1; (8)插入数据元素插入数据元素ListInsert(L,i,e) 该 运 算 在 顺 序 表该 运 算 在 顺 序 表 L 的 第的 第 i 个 位 置个 位 置(1iListLength(L)+1)上插入新的元素上插入新的元素e。 思路：思路：如果如果i值不正确值不正确,则显示相应错误信息；则显示相应错误信息；否则将顺序表原来第否则将顺序表原来第i个元素及其后元素均后移个元素及其后元素均后移一个位置一个位置,空出一个位置插入新元素；最后顺序空出一个位置插入新元素；最后顺序表长度增表长度增1。 int ListInsert(SqList &L,int i,ElemType e) /在顺序表在顺序表L中第中第i个元素前插入个元素前插入e if (iL.length+1) return ERROR;/i值不合法值不合法 if(L.Length=L.Listsize)/当前分配已满，增加空间当前分配已满，增加空间 newbase=(ElemType*) realloc(L.elem, (L.Listsize+LISTINCREMENT）*sizeof(ElemType); if (!newbase) exit(Overflow);/存储分配失败存储分配失败 L.elem=newbase; L.listsize+=LISTINCREMENT; q=&(L.elemi-1);/q为插入位置为插入位置 for (p=&(L.elemL.length-1; p=q; -p) *(p+1)=*p;/元素后移元素后移 *q=e; + L.length /顺序表长度增顺序表长度增1 return (ok); 对于本算法来说对于本算法来说,元素移动的次数不仅与表长元素移动的次数不仅与表长L.length=n有关有关,而且与插入位置而且与插入位置i有关有关:当当i=n+1时时,移移动次数为动次数为0；当；当i=1时时,移动次数为移动次数为n,达到最大值。在达到最大值。在线性表线性表sq中共有中共有n+1个可以插入元素的地方。假设个可以插入元素的地方。假设pi(= )是在第是在第i个位置上插入一个元素的概率个位置上插入一个元素的概率,则在则在长度为长度为n的线性表中插入一个元素时所需移动元素的线性表中插入一个元素时所需移动元素的平均次数为的平均次数为: 因此插入算法的平均时间复杂度为因此插入算法的平均时间复杂度为O(n)。11n)(2)1(11)1(1111nOninninniniip (9)删除数据元素删除数据元素ListDelete(L,i,e) 该运算删除顺序表该运算删除顺序表L的第的第i(1iListLength(L)个元素。个元素。 思路思路：如果：如果i值不正确值不正确,则显示相应错误信息；则显示相应错误信息；否则将线性表第否则将线性表第i个元素以后元素均向前移动一个个元素以后元素均向前移动一个位置位置,这样覆盖了原来的第这样覆盖了原来的第i个元素个元素,达到删除该元达到删除该元素的目的；最后顺序表长度减素的目的；最后顺序表长度减1。int ListDelete(SqList &L, int i, ElemType &e) if (iL.length)return ERROR; p=&(L.elemi-1); e=*p; q=L.elem+L.length-1; /表尾的位置表尾的位置 for (+p; p=q; +p) *(p-1)=*p;/被删位置以后的元素前移被删位置以后的元素前移 -L.length;/顺序表长度减顺序表长度减1 return Ok; 对于本算法来说对于本算法来说,元素移动的次数也与表长元素移动的次数也与表长n和和删除元素的位置删除元素的位置i有关有关:当当i=n时时,移动次数为移动次数为0；当；当i=1时时,移动次数为移动次数为n-1。在线性表。在线性表sq中共有中共有n个元素可以个元素可以被删除。假设被删除。假设pi(pi= )是删除第是删除第i个位置上元素的概个位置上元素的概率率,则在长度为则在长度为n的线性表中删除一个元素时所需移的线性表中删除一个元素时所需移动元素的平均次数为动元素的平均次数为: = 因此删除算法的平均时间复杂度为因此删除算法的平均时间复杂度为O(n)。)(21)(1)(11nOninninpninii n1 例例3 设计一个算法设计一个算法,将将x插入到一个有序插入到一个有序(从从小到大排序小到大排序)的线性表的线性表(顺序存储结构即顺序表顺序存储结构即顺序表)的适当位置上的适当位置上,并保持线性表的有序性。并保持线性表的有序性。 解解:先通过比较，在顺序表先通过比较，在顺序表L中找到存放中找到存放x的的位置位置i,然后将然后将x插入到插入到L.elemi中中,最后将顺序表最后将顺序表的长度增的长度增1。 void Insert(SqList &L, ElemType x) i=0; while (iL.length & L.elemi=i;j-) L.elemj+1=L.elemj; L.elemi=x; L.length+; 例例4 设计一个算法设计一个算法,将两个元素有序将两个元素有序(从小到从小到大大)的顺序表合并成一个有序顺序表。的顺序表合并成一个有序顺序表。 思路思路:将两个顺序表进行二路归并。例如将两个顺序表进行二路归并。例如: 顺序表顺序表p:1,3,5 i扫描扫描p 顺序表顺序表q:2,4,10,20 j扫描扫描q 归并到顺序表归并到顺序表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)k=5) 将将q q中余下元素插入中余下元素插入r r中。中。 SqList merge(SqList p, SqList q， SqList &r) i=j=k=0; r=(SqList *)malloc(sizeof(SqList); while (ip.length & jq.length) if (p.elemiq.elemj) r. elemk=p.elem i; i+;k+; else r.elemk=q. elemj; j+;k+; while (ip.length) r.elemk=p.elemi; i+;k+; while (jq.length) r.elemk=q.elemj; j+;k+; r.length=k; /或或p.length+q.length 例例5 已知长度为已知长度为n的线性表的线性表A采用顺序存储结构采用顺序存储结构,编写一个时间复杂度为编写一个时间复杂度为O(n)、空间复杂度为、空间复杂度为O(1)的的算法算法,该算法删除线性表中所有值为该算法删除线性表中所有值为item的数据元素。的数据元素。 解解:用用k记录顺序表记录顺序表A中等于中等于item的元素个数的元素个数,边扫边扫描描A边统计边统计k,并将不为并将不为item的元素前移的元素前移k个位置个位置,最后最后修改修改A的长度。对应的算法如下的长度。对应的算法如下:void delnode(SqList &A,ElemType item) k=0,i=0; /k记录值等于记录值等于item的元素个数的元素个数 while (inext=NULL; for (i=0;idata=ai; s-next=L-next; /将将s插在原开始结点之前插在原开始结点之前,头结点之后头结点之后 L-next=s; adcbi=0 i=1 i=2 i=3head采用头插法建立单链表的过程采用头插法建立单链表的过程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结点结点, ,插入到头结点之后插入到头结点之后 (2)尾插法建表尾插法建表 头插法建立链表虽然算法简单头插法建立链表虽然算法简单, ,但生成的链表但生成的链表中结点的次序和原数组元素的顺序相反。若希望中结点的次序和原数组元素的顺序相反。若希望两者次序一致两者次序一致, ,可采用尾插法建立。该方法是将可采用尾插法建立。该方法是将新结点插到当前链表的表尾上新结点插到当前链表的表尾上, ,为此必须增加一为此必须增加一个尾指针个尾指针r,r,使其始终指向当前链表的尾结点。采使其始终指向当前链表的尾结点。采用尾插法建表的算法如下用尾插法建表的算法如下: : void CreateListR(LinkList &L,ElemType a,int n) LinkList s,r;int i; L=(LinkList )malloc(sizeof(LinkList); /创建头结点创建头结点 L-next=NULL; r=L; /r始终指向终端结点始终指向终端结点,开始时指向头结点开始时指向头结点 for (i=0;idata=ai;r-next=s; /将将s插入插入r之后之后 r=s; r-next=NULL;/终端结点终端结点next域置为域置为NULL adcbi=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(LNode); /创建头结点创建头结点L-next=NULL; (2)销毁线性表销毁线性表DestroyList(L) 释放单链表释放单链表L占用的内存空间。即逐一释放全部结点占用的内存空间。即逐一释放全部结点的空间。的空间。 void DestroyList(LinkList &L) 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) p=L; i=0;while (p-next!=NULL) p=p-next; i+;return(i); (5)输出线性表输出线性表DispList(L) 逐一扫描单链表逐一扫描单链表L的每个数据结点的每个数据结点,并显示各结点并显示各结点的的data域值。域值。 void DispList(LinkList L) 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) p=L; j=0;while (jnext;if (ji|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) p=L-next; 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) p=L; j=0; while (jnext; if (!p|ji-1) return ERROR; /i小于小于1或大于表长或大于表长+1 s=(LinkList)malloc(sizeof(LinkList); /建新结点建新结点ss-data=e; s-next=p-next; /将将s插入到插入到p之后之后 p-next=s; return OK; (9)删除数据元素删除数据元素ListDelete(&L,i,&e) 思路：思路：先在单链表先在单链表L L中找到第中找到第i-1i-1个结点个结点p,p,若存在这若存在这样的结点样的结点, ,且也存在后继结点且也存在后继结点, ,则删除该后继结点。则删除该后继结点。 int ListDelete(LinkList &L,int i,ElemType &e) j=0;p=L;while (jnext) /查找第查找第i-1个结点个结点 j+; p=p-next;if (!(p-next)|ji-1) return ERROR; /位置不合理位置不合理 q=p-next; /q指向要删除的结点指向要删除的结点 p-next=q-next;/从单链表中删除从单链表中删除q结点结点 free(q); /释放释放q结点结点 return OK; 例例2.5 有一个带头结点的单链表有一个带头结点的单链表head,其其ElemType类型为类型为char,设计一个算法使其元素递增设计一个算法使其元素递增有序。有序。 解解: :若原单链表中有一个或以上的数据结点若原单链表中有一个或以上的数据结点, ,先构造只含一个数据结点的有序表先构造只含一个数据结点的有序表( (只含一个数只含一个数据结点的单链表一定是有序表据结点的单链表一定是有序表) )。扫描原单链表。扫描原单链表余下的结点余下的结点 p(p(直到直到p=NULLp=NULL为止为止),),在有序表中通在有序表中通过比较找插入过比较找插入 p p的前驱结点的前驱结点 q,q,然后将然后将 p p插入到插入到 q q之后之后( (这里实际上采用的是直接插入排序方法这里实际上采用的是直接插入排序方法) )。 void Sort(LinkList &head) p=head-next;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 循环链表循环链表 循环链表循环链表是另一种形式的链式存储结构。它的是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是空特点是表中最后一个结点的指针域不再是空, ,而是而是指向表头结点指向表头结点, ,整个链表形成一个环。由此整个链表形成一个环。由此, ,从表中从表中任一结点出发均可找到链表中其他结点任一结点出发均可找到链表中其他结点。 带头结点的循环单链表和循环双链表的示意图带头结点的循环单链表和循环双链表的示意图 例例2.6 编写出判断带头结点的双向循环链表编写出判断带头结点的双向循环链表L是否是否对称相等的算法。对称相等的算法。 解解:p从左向右扫描从左向右扫描L,q从右向左扫描从右向左扫描L,若对应数若对应数据结点的据结点的data域不相等域不相等,则退出循环则退出循环,否则继续比较否则继续比较,直到直到p与与q相等或相等或p的下一个结点为的下一个结点为q为止。对应算法为止。对应算法如下如下:int Equeal(DLinkList L) int same=1; p=L-next; /p指向第一个数据结点指向第一个数据结点 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 静态链表静态链表 静态链表借用一维数组来描述线性链表。数组中静态链表借用一维数组来描述线性链表。数组中的一个分量表示一个结点的一个分量表示一个结点,同时使用同时使用游标游标(指示器指示器cur即即为伪指针为伪指针)代替指针以指示结点在数组中的相对位置。代替指针以指示结点在数组中的相对位置。数组中的第数组中的第0个分量可以看成头结点个分量可以看成头结点,其指针域指示静其指针域指示静态链表的第一个结点。态链表的第一个结点。 这种存储结构仍然需要预先分配一个较大空间这种存储结构仍然需要预先分配一个较大空间,但但是在进行线性表的插入和删除操作时不需要移动元素是在进行线性表的插入和删除操作时不需要移动元素,仅需要修改仅需要修改“指针指针”,因此仍然因此仍然具有链式存储结构的主具有链式存储结构的主要优点要优点。 1 0 张斌 2 1 刘丽 3 2 李英 4 3 陈华 5 4 王奇 6 5 董强 7 6 王萍 0 7 8 9 数据域数据域 游标域游标域 1 0 张斌 2 1 刘丽 3 2 李英 5 3 陈华 5 4 王奇 6 5 董强 7 6 王萍 0 7 8 9 数据域数据域 游标域游标域 删除“陈华”删除“陈华” （a） 1 0 张斌 2 1 刘丽 8 2 李英 5 3 4 王奇 6 5 董强 7 6 王萍 0 7 王华 3 8 9 数据域数据域 游标域游标域 在 “刘丽” 之后在 “刘丽” 之后插入“王华”插入“王华” （b） （c） 下图给出了一个静态链表的示例。图下图给出了一个静态链表的示例。图(a)是一个修改之前是一个修改之前的静态链表的静态链表,图图(b)是删除数据元素是删除数据元素“陈华陈华”之后的静态链表之后的静态链表,图图(c)插入数据元素插入数据元素“王华王华”之后的静态链表之后的静态链表,图中用阴影表示修图中用阴影表示修改的游标。改的游标。 顺序表和链表的比较顺序表和链表的比较1.1.基于时间的考虑基于时间的考虑（1 1）顺序表的是一种随机存取结构，而链表中的）顺序表的是一种随机存取结构，而链表中的结点都需要从头指针开始遍历链表。结点都需要从头指针开始遍历链表。（2 2）在链表中任何位置上插入与删除都只要修改）在链表中任何位置上插入与删除都只要修改指针，而顺序表需要移动表中将近一半的元素。指针，而顺序表需要移动表中将近一半的元素。尤其是对于结点信息量较大的表，开销很大。尤其是对于结点信息量较大的表，开销很大。（3 3）对于只进行访问型操作的线性表，宜采用顺）对于只进行访问型操作的线性表，宜采用顺序存储，对于加工型线性表，则考虑使用链表。序存储，对于加工型线性表，则考虑使用链表。顺序表和链表的比较顺序表和链表的比较2. 2. 基于空间的考虑基于空间的考虑（1 1）顺序表的存储空间在程序执行之间必须明确）顺序表的存储空间在程序执行之间必须明确规定它的存储规模，若表的变化较大，则存储规定它的存储规模，若表的变化较大，则存储规模难以确定。（估计过大则容易造成空间的规模难以确定。（估计过大则容易造成空间的浪费，估计太小，将使得存储扩充增多）浪费，估计太小，将使得存储扩充增多） （2 2）链表的存储空间动态分配，只要内存空间）链表的存储空间动态分配，只要内存空间尚有空闲，就不会溢出，适合于表长变化较大尚有空闲，就不会溢出，适合于表长变化较大的情况的情况 （3 3）链表存储空间利用率低于