数据结构-清华大学出版社-严蔚敏吴伟民编著.docx

第一章绪论1、数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。2、程序设计=算法+数据结构3、解决问题方法的效率： 跟数据的组织方式有关 跟空间的利用效率有关 跟算法的巧妙程度有关4、数据：所有能输入到计算机中,且被计算机处理的符号的集合，是计算机操作对象的总称；是计算机处理的信息的某种特定的符号表示形式。5、数据元素：数据中的一个“个体"数据结构中讨论的根本单位。相当于“记录”，在计算机程序中通常作为一个整体考虑和处理。6、数据项：相当于记录的“域”，是数据的不可分割的最小单位,如学号。数据元素是数据项的集合。7、数据对象：性质相同的数据元素的集合.例如：所有运发动的记录集合8、数据结构：是相互间存在某种关系的数据元素集合。9、数据结构是带结构的数据元素的集合。10、不同的关系构成不同的结构。11、次序关系：<ai,ai+l>i=l,2,3A5,612、对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的根本操作；2）数据的存储结构，数据结构根本操作的实现;13、数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。数据结构的根本操作：指对数据结构的加工处理。14、数据的存储结构（物理结构）：数据结构在计算机内存中的表示。数据结构根本操作的实现：根本操作在计算机上的实现（方法）。15、数据结构的有关概念f线性表A.1 .数据的逻辑结构YJ数据结构的三个方面B.2、数据的存储结构,A非线性结构树形结构顺序存储链式存储图形结构I3、数据的运算：检索、排序、插入、删除、修改等。16、数据元素的4类的根本结构:集合;线性结构：结构中数据元素之间存在一对一的关系；树形结构：结构中数据元素之间存在一对多的关系；（4）图状结构或网状结构：结构中数据元素之间存在多对多的关系。17、C语言的优点：C语言可以直接操作内存。18、每个节点都由两局部组成：数据域和指针域。19、链接存储结构特点： 比顺序存储结构的存储密度小（每个节点都由数据域和指针域组成）。 逻辑上相邻的节点物理上不必相邻。 插入、删除灵活（不必移动节点，只要改变节点中的指针）。20、数据类型是一个值的集合和定义在此集合上的一组操作的总称。21、ADT有两个重要特征:数据抽象和数据封装。22、抽象数据类型（AbstractDataType简称ADT）：是指一个数学模型以及定义在此数学模型上的一组操作。23、抽象数据类型有：数据对象数据对象的定义、数据关系数据关系的定义、根本操作根本操作的定义。24、数据类型的定义和含义。定义:数据类型是一个值的集合和定义在这个值集上的一组操作的总称。含义：将数据按一定次序与形式存放的结构。24、算法空间复杂度S（n）算法的存储量包括：输入数据所占的空间;程序本身所占的空间;辅助变量所占的空间。25、算法具有有穷性、确定性、可行性、输入和输出五大特性。26、抽象数据类型具有数据抽象、数据封装的特点。27、数据的储存结构分为：顺序存储结构和链式存储结构。第二章线性表1、线性结构的特点：在数据元素中的非空有限集中。（1）存在唯一的一个被称作“第一”的数据元素；（2）存在唯一的一个被称作“最后一个”的数据元素；（3）除第一个外，集合中的每一个数据元素均只有一个前驱；（4）除最后一个外，集合中的每一个数据元素均只有一个后继。2、线性表（LinearLiSt）：一个线性表是n个数据元素的有限序列。3、线性表的顺序存储实现：typedefstructEIementTypeDataMAXSIZE;intLast;List;1.istL,*PtrL;4、初始化(建立空的顺序表)1.ist*MakeEmpty()List*PtrL;PtrL=(List*)malloc(Sizeof(List);PtrL->Last=-1;returnPtrL;)5、查找intFind(EIementTypeX,List*PtrL)inti=O;while(i<=PtrL->Last&&PtrL->Datai!=X)i+;if(i>PtrL->Last)return-1;*如果没找到，返回-1*/elsereturni;*找到后返回的是存储位置*/)6、插入算法voidlnsert(EIementTypeX,inti,List*PtrL)intj；if(PtrL->Last=MAXSIZE-1)*表空间已满,不能插入*/printf(n表满”);return;if(i<111i>PtrL->Last+2)*检查插入位置的合法性*/Printf("位置不合法”);return;)for(j=PtrL->Last;j>=i-1;j-)PtrL->Dataj+l=PtrL->Dataj;*将aian倒序向后移动/PtrL->Datai-l=X;*新元素插入*/PtrL->Last+;*Last仍指向最后元素*/return;)7、删除算法voidDelete(inti,List*PtrL)intj;if(i<111i>PtrL->Last+l)*检查空表及删除位置的合法性*/Printf(不存在第d个元素,i);return;)for(j=i;j<=PtrL->Last;j+÷)PtrL->Dataj-l=PtrL->Dataj;*将ai+lan顺序向前移动*/PtrL->Last-;*Last仍指向最后元素*/return;8、求表长intLength(List*PtrL)List*p=PtrL;*p指向表的第一个结点*/intj=O;while(p)p=p->Next;j+;*当前P指向的是第j个结点j7)returnj;9、查找按序号查找：FindKth;1.ist*FindKth(intK,List+PtrL)List*p=PtrL;inti=1;while(pI=NULL&&i<K)p=p->Next;i+;)if(i=K)returnp;*找到第K个，返回指针*/elsereturnNULL;*否那么返回空*/(2)按值查找：Find1.ist*Find(EIementTypeX,List*PtrL)(1.ist*p=PtrL;while(p!=NULL&&p->DataI=X)p=p->Next;returnp;)10、插入(在链表的第-"1<Wh+”个结点后插入一个值为X的新结点)1.ist*lnsert(EIementTypeXzinti,List*PtrL)List*p,*s;if(i=l)/*新结点插入在表头*/s=(List*)malloC(SiZeOf(LiSt);/*申请、填装结点*/s->Data=X;s->Next=PtrL;returns;/*返回新表头指针*/)p=FindKth(i-l,PtrL);/*查找第i-1个结点*/if(p=NULL)/*第i-1个不存在，不能插入*/printf(m参数i错”);returnNULL;elses=(List*)malloc(sizeof(List);*中请、填装结点*/s->Data=X;s->Ne×t=p->Next;/*新结点插入在第i-1个结点的后面*/p->Next=s;returnPtrL;)11、删除(删除链表的第V个位置上的结点)1.ist*Delete(inti,List*PtrL)List*p,*s;if(i=1)*假设要删除的是表的第一个结点*/s=PtrL;*s指向第1个结点*/PtrL=PtrL->Ne×t;/*从链表中删除*/free；/*释放被删除结点*/returnPtrL;)P=FindKth(i-1,PtrL);/*查找第i-1个结点*/if(p=NULL)Printf(第d个结点不存在”,i-1);returnNULL;elseif(p->Next=NULL)Primf("第d个结点不存在i);returnNULL; else s = p->Ne×t;*s指向第i个结点*/p->Ne×t = s->Ne×t;/*从链表中删除*/free(s);/*释放被删除结点*/return PtrL;12、链表不具备的特点是可随机访问任一节点插入删除不须要移动元素不必事先估计存储空间所需空间与其长度成正比13、带头结点的单链表head为空的判定条件是 2 head=NULL head->next=NULL(3)head->next=head(4)head!=NLL14、如果最常用的操作是取第i个结点及其前驱，那么采用4存储方单链表双链表单循环链表顺序表式最节省时间。第三章Chapter3栈(StaCkS)和队列(queues)1、 栈是限定仅能在表尾一端进行插入、删除操作的线性表。2、 栈的特点是“后进栈的元素先出栈"(IaStin,firstout),故栈又称为后进先出表(LIFO)o3、 一个栈是一些元素的线形列表，其中元素的插入和删除均在表的同一端进行。插入和删除发生的一端称为栈顶(thetopofthestack)o4、 第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素。5、 连续栈(COntigUOUSStaCk)的类型定义#defineMaxStack50TypedefstructdatatypestackMaxStack;inttop;JSeqstack;Seqstack*s;6、 判断栈是否已满？viodPush(Seqstack*s,datatypeX)(if(s->top>=Ma×Stack-l)printf(aoverflow,);elses->top+;s->stacks->top=x;)7、 判断栈是否为空？datatypepop(Seqstack*s)if(s->top<0)printf(uUnderfIoww);return(NULL);return(s->stacks->top);s->top-;)8、 返回栈顶元素的值，栈不发生变化。datatypetop(Seqstack*s)if(s->top<0)printf("underflow”)；return(NULL);return(s->stacks->top);)9、 链栈(LinkedStaCk)的类型定义栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedefstructstacknodedatatypedatastructstacknode*nextJstacknode10、链式栈的特点：链式栈无栈满问题；空间可扩充；插入与删除仅在栈顶处执行；链式栈的栈顶在链头；适合于多栈操作。11、栈是限定仅能在表的一端进行插入、删除操作的线性表。12、栈的元素具有后进先出的特点。13、栈顶元素的位置由栈顶指针的指示，进栈、出栈操作要修改栈顶指针。14、抽象数据类型队列的定义：队列(QUeUe)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front),允许插入的一端称为队尾(rear)。15、队列亦称作先进先出(FirStInFirStoUt)的线性表，简称FlFo表。16、双端队列：就是限定插入和删除操作在表的两端进行的线性表。17、链队列结点定义：typedefstructQnodeQEIemTypedata;structQNode*next;QNode,*QueuPtr;18、队列的顺序存储结构称为顺序队列，在队列的顺序存储结构中，除了用一组地址连续的储存单元依次存放从队头到队尾的元素之外，尚需要附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。19、在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。20、栈的特点是先进后出,队列的特点是先进后出o21、栈和队列的共同特点是只允许在端点处插入和删除元素o22、一个栈的进栈序列是a,b,c,d,e,那么栈的不可能的输出序列是（八）edcba(B)decba(C)dceab(D)abcde23、假设一个栈的进栈序列是pl,p2,p3,，pn。其输出序列为1,2,3,，n,假设p3=l,那么PI为C。（八）可能是2(B)一定是2(C)不可能是2(D)不可能是324、设有一个空栈，栈顶指针为100OH(十六进制，下同)，现有输入序列为1、2、3、4、5,经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后，输出序列是3,栈顶指针是一8。5、4、3、2、12、12、33、41002H1004H1005H1003H24、一个队列的入队序列是假设1,2,3,4,那么队列的输出序列是B o(A) 4, 3, 2, 1 1, 2, 3, 4(C)1,4,3,2(D)3,2,4,125、假设用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再参加两个元素后，rear和front的值分别是一Bo（八）1和5(B)2和4(C)4和2(D)5和126、有5个元素，其入栈次序为A、B、C、D、E,在各种可能的出栈次序中，以元素C、D最先出栈(即C第一个且D第二个出栈)的次序有哪几个？C、D B、An EC、 D、 E、 B、 AC、D、B、E、A第六章树和二叉树1、树型结构是一类重要的非线性结构。2、树的定义：树是n(n>=O)个结点的有限集T,T为空时称为空树，否那么它满足如下两个条件：(1)有且仅有一个特定的称为根的结点；(2)当n>l时，其余结点可分为m(m>0)个互不相交的有限集Tl,T2,T3Tm,其中每个子集又是一棵树，并称其为根的子树。3、根本术语结点一一表示树中的元素，包括数据项及假设干指向其子树的分支结点的度(degree)结点拥有的子树数叶子(Ieaf)度为O的结点孩子(Child)结点子树的根称为该结点的孩子双亲(ParentS)孩子结点的上层结点叫该结点的兄弟(Sibling)同一双亲的孩子树的度一一一棵树中最大的结点度数结点的层次(IeVel)从根结点算起，根为第一层，它的孩子为第二层深度(depth)树中结点的最大层次数森林(forest)m(m0)棵互不相交的树的集合例题:结点A的度：3叶子：K, L, F, G,结点B的度:结点M的度:结点A的层次: 结点M的层次:M,I9J树的深度：4树的度：3结点I的双亲：D结点L的双亲：EG为堂兄弟结点A是结点F,G的祖先结点A的孩子：B, C,结点B的孩子：E, F结点B, C, D为兄弟 结点K, L为兄弟4、二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。性质1:在二叉树的第i层上至多有2i-l个结点（i>=l）0性质2：深度为k的二叉树至多有2k1个结点（k>=l）0性质3：对任何一棵二叉树T,如果其终端结点数为n,度为2的结点数为n2,那么0=n2+lo性质4：具有n个结点的完全二叉树的深度为Uog2n+1。性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第IJog2n+1层，每层从左到右），那么对任一结点i（l<=i<=n）,有：（1）如果i=l,那么结点i无双亲，是二叉树的根；如果i>l,那么其双亲是结点IJZ2。（2）如果2i>n,那么结点i为叶子结点，无左孩子；否那么，其左孩子是结点2i。（3）如果2i+l>n,那么结点i无右孩子；否那么，其右孩子是结点2i+Io一棵深度为k且有2kl个结点的二叉树称为满二叉树。如:5、二叉树的存储结构顺序存储结构defineMAX-TREE-SIZE100TypedefTeIemTypeSqBiTreeMAX-TREE-SIZE;SqBitreebt;缺点是有可能对存储空间造成极大的浪费。链式存储结构二叉链式存储结构typedefstructBiTNodeTEIemTypedata;structBiTNode*lchild,*rchild;BiTNode/BiTree;三叉链表typedefstructnodedatatypedata;structnode*lchild,*rchildz*parent;JD；6、遍历二叉树二叉树是由三个根本单元组成：根结点、左子树和右子树。假设限定先左后右，那么只有前三种情况，分别称之为先（根）序遍历，中（根）序遍历和后（根）序遍历。（1）先序遍历算法假设二叉树为空树，那么空操作；否那么， 访问根结点； 先序遍历左子树； 先序遍历右子树。voidPreOrder(BiTreebt)/*先序遍历二叉树bt*/if(bt=NULL)return;/*递归调用的结束条件*/Visite(bt->data);/*访问结点的数据域*/PreOrder(bt->lchild;/*(2)先序递归遍历bt的左子树*/PreOrder(bt->rchild);/*先序递归遍历bt的右子树*/例题：©先序遍历序列：ABDCvoidpreorder(JD*bt)if(bt!=NLL)printf(',%dt",bt->data);preorder(bt->lchild);preorder(bt->rchild);(2)中序遍历算法假设二叉树为空树，那么空操作；否那么， 先序遍历左子树； 访问根结点； 先序遍历右子树。VOidlnorder(BiTreebt)/*先序遍历二叉树bt*/if(bt=NULL)return;/*递归调用的结束条件*/InOrder(bt->lchild);/*先序递归遍历bt的左子树*/Visite(bt->data);/*访问结点的数据域*/InOrder(bt->rchild);/*先序递归遍历bt的右子树*/例题：(3)后序遍历算法假设二叉树为空树，那么空操作；否那么, 先序遍历左子树； 先序遍历右子树； 访问根结点。voidPostOrder(BiTreebt)/*后序遍历二叉树bt*/if(bt=NULL)return;/*递归调用的结束条件*/PostOrder(bt->lchild);/*后序递归遍历bt的左子树*/PostOrder(bt->rchild);/*(2)后序递归遍历bt的右子树Visite(bt->data);/*访问结点的数据域*/例题：后序遍历序列：DBCA(4)层次遍历所谓二叉树的层次遍历，是指从二叉树的第一层(根结点)开始，从上至下逐层遍历，在同一层中，那么按从左到右的顺序对结点逐个访问。层次遍历序列：1234567、例题：1、先序序列：Abcdefghk中序序列：Bdcaehgkf后序序列：Dcbhkgfek层次序歹|J：Abecfdghk假设先序遍历此二叉树，按访问结点的先后次序将结点排列起来，其先序序列为：-+a*b-cdef按中序遍历，其中序序列为：a÷b*c-d-ef按后序遍历，其后序序列为：abcd-*+ef-8、(1)查询二叉树中某个结点StatusPreorder(BiTreeTfEIemTypex,BiTree&p)假设二叉树中存在和X相同的元素，那么p指向该结点并返回OK,否那么返回FALSEif(T)if(T->data=x)p=T;return0K,elseif(Preorder(T->lchild,x,p)returnOK;else(Preorder(T->rchild,x,p)returnOK;)eseifelsereturnFALSE;(2)计算二叉树中叶子结点的个数intCountLeaf(BiTreeT)返回指针T所指二叉树中所有叶子结点个数if(!T)return0;if(!T->lchild&&!T->rchild)return1;else(m=CountLeaf(T->lchild);n=CountLeaf(T->rchild);return(m+n);/else/CountLeaf(3)求二叉树的深度(后序遍历)intDepth(BiTreeT)/返回二叉树的深度if(!T)depthval=O;elsedepthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+(depthLeft>depthRight?depthLeft:depthRight);)returndepthval;)(4)按先序遍历序列建立二叉树StatusCreateBiTree(BiTree&T)按先序次序输入二叉树中结点的值(一个字符)，空格字符表示空树，构造二叉链表表示的二叉树Tscanf(&ch);if(ch='')T=NULL;elseif(!T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T->data=Ch;生成根结点CreateBiTree(T->lchild);构造左子树CreateBiTree(T->rchild);构造右子树ReturnOK;CreateBiTree9、遍历二叉树的非递归算法(1)先序遍历二叉树的非递归算法voidinorder(JD*r)先序遍历二叉树非递归算法inti=0;JD*p,*sM;p=r;dowhile(p!=NULL)printf(',%dt",p->data);if(p->rc!=NULL)si+=p->rc;p=p->lc;)if(i>O)p=s-i;while(i>O11p!=NULL);(2)中序遍历二叉树的非递归算法voidinorder(JD*r)先序遍历二叉树非递归算法inti=0;JD*p,*sM;p=r;dowhile(p!=NULL)si÷+=p;p=p->lc;)if(i>0)p=s-i;printf("%dt',p->data);p=p->lc;)if(i>O)p=s-i;while(i>011p!=NULL);(3)后序遍历二叉树的非递归算法voidinorder(JD*r)先序遍历二叉树非递归算法P=Cints2M,bJ=0;JD*p,*slM;dowhile(p!=NULL)sli-l=p;s2i+=0;p=p->lc;while(i>0&&(s2i-l=l)p=sl-i;printf(u%dtn,p->data);if(i>O)p=s-i;printf("%dt',p->data);p=p->lc;)if(i>O)s2i-l=l;p=sli-l;p=p->rc;while(i>O);11、线索二叉树：以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能在结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需的信息，可增加标志域；IchildLtagdataRtagrchild1.tag=O,Ichild域指示结点的左孩子；Ltag=I,Ichild域指示结点的前驱。Rtag=O,rchild域指示结点的右孩子；Rtag=I,rchild域指示结点的后驱。以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索，加上线索的二叉树称之为线索二叉树。(1)先序线索二叉树先序序列：ABCDE先序线索二叉树（3）后序线索二叉树后序序列：CBEDA后序线索二叉树12、树的存储结构双亲表示法a0b1C1d2e2f3g5b5i5dataparent#defineMAX_TREE_SIZE100typedefstructPTNode结点结构EIemTypedata;intparent;/双亲位置域PTNode;typedefstruct树结构PTNodenodesMAX_TREE_SIZE;intr,n;/根结点的位置和结点个数PTree;孩子表示法带双亲的孩子链表孩子兄弟表示法链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。typedefstructnodedatatypedata;structnode*fch,*nsib;JD;13、树和森林与二叉树的转换二叉树对应在兄弟之间加一连线。加线:抹线:对每个结点，除了其左孩子外，去除其与其余孩子之间的关系,旋转:以树的根结点为轴心，将整树顺时针转45°。13、将二叉树转换成树 加线：假设P结点是双亲结点的左孩子，那么将P的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与P的双亲用线连起来. 抹线：抹掉原二叉树中双亲与右孩子之间的连线 调整：将结点按层次排列，形成树结构14、森林转换二叉树（1）将各棵树分别转换成二叉树.（2）将每棵树的根结点用线相连.3）以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构EAAG14、二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线,及沿右分支搜索到的所有右孩子间E连线全部抹掉，使之变成孤立的二叉树.复原：将孤立的二叉树复原成15、树和森林的遍历树的遍历两种次序遍历树的方法：一种是先根（次序）遍历树,0<即先访问树的根结点,然后依次先根遍历根的每棵子树；一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后访问根结点。例题:先根序列：ABCDE后根序列：BDCEA森林的遍先序遍历：Abcdefghij中序遍历：Bcdafehjig16、赫夫曼树及其应用例题:w=5z29,7,8,14,23,3,11习题：1、由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法B。（八）正确(B)错误2、某二叉树的先序遍历序列和后序遍历序列正好相反，那么该二叉树一定是D_o（八）空或只有一个结点(B)完全二叉树(C)二叉排序树9高度等于其节点数3、 深度为5的二叉树至多有1个结点。（八）16(B)32(C)31(D)104、根据使用频率为5个字符设计的赫夫曼编码不可能是J(A) 111,110,10,01,00(B) 000,001,010,011,1(C) 100,11,10,1,0(D) 001,000,01,11,105、树和二叉树的主要差异是树的结点个数至少为1,而二叉树的结点个数可以为0(2)树中结点的最大度数没有限制，而二叉树结点的最大度数为2(3)树的结点无左、右之分，而二叉树的结点右左、右之分。6、深度为k的完全二叉树至少有个结点，至多有个结点，假设按自上而下，从左到右次序给结点编号(从1开始)，那么编号最小的叶子结点的编号O7、一棵二叉树的第i(il)层最多有个结点；一棵有n(n>0)个结点的满二叉树共有个叶子结点和_个非叶子结点O8、二叉树的先序、中序和后序序列分别如下，其中有一些看不清的字母用*先序序列是：*BC*FG中序序列是：CB*EAG*后序序列是：*EDB*FA©9、将右图所示的树转化为二叉树，并写出先序遍历,结果。解：©中序遍历和后序遍历的表示，请构造出一棵符合条件的二叉树并画出该二叉树。先序：Abefgcdhi中序：Efgbchida后序：GF日HDCBA10、设给定权集w=2,3,4,7,8,9,试构造关于W的一棵赫夫曼树，并求其加权路径长度WPL0配排序。f插入排序交换排序选择排序归并排序分配排序WPL=(9+7+8)*2+4*3+(2+3)*4=80第十章内部排序1、内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分（直插排序、二分排序、希尔排序）（冒泡排序、快速排序）（直选排序、树型排序、堆排序）（二路归并排序、多路归并排序）（多关键字排序、基数排序）-2、直接插入排序直接插入的算法实现voidsort(NODEarray,intn)待排序元素用一个数组array表示，数组有n个元素inti,j;NODEx;/x为中间结点变量for(i=l;i<n;i+)/i表示插入次数,共进行n-1次插入x=arrayi;把待排序元素赋给Xj=i-l;while(j>=0)&&(x.key<arrayj.key)arrayj+l=arrayj;j;顺序比拟和移动arrayj+l=x;)例如，n=6,数组R的六个排序码分别为：17,3,25,14,20,9。它的直接插入排序的执行过程如图7-1所示。201425012345第一次插入(317)2514209第二次插入(31725)14.209第三次插入(3141725)9第四次插入(31417V2025)9J第五次插入(3t914172025)图10-1直接插入排序示例初始状态直接插入排序的时间复杂度为052)。直接插入算法的元素移动是顺序的，该方法是稳定的。3、希尔排序希尔排序的时间复杂性在O(nlog2n)和0(n2)之间，大致为0(nl.3)。由于希尔排序对每个子序列单独比拟，在比拟时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。例如，n=8,数组array"的八个元素分别为:91,67,35,62,29,72,46,57o下面用图10-2给出希尔排序算法的执行过程。初始状态,selp=49167356229724657第一趟结果,step=22967355791724662第二趟结果，Step=I2957356246679172第三趟结果2935465762677291图102希尔排序算法的执行过程4、 交换排序1)冒泡排序冒泡排序的算法实现voidBubblesort(NODEarray,intn)inti,jzflag;当flag为0那么停止排序NODEtemp;for(i=l;i<n;i+)/i表示趟数，最多n-1趟fag=0;开始时元素未交换for(j=n-l;j>=i;j-)if(arrayj.key<arrayj-l.key)发生逆序temp=arrayj;arrayj=arrayj-l;arrayj-l=temp;fag=l;交换，并标记发生了交换if(flag=0)break;)例如，n=6,数组R的六个排序码分别为：17,3,25,14,20,9。下面用图10-3给出冒泡排序算法的执行过程。初始状态0(1713I22531442059)I第一趟排序L3(17t9_|2514I20)第二趟排序39(17L14I2520)I第三趟排序39L14(172025)笫四趟排序391