C语言软件基本部分知识点点.docVIP

数据结构的基础知识内容 1.数据结构的基本概念 数据结构是讨论计算机系统中数据的组织形式及其相互关系的学科.研究数据结构就是要研究以下三方面的内容: 1).数据元素之间的逻辑关系是什么? 2).适宜选用什么样的存储结构? 3).采用什么样的操作实现算法效率更高? 2.反映数据元素之间关系的数据逻辑结构可分为两大类. 1)线性结构:线性结构的逻辑特征是:有且仅有一个开始数据元素和一个终点数据元素并且所有数据元素都最多只有一个直接前趋和一个直接后继.线性表就是一个典型的线性结构. 2)非线性结构:非线性结构的逻辑特征是：该结构中一个数据元素可能有多个直接前趋和直接后继.非线性结构中取一般结构是图结构,在图结构中,任何数据元素的直接前趋和直接后继的人数都不作限制,在非线性结构中有一类较特殊的结构,我们称为树结构,它的逻辑特征是:所有数据元素(除根元素)都存在一条从根元素到该元素的路径. 3.反映数据元素在计算机中的存储方法就是数据的存储结构,数据的存储结构图:有时它称为数据的物理结构,它是数据的逻辑结构在存储器里的实现.数据的存储方法可分为如下四类: 1).顺序存储方法:该方法是把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里,元素间的逻辑关系由存储单元的邻接关系体现.由此得到的存储表称为顺序存储结构.顺序存储方法主要应用于线性的数据结构,如线性表,数组等.非线性的数据结构也可以通过某种线性化的方法来实现顺序存储. 2).链接存储方法:该方法不要求逻辑上相邻的元素其物理位置上亦相邻,元素间的逻辑关系是由附加的指针字段表示的,由此得到的存储表称为链式存储结构，链式存储结构要借助于程序结构的指针类型来描述元素的存储地址,即在此存储方法中,每个数据元素所占存储单元分成两部分:一部分为元素本身数据项; 而另一部分为指针项,指出其后继前趋元素的存储地址,从而形成一个链. 3).索引存储方法:该方法通常是在存储元素信息的同时,还建立附加的索引表,索引表中的每一项称为索引项,索引项的一般形式是:关键字,地址。关键字是能唯一标识一个元素的数据项.若每个元素在索引表中都有一个索引项,则该索引位置称为稠密索引(DENSE.INDEX)；若一级元素在索引表中只对应一个索引项,则该索引位置称稀疏索引(SDARSE.INDEX),稠密索引中索引项的地址指示元素所在存储位置,而稀疏索引中索引项的地址则指示一级元素的起始存储位置. 4).散列存储方法:该方法的基本思想是根据元素的关键字直接计算出该元素的存储地址.即在数据元素的字段中有一个或几个字段的值,通过某一散列函数唯一地确定该元素的存储地址.有时又称散列存储方法为关键字-----地址转移法. 4.把数据以一定的有效逻辑结构组织起来,并以适当的方法存储在计算机系统的存储器里,其最终目的是有效处理数据,提高数据处理的运算速度. 在数据结构中,要讨论的常用数据处理与运算有下列几种: 1).遍历:在数据结构的各个元素移动,或查看所有数据元素. 2).插入:往数据结构中加新的元素. 3).更新:修改或替代数据结构中指定元素的一个或多个数据项(字段值). 4).删除:把指定的数据元素从数据结构中去掉. 5).查找:在数据结构中查找满足一定条件的数据元素. 6).排序:在数据结构中数据元素个数不变的前提下,把元素按指定的顺序重新排列.排序一般是建立在线性逻辑结构的基础上. 线性结构 1.结构特点: 线性结构是数据结构中最简单且最常用的一种数据结构.线性结构基本特点是数据元素有序并有限.正如上一节所述:线性结构的逻辑特征是在其结构中,有且仅有一个无直接前趋而仅有一个直接后继的数据元素为起始元素：有且仅有一个无直接后继而仅有一个直接前趋的数据元素为终点元素：其余均为内部元素，它们各有一个直接前趋和直接后继.因此,线性结构的数据元素可排成一个线性的序列: A1,a2,……an 其中,a1为起始元素,an为终点元素,ai为索引号为i的数据元素. 2.常见的线性结构: 线性结构有各种类型,如线性表,堆栈,队列,数组,串等. (一)线性表:线性表是n(n0)个相同类型的元素a1,a2,……an所构成的有限线性序列,通常表示为(a1,a2,……an),其中n为线性表的长度.ai(1in)是线性表中第i个位置的数据元素.ai是抽象表示符号,在不同的情况下含义不同.例如:一个整数序列:(1,12,123,1234,321,21,22)是一个线性表,表中元素ai是一个整数,表长为7. 线性表有两种存储方式,对应地把线性表分成了两类:顺序存储结构的顺序表和链式存储结构的链表. (1).顺序表: 顺序表:在顺序表的存储结构中,数据元素按其逻辑次序集中存放在地址连续的存储单元里,由于逻辑上的相邻的元素存放在内存的相邻单元中,所以顺序表的逻辑