C语言软件基础部分知识点

数据结构的基础知识内容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(n0)个相同类型的元素a1,a2,……an所构成的有限线性序列,通常表示为(a1,a2,……an),其中n为线性表的长度.ai(1in)是线性表中第i个位置的数据元素.ai是抽象表示符号,在不同的情况下含义不同.例如:一个整数序列:(1,12,123,1234,321,21,22)是一个线性表,表中元素ai是一个整数,表长为7.线性表有两种存储方式,对应地把线性表分成了两类:顺序存储结构的顺序表和链式存储结构的链表.(1).顺序表:顺序表:在顺序表的存储结构中,数据元素按其逻辑次序集中存放在地址连续的存储单元里,由于逻辑上的相邻的元素存放在内存的相邻单元中,所以顺序表的逻辑关系蕴含在存储单元的邻接关系中.通常顺序表是用一个一维数组和一个指示当前表长的整数来表征.基于顺序表的各种操作(如建表、插入、删除、求表长等)都是很简单的在程序设计课程中一般都应有所介绍,这里仅强调下操作特点,以顺序表插入数据的算法为例:假设顺序表中已有num(1nun(MAXNUM-1))个数据元素,在第i个位置上(0inum)插入一个新的数据元素,构成一个num+1长的顺序表其实现方法是:将原来表中第i个元素到第n个元素后移一个位置,将要插入的元素x插入在第i个位置上,再将表长num加1.(2)线性链表线性链表是采用链式存储方式进行存储的线性表即有一级任意的存储单元来存放线性表有限个数据元素,这组存储单元既可是连续的,也可以是不连续,从而可以大大提高存储器的使用效率.线性链表有单向链表,双向链表和循环链表等多种形式.(a).单向链表:单向链表是链式存储结构中最简单和最基本的结构.因为在链表中元素的逻辑次序与物理存储次序不一定相同,为了能正确表示数据元素间的逻辑关系,在存储每个元素的同时,还必须存储其直接后续(或直接前趋)的存储位置,这一部分称为链.因此,单向链表的每个数据元素都是由二部分组成:存储元素的数据域(data)和存储直接后续元素存储地址的指针域(next)其结构如下:一个线性表a1,a2,……,an,对应的单向链表可以用逻辑示意图1表示.其中,h为链表的头指针,用以确定线性表中第一个元素对应的存储位置.单向链表可以用头指针的名字来命名.链表的终点元素无直接后续,故其指针域为空NIL,在图中用^表示.下图为单向链表示意图:图1设有线性表a1,a2,……an用带头结点的单链表存储,现要求在数据元素ai的结点之前插入一个数据元素为x的结点首先应找到数据元素ai,的结点,以便打开ai-1与,x,x与ai两数据元素之间的链,构成新的链表,算法示意图如图2所示.HaiA2AnnextData图2结点插入显然,与基于唯一数组的顺序表的插入操作比较,线性链表不需要大量的数据元素的移动,使得操作效率明显提高.b)双向链表:在单向链表中,每个结点的指针域只放一个指针,该指针指向该结点元素的直接后继元素的结点,每查找一个数据元素都必须从头结点开始,从前向后单方向搜寻.若在每个元素的结点中,增加指向直接前趋的指针,就可以实现线性链表从后向前的搜寻,即可双向配搭,这种指针域包括指向该结点的直接前趋附于和直接后继的两个指针的存储结构,称为双向链表,简称双链表,双链表的结点结构如图3所示.图3一个带头结点的双链表,其逻辑示意图如图4所示.显然,在双链表中,并不需要用头指针h来命名这个链表,因为,知道priordatanext指向前结点的指针域数据区指向后继结点的指针域xHA1Ai-1Aian^任一结点的指针,就可以访问整个链表的所有结点,包括结点.图4(3)循环链表:循环链表是一种首尾相接的链表.在单链表中最后一个结点的指针域指向空(NIL),如果它指向头结点(带头结点的链表)或第一个元素结点(不带头结点的链表),使整个链表形成一个环,这就构成了单向循环链表.同样,在双链表中,将双链表最后一个结点与头结点(带头结点的双链表)或第一个元素结点(不带头结点的双链表)链接起来,就可构成双向循环链表.(二)栈:栈是限制仅在表的一端进行插入和删除运算的线性表.通常称插入,删除的这一端为栈顶,另一端称为栈底.当表中没有元素是称为空栈.由于栈中元素的插入和删除只能在栈顶进行,所以总是后进栈的元素先出来.即后进先出HA1A2An(LIFO).栈根据存储方式分为采用顺序存储结构的顺序栈和采用链式结构的链栈.栈的结构示意图6所示栈的基本操作包括:判栈空,进栈,出栈等.(三)队列:队列是另一种操作受限的线性表,它只允许在线性表的一端进行数据元素插入操作而在另一端才能进行数据元素删除操作.其中允许插入的一端称为队尾,允许删除的另一端称为队头.根据队列的特点,队列需要两个队列指针来说明;一个是队头指针front,它总是指向队头元素的前一个位置;另一个是队尾指针rear,它总是指向队尾元素所在的存储位置.队列的结构示意图如图7所示.由于队列是元素的插入和删除分别在队尾和队头进行所以总是先入队列的元素先出队列.即队列具有先进先出的特性,故队列又称为先进先出表(FIFO).同栈的操作类似,队列的基本操作包括:判队列空,进队列,出队列等等.(四)数组:数组应是读者十分熟悉的类型,几乎所有的高级程序设计语言都支持数组这种数据类型.在前面讨论的各种线性表结构的顺序存储结构时都是借用一维数组来描述的.数组本身也是一种数据结构,一维数组是一种顺序表结构,多维数组是一种特殊的线性结构,是线性表的推广.基于二维数组应用最为广泛,像数学中的矩阵,生活中的常见报表都是二维数组.因此,二维数组是学习的重点.对于二维数组有两种最基本的操作:(1)给定一组下标,找到与之相应的数据元素.(2)给定一组下标,存取或修改与其相应的数据元素中某个数据项的值.这两种运算,可以归结为给定一组目标,确定与之相应的数据元素的存储地址.而这个问题是与数组的存储结构有关的.最简单的存储结构是顺序结构,在计算机内是用一组连续的内存单元来存储数组的.它又分为两种:一种是行优先顺序存储:数组元素按行向量排列,即i+1行向量紧接在第i个行向量之后;另一种数组顺序存储的方法是按列优先顺序存储:数组元素按列向量排列,即j+1个列向量紧接在第j个列向量之后.设每个数元素占s个存储单元,则在行优先存储中二维数组A(m,n)的每个元素的存储地址可用下列计算公式算出:LOC(aij)=LOC(all)+((i-1)*n+(j-1))*s.设每个数元素占s个存储单元,则在列优先存储中二维数组A(m,n)的每个元素的存储地址可用下列计算公式算出:LOC(aij)=LOC(all)+((i-1)*m+(j-1))*s.另一种二维数组的存储结构是压缩存储结构,用于特殊矩阵和稀疏矩阵的存储.特殊矩阵是指值相同的元素或者零元素的分布有一定规律的矩阵,如对称矩阵,三角矩阵,对角矩阵等,利用其规律可以实现存储压缩.稀疏矩阵是指在一个矩阵中绝大多数元素为零,非零元素很少且无一定规律.在实际应用中,经常会遇到处理大量的稀疏矩阵情况.按照压缩存储的概念,稀疏矩阵只需存储矩阵中的非零元素.这可以通过使用三元组存储法实现.这里三元组指非零元素所处的行值和列值,以及非零元素本身的值.(五)串:串是字符串的简称,它是由零到多个字符组成的连续有限序列,一般记为:S=’a1a2a3….an’,其中,S串名,引号中为串值(单引号本身不是串值).ai是串元素,它由字母或其他符号组成.n(n≥0)是串的长度.对比串的定义和线性表的定义可知,串是一种其数据元素固定为字符的线性表.因此,仅就数据结构而言,串归属于线性表这种数据结构.但是,串的基本操作和线性表上的基本操作相比却有很大的不同.线性表上的操作主要针对线性表中的某个数据元素进行,而串上的操作主要是针对串的整体或串的某一部分子串进行.串的基本操作包括:判串等,求串长,连接串,替换串.第三节非线性结构对于非线结构,重点是让学生建立基本概念.非线性结构的逻辑特征是一个结点元素可能有多个直接前趋或多个直接后继.最主要的非线性结构是树结构,二