数据结构课件第2章线性表.ppt

线性结构包括线性表、栈、队列、串、数组和广义表。其特线性结构包括线性表、栈、队列、串、数组和广义表。其特 点是：在数据元素的非空有限集合中点是：在数据元素的非空有限集合中 存在惟一的一个被称作存在惟一的一个被称作 “第一个第一个” ” 的的数据元素；数据元素； 存在惟一的一个被称存在惟一的一个被称作作 “ “最后一个最后一个” ” 的数据元的数据元素；素； 除第一个数据元素之外，集合中的每个数据元素均只有一个除第一个数据元素之外，集合中的每个数据元素均只有一个 前驱；前驱； 除最后一个数据元素之外，集合中的每个数据元素均只有一除最后一个数据元素之外，集合中的每个数据元素均只有一 个后继。个后继。 第第 2 2 章章 线性表线性表 1 第第 2 2 章章 线性表线性表 2 2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构 2.3 2.3 线性表的链式存储结构线性表的链式存储结构 2.4 2.4 线性表两种存储结构比较线性表两种存储结构比较 2.1 2.1 线性表的逻辑结构线性表的逻辑结构 3 例例2-12-1 26 26 个英文字母组成的字母表：个英文字母组成的字母表： （A A，B B，C C， ，Z Z） 是一个线性表，表中数据元素是单个字母字符。是一个线性表，表中数据元素是单个字母字符。 例例2-22-2 某校从某校从 1978 1978 年到年到 1983 1983 年各种型号的计算机拥有量的变年各种型号的计算机拥有量的变 化情况可以用一个线性表表示：化情况可以用一个线性表表示： （6 6，1717，2828，5050，9292，188188） 表中数据元素是整数。表中数据元素是整数。 例例2-32-3 一个学校的学生健康情况登记表如下图所示。一个学校的学生健康情况登记表如下图所示。 表中每个学生的情况为一个记录，它的姓名、学号、性别、表中每个学生的情况为一个记录，它的姓名、学号、性别、 年龄、班级和健康情况等六个数据项组成。年龄、班级和健康情况等六个数据项组成。 姓名姓名学号学号性别性别年龄年龄班级班级健康情况健康情况 王小林王小林790631 790631 男男18 18计计9191 健康健康 陈陈 红红790632 790632 女女20 20计计9191 一般一般 刘建平刘建平790633 790633 男男21 21计计9191 健康健康 张立立张立立790634 790634 男男17 17计计9191 神经衰弱神经衰弱 4 2.1 2.1 线性表的逻辑结构线性表的逻辑结构 2.1 2.1 线性表的逻辑结构线性表的逻辑结构 5 线性表中的数据元素可以是各种各样的，但同一线性表中的元线性表中的数据元素可以是各种各样的，但同一线性表中的元 素必须具有相同的特性，即属同一数据对象，且相邻数据元素之间素必须具有相同的特性，即属同一数据对象，且相邻数据元素之间 存在着序偶关系。存在着序偶关系。 线性表的定义线性表的定义 线性表的基本操作线性表的基本操作 一个线性表（一个线性表（linear_listlinear_list）是是 n n（n n00）个具有个具有相同属性相同属性的数据的数据 元素的元素的有限有限序列，其中各元素有着依次相邻的逻辑关系。序列，其中各元素有着依次相邻的逻辑关系。 线性表中数据元素的个数线性表中数据元素的个数 n n 称为称为线性表的长度线性表的长度。当。当 n n = = 0 0 时该时该 线性表称为线性表称为空表空表。当。当 n n 0 0 时该线性表可以记为：时该线性表可以记为： （a a 1 1 ， a a2 2 ， a a3 3 ， a a i i ， a an n ） 6 2.1.1 2.1.1 线性表的定义线性表的定义 7 2.1.2 2.1.2 线性表的基本操作线性表的基本操作 InitListInitList ( L ) ( L ) 操作结果：构造一个空的线性表操作结果：构造一个空的线性表 L L。 DestroyList(LDestroyList(L) ) 初始条件：线性表初始条件：线性表 L L 已存在。已存在。 操作结果：将操作结果：将L L销毁。销毁。 DelList(L,i,eDelList(L,i,e) ) 初始条件：线性表初始条件：线性表 L L 已存在且非空，已存在且非空，1 1iListLength(L)iListLength(L) 操作结果：删除操作结果：删除L L的第的第i i个数据元素，并用个数据元素，并用e e返回其值返回其值,L,L的长的长 度减一。度减一。 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构 线性表的顺序存储表示线性表的顺序存储表示 8 基本操作在顺序表上的实现基本操作在顺序表上的实现 线性表线性表顺序存储的小结顺序存储的小结 (1) (1) 定义定义 用一组地址连续的存储单元依次存储线性表中的各个数据元素用一组地址连续的存储单元依次存储线性表中的各个数据元素 ，称为线性表的顺序存储。，称为线性表的顺序存储。 9 2.2.1 2.2.1 线性表的顺序存储表示线性表的顺序存储表示 1 1 2 2 i i n n 空闲空闲 LOCLOC ( (a a 1 1 ) ) LOCLOC ( (a a 1 1 ) + ) + k k LOCLOC ( (a a 1 1 ) + () + (i i-1) -1) k k LOCLOC ( (a a 1 1 ) + () + (n n-1) -1) k k 线性表的最大空间线性表的最大空间 a a1 1 a a2 2 a a i i a an n 存储地址存储地址内存状态内存状态 数据元素在线数据元素在线 性表中的位序性表中的位序 因为表中各数据元素具有相 同的属性，所以占用的存储空间 也相同。假设线性表中每个数据 元素占用 k 个存储单元，第 1 个 数据元素的起始地址为 LOC (a1) ，则： 第 2 个数据元素的起始地址为： LOC (a2) = LOC (a1) + k 第 i 个数据元素的起始地址为： LOC (ai) = LOC (a1) + ( i-1 ) k ( i = 1, 2, 3, , n ) 第 n 个数据元素的起始地址： LOC (an) = LOC (a1) + ( n-1 ) k 定位公式 10 (2) (2) 特点特点 只要确定了存储线性表的起始位置，线性表中任一数据元素都只要确定了存储线性表的起始位置，线性表中任一数据元素都 可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储 结构。顺序存储结构的特点是：结构。顺序存储结构的特点是：逻辑上相邻的数据元素在物理存储逻辑上相邻的数据元素在物理存储 上（在存储器中）也相邻。上（在存储器中）也相邻。 (1) (1) 定义定义 用一组地址连续的存储单元依次存储线性表中的各个数据元素用一组地址连续的存储单元依次存储线性表中的各个数据元素 ，称为线性表的顺序存储。，称为线性表的顺序存储。 11 2.2.1 2.2.1 线性表的顺序存储表示线性表的顺序存储表示 (3) (3) 线性表的顺序存储结构线性表的顺序存储结构 可以使用可以使用一维数组一维数组来表示来表示线性表的顺序存储结构线性表的顺序存储结构。线性表的顺序。线性表的顺序 存储结构的语言描述如下。存储结构的语言描述如下。 12 # define MAXSIZE 100 /*# define MAXSIZE 100 /*此处的宏定义常量表示线性表可能达此处的宏定义常量表示线性表可能达 到的最大长度到的最大长度* */ / typedeftypedef structstruct ElemTypeElemType elemMAXSIZEelemMAXSIZE; /*; /*线性表占用的数组空间线性表占用的数组空间* */ / intint last; last; SeqListSeqList; ; /* /* 顺序表的类型名顺序表的类型名* */ / 数组指针，指示数组指针，指示 线性表的基地址线性表的基地址。 2.2.1 2.2.1 线性表的顺序存储表示线性表的顺序存储表示 记录线性表中最后一个元素记录线性表中最后一个元素 在数组在数组elemelem 中的位置中的位置( (下下 标值标值), ),空表置空表置-1-1 (1) (1) 算法思想算法思想 按序号查找按序号查找GetData(L,iGetData(L,i): ):要求查找线性表要求查找线性表L L中第中第i i个数据元个数据元 素素, ,其结果是其结果是L.elemi-1L.elemi-1或或L-elemi-1.L-elemi-1. 按内容查找按内容查找Locate( Locate( L,eL,e): ):要求查找线性表要求查找线性表L L中与给定值中与给定值e e相等相等 的数据元素的数据元素, ,结果结果: :若在表若在表L L中找到与中找到与e e相等的元素相等的元素, ,则返回该元素在则返回该元素在 表中的序号表中的序号; ;若找不到若找不到, ,则返回一个则返回一个” ”空序号空序号” ”, ,如如-1.-1. 13 2.2.2 2.2.2 基本操作在顺序表上的实现基本操作在顺序表上的实现 1. 1. 查找操作查找操作 (2) (2) 算法编写算法编写 i=0; /*i i=0; /*i为扫描计数器为扫描计数器, ,初值为初值为0*/0*/ while(iwhile(ilast+2*/-last+2*/ intint k; k; if ( i if ( i L-last+2) /*L-last+2) /*首先判断插入位置是否合法首先判断插入位置是否合法* */ / printfprintf(“(“插入位置插入位置i i值不合法值不合法” ”）；）； return ERRORreturn ERROR； 17 (2) (2) 算法编写算法编写 if if ( L-last=MAXSIZE-1) ( L-last=MAXSIZE-1) printfprintf(“(“表已满无法插入表已满无法插入” ”); ); return(ERRORreturn(ERROR); ); 18 for(kfor(k=L-=L-last;klast;k=i-1;k-) /*=i-1;k-) /*为插入元素而移动位置为插入元素而移动位置* */ / L-elemk+1=L- L-elemk+1=L-elemkelemk; ; L-elemi-1=e; /*L-elemi-1=e; /*在在C C 语言数组中语言数组中, ,第第i i个元素的下标为个元素的下标为i-1*/i-1*/ L-last+; L-last+; return(OKreturn(OK); ); (3) (3) 算法分析算法分析 算法算法InsListInsList的基本操作是数据元素的基本操作是数据元素后移操作后移操作。执行元素后移。执行元素后移 的次数是的次数是 n n i i + + 1 1。可以看到：移动元素的次数不仅和线性表的可以看到：移动元素的次数不仅和线性表的 长度长度 n n 有关，而且还与插入元素的位置有关，而且还与插入元素的位置 i i 有关。当有关。当 i i = = n n + + 1 1 时，时， 无须移动元素；当无须移动元素；当 i i = = 1 1 时，则元素后移执行时，则元素后移执行 n n 次。也就是说，次。也就是说， 该算法在最好的情况下时间复杂度是该算法在最好的情况下时间复杂度是 O O(1)(1)，在最坏的情况下时间在最坏的情况下时间 复杂度是复杂度是 O O( (n n) )。 19 设设insins为在长度为为在长度为n n的表中插入一个元素所需移动元素的平均的表中插入一个元素所需移动元素的平均 次数，假设次数，假设i i为在第为在第i i个元素之前插入元素的概率，并假设在任何个元素之前插入元素的概率，并假设在任何 位置上插入的概率相同位置上插入的概率相同 (1) (1) 算法思想算法思想 在一般情况下，删除第在一般情况下，删除第 i i 个元素时，需要将个元素时，需要将 n n 至第至第 i i+1+1 个（共个（共 n n- -i i）元素向前移动一个位置。元素向前移动一个位置。 检查删除位置的合理性；检查删除位置的合理性； 把原来第把原来第 i i+1 +1 个数据元素至第个数据元素至第 n n 个数据元素依次向前移一个数据元素依次向前移一 个数组元素位置；个数组元素位置； 修正线性表的数据元素个数。修正线性表的数据元素个数。 20 3. 3. 顺序线性表的删除算法顺序线性表的删除算法 a a1 1 a a i i-1-1 a a i i a a i i+1+1 a an n 内存位置内存位置位序位序 1 1 i i-1-1 i i i i+1+1 n n 空闲 要要删除的元素删除的元素 (a) 删除元素前 a a i i+1+1 a a i i+2+2 已删除元素已删除元素 a a i i (b) (b) 删除元素后删除元素后 a an n 空闲 21 IntInt DelListDelList( ( SeqListSeqList *L, *L, intint i, i, ElemTypeElemType *e ) *e ) /* /* 在顺序线性表在顺序线性表 L L 中删除第中删除第 i i 个元素，并用个元素，并用 e e 返回其值返回其值 i i 的合法值为的合法值为 11i i L Llast+1*/last+1*/ intint k; k; if ( ( i L-last+1 ) ) if ( ( i L-last+1 ) ) printfprintf(“(“删除位置不合法！删除位置不合法！” ”）；）； return return （ERRORERROR）; ; /* /* i i 值不合法值不合法* */ / for (k=for (k=i;ii;ilast;klast;k+ )+ ) L-elemk-1=L-L-elemk-1=L-elemkelemk;/*/*被删除元素之后的元素前移被删除元素之后的元素前移* */ / * *e = L-elemi-1;e = L-elemi-1; /* /* 被删除元素被删除元素 存放到存放到e e所指向的变所指向的变 量中量中* */ / 22 (2) 算法编写 L-last-;L-last-;/* /* 表长减表长减 1*/1*/ return OK; return OK; /* /*DelListDelList*/*/ (3) (3) 算法分析算法分析 算法算法DelListDelList的基本操作是数据元素的基本操作是数据元素前移操作前移操作。执行元素前移。执行元素前移 的次数是的次数是 n n - - i i。可以看到：移动元素的次数不仅和线性表的长度可以看到：移动元素的次数不仅和线性表的长度 n n 有关，而且还与删除元素的位置有关，而且还与删除元素的位置 i i 有关。当有关。当 i i = = n n 时，无须移动时，无须移动 元素；当元素；当 i i = = 1 1 时，则元素前移执行时，则元素前移执行 n n - - 1 1 次。也就是说，该算法次。也就是说，该算法 在最好的情况下时间复杂度是在最好的情况下时间复杂度是 O O(1)(1)，在最坏的情况下时间复杂度在最坏的情况下时间复杂度 是是 O(O(n n) )。 进一步分析算法的平均性能：算法进一步分析算法的平均性能：算法DelListDelList的时间复杂度为的时间复杂度为 O O( (n n) )。 24 线性表顺序存储结构的最大特点就是逻辑上相邻的两个元素在线性表顺序存储结构的最大特点就是逻辑上相邻的两个元素在 物理位置上也相邻。这一特点使顺序表具有十分鲜明的优点和缺点物理位置上也相邻。这一特点使顺序表具有十分鲜明的优点和缺点 。 25 2.2.3 2.2.3 线性表顺序存储的小结线性表顺序存储的小结 (2) (2) 顺序存储结构的缺点顺序存储结构的缺点 (1) (1) 插入或删除一个数据元素时，需要对插入点或删除点后面插入或删除一个数据元素时，需要对插入点或删除点后面 的全部元素逐个进行移动，需要花费较多的时间。的全部元素逐个进行移动，需要花费较多的时间。 (2) (2) 在给长度变化较大的线性表预先分配空间时必须按照最大在给长度变化较大的线性表预先分配空间时必须按照最大 空间分配，使存储空间不能得到充分利用。空间分配，使存储空间不能得到充分利用。 (3)(3) 线性表的容量难以扩充。线性表的容量难以扩充。 26 2.2.3 2.2.3 线性表顺序存储的小结线性表顺序存储的小结 1. 1. 顺序存储结构的优点顺序存储结构的优点 (1) (1) 便于随机存取线性表中任一个数据元素，且存取任一个数便于随机存取线性表中任一个数据元素，且存取任一个数 据元素所花费的时间相同。据元素所花费的时间相同。 (2)(2) 存储空间连续，不必增加额外的存储空间。存储空间连续，不必增加额外的存储空间。 27 线性表的顺序存储结构适用于数据线性表的顺序存储结构适用于数据 元素不经常变动或只需在顺序存取设备元素不经常变动或只需在顺序存取设备 上做成批处理的场合。为了克服线性表上做成批处理的场合。为了克服线性表 顺序存储结构的缺点，可采用线性表的顺序存储结构的缺点，可采用线性表的 链式存储结构。链式存储结构。 线性表的链式存储表示线性表的链式存储表示 2.3 2.3 线性表的链式存储结构线性表的链式存储结构 28 基本操作在单链表上的实现基本操作在单链表上的实现 循环链表循环链表 双向双向链表链表 线性表链线性表链式存储结构小结式存储结构小结 线性表链式存储结构的特点是用一组任意的存储单元存储该线性表链式存储结构的特点是用一组任意的存储单元存储该 线性表中的各个数据元素（存储单元可以连续，也可以不连续）线性表中的各个数据元素（存储单元可以连续，也可以不连续） 。 相关的概念有：结点，线性表的单链表存储结构，头结点和相关的概念有：结点，线性表的单链表存储结构，头结点和 头指针。头指针。 29 2.3.1 2.3.1 线性表的链式存储表示线性表的链式存储表示 (1) (1) 结点结点 一个数据元素一个数据元素 a a i i 的存储结构由两部分信息组成，称之为结点的存储结构由两部分信息组成，称之为结点 (node)(node)。结点包括两个域：结点包括两个域：数据域数据域 (data)(data)，存储数据元素信息；存储数据元素信息；指指 针域针域 (next)(next)，存储直接后继元素地址（没有后继元素时指针为存储直接后继元素地址（没有后继元素时指针为 “ 空空” (NULL)(NULL)） 。指针域中存储的信息称为指针域中存储的信息称为指针或链指针或链。 30 结点结点datadatanextnext 数据域数据域指针域指针域 (2) (2) 线性表的单链表存储结构线性表的单链表存储结构 31 通过每个结点的指针域将线性表中通过每个结点的指针域将线性表中 n n 个结点按其逻辑顺序链个结点按其逻辑顺序链 接在一起的结点序列称为接在一起的结点序列称为链表链表，即为线性表，即为线性表 ( ( a a1, 1, a a 2, 2, a a 3, 3, , , a a i i, , , , a an n ) ) 的链式存储结构。如果线性链表中的每个结点只有一个指针域的链式存储结构。如果线性链表中的每个结点只有一个指针域 ，则链表又称为，则链表又称为线性链表线性链表或或单链表单链表 (linked list)(linked list)。 例：线性表如下：例：线性表如下： （ZHAOZHAO，QIANQIAN，SUNSUN，LILI，ZHOUZHOU，WUWU，ZHENGZHENG，WANGWANG ） 线线 性性 链链 表表 在在 内内 存存 的的 存存 储储 结结 构构 起始地址起始地址 32 数据域数据域指针域指针域存储地址存储地址 LILI4343 1 1 QIANQIAN1313 7 7 SUNSUN 1 1 1313 WANGWANGNULLNULL1919 WUWU37372525 ZHAOZHAO 7 7 3131 ZHENGZHENG19193737 ZHOUZHOU25254343 ZHAOZHAOQIANQIANSUNSUNLILI ZHOUZHOUWUWUZHENGZHENGWANG WANG 3131 7 7 1313 1 1 4343252537371919 33 线性表的单链表存储表示：线性表的单链表存储表示： typedeftypedef structstruct Node Node ElemTypeElemTypedata;data;/* /* 数据域数据域* */ / structstruct Node Node*next;*next;/*/*指针域指针域* */ / Node, Node, * *LinkListLinkList; ;/*/*单链表的类型名单链表的类型名* */ / (2) (2) 线性表的单链表存储结构线性表的单链表存储结构 通过每个结点的指针域将线性表中通过每个结点的指针域将线性表中 n n 个结点按其逻辑顺序链个结点按其逻辑顺序链 接在一起的结点序列称为链表，即为线性表接在一起的结点序列称为链表，即为线性表 ( ( a a1, 1, a a 2, 2, a a 3, 3, , , a a i i, , , , a an n ) ) 的链式存储结构。如果线性链表中的每个结点只有一个指针域的链式存储结构。如果线性链表中的每个结点只有一个指针域 ，则称链表又称为，则称链表又称为线性链表线性链表或或单链表单链表 (linked list)(linked list)。 (3) (3) 头结点和头指针头结点和头指针 34 在单链表的第一个结点之前附加一个同结构的结点，称之在单链表的第一个结点之前附加一个同结构的结点，称之 为为头结点头结点。头结点的数据域可以不存储任何信息也可以存储如。头结点的数据域可以不存储任何信息也可以存储如 线性表的长度等类的附加信息；头结点的指针域指向第一个结线性表的长度等类的附加信息；头结点的指针域指向第一个结 点（即第一个元素结点的存储位置）。点（即第一个元素结点的存储位置）。 头指针头指针就是指向头结点的指针。就是指向头结点的指针。当头结点的指针当头结点的指针域为域为 “空空 ” ” 时时，单链表为空链表。，单链表为空链表。 头指头指针针 L L a a1 1 a a2 2 a an n 头结点头结点 L L 35 非空单非空单链表链表 空空链表链表 建立线性表的链式存储结构的过程是一个动态生成单链表的过建立线性表的链式存储结构的过程是一个动态生成单链表的过 程，即从程，即从 “ “空表空表” ” 的初始状态起，依次建立各元素结点，并逐个插的初始状态起，依次建立各元素结点，并逐个插 入到单链表中。入到单链表中。 (1) (1) 算法思想算法思想 首先建立一个空表，然后重复下面操作：首先建立一个空表，然后重复下面操作： 生成一个新结点；生成一个新结点； 读入数据，并存入新结点的数据域；读入数据，并存入新结点的数据域； 将新结点插入到单链表的头结点之后；将新结点插入到单链表的头结点之后； 修改单链表头结点的指针域。修改单链表头结点的指针域。 36 2. 2. 建立建立单链表单链表 ( (头插法）头插法） 2.3.1 2.3.1 线性表的链式存储表示线性表的链式存储表示 L L s s c c1 1 s s c cn n s s c c2 2 s s- -next = next = L L- -nextnextL L- -next = next = s ss s- -next = next = L L- -nextnextL L- -next = next = s ss s- -next = next = L L- -nextnext L L- -next = next = s s 37 38 p45:p45:算法编写算法编写( (线性表的长度不知道）线性表的长度不知道） void void GreateFromHeadGreateFromHead ( ( LinkListLinkList L) L) / */ *L L是已经初始化好的空链表的头指针是已经初始化好的空链表的头指针, ,通过键盘输入表中元素通过键盘输入表中元素* */ / /*/*值值, ,利用头插法建单链表利用头插法建单链表L*/L*/ Node *s; Node *s; char c; char c; intint flag=1; flag=1; While (flag) While (flag) /* flag /* flag初值为了初值为了, ,当输入当输入” ”$”$”时时, ,置置flagflag为为0, 0,建表结束建表结束* */ / c= c=getchargetchar( ) ;( ) ; if (c!=$ ) if (c!=$ ) s= (Node *) s= (Node *) mallocmalloc ( ( sizeofsizeof (Node ) ); /* (Node ) ); /* 生成新结点生成新结点* */ / s-data=c;s-data=c; s- s-next = Lnext = L- -next;next; /* /* 将新结点插入到单链表的头将新结点插入到单链表的头* */ / L L- -next =s;next =s; /* /* 修改单链表头结点的指针域修改单链表头结点的指针域* */ / /* while /* while结束结束* */ / else flag=0 /* else flag=0 /*若输入字符为若输入字符为$, $,置置flag=0*/flag=0*/ /* /*CreatFromTailCreatFromTail*/*/ (1) (1) 算法思想算法思想 在单链表中，任何两个元素存储位置间没有固定的联系，每在单链表中，任何两个元素存储位置间没有固定的联系，每 一个元素的存储位置都包含在其直接前驱结点的一个元素的存储位置都包含在其直接前驱结点的nextnext之中。之中。 假设假设 p p 是指向线性表中第是指向线性表中第 i i 个元素的指针，则该结点称为个元素的指针，则该结点称为 p p 结点或结点结点或结点 a a i i ；而；而 p p- -next next 是指向第是指向第 i i+1 +1 个元素的指针。若个元素的指针。若 p p- - data = data = a a i i ，则则 p p- -nextnext- -data = data = a ai i+1 +1。 。 由此，在单链表中，取得第由此，在单链表中，取得第 i i 个数据元素必须从头指针出发个数据元素必须从头指针出发 寻找。因此，单链表是寻找。因此，单链表是非随机的存储结构。非随机的存储结构。 40 3. 3. 单链表的查找元素算法单链表的查找元素算法( (按序号查找按序号查找) ) L L a a1 1 a a i+i+1 1 a an n a a i i p p- -nextnext p p 41 Node *Get ( Node *Get ( LinkListLinkList L, L, intint i ) i ) /* /* L L 是带头结点单链表的头指针，当第是带头结点单链表的头指针，当第 i i 个元素存在时，则返回该个元素存在时，则返回该 结点的存储位置结点的存储位置; ;否则返回否则返回 NULLNULL。 11i i 表长。表长。* */ / intint j; j; Node *p;Node *p; if(iif(inext!=NULL) j+; next; j+; /* /*顺指针向后查找，直到顺指针向后查找，直到 p p 指向第指向第 i i 个元素或个元素或 p p 为空为空* */ / if ( i=j) return p;if ( i=j) return p; /* /*取第取第 i i 个元素个元素 else return NULL /*else return NULL /*第第 i i 个元素不存在个元素不存在 /*Get*/ /*Get*/ 42(2) (2) 算法编写算法编写 (3) (3) 算法分析算法分析 算法算法 Get Get 的基本操作：比较的基本操作：比较 j j 和和 i i 且后移指针。且后移指针。while while 循环体中循环体中 的语句执行次数与被查数据元素在线性表中的位置有关。假设线性的语句执行次数与被查数据元素在线性表中的位置有关。假设线性 表长为表长为 n n，如果如果 11i i n n ，则则 while while 循环体中语句的执行次数为循环体中语句的执行次数为 i i，否，否 则执行次数为则执行次数为 n n ，因此算法因此算法 Get Get 的时间复杂度为的时间复杂度为 O O( (n n) )。 43 IntInt ListLength(LinkListListLength(LinkList L) L) /* /* L L 是带头结点单链表的头指针，求链表长度是带头结点单链表的头指针，求链表长度* */ / Node *p; Node *p; p=L-next; p=L-next; j = 0; j = 0; /* /* 初始化，初始化，p p 指向头结点，指向头结点，j j 为计数器为计数器, ,初始时为初始时为* */ / while ( p!=NULL) while ( p!=NULL) p = p p = p- -next; next; j+; j+; return j ;return j ; /*j /*j为求得的单链表长度为求得的单链表长度* */ / /* /*ListLengthListLength*/*/ 44 4.4.求单链表长度操作求单链表长度操作 算法分析 若单链表L为空,p的初值为”NULL”,算法中while循环未执行 ，则返回链表长度j为0 若单链表L为非空表，算法中while循环执行次数为表长 度n,故算法的时间复杂度为O(n). (1) (1) 算法思想算法思想 假设要在带头结点的单链表的两个数据元素假设要在带头结点的单链表的两个数据元素 a ai i-1 -1 和 和 a a i i 之间插入之间插入 一个数据元素一个数据元素 e e。 查找第查找第 i i-1 -1 个结点，检查有关参数的合理性；个结点，检查有关参数的合理性； 查找第查找第i-1i-1个结点并由指针个结点并由指针prepre指示，指示， 生成一个新结点；生成一个新结点； 使新结点数据域的值为使新结点数据域的值为 e e； 将新结点插入到单链表中；将新结点插入到单链表中； 修改第修改第 i i-1 -1 个结点的指针域。个结点的指针域。 46 5. 5.单链表的插入元素算法单链表的插入元素算法 47 L L a a1 1 a a i i a an n a a i i-1-1 prepre s s- - next=next=prepre- - nextnext prepre- - next=next=s s s s e e IntInt InsListInsList( ( LinkListLinkList L, L, intint i, i, ElemTypeElemType e ) e ) /*/*在带头结点单链表在带头结点单链表 L L 中第中第 i i 个位置前插入个位置前插入 e e。11i i 表长表长+1+1。 Node *pre,*s; Node *pre,*s; intint k; k; /* /* k k 为计数器，初始为为计数器，初始为 0*/0*/ if (inext; k+; next; k+; /* /* 顺指针向后查找，直到顺指针向后查找，直到 prepre 指向第指向第 i i1 1 个元素或个元素或 p prere为空为空* */ / if ( ! pre | k i-1 ) if ( ! pre | k i-1 ) /* /* i i1 1 或表长或表长+1*/+1*/ printfprintf(“(“插入位置不合理插入位置不合理!”);!”); return ERROR;return ERROR; s = ( Node* ) s = ( Node* ) mallocmalloc ( ( sizeofsizeof ( ( LNodeLNode ) ); ) ); /* /* 生成新结点生成新结点* */ / 48(2) (2) 算法编写算法编写 49 s-data = e;s-data = e;/*/*将将 e e 放入新结点数据域放入新结点数据域* */ / s-next = pre-next; s-next = pre-next; /* /* 将新结点插入表将新结点插入表 L L 中中* */ / p-next = s; p-next = s;/* /* 修改第修改第 i i-1-1 个结点指针个结点指针* * return OK;return OK; /*/*InsListInsList*/*/ (3) (3) 算法分析算法分析 算法算法InsListInsList的基本操作是：在插入之前，需要找到第的基本操作是：在插入之前，需要找到第 i i-1-1 个结个结 点，从算法点，从算法 Get Get 的讨论中我们可以得知，算法的讨论中我们可以得知，算法InsListInsList的时间复杂度的时间复杂度 为为 O O( (n n) )。 (1) (1) 算法思想算法思想 假设要在线性表中删除数据元素假设要在线性表中删除数据元素 a a i i 。 寻找第寻找第 i i-1 -1 个结点，并由个结点，并由prepre指示指示, , 指示检查有关参数的合理性；指示检查有关参数的合理性； 用一个指针用一个指针r r指向被删除结点；指向被删除结点； 删除第删除第 i i 个结点，即修改第个结点，即修改第 i i-1 -1 个结点的指针；个结点的指针； 释放第释放第 i i 个结点。个结点。 50 6. 6.单链表的删除元素算法单链表的删除元素算法 prepre prepre-next = next = prepre-nextnext-nextnext 51 r L L a a1 1 a a i i+1+1 a an n a a i i-1-1 aiai r IntInt DelListDelList( ( LinkListLinkList L, L, intint i, i, ElemTypeElemType *e ) *e ) /* /* 在带头结点的单链表在带头结点的单链表 L L 中，删除第中，删除第 i i 个元素，并由个元素，并由 e e 返回其值。返回其值。* */ / /* /* 11i i 表长。表长。* */ / Node *pre, *r; Node *pre, *r; intint k; k; pre = L; pre = L; k = 0; k = 0; * *初始化，初始化，prepre 指向头结点指向头结点, , k k 为计数器，初始为为计数器，初始为0*/0*/ while ( prewhile ( pre- -next!=NULL k+; next; k+; /* /* 顺指针向后查找，直到顺指针向后查找，直到 prepre 指向第指向第 i i1 1 个元素或个元素或 prepre- -next next 为空为空 if ( ! preif ( ! pre- -next )next ) printfprintf(“(“删除位置不合理删除位置不合理” ”) ;return ERROR;) ;return ERROR;/* /* 删除位置不合理删除位置不合理* */ / r= pre r= pre- -next;next;/* /* 用用r r 指向第指向第 i i 个结点个结点* */ / pre pre- -next = rnext = r- -next; next; /*/*删除第删除第 i i 个结点个结点r*/r*/ e = r e = r- -data; data; /* /* 取出第取出第 i i 个结点数据个结点数据* */ / free (r);free (r);/* /* 释放第释放第 i i 个结点个结点* */ / return OK; return OK; /* /*DelListDelList*/*/ 52(2) (2) 算法编写算法编写 free(rfree(r) ) 的作用是由系统回收一个的作用是由系统回收一个 Node Node 型型 的结点，回收后的空间可以备作再次生成结点的结点，回收后的空间可以备作再次生成结点 时使用，因此，单链表和顺序存储结构不同，时使用，因此，单链表和顺序存储结构不同， 它是一种动态结构。整个可用存储空间可以为它是一种动态结构。整个可用存储空间可以为 多个单链表共同享用，每个单链表占用的空间多个单链表共同享用，每个单链表占用的空间 不需要预先分配划定，可以由系统应需求即时不需要预先分配划定，可以由系统应需求即时 生成。生成。 (3) (3) 算法分析算法分析 算法的基本操作是：在删除之前，需要找到第算法的基本操作是：在删除之前，需要找到第 i-1 i-1 个结点个结点， 从算法从算法GetGet的讨论中，我们可以得知，算法的讨论中，我们可以得知，算法DelListDelList的时间复杂度的时间复杂度 为为 O O( (n n) )。 53 循环链表（循环链表（circular circular linked linked listlist）是另一种形式的链式存储结是另一种形式的链式存储结 构。循环链表的特点是：表中最后一个结点的指针域指向头结点构。循环链表的特点是：表中最后一个结点的指针域指向头结点 ，整个链表形成一个环。由此，由表中任一结点出发均可以找到，整个链表形成一个环。由此，由表中任一结点出发均可以找到 表中其他的结点。表中其他的结点。 在有些应用问题中，用循环链表可以使操作更加方便灵活。在有些应用问题中，用循环链表可以使操作更加方便灵活。 为了和单链表一致，在循环链表中也设置一个头结点。为了和单链表一致，在循环链表中也设置一个头结点。 空循环链表仅由一个头结点组成，并自成循环。空循环链表仅由一个头结点组成，并自成循环。 54 2.3.3 2.3.3 循环链表循环链表 5 L L 311 非空非空循环链表循环链表 L L 空循环链表空循环链表 55 56 循环链表的操作和线性链表的操循环链表的操作和线性链表的操 作基本一致，差别仅在于算法中的循作基本一致，差别仅在于算法中的循 环条件不是判断环条件不是判断 p p 或或 p p- -next next 是否为空是否为空 ，而是判断它们是否等于头指针（即，而是判断它们是否等于头指针（即 p p = = L L 或或 p p- -next = next = L L）。）。 例 2-3 LinkList merge_1(LinkList LA,LinkList LB) /此算法将两个采用头指针的循环单链表首尾连接起来 Node *p,*q; p=LA; q=LB; While (p-next!=LA) p=p-next;While (p-next!=LA) p=p-next; While (q-next!=LB) q=q-next;While (q-next!=LB) q=q-next; q-next=LA;q-next=LA; p-next=LB-next;p-next=LB-next; free(LBfree(LB); ); return(LAreturn(LA); ); / / merge_1 58 在单链表或循环链表结构的结点中，只有一个指示直接后继在单链表或循环链表结构的结点中，只有一个指示直接后继 结点的指针域，因此，从某个结点出发只能顺着指针往后寻查其结点的指针域，因此，从某个结点出发只能顺着指针往后寻查其 他结点。如果要寻查结点的直接前驱结点，则需要从表头指针出他结点。如果要寻查结点的直接前驱结点，则需要从表头指针出 发。换句话说，在单链表中，发。换句话说，在单链表中，NextElemNextElem 算法的执行时间为算法的执行时间为 O O(1)(1)， 而而 PriorElemPriorElem 算法的执行时间为算法的执行时间为 O O( (n n) )。为了克服这种单向性的缺为了克服这种单向性的缺 点，可以利用双向链表。点，可以利用双向链表。 2.3.4 2.3.4 双向链表双向链表 1. 1. 双向链表的存储表示双向链表的存储表示 (1) (1) 结点结点 在双向链表在双向链表 (double (double linked linked list) list) 中，每个结点应该包括中，每个结点应该包括 3 3 个部个部 分：分：数据域数据域 (data)(data)、前向指针域前向指针域 (prior)