数据结构期末考点总结.pdf
- 文档编号:14652357
- 上传时间:2023-06-25
- 格式:PDF
- 页数:17
- 大小:475.91KB
数据结构期末考点总结.pdf
《数据结构期末考点总结.pdf》由会员分享,可在线阅读,更多相关《数据结构期末考点总结.pdf(17页珍藏版)》请在冰点文库上搜索。
第一章第一章绪论绪论数据所有输入计算机中并被计算机处理的符号。
数据元素数据的基本单位,通常作为一个整体。
数据对象性质相同的数据元素的集合。
数据结构数据元素以及之间存在的关系。
1、线性结构;2、集合结构3、树形结构;4、图结构数据结构的形式定义:
Data-Structure=(D,S)D数据元素集合S关系集合数据的逻辑结构用形式化方式描述数据元素间的关系。
数据的物理结构数据在计算机中的具体表示。
数据类型一种数据结构和定义在其上的一组操作。
可以形式化定义为:
Data-Type=(D,S,P)算法的定义是对特定问题求解步骤的一种描述,是指令的有限序列。
算法的特性有穷性算法必须在执行有穷步之后结束,而且每一步都可在有穷时间内完成。
确定性每条指令无二义性。
可行性算法中描述的每一操作,都可以通过已经实现的基本运算来实现。
输入算法有零至多个输入。
输出算法有一个至多个输出。
时间复杂度的等级O
(1)O(logn)O(n)O(nlogn)O(n2)O(nK)O(Xn)第二章第二章线性表线性表重点:
1、链式和线性表两种方式的插入与删除2、单双链表的定义线性表的定义#defineList-Init-Size100#defineListincrement10typedefstructElemtype*elem;intlength;intlistsize;Sqlist;线性表定位插入StatusListinsert_Sq(Sqlist&L,inti,Elemtypee)if(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.elemj+1=L.elemj);L.elemi-1=e;+L.length;returnOK;线性表定位删除StatusListdelete_Sq(Sqlist&L,inti,Elemtype&e)if(iL.length)returnERROR;e=L.elemi-1);for(j=i;jL.length;+j)L.elemj-1=L.elemj);-L.length;returnOK;单链表定义:
typedefstructLnodeElemtypedata;structLnode*next;Lnode,*Linklist;链式定位插入StatusListinsert_L(Linklist&L,inti,Elemtypee)p=L;j=0;while(p&jnext;+jif(!
pji-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&jnext;+jif(!
(p-next)ji-1)returnERROR;q=p-next;p-next=q-next;e=q-data;free(q);returnOK;双向链表结点的存储结构定义typedefstructDublnodeElemtypedata;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-datadata)pc-next=pa;pc=pa;pa=pa-next;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?
pa:
pb;free(Lb);第三章第三章、栈与队列、栈与队列重点:
1、栈的插入,删除,和取栈顶2、队列的取对头,插入,删除(循环队列)栈的存储结构定义:
#defineStack_init_size100;#defineStackincrement10;typedefstructSelemtype*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队列的顺序存储表示与实现typedefstructQelemtype*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.baseQ.rear=e;Q.rear=(Q.rear+1)%Maxsize;returnOK;队的删除StatusDequeue(sqqueue&Q,Qelemtype&e)if(Q.front=Q.rear)returnERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%Maxsize;returnOK;取对头StatusGetHead(sqqueue&Q,Qelemtype&e)if(Q.front=Q.rear)returnERROR;returnQ.baseQ.front;第四章第四章串串重点:
串的比较、连接,了解串的插入,删除定义typedefstructchar*ch;intlength;Hstring;比较statusstrcompare(S,T)for(i=0;iS.length&i=j)或k=j(j+1)/2+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中选择两棵根结点值最小的树Ti,Tj作为左右子树,构成一棵新二叉树Tk,Tk根结点值为Ti,Tj根结点权值之和;(3)在F中删除Ti,Tj,并把Tk加到F中;(4)重复
(2)(3),直到F中只含一棵树。
树的遍历1先根访问先访问根,然后依次访问子树.2后根访问先依次访问子树,然后访问根.ABCDEFGIJHtree例如:
先根访问:
ABEFCGDHIJ后根访问:
EFBGCHIJDA第七章第七章图图重点:
图的定义,数组表示法,邻接表表示法深度优先遍历,广度优先遍历,生成树图的定义:
Graph=(V,E),V为顶点集;E为边集。
若E为有向边,称为有向图;若E为无向边,称为无向图。
边一般由顶点对表示:
;若为有向边,则称vi为尾,vj为头.有向边也可以表示为:
vivj无向完全图:
如果在无向图G中,任何两顶点都有一条边相连,边的数目为:
n(n-1)/2有向完全图:
如果在有向图G中,任何两顶点都有两条方向相反的边相连,边的数目为:
n(n-1)连通图:
无向图中,任意两点Vi,Vj都有路径相连,称该无向图为连通图.连通分量:
无向图中极大连通子图.数组(矩阵)表示法:
设G=(V,E)V=V1,V2,.VnAi,j=1若E,ij0否则A为一nn矩阵,称为G的邻接矩阵若G=(V,E)为网,则邻接矩阵可以表示为:
数组表示法定义:
示例:
W=1,2,3,4,51563213459w1w2w3w4w51F=1,2,3,4,52F=3,3,4,53F=6,4,54F=6,95F=15Ai,j=Wij若E,ij0否则#defineMax_V_num20/最大顶点数typedefenumDG,DN,UDG,UDNGraphkind;/有向无向图网typedefstruct/图结构VextypevexsMax_V_num;/顶点数组ArctypearcsMax_V_numMax_V_num;/边矩阵/0,1或权值wijintvexnum,arcnum;/顶点数,边数Graphkindkind;/图种类graph邻接表表示法:
每个顶点用一个链表表示(P164)#defineMax_V_num20/最大顶点数typedefstructArcnode/边结点类型intvjpos;/vj的位置structArcnode*nextarc;Arcnode;typedefstructVnode/顶点结点类型vextypedata;Arcnode*firsttarc;Vnode,AdjlistMax_V_num;typedefstructAdjlistvexs;intvexnum,arcnum;Graphkindkind;graph十字链表:
用来表示有向图.有向图中,每一条边用一个结点表示,每个顶点也用一个结点表示.(了解)深度优先遍历(dfs)算法思想:
1)访问给定结点;2)重复对第一个未被访问的邻接点进行深度优先遍历,直到不存在未被访问的邻接点结束.可以用一个数组标识顶点是否被访问过.voidDFStraverse(GraphG)for(v=0;vG.vexnum;+v)visitedv=FALSE;for(v=0;vG.vexnum;+v)/保证非连通图的遍历if(!
visitedv)DFS(G,v);voidDFS(GraphG,intv)/连通图的遍历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.的顶点.可以用一个数组标识顶点是否被访问过.用一个队列存放刚访问过的结点.voidBFStraverse(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);while(!
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);深度优先遍历:
abdhecfg广度优先遍历:
abcdefgh生成树:
一个连通图的生成树是由n-1条边且包含G的所有顶点的树组成.可按深度或广度优先遍历来创建生成树.最小生成树:
对具有n个结点的网,如何选择n-1条边构成的生成树,其权值和最小.权值和最小的生成树即为最小生成树.最小生成树的性质(MST):
假设N=(V,E)是连通网,UV若是一条具有最小权值的边,uU,v例如:
bafdhgecV-U,则必然存在一棵包含边的最小生成树.prim算法:
1设U=u0,T=;2重复执行如下操作:
在所有uU,vV-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条边.最短路径:
设V0,V1,V2,.Vn-1为n个顶点序列,求V0到各顶点的最短路径.Dijkstra算法:
令disti表示已经求出的v0到vi的最短路径,S表示已求出最短路径的顶点.1)令distv0=0;disti=|iv0;S=v0;2)求下一条最短路径:
distj=Mindisti+costi,k|viS,vkV-S3)令S=S+vj;重复2)直到S=V.Dijkstra算法的中心思想是采用路径长度递增产生最短路径.第八章第八章查找查找重点:
折半查找,了解顺序、索引查找,二叉排序树的插入删除(算法思路)哈希表元素类型定义:
typedefstructkeytypekey;其它域定义elemtype顺序存储结构typedefstructelemtype*elem;intlength;badcef15342badcef6515536426SStable顺序查找算法intsearch(SStableST,key)ST.elem0.key=key;/0位置本身为空单元for(i=ST.length;!
EQ(ST.elemi.key,key);-i);returni;/若存在返回在静态表中的位置i,否则i=0折半查找
(1)折半查找思想
(2)折半查找算法intsearch(SStableST,key)low=1;high=ST.length;while(low左子树任意结点的值小于根结点值;2右子树任意结点的值大于根结点值;3左右子树仍然为二叉排序树.查找:
StatusSearchBST(BTreeT,keytypekey,BTreef,BTree&p)/f为T的父结点,/p返回查找到的结点或/未查找到的叶结点(待插入的位置)if(!
T)p=f;returnFalse;elseifEQ(key,T-data.key)p=T;returnTrue;elseifLT(key,T-data.key)return(SearchBST(T-lchild,key,T,p);elsereturn(SearchBST(T-rchild,key,T,p);插入算法StatusinsertBST(BTreeT,Elemtypee)if(!
SearchBST(T,e.key,NUll,p)new(s);s-data=e;s-lchild=s-rchild=Null;0513192137566475808892key=21lowmidhighif(!
p)T=s;/原树为空elseifLT(e.key,p-data.key)p-lchild=s;elsep-rchild=s;returnTrue;returnFalse;删除结点分三种情况:
删除:
viodDelete(BTree&p)if(!
p-rchild)q=p;p=p-lchild;free(q);/p无右孩子elseif(!
p-lchild)q=p;p=p-rchild;free(q);/p无左孩子else/p左右孩子都有q=p;s=p-lchild;/寻找左子树中最大值的结点Swhile(s-rchild)q=s;s=s-rchild;p-data=s-data;/S的值复制到Pif(q!
=p)q-rchild=s-lchild;elseq-lchild=s-lchild;free(s);哈希表定义:
给定key,及函数f,令addr=f(key),可根据该地址直接访问或存储具有key值的记录.f称为映射函数或哈希函数,addr称映射地址.由这种方式组织的表称为哈希表.若key1key2,而f(key1)=f(key2),则称key1,key2发生地址冲突.case2:
pcase1:
p只需将p连接到待删节点的右子树,并释放p所指向的结点只需将p连接到待删节点的左子树,并释放p所指向的结点case3:
ps寻找左子树中关键字最大的结点S,将S结点的数据复制到P,然后删除S结点.构造方法(了解)1直接定址法f(key)=(a*key+b)modlengtha,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,然后将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然后分别对两序列再进行划分,直到划分后的序列剩一个元素为止。
任意子系列L.rlow.high的一趟划分算法:
intpartition(Sqlist&L,intlow,inthigh)/以L.rlow为主记录,对子系列L.rlow.high的一趟划分temp=L.rlow;/把主记录L.rlow放在temp中,使L.rlow空闲while(lowhigh)/用主记录进行一趟划分while(low=temp.key)-high;L.rlow=L.rhigh;/在high端,寻找一个比temp小的记录放入low,使L.rhigh空闲while(lowhigh&L.rlow.key=temp.key)+low;L.rhigh=L.rlow;/在low端,寻找一个比temp大的记录放入high,使L.rhigh空闲L.rlow=temp;returnlow;/找到主记录的位置low快速排序的递归算法实现voidQuicksort(Sqlist&L,intlow,inthigh)if(low若a1a2.an为堆,则a1最小;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的有序表.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 期末 考点 总结
![提示](https://static.bingdoc.com/images/bang_tan.gif)