自考02142《数据结构导论》串讲笔记

本资料由广州自考网收集整理，更多自考资料请登录下载生活就像海洋，只有意志坚强的人才能达到生命的彼岸第一张概论1.1引言两项基本任务：数据表示，数据处理软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。机外表示------逻辑结构------存储结构处理要求-----基本运算和运算-------算法1.2数据，逻辑结构和运算数据：凡是能够被计算机存储，加工的对象通称为数据数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。1.2.2数据的逻辑结构逻辑关系：是指数据元素之间的关联方式，又称“邻接关系”逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。四种基本逻辑结构：1集合：任何两个结点间没有逻辑关系，组织形式松散2线性结构：结点按逻辑关系依次排列成一条“锁链”3树形结构：具有分支，层次特性，形态像自然界中的树4.图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。注意点:1.逻辑结构与数据元素本身的形式，内容无关。2.逻辑结构与数据元素的相对位置无关3.逻辑结构与所含结点个数无关。运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。引用：查找，读取加工：插入，删除，更新同一逻辑结构S上的两个运算A和B,A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。本资料由广州自考网收集整理，更多自考资料请登录下载生活就像海洋，只有意志坚强的人才能达到生命的彼岸1.3存储实现和运算实现由于逻辑结构是设计人员根据解题需要选定的数据组织形式，因此存储实现建立的机内表示应遵循选定的逻辑结构。另一方面，由于逻辑结构不包括结点内容即数据元素本身的表示，因此存储实现的另一主要内容是建立数据元素的机内表示。按上述思路建立的数据的机内表示称为数据的存储结构。存储结构包括三部分：1．存储结点，每个存储结点存放一个数据元素。2．数据元素之间关联方式的表示，也就是逻辑结构的机内表示。3．附加设施，如方便运算实现而设置的“哑结点”等。四种基本存储方式：1．顺序存储方式：每个存储结点只含一个数据元素。所有存储结点相继存放在一个连续的存储区里。用存储结点间的位置关系表述数据元素之间的逻辑关系。2．链式存储方式：每个存储结点不仅含有一个数据元素，还包含一组指针。每个指针指向一个与本结点有逻辑关系的结点，即用附加的指针表示逻辑关系。3．索引存储方式：每个存储结点只含一个数据元素，所有存储结点连续存放。此外增设一个索引表，索引指示各存储结点的存储位置或位置区间端点。4．散列存储方式：每个结点含一个数据元素，各个结点均匀分布在存储区里，用散列函数指示各结点的存储位置或位置区间端点。1.3.2运算实现运算只描述处理功能，不包括处理步骤和方法；运算实现的核心是处理步骤的规定，即算法设计。算法：算法规定了求解给定问题所需的所有处理步骤及其执行顺序，使得给定类型的任何问题能在有限时间内被机械的求解。算法分类：1：运行终止的程序可执行部分：又称为程序2:伪语言算法：不可以直接在计算机上运行，但容易编写和阅读。3：非形式算法：用自然语言，同时可能还使用了程序设计语言或伪语言描述的算法。1.4算法分析算法质量评价指标：1．正确性：能够正确实现处理要求2．易读性：易于阅读和理解，便于调试，修改和扩充3．健壮性：当环境发生变化，算法能够适当做出反应或处理，不会产生不需要的运行结果4．高效率：达到所需要的时空性能。如何确定一个算法的时空性能，称为算法分析一个算法的时空性能是指该算法的时间性能和空间性能，前者是算法包含的计算量，后者是算法需要的存储量。算法在给定输入下的计算量：1．根据该问题的特点选择一种或几种操作作为“标准操作”。2．确定每个算法在给定输入下共执行了多少次标准操作，并将此次数规定为该算法在给定输入下的计算本资料由广州自考网收集整理，更多自考资料请登录下载生活就像海洋，只有意志坚强的人才能达到生命的彼岸量。若无特殊说明，将默认以赋值语句作为标准操作。最坏情况时间复杂性：算法在所有输入下的计算量的最大值作为算法的计算量平均时间复杂性：算法在所有输入下的计算量的加权平均值作为算法的计算量。算法的输入规模（问题规模）是指作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数。常见时间复杂性量级：1．常数阶：O（1）即算法的时间复杂性与输入规模N无关或N恒为常数。2．对数阶：Olog2N3．线性阶：O(N)4．平方阶：O（N2）5．指数阶：O（2N次方）通常认为指数阶量级的算法实际是不可计算的，而量级低于平方阶的算法是高效率的第二章线性表2.1线性表的基本概念线性结构：线性结构是N（N大于等于0）个结点的有穷序列。AI称为Ai+1的直接前趋，Ai+1称为Ai的直接后继。为满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何结点的线性结构记为（）或线性结构的基本特征：若至少含有一个结点，则除起始节点没有直接前趋外，其他结点有且只有一个直接前趋，除终端结点没有直接后继外，其他结点有且只有一个直接后继。2.1.2线性表线性表的逻辑结构是线性结构。所含结点个数称为线性表的长度（表长）。表长为0的是空表。线性表的基本运算：1．初始化initiate（L）：加工型运算，其作用是建立一个空表L=。2．求表长length（L）：引用型运算，其结果是线性表L的长度。3．读表元get（L，i）：引用型运算。若1小于等于i小于等于length（L），其结果是L的第i个结点，否则为一特殊值。4．定位（按值查找）locate（L，X）：引用型运算。若L中存在一个或多个值与X相等，结果为这些结点的序号最小值，否则，运算结果为0。5．插入insert(L,X，i)：加工型运算。在L的第i个位置上增加一个值为X的新结点，参数i的合法取值范围是1---L+1。6．删除delete（L，i）：加工型运算。撤销L的第i个结点ai,i的合法取值范围是1---N。2.2线性表的顺序实现2.2.1顺序表顺序表是线性表的顺序存储结构，即按顺序存储方式构造的存储结构。顺序表基本思想：顺序表的一个存储结点存储线性表的一个结点的内容，即数据元素（不含其他信息），所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列。本资料由广州自考网收集整理，更多自考资料请登录下载生活就像海洋，只有意志坚强的人才能达到生命的彼岸顺序表的特点：逻辑结构中相邻的结点在存储结构中仍相邻。顺序表的类C语言描述：p17Constmaxsize=顺序表的容量Typedefstruct{datatypedate[maxsize]Intlast;}sqlist;SqlistL;L表示线性表的长度，last-1是终端结点在顺序表中的位置。常数maxsize为顺序表的容量。表长L.last,终端结点L.data[L.last-1]2.2.2基本运算在顺序表上的实现1．插入Voidinset_sqlist(sqlistL,datatypex,inti){if(L.last==maxsize)error(‘表满’);/*溢出*/If(((i1)!!(iL.last+1))error(‘非法位置’);For(j=L.last;j=I;j--)L.data[j]=L.data[j-1];/*依次后移*/L.data[i-1]=x;/*置入*/L.last=L.last+1/*修改表长*/}2.删除Voiddelete_sqlist(sqlistL,intI)/*删除顺序表L中第i个位置上的结点*/{If((i1)!!(IL.last))error(‘非法位置’);For(j=i+1;j=L.last;j++)L.data[j-2]=L.data[j-1];/*依次前移，注意第一个L.data[j-2]存放ai*/L.last=L.last-1/*修改表长*/3．定位Intlocate_sqlist(sqlistL,datatypeX)/*在顺序表中从前往后查找第一个值等于X的结点。若找到则回传该结点序号，否则回传0*/{I=1;While((i=L.last)&&(L.data[i-1]!=x))/*注意：ai在L.data[i-1]中*/i++;/*从前往后查找*/if(i=L.last)return(i)elsereturn(0)}2.2.3顺序实现的算法分析本资料由广州自考网收集整理，更多自考资料请登录下载生活就像海洋，只有意志坚强的人才能达到生命的彼岸插入:平均时间复杂性：=n/2平均时间复杂性量级为O（n）删除：平均时间复杂性：n-1/2平均时间复杂性量级：O（n）定位：平均时间复杂性量级：O（n）求表长，读表元：量级O（1）以上分析得知：顺序表的插入，删除算法的时间性能方面是不理想的。2.3线性表的链接实现顺序表的优缺点：优点：1。无需为表示结点间的逻辑关系而增加额外的存储空间。2．可以方便地随机存取表中的任一结点。缺点：1。插入，删除运算不方便，除表尾位置外，其他位置上进行插入和删除操作都必须移动大量结点，效率较低。2．由于顺序表要求占用连续的空间，存储分配职能预先进行（静态分配），因此当表长变化较大时，可能造成空间长期闲置或空间不够而溢出。链表：采用链接方式存储的线性表称为链表一种数据结构的链接实现是指按链式存储方式构建其存储结构，并在此链式存储结构上实现其基本运算。2.3.1单链表单链表表示法的基本思想：用指针表示结点间的逻辑关系。一个存储结点包含两部分：data部分:称为数据域，用于存储线性表的一个数据元素。Next部分：称为指针域或链域，用于存放一个指针，指向本结点所含数据元素的直接后继所在的结点终端结点的指针NULL称为空指针，不指向任何结点，只起标志作用。Head称为头指针变量，指向单链表的第一个结点的，称为头指针。头指针具有标识单链表的作用，故常用头指针变量来命名单链表。单链表的类C语言描述:Typedefstructnode*pointer;Structnode{datatypedata;Pointernext;};Typedefpointerlklist;2.3.2单链表的简单操作为了便于实现各种运算，通常在单链表第一个结点前增设一个类型相同的结点，称为头结点。其他结点称为表结点。表结点中第一个和最后一个称为首结点和尾结点。头结点的数据域可以不存储任何信息，也可以本资料由广州自考网收集整理，更多自考资料请登录下载生活就像海洋，只有意志坚强的人才能达到生命的彼岸存放一个特殊标志或表长。1初始化：Lklistinitiate_lklist()/*建立一个空表*/{t=malloc(size);t-next=NULL;return(t);}此算法说明的问题：1．语句t=malloc(size);有双重作用：1由malloc自动生成一个类型为node的新结点。2指针型变量t得到一个值即指针，该指针指向上述新结点。2．要生成新结点必须通过调用malloc才能实现。3．语句t-next=NULL的作用是将头结点*t的链域