本文代码实现基本按照《数据结构》课本目录顺序，外加大量的复杂算法实现，一篇文章足够。能换你一个收藏了吧？

?当然如果落下什么了欢迎大家评论指出

目录

顺序存储线性表实现?

单链表不带头标准c语言实现

单链表不带头压缩c语言实现

约瑟夫环-(数组、循环链表、数学)?

线性表表示集合

?线性表实现一元多项式操作

链表环问题

?

移除链表元素

回文链表

链表表示整数，相加

LRU

LFU

合并链表

反转链表

?反转链表2

对链表排序

旋转链表

?数组实现栈

链表实现栈

数组实现队列

链表实现队列

双栈的实现

?栈/队列 互相模拟实现

栈的排序

栈——括号匹配

栈——表达式求值?

借汉诺塔理解栈与递归

单调栈

双端单调队列

?单调队列优化的背包问题

01背包问题?

完全背包问题?

多重背包问题?

?串的定长表示

串的堆分配实现

KMP

一、引子

二、分析总结

三、基本操作

四、原理

五、复杂度分析

Manacher

小问题一：请问，子串和子序列一样么？请思考一下再往下看

小问题二：长度为n的字符串有多少个子串？多少个子序列？

一、分析枚举的效率

二、初步优化

问题三：怎么用对称轴向两边扩的方法找到偶回文？（容易操作的）

那么请问，加进去的符号，有什么要求么？是不是必须在原字符中没出现过？请思考

小结：

三、Manacher原理

假设遍历到位置i，如何操作呢

四、代码及复杂度分析

前缀树

后缀树/后缀数组

后缀树：后缀树，就是把一串字符的所有后缀保存并且压缩的字典树。

?

相对于字典树来说，后缀树并不是针对大量字符串的，而是针对一个或几个字符串来解决问题。比如字符串的回文子串，两个字符串的最长公共子串等等。

后缀数组：就是把某个字符串的所有后缀按照字典序排序后的数组。（数组中保存起始位置就好了，结束位置一定是最后）

AC自动机

数组缺失

二叉树遍历

前序

中序

后序

进一步思考

二叉树序列化/反序列化

先序中序后序两两结合重建二叉树

先序遍历

中序遍历

后序遍历

层次遍历

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

输入某二叉树的后序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字

输入某二叉树的后序遍历和先序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字

先序中序数组推后序数组

二叉树遍历

遍历命名

方法1：我们可以重建整棵树：

https://blog.csdn.net/hebtu666/article/details/84322113

方法2：我们可以不用重建，直接得出：

根据数组建立平衡二叉搜索树

java整体打印二叉树

判断平衡二叉树

判断完全二叉树

判断二叉搜索树

二叉搜索树实现

堆的简单实现

堆应用例题三连

一个数据流中，随时可以取得中位数。

金条

项目最大收益（贪心问题）

?并查集实现

并查集入门三连：HDU1213 POJ1611 POJ2236

HDU1213

POJ1611

?POJ2236

线段树简单实现

功能：一样的，依旧是查询和改值。

查询[s,t]之间最小的数。修改某个值。

那我们继续说，如何查询。

如何更新？

?树状数组实现

最大搜索子树

morris遍历

最小生成树

拓扑排序

最短路

?

简单迷宫问题

深搜DFS\广搜BFS?

?皇后问题

一般思路：

优化1：

优化2：

二叉搜索树实现

Abstract Self-Balancing Binary Search Tree

?

二叉搜索树

概念引入

AVL树

红黑树

size balance tree

伸展树

Treap

最简单的旋转

带子树旋转

代码实现

AVL Tree

前言

二叉搜索树

AVL Tree

旋转

旋转总结

单向右旋平衡处理LL：

单向左旋平衡处理RR：

双向旋转（先左后右）平衡处理LR：

双向旋转（先右后左）平衡处理RL：

深度的记录

单个节点的深度更新

写出旋转代码

总写调整方法

插入完工

删除

直观表现程序

跳表介绍和实现

c语言实现排序和查找所有算法

?

?

---

顺序存储线性表实现?

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

?

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

优点：随机存取表中元素。缺点：插入和删除操作需要移动元素。

?

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储），但是把最后一个数据元素的尾指针指向了首位结点）。

给出两种基本实现：

