软考之路--数据结构之线性表

        数据就是数值,也就是我们通过观察、实验或计算得出的结果。数据有很多种,最简单的就是数字。数据也可以是文字、图像、声音等。数据可以用于科学研究、设计、查证等。结构,组成整体的各部分的搭配和安排,两者完美结合在一起,我们这样需要重新认识她,对她重新审视与定义:数据结构是程序设计的重要理论和技术基础,她所讨论的内容和技术,对从事软件项目的开发有重要作用,通过学习数据结构,我们学会从问题出发,分析和研究计算机加工的数据的特性,以便为应用所设计的数据悬着适当的逻辑结构、存储结构及其相应的操作方法,为提高应用计算机解决问题的效率服务。

        学习希赛视频有一段日子了,这一段日子夹杂的自考和等级考,夸张点儿来说,有过欢笑,也有过泪水,欢笑的是昨天等级考试抽到的两道大题都是原题,泪水的是,第二题有一个空少些了一个return,又想起那句话,总是要等到考试的时候,才知道该念的书没有念,大题一共六十分,如果按往年的算分制度,需要占百分之六十,也就是说六十分要考三十六分才算合格,可是我满打满算,最后一题只能拿到三十四分,可是后话是,过了我开心,过不了更开心,可以再学一遍C++`(*∩_∩*)′,今天小编主要来讲解一下数据结构的数据表,首先,我们来看一下基本数据结构的一张图:

        软考之路--数据结构之线性表

       了解了基本数据结构,进入到我们今天的主题线性表,该博文主要围绕以下内容展开进行阐述:

        软考之路--数据结构之线性表

        一、线性表

        概念:线性表是最简单,最基本,也是最常用的一种线性结构,她有两种存储存储方法,顺序存储和链式存储,主要的基本操作是插入,删除和查找等。

   分类:线性表分为顺序表和链表,其中链表又分为单链表、循环链表和双链表,依次进行分析。

    顺序表,如下图所示:

    软考之路--数据结构之线性表

    顺序结构:顺序结构是最简单的程序结构,也是最常用的程序结构,只要按照解决问题的顺序写出相应的语句就行,它的执行顺序是自上而下,依次执行。举个简单的例子,a = 3,b = 5,现交换a,b的值,这个问题就好像交换两个杯子水,这当然要用到第三个杯子,假如第三个杯子是c,那么正确的程序为: c = a; a = b; b = c; 执行结果是a = 5,b = c = 3。

    链表,如下图所示:

    软考之路--数据结构之线性表

    链表:链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。

   链表的类别:单链表、循环链表、双链表。如下图所示:

   软考之路--数据结构之线性表

    数据域:存放数据;指针域:存放指向下一个节点的地址;循环链表:最后一个节点她的下一个节点是头节点。

双链表:有两个指针域,从两个不同的方向把链表链接起来。双链表可以从两个方向移动,单链表朝单一的方向移动,双链表的灵活度优于单链表。双链表的开支会大一些,因为她有两个指针域。
    单双链表的删除和插入单链表的删除:结点的删除,删除a2,方法:把a1的指针域直接指向a3,跳过a2,就可以了,a2就从链表中删除了,还有一个工作需要把a2释放掉。把要删除的前序结点,前序结点的next域指向她的后序结点。单链表的插入:删除结点是把前序指向后序,那么插入一个结点就是一个逆向的过程,把新的结点,从需要插入的位置,把她的前序结点next域指向新加入的结点,再把新加入的结点的next域指向下一个结点,就可以了。双链表的删除和插入:牵涉两个方面,从左至右列出来,从右至左列出来,并不是简单的一条链过去,一条链过来就完成的,我们需要把四个步骤都写出来,把两个操作的第一步都先完成,完成之后,接着第二步。
   顺序表PK链表

    软考之路--数据结构之线性表

    

    二、队列

    概念:队列是一种特殊的线性表,它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。比如,去食堂排队,排头最先买到菜,后面来的同学排的队尾;进车站时,安检行李,先进去的最先出来,后进去的后出来。

    分类:顺序队列和循坏队列;队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。队列中没有元素时,称为空队列。在队列这种数据结构中,最先插入的元素将是最先被删除的元素;反之最后插入的元素将是最后被删除的元素,因此队列又称为“先进先出”(FIFO—first in first out)的线性表。如下图:

   顺序队列:

    软考之路--数据结构之线性表

    循环队列:

       软考之路--数据结构之线性表

      ps:“对”字写错了,大家不要见笑哦。

      三、栈

      栈:并不是一个实实在在存在的东西,是逻辑上的一个概念,一种思想,一种理念,她不像链式存储和顺序存储一个一个结点,很有规律,她是在顺序存储和链式存储之上的,是逻辑的概念,栈既可以用链式结构来实现,也可以用顺序结构来实现--即数组。定义一个规则,先进后出即可。如下:

   软考之路--数据结构之线性表

   题目如果问你:按0,1,2,3,4入栈,出栈顺序有哪些呢,是不是只有4,3,2,1,0呢?答:错误,也可能按照0,1,2,3,4,出栈,即0入栈,马上出栈,然后1入栈,马上出栈……

   小编寄语:线性表(亦作顺序表)是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构。其中栈和队列是一种特殊的线性表,软考之路,未完待续......

       

上一篇:SQL Sever 2008 R2 数据库(4) ——数据(记录)表 (重点)


下一篇:数据库事务隔离级别