《数据结构期末考点总结-修订编选》由会员分享，可在线阅读，更多相关《数据结构期末考点总结-修订编选（17页珍藏版）》请在金锄头文库上搜索。
1、第一章第一章 绪论绪论 数据所有输入计算机中并被计算机处理的符号。 数据元素数据的基本单位，通常作为一个整体。 数据对象性质相同的数据元素的集合。 数据结构数据元素以及之间存在的关系。 1 、线性结构；2、集合结构 3、树形结构； 4、图结构 数据结构的形式定义：Data-Structure=(D,S)D数据元素集合S关系集合 数据的逻辑结构用形式化方式描述数据元素间的关系。 数据的物理结构数据在计算机中的具体表示。 数据类型一种数据结构和定义在其上的一组操作。可以形式化定义为： Data-Type=(D,S,P) 算法的定义是对特定问题求解步骤的一种描述， 是指令的有限序列。 算法的特性 有
2、穷性算法必须在执行有穷步之后结束，而且每一步都可在有穷时间内完成。 确定性每条指令无二义性。 可行性算法中描述的每一操作，都可以通过已经实现的基本运算来实现。 输入算法有零至多个输入。 输出算法有一个至多个输出。 时间复杂度的等级 O（1） O（log n） O（n） O（nlog n) O (n2) O (nK） O（Xn ） 第二章第二章 线性表线性表 重点： 1、链式和线性表两种方式的插入与删除 2、单双链表的定义 线性表的定义 #defineList-Init-Size100 #defineListincrement10 typedefstruct Elemtype*elem； int
3、length； intlistsize； Sqlist； 线性表定位插入 Status Listinsert_Sq(Sqlist if (L.length=L.listsize) newbase=追加分配新空间 L.elem=newbase; L.listsize+=Listincrement; for (j=L.length-1;j=i-1;-j) L.elemj+1=L.elemj); L.elemi-1=e; +L.length; return OK; 线性表定位删除 Status Listdelete_Sq(Sqlist e= L.elemi-1); for (j=i;jL.lengt
4、h;+j) L.elemj-1=L.elemj); -L.length; return OK; 单链表定义： typedef structLnode Elemtypedata； structLnode*next； Lnode， *Linklist； 链式定位插入 Status Listinsert_L(Linklist j=0; while (p+j if ( !p ji-1) return ERROR; new(s); s-data=e; s-next=p-next; p-next=s; return OK; 链式定位删除 Status Listdelete_L(Linklist j=0;
5、while (p-next+j if ( !(p-next) ji-1)return ERROR; q= p-next ; p-next=q -next; e=q -data; free(q); return OK; 双向链表结点的存储结构定义 typedef structDublnode Elemtypedata; structDublnode*prior ； structDublnode*next ； Dublnode,*Dublinklist ； 了解：有序表的合并 void Mergelist_L(Linklist pb=Lb-next; Lc=pc=La; while (papc=p
6、a;pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; pc-next =pa?pa:pb; free(Lb); 第三章第三章、栈与队列、栈与队列 重点：1、栈的插入，删除，和取栈顶 2、队列的取对头，插入，删除（循环队列） 栈的存储结构定义: #define Stack_init_size100; #define Stackincrement10; typedefstruct Selemtype*base;指向第一个元素（有数） Selemtype*top;指向最后一个元素的下一位（为空） intstacksize; Sqstack; 栈的取栈顶 St
7、atus Gettop(Sqstack s,Selemtype e=*(s.top-1); return Ok 栈的插入 Status Push(Sqstack s.stacksize+=Stackincrement; *s.top+=e; return Ok 栈的删除栈顶 Status Pop(Sqstack e=*-s.top return Ok 队列的顺序存储表示与实现 typedef struct Qelemtype*base; intfront;指向第一个元素（有数） intrear;指向最后一个元素的下一位（为空） Sqqueue; 队空条件:Q.front = Q.rear 队满
8、条件:(Q.rear+1) % Maxsize= Q.front 队列长度：(Q.rear-Q.front+Maxsise)%Maxsize 队的插入： Status Enqueue(sqqueue Q.baseQ.rear=e; Q.rear=(Q.rear+1)%Maxsize; return OK; 队的删除 Status Dequeue(sqqueue e=Q.baseQ.front; Q.front=(Q.front+1)%Maxsize; return OK; 取对头 Status GetHead(sqqueue return Q.baseQ.front; 第四章第四章串串 重点：
9、串的比较、连接，了解串的插入，删除 定义 typedef struct char*ch; intlength; Hstring ; 比较 status strcompare(S,T) for (i=0;iS.length 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-rch
10、ild); visit(bt-data); 树的存储结构（书上 P135） 1双亲表示法： 用一组连续的空间存放结点,每个结点用一个域表示该结点的双亲. 2孩子表示法：(1)多叉链表表示法 (2)多重线性链表表示法：把每个结点的孩子组成一个线性链表. 3孩子兄弟表示法：用二叉树的左指针指向该结点的第一个孩子,右指针指向该结点的 下一个兄弟. 1 23 45 6 先序:124536 中序:425136 后序:452631 例如: 哈夫曼树(最优二叉树) 概念 路径:从一结点到另一结点上的分支 路径长度:路径上的分支数目 树的路径长度:从根到所有结点的路径长度之和 结点的带权路径长度:从该结点到树
11、根之间的路径长度与结点上权值的乘积. 树的带权路径长度:树中所有叶子结点的带权路径长度之和. 定义:设有n 个权值 w1,w2,.wn,任意构造有 n 个叶结点的二叉树,每个叶结点权值为 wi 。则其中带权路径长度最小的二叉树称为哈夫曼树(最优二叉树)。 构造方法 (1) 根据给定的 w1,w2,.wn, 生成n 棵树的森林, F= T1,T2,.Tm;根结点值为权值; (2) 在 F 中选择两棵根结点值最小的树 Ti ,Tj 作为左右子树,构成一棵新二叉树 Tk , Tk 根结点值为 Ti ,Tj 根结点权值之和; (3) 在 F 中删除 Ti ,Tj ,并把 Tk加到 F 中; (4) 重
12、复 (2) (3),直到 F 中只含一棵树。 树的遍历 1先根访问 先访问根,然后依次访问子树. 2后根访问 先依次访问子树,然后访问根. A B CD EF GIJH tree 例如: 先根访问:ABEFCGDHIJ 后根访问: EFBGCHIJDA 第七章第七章 图图 重点：图的定义，数组表示法，邻接表表示法 深度优先遍历，广度优先遍历，生成树 图的定义： Graph=(V,E)， V 为顶点集;E 为边集。 若 E 为有向边，称为有向图； 若 E 为无向边，称为无向图。 边一般由顶点对表示：; 若 为有向边,则称 vi 为尾, vj 为头. 有向边也可以表示为:vivj 无向完全图: 如
13、果在无向图 G 中,任何两顶点都有一条边相连,边的数目为:n(n-1)/2 有向完全图:如果在有向图G中,任何两顶点都有两条方向相反的边相连,边的数目为:n(n-1) 连通图:无向图中,任意两点 Vi,Vj 都有路径相连,称该无向图为连通图. 连通分量: 无向图中极大连通子图. 数组（矩阵）表示法： 设 G=(V,E)V= V1,V2,.Vn Ai,j=1若E, ij 0否则 A 为一 nn 矩阵,称为 G 的邻接矩阵 若G=(V,E) 为网,则邻接矩阵可以表示为: 数组表示法定义： 示例:W= 1,2,3,4,5 15 6 3 21345 9 w1w2w3w4w5 1F= 1,2,3,4,5
14、 2F= 3,3,4,5 3F= 6,4,5 4F= 6,9 5F= 15 Ai,j= Wij若E, ij 0否则 #defineMax_V_num20/最大顶点数 typedefenum DG,DN,UDG,UDN Graphkind;/有向无向图网 typedefstruct/ 图结构 VextypevexsMax_V_num;/ 顶点数组 ArctypearcsMax_V_num Max_V_num;/边矩阵/0,1 或权值 wij intvexnum,arcnum;/顶点数,边数 Graphkindkind;/图种类 graph 邻接表表示法: 每个顶点用一个链表表示(P164) #d
15、efineMax_V_num20/最大顶点数 typedefstructArcnode/边结点类型 intvjpos;/vj 的位置 structArcnode*nextarc; Arcnode; typedefstructVnode/顶点结点类型 vextypedata; Arcnode*firsttarc; Vnode,AdjlistMax_V_num ; typedefstruct Adjlistvexs; int vexnum,arcnum; Graphkindkind; graph 十字链表:用来表示有向图. 有向图中,每一条边用一个结点表示,每个顶点也用一个结点表 示.(了解) 深
16、度优先遍历( dfs) 算法思想: 1) 访问给定结点; 2) 重复对第一个未被访问的邻接点进行深度优先遍历,直到不存在未被访问的邻接 点结束.可以用一个数组标识顶点是否被访问过. void DFStraverse(GraphG) for (v=0;vG.vexnum;+v) visitedv=FALSE; for(v=0;vG.vexnum;+v)/保证非连通图的遍历 if (!visitedv)DFS(G,v); void DFS(GraphG,int v)/连通图的遍历 visit(v);visitedv=TRUE; for (w= First_Adj(G,V);w;w=Next_Adj(G,v,w) if (!visitedw)DFS(G,w); 广度优先遍历( bfs) 算法思想: 1) 访问给定结点 v; 2) 由近至远,依次访问和 v 有路径相连且长度为 1,2,3.
