【1】数据结构概述

【1.1】什么是数据结构？

【1.2】数据结构分类

【1.3】数据结构术语

【2】数据结构特点

【2】动态顺序表

【2.1】动态顺序表定义数据结构和接口

【2.1】动态顺序表创建初始化

【2.2】动态顺序表初始化

【2.3】动态顺序表内存释放

【2.4】动态顺序表检测扩容

【2.5】动态顺序表头插入

【2.6】动态顺序表尾插入

【2.7】动态顺序表指定位置前插入

【2.8】动态顺序表指定位置后插入

【2.9】动态顺序表头删除

【2.10】动态顺序表尾巴删除

【2.11】态顺序表指定位置前删除

【2.12】动态顺序表指定位置后删除

【2.13】动态顺序表有效数据个数

【2.14】动态顺序表查找

【2.14】动态顺序表修改

【2.15】动态顺序表打印

【2.16】动态顺序表判断空

【1】数据结构概述

【1.1】什么是数据结构？

官方解释：数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及他们之间的关系和操作等相关问题的学科。

大白话：数据结构就是把数据元素按照一定的关系组织起来的集合，用来组织和存储数据。

【1.2】数据结构分类

逻辑结构分类：

逻辑结构是从具体问题中抽象出来的模型，是抽象意义上的结构，按照对象中数据元素之间的相互关系分类，也是我们后面课题中需要关注和讨论的问题。

集合结构：

结合结构中数据元素出了属于同一集合外，他们之间没有任何其他关系。

线性结构：

线性结构中的数据元素之间存在一对一的关系。

树形结构：

树形结构中的数据元素之间存在多对一的层次关系。

图形结构：

图形结构的数据元素是多对多的关系。

物理结构分类：

逻辑结构在计算机中真正的表示方式(又称映像)称为物理结构，也可以叫做存储结构，常见的物理结构有顺序存储结构、链式存储结构。

顺序存储结构：

逻辑结构在计算机中真正的表示方式(又称映像)称为物理结构，也可以叫做存储结构，常见的物理结构有顺序存储结构、链式存储结构。

顺序存储结构存在一定的弊端，就想生活中排队时，会有人插队也有可能有人突然离开，这时候整个结构都处于变化之中，此时就需要链式存储结构。

是把数据元素存放在任意的存储单元里面，这组存储单元可以是连续的，也可以是不连续的。此时，数据元素之间的关系，并不能反映元素间的逻辑关系，因此链式存储中引进了一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。

【1.3】数据结构术语

