第三章 线性表.ppt

1、第二部分 简单数据结构,第三章 线性表,线性结构的特点是：,在数据元素的非空有限集合中，存在唯一的首元素和唯一的尾元素，首元素无直接前驱，尾元素无直接后继，集合中其它每个数据元素均有唯一的直接前驱和唯一的直接后继。,线性表是线性结构的典型代表，是一种最基本、最常用的数据结构，数据元素之间仅具有单一的前驱和后继关系。 线性表有广泛的应用，也是其它数据结构的基础。 介绍线性表的定义，两种存储结构顺序存储结构与链式存储结构，线性表的相关操作。,3.1 线性表的定义,线性表是n个类型相同的数据元素的有限序列，数据元素之间是一对一的关系，即每个数据元素最多有一个直接前驱和一个直接后继。 图3.1 n个元

2、素构成的线性表,例3.1 英文字母表(A, B, , Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，每个元素之间存在唯一的顺序关系，如在英文字母表中字母B的前面是字母A，而字母B后面是字母C。,在较为复杂的线性表中，数据元素可由若干数据项组成 表3-1 学生电话号码簿 学生姓名 所在院系 电话号码 张 平 材料学院 6321567 李 红 计算机学院 6234775 王建平 机电学院 6398786,线性表定义如下：,线性表是由n (n0)个类型相同的数据元素a1,a2,ai-1,ai,ai+1, ,an组成的有限序列，记做： L=（ a1,a2,ai-1,ai,ai+1, ,

3、an ） 其中，数据元素ai (1in)只是一个抽象的符号，其具体含义在不同情况下可以不同，它既可以是原子类型，也可以是结构类型，但同一线性表中的数据元素必须属于同一数据对象。,线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（ a1,a2,ai-1,ai,ai+1, ,an ），表中ai-1 领先于ai，称ai-1 是ai的直接前驱，而称ai 是ai-1的直接后继。 除了第一个元素a1外，每个元素ai有且仅有一个被称为其直接前驱的结点ai-1，除了最后一个元素an外，每个元素ai有且仅有一个被称为其直接后继的结点ai+1。 线性表中元素的个数n被定义为线性表的长度，当n=0时，则线

4、性表为空表。,线性表的特点可概括如下：,同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。 有穷性：线性表由有限个数据元素组成，表中数据元素的个数就是表的长度。 有序性：线性表中相邻数据元素之间存在着序偶关系。 线性表的两类存储结构： 顺序存储结构（顺序表） ；链式存储结构（链表）。,为了在计算机中存储线性表，进而实现线性表的相关操作，至少要保存两类信息： 1）线性表中的数据元素； 2）线性表中数据元素的顺序关系； 在计算机内部存放线性表，主要有两种基本的存储结构：顺序存储结构和链式存储结构。 此外还有一种叫做静态链表的存储结构，它是用顺序存储结构的存储方式模拟实现的一种链式存

5、储结构。,3.3 线性表的顺序存储结构及实现,1 线性表的顺序存储结构 线性表的顺序存储结构是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，这样就可以通过数据元素物理存储位置的相邻关系来反映数据元素之间逻辑上的相邻关系。 通常，将采用顺序存储结构的线性表称为顺序表或向量。,假设线性表中有n个元素，每个元素占K个单元，第一个元素的地址为Loc(a1)，则可以通过如下公式计算出第i个元素的地址Loc(ai)： Loc(ai) =Loc(a1)+(i-1)K 其中：Loc(a1) 称为线性表的起始地址或基地址。,知道线性表中第一

6、个元素的存储地址(即基地址)和每个元素所占存储单元的多少，就可计算出线性表中任意一个数据元素的存储地址，从而实现对顺序表中任意数据元素的随机访问 线性表的顺序存储结构是一种随机存取的存储结构。,在程序设计语言中，一维数组在内存中占用的存储空间是一组连续的存储区域 用一维数组来表示顺序表的数据存储区域 考虑到线性表的插入和删除操作，线性表的长度是可变的，因此，需要设计足够大的数组容量，可用一维数组dataMaxSize来表示，其中MaxSize是一个根据实际问题定义的足够大整数，线性表L中的数据从data0开始依次顺序存放 需要定义一个整型变量length表示线性表中实际元素的个数。,线性表的顺

7、序存储结构可用C语言描述如下：,typedef int DataType /* 定义DataType类型为int */ #define MaxSize 100 /*100仅是示例数据，表示线性表的最大长度*/ typedef struct DataType dataMaxSize； /* 将线性表定义为一个一维数组*/ intlength; /*线性表中实际元素的个数，空表时置为0*/ SeqList； 说明：编写程序时，需要注意区分元素的序号和数组的下标，如a1的序号为1，而其对应的数组下标为0。 要将L定义为SeqList类型的变量，可用说明语句：SeqList L； 若将L定义为指向Se

8、qList类型的指针，则用说明语句：SeqList * L。,线性表的运算,线性表是一种非常灵活的数据结构，对线性表中的元素，不仅可以进行访问，还可以进行插入和删除等操作，下面简单列出线性表的一些基本操作。 设L=（a1,a2,ai-1,ai,ai+1,an）是一线性表，则其基本操作有： （1）InitList(L): 线性表初始化 操作结果是：将L初始化为空表。 （2）DestroyList(L)：线性表销毁 操作结果是：将已存在的线性表L销毁，释放其占据的内存空间。 （3）ClearList(L)：清空线性表 操作结果是：将已存在的线性表L置为空表。,（4）EmptyList(L)：判读线

9、性表是否为空 操作结果是：若线性表L为空表则返回真，否则返回假。 （5）ListLength(L)：求线性表长度 操作结果是：若线性表L为空表则返回0，否则返回表中的元素个数。 （6）Locate(L,e)：按值查找，e为给定的一个数据元素 操作结果是：若线性表L中存在数据元素e，则返回数据元素e在L中首次出现的位置，查找成功；否则线性表L中不存在数据元素e，返回一特殊值表示查找失败。,（7）GetData(L,i)：按序号查找线性表的第i个元素 操作结果是：若线性表L存在，且i值合法，即(1iListLength(L)，则返回线性表L中第i个元素；否则给出错误提示。 （8）InsList(L

10、,i,e)：插入操作 操作结果是：若线性表L已存在，e为合法数据元素且1iListLength(L)+1，则在L中第i个位置之前插入新的数据元素e，L的长度加1。 （9）DelList(L,i,e)：删除操作 操作结果是：若线性表L已存在且非空， 1iListLength(L)，则删除L的第i个数据元素，并用e返回其值，L的长度减1。,顺序表的实现,在线性表的顺序存储结构上实现线性表的一些基本运算。 1. 查找操作 线性表的查找操作有两种： 1)按序号查找Data(L,i) 在线性表L中查找第i个数据元素，首先需判断给定的序号i是否合法，即1iListLength(L)，i合法时则返回线性表中

11、的第i个元素，否则给出错误提示。,按序号查找算法描述如下：,DataType GetData(SeqList L, int i) /* 查找线性表中的第i个元素*/ If (iL.length) printf(“position i errorn”); else return L.datai-1;/* 返回表中第i个元素L.datai-1 */ 算法分析：由于顺序表是一种随机存取的存储结构，故按序号查找很容易实现，查找成功时，算法的时间复杂度为,2)按值查找Locate(L,e) 在线性表L中查找与给定值e相等的数据元素， 若在线性表L中找到与e相等的元素，则返回该元素在表中的序号； 若找不到

