数据结构-02线性表

1、数据结构数据结构线性表结构第二章第二章本章主要内容本章主要内容线性表的基本概念线性表的基本概念1线性表的顺序存储结构线性表的顺序存储结构2线性表的链式存储结构线性表的链式存储结构3线性表结构的应用线性表结构的应用42.1 线性表的基本概念线性表的基本概念A=（a1, a2, ai-1，ai, ai1 ，, an）1. 线性表的定义：线性表的定义：是是n个同类结点的有限序列。个同类结点的有限序列。n=0时称为时称为空表空表数据元素数据元素始始(首首)结点结点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的序是元素的序号，表示元素在表号，表示元素在表中的位置中的位置n为元素总个

2、数，为元素总个数，即表长即表长终终(尾尾)结点结点v线性表的逻辑结构特点线性表的逻辑结构特点除第一个之外的数据元素均只有一个直接前驱除第一个之外的数据元素均只有一个直接前驱 存在唯一的一个被称作存在唯一的一个被称作“第一个第一个”的数据元素的数据元素 除最后一个之外的数据元素均只有一个直接后继除最后一个之外的数据元素均只有一个直接后继 数据元素的数据元素的 非空有限集非空有限集 存在唯一的一个被称作存在唯一的一个被称作“最后一个最后一个”的数据元素的数据元素线性表可以看作是除第一个元素无前驱,最后一个元素无后继外,其余元素都有唯一的直接前驱和直接后继的元素构成的集合2.1.1 线性表举例线性表

3、举例v 例例2 22 2：学生成绩登记表：学生成绩登记表学号学号姓名姓名政治政治成绩成绩数学数学成绩成绩英语英语成绩成绩信息技信息技术成绩术成绩数据结数据结构成绩构成绩210806101陈敏敏7883689277210806102李学好8386868467210806103顾家新6594977891210806104黄玲玲90100756690210806105柯向民10079837374210806106王怀国7277619568210806107徐晶晶5684649979210806108余美美9873888777210806109张全理8899918588线性表中的数据元素可以是各种各样

4、的，但同一线性线性表中的数据元素可以是各种各样的，但同一线性 表中的元素必定具有相同特性（属于同一数据对象）。表中的元素必定具有相同特性（属于同一数据对象）。分析：数据元素分析：数据元素( (结点、记录结点、记录) )由由7 7个数据项个数据项( (字段、域字段、域) )组成。组成。v 例例2 21 1：1 1到到3030之间的质数序列是一个线性表之间的质数序列是一个线性表 P=( P=(2 2，3 3，5 5，7 7，1111，1313，1717，1919，2323，2929) )分析：分析： 数据元素都是质数，数据元素都是质数， 元素间关系是线性的，元素间关系是线性的， 表长是表长是111

5、1判断指定线性表是否是空表。若为空则返回判断指定线性表是否是空表。若为空则返回1 1，否则返回，否则返回0 0置指定线性表置指定线性表L L成空表，即清除所有原有的结点，并返回成空表，即清除所有原有的结点，并返回L L 2.1.2 线性表的基本操作线性表的基本操作同一种操作在数据的不同物理结构下，执行过程不同线性表的常用操作：线性表的常用操作：注意：注意：建立一个空线性表建立一个空线性表L L（即建立一个线性表结构）（即建立一个线性表结构）, ,并返回并返回L L统计指定线性表统计指定线性表L L中当前结点个数，并返回个数中当前结点个数，并返回个数用给定值用给定值x，在指定线性表，在指定线性表

6、L中查找与中查找与x等值的结点。等值的结点。若存在则返回结点位置信息。若存在则返回结点位置信息。给定结点数据给定结点数据x和整数和整数i，向指定线性表向指定线性表L中第中第i个位置插入结点数据为个位置插入结点数据为x的新结点的新结点给定数据给定数据x和整数和整数i,用用x替换指定线性表替换指定线性表L中第中第i个结点的原数个结点的原数据，使其有新值据，使其有新值给定结点序号给定结点序号i，从指定线性表，从指定线性表L中读出并返回该结点数据中读出并返回该结点数据从指定线性表从指定线性表L中删去第中删去第i个结点。个结点。把两个指定线性表把两个指定线性表L1和和L2，按规定的要求连接成一个线性表，

