数据结构

关于数据结构的一些基础知识

几种类型的数据结构

1、线性结构:有且仅有一个根节点,且每个根节点最多有一个直接前驱和一个后继的非空数据结构。

2、非线性结构:不满足线性结构的数据结构。

3、二叉树:详见“二叉树”blog。

4、队列:队列是指允许在一端进行插入,在另一端进行删除的线性表,又称“先进先出”的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。 进行插入操作的端称为队尾,进行删除操作的端称为队头。

5、循环队列:循环队列是指将队列的存储空间的最后一个位置绕到第一个位置,形成逻辑上的循环空间。

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

其次链表又分为线性链表与非线形链表。

线形链表:具有链接存储结构的线性表,它用一组地址任意的存储单元存放线性表中的数据元素,逻辑上相邻的元素在物理上不要求也相邻,不能随机存取。

非线形链表:与线形链表相反。

循环链表:循环链表是一种链式存储结构,它的最后一个结点指向头结点,形成一个环。
< !–more–>
7、矩阵:一个m*n的矩阵是一个由m行和n列元素排列成的矩形阵列。

8、栈:栈是一种特殊的线形表,其插入运算与删除运算都只在线性表的一端进行,也被称为“先进后出”表或“后进先出”表。

Ps:栈顶指针top动态反映了栈中元素的变化情况。

9、线形表:线性结构又称线性表,线性表是最简单也是最常用的一种数据结构。

10、顺序存储结构:顺序存储结构是存储结构类型中的一种,该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。ß

查找方法

1、顺序查找

即在线性表中查找指定的元素。最坏情况需查找n次。

2、二分查找

也称折半查找,它是一种高效率的查找方法。但二分查找有条件限制,它要求表必须用顺序存储结构,且表中元素需按有序排列(升序or降序)。对长度为n的线形表,最坏情况下要查找log2^n 次。

排序方法

1、交换排序法

-冒泡排序 :

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  2. 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

  3. 针对所有的元素重复以上的步骤,除了最后一个。

  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

    for(i=1;i<=N-1;i++)

    for(j=1;j<=N;j++)

    if(a[j]>a[j+1])

    {

    t=a[j];a[j]=a[j+1];a[j+1]=t;

    }

-选择排序 :

  1. 每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置。

  2. 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

  3. 以此类推,直到全部待排序的数据元素排完。

  4. 选择排序是不稳定的排序方法。

    for(i=0;i<9;i++)

    {

    k=i;

    for(j=i+1;j<10;j++)

    if(a[k]>a[j]) k=j;

    if(k!=i)

    {

    t=a[i];a[i]=a[k];a[k]=t;

    }

    }

    2、插入排序法
    -简单插入排序法:

    1. 把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表中只包含一个元素,无序表中包含剩余的n-1个元素。
    2. 每次从无序表中取出第一个元素,把它的排序码一次与有序表中的元素的排序码进行比较。
    3. 将它插入到有序表的适当位置,使之成为新的有序表。
    4. 最坏的情况下,要比较n(n-1)/2次移动次数为n(n-1)/2次。

    -希尔排序法:

    1. 也称递减增量排序算法
    2. 将整个待拍序列以某一增量分成若干个子序列。
    3. 分别进行插入排序。
    4. 等到增量足够小时(序列基本有序时),再进行一次直接的插入排序即可。
    5. 图解 见https://www.cnblogs.com/chengxiao/p/6104371.html(借鉴:非本人blog)。

    3、选择类排序法

    -简单的选择排序法:

    1. 扫描整个线形表,从中选出最小的元素,将它交换到表的最前面。
    2. 对剩下的子表采用同样的方法。
    3. 直到子表空为止。
    4. 最坏的情况要比较n(n-1)/2次。

    -堆排序的方法:

    1. 首先将一个无序序列建成堆(一种特别的树状数据结构)。
    2. 将栈定元素(序中最大项)与堆中最后一个元素交换。
    3. 不考虑已换元素,只考虑前n-1个元素构成的子序列。
    4. 将子序列调整为堆。
    5. 反复进行步骤 2。
    6. 知道剩下的子序列空为止。
    7. 最坏的情况下堆排序法需要比较的次数为nlog2^n次。