12、，则返回一个特殊标志，如 -1，表示查找失败。 可采用顺序查找法实现，即从第一个元素开始，依次将表中元素与e相比较，若相等，则查找成功，返回该元素在表中的序号；若e与表中的所有元素都不相等，则查找失败，返回“-1”。 有无其它方法查找?思考!,按值查找算法描述如下：,intLocate(SeqList L, DataType e) /*在顺序表L中查找与e相等的元素，若 L.datai=e,则找到该元素，并返回i+1，若找不到，则返回“-1”*/ i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while (i=L.length-1) /*若没找到，则返回空序号-1*/

13、,算法分析：,按值查找时，需要将待查元素e和线性表中的元素依次作比较，而比较次数跟元素的位置有关，若e和第i个元素相等，则比较次数为i（其中1iListLength(L)），查找不成功时，比较次数为L.length。 算法的事件复杂度为,2.插入操作,线性表的插入操作是指在表的第i (1in+1)个位置，插入一个新元素e， 使长度为n的线性表 (a1,ai-1,ai,an) 变成长度为n+1的线性表（ a1,ai-1, e,ai,an ）。 数据元素ai-1和ai之间的逻辑关系发生了变化。 而用顺序表作为线性表的存储结构时，要求逻辑上相邻的数据元素在物理位置上也是相邻的。 插入时若i=n+1，

