数据结构与算法

数据结构

数据、数据对象、数据元素、数据项，层层包含的关系
数据：描述客观事物的符号，是计算机中可操作的对象，能被识别，并输入给计算机处理的符号集合。
数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。数据元素才是数据结构中建立数据模型的着眼点。
数据项：一个数据元素的组成部分。是数据不可分割的最小单位。
数据对象：性质相同的数据元素的集合，是数据的子集。存储数据的容器

数据结构

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合

逻辑结构：数据对象中数据元素之间的相互关系

集合结构：各个元素都是平等的。除了同属于一个集合外，无其他关系。
线性结构：线性结构中数据元素之间是一一对应的关系
树形结构：数据元素之间存在一种一对多的层次关系
图形结构：多对多的关系

逻辑结构示意图
每个数据元素看错一个结点，用圆圈表示
元素之间的关系连线表示，如果有方向，则用带箭头的连线表示
物理结构：也叫存储结构，数据的逻辑结构在计算机中的存储形式

顺序存储结构：存放地址连续的存储单元，数据间逻辑关系和物理关系一致，顺序一定，如数组
链式存储结构：数据元素存放在任意的存储单元，可连续也可不连续。不能反映逻辑关系，用指针存放地址，通过指向地址确定顺序

逻辑结构是面向问题的，物理结构是面向计算机的，基本目标是将数据及其逻辑关系存储到计算机内存中。

数据类型

数据类型：指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
数据本身没有类型，是抽象出来的。

原子类型：不可再分解的基本类型，包括整型 实型 字符型等
结构类型：由若干个类型组合而成，可再分解的。如整型数组由若干整型数据组成

抽象数据类型：Abstract Data Type 指数学模型及定义在该模型上的一组操作。抽象的意义在于数据类型的书序抽象特性。体现程序设计种问题分解、抽象和信息隐藏的特性

数据结构与数据类型

数据结构：数据元素之间的相互关系
数据类型：性质相同的值的集合以及一些操作的总称

算法

算法是解决等特点问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令标识一个或多个操作

算法特性

算法特性：输入、输出、有穷性、确定性、和可行性

输入输出：算法具有零个或多个输入，至少有一个或多个输出
有穷性：指算法在执行有限的步骤之后，自动结算二不会出现无限循环
确定性：算法的每一步都具有确定的含义，不会出现二义性
可行性：算法的每一步必须是可行的，也就是每一步都能够通过执行的有限次数完成

算法设计要求

算法设计要求：正确性 可读性健壮性 时间效率高 存储量低

正确性：至少具有输入、输出和加工处理无歧义能正确反映问题的需求、能够得到问题的正确答案
可读性：算法设计的另一目的是为了便于阅读、理解和交流
健壮性:当输入数据不合法时，算法也能做出相关处理，而不是产生或莫名其妙的结果
时间效率高：执行时间段
存储量低：算法程序运行时所占的内存或外部硬盘存储空间

算法效率度量

事后统计法：不予采纳
事前分析估算法：算法采用的策略、方法；编译产生的代码质量；问题的输入规模；机器执行指令的速度。

一个程序运行的时间，依赖于算法的好坏和问题的输入规模，所以问题输入规模是指输入量的多少。在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。

函数的渐近增长

函数的渐近增长：给定两个函数f(n),g(n),如果存在一个整数N，使得n>N，f（n）总是比g（n）大，那么我们说f(n)的增长渐近快鱼g(n)

与最高次项相乘的常数并不重要，最高次项的指数大的，函数随着n的增长，解雇偶也会变得增长特别快
判断一个算法效率时，函数中的其他常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数

算法时间复杂度

