《数据结构期末考点总结.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考点总结.pdf（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
17、(G,v,w) if (!visitedw)DFS(G,w); 广度优先遍历( bfs) 算法思想: 1) 访问给定结点 v; 2) 由近至远,依次访问和 v 有路径相连且长度为 1,2,3.的顶点.可以用一个 数组标识顶点是否被访问过.用一个队列存放刚访问过的结点. void BFStraverse(GraphG) for (v=0;vG.vexnum;+v) visitedv=FALSE; iniqueue(Q); for(v=0;vG.vexnum;+v)/保证非连通图的遍历 if (!visitedv) visit(v);visitedv=TRUE;Enqueue(Q,v); whil
18、e(!Queueempty(Q) Dequeue(Q,u); for (w= First_Adj(G,u);w;w=Next_Adj(G,u,w) if (!visitedw) visit(w);visitedw=TRUE;Enqueue(Q,w); 深度优先遍历:a b d h e c f g 广度优先遍历:a b c d e f g h 生成树：一个连通图的生成树是由 n-1 条边且包含 G 的所有顶点的树组成. 可按深度或广度优先遍历来创建生成树. 最小生成树：对具有 n 个结点的网,如何选择n-1 条边构成的生成树,其权值和最小.权值 和最小的生成树即为最小生成树. 最小生成树的性质(
19、MST): 假设 N=(V,E)是连通网,UV 若 是一条具有最小权值的边,uU,v 例如: b a f d h g e c V-U,则必然存在一棵包含边 的最小生成树. prim 算法: 1 设 U=u0,T=; 2重复执行如下操作: 在所有 uU,v V-U 的边 E 中找一条代价最小的边 , 并入 T 中,U=U+v，直到 U=V 或 T 中有 n-1 条边. kruscal 算法:（结果也如上图） 1设 G=(V,E);T=(v,); 2 从 E 中选一条最小权值的边,并从 E 中消除此边 3 若 属于 T 中不同的连通分量,则将加入到 T 中,重复 2 ,直到 T 中有 n-1 条边
20、. 最短路径：设 V0,V1,V2,.Vn -1 为 n 个顶点序列，求 V0 到各顶点的最短路径. Dijkstra算法: 令 disti 表示已经求出的 v0 到 vi 的最短路径,S 表示已求出最短路径的顶点. 1)令 distv0 =0; disti= | i v0 ；S=v0; 2)求下一条最短路径: distj=Mindisti+costi,k | viS,vk V-S 3)令 S=S+vj; 重复 2) 直到 S=V. Dijkstra算法的中心思想是采用路径长度递增产生最短路径. 第八章第八章 查找查找 重点：折半查找，了解顺序、索引查找， 二叉排序树的插入删除（算法思路） 哈
21、希表 元素类型定义： typedef struct keytypekey; 其它域定义 elemtype 顺序存储结构 typedef struct elemtype*elem; int length; b a d c ef 1 5 3 4 2 b a d c ef 6 5 1 5 5 3 6 4 2 6 SStable 顺序查找算法 int search(SStable ST,key) ST.elem0.key=key;/0 位置本身为空单元 for(i=ST.length;!EQ(ST.elemi.key,key);- -i); return i; /若存在返回在静态表中的位置 i ,否则
22、 i=0 折半查找 ( 1 ) 折半查找思想 ( 2 )折半查找算法 int search(SStable ST,key) low=1;high=ST.length; while (low 左子树任意结点的值小于根结点值; 2右子树任意结点的值大于根结点值; 3左右子树仍然为二叉排序树. 查找： StatusSearchBST(BTreeT,keytype key,BTree f,BTree return False; else ifEQ(key,T-data.key) p=T;return True; else if LT (key,T-data.key) return ( SearchBS
23、T(T-lchild,key,T,p); else return(SearchBST(T-rchild,key,T,p); 插入算法 StatusinsertBST(BTreeT,Elemtype e) if (!SearchBST(T,e.key,NUll,p) new(s); s-data=e; s-lchild=s-rchild=Null; 0513192137566475808892key=21 lowmidhigh if (!p) T=s;/ 原树为空 else if LT(e.key,p-data.key)p-lchild=s; else p-rchild=s; return Tr
24、ue; return False; 删除结点分三种情况: 删除： viod Delete (BTreep=p-lchild;free(q);/p 无右孩子 else if(!p-lchild) q=p;p=p-rchild;free(q);/p 无左孩子 else/p 左 右孩子都有 q=p;s=p-lchild;/寻找左子树中最大值的结点 S while (s-rchild) q=s;s=s-rchild ; p-data=s-data;/ S 的值复制到 P if (q!=p) q-rchild=s-lchild; elseq-lchild=s-lchild;free(s); 哈希表 定义
25、:给定 key ,及函数 f,令 addr=f(key),可根据该地址直接访问或存储具有 key 值的 记录. f 称为映射函数或哈希函数, addr 称映射地址.由这种方式组织的表称为哈希表.若 key1 key2,而 f(key1)= f(key2),则称 key1,key2 发生地址冲突. case2: p case1:p 只需将 p 连接到待 删节点的右子树,并释 放 p 所指向的结点 只需将 p 连接到待 删节点的左子树,并释 放 p 所指向的结点 case3:p s 寻找左子树中关键字最大的结点S ,将 S 结点的数据复制到 P,然后删除 S 结点. 构造方法（了解） 1直接定址法
26、 f(key)=(a*key+b) mod lengtha,b 为常量 2数字分析法 取 key 的某几位,或进行叠加. 3平方取中法 从 (key)2 中取某些位 4折叠法 把 key 分割,求叠加和. 5除留余数法 f(key)=keymodp,p 为小于等于 length 的质数. 6随机数法 f(key)=random(key) 处理冲突的方法：1开放地址法 2链地址法 3公共冲突区 第九章第九章 内部排序内部排序 重点：插入排序，快速排序，堆排序，归并排序 插入排序 基本思想：设 R=R1,R2.Rn, 为原始序列,R=初始为空，插入排序的基本 思想就是依次取出 R 中的元素 Ri，
27、然后将 Ri 有序地插入到 R中 冒泡排序（了解基本思想） 基本思想:a1a2a3.an-1an 首先在 n 个元素中,若 aiai+1 (i=1.n-1)则交换,这样得到一个最大元素放于 an. 其次在n-1个元素中,若 aiai+1 (i=1.n-2)则交换,这样得到一个次大元素放于an-1. 以此类推,直到选出 n-1 个元素.排序完成. 快速排序（实例 P275） 基本思想:：设序列为a1a2.an 首先把比 a1 小的记录放前,把比a1 大的记录放后，得到一次划分: as1as2. aska1at1at2.atj 然后分别对两序列再进行划分,直到划分后的序列剩一个元素为止。 任意子系
28、列 L.rlow.high的一趟划分算法: int partition(Sqlist / 把主记录 L.rlow放在 temp 中,使 L.rlow空闲 while (lowhigh)/用主记录进行一趟划分 while (low=temp.key) -high; L.rlow=L.rhigh;/在 high 端,寻找一个比 temp 小的记录放入 low,使 L.rhigh空闲 while (lowhigh L.rhigh=L.rlow;/在 low端,寻找一个比 temp 大的记录放入 high,使 L.rhigh空闲 L.rlow=temp;return low;/找到主记录的位置 low
29、 快速排序的递归算法实现 voidQuicksort(Sqlist 2 将 a1, an 交换; 3 将剩余a1a2. an-1调整为堆,当作新的序列,重复 1,直到序列剩一个元素. 建堆： (1)把给定序列看成是一棵完全二叉树: (2)从第 i =trunc(n/2) 结点开始,与子树结点比较,若直接子结点中较小者小于 i 结 点,则交换,直到叶结点或不再交换; (3)令 i=i-1,重复 (2) 直到 i=1. 归并排序的依据: 对任意两个有序序列,长度分别为 m,n ,可以设计一算法,在 O(m+n)时间内完成有序归并. 归并算法的基本思想: 对任意长度为 n 的序列,首先看成是 n 个长度为 1 的有序序列,然后两两归并为 n/2 个 有序表;再对 n/2 个有序表两两归并,直到得到一长度为 n 的有序表.