一、什么是数据结构

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

数据结构基本术语

• 数据
数据是指所有能输入到计算机并被计算机程序处理的符号的介质的总称
程序的操作对象,用于描述客观事物.
数据的特点: 1 可以输入到计算机 2 可以被计算机处理

• 数据元素
数据元素(data element)是[计算机]科学术语。它是数据的基本单位，数据元素也叫做结点或记录

• 数据项
组成数据元素的最小单位

• 数据对象
在应用程序中引用的任何数据结构元素，如文件、数据、变量等都称为数据对象，简称为对象
性质相同的数据元素的集合(类似于数组)

• 数据结构
结构：数据元素之间不是独立的,存在特定的关系.这些关系即是结构;
数据结构：指的数据对象中的数据元素之间的关系

• 逻辑结构与物理结构 数据类型与抽象数据类型

通过下图你可以更直观的去了解

1712f67ca2dbc4e0 (1).png

思维导图

1-2算法与数据结构导图.png

二、逻辑结构

集合结构

EFAC9102-8B38-4D9C-98F4-B722D5EE03D6.png

线性结构

439D38ED-8D4E-4D9D-BEC5-290989D23FDB.png

树形结构

D33E8DBD-0F38-419B-9E6C-E4761B18BF41.png

图形结构

093F9182-5579-4961-89E4-EB06985BAC36.png

三、物理结构

顺序存储结构

FE3BD769-319B-4598-893A-2F4B0B52BF84.png

链式存储结构

35C79340-E4CB-43CB-88A8-E2F1CEFB7260.png

四、算法

什么是算法? 算法就是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,
并且每个指令表示⼀个或多个操作.

数据结构—算法特性

• 输⼊输出
• 有穷性
• 确定性
• 可⾏性

数据结构算法的设计要求

• 正确性
• 可读性
• 健壮性
• 时间效率⾼和储存量低

五、常见的时间复杂度

image.png

还有一些，最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均情况时间复杂度（average case time complexity）、均摊时间复杂度（amortized time complexity），有兴趣的可以深入研究

六、线性表

线性表可分为顺序表和链式表

一、顺序表

// 定义一个顺序表

typedef struct {
    ElemType *data;
    int length;
}Sqlist;

// 初始化一个顺序表

Status InitList(Sqlist *L){
    //为顺序表分配一个大小为MAXSIZE 的数组空间
    L->data =  malloc(sizeof(ElemType) * MAXSIZE);
    //存储分配失败退出
    if(!L->data) exit(ERROR);
    //空表长度为0
    L->length = 0;
    return OK;
}

//清空顺序表

Status ListEmpty(Sqlist L)
{
    if(L.length==0)
        return TRUE;
    else
        return FALSE;
}

插入

/*
 初始条件：顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
 */
Status ListInsert(Sqlist *L,int i,ElemType e){
    
    //i值不合法判断
    if((i<1) || (i>L->length+1)) return ERROR;
    //存储空间已满
    if(L->length == MAXSIZE) return ERROR;
 
    //插入数据不在表尾,则先移动出空余位置
    if(i <= L->length){
        for(int j = L->length-1; j>=i-1;j--){
       
            //插入位置以及之后的位置后移动1位
            L->data[j+1] = L->data[j];
        }
    }
    
    //将新元素e 放入第i个位置上
    L->data[i-1] = e;
    //长度+1;
    ++L->length;
    
    return OK;
    
}

删除

Status ListDelete(Sqlist *L,int i){
    
    //线性表为空
    if(L->length == 0) return ERROR;
    
    //i值不合法判断
    if((i<1) || (i>L->length+1)) return ERROR;
    
    for(int j = i; j < L->length;j++){
        //被删除元素之后的元素向前移动
        L->data[j-1] = L->data[j];
    }
    //表长度-1;
    L->length --;
    
    return OK;
    
}

二、链表

//定义结点

typedef struct Node{
    ElemType data;
    struct Node *next;
}Node;

typedef struct Node * LinkList;

// 初始化单链表线性表