14、即在线性表的末尾插入新元素，则只要n+1MaxSize，直接插入即可； 当1in时，都必须移动元素才能反映插入后逻辑关系的变化。,如果在第i(1in)个位置插入，就必须把第i个到第n个元素之间共n-i+1个元素依次向后移动一个位置，再将新元素e插入到第i个位置，线性表的长度变为n+1。 注意区分元素的序号和数组的下标,顺序表中插入元素前后的状况,顺序表的插入算法描述如下：,#define OK 1 #define ERROR 0 int InsList(SeqList L, int i, DataType e) /*在顺序表L中第i个数据元素之前插入一个元素e,使表长L.length+1*/

15、/*i的合法取值范围是 1iL.length */ int k; if (iL.length) /*首先判断插入位置是否合法*/ printf(“插入位置i值不合法”)； return(ERROR); ,If (L.length=MaxSize) printf(“表已满无法插入”)； return(ERROR); for (k=L.length-1; k=i-1; k-) /*为插入元素而移动位置*/ L.datak+1=L.datak; L.datai-1=e; /*在C语言数组中，第i个元素的下标为i-1*/ L.length+; return(OK); ,算法分析：,上述算法可看出，当i

16、=L.length时，语句L.datak+1=L.datak将不会执行，因为循环的终值大于初值，此时不需要移动元素，可直接在表尾插入e。 当i= 1时，语句L.datak+1=L.datak需执行n次，即将表中已存在的n个元素依次后移一个位置才能将e插入。 语句L.datak+1=L.datak的频度与插入位置i有关,设Pi为在第i个元素之前插入元素的概率，并假设在任何位置上插入元素的概率相等，即 设 为 在长度为n的表中插入一元素所需移动元素的平均次数，则 顺序表的插入操作时间复杂度为,3. 删除操作,线性表的删除运算是指将表的第i(1in)个元素删去，使长度为n的线性表 (a1,ai-1,

17、 ai, ai+1,an)，变成长度为n-1的线性表(a1,ai-1, ai, ai+1,an )。 此时数据元素ai-1,ai和ai+1之间的逻辑关系发生变化，为了在存储结构上反映这个变化，需要移动线性表中的元素，将ai+1,an 这些元素依次向前移动一个位置，并将线性表的长度-1,顺序表删除前、后的状况,顺序表的删除算法描述如下：,int DelList(SeqList L,int i, DataType *e) /*在顺序表L中删除第i个数据元素，并用指针参数e返回其值*/ /*i的合法取值为1iL.length */ int k; if(iL.length) printf(“删除位置不

18、合法！”)； return(ERROR); *e= L.datai-1; /* 将删除的元素存放到e所指向的变量中*/ for(k=i;i=L.length-1;k+) L.datak-1= L.datak; /*将后面的元素依次前移*/ L.length-; return(OK); ,算法分析：,与插入操作类似，在顺序表上实现删除操作也必须移动元素，这样才能反映出元素间逻辑关系的变化。 若i=L.length，则移位语句L.datak-1= L.datak不执行，因为循环变量的初值大于终值，此时不需要移动元素，仅将表长度减1即可。 删除算法中移位语句L.datak-1= L.datak的执行

19、频度也与删除位置i有关。,设Qi为删除第i个元素的概率，并假设在任何位置上删除的概率相等，即 删除任意一个元素所需移动元素的平均次数Edel为： 故顺序表的删除操作其时间复杂度为,例3-1 有两个顺序表La和Lb，其元素均为非递减有序排列，试编写一个算法，将它们合并成一个顺序表Lc，要求Lc也是非递减有序排列。 例如La=(3,5,7,9), Lb=(1,4,6,10,11), 则Lc=(1,3,4,5, 6,7,9,10,11)。,算法描述：,设表Lc是一个空表，为使Lc也是非递减有序排列，可设两个指针i、j分别指向表La和Lb中的元素 若La.dataiLb.dataj，则当前先将Lb.d