定义：语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随时间变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记做：T(n)=O(f(n))。表示问题规模n的增大，算法执行时间的增长率和f(n）的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。期中f（n）是问题规模n的某个函数

推导大O阶：
1 用常数1取代运行时间中的所有加法常数
2 在修改后的运行次数函数中，只保留最高阶项
3 如果最高阶项存在且不是1，则去除与这个项相乘的常数

常数阶O(1) :无论常数是多少都是O(1)
线性阶：分析循环结构的运行情况（+ -）
对数阶：如下所示运行x次大于n，即2的x次方大于n时结束，x为一对数

int count = 1;
while （count<n）
{
    count * 2;
    /**循环体复杂度为O(1)**/
}

平方阶：循环嵌套

循环的时间复杂度=循环体的复杂度x循环运行次数
常用的时间复杂度所耗费的时间从小到大依次是：
O(1) < O(logn) < O(n) < O($n^2$)< O($n^3$)< O(指数)< O(阶乘）< O(幂）

算法空间复杂度

通过计算孙发所需的存储空间实现，算法空间复杂度的计算公式：
S(n)=O(f(n)),n为问题规模，f(n)为语句关于n所占存储空间的函数

线性表

零个或多个数据元素的有限序列

线性表记为（a1 a2 a3... an）则表中ai-1领先于ai，ai领先于ai+1，直接前驱元素 直接后继元素 i=1 和i=n-1分别只含有后继和前驱

线性表元素个数n定义为其长度，n=0时，为空表
在较为复杂的线性表中，一个数据元素可以有若干个数据项组成

线性表的抽象数据类型

Operation
    InitLis（*L）：初始化操作，建立一个空表
    ListEmpty（L）：若线性表为空，返回true，否则返回false
    ClearList（*L）：将线性表清空
    GetElem（L,i,*e）：将线性表L中第i个位置元素值返还给e
    LocateElem（L,e）：查找与给定值e相等的元素，如果查找成功，则返回该元素在表中序号表示成功；否则，返回0表示失败
    ListInsert（*L,i,e）：在线性表L中的第i个位置插入新元素e
    ListDelete（*L,i,e）：删除表L中的第i个位置的元素，并用e返回其值
    ListLength（L)：返回线性表L的元素个数
endADT

应用示例

void unionL(List *La, List Lb)
{
    int La_len, Lb_len,i;
    ElemType e;
    La_len=ListLength(*La);
    Lb_len=ListLength(Lb);
    for (i=1;i<Lb_len;i++)
    {
        GetElem(Lb,i,e);
        if(!LocateElem(*La,e);)
            ListInsert(La,++La_len,e)
    }
 }

线性表的顺序存储结构

三个属性：数组data存储空间的起始位置、线性表的最大存储容量Maxsize；线性表当前的长度lenght

数组长度和线性表长度：
数组长度：存放线性表存储空间的长度，存储分配后一般不变
线性表长度：线性表中数据元素的个数，随着插入和删除，该量不断变化

地址计算方法

存储器汇总的每个存储单元都有自己的编号，即地址
从0开始：0 1 2 3 ，....，n
LOC表示获得存储位置的函数

线性表顺序存储结构的插入与删除

获取元素值

/**实现GetElem操作，获取第i个位置的元素值**/
 #define OK 1 
 #define ERROR 0
 #define true 1
 #define false 0
 typedef int Status;
 /*初始条件：顺序线性表L已存在，1≤i≤ListLenght(L)*/
 /*操作结果：用e返回L中第i个数据元素的值*/
 Status GetElem(SqList L, int i, ElemType *e)
 {
    if(L.Length==0 || i<1 || i>L.Length)
    /*如果L为空表或者i小于1或者i的长度比表要长，都报错*/
        return ERROR;
    *e=L.data[i-1];
    return OK;
 }

插入元素值

插入算法思路：

1 位置不合理，则抛出异常；
2 线性表长度>=数组长度，则抛出异常或动态增加容量
3 从最后一个元素开始遍历到第i个位置，分别将它们后移一位
4 将插入元素填入位置的i处，表长加1

 /*初始条件：顺序线性表L已存在，1≤i≤ListLenght(L)*/
 /*操作结果：在L中第i个位置之前插入新的数据元素 e，L的长度加1*/
 Status ListInsert(SqList *L,int i,ElemType e)
 {
    int k;
    if (L->length==MAXSIZE) /*数据表已经满了*/
        return ERROR;
    if (i<1 || i>L->length+1)/*当i不在范围内时*/
        return ERROR
    if (i<=L->length)/*当插入的位置不在表尾时*/
    {
        for (k=L->lenght;k>=i-1;k--)/*将要插入位置哈后的数据元素想后移动一位*/
            L->data[k+1]=L->data[k];
    }
    L->data[i-1]=e;/*将新元素插入*/
    L->length++;
    return OK;
 }

删除元素值

/*删除元素的算法*/
  /*初始条件：顺序线性表L已存在，1≤i≤ListLenght(L)*/
 /*操作结果：在L中第i个位置之前删除数据元素 e，并用e返回其值，L的长度减1*/
 Status ListDelete(SqList *L,int i,ElemType *e)
 {
    int k;
    if (L->length==0) /*线性表为空*/
        return ERROR
    if (i<1 || i>L->length)/*当i不在范围内时*/
        return ERROR
    *e=L->data[i-1];
    if (i<L->length)/*如果删除的不是最后位置*/
    {
        for (k=i;k<L->length;k++) /*将删除位置后继元素前移*/
            L->data[k-1]=L->data[k];
        }
        L->length--;
        return OK;
 }

线性表顺序存储结构优缺点

线性表的链式存储结构

单线索、无分支
为了表示每个暑假元素ai与其直接后技术局元素ai+1的之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其后继的信息。把存储数据元素信息的域称为数据域，把数据直接后继位置的域称为指针域。指针域中存储的信息称作指针或链

链表的第一个结点的存储位置叫做头指针，最后一个为“空”"NULL"或“^”，每个结点上的指针是上一个后继指针指向的位置

有时候在第一个结点前附设一个头结点存放公共信息，从而第一个结点变成了头结点。实际上命名仍没有发生变化，第一个结点我们叫头结点，第二个仍叫“第一个结点”。

头指针和头结点异同点

线性链表式存储结构代码描述

结点由存在数据元素的数据域和存放后继结点地址的指针域组成。

p->data
p->next->data

循环列表

树

结点拥有的子树数目为度，度为零时称为叶节点