/*
静态顺序存储线性表的基本实现
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INITSIZE 100
#define ElemType int
#define Status int
#define OK     1
#define ERROR  0

typedef struct
{
	ElemType elem[LIST_INITSIZE];
	int length;
}SqList;

//函数介绍
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//删除
void ListPrint(SqList L);//输出打印
void DisCreat(SqList A,SqList *B,SqList *C);//拆分(按正负)，也可以根据需求改
//虽然思想略简单，但是要写的没有错误，还是需要锻炼coding能力的

Status InitList(SqList *L)
{
    L->length = 0;//长度为0
    return OK;
}

Status ListInsert(SqList *L, int i,ElemType e)
{
    int j;
    if(i<1 || i>L->length+1)
        return ERROR;//判断非法输入
    if(L->length == LIST_INITSIZE)//判满
    {
        printf("表已满");//提示
        return ERROR;//返回失败
    }
    for(j = L->length;j > i-1;j--)//从后往前覆盖，注意i是从1开始
        L->elem[j] = L->elem[j-1];
    L->elem[i-1] = e;//在留出的位置赋值
    (L->length)++;//表长加1
    return OK;//反回成功
}

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int j;
    if(i<1 || i>L->length)//非法输入/表空
        return ERROR;
    *e = L->elem[i-1];//为了返回值
    for(j = i-1;j <= L->length;j++)//从前往后覆盖
        L->elem[j] = L->elem[j+1];
    (L->length)--;//长度减1
    return OK;//返回删除值
}

void ListPrint(SqList L)
{
    int i;
    for(i = 0;i < L.length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");//为了美观
}

void DisCreat(SqList A,SqList *B,SqList *C)
{
    int i;
    for(i = 0;i < A.length;i++)//依次遍历A中元素
    {
        if(A.elem[i]<0)//判断
            ListInsert(B,B->length+1,A.elem[i]);//直接调用插入函数实现尾插
        else
            ListInsert(C,C->length+1,A.elem[i]);
    }
}

int main(void)
{
    //复制的
	SqList L;
	SqList B, C;
	int i;
	ElemType e;
	ElemType data[9] = {11,-22,33,-3,-88,21,77,0,-9};
	InitList(&L);
	InitList(&B);
	InitList(&C);
	for (i = 1; i <= 9; i++)
		ListInsert(&L,i,data[i-1]);
    printf("插入完成后L = : ");
	ListPrint(L);
    ListDelete(&L,1,&e);
	printf("删除第1个后L = : ");
	ListPrint(L);
    DisCreat(L , &B, &C);
	printf("拆分L后B = : ");
	ListPrint(B);
	printf("拆分L后C = : ");
	ListPrint(C);
	printf("拆分L后L = : ");
	ListPrint(L);
}

静态：长度固定

动态：不够存放可以加空间（搬家）

?

/*
子任务名任务:1_2 动态顺序存储线性表的基本实现
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define Status int
#define OVERFLOW -1
#define OK 1
#define ERROR 0
#define ElemType int

typedef struct
{
	ElemType * elem;
	int length;
	int listsize;
}SqList;
//函数介绍
Status InitList(SqList *L); //初始化
Status ListInsert(SqList *L, int i,ElemType e);//插入
Status ListDelete(SqList *L,int i,ElemType *e);//删除
void ListPrint(SqList L);//输出打印
void DeleteMin(SqList *L);//删除最小

Status InitList(SqList *L)
{
    L->elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));//申请100空间
	if(!L->elem)//申请失败
		return ERROR;
	L->length = 0;//长度0
	L->listsize = LIST_INIT_SIZE;//容量100
	return OK;//申请成功
}

Status ListInsert(SqList *L,int i,ElemType e)
{
    int j;
    ElemType *newbase;
    if(i<1 || i>L->length+1)
        return ERROR;//非法输入
        
    if(L->length >= L->listsize)//存满了，需要更大空间
    {
        newbase = (ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));//大10的空间
        if(!newbase)//申请失败
            return ERROR;
        L->elem = newbase;//调指针
        L->listsize+= LISTINCREMENT;//新容量
    }
    
    for(j=L->length;j>i-1;j--)//从后往前覆盖
        L->elem[j] = L->elem[j-1];
    L->elem[i-1] = e;//在留出的位置赋值
    L->length++;//长度+1
    return OK;
}

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int j;
    if(i<1 || i>L->length)//非法输入/表空
        return ERROR;
    *e = L->elem[i-1];//为了返回值
    for(j = i-1;j <= L->length;j++)//从前往后覆盖
        L->elem[j] = L->elem[j+1];
    (L->length)--;//长度减1
    return OK;//返回删除值
}

void ListPrint(SqList L)
{
    int i;
    for(i=0;i<L.length;i++)
        printf("%d ",L.elem[i]);
    printf("\n");//为了美观
}

void DeleteMin(SqList *L)
{
    //表空在Listdelete函数里判断
    int i;
    int j=0;//最小值下标
    ElemType *e;
    for(i=0;i<L->length;i++)//寻找最小
    {
        if(L->elem[i] < L->elem[j])
            j=i;
    }
    ListDelete(L,j+1,&e);//调用删除，注意j要+1
}

int main(void)
{
	SqList L;
	int i;
	ElemType e;
	ElemType data[9] = {11,-22,-33,3,-88,21,77,0,-9};
	InitList(&L);
	for (i = 1; i <= 9; i++)
	{
		ListInsert(&L,i,data[i-1]);
	}
	printf("插入完成后 L = : ");
	ListPrint(L);
    ListDelete(&L, 2, &e);
	printf("删除第 2 个后L = : ");
	ListPrint(L);
    DeleteMin(&L);
	printf("删除L中最小值后L = : ");
	ListPrint(L);
	DeleteMin(&L);
	printf("删除L中最小值后L = : ");
	ListPrint(L);
	DeleteMin(&L);
	printf("删除L中最小值后L = : ");
	ListPrint(L);
}

单链表不带头标准c语言实现

?

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

?

下面给出不带头的单链表标准实现：

定义节点：

typedef struct node 
{ 
    int data;
    struct node * next;
}Node;

尾插：

void pushBackList(Node ** list, int data) 
{ 
    Node * head = *list;
    Node * newNode = (Node *)malloc(sizeof(Node));//申请空间
    newNode->data = data; newNode->next = NULL;
    if(*list == NULL)//为空
        *list = newNode;
    else//非空
    {
        while(head ->next != NULL)
            head = head->next;
        head->next = newNode;
    }
}

插入：

int insertList(Node ** list, int index, int data) 
{
    int n;
    int size = sizeList(*list); 
    Node * head = *list; 
    Node * newNode, * temp;
    if(index<0 || index>size) return 0;//非法
    newNode = (Node *)malloc(sizeof(Node)); //创建新节点
    newNode->data = data; 
    newNode->next = NULL;
    if(index == 0) //头插
    {
        newNode->next = head; 
        *list = newNode; 
        return 1; 
    }
    for(n=1; n<index; n++) //非头插
        head = head->next;
    if(index != size) 
        newNode->next = head->next; 
    //链表尾部next不需指定
    head->next = newNode; 
    return 1;
}