1.数据结构

数据结构研究的是数据存储的问题，数据结构=个体的存储+个体的关系存储。
算法 = 对存储数据的操作
衡量算法的标准：

时间复杂度：程序执行的次数，而非时间
空间复杂度：程序执行过程中所占用的最大内存
难易程度
健壮性

2.线性结构

2.1 定义

把所有的结点用一根直线穿起来。

2.2 分类

连续存储（数组）、离散存储（链表）

2.2.1连续存储（数组）

看懂一个程序分为三步：流程、每个语句的功能、试数。
参数，长度，有效元素的个数

（1）用C实现面向对象数组：（此处代码省略了数组增长因子Inversion）

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h> //包含exit函数
struct Array
{
    int* pArr;//数组地址
    int len;//数组长度
    int ctn;//数组有效元素个数
};
void init(struct Array*,int length);//数组初始化
bool is_empty(struct Array*);//数组为空判断
bool is_full(struct Array*);//数组是否满了
bool show_array(struct Array*);//数组打印操作
bool add_array(struct Array*,int value);//数组添加元素操作
int main()
{
    struct Array array;
    init(&array, 10);
    add_array(&array, 4);
    show_array(&array);
    add_array(&array, 5);
    show_array(&array);
}
bool is_full(struct Array* array)
{
    if (array->ctn > array->len)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool add_array(struct Array* array, int value)
{
    if (is_full(array))
    {
        printf("数组已满\n");
        return false;
    }
    else
    {
        int index = array->ctn;
        array->pArr[index] = value;
        (array->ctn)++;
        return true;
    }
}
void init(struct Array* array, int length)
{
    array->pArr = (int*)malloc(sizeof(int)*length);
    if (NULL == array->pArr)
    {
        printf("未申请到内存空间\n");
        exit(-1);//退出函数
    }
    else
    {
        array->len = length;
        array->ctn = 0;
    }
    return;
}
bool is_empty(struct Array* array)
{
    if (0 == array->ctn)
    {        
        return true;
    }
    else
    {
        return false;
    }
}
bool show_array(struct Array* array)
{
    if (!is_empty(array))
    {
        for (int i = 0; i < array->ctn; i++)
        {
            printf("%d\n", array->pArr[i]);
        }
        printf("\n");
        return true;
    }
    else
    {
        printf("数组为空！\n");
        return false;
    }
}

（2）排序

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h> //包含exit函数
struct Array
{
    int* pArr;//数组地址
    int len;//数组长度
    int ctn;//数组有效元素个数
};
void init(struct Array*,int length);
bool is_empty(struct Array*);
bool is_full(struct Array*);
bool show_array(struct Array*);
bool add_array(struct Array*,int value);
bool insert_array(struct Array*, int pos, int val);
void sort_array(struct Array*);
int main()
{
    struct Array array;
    init(&array, 5);
    add_array(&array, 4);
    show_array(&array);
    add_array(&array, 5);
    show_array(&array);
    insert_array(&array, 1, 3);
    show_array(&array);
    v
}
bool is_full(struct Array* array)
{
    if (array->ctn > array->len)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool insert_array(struct Array* parray, int pos, int val)
{
    if (pos<=parray->ctn)
    {
        int index = parray->ctn - 1;
        for (int i = index; i > pos-1; --i)
        {
            parray->pArr[index+1] = parray->pArr[index];
        }
        parray->pArr[pos-1] = val;
        parray->ctn++;
        return true;
    }
    else
    {
        printf("超出数组长度%d\n", parray->len);
        return false;
    }
}
//冒泡排序法
//两两比较，最外围循环递减，内层循环递增
void sort_array(struct Array* parray)
{
    for (int j = parray->ctn - 1; j >0 ; j--)
    {
        for (int i = 0; i < j; i++)
        {
            if (parray->pArr[i] > parray->pArr[i + 1]) {
                int t = parray->pArr[i];
                parray->pArr[i] = parray->pArr[i + 1];
                parray->pArr[i + 1] = t;
            }
        }        
    }
}
bool add_array(struct Array* array, int value)
{
    if (is_full(array))
    {
        printf("数组已满\n");
        return false;
    }
    else
    {
        int index = array->ctn;
        array->pArr[index] = value;
        (array->ctn)++;
        return true;
    }
}
void init(struct Array* array, int length)
{
    array->pArr = (int*)malloc(sizeof(struct Array)*length);
    if (NULL == array->pArr)
    {
        printf("未申请到内存空间\n");
        exit(-1);//退出函数
    }
    else
    {
        array->len = length;
        array->ctn = 0;
    }
    return;
}
bool is_empty(struct Array* array)
{
    if (0 == array->ctn)
    {        
        return true;
    }
    else
    {
        return false;
    }
}
bool show_array(struct Array* array)
{
    if (!is_empty(array))
    {
        for (int i = 0; i < array->ctn; i++)
        {
            printf("%d\n", array->pArr[i]);
        }
        printf("\n");
        return true;
    }
    else
    {
        printf("数组为空！\n");
        return false;
    }
}

（3）小知识

typedef 重命名：

#include <stdio.h>
#include <string>
using namespace std;
typedef struct Student // Typedef重命名
{    
    int Weight;
}ST;//ST等价于struct Student
int main(void)
{
    ST st;
    st.Weight = 120;
    printf("Name = %d\n",st.Weight);
}

#include <stdio.h>
#include <string>
using namespace std;
typedef struct Student // Typedef重命名
{
    int Weight;
}* PST;//PST等价于struct Student *;
int main(void)
{
    struct Student st;
    st.Weight = 120;
    PST pst = &st;
    pst->Weight = 124;
    printf("Name = %d\n",st.Weight);
}

//二合一
#include <stdio.h>
#include <string>
using namespace std;
typedef struct Student // Typedef重命名
{
    int Weight;
}* PST,ST;
int main(void)
{
    ST st;
    st.Weight = 120;
    PST pst = &st;
    pst->Weight = 124;
    printf("Name = %d\n",st.Weight);
}

2.2.2离散存储（链表）

用C实现面向对象Linked
用C实现面向对泛型

（1）链表的重要性：树，图的本质都是链表

（2）定义

n个节点离散分配
彼此通过指针相连
每个节点只有一个前驱节点，每个节点只有一个后续节点
首节点没有前驱节点 尾节点没有后续节点

专业术语：
头节点—首节点————-尾节点
首节点：第一个有效节点
尾节点：最后一个有效节点
头节点：
头节点的数据类型和首节点类型一样
第一个有效节点之前的那个节点
头节点并不存放有效数据
加头节点的目的是为了方便对链表的操作
头指针：指向头节点的指针变量
尾指针：指向尾节点的指针变量

如果希望通过一个函数来对链表进行处理，我们至少需要接受链表的哪些信息：一个参数，头指针
因为我们通过头指针可以推算出链表的其他所有信息
struct Node
{
int data;数据域
struct Node * pNext;指针域
};

（3）分类

单链表
双链表：每个节点有两个指针域
循环链表：
能通过任何一个节点找到其他所有的节点
非循环链表

（4）算法

狭义的算法是与数据存储方式密切相关的，广义的算法与数据存储方式无关。
泛型：利用某种技术达到的效果就是：不同的存储方式执行的操作是相同的。
遍历
查找
清空
销毁
求长度
排序
插入：r=p->pNext;p->pNext = q;q->pNext = r;

（5）链表的优缺点

2.3 链表的创建及遍历

创建

#include <stdio.h>
typedef struct Node {
    int data;//Data Field
    struct Node* pNext;// Point Field
}NODE,*PNODE;
void TraverseList(PNODE);
PNODE CreateList();
int main(void) {
    PNODE pHead = NULL;
    pHead = CreateList();
    TraverseList(pHead);
}
PNODE CreateList() {
    int len;//Node Ctn
    int value;//Node Value
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    PNODE pTail = pHead;
    pTail->pNext = NULL;
    printf("Please input node number:");
    scanf_s("%d", &len);
    if (len > 0) {
        for (int i = 0; i < len; i++)
        {
            printf("Please input value of %d", i + 1);
            scanf_s("%d", &value);
            PNODE pNext = (PNODE)malloc(sizeof(NODE));
            pNext->data = value;
            pTail->pNext = pNext;
            pTail = pNext;
            pNext->pNext = NULL;//The end node pNext is NULL.
        }
    }
    else {
        printf("Please input number more than zero.");
    }
    return pHead;
}
void TraverseList(PNODE pHead) {
    PNODE pTemp = pHead->pNext;
    while (NULL != pTemp) {
        printf("%d\n", pTemp->data);
        pTemp = pTemp->pNext;
    }
}

遍历
临时结点p

#include <stdio.h>
typedef struct Node {
    int data;//Data Field
    struct Node* pNext;// Point Field
}NODE,*PNODE;
void TraverseList(PNODE);
PNODE CreateList();
int main(void) {
    PNODE pHead = NULL;
    pHead = CreateList();
    TraverseList(pHead);
}
PNODE CreateList() {
    int len;//Node Ctn
    int value;//Node Value
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    PNODE pTail = pHead;
    pTail->pNext = NULL;
    printf("Please input node number:");
    scanf_s("%d", &len);
    if (len > 0) {
        for (int i = 0; i < len; i++)
        {
            printf("Please input value of %d", i + 1);
            scanf_s("%d", &value);
            PNODE pNext = (PNODE)malloc(sizeof(NODE));
            pNext->data = value;
            pTail->pNext = pNext;
            pTail = pNext;
            pNext->pNext = NULL;//The end node pNext is NULL.
        }
    }
    else {
        printf("Please input number more than zero.");
    }
    return pHead;
}
void TraverseList(PNODE pHead) {
    PNODE pTemp = pHead->pNext;
    while (NULL != pTemp) {
        printf("%d\n", pTemp->data);
        pTemp = pTemp->pNext;
    }
}

2.4 应用

栈、队列

2.4.1栈实现

栈：先进后出，压栈出栈。

#include <stdio.h>
#include <malloc.h>
#include <stdbool.h>
typedef struct Node {
    int data;
    struct Node* pNext;
}NODE,*PNODE;
typedef struct Stack {
    PNODE pTop;
    PNODE pBottom;
}STACK,*PSTACK;
void init(PSTACK pS);
void push(PSTACK pS, int value);
void traverse(PSTACK pS);
bool pop(PSTACK, int*);
void clear(PSTACK pS);
int main(void) {
    STACK S;
    int popVal;
    init(&S);
    push(&S, 1);
    push(&S, 2);
    push(&S, 3);
    push(&S, 4);
    push(&S, 5);
    traverse(&S);
    if (pop(&S, &popVal)) {
        printf("³öÕ»³É¹¦£¬³öÕ»µÄÔªËØÎª%d\n", popVal);
    }
    else {
        printf("³öÕ»Ê§°Ü\n");
    }
    traverse(&S);
    clear(&S);
    traverse(&S);
}
void init(PSTACK pS) {
    pS->pTop = (PNODE)malloc(sizeof(NODE));
    if (pS->pTop == NULL) {
        printf("Malloc is error.");
        exit(-1);
    }
    else {
        pS->pBottom = pS->pTop;
        pS->pTop->pNext = NULL;
    }
}
void push(PSTACK pS, int value) {
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    pNew->data = value;
    pNew->pNext = pS->pTop; //pS->
    pS->pTop = pNew;
}
bool pop(PSTACK pS, int* popValue) {
    if (pS->pBottom == pS->pTop) {
        return false;
    }
    else {
        PNODE pTmp = pS->pTop;
        *popValue = pTmp->data;
        pS->pTop = pS->pTop->pNext;
        free(pTmp);
        pTmp = NULL;
        return true;
    }
}
void clear(PSTACK pS) {
    if (pS->pBottom == pS->pTop) {
        return;
    }
    else {
        printf("ÕýÔÚÇå³ý...");
        PNODE p = pS->pTop;
        PNODE q = NULL;
        while (p != pS->pBottom) {
            q = p->pNext;
            free(p);
            p = q;
        }
        pS->pTop = pS->pBottom;
        printf("Çå³ýÍê³É");
    }
}
void traverse(PSTACK pS) {
    PNODE p = pS->pTop;
    while (p->pNext != NULL) {
        printf("%d\n", p->data);
        p = p->pNext;
    }
}

2.4.2栈应用

函数调用
中断
表达式求值
走迷宫
内存分配
缓冲处理

2.4.3队列

定义：一种可以实现“先进先出”的存储结构
分类：链式队列、静态队列
静态队列通常都必须是循环队列：

静态队列为什么必须是循环队列
循环队列需要几个参数来确定
循环队列各个参数的含义
循环队列入队伪算法讲解
循环队列出队伪算法讲解
如何判断循环队列是否为空
如何判断循环队列是否已满

01_DotNet技术官

02 线性存储