零基础学数据结构线性表.pptx

3.1 线性表的定义及抽象数据类型3.1.1 线性表的逻辑结构 线性表是由n个类型相同的数据元素组成的有限序列，记为（a1，a2，ai-1，ai，ai+1，an）。其中，这里的数据元素可以是原子类型也可以是结构类型。线性表的数据元素存在着序偶关系，即数据元素之间具有一定的次序。在线性表中，数据元素ai-1在ai的前面，ai又在ai+1的前面，我们把ai-1称为ai的直接前驱元素，ai称为ai+1的直接前驱元素。ai称为ai-1的直接后继元素，ai+1称为ai的直接后继元素。线性表的逻辑结构如图3.1所示。第1页/共81页3.1 线性表的定义及抽象数据类型 我 们 学 过 的 英 文 单 词 就 是 简 单 的 线 性 表，例 如，“China”、“Science”、“Structure”。其中每一个英文字母就是一个数据元素，每个数据元素之间存在着唯一的顺序关系。如“China”中字母C后面是字母h，字母h后面是字母i。在较为复杂的线性表中，一个数据元素可以由若干个数据项组成，在表3.1所示的一个学校的教职工情况表中，数据元素也称为记录。表3.1 教职工情况表第2页/共81页3.1 线性表的定义及抽象数据类型3.1.2 线性表的抽象数据类型 线性表的抽象数据类型包括数据对象集合和基本操作集合。1数据对象集合 线性表的数据对象集合为a1，a2，an，元素类型为DataType。数据元素之间的关系是一对一的关系。除了第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。第3页/共81页3.1 线性表的定义及抽象数据类型2基本操作集合（1）InitList(&L)：初始化操作，建立一个空的线性表L。（2）ListEmpty(L)：若线性表L为空，返回1，否则返回0。（3）GetElem(L,i,&e)：返回线性表L的第i个位置元素值给e。（4）LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功返回该元素在表中的序号表示成功，否则，返回0表示失败。（5）InsertList(&L,i,e)：在线性表L中的第i个位置插入新元素e。（6）DeleteList(&L,i,&e)：删除线性表L中的第i个位置元素，并用e返回其值。（7）ListLength(L)：返回线性表L的元素个数。（8）ClearList(&L)：将线性表L清空。第4页/共81页3.2 线性表的顺序表示与实现 线性表的存储结构主要有两种：顺序存储结构和链式存储结构。3.2.1 线性表的顺序存储结构 线性表的顺序存储指的是将线性表中的各个元素依次存放在一组地址连续的存储单元中。线性表中第i+1个元素的存储位置LOC(ai+1)和第i个元素的存储位置LOC(ai)之间满足以下关系：LOC(ai+1)=LOC(ai)+m 第i个元素的存储位置与第一个元素a1的存储位置满足以下关系：LOC(ai)=LOC(a1)+(i-1)*m 其中，第一个元素的位置LOC(a1)称为起始地址或基地址。第5页/共81页3.2 线性表的顺序表示与实现 线性表的这种机内表示称为线性表的顺序存储结构或顺序映像，将这种方法存储的线性表称为顺序表。顺序表具有以下特征：逻辑上相邻的元素，在物理上也是相邻的。每一个数据元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比的常数（见图3.2）。只要确定了第一个元素的起始位置，线性表中的任一元素都可以随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构。第6页/共81页3.2 线性表的顺序表示与实现 顺序表的存储结构描述如下。#define ListSize 100 typedef struct DataType listListSize;int length;SeqList;其中，DataType表示数据元素类型，list用于存储线性表中的数据元素，length用来表示线性表中数据元素的个数，SeqList是结构体类型名。第7页/共81页3.2 线性表的顺序表示与实现3.2.2 顺序表的基本运算（1）初始化线性表。void InitList(SeqList*L)/*初始化线性表*/L-length=0;/*把线性表的长度置为0*/（2）判断线性表是否为空。int ListEmpty(SeqList L)/*判断线性表是否为空，线性表为空返回1，否则返回0*/if(L.length=0)/*线性表的长度若为0*/return 1;/*返回1*/else/*否则*/return 0;/*返回0*/第8页/共81页3.2 线性表的顺序表示与实现（3）按序号查找。先判断序号是否合法，如果合法，把对应位置的元素赋给e，并返回1表示查找成功；否则，返回-1表示查找失败。按序号查找的算法实现如下。int GetElem(SeqList L,int i,DataType*e)/*查找线性表中第i个元素。查找成功将该值返回给e，并返回1表示成功；否则返回-1表示失败。*/if(iL.length)/*判断该序号是否合法*/return-1;*e=L.listi-1;/*将第i个元素的值赋值给e*/return 1;第9页/共81页3.2 线性表的顺序表示与实现（4）按内容查找。从线性表中的第一个元素开始，依次与e比较，如果相等，返回该序号表示成功；否则，返回0表示查找失败。int LocateElem(SeqList L,DataType e)/*查找线性表中元素值为e的元素*/int i;for(i=0;iL.length;i+)/*从第一个元素开始与e进行比较*/if(L.listi=e)/*若存在与e值相等的元素*/return i+1;/*返回该元素在线性表中的序号*/return 0;/*否则，返回0*/第10页/共81页3.2 线性表的顺序表示与实现（5）插入操作。插入操作就是在线性表L中的第i个位置插入新元素e，使线性表a1，a2，ai-1，ai，an变为 a1，a2，ai-1，e，ai，an，线性表的长度也由n变成n+1。例如，在线性表9，12，6，15，20，10，4，22中，要在第5个元素之前插入1个元素28，需要将序号为8，7，6，5的元素依次向后移动1个位置，然后在第5号位置插入元素28，这样，线性表就变成了9，12，6，15，28，20，10，4，22，如图3.3所示。第11页/共81页3.2 线性表的顺序表示与实现插入元素的算法实现如下。int InsertList(SeqList*L,int i,DataType e)int j;if(iL-length+1)/*在插入元素前，判断插入位置是否合法*/printf(“插入位置i不合法！n”);return-1;else if(L-length=ListSize)/*在插入元素前，判断顺序表是否已经满，不能插入元素*/printf(“顺序表已满，不能插入元素。n”);return 0;else for(j=L-length;j=i;j-)/*将第i个位置以后的元素依次后移*/L-list j=L-list j-1;L-listi-1=e;/*插入元素到第i个位置*/L-length=L-length+1;/*将顺序表长增1*/return 1;第12页/共81页3.2 线性表的顺序表示与实现（6）删除第i个元素。删除第i个元素之后，线性表a1，a2，ai-1，ai，ai+1，an变为a1，a2，ai-1，ai+1，an，线性表的长度由n变成n-1。例如，如果要删除线性表9，12，6，15，28，20，10，4，22的第4个元素，需要依次将序号为5，6，7，8，9的元素向前移动一个位置，并将表长减1。如图3.4所示。第13页/共81页3.2 线性表的顺序表示与实现 删除第i个元素的算法实现如下。int DeleteList(SeqList*L,int i,DataType*e)int j;if(L-length=0)printf(“顺序表已空不能进行删除!n”);return 0;else if(iL-length)printf(“删除位置不合适!n”);return-1;第14页/共81页1.3 数据的逻辑结构与存储结构 else *e=L-listi-1;for(j=i;jlength-1;j+)L-listj-1=L-listj;L-length=L-length-1;return 1;第15页/共81页1.3 数据的逻辑结构与存储结构3.2.3 顺序表的实现算法分析在顺序表的实现算法中，除了按内容查找运算、插入和删除操作外，算法的时间复杂度均为O（1）。在按内容查找的算法中，若要查找的是第一个元素，则仅需要进行一次比较；若要查找的是最后一个元素，则需要比较n次才能找到该元素（设线性表的长度为n）。设Pi表示在第i个位置上找到与e相等的元素的概率，若在任何位置上找到元素的概率相等，即Pi=1/n。则查找元素需要的平均比较次数为因此，按内容查找的平均时间复杂度为O（n）。第16页/共81页1.3 数据的逻辑结构与存储结构 在顺序表中插入元素时，时间主要耗费在元素的移动上。若插入的位置在第一个位置，则需要移动元素的次数为n次；如果要将元素插入到倒数第2个位置，则仅需把最后一个元素向后移动；若要将元素插入到最后一个位置，即第n+1个位置，则不需要移动元素。设Pi表示在第i个位置上插入元素的概率，假设在任何位置上找到元素的概率相等，即Pi=1/（n+1）。则在顺序表的第i个位置插入元素时，需要移动元素的平均次数为 因此，插入操作的平均时间复杂度为O（n）。第17页/共81页1.3 数据的逻辑结构与存储结构 在顺序表的删除算法中，时间主要耗费仍在在元素的移动上。如果要删除的是第一个元素，则需要移动元素次数为n-1次；如果要删除的是最后一个元素，则需要移动0次。设Pi表示删除第i个位置上的元素的概率，假设在任何位置上找到元素的概率相等，即 Pi=1/n。则在顺序表中删除第i个元素时，需要移动元素的平均次 数为 因此，删除操作的平均时间复杂度为O（n）。第18页/共81页1.3 数据的逻辑结构与存储结构3.2.4 顺序表的优缺点 线性表的顺序存储结构的优缺点如下：优点：（1）无须为表示表中元素之间的关系而增加额外的存储空间。（2）可以快速地存取表中任一位置的元素。缺点：（1）插入和删除操作需要移动大量的元素。（2）使用前须事先分配好存储空间，当线性表长度变化较大时，难以确定存储空间的容量。分配空间过大会造成存储空间的巨大浪费，分配的空间过小，难以适应问题的需要。第19页/共81页1.3 数据的逻辑结构与存储结构3.2.5 顺序表应用举例 【例3_1】假设线性表LA和LB分别表示两个集合A和B，利用线性表的基本运算，实现新的集合A=AB，即扩大线性表LA，将存在于线性表B中且不存在于A中的元素插入到A中。【分析】只有依次从线性表LB中取出每个数据元素，并依次在线性表LA中进行查找该元素，如果LA中不存在该元素，则将该元素插入到LA中。第20页/共81页1.3 数据的逻辑结构与存储结构 【例3_2】编写一个算法，把一个顺序表分拆成两个部分，使顺序表中小于等于0的元素位于左端，大于0的元素位于右端。要求不占用额外的存储空间。例如，顺序表（-12，3，-6，-10，20，-7，9，-20）经过分拆调整后变为（-12，-20，-6，-10，-7，20，9，3）。【分析】设置两个指示器i和j，分别扫描顺序表中的元素，i和j分别从顺序表的左端和右端开始扫描。如果i遇到小于等于0的元素，略过不处理，继续向前扫描；如果遇到大于0的元素，暂停扫描。如果j遇到大于0的元素，略过不处理，继续向前扫描；如果遇到小于等于0的元素，暂停扫描。如果i和j都停下来，则交换i和j指向的元素。重复执行直到ij为止。第21页/共81页1.3 数据的逻辑结构与存储结构算法描述如下：void SplitSeqList(SeqList*L)/*将顺序表L分成两部分：左边是小于等于0的元素，右边是大于0的元素*/int i,j;/*定义两个指示器i和j*/DataType e;i=0,j=(*L).length-1;/*指示器i和j分别指示顺序表的左端和右端元素*/while(ilistilist j0)/*j遇到大于0的元素*/j-;/*略过*/if(ilisti;L-listi=L-list j;L-list j=e;第22页/共81页1.3 数据的逻辑结构与存储结构【例3_3】试设计一种表示任意长的整数的数据结构，计算任意给定的两个整数之和的算法。【分析】C语言提供的整数范围为-231231-1，超出这个范围的整数该如何表示呢？可以利用数组来存储，数组中的每一个元素存放一个数字，数组A和B分别存储两个整数，在将两个整数相加时，从低位到高位依次将对应位相加，如果和大于9，则将高位上加上进位1，并将和减去10后存储到当前位。具体实现代码如下所示。第23页/共81页1.3 数据的逻辑结构与存储结构 【考研真题】设将n（n1）个整数存放到一维数组R中，试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（0pnext=NULL;/*将单链表的头结点指针域置为空*/3.3 线性表的链式表示与实现第30页/共81页3.3 线性表的链式表示与实现（2）判断单链表是否为空。若单链表为空，返回1；否则，返回0。int ListEmpty(LinkList head)/*判断单链表是否为空*/*如果单链表头结点的指针域为空*/if(head-next=NULL)return 1;/*返回1*/else/*否则*/return 0;/*返回0*/第31页/共81页3.3 线性表的链式表示与实现（3）按序号查找操作。ListNode*Get(LinkList head,int i)ListNode*p;int j;if(ListEmpty(head)/*如果链表为空*/return NULL;/*返回NULL*/if(inext!=NULL&jnext;j+;if(j=i)/*找到第i个结点*/return p;/*返回指针p*/else/*否则*/return NULL;/*返回NULL*/第32页/共81页（4）按内容查找，查找元素值为e的结点。ListNode*LocateElem(LinkList head,DataType e)ListNode*p;p=head-next;/*指针p指向第一个结点*/while(p)if(p-data!=e)/*没有找到与e相等的元素*/p=p-next;/*继续找下一个元素*/else/*找到与e相等的元素*/break;/*退出循环*/return p;3.3 线性表的链式表示与实现第33页/共81页（5）定位操作。定位操作与按内容查找类似，只是定位操作返回的是该结点的序号。int LocatePos(LinkList head,DataType e)ListNode*p;int i;if(ListEmpty(head)/*在查找第i个元素之前，判断链表是否为空*/return 0;p=head-next;/*指针p指向第一个结点*/i=1;while(p)if(p-data=e)/*找到与e相等的元素*/return i;/*返回该序号*/else p=p-next;i+;if(!p)/*如果没有找到与e相等的元素*/return 0;/*返回0*/3.3 线性表的链式表示与实现第34页/共81页（6）在第i个位置插入元素e。先来看如何在单链表中插入一个结点。假设存储元素e的结点为p，要将p指向的结点插入到pre和pre-next之间，根本不需要移动其他结点，只需要让p指向结点的指针和pre指向结点的指针做一点改变即可。即先把*pre的直接后继结点变成*p的直接后继结点，然后把*p变成*pre的直接后继结点，如图3.14所示，代码如下：p-next=pre-next;pre-next=p;3.3 线性表的链式表示与实现第35页/共81页 注意：插入结点的两行代码不能颠倒顺序。如果先进行pre-next=p，后进行p-next=pre-next操作，则第一条代码就会覆盖掉pre-next的地址，pre-next的地址就变成了p的地址，执行p-next=pre-next就等于执行p-next=p，这样pre-next就与上级断开了链接，造成尴尬的局面。如图3.15所示。3.3 线性表的链式表示与实现第36页/共81页 如果要在单链表的第i个位置插入一个新元素e，首先需要在链表中找到其直接前驱结点，即第i-1个结点，并由指针pre指向该结点，如图3.16所示。然后申请一个新结点空间，由p指向该结点，将值e赋值给p指向结点的数据域。最后修改*p和*pre结点的指针域，如图3.17所示。这样就完成了结点的插入操作。3.3 线性表的链式表示与实现第37页/共81页在单链表的第i个位置插入新数据元素e的算法实现如下。int InsertList(LinkList head,int i,DataType e)ListNode*pre,*p;int j;pre=head;/*指针p指向头结点*/j=0;while(pre-next!=NULL&jnext;j+;3.3 线性表的链式表示与实现第38页/共81页 if(j!=i-1)/*如果没找到，说明插入位置错误*/printf(“插入位置错误！”);return 0;/*新生成一个结点，并将e赋值给该结点的数据域*/if(p=(ListNode*)malloc(sizeof(ListNode)=NULL)exit(-1);p-data=e;/*插入结点操作*/p-next=pre-next;pre-next=p;return 1;3.3 线性表的链式表示与实现第39页/共81页 （7）删除第i个结点。先来看下如何删除链表的第i个结点。假设p指向第i个结点，要将*p结点删除，只需要将它的直接前驱结点的指针绕过，使其直接指向它的直接后继结点即可。如图3.18所示。3.3 线性表的链式表示与实现第40页/共81页 将单链表中第i个结点删除可分为3步：（1）找到第i个结点的直接前驱结点，即第i-1个结点，并用pre指向该结点，p指向其直接后继结点，即第i个结点，如图3.19所示；（2）将*p结点的数据域赋值给e；（3）删除第i个结点，即pre-next=p-next，并释放*p结点的内存空间。删除过程如图3.20所示。3.3 线性表的链式表示与实现第41页/共81页 删除第i个结点的算法实现如下。int DeleteList(LinkList head,int i,DataType*e)/*删除单链表中的第i个位置的结点。删除成功返回1，失败返回0*/ListNode*pre,*p;int j;pre=head;j=0;while(pre-next!=NULL&pre-next-next!=NULL&jnext;j+;3.3 线性表的链式表示与实现第42页/共81页 if(j!=i-1)/*如果没找到要删除的结点位置，说明删除位置有误*/printf(“删除位置有误”);return 0;/*指针p指向单链表中的第i个结点，并将该结点的数据域值赋值给e*/p=pre-next;*e=p-data;/*将前驱结点的指针域指向要删除结点的下一个结点，也就是将p指向的结点与单链表断开*/pre-next=p-next;free(p);/*释放p指向的结点*/return 1;3.3 线性表的链式表示与实现第43页/共81页（8）求表长操作。int ListLength(LinkList head)ListNode*p;int count=0;p=head;while(p-next!=NULL)p=p-next;count+;return count;3.3 线性表的链式表示与实现第44页/共81页（9）销毁链表操作。void DestroyList(LinkList head)ListNode*p,*q;p=head;while(p!=NULL)q=p;p=p-next;free(q);3.3 线性表的链式表示与实现第45页/共81页3.3 线性表的链式表示与实现3.3.3 单链表存储结构与顺序存储结构的优缺点 1存储分配方式 顺序存储结构用一组连续的存储单元依次存储线性表的数据元素。单链表采用链式存储结构，用一组任意的存储单元存放线性表的数据元素。2时间性能 采用顺序存储结构时，查找操作时间复杂度为O（1），插入和删除操作需要移动平均一半的数据元素，时间复杂度为O（n）。采用单链表存储结构时，查找操作时间复杂度为O（n），插入和删除操作不需要大量移动元素，时间复杂度仅为O(1)。3空间性能 采用顺序存储结构时，需要预先分配存储空间，分配的空间过大会造成浪费，分配的过小不能满足问题需要。采用单链表存储结构时，可根据需要临时分配，不需要估计问题的规模大小。第46页/共81页3.3 线性表的链式表示与实现3.3.4 单链表应用举例【例3_4】已知两个单链表A和B，其中的元素都是非递减排列，编写算法将单链表A和B合并得到一个递减有序的单链表C（值相同的元素只保留一个），并要求利用原链表结点空间。【分析】此题为单链表合并问题。利用头插法建立单链表，使先插入元素值小的结点在链表末尾，后插入元素值大的结点在链表表头。初始时，单链表C为空（插入的是C的第一个结点），将单链表A和B中较小的元素值结点插入到C中；单链表C不为空时，比较C和将插入结点的元素值大小，值不同时插入到C中，值相同时，释放该结点。当A和B中有一个链表为空时，将剩下的结点依次插入到C中。第47页/共81页3.3 线性表的链式表示与实现【例3_5】利用单链表的基本运算，求两个集合的交集。【分析】假设A和B是两个带头结点的单链表，分别表示两个给定的集合A和B，求C=AB。先将单链表A和B分别从小到大排序，然后依次比较两个单链表中的元素值大小，pa指向A中当前比较的结点，pb指向B中指向的当前结点，如果pa-datadata，则pa指向A中下一个结点；如果pa-datapb-data，则pb指向B中下一个结点；如果pa-data=pb-data，则将当前结点插入到C中。第48页/共81页3.3 线性表的链式表示与实现 【考研真题】已经一个带有表头结点的单链表，结点结构为 假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k各位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，返回0。要求：（1）描述算法的基本设计思想。（2）描述算法的详细实现步骤。（3）根据设计思想和实现步骤，采用程序设计语言描述算法.第49页/共81页3.3 线性表的链式表示与实现【分析】这是2009年考研试题，主要考察大家对链表的掌握程度，这个题目灵活性比较大，利用一般的思维方式不容易实现。（1）算法的基本思想：定义两个指针p和q，初始时均指向头结点的下一个结点。p指针沿着链表移动，当p指针移动到第k个结点时，q指针与p指针同步移动，当p指针移动到链表表尾结点时，q指针所指向的结点即为倒数第k个结点。（2）算法的详细步骤如下：a.令count=0，p和q指向链表的第一个结点。b.若p为空，则转向e执行。c.若count等于k，则q指向下一个结点；否则，令count+。d.令p指向下一个结点，转向b执行。e.若count等于k，则查找成功，输出结点的data域的值，并返回1；否则，查找失败，返回0。第50页/共81页3.4 循环单链表3.4.1 循环链表的链式存储 循环单链表（circular linked list）是一种首尾相连的单链表。将单链表的最后一个结点的指针域由空指针改为指向头结点或第一个结点，整个链表就形成一个环，我们称这样的单链表称为循环单链表。从表中任何一个结点出发均可找到表中其他结点。与单链表类似，循环单链表也可分为带头结点结构和不带头结点结构两种。对于不带头结点的循环单链表，当表不为空时，最后一个结点的指针域指向头结点。如图3.23所示。对于带头结点的循环单链表，当表为空时，头结点的指针域指向头结点本身。如图3.24所示。第51页/共81页3.4 循环单链表 循环单链表与单链表在结构、类型定义及实现方法上都是一样的，唯一的区别仅在于判断链表是否为空的条件上。判断单链表为空的条件是head-next=NULL，判断循环单链表为空的条件是head-next=head。在单链表中，访问第一个结点的时间复杂度为O(1)，而访问最后一个结点则需要将整个单链表扫描一遍，故时间复杂度为O(n)。对于循环单链表，只需设置一个尾指针（利用rear指向循环单链表的最后一个结点）而不设置头指针，就可以用直接访问最后一个结点，时间复杂度为O(1)。访问第一个结点即rear-next-next，时间复杂度也为O(1)。如图3.25所示。第52页/共81页3.4 循环单链表 将循环单链表设置尾指针，还可以使有些操作变得简单，例如，要将如图3.26所示的两个循环单链表（尾指针分别为LA和LB）合并成一个链表，只需要将一个表的表尾和另一个表的表头连接即可。如图3.27所示。第53页/共81页3.4 循环单链表 将循环单链表合并为一个循环单链表只需要以下3步操作：（1）将LA的表尾与LB的第一个结点相连：LA-next=LB-next-next；（2）释放LB的头结点：free(LB-next)；（3）将LB的表尾与LA的表头相连：LB-next=LA-next。第54页/共81页3.4 循环单链表合并两个循环单链表的算法实现如下：LinkList Link(LinkList head1,LinkList head2)/*将两个链表head1和head2连接在一起形成一个循环链表*/ListNode*p,*q;p=head1;while(p-next!=head1)/*指针p指向链表的最后一个结点*/p=p-next;q=head2;while(q-next!=head2)/*指针q指向链表的最后一个结点*/q=q-next;p-next=head2;/*将第一个链表的尾端连接到第二个链表的第一个结点*/q-next=head1;/*将第二个链表的尾端连接到第一个链表的第一个结点*/return head1;第55页/共81页3.4 循环单链表3.4.2 循环单链表应用举例【例3_6】已知一个带哨兵结点h的循环单链表中的数据元素含有整数和负数，试编写一个算法，构造两个循环单链表，使一个循环单链表中只含正数，另一个循环单链表只含负数。【分析】初始时，先创建两个空的单链表ha和hb，然后依次查看指针p指向的结点元素值，如果值为正数，则将其插入到ha中，否则，将其插入到hb中。最后，使最后一个结点的指针域指向头结点，构成循环单链表。第56页/共81页3.5 双向链表3.5.1 双向链表的存储结构 顾名思义，双向链表（double linked list）就是链表中的每个结点有两个指针域：一个指向直接前驱结点，另一个指向直接后继结点。双向链表的每个结点有3个域：data域、prior域和next域。双向链表的结点结构如图3.29所示。第57页/共81页3.5 双向链表 与单链表类似，也可以为双向链表增加一个头结点，这样使某些操作更加方便。双向链表也有循环结构，称为双向循环链表（double circular linked list）。带头结点的双向循环链表如图3.30所示。双向循环链表为空的情况如图3.31所示，判断带头结点的双向循环链表为空的条件是head-prior=head或head-next=head。第58页/共81页3.5 双向链表 在双向链表中，因为每个结点既有前驱结点的指针域又有后继结点的指针域，所以查找结点非常方便。对于带头结点的双向链表中，如果链表为空，则有p=p-prior-next=p-next-prior。双向链表的结点存储结构描述如下：typedef struct Node DataType data;struct Node*prior;struct Node*next;DListNode,*DLinkList;第59页/共81页3.5 双向链表3.5.2 双向链表的插入和删除操作 1在第i个位置插入元素值为e的结点 首先找到第i个结点，用p指向该结点。再申请一个新结点，由s指向该结点，将e放入到数据域。然后修改p和s指向的结点的指针域：修改s的prior域，使其指向p的直接前驱结点，即s-prior=p-prior；将p的直接前驱结点的next域，使其指向s指向的结点，即p-prior-next=s；修改s的next域，使其指向p指向的结点，即s-next=p；修改p的prior域，使其指向s指向的结点，即p-prior=s。插入操作指针修改情况如图3.32所示。第60页/共81页3.5 双向链表 2删除第i个结点 首先找到第i个结点，用p指向该结点。然后修改p指向的结点的直接前驱结点和直接后继结点的指针域，从而将p与链表断开。将p指向的结点与链表断开需要两步：第1步，修改p的前驱结点的next域，使其指向p的直接后继结点，即p-prior-next=p-next；第2步，修改p的直接后继结点的prior域，使其指向p的直接前驱结点，即p-next-prior=p-prior。删除操作指针修改情况如图3.33所示。第61页/共81页3.5 双向链表3.5.3 双向链表应用举例【例3_7】约瑟夫问题。有n个小朋友，编号分别为1，2，n，按编号围成一个圆圈，他们按顺时针方向从编号为k的人由1开始报数，报数为m的人出列，他的下一个人重新从1开始报数，数到m的人出列，照这样重复下去，直到所有的人都出列。编写一个算法，输入n、k和m，按照出列顺序输出编号。第62页/共81页3.6 静态链表3.6.1 静态链表的存储结构 可利用一维数组实现静态链表，其类型说明如下：#define ListSize 100 typedef struct DataType data;int cur;SListNode;typedef struct SListNode listListSize;int av;SLinkList;第63页/共81页3.6 静态链表 在静态链表的类型定义中，数组的一个分量表示一个结点，同时用游标（指示器cur）代替指针指示结点在数组中的相对位置。数组的第0分量可看成是头结点，其指针域指示链表的第一个结点。表中的最后一个结点的指针域为0，指向头结点，这样就构成一个静态循环链表。第64页/共81页3.6 静态链表 SListNode是一个结点类型，SLinkList是一个静态链表类型，av是备用链表的指针，即av指向静态链表中一个未使用的位置。这种描述方法便于在不设“指针”类型的高级程序设计语言中使用链表结构。例如，线性表(Yang,Zheng,Feng,Xu,Wu,Wang,Geng)的静态链表存储情况如图3.35所示。第65页/共81页3.6 静态链表3.6.2 静态链表的基本运算（1）初始化静态链表。只需要让静态链表的游标cur指向下一个结点，并将链表的最后一个结点的cur域置为0。void InitSList(SLinkList*L)int i;for(i=0;iListSize;i+)(*L).listi.cur=i+1;(*L).listListSize-1.cur=0;(*L).av=1;第66页/共81页3.6 静态链表（2）分配结点。从备用链表中取出一个结点空间，分配给要插入链表中的元素，并返回要插入结点的位置。分配结点的算法实现如下。int AssignNode(SLinkList L)/*从备用链表中取下一个结点空间，分配给要插入链表中的元素*/int i;i=L.av;L.av=L.listi.cur;return i;第67页/共81页3.6 静态链表（3）回收结点。结点用过之后，要将空闲结点回收，以便其他结点使用，使其称为备用链表的空间。回收结点的算法实现如下。void FreeNode(SLinkList L,int pos)/*将空闲结点插入到备用链表*/L.listpos.cur=L.av;L.av=pos;第68页/共81页3.6 静态链表（4）插入操作。例如，在图3.36的静态链表中的第5个元素后插入元素“Hao”，具体方法：从备用链表中取出一个空闲结点，即k=L.av，图3.36中为数组编号为8的结点；使备用链表指向下一个有用结点，修改备用链表指针，使其指向下一个结点，即L.av=L.listk.cur；把元素“Hao”放在新空闲结点中，即(*L).listk.data=e；将新结点插入到对应的位置，这需要先找到前一个结点，让前一个结点的cur域指向新结点，然后让新结点的cur域指向下一个结点，图3.36中为L.list5.cur=L.list8.cur，L.list8.cur=6。第69页/共81页3.6 静态链表插入操作的算法实现如下。void InsertSList(SLinkList*L,int i,DataType e)/*插入操作*/int j,k,x;k=(*L).av;(*L).av=(*L).listk.cur;(*L).listk.data=e;j=(*L).list0.cur;for(x=1;xi-1;x+)j=(*L).list j.cur;(*L).listk.cur=(*L).list j.cur;(*L).list j.cur=k;第70页/共81页3.6 静态链表 （5）删除操作。将静态链表中第i个位置的元素删除分为两种情况：（1）如果删除的是第1个结点，则将头结点的cur域指向第2个结点，代码如下：k=(*L).list0.cur;(*L).list0.cur=(*L).listk.cur;（2）如果删除的不是第1个结点，则先找到第i-1个元素的位置，修改cur域使其指向第i1个元素，例如要删除图3.37所示的静态链表中的第3个元素，需要根据游标找到第2个元素，将其cur域修改为第4个元素的位置，即L.list2.cur=L.list3.cur。第71页/共81页3.6 静态链表删除第3个结点的操作如图3.37所示。第72页/共81页3.6 静态链表删除操作的实现代码如下。void DeleteSList(SLinkList*L,int i,DataType*e)/*删除操作*/int j,k,x;if(i=1)k=(*L).list0.cur;(*L).list0.cur=(*L).listk.cur;elsej=(*L).list0.cur;for(x=1;xnext；若和等于k，则求出两个多项式系数的乘积，并将其存入新结点中。若和大于k，则pa=pa-next。这样就可以得到多项式A(x)和B(x)的乘积C(x)。算法结束后重新将链表B逆置，将链表B恢复原样。第79页/共81页3.8 小结 线性表中的元素之间是一对一的关系。线性表有两种存储方式：顺序存储和链式存储。顺序表中数据元素的逻辑顺序与物理顺序一致，因此可以随机存取。链表又分为单链表和双向链表，这两种链表又可构成单循环链表、双向循环链表。单链表只有一个指针域，指针域指向直接后继结点。顺序表的优点是可以随机存取任意一个元素，算法实现较为简单，存储空间利用率高，缺点是需要预先分配存储空间，存储规模不好确定，插入和删除操作需要移动大量元素。链表的优点是不需要事先确定存储空间的大小，插入和删除元素不需要移动大量元素，缺点是只能从第一个结点开始顺序存取元素，存储单元利用率不高，算法实现较为复杂。第80页/共81页感谢您的观看！第81页/共81页