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

1、第二章第二章 线性表线性表 题目一：狐狸逮兔子实验题目一：狐狸逮兔子实验 【问题描述】【问题描述】 围绕着山顶有围绕着山顶有1010个圆形排列的洞，狐狸要吃兔个圆形排列的洞，狐狸要吃兔 子，兔子说：子，兔子说：“可以，但必须找到我，我就藏可以，但必须找到我，我就藏 身于这十个洞中，你先到号洞找，第二次隔身于这十个洞中，你先到号洞找，第二次隔 个洞（即个洞（即3 3号洞）找，第三次隔个洞（即号洞）找，第三次隔个洞（即6 6 号洞）找，以后如此类推，次数不限。号洞）找，以后如此类推，次数不限。”但狐但狐 狸从早到晚进进出出了狸从早到晚进进出出了10001000次，仍没有找到兔次，仍没有找到兔 子。

2、问兔子究竟藏在哪个洞里？子。问兔子究竟藏在哪个洞里？ 学习目标学习目标 l掌握线性表的顺序存储结构及掌握线性表的顺序存储结构及 具体操作实现；具体操作实现； l掌握线性表的单、双向链接存掌握线性表的单、双向链接存 储结构及具体操作实现；储结构及具体操作实现； l掌握算法时间复杂度分析。掌握算法时间复杂度分析。 线性结构线性结构的定义：的定义： 若结构是非空有限集，则有且仅有一个开始若结构是非空有限集，则有且仅有一个开始 结点和一个终端结点，并且所有结点都最多只结点和一个终端结点，并且所有结点都最多只 有一个直接前趋和一个直接后继。有一个直接前趋和一个直接后继。 可表示为：可表示为： （a1 ,

3、 a2 , , an） 特点：特点： 1集合中必存在唯一的一个集合中必存在唯一的一个“第一元素第一元素”； 2集合中必存在唯一的一个集合中必存在唯一的一个 “最后元素最后元素” ； 3除最后元素在外，均有除最后元素在外，均有 唯一的后继唯一的后继； 4除第一元素之外，均有除第一元素之外，均有 唯一的前驱唯一的前驱。 简言之，线性结构反映结点间的逻辑关简言之，线性结构反映结点间的逻辑关 系是系是 的。的。 线性结构包括：线性结构包括：线性表、堆栈、队列、线性表、堆栈、队列、 字符串、数组字符串、数组等，其中最典型、最常等，其中最典型、最常 用的是用的是- 一对一一对一 (1:1) 2.1 线性表

4、的类型定义线性表的类型定义 2.3 线性表类型的实现线性表类型的实现 链式映象链式映象 2.2 线性表类型的实现线性表类型的实现 顺序映象顺序映象 2.1 线性表的类型定义线性表的类型定义 2.1 线性表的基本概念线性表的基本概念 、线性表线性表 它是一种最简单的线性结构。是一它是一种最简单的线性结构。是一 种可以在任意位置进行插入和删除数据种可以在任意位置进行插入和删除数据 元素操作的，由元素操作的，由n（n0)个个相同类型相同类型数据数据 元素元素a0, a1, , an-1组成的线性结构。组成的线性结构。 （a0, a1, ai-1， ，ai, ai1 ， ，, an-1） 线性表的逻辑

5、结构：线性表的逻辑结构： n=0时称为时称为 数据元素数据元素 线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继 下标，下标，是元素的是元素的 序号，表示元素序号，表示元素 在表中的位置在表中的位置 n为元素总为元素总 个数，即表个数，即表 长。长。 空表空表 线性终点线性终点 （ a, b, c, d, , z） 学号学号姓名姓名性别性别年龄年龄班级班级 012003010622陈建武陈建武男男 192003级信息级信息0301班班 012003010704赵玉凤赵玉凤女女 182003级信息级信息0302班班 012003010813王王 泽泽男男 192003级信息级信息