抽象数据类型：(Abstract Data Type,简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

抽象数据类型和数据类型实质上是一个概念。例如,各个计算机都拥有的“整数”类型是一个抽象数据类型,尽管它们在不同处理器上实现的方法可以不同,但由于其定义的数学特性相同,在用户看来都是相同的。因此,“抽象”的意义在于数据类型的数学抽象特性。

数据结构的表示(存储结构)用类型定义( typedef)描述。数据元素类型约定为Data。

【2】数据结构特点

线性结构的特点是：

在数据元素的非空有限集合中。

存在唯一的一个被称为"第一个"的数据元素
存在唯一的一个被称为“最后一个”的数据元素
除了第一个之外，结合中的每个数据元素均只有一个前驱
除了最后一个之外，集合中每个数据元素均只有一个后继

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

线性表示一个相当灵活的数据结构，它的长度可以根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等。

【2】动态顺序表

【2.1】动态顺序表定义数据结构和接口

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

/* 动态顺序表-数据结构 */ 
typedef int SEQLDataType;
typedef struct SequenceList {
    SEQLDataType* _data;            // 数组类型：存储容器.
    size_t _size;                   // 有效数据个数.
    size_t _capacity;               // 有效容器容量.
}SeqList;

/* 动态顺序表-创建初始化函数 */
SeqList* SequenceListCreateInitialize();

/* 动态顺序表-初始化函数 */
void SequenceListInitialize(SeqList* pSL);

/* 动态顺序表-释放内存 */
void SequenceListDestory(SeqList* pSL);

/* 动态顺序表-检测容量 */
void SequenceListCheakCapacity(SeqList* pSL);

/* 动态顺序表-头部插入 */
void SequenceListPushFront(SeqList* pSL, SEQLDataType val);

/* 动态顺序表-尾部插入 */
void SequenceListPushBack(SeqList* pSL, SEQLDataType val);

/* 动态顺序表-指定位置前插入 */
void SequenceListPushInsterFront(SeqList* pSL, size_t pos, SEQLDataType val);

/* 动态顺序表-指定位置后插入 */
void SequenceListPushInsterBack(SeqList* pSL, size_t pos, SEQLDataType val);

/* 动态顺序表-头部删除 */
void SequenceListPopFront(SeqList* pSL);

/* 动态顺序表-尾部删除 */
void SequenceListPopBack(SeqList* pSL);

/* 动态顺序表-指定位置前删除 */
void SequenceListPopEraseFront(SeqList* pSL, size_t pos);

/* 动态顺序表-指定位置后删除 */
void SequenceListPopEraseBack(SeqList* pSL, size_t pos);

/* 动态顺序表-大小 */
size_t SequenceListSize(SeqList* pSL);

/* 动态顺序表-查找 */
int SequenceListFind(SeqList* pSQL, SEQLDataType val);

/* 动态顺序表-修改 */
void SequenceListModification(SeqList* pSQL, size_t pos, SEQLDataType val);

/* 动态顺序表-打印 */
void SequenceListPrint(SeqList* pSQL);

/* 动态顺序表-判空 */
bool SequenceListEmpty(SeqList* pSQL);

【2.1】动态顺序表创建初始化

创建结构体指针，对其进行初始话。

/* 动态顺序表-创建初始化函数 */
SeqList* SequenceListCreateInitialize() {
    // 创建SeqList指针对象，初始化后返回指针.
    SeqList* pTemp = (SeqList*)malloc(sizeof(SeqList));
    if (pTemp == NULL) {
        perror("SequenceListCreateInitialize malloc fail!\n");
        exit(-1);
    }

    // 处理数据.
    pTemp->_data = NULL;
    pTemp->_size = pTemp->_capacity = 0;
    return pTemp;
}

【2.2】动态顺序表初始化

/* 动态顺序表-初始化函数 */
void SequenceListInitialize(SeqList* pSL) {
    // 断言保护指针数据.
    assert(pSL);

    // 处理数据.
    pSL->_data = NULL;
    pSL->_size = pSL->_capacity = 0;
}

【2.3】动态顺序表内存释放

/* 动态顺序表-释放内存 */
void SequenceListDestory(SeqList* pSL) {
    // 断言保护指针数据.
    assert(pSL);

    free(pSL->_data);
    pSL->_data = NULL;
    free(pSL);
    pSL = NULL;
}

【2.4】动态顺序表检测扩容

这个检测扩容的函数提前拿出来说一下，在每次进行添加数据的时候，都要进行检测扩容，如果数据不足的话就应该进行扩容了，值得注意的是，此程序没有初始化的开辟内存，当容量和数据个数相等的时候，会自己判断是否是第一次扩容。

/* 动态顺序表-检测容量 */
void SequenceListCheakCapacity(SeqList* pSL) {
    // 断言保护指针数据.
    assert(pSL);
    
    // 检查扩容.
    if (pSL->_size == pSL->_capacity) {
        // 程序走到这里，说明需要进行扩容了.
        // 检查是否是第一次扩容，第一次扩容扩4个，第二次扩容扩2倍.
        size_t newCapacity = pSL->_capacity == 0 ? 4 : pSL->_capacity * 2;
        SEQLDataType* pTemp = (SEQLDataType*)realloc(pSL->_data, sizeof(SEQLDataType) * newCapacity);
        if (pTemp == NULL) {
            perror("SequenceListCheakCapacity realloc faid!\n");
            exit(-1);
        }

        // 程序走到这里说明扩容成功了，数据进行处理.
        pSL->_data = pTemp;
        pTemp = NULL;
        // 更新容量.
        pSL->_capacity = newCapacity;
    }

}

代码这里用了realloc这个函数进行扩容的，为啥不用malloc呢？

【2.5】动态顺序表头插入

在头插前我们需要把第一位的数据空出来，注意：我们需要倒这拿数据。

/* 动态顺序表-头部插入 */
void SequenceListPushFront(SeqList* pSL, SEQLDataType val) {
    // 断言保护指针数据.
    assert(pSL);

    // 检测扩容.
    SequenceListCheakCapacity(pSL);

    // 插入数据，将数据从后往前挪动，挪动完成下标为0的数据就可以插入了.
    size_t end = SequenceListSize(pSL);
    while (end > 0) {
        pSL->_data[end] = pSL->_data[end - 1];
        --end;
    }

    // 挪动完成，将数据插入0位置.
    pSL->_data[0] = val;
    ++pSL->_size;
}

【2.6】动态顺序表尾插入

/* 动态顺序表-尾部插入 */
void SequenceListPushBack(SeqList* pSL, SEQLDataType val) {
    // 断言保护指针数据.
    assert(pSL);

    // 检测扩容.
    SequenceListCheakCapacity(pSL);

    // 挪动完成，将数据插入0位置.
    pSL->_data[SequenceListSize(pSL)] = val;
    ++pSL->_size;
}

【2.7】动态顺序表指定位置前插入

/* 动态顺序表-指定位置前插入 */
void SequenceListPushInsterFront(SeqList* pSL, size_t pos, SEQLDataType val) {
    // 断言保护指针数据.
    assert(pSL);

    // 检测扩容.
    SequenceListCheakCapacity(pSL);

    // 移动数据
    // 这里需要注意：如果顺序表没有数据的话，直接进行尾插。
    size_t end = SequenceListSize(pSL);
    while (end > pos) {
        pSL->_data[end] = pSL->_data[end - 1];
        --end;
    }
    pSL->_data[pos] = val;
    ++pSL->_size;
}

【2.8】动态顺序表指定位置后插入

与指定位置前插入是一致的，注意：数组边界，否侧会出现访问冲突。

![1-9](E:\文档\【ShaXiang】LearningNotes\【LessonRecord】C.C++_数据结构与算法\【01】\1-9.png)/* 动态顺序表-指定位置后插入 */
void SequenceListPushInsterBack(SeqList* pSL, size_t pos, SEQLDataType val) {
    // 断言保护指针数据.
    assert(pSL);

    // 检测扩容.
    SequenceListCheakCapacity(pSL);

    // 移动数据
    // 这里需要注意：如果顺序表没有数据的话，直接进行尾插。
    if (pos == 0) {
        size_t end = SequenceListSize(pSL);
        while (end > pos + 1) {
            pSL->_data[end] = pSL->_data[end - 1];
            --end;
        }
        pSL->_data[pos + 1] = val;
        ++pSL->_size;
    }
    else {
        size_t end = SequenceListSize(pSL);
        while (end > pos) {
            pSL->_data[end] = pSL->_data[end - 1];
            --end;
        }
        pSL->_data[pos + 1] = val;
        ++pSL->_size;
    }
}

【2.9】动态顺序表头删除

/* 动态顺序表-头部删除 */
void SequenceListPopFront(SeqList* pSL) {
    // 断言保护指针数据.
    assert(pSL);

    // 检查是否还有数据存在.
    if (SequenceListEmpty(pSL)) {
        printf("SeqList Not Data!\n");
        return;
    }

    // 直接删除数据，容器数组中从元素下标0开始，依次往前覆盖数据.
    size_t begin = 0;
    while (begin < SequenceListSize(pSL) - 1) {
        pSL->_data[begin] = pSL->_data[begin + 1];
        ++begin;
    }    

    --pSL->_size;
}

【2.10】动态顺序表尾巴删除

尾插的时候无非注意的就是，在插之前检查容量是否满足，让size指向的下表位置的数据存储要插入的数据。

/* 动态顺序表-尾部删除 */
void SequenceListPopBack(SeqList* pSL) {
    // 断言保护指针数据.
    assert(pSL);

    // 检查是否还有数据存在.
    if (SequenceListEmpty(pSL)) {
        printf("SeqList Not Data!\n");
        return;
    }

    --pSL->_size;
}

【2.11】态顺序表指定位置前删除

/* 动态顺序表-指定位置前删除 */
void SequenceListPopEraseFront(SeqList* pSL, size_t pos) {
    // 断言保护指针数据.
    assert(pSL);

    // 检查是否还有数据存在.
    if (SequenceListEmpty(pSL)) {
        printf("SeqList Not Data!\n");
        return;
    }

    // 和头删是一样的，将0的位置变为pos的位置.
    size_t begin = pos;
    while (begin < SequenceListSize(pSL)) {
        pSL->_data[begin] = pSL->_data[begin + 1];
        ++begin;
    }

    --pSL->_size;
}

【2.12】动态顺序表指定位置后删除

指定位置后删除和指定位置前删除是一致的，注意：处理边界问题

/* 动态顺序表-指定位置后删除 */
void SequenceListPopEraseBack(SeqList* pSL, size_t pos) {
    // 断言保护指针数据.
    assert(pSL);

    // 检查是否还有数据存在.
    if (SequenceListEmpty(pSL)) {
        printf("SeqList Not Data!\n");
        return;
    }

    // 和头删是一样的，将0的位置变为pos的位置.
    size_t begin = pos + 1;
    if (begin == SequenceListSize(pSL)) {
        --pSL->_size;
    }
    else {
        while (begin < SequenceListSize(pSL)) {
            pSL->_data[begin] = pSL->_data[begin + 1];
            ++begin;
        }
    }
}

【2.13】动态顺序表有效数据个数

/* 动态顺序表-大小 */
size_t SequenceListSize(SeqList* pSL) {
    // 断言保护指针数据.
    assert(pSL);

    return pSL->_size;
}

【2.14】动态顺序表查找

/* 动态顺序表-查找 */
int SequenceListFind(SeqList* pSL, SEQLDataType val) {
    // 断言保护指针数据.
    assert(pSL);

    // 遍历查找.
    for (size_t i = 0; i < SequenceListSize(pSL); ++i) {
        if (pSL->_data[i] == val)
            return (int)i;
    }

    // 程序走到这里说明没有找到对应的值.
    return -1;
}

【2.14】动态顺序表修改

/* 动态顺序表-修改 */
void SequenceListModification(SeqList* pSL, size_t pos, SEQLDataType val) {
    // 断言保护指针数据.
    assert(pSL);
    
    // 遍历修改.
    pSL->_data[pos] = val;
}

【2.15】动态顺序表打印

/* 动态顺序表-打印 */
void SequenceListPrint(SeqList* pSL) {
    // 断言保护指针数据.
    assert(pSL);
    
    // 遍历打印.
    for (size_t i = 0; i < SequenceListSize(pSL); ++i) {
        printf("%d ", pSL->_data[i]);
    }
    printf("\n");
}

【2.16】动态顺序表判断空

/* 动态顺序表-判空 */
bool SequenceListEmpty(SeqList* pSL) {
    // 断言保护指针数据.
    assert(pSL);

    return pSL->_size == 0;
}

【C数据结构】动态顺序表_SeqList

【1】数据结构概述

【1.1】什么是数据结构？

【1.2】数据结构分类

【1.3】数据结构术语

【2】数据结构特点

【2】动态顺序表

【2.1】动态顺序表定义数据结构和接口

【2.1】动态顺序表创建初始化

【2.2】动态顺序表初始化

【2.3】动态顺序表内存释放

【2.4】动态顺序表检测扩容

【2.5】动态顺序表头插入

【2.6】动态顺序表尾插入

【2.7】动态顺序表指定位置前插入

【2.8】动态顺序表指定位置后插入

【2.9】动态顺序表头删除

【2.10】动态顺序表尾巴删除

【2.11】态顺序表指定位置前删除

【2.12】动态顺序表指定位置后删除

【2.13】动态顺序表有效数据个数

【2.14】动态顺序表查找

【2.14】动态顺序表修改

【2.15】动态顺序表打印

【2.16】动态顺序表判断空

相关文章