Status InitList(LinkList *L){
    
    //产生头结点,并使用L指向此头结点
    *L = (LinkList)malloc(sizeof(Node));
    //存储空间分配失败
    if(*L == NULL) return ERROR;
    //将头结点的指针域置空
    (*L)->next = NULL;
    
    return OK;
}

单链表插入

/*
 初始条件:顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：在L中第i个位置之后插入新的数据元素e，L的长度加1;
 */
Status ListInsert(LinkList *L,int i,ElemType e){
 
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    
    //寻找第i-1个结点
    while (p && j<i) {
        p = p->next;
        ++j;
    }
    
    //第i个元素不存在
    if(!p || j>i) return ERROR;
    
    //生成新结点s
    s = (LinkList)malloc(sizeof(Node));
    //将e赋值给s的数值域
    s->data = e;
    //将p的后继结点赋值给s的后继
    s->next = p->next;
    //将s赋值给p的后继
    p->next = s;
    
    return OK;
}

单链表取值

/*
 初始条件: 顺序线性表L已存在,1≤i≤ListLength(L);
 操作结果：用e返回L中第i个数据元素的值
 */
Status GetElem(LinkList L,int i,ElemType *e){
    
    //j: 计数.
    int j;
    //声明结点p;
    LinkList p;
    
    //将结点p 指向链表L的第一个结点;
    p = L->next;
    //j计算=1;
    j = 1;
    
    
    //p不为空,且计算j不等于i,则循环继续
    while (p && j<i) {
        
        //p指向下一个结点
        p = p->next;
        ++j;
    }
    
    //如果p为空或者j>i,则返回error
    if(!p || j > i) return ERROR;
    
    //e = p所指的结点的data
    *e = p->data;
    return OK;
    
    
}

单链表删除元素

/*
 初始条件：顺序线性表L已存在，1≤i≤ListLength(L)
 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1
 */

Status ListDelete(LinkList *L,int i,ElemType *e){
    
    int j;
    LinkList p,q;
    p = (*L)->next;
    j = 1;
    
    //查找第i-1个结点,p指向该结点
    while (p->next && j<(i-1)) {
        p = p->next;
        ++j;
    }
    
    //当i>n 或者 i<1 时,删除位置不合理
    if (!(p->next) || (j>i-1)) return  ERROR;
    
    //q指向要删除的结点
    q = p->next;
    //将q的后继赋值给p的后继
    p->next = q->next;
    //将q结点中的数据给e
    *e = q->data;
    //让系统回收此结点,释放内存;
    free(q);
    
    return OK;
}

重置为空表

/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next;           /*  p指向第一个结点 */
    while(p)                /*  没到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    (*L)->next=NULL;        /* 头结点指针域为空 */
    return OK;
}

单链表前插入法

/* 随机产生n个元素值,建立带表头结点的单链线性表L(前插法)*/
void CreateListHead(LinkList *L, int n){
    
    LinkList p;
    
    //建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    //循环前插入随机数据
    for(int i = 0; i < n;i++)
    {
        //生成新结点
        p = (LinkList)malloc(sizeof(Node));
       
        //i赋值给新结点的data
        p->data = i;
        //p->next = 头结点的L->next
        p->next = (*L)->next;
        
        //将结点P插入到头结点之后;
        (*L)->next = p;
        
    }
}

单链表后插入法

/* 随机产生n个元素值,建立带表头结点的单链线性表L(后插法)*/
void CreateListTail(LinkList *L, int n){
    
    LinkList p,r;
 
    //建立1个带头结点的单链表
    *L = (LinkList)malloc(sizeof(Node));
    //r指向尾部的结点
    r = *L;
    
    for (int i=0; i<n; i++) {
        
        //生成新结点
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        
        //将表尾终端结点的指针指向新结点
        r->next = p;
        //将当前的新结点定义为表尾终端结点
        r = p;
    }
    
    //将尾指针的next = null
    r->next = NULL;
    
}

回想第一次写链表代码的时候，在初始化和指针问题上憋了一个下午，回想起来都是泪，但多写多练之后你就再也不会害怕写链表代码了。