一. 数据结构

数据结构是数据的集合，这些数据相互之间存在一种或多种特定关系

1.1 数据结构三要素

1.1.1 数据的逻辑结构

逻辑结构是指数据之间的逻辑关系，与数据的存储无关，独立于计算机。

数据的逻辑结构分为线性结构和非线性结构

  1. 线性结构有：线性表，栈，队列
  2. 非线性结构有：树，图

1.1.2 数据的存储结构

存储结构是指数据结构在计算机中的表示。它依赖计算机语言。

存储结构主要有：

  1. 顺序存储
  2. 链式存储
  3. 索引存储
  4. 散列存储

1.1.3 数据的运算

数据的运算是指定义在这个数据结构上的各种操作

二. 线性表

线性表是具有相同数据类型的 $n(n\geqslant0)$ 个数据元素的有限序列，n 为表长，当 n = 0 时线性表是一个空表

若用 L 命名线性表，则其一般表示为 $L=(a_1,a_2,\dots,a_i,a_{i+1},\dots,a_n)$

线性表的逻辑特性如下：

  1. 除第一个元素外，每个元素有且仅有一个直接前驱
  2. 除最后一个元素外，每个元素有且仅有一个直接后继

2.1 线性表的基本操作

一个数据结构的基本操作是指其最核心，最基本的操作。其它较复杂的操作可通过调用基本操作来实现

  1. 初始化表，构造一个空的线性表
initList
  1. 销毁操作，销毁线性表，释放线性表所占用的内存空间
destroyList
  1. 插入操作，在表中第 i 个索引位置上插入指定元素 value
insertList
  1. 输出操作，按前后顺序输出线性表的所有元素值
printList
  1. 求表长，返回线性表中数据元素的个数
length
  1. 判空操作，若 L 为空，返回 true，否则返回 false
empty
  1. 按值查找，返回指定值的元素的索引
getElemByValue
  1. 按位置查找，返回指定索引位置的元素
getElemByLocation
  1. 删除操作，删除表中第 i 个位置的元素，并返回删除的元素
deleteByPos

基本操作的实现取决于采取哪种存储结构，存储结构不同，算法的实现也不同

2.2 线性表的顺序存储

typedef struct{
    int *data;
    int max_size;
    int cur_size;
}Sqlist;

一维数组可以是静态分配的，也可以是动态分配的。在静态分配时，由于数组的大小和空间事先已经固定，一旦空间占满，再加入新的数据就会溢出，进而导致程序崩溃

动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦空间占满，就另外开辟一块更大的存储空间，用以替换原来的存储空间，从而达到扩充存储数组空间的目的

int initSqlist(Sqlist *sqlist, int max_size){
    if(sqlist == NULL || max_size <= 0 || sqlist->data != NULL)
        return -1;
    sqlist->data = (int*)calloc(max_size, sizeof(int));
    sqlist->max_size = max_size;
    sqlist->cur_size = 0;
    return 0;  
}

int destorySqlist(Sqlist *sqlist){
    if(sqlist == NULL || sqlist->data == NULL)
        return -1;
    free(sqlist->data);
    return 0;
}

int insertSqlist(Sqlist *sqlist, int pos, int value){
    if(pos < 0 || pos > sqlist->cur_size)
        return -1;

    if(sqlist->cur_size == sqlist->max_size){
        sqlist->data = (int*)realloc(sqlist->data, sqlist->max_size * 2 * sizeof(int));
        sqlist->max_size *= 2;
    }

    for(int i = sqlist->cur_size++; i > pos; --i){
        sqlist->data[i] = sqlist->data[i - 1];
    }
    sqlist->data[pos] = value;
    return 0;
}

void printSqlist(Sqlist *sqlist){
    for(int i = 0; i < sqlist->cur_size; ++i){
        printf("%d ", sqlist->data[i]);
    }
    printf("\n");
}

int length(Sqlist *sqlist){
    return sqlist->cur_size;
}

bool empty(Sqlist *sqlist){
    if(sqlist->cur_size == 0)
        return true;
    return false;
}

int getElemByValue(Sqlist *sqlist, int value){
    for(int i = 0; i < sqlist->cur_size; ++i){
        if(sqlist->data[i] == value)
            return i;

    }
    return -1;
}

int getElemByLocation(Sqlist *sqlist, int pos){
    if(pos < 0 || pos >= sqlist->cur_size)
        return -1;
    return sqlist->data[pos];
}

int deleteByPos(Sqlist *sqlist, int pos){
    if(pos < 0 || pos >= sqlist->cur_size)
        return -1;
    for(int i = pos + 1; i < sqlist->cur_size; ++i){
        sqlist->data[i - 1] = sqlist->data[i];
    }
    --(sqlist->cur_size);
    return 0;
}

作业

1. 从顺序表中删除具有最小值的元素

2. 从顺序表中删除其值在给定值 s 与 t 之间的所有元素

3. 找出给定数组中未出现的最小正整数