数据结构培训数据结构课件

数据结构培训数据结构数据结构培训数据结构41、俯仰终宇宙，不乐复何如。42、夏日长抱饥，寒夜无被眠。43、不戚戚于贫贱，不汲汲于富贵。44、欲言无予和，挥杯劝孤影。45、盛年不重来，一日难再晨。及时当勉励，岁月不待人。线性表的存储结构线性表的存储结构-顺序表、线性链表顺序表、线性链表(单链表单链表)1.顺序存储结构顺序存储结构(可用C语言的一维数组实现)逻辑上相邻物理地址相邻实现随机存取在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低特特点点：只只有有数数据据域域，存存储储空空间间利利用用率率高高，做做插插入入、删删除除时时需需移移动动大大量量元元素素。空空间间估估计计不不明明时时，按按最最大大空间分配。空间分配。6/25/202462、线性表的链式存储结构、线性表的链式存储结构将将线线性性表表的的元元素素放放到到一一个个具具有有头头指指针针的的链链表表中中，链链表中每个结点包含数据域和指针域。表中每个结点包含数据域和指针域。数数据据域域存存放放数数据据，指指针针域域存存放放后后继继结结点点的的地地址址，最最后一个结点的指针域为空。后一个结点的指针域为空。特特点点：插插入入、删删除除灵灵活活方方便便，不不需需要要移移动动结结点点，只只要改变结点中指针域的值即可。要改变结点中指针域的值即可。2-1单链表的插入运算单链表的插入运算2-2单链表的删除运算单链表的删除运算datalink6/25/20247anaia1a2ai-1xLStatusListInsert_L(LinkList&L,inti,ElemTypex)p=L;j=0;while(p&jnext;+j;/寻找第寻找第i-1个结点个结点if(!pji-1)returnERROR;/插入位置错插入位置错s=(structLNode*)malloc(sizeof(structLNode);/生成新结点生成新结点s-data=x;s-next=p-next;p-next=s;returnOK;babaxPP单链表的插入运算单链表的插入运算S6/25/20248ai-1a1aiai+1LpqStatusListDelete_L(LinkList&L,inti,ElemTypex)p=L;j=0;while(p-next&jnext;+j;/寻找第寻找第I个结点，并使个结点，并使p指向其前驱指向其前驱if(!(p-next)ji-1)returnERROR;/删除错删除错q=p-next;p-next=q-next;free(q);/删删除除并并释放结点释放结点returnOK;单链表的删除运算单链表的删除运算6/25/20249循环链表(circular linked list)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p-link=NULL循环链表p或p-link=Hhh空表6/25/202410双向链表（double linked list）单链表具有单向性的缺点结点定义typedef struct node datatype element;struct node*prior,*next;JD;priorelementnextL空双向循环链表：非空双向循环链表：LABbcapp-prior-next=p=p-next-proir;6/25/202411bcaaPPvoid del_dulist(JD*p)p-prior-next=p-next;p-next-prior=p-prior;free(p);删除算法描述p-prior-next=p-next;p-next-prior=p-prior;6/25/202412void ins_dulist(JD*p,int x)JD*s;s=(JD*)malloc(sizeof(JD);s-element=x;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;算法描述算法评价：T(n)=O(1)xSbaP插入6/25/202413线性表的应用：应用最广的数据结构。线性表的应用：应用最广的数据结构。高级语言中的数组；高级语言中的数组；电话号码查询系统（可采用顺序表或单链表结构电话号码查询系统（可采用顺序表或单链表结构）；）；各种事务处理（各种表格均采用顺序表和线性链表结构）各种事务处理（各种表格均采用顺序表和线性链表结构）6/25/2024143 3 栈和队列栈和队列3.1 3.1 栈栈3.1.13.1.1栈的定义栈的定义栈：栈：限定只能在表的一端进行插入和删除的特殊的线性表限定只能在表的一端进行插入和删除的特殊的线性表 (LIFO/FILO)(LIFO/FILO)。栈顶（栈顶（top)top)：允许插入和删除的一端；：允许插入和删除的一端；栈底（栈底（bottom):bottom):不允许插入和删除的一端。不允许插入和删除的一端。a1a2.an进栈进栈出栈出栈栈顶栈顶栈底栈底6/25/202415栈的存储结构顺序栈实现：一维数组sM入栈算法出栈算法stop=x;return(+top);*q=s-top;6/25/202416入栈算法出栈算法 .栈底toptopxptop .栈底topq链栈 p-data=x;p-link=top;top=p;q=top;*p=top-data;top=top-link;free(q);6/25/202417栈的应用栈的应用(1)过程的嵌套过程的嵌套(2)递归算法递归算法(3)表达式的计算表达式的计算(4)地图四染色问题地图四染色问题6/25/202418队列的主要运算队列的主要运算（1）设置一个空队列；）设置一个空队列；（2）插入一个新的队尾元素，称为进队；）插入一个新的队尾元素，称为进队；（3）删除队头元素，称为出队；）删除队头元素，称为出队；（4）读取队头元素；）读取队头元素；4队列队列（一种特殊的线性结构一种特殊的线性结构，限定在一端插入，一端删除），限定在一端插入，一端删除）4.1队列的定义与运算队列的定义与运算 a1,a2,a3,a4,an-1,an 队 列 示 意 图队头队尾先先 进进 先先出出FIFO6/25/2024194.2队列的存储结构队列的存储结构（1）顺序存储结构）顺序存储结构(a)线性队列线性队列e4e3 e3e2e1 3210 (a)(b)(c)rear=front（队空）（队空）rearfront 队队满满rear=4front6/25/202420(b)循环队列循环队列 rearfront 0123(3)队空队空 rear(1)一般情况一般情况front 0123e4e3 (2)队满队满reare3 e40123fronte5队满条件队满条件：(Q.rear+1)%MAX=Q.front显示循环队列中显示循环队列中入队和出队时的入队和出队时的指针变换过程指针变换过程6/25/202421入队算法：出队算法：rear=(rear+1)%M;sqrear=x;front=(front+1)%M;*q=sqfront;6/25/202422链队列入队算法出队算法p-data=x;p-link=NULL;rear-link=p;s=front-link;front-link=s-link;if(s-link=NULL)rear=front;x=s-data;free(s);6/25/2024233.写出下列程序段的输出结果写出下列程序段的输出结果Voidmain()SqStackS;/定义栈定义栈charx,y;InitStack(S);/初始化栈初始化栈x=c;y=k;Push(S,x);Push(S,a);Push(S,y);Pop(S,x);Push(S,t);Push(S,x);Pop(S,x);Push(S,s);while(!StackEmpty(S)Pop(S,y);printf(y);.cakprintf(x);.cacatk.cat.catsstack6/25/2024244.Voidalgo(SqQueue&Q)StackS;intd;InitStack(S);while(!QueueEmpty(Q)DeQueue(Q,d);Push(S,d);while(!StackEmpty(S)Pop(S,d);EnQueue(Q,d);.0123abQ.frontQ.rear.0123Q.frontQ.rearab.0123baQ.frontQ.rear6/25/2024255数数组组（线性表的推广）线性表的推广）51二维数组的定义二维数组的定义a1a11a12.a1na2a21a22.a2namam1am2.amn.ai=(ai1,ai2,.,ain)(1=i=n)数组的运算主要是存取元素、修改相应的元素。数组的运算主要是存取元素、修改相应的元素。6/25/202426（1）按行优先顺序存放按行优先顺序存放（2）按列优先顺序存放按列优先顺序存放53矩阵的压缩存储矩阵的压缩存储1、特殊矩阵：值相同元素或非零元素的分布具有一定规律。特殊矩阵：值相同元素或非零元素的分布具有一定规律。（1）下三角阵下三角阵（2）三对角阵三对角阵2、稀疏矩阵稀疏矩阵：元素分布无规律。：元素分布无规律。（1）顺序存储结构顺序存储结构三元组表示法三元组表示法（3）数组的链接存储结构数组的链接存储结构十字链表结构十字链表结构52数组的顺序存储结构数组的顺序存储结构6/25/202427a1100.0a21a220.0an1an2an3.ann.0A=按行优先存放按行优先存放a11,a21,a22,a31,a32,an1,an2,ann前前i-1行非零元素个数行非零元素个数R=i(i-1)2loc(aij)=loc(a11)+(+(j-1)Si(i-1)2i-1R=1下三角阵下三角阵6/25/202428a11a120.0a21a22a230.000an-1,n-2an-1.n-1an-1,n.A=0a21a22a230.000.an,n-1ann.按行优先存放按行优先存放a11,a12,a21,a22,a23,a32,a34,an,n-1,annloc(aij)=loc(a11)+2(i-1)+(j-1)三对角阵三对角阵6/25/20242970001500-40000-2000021000-100M=2164-214-143-4221551711列列行行值值顺序存储结构顺序存储结构三元组表示法三元组表示法6/25/20243070001500-40000-2000021000-100M=22-4151541-2462111734-1 ij edownright6/25/202431结结点点（Node）：树树中中的的元元素素，包包含含数数据据项项及及若若干干指指向向其其子子树树的分支。的分支。结点的度（结点的度（Degree）：结点拥有的子树数。）：结点拥有的子树数。叶子（叶子（Leaf）：度为零的结点，也称端结点。）：度为零的结点，也称端结点。孩子（孩子（Child）：结点子树的根称为该结点的孩子结点。）：结点子树的根称为该结点的孩子结点。兄弟（兄弟（Sibling）：）：同一双亲的孩子。同一双亲的孩子。双亲（双亲（Parent）：孩子结点的上层结点，称为这些结点的双亲）：孩子结点的上层结点，称为这些结点的双亲深度（深度（Depth)：树中结点的最大层次数。树中结点的最大层次数。森林（森林（Forest）：）：M棵互不相交的树的集合。棵互不相交的树的集合。6树树6/25/2024326.2二叉树二叉树（BinaryTree）1、二叉树的定义及其性质、二叉树的定义及其性质(1)二叉树的定义二叉树的定义(a)空二空二叉树叉树(b)仅仅有跟结有跟结点点(c)(d)(e)(2)二叉树的性质二叉树的性质二叉树的基本性质：二叉树的基本性质：A、二叉树的第二叉树的第i层上至多有层上至多有2i-1（i 1）个结点。个结点。B、深度为深度为h的二叉树中至多含有的二叉树中至多含有2h-1个结点。个结点。C、若在任意一棵二叉树中，有若在任意一棵二叉树中，有n0个叶子结点，有个叶子结点，有n2个度为个度为2的结点，的结点，则则：n0=n2+1二叉数的五种基本形态二叉数的五种基本形态ABCDEF一一种种特特殊殊的的树树型型结结构构，特特点点是是树树中中每每个个结结点点只只有有两两棵棵子子树树，且且子子树树有有左左右右之之分分，次次序不能颠倒。序不能颠倒。6/25/202433（3）满二叉树）满二叉树423156789101112131415（4）完全二叉树）完全二叉树842315679101112完全二叉树完全二叉树423156789101112非完全二叉树非完全二叉树特特点点：每每一一层层上上的的结结点点数数都都是是最最大大结结点数。点数。完完全全二二叉叉树树：指指深深度度为为k的的，有有n个个结结点点的的，且且每每一一个个结结点点都都与与深深度度为为k的的满满二二叉叉树树中中编编号号从从1至至n的的结结点点一一一一对对应。应。6/25/2024342、二叉树的存储结构、二叉树的存储结构(2)链式存储结构链式存储结构FEDCBA1514131211109876543210T16若父结点在数组中若父结点在数组中i下标处，其左孩子在下标处，其左孩子在2*i处，右孩子在处，右孩子在2*i+1处。处。ABcFED12 4 8 91011563712131415(1)顺序存储结构顺序存储结构(1)顺序存储结构顺序存储结构2h-1=24-1=15用用一一组组连连续续的的存存储储单单元元存存放放二二叉叉树树的的数数据据元元素素。结结点点在在数数组组中中的的相相对对位位置置蕴蕴含含着着结结点之间的关系。点之间的关系。6/25/202435(2)链式存储结构链式存储结构：每个结点由数据域、左指针域和右指针域每个结点由数据域、左指针域和右指针域组成。组成。rchildDatalchildADBCEF图图2-5 一一般般二二叉叉树树的的二二叉叉链链表结构表结构6/25/2024366.3树的存储结构树的存储结构双亲表示法孩子表示法带双亲的孩子链表孩子兄弟表示法（二叉树表示法）多重链表表示法6/25/2024373、将树和森林转换为二叉树、将树和森林转换为二叉树（1）树转换为二叉树）树转换为二叉树方法：方法：对每个孩子进行自左至右的排序；对每个孩子进行自左至右的排序；在兄弟之间加一条连线；在兄弟之间加一条连线；对每个结点，除了左孩子外，去除其与其余孩子对每个结点，除了左孩子外，去除其与其余孩子之间的联系；之间的联系；以根结点为轴心，将整个树顺时针转以根结点为轴心，将整个树顺时针转45度。度。6/25/202438 I A B C DE F G H(b)A B CD E G H FI(a)树转换为二叉树树转换为二叉树ABEFCDGHI(d)ABCDEFGHI(c)6/25/202439（2）森林转换为二叉树森林转换为二叉树ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：方法：将各棵树分别转成二叉树；将各棵树分别转成二叉树；把每棵数的根结点用线连起来；把每棵数的根结点用线连起来；以以第第一一棵棵数数的的根根结结点点作作为为二二叉叉树树的根结点，按顺时针方向旋转。的根结点，按顺时针方向旋转。6/25/202440将二叉树转换成树加线：若加线：若p结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将p的右孩子，右孩的右孩子，右孩子的右孩子，子的右孩子，沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与p的双亲的双亲用线连起来用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI6/25/2024415.4 树和二叉树的遍历树的遍历遍历按一定规律走遍树的各个顶点，且使每一顶点仅被访问一次，即找一个完整而有规律的走法，以得到树中所有结点的一个线性排列常用方法先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树后根（序）遍历：先依次后根遍历每棵子树，然后访问根结点按层次遍历：先访问第一层上的结点，然后依次遍历第二层，第n层的结点6/25/202442ABCDEFGHIJKLMNO先序遍历：后序遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO6/25/202443二叉树的遍历方法先序遍历：先访问根结点,然后分别先序遍历左子树、右子树中序遍历：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历：先后序遍历左、右子树，然后访问根结点按层次遍历：从上到下、从左到右访问各结点DLRLDR、LRD、DLRRDL、RLD、DRL6/25/202444（2）给给定定先先（后后）序序遍遍历历和和中中序序遍遍历历，可可唯唯一一的的得得到一棵二叉树到一棵二叉树ADBCT1T2T3ABDCBDACDBCA6/25/2024452.5.3哈夫曼树及其应用哈夫曼树及其应用1、哈夫曼树、哈夫曼树（最优树）（最优树）带权路径长度最短的树带权路径长度最短的树结点带权的路径长度为从该结点到树根之间的路径长度与结点上结点带权的路径长度为从该结点到树根之间的路径长度与结点上权的乘积。权的乘积。树的带权路径长度为树中叶子结点带权路径长度之和。树的带权路径长度为树中叶子结点带权路径长度之和。记作：记作：其中：其中：Wk为树中每个叶子结点的权；为树中每个叶子结点的权；Lk为每个叶子结点到根的路径长度为每个叶子结点到根的路径长度WPL最小的二叉树就称作最优二叉树或哈夫曼树最小的二叉树就称作最优二叉树或哈夫曼树。6/25/202446abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=351、哈夫曼树、哈夫曼树（最优树）（最优树）公式：公式：6/25/202447675cd(b)11b57cd(c)18a711cdb5624(d)abcd7524(a)2、哈夫曼树的构造、哈夫曼树的构造6/25/202448146833442200001111T;ACS例例2：哈夫曼树用于电文编码哈夫曼树用于电文编码要传输的电文是要传输的电文是CAS；CAT；SAT；AT要传输的字符集是要传输的字符集是D=C，A，S，T，；每个字符出现的频率是每个字符出现的频率是W=2，4，2，3，3各字符编码是各字符编码是T；ACS000110110111上述电文编码：上述电文编码：110101110111010000111110000110006/25/202449线索二叉树定义：前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为线索：指向前驱或后继结点的指针称为线索二叉树：加上线索的二叉链表表示的二叉树叫线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫实现在有n个结点的二叉链表中必定有n+1个空链域在线索二叉树的结点中增加两个标志域lt :若 lt=0,lc 域指向左孩子；若 lt=1,lc域指向其前驱rt :若 rt=0,rc 域指向右孩子；若 rt=1,rc域指向其后继结点定义：typedef struct node int data;int lt,rt;struct node*lc,*rc;JD;lc lt data rt rc6/25/202450ABCDE A B D C ET先序序列：ABCDE先序线索二叉树00001111 116/25/202451二叉排序树定义：二叉排序树或是一棵空树，或是具有下列性质定义：二叉排序树或是一棵空树，或是具有下列性质的二叉树：的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值结点的值若它的右子树不空，则右子树上所有结点的值均大于或等于若它的右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值它的根结点的值它的左、右子树也分别为二叉排序树它的左、右子树也分别为二叉排序树6/25/202452插入算法例 10，18，3，8，12，2，7，310101810183101838101838 12101838 122101838 1227101838 12273中序遍历二叉排序树可得到一个关键字的有序序列6/25/2024532.6图图图是一种非线性的数据结构，结点之间的关系可以是任意的。图是一种非线性的数据结构，结点之间的关系可以是任意的。图中任意两个元素之间都可能相关。图中任意两个元素之间都可能相关。图的存储结构图的存储结构（1）图的邻接矩阵表示法）图的邻接矩阵表示法表示顶点间相邻关系的矩阵。表示顶点间相邻关系的矩阵。有向：从一个结点到另一个结点有弧为有向：从一个结点到另一个结点有弧为1，否则为，否则为0。无向：有边连接则为无向：有边连接则为1，否则为，否则为0。（2）图的邻接表表示法）图的邻接表表示法在边少的情况下，用邻接表比邻接矩阵节省存储空间。在边少的情况下，用邻接表比邻接矩阵节省存储空间。6/25/202454V1V3V2V4V1V3V2V4 V1V2V3V4 V1 0010V20001V30101V41000 V1V2V3V4 V1 0111V21011V31100V41100图的邻接矩阵表示法图的邻接矩阵表示法无向图中某顶点的度数为矩阵中对应该顶点的行或列的无向图中某顶点的度数为矩阵中对应该顶点的行或列的1的个数的个数有向图中某顶点的有向图中某顶点的出度出度为矩阵中对应该顶点的为矩阵中对应该顶点的行行的的1的个数的个数有向图中某顶点的有向图中某顶点的入度入度为矩阵中对应该顶点的为矩阵中对应该顶点的列列的的1的个数的个数6/25/202455V1V3V2V4V1V3V2V44321211134421344321图的邻接表表示法图的邻接表表示法46/25/202456V1V3V2V42434311有向图的逆邻接表表示法有向图的逆邻接表表示法6/25/202457无向图的邻接多重表表示法无向图的邻接多重表表示法V1V3V2V443212212312412426/25/202458深度优先遍历深度优先遍历(DFS)V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍历：V1 V2 V4 V8 V5 V6 V3 V7深度遍历：V1 V2 V4 V8 V5 V6 V3 V76/25/202459广度优先遍历广度优先遍历(BFS)V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V8广度遍历：V1 V2 V3 V4 V5 V6 V7 V86/25/202460构造最小生成树方法构造最小生成树方法普里姆(Prim)算法算法思想：设N=(V,E)是连通网，TE是N上最小生成树中边的集合从任一顶点出发，将此点包含在生成树里在这些一个顶点已在生成树里而另一顶点未在生成树里的边中，找一条代价最小的边将此边和那个顶点包含进生成树重复上述操作，每次加一个顶点和一个代价最小的边。直至所有的顶点包含进去，则得到最小生成树拓扑排序拓扑排序:一个一个AOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的6/25/2024611383032V2:813-133032V1:13-13302220V3:13-192220V4:19终点 从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj-2120V6:20516432085623013717329最短路径最短路径迪杰斯特拉(Dijkstra)算法6/25/2024622.7查找查找271顺序查找顺序查找思思想想：对对给给定定的的一一关关键键字字K，从从线线性性表表的的一一端端开开始始，逐逐个个进进行行记记录录的的关关键键字字和和K的的比比较较，直直到到找找到到其其关关键键字字等等于于K的的记记录录或或到到达达表的另一端。表的另一端。6/25/202463顺序查找的算法：顺序查找的算法：int seqsrch(JD r,int n,int k)int i=n;r0.key=k;while(ri.key!=k)i-;return(i);2560308040201080012345672560308040201001234567256030804020109001234567（a）初态初态(b)K=80(c)K=90(returni=0)length=7(returni=4)6/25/202464272折半查找折半查找思思想想：先先确确定定待待查查找找记记录录所所在在的的范范围围，然然后后逐逐步步缩缩小范围，直到找到或确认找不到该记录为止。小范围，直到找到或确认找不到该记录为止。必须在具有必须在具有顺序存储结构的有序表顺序存储结构的有序表中进行。中进行。6/25/202465(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowmidhigh(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowmidhighmidlowhighmidmidlowhigh折半查找例：折半查找例：highlow(08,14,23,37,46,55,68,79,91)midlowhigh6/25/202466IntSearch_Bin(SSTableST,KeyTypek)low=1;high=ST.length;while(low=high)mid=(low+high)/2;if(ST.elemmid=k)returnmid;elseif(kST.elemmid)high=mid-1;/在前半区间继续查找在前半区间继续查找elselow=mid+1;return0;6/25/2024672.7.3散列（散列（HSAE）查找）查找根根据据关关键键字字的的值值，利利用用某某个个函函数数直直接接计计算算出出元元素素所所在在的的位位置置。这这函函数数称称为为“哈哈希希函函数数”，能能用用散散列列技技术术进进行行查查找找的的表表称称为为散散列列表（表（哈希表）。哈希表）。1、基本概念基本概念哈希函数，冲突哈希函数，冲突哈哈希希表表技技术术的的主主要要目目标标是是提提高高查查找找效效率率，即即缩缩短短查查表表和和填填表的时间。表的时间。冲突是指存在多个关键字，能计算出相同的存储位置。冲突是指存在多个关键字，能计算出相同的存储位置。312726211916130911050102H(K)=int(K/3)+1121110987654321表项序号表项序号6/25/2024683、处理冲突的方法处理冲突的方法 （1）开放定址法开放定址法设散列函数设散列函数H（k）=kMODm（m为表长为表长,若若发发生生冲冲突突，设设发发生生冲冲突突的的地地址址为为p,则则沿沿着着一一个个探查序列逐个探查，那么，探查的地址序列为探查序列逐个探查，那么，探查的地址序列为P+1,P+2,P+3,m-1,0,1,P-1.38 29 17 60012345678910m=11)(2)链地址法链地址法链链地地址址法法解解决决冲冲突突的的方方法法：把把具具有有相相同同散散列列地地址址的的键键值值存存放放在在同同一一个个链链表表中中，称称为为同同义义词链表。词链表。6/25/202469例例一组关键字为一组关键字为（21，14，19，58，65，32，72）H(K)=KMOD11012345678910216532197214586/25/202470排排序序的的重重点点是是各各种种排排序序方方法法的的各各趟趟排排序序结结果果以以及及比比较较次次数和移动次数数和移动次数6/25/202471待排元素序列：待排元素序列：532736156942第一次排序：第一次排序：275336156942第二次排序：第二次排序：273653156942第三次排序：第三次排序：152736536942第四次排序：第四次排序：152736536942第五次排序：第五次排序：152736425369直接插入排序示例直接插入排序示例2.8.2插入排序插入排序直接插入、折半插入直接插入、折半插入1、直接插入排序、直接插入排序思思想想:从从数数组组中中的的第第2号号元元素素开开始始,顺顺序序从从数数组组中中抽抽取取元元素素并并将将该该元元素素插插入入到到其其左左端端已已排排好好序序的的数数组组的的适适当当位位置上置上.6/25/202472例：有例：有6个记录，前个记录，前5个已排序的基础上，对第个已排序的基础上，对第6个记录排序。个记录排序。152736536942 low mid high152736536942 low high mid152736536942 high low1527364253692、折半插入排序、折半插入排序折半插入排序在寻找插入位置时，利用折半查找的原理寻找插入折半插入排序在寻找插入位置时，利用折半查找的原理寻找插入位置位置,不是逐个比较。不是逐个比较。6/25/202473voidBinsertSort(Sqlist&L)for(i=2;i=L.length;+i)L.r0=L.ri;/r0作为监视哨作为监视哨low=1;high=i-1;While(low=high)m=(low+high)/2;if(L.r0.key=high+1;j)L.ij+1=L.rj;/记录后移记录后移L.rlow=L.r0;/插入插入for/折半插入排序折半插入排序6/25/202474取d3=1三趟分组：13 27 48 55 4 49 38 65 97 76三趟排序：4 13 27 38 48 49 55 65 76 97例 初始：49 38 65 97 76 13 27 48 55 4一趟排序：13 27 48 55 4 49 38 65 97 76二趟排序：13 4 48 38 27 49 55 65 97 76取d1=5一趟分组：49 38 65 97 76 13 27 48 55 4取d2=3二趟分组：13 27 48 55 4 49 38 65 97 76希尔排序(缩小增量法)6/25/2024752.8.3选择排序选择排序简单选择排序、堆排序。简单选择排序、堆排序。1、简单选择排序、简单选择排序思想：首先从思想：首先从1-n个元素中个元素中选出关键字最小的记录交换选出关键字最小的记录交换到第一个位置上。然后从第到第一个位置上。然后从第2个到第个到第n个元素中选出次小个元素中选出次小的记录交换到第的记录交换到第2个位置上，个位置上，依次类推。依次类推。初态初态83916839168391683916ijkijkijkijk13986互换互换ijk13986ikj13986ikj第第一一趟趟第第二二趟趟13986i kj第第三三趟趟6/25/2024762堆堆排排序序也也是是一一种种选选择择排排序序。是是具具有有特特定定条条件件的的顺顺序序存存储储的的完完全全二二叉叉树树，其其特特定定条条件件是是：任任何何一一个个非非叶叶子子结结点点的的关关键键字字大于等于（或小于等于）子女的关键字的值。大于等于（或小于等于）子女的关键字的值。A、堆的示例、堆的示例 897624331510112536497856(a):堆顶元素取最大值堆顶元素取最大值(b):堆顶元素取最小值堆顶元素取最小值B、实现堆排序需解决两个问题：、实现堆排序需解决两个问题：（1）如何由一个无序序列建成一个堆？如何由一个无序序列建成一个堆？（2）输出堆顶元素后，如何将剩余元素调整成一个新的堆？输出堆顶元素后，如何将剩余元素调整成一个新的堆？6/25/2024772.8.4交交换换排排序序1、冒泡排序、冒泡排序4936416511第第六六趟趟排排序序后后第第五五趟趟排排序序后后第第四四趟趟排排序序后后第第三三趟趟排排序序后后第第二二趟趟排排序序后后第第一一趟趟排排序序后后初初始始关关键键字字783665364156364165413641561178363641491156492525251149495611111125252525思思想想：小小的的浮浮起起，大大的的沉底。沉底。6/25/2024782、快速排序、快速排序三次交换三次交换186236752/完成一趟排序后分别进行快速排序完成一趟排序后分别进行快速排序有序序列有序序列618235267初始序列初始序列235266718一次交换一次交换1852667二次交换二次交换18 66752keylowhighlowhighlowhigh high6/25/2024792.8.5归并排序归并排序初始序列初始序列23526761810一趟归并后一趟归并后23526671018二趟归并后二趟归并后62352671018三趟归并后三趟归并后61018235267归并排序示例归并排序示例6/25/20248041、学问是异常珍贵的东西，从任何源泉吸收都不可耻。阿卜日法拉兹42、只有在人群中间，才能认识自己。德国43、重复别人所说的话，只需要教育；而要挑战别人所说的话，则需要头脑。玛丽佩蒂博恩普尔44、卓越的人一大优点是：在不利与艰难的遭遇里百折不饶。贝多芬45、自己的饭量自己知道。苏联