7、按规定的要求连接成一个线性表 2.1.2 线性表的基本操作线性表的基本操作2.2 线性表的顺序存储结构线性表的顺序存储结构a2a3a1an.已已用用区区段段空空闲闲区区段段An+1A1A2AnAm把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。足够大小、地址连续的单元构成的一个存储空间片。线性表的结点按它的逻辑结构顺序一个接一个地依次存储 。2.2.1 顺序表中元素存储位置的计算顺序表中元素存储位置的计算线性表的第 1 个数据元素 a1从地址h h单元开始存储a1 a2 ai-1 ai ai+1 an h单元假设线性表的每个元素需占 b b个存储单

8、元，则第 i + 1 个 元素的存储位置和第 i 个元素的存储位置之间满足关系： LOC(ai +1) = LOC(ai ) + b由此，所有数据元素的存储位置均可通过基地址得到： LOC(ai ) = LOC(a1) + (i1) b=h+(i1)bh单元单元a2a3a1an.空空闲闲区区段段内存状态内存状态LOC(a1) LOC(a1)+b LOC(a1)+(n -1) b LOC(a1)+n b 存储地址存储地址123n数据元素在线数据元素在线 性表中的位序性表中的位序 顺序表的特点：以物理位置相邻表示逻辑关系顺序表的特点：以物理位置相邻表示逻辑关系 任一元素均可随机存取。任一元素均可随

9、机存取。 （优点）（优点）2.2.2 顺序表存储结构的顺序表存储结构的C语言描述语言描述用用C C的一维数组的一维数组 表示顺序表表示顺序表 类型相同类型相同 用一变量表示顺序用一变量表示顺序表的长度属性表的长度属性 线性表长可变（插入删除）线性表长可变（插入删除） 顺序表的特点顺序表的特点地址连续地址连续 随机存取随机存取 依次存放依次存放 一维数组一维数组 数组长度不可动态定义数组长度不可动态定义 #define m 100typedef struct int datam; int n; SEQUENLIST；说明：常量表达式中可以包含常量和说明：常量表达式中可以包含常量和 符号常量，符号

10、常量，不能包含变量不能包含变量。即。即 C 不允不允 许对数组的大小作动态定义。许对数组的大小作动态定义。 说明：说明：n表示顺序表的长度。表示顺序表的长度。 注意注意：区分元素的序号和数：区分元素的序号和数组的下标，如组的下标，如a1的序号为的序号为1，而其对应的数组下标为而其对应的数组下标为02.2.3 顺序表的操作顺序表的操作函数表示函数表示 操作含义操作含义 算法思路算法思路 算法描述算法描述 C C语言程序语言程序程序说明程序说明添加插入添加插入Phase 3uAPPEND(A，x) A A为顺序表名；为顺序表名； x x为新结点数据，为新结点数据， 可以是常数或变量可以是常数或变量

11、u要求把要求把x x作为一个新作为一个新结点插入到顺序表结点插入到顺序表A A的终结点的紧后一个的终结点的紧后一个位置位置u首先查看顺序表空闲区首先查看顺序表空闲区段是否还有空闲结点段是否还有空闲结点u若无则拒绝插入若无则拒绝插入( (称为称为上溢上溢); );否则把新结点存否则把新结点存储到插入位置储到插入位置u顺序表长度加顺序表长度加1 11.添加插入添加插入函函数数表表示示操操作作含含义义算算法法思思路路插入位置插入位置插入前：插入前： a1 a2 ai-1 ai ai+1 an-1 an A.mA.n插入后：插入后： a1 a2 ai-1 ai ai+1 an-1 an x A.mA.

12、n添加插入添加插入u APP1.上溢吗？上溢吗？若若n m ，则算法终止（失败），则算法终止（失败） u APP2.计算查入位置计算查入位置 n n + 1 u APP3.插入插入x An x ，算法终止（成功），算法终止（成功）算法描述算法描述 SEQUENLIST append(SEQUENLIST A,int x)if(A.n=m) printf(Overflow!n);else A.n+; A.dataA.n-1=x;return(A);C语言程序语言程序xA.datan+1A.data1A.data2A.datanA.datamA.data1.A.data2A.datan线性表线性表