20、ataj插入到表Lc中 若La.dataiLb.dataj ，则先将La.datai插入到表Lc中 如此进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表Lc中。,void merge(SeqList La, SeqList Lb, SeqList Lc) int i, j, k, l; i=0; j=0; k=0; while (iLa.length ,while (iLa.length) /*当表LA有剩余元素时，则将表LA余下的元素赋给表LC*/ Lc.datak= La.datai; i+; k+; while (jLb.length) /*当表LB有剩余元

21、素时，则将表LB余下的元素赋给表LC*/ Lc.datak= Lb.dataj; j+; k+; Lc.length=La.length+Lb.length; ,算法分析：,由于两个待合并的表La、Lb本身就是有序表，元素经过相互比较按序插入在表Lc的末尾，故插入时不需要移动元素，所以整个合并算法的时间复杂度,线性表的顺序存储结构具有以下优点：,1）在顺序表中，逻辑关系上相邻的元素存储在相邻的物理位置，故不需要为表示元素间的逻辑关系而增加额外的存储空间 2）在顺序表中可方便地随机存取任意元素。,线性表的顺序存储结构的缺点是：,1）插入或删除操作时需要移动大量的元素，效率较低。 2）顺序表的容量

22、难以确定。 顺序表需要预先静态分配存储空间，因此当表长变化较大时，难以确定合适的存储规模。 若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分利用； 若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。,3.4 线性表的链式存储结构及实现,在线性表的实际应用，如果需要进行大量的插入或删除操作，则采用线性表的链式存储结构较为合适，它不需要使用地址连续的存储空间，使用“链”来表示元素之间的逻辑关系，插入或删除操作不需要移动数据元素。 线性表的链式存储结构通常称为链表。,单链表,链表是用一组任意的存储单元来存放线性表的元素，这组存储单元可以是连续的，也

23、可以是不连续的，甚至是零散分布在内存的任何位置上。 链表中元素的逻辑次序和物理次序不一定相同,为表示元素间的逻辑关系，必须在存储线性表的每个数据元素值的同时，还要存储指示其后继元素的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node） 它包括两个域： 数据域data用来存储结点的值 指针域link用来存储数据元素的直接后继的地址（或位置）,单链表的结点结构,链表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起。 由于链表的每个结点只有一个指针域，故将这种链表又称为单链表。,由于单链表中每个结点的存储地址是存放在其前趋结点的指针域link中的，而第一个结点无前趋，所

24、以设一个头指针H指向第一个结点。 由于表中最后一个结点没有直接后继，则指定线性表中最后一个结点的指针域为“空”（NULL）。 这样对于整个链表的存取必须从头指针开始。,线性表（a1,a2,a3,a4）的单链表存储结构,整个链表的存取需从头指针head开始进行，依次顺着每个结点的指针域找到线性表的各个元素,单链表的逻辑状态,通常我们使用链表时，只关心链表中结点间的逻辑顺序，并不关心每个结点的实际存储位置，故通常是用箭头来表示链域中的指针，于是链表就可以更直观地画成用箭头链接起来的结点序列。,有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点，头结点的数据域可以存储一些关于线性表的长

25、度的附加信息，也可以什么都不存； 而头结点的指针域存储指向第一个结点的指针（即第一个结点的存储位置）。 此时带头结点单链表的头指针就不再指向表中第一个结点而是指向头结点。 如果线性表为空表，则头结点的指针域为“空”,单链表可以由头指针唯一确定 单链表的存储结构描述如下： typedef struct Node / * 结点类型定义 * / DataType data； struct Node * Link； Node, *LinkList； /* LinkList为结构指针类型*/,假设head是Linklist型的变量，则head是一个结构指针，即单链表的头指针，它指向表中第一个结点（对于带

26、头结点的单链表，则指向单链表的头结点） 若head=NULL（对于带头结点的单链表为head-link=NULL），则表示单链表为一个空表，其长度为0。 若不是空表，则可以通过头指针访问表中结点，找到要访问的所有结点的数据信息。 对于带头结点的单链表head，定义一个结点类型的指针p,让p=head-link使其指向单链表中的第一个结点a1，即p-data=a1，而p-link-data=a2；依此类推。,单链表的基本操作,下面将讨论用单链表作存储结构时，如何实现线性表的几种基本操作。 首先讨论如何建立单链表。 1）建立单链表 链表不同于顺序表，它是一种动态管理的存储结构，链表中的每个结点占用

27、的存储空间不是预先分配，而是系统根据需要动态申请的。,假设线性表中的元素是若干个正整数，逐个输入这些数据,作为结点的值，并以“-1”作为输入结束标志。 动态建立单链表有如下两种方式,（1）在链表的头部插入结点建立链表,从一个空表开始，重复读入数据，生成新结点，将读入的数据存放到新结点的数据域中，然后再将新结点插入到当前链表的头结点之后，直至读入结束标志为止。,在链表的头部插入结点建立单链表,在链表的头部插入结点建立单链表的算法描述如下：,Linklist * Create_List(void) LinkList*head; Node *p; int x; int flag=1;/* 设置一个标

28、志flag=1,当输入“-1”时，flag为0，建表结束*/ head=(Linklist*)malloc(sizeof(Node); /*为头结点分配存储空间*/ head-link=NULL; while(flag) scanf(“%d”, ,在链表的头部插入，建立的单链表的逻辑顺序与输入的顺序相反，这种建立方式也称为逆序建表法。,(2)在单链表的尾部插入结点建立单链表,逆序建表法虽然简单，但生成的单链表中结点的次序和输入的顺序相反。 若希望二者次序一致，则可在链表的尾部插入结点建立链表。 该方法需要增加一个尾指针q，使其始终指向当前链表的表尾，以便于将新结点插入在q的后面。,在单链表的尾

29、部插入结点建立单链表,尾部插入结点算法描述如下：,Linklist *Create_List(void) /*将新结点插入在链表的末尾*/ LinkList *head; Node *p, *q; int flag =1; /*设置标志flag=1,当输入-1时，flag为0，建表结束*/ head=(Node * )malloc(sizeof(Node); /*为头结点分配存储空间*/ head-link=NULL; q=head; /*q指针始终动态指向链表的当前表尾，其初值指向头结点*/ while(flag) scanf(“%d”,if(x!=-1) p=(Node*)malloc(s

30、izeof(Node); /*申请新结点p */ p-data=x; /* 给新结点的数据域赋值 */ q-link=p; /*将新结点链接在尾结点之后 */ q=p； /*移动尾指针，使其指向新的表尾结点 */ else flag=0; q-link=NULL; /*将最后一个结点的link域置为空，表示链表的结束*/ /*while*/ return head; ,算法分析： 上述两个建立链表的算法时间复杂度均为,2）查找操作,在单链表中，由于每个结点的存储位置都放在其前驱结点的指针域中，所以即使知道被访问结点的序号i，也不能像顺序表那样直接按序号i访问相应元素，无法实现随机存取，而只能从

31、链表的头指针出发，顺着链域link逐个结点往下查找，直至找到第i个结点为止。,（1）按序号查找,设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针head出发，从头结点（head-link）开始顺着链域扫描，用指针p指向当前被扫描到的结点，初值指向头结点（p=head-link），用j做计数器，累计当前扫描过的结点个数（初值为1），如图所示，当j = i 时，指针p所指的结点就是要找的第i个结点。,按序号查找 算法:,Node * GetNode (LinkList *head, int i) / * 在带头结点的单链表head中查找第i个结点，若找到(1in)，则返回

32、该结点的存储位置; 否则返回NULL * / int j； Node *p； p=head-link；j=1； / * 从头结点开始扫描 * / while (p-link!=NULL) p=head-link; / * 从表中第一个结点比较 * / while (p!=NULL) if (p-data!=e) p=p-link; else break; / * 找到结点e，退出循环 * / return p; / * Locate * /,算法分析： 这两个查找算法的基本语句是将指针p后移，其执行次数与被查结点在表中的位置有关。 在查找成功的情况下，若查找位置为i(1in),则需要执行i-1

33、次移动，等概率的情况下，平均时间复杂度是相同的，即,3）单链表插入操作,在带头结点的单链表head中的第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针p指示，然后申请一个新的结点并由指针q指示，其数据域的值为e，指针域指向第i个结点，然后修改第i-1个结点的指针使其指向q。,在单链表第i个结点前插入一个结点的过程,在单链表的第i个结点之前插入新结点的算法描述如下：,void InsList(LinkList *head, int i,DataType e) /*在带头结点的单链表head的第i个结点之前插入值为e的新结点*/ Node *p,*q; int j

34、; p=head-link; j=1; while(p!=NULL ,if(j!=i-1) /*p=NULL时，链表为空，不存在第i个结点；或者idata=e; /*将待插入结点的值e赋给q的数据域*/ q-link=p-link; /*将第i个结点链接在新结点q之后*/ p-link=q; /*将新结点连接在p之后，完成插入操作*/ ,如果在带头结点的单链表head中的第i个数据元素之后插入一个数据元素e，则只需要在单链表中找到第i个结点并由指针p指示 然后申请一个新的结点并由指针q指示，其数据域的值为e 指针域指向第i个结点的后继（即q-link=p-link） 然后修改p的指针域使其指向

35、新结点q。,在单链表第i个结点之后插入一个结点的过程,在单链表的第i个结点之后插入新结点的算法描述如下：,void InsList(LinkList *head,int i,DataType e) /*在带头结点的单链表head的第i个结点之前插入值为e的新结点*/ Node *p,*q; int j; p=head-link; j=1; while(p!=NULL ,if(j!=i) /*p=NULL时，链表为空，不存在第i个结点；或者idata=e; /*将待插入结点的值e赋给q的数据域*/ q-link=p-link; /*将第i个结点链接在新结点q之后*/ p-link=q; /*将新

36、结点连接在p之后，完成插入操作*/ ,算法分析：,上述两个插入算法的时间复杂度均为 在插入新结点之前，都需要从头遍历链表，找到合适的插入位置（前者需找到第i-1个结点，才能在第i个结点之前插入新结点，后者则需找到第i个结点，便于在其后插入新结点）,4）删除操作,在带头结点的单链表head中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，q指向被删除的第i个结点， 然后将q的后继作为p的后继（即p-link=q-link）从链表中删除q 然后释放q的结点空间。,单链表的删除操作,int DelList(LinkList *head,int i,DataType *

37、e) /*在带头结点的单链表head中删除第i个元素，并将删除元素保存到变量e中*/ Node *p,*q; int j; p=head; j=0; while(p-link!=NULL ,if(j!=i-1) /* 即while循环是因为p-link=NULL或ilink; p-link=q-link; /*或p-link=p-link-link;均可删除结点q*/ free(q); /*释放被删除的结点所占的内存空间*/ return OK; ,算法分析：,删除操作与插入操作类似，首先需要找到被删结点的前驱结点，然后修改指针就可完成操作，故其时间复杂度仍为,3、单链表的应用举例,例3-2编

38、写一个算法，求单链表的长度。 可以通过计数的方法来求出单链表的长度，用指针p依次指向各个结点，从第一个元素开始计数，一直到最后一个结点（p-link=NULL）。,int ListLength(LinkList head) /*本算法用来求带头结点的单链表head的长度*/ Node *p; p=head-link; j=0; /*用来存放单链表的长度*/ while(p!=NULL) p=p-link; j +; return j; /* End of function ListLength */,例3-3 如果以单链表表示集合，假设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求

39、两个集合的差，即A-B。 由集合运算的规则可知，集合的差A-B中包含所有属于集合A而不属于集合B的元素。 具体做法: 对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素，则从LA中将其删除。,此算法求两个集合的差集,void Difference (LinkList LA,LinkList LB) Node *pre;*p, *r; pre=LA; p=LA-link; /*p指向LA表中的某一结点，而pre始终指向p的前驱*/ while(p!=NULL) q=LB-link; /*依次扫描LB中的结点，看有否与LA中*P结点的值相同的结点*/ while (q!=

40、NULL,if (q!=NULL) r=p; pre-link=p-link; p=p-link; free(r); else pre=p; p=p-link; /* while(p!=NULL)*/ ,循环链表,1、循环链表的定义 循环链表(Circular Linked List)是单链表的另一种形式，其结构特点是链表中的最后一个结点的指针域不再为空，表示链表结束，而是指向链表的第一个结点，从而使链表首尾相接形成一个环。,循环单链表,对于单链表只能从头结点开始遍历整个链表，而在循环单链表中，表中所有结点被链在一个环上，因而从表中任何一个结点出发均可访问到表中的其它结点。 当要处理得数据元素

41、序列具有环形结构特点时，适合采用循环单链表，如约瑟夫环问题。 对于循环链表，若访问一个表中根本不存在的结点，如果不采取措施，则将会导致“死”循环。,为了使链表的插入和删除操作实现起来方便，在循环单链表中也可设置一个头结点。 头结点的数据域为空或按需要设定,带头结点的循环单链表,循环链表的操作,带头结点的循环单链表的各种操作的实现算法与带头结点的单链表的实现算法类似，差别仅在于： 当需要从头到尾扫描整个链表时，判断是否到表尾的条件不同。 在单链表中以指针域是否为“空”作为循环条件 （即p!=NULL或p-link !=NULL）， 而在循环链表中则以结点的指针域是否等于头指针作为判断表尾结点的条

42、件（即p!=head或p-link!=head）。 有时对链表常作的操作是在表尾、表头进行，此时在循环单链表中附设尾指针比附设头指针会使操作变得更为简单,仅设尾指针的两个循环单链表,3、循环链表的应用举例,例3-4有两个带头结点的循环单链表L1、L2，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。 思路： 在用头指针表示的循环单链表中，首先要找到两个链表的尾结点，分别让指针p和q指向它们，然后将第一个链表的尾与第二个链表的第一个结点链接起来，并修改第二个表的尾q，使它的链域指向第一个表的头结点。,算法描述如下：,LinkList Merge1( LinkList L1,

43、LinkList L2) /*此算法将两个采用头指针的循环单链表的首尾连接起来*/ Node *p, *q; p=L1; q=L2; while (p-link!=L1) p=p-link; /*找到表L1的表尾，用p指向它*/ while (q-link!=L2) q=q-link; /*找到表L2的表尾，用q指向它*/ q-link=L1; /*修改表L2 的尾指针，使之指向表L1 的头结点*/ p-link=L2-link; /*修改表L1的尾指针，使之指向表L2中的第一个结点*/ free(L2); return(L1); ,算法分析：,将两个线性表合并成一个，找开始结点a1的时间复杂

44、度是 然而要找到终端结点an，则需要从头指针开始遍历整个链表，其时间复杂度是,若用图中的尾指针rear来表示循环单链表，则查找开始结点和终端结点都很方便，其存储位置分别是rear-link-link和rear，显然，查找时间复杂度都是 实用中多采用尾指针表示循环单链表,合并后的的循环单链表,算法描述如下：,LinkList Merge2（LinkList R1,LinkList R2） /*此算法将两个采用尾指针的循环链表首尾连接起来*/ Node *p; p=R1-link; /*保存链表R1的头结点地址*/ R1-link=R2-link-link; /*链表R2的开始结点链到链表R1的终

45、端结点之后*/ free(R1-link); /*释放链表R1的头结点*/ R2-link=p; /*链表R1的头结点链到链表R2的终端结点之后*/ return R2; /*返回新循环链表的尾指针*/ ,例3-5 求解约瑟夫环,设编号为1,2,3,n的n(n0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。 开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将其密码作为新的m值，从他下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。,分析：,该问题适合采用循环单链表（为便于操作，可使其不带头结点）存储相关数据。 问题求

46、解时，首先从头指针顺序从1扫描到第m个结点，取其密码作为新的报数上限m，输出其序号，删除该结点，然后从其后继结点重复上述动作，直到输出n个结点。,结点结构定义及算法如下：,#include #include typedef struct jos int order; int mima; struct jos *link; Node;,Node *creat(void) Node *p,*q,*head; int i,s100; int n; /*人数*/ /*输入人数和各自的密码 */ printf(请输入人数(n):); scanf(%d,head=(Node *)malloc(sizeof

47、(Node); /*建立循环单链表*/head-order=1;head-mima=s1;q=head;for(i=1;ilink=p; p-order=i+1; p-mima=si+1; q=p; /*将新结点插入在链表的尾部*/ p-link=head; /*首尾相接，构成循环*/ return head; /* creat(void)*/,main() Node *head,*p,*q; int i，m, k=1,t=0,del100; head=creat(); p=head; q=head; printf(请输入初值(m):); scanf(%d,do loop1: if(k=m)

48、k=1; m=p-mima; t+; delt=p-order; q-link=p-link; free(p); p=q-link; goto loop1; q=p; p=p-link; k+;if(t=n-1) deln=p-order; t+;while(t=n-1);,printf(出列顺序为:n);if(n=1) printf(%d, 1);elsefor(i=1;i=n;i+)printf(%7d,deli);,3 双向链表,1、双向链表的定义 循环单链表的出现，虽然能够实现从任意某结点出发沿着指针域能找到其前趋结点，但时间耗费是。 若希望从链表中快速确定某个结点的前驱结点，另一种解

49、决方法就是在单链表的每个结点结构里再增加一个指向其前驱的指针域prior。 这样形成的链表中就有两条方向不同的链，我们称之为双 ( 向) 链表 (Double Linked List)，,结点结构可定义如下：,typedef struct DNode DataType data； struct DNode *prior，*link； DNode, * DoubleList；,双向链表的结点结构,带头结点的非空双向链表,与单链表类似，双向链表一般也是由头指针唯一确定的，增加头结点也能使双向链表的某些操作变得方便,将双向链表的头结点和尾结点连接起来，也可以构成双向循环链表，如图所示，链表中有两个环

50、,由于在双向链表中，既有前向链又有后向链，寻找任一结点的直接前驱与直接后继变得非常方便。 设指针p指向双向链表中某一结点，则p-prior-link表示p结点的前驱结点的后继结点，即p结点； 类似，p-link-prio表示p结点的后继结点的前驱结点，也是p结点。 所以有以下等式： p-prior-link = p = p-link-prior,2、双向链表的操作,在双向链表中，那些只涉及后继指针的算法，如求链表长度、获取元素、元素定位等，与单链表中相应的算法相同，但是进行插入、删除操作时，在双向链表中需同时修改前驱和后继两个方向的指针，因此与单链表中的算法不同。,1)双向链表的插入操作,双向

51、链表中结点的插入操作和单链表类似，若在双向链表的第i个结点之前插入一个的新的结点，则可使指针p指向第i个结点，指针s指向待插入的新结点，插入过程如图所示,操作如下： s-prior=p-prior; p-prior-link=s; s-link=p; p-prior=s; 上述指针操作的顺序不是唯一的，但也不是任意的，其中操作必须放在操作之前完成，否则就无法找到p结点的前驱。,双向链表的插入算法描述如下：,int DlinkIns ( DoubleList head , int i, DataType e ) DNode *s,*p; /*先检查待插入的位置i是否合法（实现方法同单链表的前插操

52、作）*/ /*若位置i合法，则让指针p指向它*/ s=(DNode*)malloc(sizeof(DNode); /*申请待插入新结点*/ if (s) /*若申请成功，则给数据域赋值，然后修改指针*/ s-data=e; s-prior=p-prior; p-prior-link=s; s-link=p; p-prior=s; return OK; else return ERROR; ,2) 双向链表的删除操作,在双向链表中删除第i个结点，则可使指针p指向第i个结点，修改其前驱结点和后继结点的相关指针，返回p结点的值，然后删除p结点，删除过程如图所示,操作如下：, p-link-prior

53、=p-prior; p-prior-link=p-link; 上述指针操作的顺序可以互换，双向链表的删除算法描述如下： int DlinkDel(DoubleList head,int i,DataType *e) DNode *p; /*先检查待插入的位置i是否合法（实现方法同单链表的删除操作）*/ /*若位置i合法，则让指针p指向它*/ *e=p-data; p-link-prior=p-prior; p-prior-link=p-link; free(p); return OK; ,3、双向链表的应用举例,例3-6设一个循环双链表L=（a,b,c,d），编写一个算法将链表转换为L=（b,

54、a,c,d）。 分析：本题实际上是交换表中前两个元素的次序。 void swap(DLinkList L) DNode * p,*q,*h; h=L-link; /* h指向表中的第一个结点，即a */ p=h-link; /* p指向b结点 */ q=h-prior; /* 保存a 结点的前驱 */ h-link=p-link; /* a结点的后继指向c结点 */ p-link-prior=h; /* c结点的前驱指向a结点 */ p-prior=q; /* 将b结点插入，作为表的第一个结点 */ p-link=h; h-prior=p; L-link=p; /* 将表的头结点的next 域

55、指向b结点 */ ,3.4.5 顺序表和链表的比较,上面介绍了线性表的两种存储结构：顺序表和链表，它们各有优缺点。 在实际应用中究竟选用哪一种存储结构呢？ 这要根据具体的要求和性质决定。,通常从以下几方面来考虑：,1基于空间的考虑 顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模。 若线性表的长度n变化较大，则存储规模难于预先确定。 估计过大将造成空间浪费，估计太小又将使空间溢出的机会增多。,动态链表的存储空间是动态分配的，只要内存空间尚有空闲，就不会产生溢出。 当线性表的长度变化较大，难以估计其存储规模时，采用动态链表作为存储结构较好。,在链表中的每个结点，除了数据域外，

56、还要额外设置指针（或游标）域，从存储密度来讲，这是不经济的。 所谓存储密度(Storage Density)是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即： 存储密度=结点数据本身所占的存储量/结点结构所占的存储总量,一般地，存储密度越大，存储空间的利用率就高。 顺序表的存储密度为1，而链表的存储密度小于1。 例如单链表的结点的数据均为整数，指针所占空间和整型量相同，则单链表的存储密度为50%。 若不考虑顺序表中的备用结点空间，则顺序表的存储空间利用率为100%，而单链表的存储空间利用率为50%。 由此可知，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用

57、顺序表作为存储结构。,2基于时间的考虑,顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可以在O (1) 时间内直接地存取，而链表中的结点，需从头指针起顺着链域查找才能取得。 若线性表的操作主要是进行查找，很少做插入和删除时，采用顺序表做存储结构为宜。,在链表中的任何位置上进行插入和删除，都只需要修改指针。 而在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。 对于频繁进行插入和删除的线性表，宜采用链表做存储结构。 若表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的循环单链表为宜。,3.5 线性表的应用,3.5.1一元多项式的表示及相加 1、一元多项式的表示 对于符