6、0303班班 012003010906薛薛 荃荃男男 192003级信息级信息0304班班 012003011018王 春男 19 192003级信息级信息0305班班 ： ： 例例2 分析学生情况登记表是什么结构。分析学生情况登记表是什么结构。 分析分析：数据元素都是同类型（数据元素都是同类型（记录记录），元素间关系是线性的。），元素间关系是线性的。 分析分析： 数据元素都是同类型（数据元素都是同类型（字母字母），）， 元素间关系是线性的。元素间关系是线性的。 例例1 分析分析26 个英文字母组成的英文表是什么结构。个英文字母组成的英文表是什么结构。 抽象数据类型线性表线性表的定义如下： a

7、dt list 数据对象数据对象： d ai | ai elemset, i=1,2,.,n, n0 数据关系数据关系： r1 |ai-1 ,aid, i=2,.,n 基本操作：基本操作： 结构初始化操作结构初始化操作 结构销毁操作结构销毁操作 引用型操作引用型操作 加工型操作加工型操作 adt list initlist( 2依值在线性表la中进行查访; 3若不存在，则插入之。 getelem(lb, i)e locateelem(la, e, equal( ) listinsert(la, n+1, e) 操作步骤：操作步骤： getelem(lb, i, e); / 取取lb中第中第i个

8、数据元素赋给个数据元素赋给e if (!locateelem(la, e, equal( ) ) listinsert(la, +la_len, e); / la中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 void union(list / 求线性表的长度求线性表的长度 lb_len = listlength(lb); for (i = 1; i = lb_len; i+) / union 已知已知一个非纯集合非纯集合 b，试构造构造一个 纯集合纯集合 a，使使 a中只包含中只包含 b 中所有值各中所有值各 不相不相 同的数据元素同的数据元素。 仍选用线性表线性

9、表表示集合。 例例 2-2 集合集合 b集合集合 a 从集合 b 取出物件放入集合 a 要求集合a中同样物件不能有两件以上同样物件不能有两件以上 因此，算法的策略应该和例算法的策略应该和例2-1相同相同 void union(list lb_len=listlength(lb); / union getelem(lb, i, e); / 取取lb中第中第 i 个数据元素赋给个数据元素赋给 e if (!locateelem(la, e, equal( ) ) listinsert(la, +la_len, e); / la中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入

10、之 for (i = 1; i = lb_len; i+) initlist(la); / 构造(空的)线性表la 若线性表中的数据元素相互之间可以比比 较较，并且数据元素在线性表中依值非递依值非递 减或非递增有序减或非递增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)， 则称该线性表为有序表有序表(ordered list)(ordered list)。 试改变结构，以有序表有序表表示集合。 例如例如：如果集合 b ， （2，3，3，5，6，6，6，8，12） 对集合 b 而言， 值相同的数据元素必定相邻；值相同的数据元素必定相邻； 如果构造一个纯集合 a，对集合 a

11、而言， 数据元素依值从小至大的顺序插入。数据元素依值从小至大的顺序插入。 因此，数据结构改变了，数据结构改变了， 解决问题的策略也相应要改变。解决问题的策略也相应要改变。 void purge(list la_len = listlength(la); lb_len =listlength(lb); / 求线性表的长度求线性表的长度 for (i = 1; i = lb_len; i+) / purge getelem(lb, i, e); / 取取lb中第中第i个数据元素赋给个数据元素赋给 e if (listempty(la) | !equal (en, e) listinsert(la,

12、 +la_len, e); en = e; / la中不存在和中不存在和 e 相同的数据元素，则插入之相同的数据元素，则插入之 线性表的存储结构是指为它开辟的计算机线性表的存储结构是指为它开辟的计算机 存储空间、存储空间的联系以及所采用的存储空间、存储空间的联系以及所采用的 程序实现方法。线性表的存储结构主要有程序实现方法。线性表的存储结构主要有 如下两类：如下两类： (1)顺序存储结构顺序存储结构 (2)(2)链式链式存储结构存储结构 2.22.2 线性表类型的实现线性表类型的实现 顺序映像顺序映像 1、用一组地址连续地址连续的存储单元 依次存放依次存放线性表中的数据元素 （逻辑关系相邻（逻

13、辑关系相邻, , 物理位置相邻。）物理位置相邻。） a1 a2 ai-1 ai an 线性表的线性表的起始地址起始地址 称作线性表的基地址基地址 (1) 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻； (2) 若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元 素存放位置亦可求出素存放位置亦可求出。 设首元素设首元素a0的存放地址为的存放地址为loc(a0)（称称为首地址为首地址），）， 设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为l字节，字节， 则表中任一数据元素的则表中任一数据元素的存放地址存放地址

14、为：为： loc ( ai+1 ) = loc( ai ) + l 对上述公式的解释如图所示对上述公式的解释如图所示 2、线性表顺序存储特点： a a0 0 a a1 1 a ai i a ai i+1 +1 a an-1 n-1 地址地址 内容内容 元素在表中的位序元素在表中的位序 0 0 i i 1 1 n-1n-1 空闲区空闲区 i+1i+1 l b=loc(a0) b + + l l b +i+il l b +(n-1)+(n-1)l l b +(maxsize+(maxsize-1)-1)l l 3、线性表的顺序存储结构示意图、线性表的顺序存储结构示意图 4、顺序映像的、顺序映像的

15、c 语言描述语言描述 typedef struct sqlist; / 俗称 顺序表顺序表 #define list_init_size 80 / 线性表存储空间的初始分配量 #define listincrement 10 / 线性表存储空间的分配增量 elemtype *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量 / (以sizeof(elemtype)为单位) 5、线性表的基本操作在顺序表中的实现、线性表的基本操作在顺序表中的实现 initlist( if (!l.elem) exit(overflow); l.

16、length = 0; l.listsize = list_init_size return ok; 定位：判断某个元素是否存在，存在给出其定位：判断某个元素是否存在，存在给出其 位置，否则为位置，否则为0 0 23 75 41 38 54 62 17 l.elem l.length l.listsize e =38 ppppp i 1 2 3 4 1 8 50 p 可见，基本操作是： 将顺序表中的元素 逐个和给定值 e 相比较。 int locateelem_sq(sqlist l, elemtype e, status (*compare)(elemtype, elemtype) / 在顺

17、序表中查询第一个满足判定条件的数据元素，在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回若存在，则返回它的位序，否则返回 0 0 / locateelem_sq o( listlength(l) ) 算法的算法的时间复杂度时间复杂度为：为： i = 1; / i i 的初值为第的初值为第 1 1 元素的位序元素的位序 p = l.elem; / p p 的初值为第的初值为第 1 1 元素的存储位置元素的存储位置 while (i = l.length if (i = l.length) return i; else return 0; (*compare)(*

18、p+, e) int locateelem_sq(sqlist l, elemtype e,) p=l.elem; for(i=1;i=l.length;i+) if(*p+=e) return i; else return 0; / locateelem_sq 时间复杂性：时间复杂性：( (找到找到) ) 最好最好 1 1次次 o(1)o(1) 最坏最坏 n n次次 o(n)o(n) 平均平均 n/2n/2次次 o(n)o(n) (找不到找不到) ) 最好最好 n+1n+1次次 o(n)o(n) 最坏最坏 n+1n+1次次 o(n)o(n) 平均平均 n+1n+1次次 o(n)o(n) 线性

19、表操作 listinsert( / q 指示插入位置 for (p = p = q; -p) *(p+1) = *p; / 插入位置及之后的元素右移元素右移 *q = e; / 插入e +l.length; / 表长增1 return ok; 元素右移元素右移 21 18 30 75 42 56 87 21 18 30 75 例如：listinsert_sq(l, 5, 66) l.length-1 0 ppp q 87564266 q = / q 指示插入位置 for (p = p = q; -p) *(p+1) = *p; *q = 66; / / 插入插入e e p 线性表操作 list

20、delete( p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移被删除元素之后的元素左移 -l.length; / 表长减表长减1 1 return ok;算法时间复杂度算法时间复杂度为为: : o( listlength(l) p = / p 为被删除元素的位置为被删除元素的位置 e = *p; / 被删除元素的值赋给被删除元素的值赋给 e q = l.elem+l.length-1; / 表尾元素的位置表尾元素的位置 if (i l.length) return error; / 删除位置不合法删除位置不合法 元素左移元素左移 21 18 30 75 42 56

21、 87 21 18 30 75 l.length-1 0 ppp q 8756 p = q = l.elem+l.length-1; for (+p; p if(l-lenghthlenghth = =0) return(0); / = =0) return(0); /空表则结束空表则结束 else else for( i=0; ilenghth-1; i+) for( i=0; ilenghth-1; i+) if (l-elemi0) if (l-elemi0) l- elemi- zerosum= l- elemi; l- elemi- zerosum= l- elemi; else z

22、erosum+; else zerosum+; for( i= l-lenghth -zerosum;ilenghth; for( i= l-lenghth -zerosum;ilenghth; i+)i+) l-elem l-elemi=0; /i=0; /表的后部补表的后部补0 0 6 6、其它一些操作实现、其它一些操作实现 1、 清空操作清空操作 void clearlist(sqlist 删除删除l中所有元素，使之成为一个中所有元素，使之成为一个 空表空表 2. 判空操作判空操作 bool listempty(sqlist / if （l. length =0） / return tr

23、ue; / else return false; 若若l为空表，返回真，否则返回假为空表，返回真，否则返回假 3、有关查表的操作、有关查表的操作 1.遍历一个线性表遍历一个线性表 void traverselist(sqlist il. length-1; i+) coutl.elemi; coutendl; 依次访问依次访问l中每一个元素一次中每一个元素一次 2. 查找指定序号的元素查找指定序号的元素 elemtype getelem(sqlist j = 1; / p p指向第一个结点，指向第一个结点，j j为计数器为计数器 while (p +j; / 顺指针向后查找，直到顺指针向后查找

24、，直到 p p 指向第指向第 i i 个元素个元素 / 或或 p p 为空为空 if ( !p | ji ) return error; / 第第 i i 个元素不存在个元素不存在 e = p-data; / 取得第取得第 i i 个元素个元素 return ok; ai-1 线性表的操作 listinsert( j = 0; while (p +j; / 寻找第寻找第 i-1 个结点个结点 if (!p | j i-1) return error; / i 大于表长或者小于大于表长或者小于1 s = (linklist) malloc ( sizeof (lnode); / 生成新结点 s-

25、data = e; s-next = p-next; p-next = s; / 插入 return ok; e ai-1aiai-1 s p 线性表的操作listdelete ( p-next = q-next; e = q-data; free(q); p q status listdelete_l(linklist l, int i, elemtype j = 0; while (p-next +j; / 寻找第 i 个结点，并令 p 指向其前趋 if (!(p-next) | j i-1) return error; / 删除位置不合理 q = p-next; p-next = q-n

26、ext; / 删除并释放结点 e = q-data; free(q); return ok; 操作 clearlist( while (p) p=l-next; l-next=p-next; / clearlist free(p); 算法时间复杂度：o(listlength(l) 如何从线性表得到单链表？如何从线性表得到单链表？ 链表是一个动态的结构，它不需要预分配空链表是一个动态的结构，它不需要预分配空 间，因此间，因此生成链表的过程生成链表的过程是一个结点是一个结点“逐个逐个 插入插入” ” 的过程。的过程。 实现思路：实现思路：先开辟头指针，然后陆续为每个结先开辟头指针，然后陆续为每个结

27、 点开辟存储空间并及时赋值，后继结点的地址点开辟存储空间并及时赋值，后继结点的地址 要要提前提前送给前面的指针。送给前面的指针。 先挖先挖“坑坑”, ,后种后种“萝萝 卜卜”！ 新手特别容易忘记！新手特别容易忘记！ l = (linklist) malloc (sizeof (lnode); l-next = null; / 先建立一个带头结点的单链表 p=l; for( i=1; inext= (linklist) malloc (sizeof (lnode); p=p-next； /让指针变量让指针变量p指向后一个结点指向后一个结点 cinp-data; /输入数据输入数据 p-next=

28、null ; / /单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！ void createlist_l(linklist l-next = null; / 先建立一个带头结点的单链表 for (i = n; i 0; -i) p = (linklist) malloc (sizeof (lnode); cinp-data; / 输入元素值 p-next = l-next; l-next = p; / 插入 作业：作业： 用单链表结构来存放用单链表结构来存放2626个英文字母组成个英文字母组成 的线性表（的线性表（a a，b b，c c，z z）, ,请写出请写出 完整的完整的c/c+

29、c/c+语言程序。语言程序。 四、用单链表实现线性表上其它的操作四、用单链表实现线性表上其它的操作 1. 1. 初始化单链表初始化单链表 void initlist(lnodevoid initlist(lnode* * /o(1) hl=null; /o(1) 2. 2. 检查单链表是否为空检查单链表是否为空 bool listempty(lnodebool listempty(lnode* * hl) hl) return (hl=null); return (hl=null); / o(1) / o(1) 3. 3. 删除单链表中结点，使之成为空表删除单链表中结点，使之成为空表 void

30、 clearlist(lnodevoid clearlist(lnode* * ; cp=hl; cp=hl; while(cp!=null) while(cp!=null) np=cp-next;cp-next=np np=cp-next;cp-next=np-next;-next; delete cp; delete cp; hl=null; hl=null; /o(n) /o(n) 4. 4. 得到单链表的长度得到单链表的长度 int listsize(lnodeint listsize(lnode* * hl) / hl) /带头结点带头结点 p=hl-next; p=hl-next;

31、 int int i=0; i=0; while(p!=null) while(p!=null) i+; i+; p = p -next; p = p -next; return i; return i; /o(n) /o(n) 5. 5. 得到单链表中第得到单链表中第pospos个结点中的元素个结点中的元素 elemtype getelem(lnodeelemtype getelem(lnode* * hl, int hl, int pos) pos) if(pos1) if(pos1) cerrpos is out range!endl cerrpos is out range!next;

32、 i=0; p=hl-next; while(p!=null) while(p!=null) i+; i+; if(i=pos) break; if(i=pos) break; p = p -next; p = p -next; if(p!=null) return p -data; if(p!=null) return p -data; else cerrpos is out range!endl else cerrpos is out range!next;p=hl-next; while( while(p p!=null) !=null) cout coutdata ;datanext;

33、 -next; coutendl coutdata=item) if (p-data=item) return i; return i; else p=p-next;i+; else p=p-next;i+; return false; return false; o(n) o(n) 五、单链表的操作效率分析五、单链表的操作效率分析 （1 1） 查找查找 ：因线性链表只能顺序存取，即在查找时：因线性链表只能顺序存取，即在查找时 要从头指针找起，查找的时间复杂度为要从头指针找起，查找的时间复杂度为 o(n)o(n)。 时间效率分析时间效率分析 （2 2） 插入和删除：因线性链表不需要移动元素，只

34、要插入和删除：因线性链表不需要移动元素，只要 修改指针，仅就插入或删除而言，时间复杂度为修改指针，仅就插入或删除而言，时间复杂度为 o(1)o(1)。 但是，如果要在单链表中进行在某结点但是，如果要在单链表中进行在某结点前前插或删插或删 除操作，因为要除操作，因为要从头查找前驱从头查找前驱结点，所以一般情结点，所以一般情 况下，况下，单链表插入和删除操作单链表插入和删除操作的时间复杂度是的时间复杂度是 o(n)（同顺序表）。（同顺序表）。 1. 双向链表双向链表 六、其它形式的链表六、其它形式的链表 typedef struct dulnode elemtype data; / 数据域 str

35、uct dulnode *prior; / 指向前驱的指针域 struct dulnode *next; / 指向后继的指针域 dulnode, *dulinklist; 双向链表双向链表：链表中每个结点除后继指针域和数据域链表中每个结点除后继指针域和数据域 外还有一个前驱指针域。外还有一个前驱指针域。 最后一个结点的指针域的指针又指 回第一个结点的链表 a1 a2 . an 2. 循环链表循环链表 和单链表的差别仅在于，判别链表中 最后一个结点的条件不再是“后继是否 为空”，而是“后继是否为头结点”。 双向循环链表双向循环链表 空表空表 非空表非空表 a1 a2 . an 双向链表的操作特点

36、：双向链表的操作特点： “查询查询” ” 和单链表相同。和单链表相同。 “插入插入” ” 和和“删除删除”时需要同时修时需要同时修 改两个方向上的指针。改两个方向上的指针。 ai-1ai e s-next = p-next; p-next = s; s-next-prior = s; s-prior = p; p s ai-1ai 插入插入 ai-1 删除删除 aiai+1 p-next = p-next-next; p-next-prior = p; p ai-1 七、七、 静态链表静态链表 静态链表：静态链表：在数组中增加一个（或两在数组中增加一个（或两 个）指针域，这些指针域用来存放个）

37、指针域，这些指针域用来存放 下一个（或上一个）数据元素在数下一个（或上一个）数据元素在数 组中的下标，从而构成用数组构造组中的下标，从而构成用数组构造 的单链表（或双链表）。静态链表的单链表（或双链表）。静态链表 中的指针又称仿真指针。中的指针又称仿真指针。 # #define maxsize 1000 define maxsize 1000 /预分配最大的元素个数（连续空间预分配最大的元素个数（连续空间 typedef typedef struct struct datatype datatype data ; data ; /数据域数据域 int int next ; next ; /指示

38、域指示域 component , slinklistcomponent , slinklistmaxsizemaxsize ; ; /这是一维结构型数组这是一维结构型数组 例例 2：一：一线性表线性表 s = ( zhao, qian, sun, li, zhou, wu )，用静态链表如何表示？，用静态链表如何表示？ data 3 5 6 0 4 2 next 说明说明1 1：假设假设s s为为slinklistslinklist型变量，则型变量，则 smaxsizesmaxsize 为一个静态链表；为一个静态链表； s0.nexts0.next则表示第则表示第1 1个结点在数组中的个结点在

39、数组中的 位置。位置。 说明说明2 2：如果数组的第如果数组的第i i个分量表示链表个分量表示链表 的第的第k k个结点，则：个结点，则： si.datasi.data表示第表示第k k个结点的数据；个结点的数据； si.nextsi.next 表示第表示第k+1k+1个结点个结点( (即即k k的直的直 接后继接后继) )的位置。的位置。 i 说明说明3 3：静态链表的插入与删除操作与普通链表一样，不需要移静态链表的插入与删除操作与普通链表一样，不需要移 动元素，只需修改指示器就可以了。动元素，只需修改指示器就可以了。 例如：在线性表例如：在线性表 s = ( zhao, qian, sun

40、, li, zhou, wu )的的 qian, sun之间之间liu，可以这样实现：，可以这样实现： step2:step2:将将qianqian的游标换为新元素的游标换为新元素liuliu的的 下标：下标： step1:step1:将将qianqian的游标值存入的游标值存入nextnext的游的游 标中：标中： data 2 4 0 6 5 3 curi 本章小结本章小结 1.1.线性结构线性结构( (包括表、栈、队、数组）的定义和特点包括表、栈、队、数组）的定义和特点： 仅一个首、尾结点，其余元素仅一个直接前驱和一个仅一个首、尾结点，其余元素仅一个直接前驱和一个 直接后继。直接后继。 2. 2. 线性表线性表 逻辑结构逻辑结构：“一对一一对一” ” 或或 “ “1:1”1:1” 存储结构：存储结构：顺序、链式顺序、链式 运运 算：算：修改、插入、删除修改、插入、删除 查找和排序另述查找和排序另述 3.3.顺序存储顺序存储 特征特征：逻辑上相邻，物理上也相邻；逻辑上相邻，物理上也相邻； 优点：优点：