13、A待插入数待插入数:x随机插入随机插入uINSSL(A，i，x) A A为顺序表名；为顺序表名； i i为指定的插入位置，为指定的插入位置， x x为新结点数据，常数为新结点数据，常数 或变量或变量u要求把要求把x x作为一个新结作为一个新结点插入到顺序表点插入到顺序表A A的第的第i1i1和第和第ii个结点之间的个结点之间的结点位置上结点位置上u首先查看位置号首先查看位置号i i是否合是否合法法u把第把第i i到第到第n n之间的所有之间的所有结点依次逐个向后移动结点依次逐个向后移动一个结点位置，使第一个结点位置，使第i i个个结点位置空出结点位置空出u把新结点存储到第把新结点存储到第i i

14、个结个结点位置上；并长度点位置上；并长度n n加加1 12.随机插入随机插入函数表示函数表示操作含义操作含义算法思路算法思路插入位置插入位置插入前：插入前：插入后：插入后：x a1 a2 ai-1 ai ai+1 an-1 an a1 a2 ai-1 ai ai+1 an-1 an A.mA.nA.n a1 a2 ai-1 ai ai+1 an-1 an 随机插入随机插入ISL1.插入非法？插入非法？ 若若n m 或或( i n + 1)， 则算法终止则算法终止(失败失败)；否则；否则 k n 。ISL2.移动结点移动结点 若若 k i，则，则Ak + 1 Ak，k k-1；转；转ISL2继续

15、继续 。ISL3.插入插入x Ai x ；n n+1；算法终止；算法终止(成功成功)算法思路算法思路 int a;if(iA.n+1|A.n=m) printf(i(location) is illegal!n); exit(0); a= A.n; for(;a=i;a-) A.dataa=A.dataa-1; A.datai-1=x; A.n+; return(A);C语言程序语言程序插入位插入位置置 an an-1 ai+1aixA.mA.n+1删除算法删除算法u DELSL(A，i) A A为顺序表名；为顺序表名； i i为结点位置号为结点位置号u要求把第要求把第ii个结点从顺序个结点从

16、顺序表中删除掉表中删除掉u首先查看顺序表空闲区首先查看顺序表空闲区段是否还有空闲结点段是否还有空闲结点u把第把第i+1i+1到第到第n n之间的所之间的所有结点依次逐个向前移有结点依次逐个向前移动一个结点位置动一个结点位置u并长度并长度减减1 13.删除算法删除算法函数表示函数表示操作含义操作含义算法思路算法思路要删除的结点要删除的结点删除前：删除前：删除后：删除后： a1 a2 ai-1 ai ai+1 an-1 an a1 a2 ai-1 ai an-1 an A.nA.nu DSL1.i合法吗？合法吗？ 若若i n，则算法终止（失败）；否则，则算法终止（失败）；否则 k i 。u DSL

