数据结构基础与线性表-六虎

数据结构核心名词解说

以下称号解说摘自《算法与数据结构》严蔚敏版。

数据（Data）

是客观事物的符号表示。在计算机科学中指的是一切能输入到计算机中并被计算机程序处理的符号的总称。

数据元素（Data Element）

数据元素是数据的根本单位，在程序中一般作为一个全体来进行考虑和处理。一个数据元素可有若干个数据项（Data Item）组成。

数据项（Data Item）

数据项是数据不可分割的最小单位。数据项是对客观事物某一方面特性的数据描绘。

数据目标（Data Object）

是性质相同的数据元素的调集，是数据的一个子集。

数据结构（Data Structure）

是指相互之间具有（存在）必定联系（联系）的数据元素的调集。元素之间的相互联系（联系）称为逻辑结构。数据元素之间的逻辑结构有四种根本类型。

逻辑结构与物理结构

逻辑结构

数据元素之间的联系可所以元素之间代表某种含义的天然联系，也可所以为处理问题便利而人为界说的联系，这种天然或人为界说的“联系”称为数据元素之间的逻辑联系，相应的结构称为逻辑结构。逻辑结构有四种根本类型：

调集，结构中的数据元素除了”同归于同一个调集“外，没有其他联系。
线性结构，结构中的数据元素之间存在一对一的联系。
树形结构，结构中的数据元素之间存在一对多的联系。
图状结构或网状联系，结构中的数据元素之间存在多对多的联系。

物理结构

物理结构是指数据逻辑结构在计算机中的存储方式，一般有三种。

次序存储结构，例如线性表。
链式存储结构，如树。
复合存储结构，如图。

算法

算法是对特定问题求解办法（过程）的一种描绘，是指令的有限序列，其中每一条指令表示一个或多个操作。

算法的特性

有穷性：一个算法有必要总是在履行有穷过程之后结束，且每一过程都在有穷时刻内完结。
确定性：算法中的每一条指令有必要有切当的含义。不存在二义性。且算法只有一个入口和出口。
可行性：一个算法是能行的。即算法描绘的操作都可以经过已经实现的根本运算履行有限次来实现。
输入：一个算法有零个或许多个输入，这些输入取自于某个特定的目标调集。
输出：一个算法有一个或多个输出，这些输出是同输出有着某些特定联系的量。

算法规划要求

点评一个好的算法有以下几个标准：

正确性：算法应该满意具体问题的需求。
可读性：算法应该简单供人阅读和交流。可读性好的算法有助于对算法的理解和修正。
健壮性：算法应该有容错处理。当输入非法或许错误数据时，算法能适当的做出反应或许处理，而不是产生不可思议的输出结果。
通用性：算法应具有一般性，即算法的处理结果对于一般的数据调集都建立。
功率与存储量需求：功率指的是算法履行的时刻；存储量需求指算法履行过程中所需要的最大存储空间。一般与问题的规划有关。

算法功率衡量办法

算法履行时刻虚经过根据该算法编制的程序在计算机上运行所消耗的时刻来衡量，也便是时刻复杂度。

时刻复杂度

算法中根本操作重复履行的次数是问题规划n的某个函数，其时刻衡量记作T(n)=O(f(n))，称作算法的渐近时刻复杂度，简称时刻复杂度。一般地，常用最深层循环内的语句中的原操作的履行频度（重复履行的次数）来表示。常用的时刻复杂度的巨细联系为：

空间复杂度

空间复杂度：是指算法编写成程序后，在计算机中运行时所需存储空间的巨细的衡量。记作：S(n)=O(f(n))。其中n为问题的规划。例如：

线性表

线性表(Linear List)：是由n（n>=0）个元素（结点）a1，a2……an组成的有限序列。该序列中的一切结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。

当n=0时，称为空表。
当n>0时，将非空线性表记作：（a1，a2……an），a1称为线性表的第一个（首）结点，an称为线性表的最终一个（尾）结点。

次序存储

把线性表的结点按逻辑次序顺次存放在一组地址接连的存储单元里。用这种办法存储的线性表简称次序表。

次序存储的特色

线性表的逻辑次序与物理次序一致；
数据元素之间的联系是以元素在计算机内“物理方位相邻”来体现。

次序表的根本操作

次序存储结构中，很简单实现线性表的一些操作：初始化、赋值、查找、修正、刺进、删去、求长度等。

次序表的初始化

Status Init_SqList(SqList *L){
    L->elem_array = (ElemType*)malloc(MAX_SIZE*sizeof(ElemType));
    if(!L->elem_array){
        return ERROR;
    }else{
        L->Length = 0;
        return OK;
    }
}

直接进行malloc关键字的内存空间开辟。

次序表的刺进

Status Insert_SqList(Sqlist *L, int i, ElemType e){
    int j;
    if(i<0||i>L->Length-1) return ERROR;
    if(L->Length >= MAX_SIZE){
        printf("线性表溢出！")；
        return ERROR；
    }
    for(j= L->Length;j>=i-1;j--){
        L->Elem_array[j+1] = L->Elem_array[j];
    }
    L->Elem_array[i-1] = e;
    L->Length++;
    return OK;
}

过程实现拆分：

将线性表L中的第i个至第n个结点后移一个方位。
将结点e刺进到结点a[i-1]之后。
线性表长度加1。

线性表的删去

ElemType Delete_SqList(Sqlist *L,int i){
    int l;
    ElemType x;
    if(L->length == 0){
        printf("线性表L为空")；
        return ERROR；
    }else if(i<1||i>L->length){
        printf("要删去的数据元素不存在")；
        return ERROR；
    }else{
        //要删去的结点的值 保存
        x = L->Elem_array[i-1];
        for(k = i; k<L->Lenght;k++){
            L->Elem_array[k-1] = L->Elem_array[k];
            L->length--;
            return(x);
        }
    }
}

过程解析：

将线性表L中的第i+1个至第n个结点顺次向前移动一个方位。
线性表长度减1。

链式存储

用一组恣意的存储单元存储线性表中的数据元素。用这种办法存储的线性表简称线性链表。

链式存储的特色

存储链表中结点的一组恣意的存储单元可所以接连的，也可所以不接连的，乃至是分布在内存中的恣意方位上的。链表中的逻辑次序和物理次序不必定相同。

本篇主要介绍了一些根本概念，下一篇会对链表进行具体的介绍和一些根本的操作进行算法实现。

数据结构基础与线性表