数据结构笔记【1】

数据的三种结构

逻辑结构

包含：

• 集合
• 线性结构（一对一），如线性表、栈、队列
• 树形结构 一个对多个
• 图状结构 多个对多个

存储结构

• 顺序存储：按照逻辑顺序存放于连续空间
• 链式存储（重点）：放到存储区的不同位置，用地址（指针）方式建立逻辑上的联系
• 索引存储：建立附加的索引表（电话簿）
• 散列存储：依据数据元素的特殊字段（关键字key）计算元素的存放地址，然后按地址存放

线性表

线性表是包含若干数据元素的一个线性序列，记为

$$L=(a_0,...,a_{i-1},a_i,a_{i+1},...,a_{n-1})$$

$L$为表名，$a_i$为数据元素，$n$为表长，$n>0$时表为非空表，否则为空表

线性表可以用二元组形式描述

$$L=(D,R)$$

即线性表$L$包含数据元素集合$D$和关系集合$R$

• 关系符<$a_i$,$a_{i+1}$>为有序对
• 表示任意两个相邻元素之间的先后次序

$E.g.$ 有顺序表L={1,2,3,4,5,6}，若使用$L=(D,R)$表示，则$D={1,2,3,4,5,6}$,$R=<1,2>,<2,3>,...$

线性表的特征：

• 表头无前驱
• 表尾无后继
• 其余元素仅有一个直接前驱和直接后继

顺序存储结构的特点：

• 逻辑上相邻，则存储位置也相邻
• 对元素的存取为随机存取或按地址存储
• 存储密度高
• 对表的插入和删除等运算的时间复杂度高

C语言中，可借助一维数组类型来表述线性表的顺序存储结构

/*
    * @brief:创建新线性表
    * @param:无
    * @return:线性表指针(sqlink类型)，申请失败返回NULL
*/
sqlink list_create()
{
    sqlink L;   //声明sqlink类型的表L
    L = (sqlink)malloc(sizeof(sqlist));  // 为空表申请内存，返回分配的内存地址
    
    //判断内存是否申请成功
    if (L == NULL)
    {
        printf("memory allocation failed\n");
        return NULL;
    }

    memset(L, 0, sizeof(sqlist));   //L指向的sqlist结构体的内存清零
    L->last = -1;   //表示线性表为空

    return L;
}

/*
    * @brief:清除线性表内的元素，全部置为零
    * @param: L:指向表的指针
    * @return:成功返回0，失败返回-1
*/
int list_clear(sqlink L)
{
    //判断是否是空表
    if (L == NULL)
    {
        return -1;
    }

    memset(L, 0, sizeof(sqlist));   //L指向的sqlist结构体的内存清零
    L->last = -1;   //last置为-1，表示线性表为空 

    return 0;
}

