Data Structures and Algorithms 分类

【数据结构】串的普通的模式匹配算法（BF 算法）

#include<bits/stdc++.h>

using namespace std;

int BF(string S, string T);

int BF(string S, string T, int pos);

int BF(string S, string T) {
    return BF(S, T, 0);
}

/***
 * BF即暴力(Brute Force)算法 算法的实现过程很 "无脑",不包含任何技巧,在对数据量大的串进行模式匹配时,算法的效率很低。
 * 其实,BF 算法还可以改进,就是 KMP 算法
 * @param S 主串
 * @param T 子串
 * @param pos 从第几个字符之后开始匹配
 * @return 字串T在主串S中第pos个字符之后的位置
 */
int BF(string S, string T, int pos) {
    int lenA = S.length();
    int lenB = T.length();
    int i = pos;
    int j = 0;
    while (i < lenA && j < lenB) {
        if (S[i] == T[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= lenB) {
        return i - lenB;
    }
    // 找不到返回-1
    return -1;
}

int main() {
    string a, b;
    cin >> a >> b;
    printf("%d\n", BF(a, b, 3));
    return 0;
}

【数据结构】顺序表的链式存储结构（单链表，C 语言版）

#include <stdio.h>
#include <stdlib.h>

#define OK 0
#define ERROR -1

typedef int ElemType;
// 线性表的链式存储结构（单链表）
typedef struct LNode {
    // 数据域
    ElemType data;
    // 指针域
    LNode *next;
} *LinkList;

// 头插法创建单链表
int create1(LinkList &L, int n);

// 尾插法创建单链表
int create2(LinkList &L, int n);

// 求单链表长度
int length(LinkList &L);

// 取元素
int get(LinkList &L, int i);

// 插入结点
int insert(LinkList &L, int i, ElemType e);

// 删除结点，返回删除元素
ElemType remove(LinkList &L, int i);

// 遍历链表
int display(LinkList &L);

// 销毁链表
int destroy(LinkList &L);

// 清空链表
int clear(LinkList &L);

// 逆置链表
void reverse_list(LNode *p, LinkList &L);

// 判断链表是否为空
int isNull(LinkList &L);

// 判断链表是否为空链表
int isEmpty(LinkList &L);

// 头插法，从表尾到表头逆向建立单链表L，每次均在头结点之后插入元素
int create1(LinkList &L, int n) {
    L = (LinkList) malloc(sizeof(LNode));// 建立带头结点的的单链表L
    L->next = NULL;// 初始为空链表

    // p为新结点，指向最后一个元素
    LNode *p;

    for (int i = 1; i <= n; i++) {
        // 生成新结点
        p = (LinkList) malloc(sizeof(LNode));
        p->data = i;
        p->next = L->next;
        L->next = p;
    }

    return OK;
}

// 尾插法，从表头到表尾正向建立单链表L,每次均在表尾插入元素
int create2(LinkList &L, int n) {
    L = (LinkList) malloc(sizeof(LNode));// 创建头结点
    L->next = NULL;

    LNode *p, *q = L;

    for (int i = 1; i <= n; i++) {
        // 生成新结点
        p = (LinkList) malloc(sizeof(LinkList));
        p->data = i;
        p->next = NULL;// 不写报错
        q->next = p;// 将头节点和新和新创建的结点链接起来
        q = p;// q指向新的表尾结点（指针右移）
        // or q  = q->next;// q指向新的表尾结点
    }

    return OK;
}

ElemType get(LinkList &L, int i) {
    // p指向L的首结点
    LNode *p = L->next;
    int j = 0;

    // 顺指针向后查找，直到p为空（说明p已指向最后一个结点了）或p指向第i个元素
    while (p && j < i) {
        p = p->next;
        j++;
    }

    if (!p || j > i) {
        return ERROR;
    }

    return p->data;
}

int insert(LinkList &L, int i, ElemType e) {
    LNode *temp = L;// 创建临时结点，用于寻找第i-1个结点

    int j;
    // 首先找到插入位置的上一个结点,即temp指向的结点
    for (j = 0; temp && j < i; j++) {
        temp = temp->next;
    }

    if (!temp || j > i) {
        return ERROR;
    }

    LNode *p = (LinkList) malloc(sizeof(LinkList));// 生成新结点（待插入的结点）
    p->data = e;// 给新结点的数据域赋值
    p->next = temp->next;// 将新结点的next指针指向插入位置后的结点
    temp->next = p;// 将插入位置前的结点的next指针指向插入结点

    return OK;
}

ElemType remove(LinkList &L, int i) {
    LNode *temp = L;

    int j;
    // 寻找第i个结点，temp指向其前趋
    for (j = 0; temp && j < i; j++) {
        temp = temp->next;
    }

    if (!temp->next || j > i) {
        return ERROR;
    }

    LNode *del = temp->next;// 单独设置一个指针指向被删除结点，以防丢失
    ElemType e = del->data;// 存储待删除结点的数据，作为返回值

    temp->next = del->next;// 删除某个结点的方法就是更改前一个结点的指针域
    free(del);// 手动释放该结点，防止内存泄漏

    return e;
}

int length(LinkList &L) {
    // 判断链表是否为空
    if (isNull(L)) {
        return ERROR;
    }

    LNode *p = L->next;
    int len = 0;

    while (p != NULL) {
        len++;
        p = p->next;
    }

    return len;
}

int display(LinkList &L) {
    // 判断链表是否为空
    if (isNull(L)) {
        return ERROR;
    }

    // 判断链表是否为空链表
    if (isEmpty(L)) {
        return ERROR;
    }

    // p指向首结点
    LNode *p = L->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

int destroy(LinkList &L) {
    LNode *temp;
    while (L) {
        temp = L->next;
        free(L);
        L = temp;
    }
    return OK;
}

int clear(LinkList &L) {
    LNode *temp = L->next, *p;
    while (temp) {
        p = temp->next;
        free(temp);
        temp = p;
    }

    L->next = NULL;
}

void reverse_list(LNode *p, LinkList &L) {
    if (p->next == NULL) {// 以p为首结点指针的单链表只有一个结点时
        L->next = p; // p结点变为尾结点
        return;
    }

    reverse_list(p->next, L);
    p->next->next = p; // 将结点链接在尾结点之后
    p->next = NULL; // 尾结点next域置为NULL
}

int isNull(LinkList &L) {
    // 不存在头节点，链表不存在（未创建或已被销毁）
    if (!L) {
        printf("linklist is null!\n");
        return ERROR;
    }
    return OK;
}

int isEmpty(LinkList &L) {
    // 不存在首元节点，是空链表
    if (!L->next) {
        printf("linklist is empty!\n");
        return ERROR;
    }
    return OK;
}

int main() {

    LinkList linkList;
    create2(linkList, 5);
    display(linkList);

    // 插入元素
    insert(linkList, 5, 666);
    display(linkList);

    printf("length:%d\n", length(linkList));
    printf("%d\n", get(linkList, 4));

    printf("%d\n", remove(linkList, 5));
    display(linkList);

    reverse_list(linkList->next, linkList);
    display(linkList);

    clear(linkList);
    display(linkList);
    printf("length:%d\n", length(linkList));

    destroy(linkList);

    printf("length:%d\n", length(linkList));
    //display(linkList);

    return 0;
}

【数据结构】栈的顺序存储结构（C 语言版）

#include <stdio.h>
#include <stdlib.h>

// 初始长度
#define STACK_INIT_SIZE 10
// 扩容量
#define STACK_INCREMENT 100

typedef int ElemType;
// 栈的顺序存储结构
typedef struct {
    // 栈顶指针
    ElemType *top;
    // 栈底指针
    ElemType *base;
    // 栈长
    int stackSize;
} Stack;

// 创建栈
int initStack(Stack &S);
// 判断栈是否为空
int isEmpty(Stack &S);
// 栈扩容
int grow(Stack &S);
// 入栈
int push(Stack &S, ElemType e);
// 出栈
int pop(Stack &S);
// 求栈长
int length(Stack &S);
// 清空栈
int clear(Stack &S);

int initStack(Stack &S) {
    S.base = (ElemType *) malloc(STACK_INIT_SIZE * sizeof(ElemType));

    if (!S.base)return -1;

    S.top = S.base;
    S.stackSize = STACK_INIT_SIZE;

    return 0;
}

int isEmpty(Stack &S) {
    if (S.base == S.top) {
        printf("stack is empty");
        exit(-1);
    }

    return 0;
}

int grow(Stack &S) {
    if (S.top - S.base >= S.stackSize) {
        // 重新分配存储空间
        S.base = (ElemType *) realloc(S.base, (S.stackSize + STACK_INCREMENT) * sizeof(ElemType));
        if (!S.base)return -1;

        S.top = S.base + S.stackSize;
        S.stackSize += STACK_INCREMENT;
    }

    return 0;
}

int push(Stack &S, ElemType e) {
    grow(S);
    // e赋值给栈顶指针所指的空间，然后指针上移一位
    *S.top++ = e;

    return 0;
}

ElemType pop(Stack &S) {
    isEmpty(S);
    // 栈顶指针是指向最后一个入栈的元素的后一位
    return *--S.top;
}

int length(Stack &S) {
    int len = 0;
    ElemType *temp = S.top;

    while (temp != S.base) {
        len++;
        temp--;
    }

    return len;
}

int clear(Stack &S) {
    while (S.top != S.base) {
        *--S.top = NULL;
    }

    return 0;
}


int main() {

    Stack S;
    // 创建栈
    initStack(S);

    printf("When there is no element on the stack, the stack length is:%d\n", length(S));

    // 10个元素入栈
    for (int i = 0; i < 10; ++i) {
        push(S, i + 1);
    }

    printf("After 10 elements are put on the stack, the stack length is:%d\n", length(S));

    // 10个元素出栈
    for (int i = 0; i < 10; ++i) {
        printf("%d ", pop(S));
        if(i == 9)printf("\n");
    }

    printf("After 10 elements are popped out of the stack, the stack length is:%d\n", length(S));

    // 清空栈
    clear(S);
    printf("After clearing the stack, the stack length is:%d\n", length(S));

    push(S, 419);
    printf("%d\n", pop(S));

    return 0;
}

【数据结构】线性表的顺序存储结构（C 语言版）

#include <stdio.h>
#include <stdlib.h>

#define OK 0
#define ERROR -1
// 分配存储空间的初始长度
#define LIST_INIT_SIZE 10

typedef int ElemType;

// 线性表的顺序存储结构
typedef struct {
    // 存储空间基址
    ElemType *elem;
    // 当前长度
    int length;
    // 当前分配的存储容量
    int listSize;
} List;

// 创建线性表
int create(List &L);

// 扩容
int grow(List &L);

// 查找元素，返回首次出现的下标，找不到返回-1
int get(List &L, ElemType e);

// 添加元素
int add(List &L, ElemType e);

// 在指定位置插入元素
int insert(List &L, int i, ElemType e);

// 删除指定位置的元素，并返回
ElemType remove(List &L, int i);

// 打印线性表
int display(List &L);

// 清空线性表
int clear(List &L);

// 销毁线性表
int destroy(List &L);

int create(List &L) {
    L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));

    // 存储空间分配失败
    if (!L.elem)return ERROR;

    L.length = 0;
    L.listSize = LIST_INIT_SIZE;

    return OK;
}

int grow(List &L) {
    if (L.length >= L.listSize) {
        // 扩容机制仿照 Java的ArrayList，为原大小的1.5倍，>>1 表示除以2的1次方
        ElemType *newBase = (ElemType *) realloc(L.elem, (L.listSize + (L.listSize >> 1)) * sizeof(ElemType));
        if (!newBase)return ERROR;
        L.elem = newBase;
        L.listSize += L.listSize >> 1;
    }

    return OK;
}

int get(List &L, ElemType e) {
    for (int i = 0; i < L.length; ++i) {
        if (L.elem[i] == e)return i;
    }

    return ERROR;
}

int add(List &L, ElemType e) {
    grow(L);
    L.elem[L.length++] = e;

    return OK;
}

int insert(List &L, int i, ElemType e) {
    if (i < 0 || i > L.length)return ERROR;
    grow(L);

    // p指向待插入位置，q指向最后一个元素
    ElemType *p = &L.elem[i], *q = &L.elem[L.length - 1];
    while (q >= p) {
        *(q + 1) = *q;
        q--;
    }

    *p = e;
    L.length++;

    return OK;
}

ElemType remove(List &L, int i) {
    if (i < 0 || i > L.length)return ERROR;

    // p指向待删除位置
    ElemType *p = &L.elem[i];
    // q指向最后一个元素
    ElemType *q = &L.elem[L.length - 1];
    ElemType del = *p;
    p++;

    while (p <= q) {
        *(p - 1) = *p;
        p++;
    }
    L.length--;

    // 最后一个元素并没有删除，由于length的限制没有打印出来，这句写不写无所谓，因为已经开辟了这一块的存储空间
    //L.elem[L.length] = NULL;

    return del;
}

int display(List &L) {
    if (L.elem == NULL || L.length == 0) {
        printf("[]\n");
        return ERROR;
    }

    printf("[");
    for (int i = 0; i < L.length - 1; i++) {
        printf("%d,", L.elem[i]);
    }
    // 最后一个元素单独打印，目的是让最后一个逗号不打印
    printf("%d]\n", L.elem[L.length - 1]);

    return OK;
}

int clear(List &L) {
    ElemType *temp = L.elem;

    // 将每一个元素设为NULL
    for (int i = 0; i < L.length; ++i) {
        *L.elem = NULL;
        L.elem++;
    }

    L.length = 0;
    L.elem = temp;

    return OK;
}

int destroy(List &L) {
    free(L.elem);
    L.elem = NULL;
    L.length = 0;
    L.listSize = 0;

    return OK;
}


int main() {
    List list;
    create(list);

    // 添加10个元素
    for (int i = 0; i < 5; ++i) {
        add(list, (i + 1) * 10);
    }

    printf("%d\n", list.length);
    display(list);

    insert(list, 3, 123);
    display(list);


    // 移除下标为0的元素，并返回
    printf("%d\n", remove(list, 0));
    display(list);
    printf("%d\n", list.elem[4]);

    printf("%d\n", get(list, 123));


    clear(list);
    display(list);

    add(list, 223);
    add(list, 233);
    add(list, 2233);

    display(list);
    printf("%d\n", list.length);

    destroy(list);
    printf("%d\n", list.length);
    display(list);


    return 0;
}