数据结构知识点总结-

数据结构知识点总结-数据结构知识点总结绪论时间复杂度T（n）=O（f（n））通常用：常量阶O(1)线性阶O(n)平方阶O(n^2)对数阶O(logn)指数阶O(2^n)计算的复杂性：算法的计算量的大小算法的时间复杂度取决于问题的规模和待处理数据的初态。算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。（1）有穷性（2）确定性（3）可行性（4）输入（5）输出从逻辑上可以把数据结构分为线性结构和非线性结构栈与数据的存储结构无关串是线性结构有序表属于逻辑结构连续存储设计时，存储单元的地址一定连续一、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的“原料”。二、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。三、数据对象：是性质相同的数据元素的集合，是数据的一个子集。数据结构知识点总结-全文共47页，当前为第1页。四、数据机构：是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。数据结构知识点总结-全文共47页，当前为第1页。五、元素在存贮结构（1）物理结构（存储结构）：它包括数据元素的表示和关系。（2）逻辑结构六、位bit：在计算机中表示信息的最小单位是二进制的一位七、元素element/节点node：位串八、数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串九、数据元素之间的关系在计算机中有两种不同的表示方法，顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构（借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系）和链式存储结构（借助指示元素存储地址的指针表示数据元素之间的逻辑关系）。算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。（1）有穷性（2）确定性（3）可行性（4）输入（5）输出算法设计要求：（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求-------------------------------------------------------------------------------线性表：采用顺序存储，便于进行插入和删除的操作顺序表的优点：结构紧凑，存储空间利用率高，操作简单。（存储密度大）数据结构知识点总结-全文共47页，当前为第2页。数据结构知识点总结-全文共47页，当前为第2页。当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。若某线性表最常用的操作是存取任一指定序号的元素和最后进行插入和删除运算，则利用顺序表的存储方式最节省时间；若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除一个元素，则采用仅有尾指针的单循环链表的存储方式最节省时间。设一个链表最常用的操作是在末尾插入结点或删除尾结点，则利用带头结点的双循环链表的存储方式最节省时间。若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则利用带头结点的双循环链表的存储方式最节省时间。链表的优点：在空间的合理利用上和插入、删除时不需要移动，是线性表的首选存储结构。（不必事先估计存储空间、所需空间与线性长度成正比）缺点：求线性表的长度时不如顺序存储结构（不可随机访问任一元素）线性表在顺序存储时，查找第i个元素的时间同i的值无关；线性表在链式存储时，查找第i个元素的时间同i的值成正比。对于顺序存储的线性表，访问结点的时间复杂度为O（1），插入和删除结点的时间复杂度为O（n）。对于链式存储的线性表，访问第i个元素的时间复杂度为O（n）。对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为O(n)根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分为单链表和多重链表；根据指针的连接方式，链表又可分为动态链表和静态链表。数据结构知识点总结-全文共47页，当前为第3页。链表的头结点的作用：数据结构知识点总结-全文共47页，当前为第3页。静态链表中指针表示的是下一个元素地址静态链表能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。线性表是线性结构的基本形式线性表的逻辑结构线性表的定义线性结构的特点是数据元素之间是一种线性关系，数据元素“一个接一个的排列”。线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，记为：(a1，a2，…ai-1，ai，ai+1，…an)；其中：n为表长，n＝0时称为空表。表中相邻元素之间存在顺序关系：ai-1称为ai的直接前趋，ai+1称为ai的直接后继。a1，…an-1有且仅有一个直接后继；（非空线性表）a2，…an有且仅有一个直接前趋。（非空线性表）线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序表。存储的特点：物理上的相邻实现了逻辑相邻的表示。数据结构知识点总结-全文共47页，当前为第4页。顺序存储能随机访问第i个元素：数据结构知识点总结-全文共47页，当前为第4页。设a１的存储地址为Loc(a１)，每个数据元素占d个存储地址，则第i个数据元素的地址为：Loc(ai)=Loc(a１)+(i-1)*d1≤I≤n顺序表插入运算时间主要消耗：数据的移动。一般情况下，在第i（1<=i<=n）个元素之前插入一个元素时，需将第n至第i（共n-i+1）个元素向后移动一个位置。（在第i个位置上插入x，从ai到an都要向下移动一个位置，共需要移动n－i＋1个元素。）一般情况下，删除第i（1<=i<=n）个元素时，需从第i+1至第n（共n-i）个元素向前移动一个位置i的取值范围为：1≤i≤n+1（即有n＋1个位置可以插入）。设在第i个位置上作插入的概率为Pi：在等概率情况下：Pi=1/(n+1)，则平均移动数据元素的次数则为：这说明：在顺序表上做插入操作需移动表中一半的数据元素。显然顺序表上插入时间复杂度为Ｏ(n)。intSeqlistInsert(A[],n,i，x){if(i<1||i>n)//检查插入位置的正确性{Printf(“参数非法”);return0;//插入位置参数错，返回错误代码0数据结构知识点总结-全文共47页，当前为第5页。}数据结构知识点总结-全文共47页，当前为第5页。else{for(k=n;k>=i;k--)A[k-1]<=A[k];//结点移动A[i]<=x;//新元素插入n<=n+1;//n指向新的最后元素returnn;//插入成功，返回成功代码}}线性表的删除运算是指将表中第i个元素从线性表中去掉。SeqlistDelete(A[],n,i){if(i<1ORi>n)//检查空表及删除位置的合法性{Printf(“参数非法”);return0;//不存在第i个元素，返回错误代码0}else{for(k=i+1;k<n;k++)A[k-1]<=A[k];//数据元素向前移动数据结构知识点总结-全文共47页，当前为第6页。n<=n-1;//n指向新的最后元素数据结构知识点总结-全文共47页，当前为第6页。returnn;//删除成功，返回成功代码}删除算法的时间性能分析与插入运算相同，其时间主要消耗在了移动元素上。计算数据移动的次数：某次删除数据的移动次数与具体位置有关。求平均性能。删除第i个元素时，其后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素。i的取值范围为：1≤i≤n（即有n个位置可以删除）。设在第i个位置上作删除的概率为Pi，平均移动数据元素的次数：在等概率情况下：Pi=1/n，则平均移动数据元素的次数则为：这说明顺序表上作删除运算时大约需要移动表中一半的元素。显然该算法的时间复杂度为Ｏ(n)。线性表链式存储结构，不要求逻辑上相邻的两个数据元素物理上也相邻，因此不需要用地址连续的存储单元来实现。链表是通过一组任意的存储单元来存储线性表中的数据元素的，对每个数据元素ai，除了存放数据元素的自身的信息ai之外，还需要和ai一起存放其后继ai+1所在的存贮单元的地址，这两部分信息组成一个“结点”。存放数据元素信息的称为数据域，存放其后继地址的称为指针域。链表的表示：链表是由一个个结点构成的。数据结构知识点总结-全文共47页，当前为第7页。结点的申请：p=newLNode;结点的释放：deletep；数据结构知识点总结-全文共47页，当前为第7页。在某结点后面插入新结点：设p指向单链表中某结点，s指向待插入的值为x的新结点，将*s插入到*p的后面。操作如下：①s->next=p->next;②p->next=s;注意：两个指针的操作顺序不能交换。在某结点前面插入新结点：设ｐ指向链表中某结点，ｓ指向待插入的值为x的新结点，将*s插入到*p的前面。与后插不同的是：首先要找到*p的前驱*q，然后再完成在*q之后插入*s。设单链表头指针为L，操作如下：q=L;while(q->next!=p)q=q->next;//找*p的直接前驱s->next=q->next;q->next=s;删除结点：设p指向单链表中某结点，删除*p。作业1：线性表中元素为整型，以50为界，小于50在左，大于50在右。作业讲解：x<=A[i];数据结构知识点总结-全文共47页，当前为第8页。 while(A[j]>=xandi<j)数据结构知识点总结-全文共47页，当前为第8页。 { j<=j-1; if(A[j]<x) {A[i]<=A[j]; i<=i+1;}while(A[i]<xandx<j) i<=i+1;if(A[i]>=x){A[j] <=A[i];j<=j-1;}插入a1：*p=a1;改为：p->date=a1;指针p指向对象date=a1，该对象是一个结构体，指向结构体里a1那部分删除a1并把存储空间解放：free（p）；二、链表的构造q<=NULL;for(j=n;i>=1;i--)数据结构知识点总结-全文共47页，当前为第9页。{数据结构知识点总结-全文共47页，当前为第9页。p<=(NODE*)malloc(sizeof(NODE));p->date<=an;将an替换为ai注：i此处为n-1p->next<=NULL;把指针设为空指针，替换为qq<=p;}考虑链表的头指针当ai未插入时：算法：CreatLinkList(n)构造链表，n为节点{q<=NULL;for(i=n;i>=1;i--){p<=(NODE*)malloc(sizeof(NODE));scanf(ai);p->date<=ai;p->next<=q;q<=p;}return(p);}数据结构知识点总结-全文共47页，当前为第10页。注：此时p、q一样∵已被赋值给对方数据结构知识点总结-全文共47页，当前为第10页。作业4：倒过来。从前节点到后节点。头指针headp<=head;从头指针出发，依次输出节点。可用for循环或while循环（不确定循环次数时用）p<=head;while(p=\NULL){printf(p->data);p<=p->next;}三、链表的插入算法：假定：在表中值为x的节点前面插入一个值为y的节点。分析：1.空链2.表中第1个节点的值为x3.表中有一个值为x的节点4.表中没有值为x的节点数据结构知识点总结-全文共47页，当前为第11页。5.表中有多个值为x的节点。数据结构知识点总结-全文共47页，当前为第11页。NODE*InsertLinkList(head,x,y){q<=(NODE*)malloc(sizeof(NODE));q->data<=y;q->next<=NULL;if(head=NULL)head<=q;elseif(head->date=x){q->next<=head;head<=q;}else{r<=head;p<=head->next;while(p->data=/xandp=\NULL)数据结构知识点总结-全文共47页，当前为第12页。p<=p->next;数据结构知识点总结-全文共47页，当前为第12页。if(p=\NULL){q->next<=p;r->next<=q;}elser->next<=q;}return(head);}假定：删除表中值为x的节点分析：1.空表； 2.第1个节点的值为x； 3.在表中有值为x的节点； 4.在表中没有值为x的节点NODE*=DeleteLinkList(head,x,t)（返回指针）a.值参callbyvalue数据结构知识点总结-全文共47页，当前为第13页。{b.变参callbyaddress数据结构知识点总结-全文共47页，当前为第13页。 s<=NULL; if(head=NULL) printf("这是一个空表") elseif(head->data=x) { s<=head; head<=head->next; } else q<=head;（返回内容不同） p<=head->next; while(p->data=\xandp->next=\NULL) { q<=p; p<=p->next; } if(p->data=x) { s<=p; q->next<=p->next;数据结构知识点总结-全文共47页，当前为第14页。 }数据结构知识点总结-全文共47页，当前为第14页。 else printf("表中没有值为x的节点")；}if(s=\NULL){ t<=s->data; free(s); return(head);（返回值）}}四、链式存贮结构的栈五、链式存贮结构的队列六、循环链表循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。双向链表在双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。二叉链表的特征：n个结点，则链指针所指的为n-1二叉链表总链域个数2n，头指针指向根结点，其余n-1个结点数据结构知识点总结-全文共47页，当前为第15页。∴在有n个结点的K叉树链表中，值为非空的链域个数为n-1；数据结构知识点总结-全文共47页，当前为第15页。空的链域个数为kn-（n-1）=kn-n+1对于任意给定的一个线性表：L=(a1,a2,……,an),写出构造一个链表的算法。节点类型及其算法头部约定如下：structnode{ElemTypedata；structnode*next；}；typedefstructnodeNODE；NODE*CreateLinkList(intn)算法如下：NODE*CreateLinkList(intn){q(NODE*)malloc(sizeof(NODE));scanf(an);q->dataan;q->nextNULL;for(i=n-1;i≥1;i--){p(NODE*)malloc(sizeof(NODE));scanf(ai);数据结构知识点总结-全文共47页，当前为第16页。p->dataai;数据结构知识点总结-全文共47页，当前为第16页。p->nextq;qp;}return(p);}有一个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算数据域为x的结点个数。链表节点结构定义如下：datanext解：遍历该链表的每个结点，每遇到一个结点，判断其值是否为x，是的话就计数。结点个数存储在变量n中。算法如下：intCounter(head,x)

{

intn=0;

p<=head;

while(p!=NULL)

{

if(p->data=x)数据结构知识点总结-全文共47页，当前为第17页。n<=n+1;

p<=p->next;

}

return(n);

}

数据结构知识点总结-全文共47页，当前为第17页。-------------------------------------------------------------------------------栈和队列栈：限定仅在表尾进行插入或删除栈：是限定仅在表尾进行插入或删除操作的线性表表尾（栈顶）表头（栈底）假设栈S=（a1，a2，…，an），则称a1为栈底元素，an为栈顶元素。栈中元素按a1，a2，…，an的次序进栈，退栈的第一元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进后出的线性表。压栈算法：intPushStack(s[],top,x){ if(top>=SMAX) { printf("overlow");数据结构知识点总结-全文共47页，当前为第18页。 return0;数据结构知识点总结-全文共47页，当前为第18页。 } else { S[top]<=x; top=top++; }}出栈算法：ElemTypePopstack(s[],top,bottom){ if(top<=bottom) { printf("overlow"); } return0; } else { top<=top-1; y<=S[top];数据结构知识点总结-全文共47页，当前为第19页。 returny;数据结构知识点总结-全文共47页，当前为第19页。 }作业2：为了节省空间，两个栈共享一段内存，写出这两个栈的压栈及出栈算法。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续地内存空间时，应将两栈的栈底，分别设在这片内存空间的两端，这样，当两个栈的栈顶在栈空间的某一位置相遇时，才会产生上溢。两个栈共享空间的条件：两栈顶指针值相减的绝对值为1（两栈顶指针相邻）数组Q[0..n-1]作为一个环形队列，f为当前队头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数总小于n，计算队列中元素个数的公式是(n+r-f)mod队列特点：先进先出，队头出，队尾进，当队尾大于队头时，说明进的比出的多，此时元素个数为Rear–Front循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是(rear-front+m)MODm循环队列两指针front指示队列头元素位置rear指示队列尾元素位置初始化建空队列时，令front=rear=0，插入新的尾元素->尾指针+1；删除队列头元素->头指针+1数据结构知识点总结-全文共47页，当前为第20页。头指针始终指向队列头元素数据结构知识点总结-全文共47页，当前为第20页。尾指针始终指向队列尾指针的下一个位置在栈满的情况下，不能作进栈运算，否则产生“上溢”。队列：1.什么是队列？也是一种特殊的线性表（插入在表的一端，删除在表的另一端）队列：先进先出数据结构知识点总结-全文共47页，当前为第21页。区别于线性表：插入、删除在同一端。数据结构知识点总结-全文共47页，当前为第21页。2.队列的操作：1.插入。判别队列空间“空”或“满”a.另设一个标志位以区别队列“空”或“满”b.少用一个元素空间，约定以“队列头指针在队列尾指针的下一个位置（指环状的下一位置）”上作为队列呈“满”状态的标志总结：若Rear>Front，元素个数为Rear-Front；若Rear<Front，元素个数为(Rear-Front+N)%N(N为队列容量)如何判断其满？intQueueInsert(Q[],front,rear,x){ if(rear>=QMAX) { printf("Overlow");数据结构知识点总结-全文共47页，当前为第22页。 return0;数据结构知识点总结-全文共47页，当前为第22页。 } else { rear=rear+1; Q[rear]<=x; return1; }}2.删除：ElemTypeQueueDelete(Q[],front,rear){ if(rear<=front) { printf("Overlow"); return0; } else { front=front+1; }}数据结构知识点总结-全文共47页，当前为第23页。以上为错误算法,rear<QMAX才能插入，空队列：rear=front指针重叠“假满”∵删除/插入一次无事，N次则无用了。插入满了只能删除，rear、front均在尾，插入为满，删除为空∴成为了无用队列。数据结构知识点总结-全文共47页，当前为第23页。正确的队列插入与删除算法如下：intQueueInsert(Q[],front,rear,x){ if((rear+1)modQMAX=front) { printf("Overlow"); return0; } else { modQMAX数据结构知识点总结-全文共47页，当前为第24页。数据结构知识点总结-全文共47页，当前为第24页。 return1; }}ElemTypeQueueDelete(Q[],front,rear){ if(rear<=front) { printf("Overlow"); return0; } else { modQMAX }3.队列的应用keyboardbuffer32byte如何解决“假满”？---------还有空的地方却不能再插入。答：接为环状（上弯下弯不同）总结：优点：1.不要求连续的、大块的内存，充分地利用内存空间 2.动态的存储结构不足：1.空间复杂度增加数据结构知识点总结-全文共47页，当前为第25页。2.操作（算法）复杂些数据结构知识点总结-全文共47页，当前为第25页。双端队列：限定插入和删除操作在表的两端进行的线性表。这两端分别是端点1和端点2。在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则该双端队列就蜕变成两个栈底相邻接的栈了。链队列：用链表表示的队列。-------------------------------------------------------------------------------数组和广义表数据结构知识点总结-全文共47页，当前为第26页。从一给定的数组A[]中删除元素值在x到y（x≤y）之间的所有元素（假定数组中有n个元素）。算法头部约定如下：数据结构知识点总结-全文共47页，当前为第26页。voidDelete(A[],n,x,y)本题的算法思想是：先将A[]中所有元素值在x≤y之间的元素置成一个特殊的值（如0），并不立即删除它们，然后从最后向前依次扫描，对于该特殊值的元素便移动其后面的元素将其删除，这种算法比每删除一个元素后立即移动其后元素效率要高一些。实现本题功能的过程如下：voidDelete(A[],n,x,y)

{

for(i1;i≤n;i++)if(A[i]≥x&&A[i]≤y)A[i]0;for(in;i≥1;i--)if(A[i]==0){for(kj;k≤(n-1);k++)A[k]A[k+1];nn-1;}}---------------------------------------------------------------------树和二叉树数据结构知识点总结-全文共47页，当前为第27页。设一棵Huffman树中度为2的节点数为n2，则该树的总节点数为2n2+1数据结构知识点总结-全文共47页，当前为第27页。度的概念：结点的度指结点的孩子结点个数，例如度为2就是有2个孩子结点的结点；叶子结点就是度为0的结点，没有孩子结点的结点.按照这个概念，度为2的结点树为n2,即为非叶子结点，Huffman树中叶子结点个数是非结点个数+1，所以总结点个数：n2+n2+1有一棵非空的二叉树（第0层为根结点），其第i层上至多有2i个结点。对于n个节点的满二叉树，设叶节点数为m，分枝节点数为k，则n=k+m满二叉树中，除了叶子结点，就是分支结点。数据结构知识点总结-全文共47页，当前为第28页。数据结构知识点总结-全文共47页，当前为第28页。数据结构知识点总结-全文共47页，当前为第29页。将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。数据结构知识点总结-全文共47页，当前为第29页。已知完全二叉树的第八层有8个结点，则其叶子结点数是68。数据结构知识点总结-全文共47页，当前为第30页。注意是根结点为第1层，第7层该有26=64个结点，第八层有8个结点用去第7层的4个结点，所以叶子结点总数：64-4+8=68。数据结构知识点总结-全文共47页，当前为第30页。叶子的带权路径长度=权值*路径长度数据结构知识点总结-全文共47页，当前为第31页。树的带权路径长度=所有叶子结点的带权路径长度之和数据结构知识点总结-全文共47页，当前为第31页。已知某二叉树中，有n0个叶节点，n1个度为1的节点，n2个度为2的节点。则：n0=n2+1二叉树采用顺序存储结构（数组形式）和链式存储结构（二叉链表）来存储。高度为k的二叉树至多有2^k-1个节点。二叉树节点数目的算法。counter<=0;voidNumbers(NODE*tree)数据结构知识点总结-全文共47页，当前为第32页。{数据结构知识点总结-全文共47页，当前为第32页。if(tree){counter++;Numbers(tree->Lsubtree);Numbers(tree->Rsubtree);}}设二叉树的根节点的指针为tree，每个节点的结构为：LsubtreedataRsubtree试写一算法，用于输出该二叉树中最大的节点值。算法如下：max<=0;voidMaxNode(NODE*tree){if(tree){if(tree->data>max)max<=tree->data;MaxNode(tree->Lsubtree);MaxNode(tree->Rsubtree);}数据结构知识点总结-全文共47页，当前为第33页。}数据结构知识点总结-全文共47页，当前为第33页。或者：max<=0;voidMaxNode(NODE*tree){if(tree){x<=tree->data;y<=MaxNode(tree->Lsubtree);z<=MaxNode(tree->Rsubtree);reyurn(max(x，y，z));}elsereturn(-∞);}---------------------------------------------------------------------图设有向图G有n个顶点，m条弧，则其邻接表中链上的节点个数为m若一无向图是连通的，且其中有n个顶点和e条边，则必满足e≥n-1数据结构知识点总结-全文共47页，当前为第34页。有向图强连通分量在有向图G中，如果两个顶点vi,vj间（vi<>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(stronglyconnected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(stronglyconnectedcomponents)。记主要特征：强联通分量图中两两都可达，也可见下图实例。按照这个定义，得到图G中的强联通分量共3个：<1,2>,<3,5,6>,<4>数据结构知识点总结-全文共47页，当前为第34页。在一个有n（n≥1）个顶点的有向图中，边数最多为n(n-1)带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中第i列非∞且非O的元素个数有向图中，结点i的入度就是指向i结点的弧的条数,而邻接矩阵是行数据中非0非无穷元素个数为i的出度，列才为入度有向图用邻接矩阵表示后，顶点i的出度等于第i行中非0且非∞的元素个数。数据结构知识点总结-全文共47页，当前为第35页。图的深度优先和广度优先都要弄清楚。深度优先为相连访问（注意退回到还有连接结点没有访问过的那个结点上，广度优先为层次访问,先访问的结点其子树也先访问（子树访问无次序，仅对下层访问有影响）数据结构知识点总结-全文共47页，当前为第35页。广度优先和深度优先遍历序列均可能是不唯一的。---------------------------------------------------------------------查找数据结构知识点总结-全文共47页，当前为第36页。折半查找算法。数据结构知识点总结-全文共47页，当前为第36页。intBinSearch(sqlistr,intk,intn){low1；highn；find0;while(low≤highandnotfind){mid(low+high)/2;if(k<r[mid].key)highmid-1;elseif(k>r[mid].key)lowmid+1;else{imid;find1;}}if(notfind)i0;return(i);}数据结构知识点总结-全文共47页，当前为第37页。数据结构知识点总结-全文共47页，当前为第37页。折半查找法使用于存储结构为顺序存储且按关键字排好序的线性表。在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。数据结构知识点总结-全文共47页，当前为第38页。数据结构知识点总结-全文共47页，当前为第38页。---------------------------------------------------------------------排序在已知待排序文件已基本有序的前提下，效率最高的排序方法是直接插入排序考排序的效率和特点：数据结构知识点总结-全文共47页，当前为第39页。一、插入排序(InsertionSort)

1.基本思想：

每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

2.排序过程：

【示例】：

[初始关键字][49]38659776132749

J=2(38)[3849]659776132749

J=3(65)[384965]9776132749

J=4(97)[38496597]76132749

J=5(76)[3849657697]132749

J=6(13)[133849657697]2749

J=7(27)[13273849657697]49

J=8(49)[1327384949657697]

二、选择排序

1.基本思想：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2.排序过程：

【示例】：

初始关键字[4938659776132749]

第一趟排序后13［38659776492749]

第二趟排序后1327［659776493849]

第三趟排序后132738[9776496549]

第四趟排序后13273849[49976576]

数据结构知识点总结-全文共47页，当前为第40页。第五趟排序后1327384949[979776]

第六趟排序后132738494976[7697]

第七趟排序后13273849497676[97]

最后排序结果1327384949767697

三、冒泡排序(BubbleSort)

1.基本思想：

两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

2.排序过程：

设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

【示例】：

4913131313131313

3849272727272727

6538493838383838

9765384949494949

7697654949494949

1376976565656565

2727769776767676

数据结构知识点总结-全文共47页，当前为第41页。4949497697979797

四、快速排序（QuickSort）

1.基本思想：

在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。

2.排序过程：

【示例】：

初始关键字[4938659776132749］

第一次交换后［2738659776134949］

第二次交换后［2738499776136549］

J向左扫描，位置不变，第三次交换后［2738139776496549］

I向右扫描，位置不变，第四次交换后［2738134976976549］

J向左扫描［2738134976976549］

（一次划分过程）

初始关键字［4938659776132749］

数据结构知识点总结-全文共47页，当前为第42页。一趟排序之后［273813］49［76976549］

二趟排序之后［13］27［38］49［4965］76［97］

三趟排序之后1327384949［65］7697

最后的排序结果1327384949657697

各趟排序之后的状态

五、堆排序(HeapSort)

1.基本思想：

堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

2.堆的定义:N个元素的序列K1,K2,K3,...,Kn.称为堆，当且仅当该序列满足特性：

Ki≤K2iKi≤K2i+1(1≤I≤[N/2])

堆实质上是满足如下性质的完全二叉树：树中任一非叶子结点的关键字均大于等于其孩子结点的关键字。例如序列10,15,56,25,30,70就是一个堆，它对应的完全二叉树如上图所示。这种堆中根结点（称为堆顶）的关键字最小，我们把它称为小根堆。反之，若完全二叉树中任一非叶子结点的关键字均大于等于其孩子的关键字，则称之为大根堆。

3.排序过程：

堆排序正是利用小根堆（或大根堆）来选取当前无序区中关键字小（或最大）的数据结构知识点总结-全文共47页，当前为第43页。记录实现排序的。我们不妨利用大根堆来排序。每一趟排序的基本操作是：将当前无序区调整为一个大根堆，选取关键字最大的堆顶记录，将它和无序区中的最后一个记录交换。这样，正好和直接选择排序相反，有序区是在原记录区的尾部形成并逐步向前扩大到整个记录区。

【示例】：对关键字序列42，13，91，23，24，16，05，88建堆

对于已排好序的、具有12个数据元素的线性表，采用冒泡排序方法排序时最少需要11比较。数据结构知识点总结-全文共47页，当前为第39页。数据结构知识点总结-全文共47页，当前为第40页。数据结构知识点总结-全文共47页，当前为第41页。数据结构知识点总结-全文共47页，当前为第42页。数据结构知识点总结-全文共47页，当前为第43页。冒泡排序法：For(i=0;i<n-1;i++)For(j=0;j<n-1-I;j++)If(a[j]>a[j+1]则交换优化一下冒泡排序法Intf=0;For(i=0;i<n-1;i++){For(j=0;j<n-1-I;j++)If(a[j]>a[j+1])则{F=1；交换}if(！f)break;//如果第一趟排序，发现已经是有序，则退出了，只比较了第一趟的11次

}只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。数据结构知识点总结-全文共47页，当前为第44页。冒泡排序在最坏情况是初始序列为“逆序”，需要进行N-1次排序，进行的比较次数为：∑（i-1），下标从n到2，即n(n-1)/2.数据结构知识点总结-全文共47页，当前为第44页。简单选择排序算法，效率不高voidSelectSort(intr[],intn)

{

for(i1；i≤n-1；i++)

for(ji+1；j≤n；j++)

if(r[j]<r[k