17、2.移动结点移动结点 若若 k n，则，则Ak Ak + 1，k k+1；转；转DSL2继续。继续。u DSL3.长度减长度减1 n n-1；算法终止（成功）。；算法终止（成功）。算法思路算法思路 SEQUENLIST delsl(SEQUENLIST A,int i) if(iA.n) /*判断判断i值是否合法值是否合法*/ printf( is OverFlow !n); exit(0); /*非法算法终止非法算法终止*/ for (;i=A.n返回返回0合并算法合并算法u CONSL(A，B)其中其中，A A、 B B为顺序表为顺序表名名uA A、B B必须是同质的顺必须是同质的顺序表。

18、操作把序表。操作把A A、B B两两顺序表进行合并，顺序表进行合并，A A在在前前B B在后，并把合并结在后，并把合并结果仍存储在果仍存储在A A中中u首先要检测首先要检测A A的空闲区的空闲区段是否有足够的空间存段是否有足够的空间存储储B B的所有结点的所有结点u若无，则拒绝执行本操若无，则拒绝执行本操作作u若有，则把若有，则把B B中的所有中的所有结点逐个插入到结点逐个插入到A A的终的终结点紧后的空闲结点上结点紧后的空闲结点上5.合并算法合并算法函数表示函数表示操作含义操作含义算法思路算法思路顺序表顺序表A A：顺序表顺序表B B： a1 a2 ai an b1 b2 bi bk 合并后

19、合并后顺序表顺序表A A： a1 a2 ai an b1 b2 bi bk A.m合并算法合并算法 SEQUENLIST consl(SEQUENLIST A,SEQUENLIST B)int j; if(m-A.nB.n) /*判断判断A表空间是否足够表空间是否足够*/ printf( is OverFlow !n); exit(0); /*空间不够算法终止空间不够算法终止*/ for(j=0;jdata表示表示p指向结点的数据域指向结点的数据域(*p).linkp-next表示表示p指向结点的指针域指向结点的指针域对上述结构的改进对上述结构的改进 在单链单链表的首结结点前增加一个个附加结结

20、点，让让头头指针针始终终指向该该结结点 Data_1Data_2Data_nH头结点头结点称为头结点称为头结点带头结点的单链表带头结点的单链表H带头结点的空单链表带头结点的空单链表有头结点时，有头结点时，当头结点的指针域为空当头结点的指针域为空时表示空表时表示空表需要澄清的几个概念需要澄清的几个概念指针变量指针变量指针所指的结点指针所指的结点结点域结点域头结点头结点首结点首结点首指针首指针头指针头指针指针指针 结点的存储地址 存放指针的变量（如p），其值是指针 指针为地址存储的结点 构成结点的数据字段，包括指针域指向链表中第一个结点(头结点或首元结点)的指针.单链表可由它唯一确定在链表的首结点

21、之前附设的一个结点;数据域内只放标志等信息;是指链表中存储线性表第一个数据元素a1的结点指向首结点的指针（链表的头指针或头结点中的指针） 2.3.2单链表的操作单链表的操作链式结构链式结构很适合涉及到插入或删除的操作.合并合并删除删除定位定位按值、按号按值、按号创建创建头插头插,尾插尾插插入插入求表长度求表长度单链表单链表基本操作基本操作创建创建LINKLIST *inill() LINKLIST *L L=( LINKLIST *)malloc(sizeof(LINKLIST); L-next=NULL; L-data=-1; return(L);1.申请结点空间申请结点空间 new(L)。

22、2.设置头结点设置头结点 data(L) -1 ，next (L) “”。带头结带头结点点单链单链表初始化算法表初始化算法头插入法头插入法一、建立一个“空表”；二、输入数据元素a11，建立结点并在Q的首结点后插入；三、输入数据元素a2 1 ，建立结点并在Q的首结点插入；a1a1a2四、依次类推，直至输入1为止。p-next=Q-next;Q-next=p;程序见书中P程序22。Q1pp-data=a2;p1Q-next=p;1QQ尾插入法尾插入法一、建立一个“空表”；二、输入数据元素a11，建立结点并在Q的终结点后插入；a1Q1p1r-next=p;三、输入数据元素a2 1 ，建立结点并在Q的

23、终结点插入；rrQr=p;a11Qr a2p-data=a2;pp-next=NULL;r-next=p;r=p;四、依次类推，直至输入1为止。程序见书中P程序22。按号定位按号定位单链表中，为找第单链表中，为找第 i i 个数据元素，必须从单链表的头指针出发，沿着链指针方向对结点个数据元素，必须从单链表的头指针出发，沿着链指针方向对结点顺序逐个扫描、计数；当计数值等于顺序逐个扫描、计数；当计数值等于i i时，定位完成。时，定位完成。令指令指针针 p p 始始终终指向指向线线性表中第性表中第 j j 个数个数据元素据元素例如：例如：算法搜索表算法搜索表Q Q，找出第，找出第i i结结点的指点的

24、指针输针输出出 211830754256pppj1 2 3Qi=3因此，查找第因此，查找第 i 个数据元素的基本操作为：移动指针，比较个数据元素的基本操作为：移动指针，比较 j 和和 i 。程序见书中P。按值定位按值定位算法搜索表算法搜索表Q Q，找出，找出结结点点数数据据与与x x值值相等的相等的结结点，点，并输并输出出该结该结点指点指针针 当遇到结点数据与当遇到结点数据与x x 值相等时，或比较完所有结点时，即结束扫描。值相等时，或比较完所有结点时，即结束扫描。因此，查找值为因此，查找值为x x结点的基本操作为：移动指针，比较结点的基本操作为：移动指针，比较 p-datap-data和和

25、x x 。 211830754256Qx=30ppppppppppp p-data=x返回返回px=53p=NULL返回返回p例如：例如：程序见书中P。求表长求表长只要设一个移动指针沿着链指针方向对结点顺序逐个扫描、计数；当扫描完所有结点，计只要设一个移动指针沿着链指针方向对结点顺序逐个扫描、计数；当扫描完所有结点，计数完成。数完成。例如：例如：p p为为移移动动指指针针 ，j j为计数为计数器器统计单链统计单链表表L L中中结结点的点的个数个数，并输并输出出因此，求表长的基本操作为：移动指针，计数器自加因此，求表长的基本操作为：移动指针，计数器自加 。程序见书中P。211830754256p

26、ppj1 2 3Qppp4 5 6next(p)=,next(p)=,结束结束扫描，返回扫描，返回j j的值的值 插入插入xs s next = p next; p next = s; p ai ai 1 插入该新结点，使之成为单链表插入该新结点，使之成为单链表Q的第的第i个结点个结点 1u首先找到首先找到 ai -1 的存储位置的存储位置 p 2u生成一个数据域为生成一个数据域为 x 的新结点的新结点3u插入新结点：、结点插入新结点：、结点 ai -1的指针域指向新结点的指针域指向新结点 、新结点的指针域指向结点、新结点的指针域指向结点 ai 程序见书中P。删除删除把第把第i个结点从单链表个

27、结点从单链表Q中删除掉中删除掉1u 首先找到首先找到 ai -1 的存储位置的存储位置 p 2u 令令 pnext 指向指向 ai 1 3u 释放结点释放结点ai的空间的空间p next = p next next; p ai 1 ai ai+1 程序见书中P。合并合并操作把操作把A A、B B两单链表进行合并，两单链表进行合并，A A在前在前B B在后，并把合并结果仍存储在在后，并把合并结果仍存储在A A中中分析：分析： 对链表来说，对链表来说，“插入插入”和和“删除删除”仅需修改指针即可完成，并且由于前仅需修改指针即可完成，并且由于前 m m 个元素之间和后个元素之间和后 n n 个元素之

28、间的链接关系分别都不需要改变，则算法的个元素之间的链接关系分别都不需要改变，则算法的实际操作为：实际操作为： 找到找到A A的终点，修改的终点，修改A A的终点指针，即的终点指针，即将将 (b1, b2, , bn) 链接到链接到am之后之后；A a1a2am b1b2bn B A a1a2am b1b2bn B P P P 程序见书中P。2.3.3循环链表和双向链表循环链表和双向链表 d1dn非空环链表非空环链表 (使用头指针使用头指针) H循环链表：循环链表：是一种首尾相接的链表是一种首尾相接的链表(即：即：把终结点指针域的值为把终结点指针域的值为“空空”改为改为指向头结点，整个链表形成一

29、个环指向头结点，整个链表形成一个环),简称环链简称环链表表创建空表时，其创建空表时，其头结点指针域的指针值就是头指针头结点指针域的指针值就是头指针 空表空表(使用头指针使用头指针) H 特点：从表的任意结点出发，都可以通过后移指针的方法找到表中所有结点特点：从表的任意结点出发，都可以通过后移指针的方法找到表中所有结点 没有没有 指针指针如何判别终如何判别终结点？结点？改进的循环链表改进的循环链表 d1dn非空环链表非空环链表 (使用尾指针使用尾指针) R由于查找终结点必须扫描全表才能找到，时间效率不高由于查找终结点必须扫描全表才能找到，时间效率不高 如何改进如何改进呢？呢？改进的办法是设置一个

30、尾指针，而不设置头指针。改进的办法是设置一个尾指针，而不设置头指针。这样的好处是：只设置一个指针，但获得头结点指针和终结点这样的好处是：只设置一个指针，但获得头结点指针和终结点next(R)实际上就是头指针，首结点指针是实际上就是头指针，首结点指针是next(next() 空表空表(使用头指针使用头指针) R这种改进为某些操作提供许多方便这种改进为某些操作提供许多方便例如：若例如：若A、B为使用尾指针的循环链表，则上面的合并算法只需两步就完成了为使用尾指针的循环链表，则上面的合并算法只需两步就完成了 a1an A b1bn Bpnext(B) next(B)next(A) next(A)nex

31、t(p) AB a1an b1bn AB双向链表双向链表双向链表的结点除数据域外含有两个指针域双向链表的结点除数据域外含有两个指针域后继指针域后继指针域nextnext和前继指针域和前继指针域priorprior，分别存放指向后继结点和前继结点，分别存放指向后继结点和前继结点为什么要讨为什么要讨论双向链表论双向链表呢？呢？单链表的结点单链表的结点有指示后继的指针域有指示后继的指针域找后继结点方便；找后继结点方便； 无指示前驱的指针域无指示前驱的指针域找前驱结点难：从表头出发查找。找前驱结点难：从表头出发查找。 前驱指针前驱指针结点数据结点数据后继指针后继指针datanextprior Type

32、def struct dnode Int data； Struct dnode *prior，*next； DOUBLELINKLIST；双向循环链表双向循环链表 空双向链表空双向链表 H H双向链表结构双向链表结构和单链的循环表类似，双向链表也可以有循环表，让头结点的前驱指针指向链表的最后一个结点，让最后一个结点的后继指针指向头结点，所以又称双向循环链表 空表如何定空表如何定义？义？双向链表的对称性双向链表的对称性双向链表是一种对称结构双向链表是一种对称结构(设指针设指针 p 指向某一结点指向某一结点)：ppriornext= p =pnextprior pnext(p)prior(p)ne

33、xt(prior (p) prior( next (p) 特点：可以双向查找表中结点，特点：可以双向查找表中结点，“插入插入” 和和“删除删除”时需要时需要同同时修改两个方向时修改两个方向上的指针上的指针例如：例如： 删除结点删除结点 a b c p-prior -next = p-next;pnextprior=p priorp双向链表操作演示双向链表操作演示 x 在在p所指结点前插入所指结点前插入 p a b t next(t)=p prior(t)=prior(p) prior(p)=t next(prior(p)=t x 在在p所指结点后插入所指结点后插入p a b t next(t)

34、=next(p) prior(next(p)=t next(p)=t prior(t)=p链式存储结构小结链式存储结构小结链式存储结构的优点：结点空间可以动态申请和释放；数据元素的逻辑次序靠结点的指针来指示，插入和删除时不需要移动数据元素。(事实上，链表插入、删除运算的快捷是以空间代价来换取时间)链式存储结构的缺点：存储密度小，存储空间利用率低(每个结点的指针域需额外占用存储空间。当数据域所占字节不多时，指针域所占存储空间的比重显得很大)。链表是非随机存取结构。对任一结点的操作都要从头指针依链查找该结点，这增加了算法的复杂度。 不便于在表尾插入元素：需遍历整个表才能找到位置。 2.4线性表结构

35、的应用线性表结构的应用用链式存储或顺序存储用链式存储或顺序存储线性表排序线性表排序线性表查找线性表查找数据查重数据查重2.4.1数据查重数据查重清理性查重清理性查重 当有当有“相同相同”结点存储结点存储时只保留其一（通常是时只保留其一（通常是顺序上的第一个），其顺序上的第一个），其余结点统统摘除余结点统统摘除查重目的查重目的不同不同统计性查重统计性查重分别统计每一结点在表分别统计每一结点在表中重复出现的次数中重复出现的次数.基本思想基本思想提取表中一个结点（将保留在表中）提取表中一个结点（将保留在表中）用该结点的结点数据与其他结点进行比较用该结点的结点数据与其他结点进行比较若有相同者将其从表中

36、删除掉若有相同者将其从表中删除掉(或对重复结点计数或对重复结点计数 ) 第第5次扫描次扫描 S5=41 2 3 5 4n=5实例演示实例演示设有顺序表设有顺序表S =（1，2，3，1，1，5，2，4，2，4），），n=10查重的执行过程是：查重的执行过程是：第第1次扫描次扫描 S1=11 2 3 5 2 4 2 4n=8第第2次扫描次扫描 S2=21 2 3 5 4 4n=6第第3次扫描次扫描 S3=31 2 3 5 4 4n=6查重结点查重结点 查重结果表查重结果表第第4次扫描次扫描 S4=51 2 3 5 4 4n=6初态初态1 2 3 1 1 5 2 4 2 4n=10算法的核心操算法的

37、核心操作是作是比较比较和和删删除除。最多。最多n-1次次扫描扫描每一次新扫描都是在上一次每一次新扫描都是在上一次查重结果表的基础上执行的查重结果表的基础上执行的注意注意：有序表查重有序表查重 原始表原始表S =（1，1，1，2，2，2，3，4，4，5）n = 10 第第1 1结点结点S1 = 1，查重后查重后S =（1，2，2，2，3，4，4，5）n = 8 第第2结点结点S2 = 2，查重后，查重后S =（1，2， 3，4，4，5）n = 6 第第3结点结点S3 = 3，查重后查重后S =（1，2，3，4，4，5） n = 6 第第4结点结点S4 = 4，查重后查重后S =（1，2， 3，4

38、，5） n = 5当遇到不相同结点时，就从当遇到不相同结点时，就从下一结点下一结点开始重复上述操作开始重复上述操作查重过程：查重过程： 2.4.2基于线性表排序基于线性表排序43512什么是什么是排序排序排序结果排序结果排序操作排序操作排序对象排序对象排序方向排序方向排序标准排序标准(关键字关键字)直接插入排序直接插入排序直接插入排序的基本思想：直接插入排序的基本思想：把待排序序列一分为二：“已排好序子序列”和“待排序子序列” 依次将各个数据插入已排序好的有序子表中有序序列有序序列 a1 . a i -1 ai无序序列无序序列 aai i . An有序序列有序序列 a1 . a i 无序序列无

39、序序列 ai +1 . An排序结果仍存储在原序排序结果仍存储在原序列的空间上，原序列不列的空间上，原序列不再存在了再存在了最简单的一种排序方法 新元素插在新元素插在哪？哪？实例演示实例演示设有序列设有序列41，25，17，12，28，14，23，16，直接插入排序的过程，直接插入排序的过程 01234567初始划分初始划分4125171228142316第第1次插入次插入2541171228142316第第2次插入次插入1725411228142316第第3次插入次插入1217254128142316第第4次插入次插入1217252841142316第第5次插入次插入121417252841

40、2316第第6次插入次插入1214172325284116第第7次插入次插入1214161723252841改进改进设待排序顺序表设待排序顺序表S，为了提高效率，我们附设一个哨兵结点，为了提高效率，我们附设一个哨兵结点S0，使得，使得S0始终存放当前待插入的记录始终存放当前待插入的记录哨兵结点的哨兵结点的作用？作用？初始状态初始状态4125171228142316 S0 S1 S2 S3 S4 S5 S6 S7 i =3 1725411228142316 i =4 1217254128142316 i =6 3817252897122316i =7 1723252841121416i =8 1

41、617252841121423i =2 4938171228142316 4125254125171241i =5 12172528411423162828144125411725121741252814144117252841232316172528412316该算法的要点是：该算法的要点是：使用监视哨使用监视哨s0临时保临时保存待插入的记录。存待插入的记录。从后往前查找应插入从后往前查找应插入的的 位置。位置。查找与移动用同一循查找与移动用同一循环环 完成。完成。 简单交换排序简单交换排序基本思路：基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。选择最小结点的方法是，从终结点Rn开始顺序向上两个两个地比较优点优点：每趟结束时，不仅能挤出一个最小值到最前面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序前提前提：顺序存储结构 排序过程：排序过程：简单交换排序过程实例简单交换排序过程实例1214161723252841第第7趟趟扫扫描描2523171216412814待待排排序序序序列列2523171216412814第第1趟趟扫扫描描1225231714164128第第2趟趟扫扫描描1214252317162841第第3趟趟扫扫描描142814411416121