bug记录

数据结构

线性表

顺序表

//
// Created by Administrator on 2022/10/7.
// 描述顺序线性表这种常用的数据结构
//

#include <stdio.h>

#define MAXSIZE 100
#define ElemType int
#define OK 1
#define ERROR 0

typedef int Status;

// 定义一个存储整形int的顺序表，最大长度为100，实际长度为length
typedef struct {
    ElemType data[MAXSIZE];
    int length;
} SqList;

// 初始化线性表
int initSqList(SqList *L, ElemType a[], int n) {
    if (n > MAXSIZE) {
        printf("failed!");
        return ERROR;
    }
    for (int i = 0; i < n; i++)
        L->data[i] = a[i];
    L->length = n;
    return OK;
}

// 获取元素
// 获取L的第i个元素，并用e返回值
Status GetElem(SqList L, int i, ElemType *e) {
    if (L.length == 0 || i < 1 || i > L.length)
        return ERROR;
    *e = L.data[i - 1];
    return OK;
}

// 插入元素
// 在L的第i个位置，插入元素e，L长度加一
Status InsertElem(SqList *L, int i, ElemType e) {
    int k;
    if (L->length == MAXSIZE)
        return ERROR;
    if (i < 1 || i > L->length + 1)
        return ERROR;
    if (i <= L->length) {
        for (k = L->length - 1; k >= i - 1; k--)
            L->data[k + 1] = L->data[k];
    }
    L->data[i - 1] = e;
    L->length++;
    return OK;
}

// 打印线性表
void PrintElem(SqList *L) {
    for (int i = 0; i < L->length; i++) {
        printf("%d\t", L->data[i]);
    }
    printf("\n");
}

// 删除元素
// 删除L的第i个元素，并且e返回值，L的长度减1
Status DeleteElem(SqList *L, int i, ElemType *e) {
    int k;
    if (L->length == 0) {
        return ERROR;
    }
    if (i > L->length || i < 1) {
        return ERROR;
    }
    *e = L->data[i - 1];
    if (i < L->length) {
        for (k = i; k < L->length; k++) {
            L->data[k - 1] = L->data[k];
        }
    }
    L->length--;
    return OK;
}

// 修改元素
// 修改L的第i个元素为e
Status UpdateElem(SqList *L, int i, ElemType e) {
    if (L->length == 0)
        return ERROR;
    if (i > L->length || i < 1)
        return ERROR;
    L->data[i - 1] = e;
    return OK;

}

int main() {
    SqList L;
    ElemType e;
    int data[] = {1, 10, 2, 3, 1, 5};
    initSqList(&L, data, 6);
    PrintElem(&L);
    GetElem(L, 3, &e);
    printf("获取到了元素：%d\n", e);
    InsertElem(&L, 5, 10);
    PrintElem(&L);
    DeleteElem(&L, 1, &e);
    printf("删除了元素：%d\n", e);
    PrintElem(&L);
    UpdateElem(&L,2,100);
    PrintElem(&L);
}

单链表

//
// Created by Administrator on 2022/10/9.
//
#include <stdio.h>
#include <malloc.h>

#define OK 1
#define ERROR 0

typedef int DataType;
typedef int Status;

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

// 初始化链表
Node *InitList() {
    Node *first = (Node *) malloc(sizeof(Node));
    first->next = NULL;
    return first;
}

// 输出链表
void PrintNode(Node *first) {
    Node *p = first->next;
    printf("Node:");
    while (p != NULL) {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("\n");
}

// 求链表长度
int length(Node *first) {
    Node *p = first->next;
    int count = 0;
    while (p != NULL) {
        p = p->next;
        count++;
    }
    return count;
}

// 头插法建立单链表
Node *CreateList_head(DataType a[], int n) {
    Node *s = NULL;
    Node *first = (Node *) malloc(sizeof(Node));
    first->next = NULL; // 初始化头结点
    for (int i = 0; i < n; i++) {
        s = (Node *) malloc(sizeof(Node)); // 申请内存
        s->data = a[i];
        s->next = first->next; // 将结点s插入头结点之后
        first->next = s;
    }
    return first;
}

// 尾插法建立单链表
Node *CreateList_end(DataType a[], int n) {
    Node *s = NULL;
    Node *r = NULL;
    Node *first = (Node *) malloc(sizeof(Node)); // 生成头结点
    r = first; // 尾指针初始化
    for (int i = 0; i < n; i++) {
        s = (Node *) malloc(sizeof(Node));
        s->data = a[i];
        r->next = s; // 将结点s插到尾指针之后
        r = s;
    }
    r->next = NULL; // 单链表建立完毕，将尾指针指针域置空
    return first;
}

// 插入元素
Status Insert(Node *first, int i, DataType x) {
    Node *s = NULL;
    Node *p = first; // 指针初始化，指向头结点
    int count = 0;
    while (p != NULL && count < i) { // 查找第i-1个节点
        p = p->next;
        count++;
    }
    if (p == NULL) {
        printf("error location cannot insert!\n");\
        return 0;
    } else {
        s = (Node *) malloc(sizeof(Node)); // 创建一个新节点
        s->data = x;
        s->next = p->next; // 将结点插入到p之后
        p->next = s;
        return OK;
    }
}

// 删除元素
Status Delete(Node *first, int i, DataType *ptr) {
    Node *p = first; // 指针指向头结点
    Node *q = NULL;
    int count = 0;
    while (p != NULL && count < i - 1) { // 查找第i-1个节点
        p = p->next;
        count++;
    }
    if (p == NULL || p->next == NULL) { // p节点或者p的后置节点不存在
        printf("ERROR location!");
    } else { // 找到i节点并删除，通过指针*ptr返回删除后的数据
        q = p->next;
        *ptr = q->data;
        p->next = q->next;
        free(q);
        return OK;
    }
}

// 删除单链表
Status Destory(Node *first) {
    Node *p = first;
    while (p != NULL) {
        first = first->next;
        free(p);
        p = first;
    }
}

// 判断链表是否为空
Status isEmpty(Node *first) {
    if (first->next == NULL) {
        return OK;
    } else {
        return ERROR;
    }
}

// 按值查找位置
int locate(Node *first, DataType x) {
    Node *p = first->next;
    int count = 1;
    while (p != NULL) {
        if (p->data == x) {
            return count;
        }
        p = p->next;
        count++;
    }
    return 0;
}

// 按照位置查找
int Get(Node *first, int i, DataType *ptr) {
    Node *p = first->next;
    int count = 1;
    while (p != NULL && count < i) {
        p = p->next;
        count++;
    }
    if (p == NULL) {
        printf("error location!");
    } else {
        *ptr = p->data;
        return OK;
    }
}

int main() {
    DataType x;
    int data[5] = {1, 2, 3, 4, 5};
    Node *first = CreateList_head(data, 5);
    Node *last = CreateList_end(data, 5);
    PrintNode(first);
    printf("链表的长度为：%d\n", length(first));
    PrintNode(last);
    printf("链表的长度为：%d\n", length(last));
    Insert(first, 1, 10);
    PrintNode(first);
    Delete(first, 3, &x);
    PrintNode(first);
    return 0;
}

循环链表

双向链表

队列

栈

二叉树

堆