自考02331数据结构重点总结(最终修订).doc
《自考02331数据结构重点总结(最终修订).doc》由会员分享,可在线阅读,更多相关《自考02331数据结构重点总结(最终修订).doc(13页珍藏版)》请在咨信网上搜索。
1、自考02331数据结构重点总结(最终修订)第一章 概论1。瑞士计算机科学家沃思提出:算法+数据结构=程序。算法是对数据运算的描述,而数据结构包括逻辑结构和存储结构.由此可见,程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法,而好的算法在很大程度上取决于描述实际问题的数据结构。2.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成,数据项是具有独立含义的最小标识单位.数据对象是具有相同性质的数据元素的集合。3。数据结构指的是数据元素之间的相互关系,即数据的组织形式。数据结构一般包括以下三方面内容:数据的逻辑结构、数据的存储结构、数据的运算数据的逻辑结
2、构是从逻辑关系上描述数据,与数据元素的存储结构无关,是独立于计算机的。数据的逻辑结构分类: 线性结构和非线性结构.线性表是一个典型的线性结构。栈、队列、串等都是线性结构.数组、广义表、树和图等数据结构都是非线性结构。数据元素及其关系在计算机内的存储方式,称为数据的存储结构(物理结构).数据的存储结构是逻辑结构用计算机语言的实现,它依赖于计算机语言。数据的运算。最常用的检索、插入、删除、更新、排序等。4.数据的四种基本存储方法: 顺序存储、链接存储、索引存储、散列存储(1)顺序存储:通常借助程序设计语言的数组描述。(2)链接存储:通常借助于程序语言的指针来描述。(3)索引存储:索引表由若干索引项
3、组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。(4)散列存储:该方法的基本思想是:根据元素的关键字直接计算出该元素的存储地址。5。算法必须满足5个准则:输入,0个或多个数据作为输入;输出,产生一个或多个输出;有穷性,算法执行有限步后结束;确定性,每一条指令的含义都明确;可行性,算法是可行的。算法与程序的区别:程序必须依赖于计算机程序语言,而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类:类Pascal和类C。6。评价算法的优劣:算法的正确性”是首先要考虑的。此外,主要考虑如下三点: 执行算法所耗费的时间,即时间复杂性; 执行算法所
4、耗费的存储空间,主要是辅助空间,即空间复杂性; 算法应易于理解、易于编程,易于调试等,即可读性和可操作性.以上几点最主要的是时间复杂性,时间复杂度常用渐进时间复杂度表示.7.算法求解问题的输入量称为问题的规模,用一个正整数n表示。8。常见的时间复杂度按数量级递增排列依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)和阶乘阶0(n!)。9。一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间,它是问题规模n的函数,它包括存储算法本身所占的存储空间、算法的输入输出数据所占的存储空间
5、和算法在运行过程中临时占用的存储空间.第二章 线性表1。数据的运算是定义在逻辑结构上的,而运算的具体实现是在存储结构上进行的。2.只要确定了线性表存储的起始位置,线性表中任意一个元素都可随机存取,所以顺序表是一种随机存取结构.3.常见的线性表的基本运算:(1)置空表InitList(L) 构造一个空的线性表L。(2)求表长ListLength(L)求线性表L中的结点个数,即求表长。(3)GetNode(L,i) 取线性表L中的第i个元素。(4)LocateNode(L,x)在L中查找第一个值为x 的元素,并返回该元素在L中的位置。若L中没有元素的值为x ,则返回0值。(5)InsertList
6、(L,i,x)在线性表L的第i个元素之前插入一个值为x 的新元素,表L的长度加1。(6)DeleteList(L,i)删除线性表L的第i个元素,删除后表L的长度减1。4。顺序存储方法:把线性表的数据元素按逻辑次序依次存放在一组地址连续的存储单元里的方法。顺序表(Sequential List):用顺序存储方法存储的线性表称为顺序表。顺序表是一种随机存取结构,顺序表的特点是逻辑上相邻的结点其物理位置亦相邻.顺序表中结点ai 的存储地址: LOC(ai)= LOC(a1)+(i-1)c 1in,5.顺序表上实现的基本运算:(1)插入:该算法的平均时间复杂度是O(n),即在顺序表上进行插入运算,平均
7、要移动一半结点(n/2).在第i个位置插入一个结点的移动次数为n-i+1(2)删除:顺序表上做删除运算,平均要移动表中约一半的结点(n-1)/2,平均时间复杂度也是O(n)。删除第i个结点移动次数为ni6。采用链式存储结构可以避免频繁移动大量元素。一个单链表可由头指针唯一确定,因此单链表可以用头指针的名字来命名.生成结点变量的标准函数 p=( ListNode )malloc(sizeof(ListNode)); /函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中释放结点变量空间的标准函数 free(p);/释放p所指的结点变量空间 结点分量的访问
8、方法二:p-data和p-next指针变量p和结点变量*p的关系: 指针变量p的值-结点地址, 结点变量p的值结点内容7。建立单链表: (1) 头插法建表:算法: p=(ListNode *)malloc(sizeof(ListNode));/生成新结点p-data=ch; /将读入的数据放入新结点的数据域中p-next=head; head=p;(2) 尾插法建表:算法: p=(ListNode *)malloc(sizeof(ListNode)); /生成新结点p-data=ch; /将读入的数据放入新结点的数据域中if (head=NULL) head=p;/新结点插入空表else re
9、ar-next=p;/将新结点插到*r之后rear=p;/尾指针指向新表尾(3) 尾插法建带头结点的单链表:头结点及作用:头结点是在链表的开始结点之前附加一个结点。它具有两个优点: 由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理; 无论链表是否为空,其头指针都是指向头结点的非空指针(空表中头结点的指针域空),因此空表和非空表的处理也就统一了。头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。具体算法:r=head;/尾指针初值也指向头结点while(ch=getchar())!=n) s=(L
10、istNode )malloc(sizeof(ListNode));/生成新结点 sdata=ch; /将读入的数据放入新结点的数据域中 r-next=s; r=s;rnext=NULL;/终端结点的指针域置空,或空表的头结点指针域置空以上三个算法的时间复杂度均为O(n)。8.单链表上的查找:(带头结点)(1)按结点序号查找:序号为0的是头结点。算法:p=head;j=0;/从头结点开始扫描 while(pnext&jnext为NULL或i=j为止 p=pnext; j+; if(i=j) return p;/找到了第i个结点 else return NULL;/当i0或i0时,找不到第i个结
11、点时间复杂度:在等概率假设下,平均时间复杂度为:为n/2=O(n)(2)按结点值查找:具体算法:ListNode *p=head-next;/从开始结点比较.表非空,p初始值指向开始结点 while(p&pdata!=key)/直到p为NULL或pdata为key为止 p=p-next;/扫描下一结点 return p;/若p=NULL,则查找失败,否则p指向值为key的结点时间复杂度为:O(n)9。插入运算:插入运算是将值为x的新结点插入到表的第i个结点的位置上,即插入到ai-1与ai之间。s=(ListNode *)malloc(sizeof(ListNode); sdata=x; s-n
12、ext=pnext; pnext=s;算法的时间主要耗费在查找结点上,故时间复杂度亦为O(n).10.删除运算r=p-next;/使r指向被删除的结点ai p-next=r-next;/将ai从链上摘下free(r);/释放结点ai的空间给存储池算法的时间复杂度也是O(n)。p指向被删除的前一个结点。链表上实现的插入和删除运算,无须移动结点,仅需修改指针。11。单循环链表在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点即可。判断空链表的条件是head=headnext;12。仅设尾指针的单循环链表: 用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1
13、)。而表的操作常常是在表的首尾位置上进行,因此,实用中多采用尾指针表示单循环链表。判断空链表的条件为rear=rear-next;13。循环链表:循环链表的特点是无须增加存储量,仅对表的链接方式稍作改变,即可使得表处理更加方便灵活.若在尾指针表示的单循环链表上实现,则只需修改指针,无须遍历,其执行时间是O(1)。具体算法:LinkList Connect(LinkList A,LinkList B) /假设A,B为非空循环链表的尾指针LinkList p=A-next;/保存A表的头结点位置 Anext=Bnextnext;/B表的开始结点链接到A表尾 free(Bnext);/释放B表的头结
14、点 B-next=p;/ return B;/返回新循环链表的尾指针循环链表中没有NULL指针.涉及遍历操作时,其终止条件就不再是像非循环链表那样判别p或pnext是否为空,而是判别它们是否等于某一指定指针,如头指针或尾指针等。在单链表中,从一已知结点出发,只能访问到该结点及其后续结点,无法找到该结点之前的其它结点。而在单循环链表中,从任一结点出发都可访问到表中所有结点,这一优点使某些运算在单循环链表上易于实现。14.双向链表: 双(向)链表中有两条方向不同的链,即每个结点中除next域存放后继结点地址外,还增加一个指向其直接前趋的指针域prior。双链表由头指针head惟一确定的.带头结点的
15、双链表的某些运算变得方便.将头结点和尾结点链接起来,为双(向)循环链表。15。双向链表的前插和删除本结点操作双链表的前插操作void DInsertBefore(DListNode *p,DataType x)/在带头结点的双链表中,将值为x的新结点插入p之前,设pNULL DListNode s=malloc(sizeof(DListNode));/ s-data=x;/ s-prior=pprior;/ snext=p;/ pprior-next=s;/ p-prior=s;/双链表上删除结点p自身的操作void DDeleteNode(DListNode p) /在带头结点的双链表中,删
16、除结点*p,设p为非终端结点 pprior-next=p-next;/ pnextprior=p-prior;/ free(p); /与单链表上的插入和删除操作不同的是,在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。16. 顺序表和链表比较时间性能:a、线性表:经常性的查找; b、链式存储结构:经常插入删除操作;空间性能:a、对数据量大小事先能够知道的用线性表; b、数据量变化较大的用链式存储结构。存储密度越大,存储空间的利用率越高。显然,顺序表的存储密度是1,链表的存储密度肯定小于1。第三章 栈和队列1.栈称为后进先出(Last In First O
17、ut)的线性表,简称为LIFO表. 栈是运算受限的线性表,顺序栈也是用数组表示的。 进栈操作:进栈时,需要将Stop加1, Stop=StackSize-1表示栈满”上溢现象-当栈满时,再做进栈运算产生空间溢出的现象.退栈操作:退栈时,需将S-top减1, S-top0表示空栈”下溢”现象-当栈空时,做退栈运算产生的溢出现象。 下溢是正常现象,常用作程序控制转移的条件。空栈时栈顶指针不能是0,只能是1。两个栈共享同一存储空间: 当程序中同时使用两个栈时,可以将两个栈的栈底分别设在顺序存储空间的两端,让两个栈顶各自向中间延伸。当一个栈中的元素较多而栈使用的空间超过共享空间的一半时,只要另一个栈的
18、元素不多,那么前者就可以占用后者的部分存储空间。当Top1=Top2-1时,栈满2。为了克服顺序存储分配固定空间所产生的溢出和空间浪费问题.可采用链式存储结构来存储栈。链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。链栈中的结点是动态分配的,所以可以不考虑上溢,无须定义StackFull运算栈的一个重要应用是实现递归,直接调用自己或间接调用自己的函数.3。 队列(Queue)是只允许在一端进行插入,而在另一端进行删除的运算受限的线性表。允许删除的一端称为队头(Front),允许插入的一端称为队尾(Rear),当队列中没有元素时称为空队列,队列亦称作先进先出(First In
19、First Out)的线性表,简称为FIFO表. 队列的顺序存储结构称为顺序队列,顺序队列实际上是一个受限的线性表。顺序队列的基本操作入队时:将新元素插入rear所指的位置,然后将rear加1。出队时:删去front所指的元素,然后将front加1并返回被删元素。当头尾指针相等时,队列为空。在非空队列里,头指针始终指向队头元素,而队尾指针始终指向队尾元素的下一位置。而栈顶指针指向栈顶元素.4. 循环队列:为充分利用数组空间,克服上溢,可将数组空间想象为一个环状空间,并称这种环状数组表示的队列为循环队列。循环队列中进行出队、入队操作时,头尾指针仍要加1,朝前移动.只不过当头尾指针指向向量上界(Q
20、ueueSize1)时,其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为: 方法一: if(i+1=QueueSize) i=0;/i表示front或rear else i+; 方法二-利用”模运算” i=(i+1)%QueueSize;循环队列中,由于入队时尾指针向前追赶头指针;出队时头指针向前追赶尾指针,造成队空和队满时头尾指针均相等。因此,无法通过条件Q.front=Q.rear来判别队列是空”还是”满.解决这个问题的方法至少有三种: 另设一个标志位以区别队列是空还是满; 设置一个计数器记录队列中元素的总数(即队列长度). 少用一个元素的空间。约定入队前,测试尾指针
21、在循环意义下加1后是否等于头指针,若相等则认为队列满即尾指针Q。rear所指的单元始终为空。5.循环队列的基本运算: 置队空: Qfront=Qrear=0; 判队空: return Q-rear=Q-front; 判队满: return (Qrear+1)QueueSize=Q-front; 入队 Q-dataQ-rear=x; /新元素插入队尾 Q-rear=(Qrear+1)QueueSize; 出队 temp=QdataQfront; Q-front=(Q-front+1)QueueSize; /循环意义下的头指针加1 return temp;取队头元素 return QdataQfr
22、ont;6. 队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。 为了简化处理,在队头结点之前附加一个头结点,并设队头指针指向此结点。链队列的基本运算:(带头结点)(1) 构造空队:Qrear=Qfront;Q-rear-next=NULL;(2) 判队空:return Qrear=Q-front;(3) 入队:QueueNode p=(QueueNode )malloc(sizeof(QueueNode);/申请新结点 pdata=x; p-next=NULL; Q-rear-next=p; /p链到原队尾结点后Qrear=p; /队尾指针指向新的尾(4) 出队:当队列
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 自考 02331 数据结构 重点 总结 最终 修订
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【快乐****生活】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【快乐****生活】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。