/*
    * @brief:判断线性表是否为空表
    * @param: L:指向线性表的指针
    * @return:空表返回1，非空表返回0
*/
int list_empty(sqlink L)
{
    //判断是否为空表
    if (L->last == -1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

/*
    * @brief:求线性表的长度(有效元素个数)
    * @param: L:指向线性表的指针
    * @return:表不存在返回-1，否则返回长度
*/
int list_length(sqlink L)
{
    if (L == NULL)
    {
        return -1;
    }
    return (L->last + 1);   //长度为表尾下标加1
}

/*
    * @brief:向线性表内插入数值，插入后原位置向后的所有元素后移一位
    * @param: L:指向线性表的指针 
    * @param: value:待插入值 
    * @param: pos:插入位置
    * @return:插入成功返回0，失败返回-1
*/
int list_insert(sqlink L, data_t value, int pos)
{
    if (L == NULL) return -1;   //表不存在返回-1
    //判断线性表是否满
    if (L->last == N - 1)
    {
        printf("table is full\n");
        return -1;
    }
    //检查插入位置是否正确，应属于[0,last]，如果是空表则不检查
    if (pos < 0 || pos >= L->last + 1)
    {
        if (L->last != -1) 
        {
            printf("pos is illegal\n");
            return -1;
        }

    }
    //向后移动原有元素，从最后一个元素开始
    for (int i = L->last; i >= pos; i--)
    {
        L->data[i+1] = L->data[i];
    }
    //更新插入值和last
    L->data[pos] = value;
    L->last++;

    return 0;    
}

/*
    * @brief:遍历并打印线性表内元素
    * @param: L:指向线性表的指针
    * @return:成功返回0，失败返回-1
*/
int list_show(sqlink L)
{
    if (L == NULL) return -1;   //判断是否为有效表
    if (L->last == -1) printf("table is empty\n");  //判断是否为空表
    //遍历并打印
    for (int i = 0; i <= L->last; i++)  //注意是小于等于，不然不显示表尾
    {
        printf("%d ",L->data[i]);
    }

    return 0;
}

/*
    * @brief:删除全表，包括创建表时所分配的内存
    * @param: L:指向线性表的指针
    * @return:表不存在返回-1，成功返回0
*/
int list_delete(sqlink L)
{
    if (L == NULL) return -1;
    free(L);    //释放为表L申请的内存
    L = NULL;   //标记表L为无效表
    return 0;
}

/*
    * @brief:删除表中某一位置的元素
    * @param: L：指向线性表的指针
    * @param: pos：待删除元素位置
    * @return:删除成功返回0，失败返回-1
*/
int list_delete_single(sqlink L, int pos)
{
    if (L == NULL) return -1;   //判断是否为无效表

    //判断pos是否位于有效范围内 应为[0,last]
    if (pos < 0 || pos > L->last)
    {
        printf("pos is illegal\n");
        return -1;
    }

    //[pos+1,last]区间内已有元素前移
    for (int i = pos + 1; i < L->last + 1; i++)
    {
       L->data[i-1] = L->data[i];   //数据前移，自动覆盖
    }

    //更新last
    L->last--;   

    return 0;
}

/*
    * @brief:合并两个线性表，L2全表元素置于L1元素之后
    * @param: L1：指向待合并线性表L1的指针
    * @param: L1：指向待合并线性表L2的指针
    * @return:合并成功返回0，失败返回-1
*/
int list_merge(sqlink L1, sqlink L2)
{
    int count = 0;
    if (L1 == NULL || L2 == NULL) return -1;

    //判断合并后L1是否越界
    if (L1->last + 1 + L2->last + 1 > N) printf("table is too big\n");

    //L2的第i位加到L1的last+1+i位置，总共传递L2->last个数
    for (int i = 0; i <= L2->last; i++)
    {
        L1->data[L1->last+1+i] = L2->data[i];
        count++;    //计数
    }

    //更新L1->last为原last值+传递完成的元素个数
    L1->last = L1->last + count;

    return 0;
}

/*
    * @brief:查询线性表中是否存在某一元素
    * @param: L：指向待查询线性表L的指针
    * @param: value：待查询值
    * @return:值对应的元素存在返回1，不成功返回-1
*/
int list_locate(sqlink L, data_t value)
{
    int i = 0;

    //搜索L中是否有元素等于value
    for (i = 0 ; i <=L->last; i++)
    {
        if (L->data[i] == value) return 1;
    }

    return -1;
}

/*
    * @brief:查找L1和L2中是否有相同的元素，将不同的元素存于新表L3
    * @param: L1：指向待合并线性表L1的指针
    * @param: L2：指向待合并线性表L2的指针
    * @return:合并成功返回0，失败返回-1
*/
sqlink list_mergetonewtable(sqlink L1, sqlink L2)
{
    sqlink L3 = list_create();  //创建新表L3
    int i = 0;
    int ret;

    if (L1 == NULL || L2 == NULL) 
    {
        printf("no such table");
        return NULL;
    }
    //遍历L2内元素
    while (i <= L2->last)
    {
        ret = list_locate(L1, L2->data[i]);   //查找L1中是否有L2中的第i个元素，即判断是否重复
        //某元素不重复则向L3插入
        if (ret == -1)
        {
            list_insert(L3, L2->data[i], L3->last+1);   //按顺序向L3插入非重复值
        }
        i++;    //更新索引
    }
    return L3;
}

/*
    * @brief:清除线性表内的重复元素，清除后所有元素前移补空
    * @param: L：指向待合并线性表L1的指针
    * @return:操作成功返回0，失败返回-1
*/
int list_purge(sqlink L)
{
    if (L == NULL) return -1;

    for (int i = 0; i <= L->last; i++)  //遍历线性表
    {
        for (int j = i + 1; j <= L->last; j++)  //从索引i+1开始，如果i+1及之后的元素和data[i]相等，判断为重复
        {
            if (L->data[i] == L->data[j])
            {
                printf("The repeated elements are:%d\n",L->data[i]);
                list_delete_single(L, j);   //删除重复的第j个元素
                j--;    //回退索引，防止跳过未检查的元素
            }
        }
    }
    return 0;
} 

线性表的顺序存储缺点

• 要求系统提供一大片连续存储空间
• 插入、删除等运算需要遍历整个内存，运算耗时，且元素可能在存储器中成片移动