数据结构期末考点总结

第一章绪论数据——所有输入计算机中并被计算机处理的符号。数据元素——数据的基本单位，通常作为一个整体。数据对象——性质相同的数据元素的集合。数据结构——数据元素以及之间存在的关系。1、线性结构；2、集合结构3、树形结构；4、图结构数据结构的形式定义：Data--Structure=(D,S)D——数据元素集合S——关系集合数据的逻辑结构——用形式化方式描述数据元素间的关系。数据的物理结构——数据在计算机中的具体表示。数据类型——一种数据结构和定义在其上的一组操作。可以形式化定义为：Data--Type=(D,S,P)算法的定义是对特定问题求解步骤的一种描述，是指令的有限序列。算法的特性有穷性——算法必须在执行有穷步之后结束，而且每一步都可在有穷时间内完成。确定性——每条指令无二义性。可行性——算法中描述的每一操作，都可以通过已经实现的基本运算来实现。输入——算法有零至多个输入。输出——算法有一个至多个输出。时间复杂度的等级O（1）O（logn）O（n）O（n×logn)O(n2)O(nK）O（Xn）第二章线性表重点：1、链式和线性表两种方式的插入与删除2、单双链表的定义线性表的定义#defineList-Init-Size100#defineListincrement10typedefstruct{Elemtype*elem；intlength；intlistsize；}Sqlist；线性表定位插入StatusListinsert_Sq(Sqlist&L,inti,Elemtypee){if(i1‖iL.length+1)returnERROR;if(L.length=L.listsize){newbase=追加分配新空间L.elem=newbase;L.listsize+=Listincrement;}for(j=L.length-1;j=i-1;--j)L.elem[j+1]=L.elem[j]);L.elem[i-1]=e;++L.length;returnOK;}线性表定位删除StatusListdelete_Sq(Sqlist&L,inti,Elemtype&e){if(i1‖iL.length)returnERROR;e=L.elem[i-1]);for(j=i;jL.length;++j)L.elem[j-1]=L.elem[j]);--L.length;returnOK;}单链表定义：typedefstructLnode{Elemtypedata；structLnode*next；}Lnode，*Linklist；链式定位插入StatusListinsert_L(Linklist&L,inti,Elemtypee){p=L;j=0;while(p&&ji-1){p=p-next;++j}if(!p‖ji-1)returnERROR;new(s);s-data=e;s-next=p-next;p-next=s;returnOK;}链式定位删除StatusListdelete_L(Linklist&L,inti,Elemtype&e){p=L;j=0;while(p-next&&ji-1){p=p-next;++j}if(!(p-next)‖ji-1)returnERROR;q=p-next;p-next=q-next;e=q-data;free(q);returnOK;}双向链表结点的存储结构定义typedefstructDublnode{Elemtypedata;structDublnode*prior；structDublnode*next；}Dublnode,*Dublinklist；了解：有序表的合并voidMergelist_L(Linklist&La,Linklist&Lb,Linklist&Lc){pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&&pb){if(pa-data=pb-data){pc-next=pa;pc=pa;pa=pa-next;}else{pc-next=pb;pc=pb;pb=pb-next;}}pc-next=pa?pa:pb;free(Lb);}第三章、栈与队列重点：1、栈的插入，删除，和取栈顶2、队列的取对头，插入，删除（循环队列）栈的存储结构定义:#defineStack_init_size100;#defineStackincrement10;typedefstruct{Selemtype*base;指向第一个元素（有数）Selemtype*top;指向最后一个元素的下一位（为空）intstacksize;}Sqstack;栈的取栈顶StatusGettop(Sqstacks,Selemtype&e){if(s.top==s.base)returnERROR;e=*(s.top-1);returnOk}栈的插入StatusPush(Sqstack&s,Selemtypee){if(s.top-s.base=s.stacksize){s.base=追加分配空间;s.stacksize+=Stackincrement;}*s.top++=e;returnOk}栈的删除栈顶StatusPop(Sqstack&s,Selemtype&e){if(s.top==s.base)returnERROR;e=*--s.topreturnOk}队列的顺序存储表示与实现typedefstruct{Qelemtype*base;intfront;指向第一个元素（有数）intrear;指向最后一个元素的下一位（为空）}Sqqueue;队空条件:Q.front=Q.rear队满条件:(Q.rear+1)%Maxsize=Q.front队列长度：(Q.rear-Q.front+Maxsise)%Maxsize队的插入：StatusEnqueue(sqqueue&Q,Qelemtypee){if((Q.rear+1)%Maxsize==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%Maxsize;returnOK;}队的删除StatusDequeue(sqqueue&Q,Qelemtype&e){if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%Maxsize;returnOK;}取对头StatusGetHead(sqqueue&Q,Qelemtype&e){if(Q.front==Q.rear)returnERROR;returnQ.base[Q.front];}第四章串重点：串的比较、连接，了解串的插入，删除定义typedefstruct{char*ch;intlength;}Hstring;比较statusstrcompare(S,T){for(i=0;iS.length&&iT.length;++i)if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;}连接Statusconcat(&t,s1,s2){if(t.ch)free(t.ch);if(!(T.ch=(char*)malloc((s1.length+s2.lengrh)*sizeof(char))))exit(overflow);t.ch[0..s1.length-1]=s1.ch[0..s1.length-1];t.length=s1.length+s2.length;t.ch[s1.length..t.length-1]=s2.ch[0..s2.length-1];returnOK;}第五章数组和广义表重点：特殊矩阵，稀疏矩阵（明白思路）对称矩阵aij=aji0≤i,j≤n-1SA[k]=aijk=i(i+1)/2+j（i=j）或k=j(j+1)/2+i（ij）稀疏矩阵一般采用三元组存储一个非零元素。如：三元组（1，5，a）（2，2，b）（3，4，c）（4，7，d）0000a000b00000000c000000000dm×n三元组定义#defineMaxsize=1000typedefstruct{inti,j;elemtypee;}tripletypedefstruct{tripledata[Maxsize+1]intm,n,num;}TSmatrix第六章树与二叉树重点：1、二叉树的遍历和性质，2、树的存储结构及遍历3、哈夫曼树基本概念结点的度:结点拥有子树的数目叶结点:结点的度为零的结点分枝结点:结点的度非零的结点树的度:树中各结点度的最大值孩子:j,k,l称为i的孩子双亲:i称为j,k,l的双亲兄弟:j,k,l互为兄弟祖先:树的根结点到某结点j路径上的所有结点,为结点j的祖先子孙:结点i下的所有结点,称为结点i的子孙结点层次:从根结点到某结点j路径上结点的数目树的深度:树中结点的最大层次有序树:若树中结点的各子树从左到右是有次序的,称该树为有序树,否则为无序树森林:由m棵互不相交的树构成F=(T1,T2,.......Tm)二叉树的性质定义:深度为k且有2k-1个结点的二叉树称为满二叉树定义：深度为k且有n个结点的二叉树，当且仅当n个结点都满足满二叉树的位置编号的升序排列结构时，称为完全二叉树性质1:在二叉树的i层上至多有2i-1个结点。(归纳法证明)性质2:深度为k的二叉树,至多有2k-1个结点。(等比求和)性质3:对任意二叉树BT,若叶结点数为n0,度为2的结点数为n2,则n0=n2+1性质4：具有n个结点的完全二叉树深度为[n2log]+1(取整)性质5：对结点数为n的完全二叉树，第i个结点有如下特征：(1)若i=1则i为根结点，无双亲若i1则双亲为parent(i)=[i/2]；(2)若2in则i无孩子,为叶结点否则lchild(i)=2i；ijkl(3)若2i+1n则i无右孩子否则rchild(i)=2i+1。遍历的访问顺序有三种:1先序访问:根左子树右子树2中序访问:左子树根右子树3后序访问:左子树右子树根递归遍历:中序Voidinorder(bt){if(bt){inorder(bt-lchild);visit(bt-data);inorder(bt-rchild);}}先序Voidpreorder(bt){if(bt){visit(bt-data);preorder(bt-lchild);preorder(bt-rchild);}}后序Voidpostorder(bt){if(bt){postorder(bt-lchild);postorder(bt-rchild);visit(bt-data);}}树的存储结构（书上P135）1双亲表示法：用一组连续的空间存放结点,每个结点用一个域表示该结点的双亲.2孩子表示法：(1)多叉链表表示法(2)多重线性链表表示法：把每个结点的孩子组成一个线性链表.3孩子兄弟表示法：用二叉树的左指针指向该结点的第一个孩子,右指针指向该结点的下一个兄弟.123456先序:124536中序:425136后序:452631例如:哈夫曼树(最优二叉树)概念路径:从一结点到另一结点上的分支路径长度:路径上的分支数目树的路径长度:从根到所有结点的路径长度之和结点的带权路径长度:从该结点到树根之间的路径长度与结点上权值的乘积.树的带权路径长度:树中所有叶子结点的带权路径长度之和.定义:设有n个权值{w1,w2,......wn},任意构造有n个叶结点的二叉树,每个叶结点权值为wi。则其中带权路径长度最小的二叉树称为哈夫曼树(最优二叉树)。构造方法(1)根据给定的{w1,w2,......wn},生成n棵树的森林,F={T1,T2,.......Tm};根结点值为权值;(2)在F中选择两棵根结点值最小的树T