头像

codehorse

$\color{pink}{\Huge{y总粉丝团}}$




离线:5天前


最近来访(75)
用户头像
白茶坔乌龙
用户头像
acwing_0842
用户头像
AcWingYyyyyy
用户头像
+10
用户头像
不高兴就做题
用户头像
nickxiao
用户头像
fduytfkuhj
用户头像
mattqqq
用户头像
xiaoshui
用户头像
WA_1
用户头像
795
用户头像
我是好人
用户头像
2022fjq
用户头像
itdef
用户头像
v_viggins
用户头像
小松鼠1996
用户头像
夜寐
用户头像
用户头像
GLFV
用户头像
zyitst


线性结构

顺序表

/*
    malloc(m)函数:开辟m字节长度的地址空间,并返回这段空间的首地址
    sizeof(x)函数:计算变量x的长度
    free(*p)函数:释放指针p所指变量的存储空间,即彻底删除一个变量
*/
#include <stdio.h>
#include <stdlib.h>

//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define MAX_SIZE 1000  //顺序表初始长度
typedef int Status; //Status 是函数的类型,其值是函数结果状态代码
typedef int ElemType; //ElemType 是元素类型

//顺序表存储结构(静态数组实现)
// typedef struct {
//     ElemType e[MAX_SIZE];     //数据
//     int length; //当前长度
// } SqList;

//顺序表存储结构(动态数组实现)
typedef struct {
    ElemType *e;     //元素数据
    int length; //当前长度
} SqList;

//初始化顺序表
Status initList(SqList *list) {
    list->e = (ElemType*)malloc(sizeof(ElemType) * MAX_SIZE);
    if (!list->e) {
        printf("分配内存失败\n");
        exit(OVERFLOW);
    }
    list->length = 0;
    printf("初始化顺序表成功\n");
    return OK;
}

//销毁顺序表
void distroyList(SqList *list) {
    if (list->e) {
        free(list->e);     //free释放指针指向的空间
        printf("销毁成功\n");
    }
}

//清空顺序表,顺序表将从头开始存储(覆盖),但并不销毁原有空间
void clearList(SqList *list) {
    list->length = 0;       //长度重置为0
    printf("清空成功\n");
}

//求顺序表长度
int getLength(SqList *list) {
    return list->length;
}

//判断顺序表是否为空
bool isEmpty(SqList *list) {
    return list->length ? 0 : 1;        //1为空,0为不空
}

//获取第k个元素,平均时间复杂度:O(1)
int getElem(SqList *list, int k) {
    if (k < 1 || k > list->length) return ERROR;

    return list->e[k - 1];  //第k - 1个单元存储着第k个数据
}

//查找元素x, 平均时间复杂度:O(n)
int locateElem(SqList *list, ElemType x) {
    for(int i = 0; i < list->length; i ++ )
        if (list->e[i] == x) return i + 1;     //查找成功,返回序号
    return 0;   //查找失败
}


//在第k个位置插入元素, 平均时间复杂度:O(n)
Status insertElem(SqList *list, int k, ElemType x) {
    // n + 1的位置是可以插入的,为最后的位置
    if (k < 1 || k > list->length + 1 || list->length == MAX_SIZE) return ERROR;
    for (int i = list->length - 1; i >= k - 1; i -- ) {
        list->e[i + 1] = list->e[i];
    }
    list->e[k - 1] = x;
    list->length ++ ;
    printf("[%d]=%d,插入成功\n", k - 1, x);
    return OK;
}

//删除第k个位置的元素, 平均时间复杂度:O(n)
Status delElem(SqList *list, int k) {
    if (k < 1 || k > list->length) return ERROR;
    for (int i = k - 1; i < list->length; i ++ )
        list->e[i] = list->e[i + 1];
    list->length --;
    return OK;
}

int main() {
    SqList list;

    initList(&list);
    insertElem(&list, 1, 520);
    insertElem(&list, 2, 1314);
    delElem(&list, 1);
    printf("顺序表第1个元素:%d\n", getElem(&list, 1));
    printf("顺序表长度为:%d\n", getLength(&list));
    printf("顺序表是否为空(1为空,0为不空):%d\n", isEmpty(&list));
    printf("查找元素1314的位置:%d\n", locateElem(&list, 1314));

    clearList(&list);
    distroyList(&list);
    return 0;
}

单链表

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

typedef int E;

//单链表存储结构
typedef struct Node {
    E data;
    struct Node *next;
}Node, *LinkList;

//初始化结点,并返回结点地址
LinkList init(int x = 0) {
    LinkList node = (LinkList)malloc(sizeof(Node));
    node->next = NULL;
    node->data = x;
}

//在第k个位置插入数据x
void insert(LinkList l, int k, E x) {
    LinkList p = l;
    int j = 0;
    while (p && j < k - 1) p = p->next, j ++ ;
    if (!p || j != k - 1) return;
    LinkList q = init(x);
    q->next = p->next;
    p->next = q;
}

//查找第k个元素, 找不到则返回-1
E getK(LinkList l, int k) {
    int j = 0;
    LinkList p = l->next;
    while (p && j < k - 1) p = p->next, j ++ ;
    if (!p || j != k - 1) return -1;
    return p->data;
}

//按值查找, 查找值为x的位置,返回结点地址
LinkList locateE(LinkList l, E x) {
    LinkList p = l->next;
    while (p && x != p->data) p = p->next;
    if (!p || x != p->data) return NULL;
    return p;
}

//删除第k个元素
void delK(LinkList l, int k) {
    LinkList p = l;
    int j = 0;  //从头结点开始
    while (p->next && j < k - 1) p = p->next, j ++ ;   //走到k - 1的位置上
    if (!(p->next) || j != k - 1) return ;
    p->next = p->next->next;
}

//生成数据
void randomData(LinkList l) {
    for (int i = 1; i <= 100; i ++ ) {
        insert(l, i, i);
    }
}
//遍历链表,输出链表
void printList(LinkList l) {
    int i = 0;
    while (l) {
        // if (i == 1) printf("(0x%X)", l);    //测试按值查找的地址
        printf("%d->", l->data);
        l = l->next;
        i ++ ;
    }
    printf("NULL\n");
}

int main() {
    LinkList list = init(-1);
    randomData(list); 

    printf("第50个元素:%d\n", getK(list, 50));

    LinkList t = locateE(list, 1);
    printf("链表值为1的地址:0x%X\n", t);

    delK(list, 50);
    printList(list);

    return 0;
}

双链表

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

typedef int E;
typedef struct Node {
    E data;
    struct Node *l;
    struct Node *r;
}Node, *PNode;

//初始化一个结点, 并返回起始地址
PNode init(E x = 0) {
    PNode t = (PNode)malloc(sizeof(Node));
    t->data = x;
    t->l = t->r = NULL;
    return t;
}

//输出所有值
void printNode(PNode node) {
    while (node) {
        printf("%d->", node->data);
        node = node->r;
    }
    printf("NULL\n");
}

//插入操作, 第k个位置前插入x
void insert(PNode node, int k, E x) {
    PNode p = node;
    int j = 0;
    while (p && j < k - 1) p = p->r, j ++ ;
    // printf("j=%d, k=%d\n", j, k - 1);
    // printNode(node);
    if (!p || j != k - 1) return ;
    PNode t = init(x);

    if(p->r) p->r->l = t;
    t->r = p->r;
    p->r = t;
    t->l = p;
}

//删除第k个位置的元素
void delNode(PNode node, int k) {

    PNode p = node;
    int j = 0;
    while (p && j < k - 1) p = p->r, j ++ ;
    if (!p || j != k - 1) return;

    p->r->l = p;
    p->r = p->r->r;
}

void randomData(PNode node) {
    for (int i = 1; i <= 50; i ++ )
        insert(node, i, i);
}

int main() {
    PNode p = init(-1);
    randomData(p);
    delNode(p, 25);
    insert(p, 25, 5201314);
    printNode(p);
    return 0;
}

顺序栈

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

#define MAXSIZE 100
#define E int

//顺序栈结构体
typedef struct stack {
    E *top;      //栈顶地址
    E *base;     //栈底地址
    int maxsize;        //最大高度
} Stk;

//初始化一个栈
void init(Stk *stk) {
    stk->base = (E*)malloc(sizeof(E) * MAXSIZE);    //(栈低开始)开辟一段连续空间
    if (!stk) printf("分配失败\n");
    stk->top = stk->base;     //栈顶等于栈底
    stk->maxsize = MAXSIZE;
}

//判断栈是否为空
bool empty(Stk stk) {
    return stk.top == stk.base ? true : false;
}

//清空栈
void clear(Stk *stk) {
    stk->top = stk->base;
}

//销毁栈
void destory(Stk *stk) {
    if (stk->base) {
        free(stk->base);
        stk->maxsize = 0;
        stk->base = stk->top = NULL;
    }
}

//入栈
void push(Stk *stk, E e) {
    if (stk->top - stk->base == stk->maxsize) return;   //栈满, 上溢
    *(stk->top) = e;    //入栈
    stk->top ++;        //栈顶后移
}

//获取栈顶元素
E top(Stk stk) {
    if (stk.top == stk.base) return -1;
    return *(stk.top - 1);   
}

//出栈
void pop(Stk *stk) {
    if (stk->top == stk->base) return ;     //栈空, 下溢
    stk->top --;
}

int main() {
    Stk stk;
    init(&stk);
    push(&stk, 1);
    push(&stk, 2);
    pop(&stk);pop(&stk);
    printf("栈顶元素:%d\n", top(stk));

    // printf("%d\n", stk.maxsize);
    // printf("%X\n", stk.top);
    // printf("%X\n", stk.base);
    // printf("%d\n", empty(stk));
    return 0;
}

链栈

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

#define MAXSIZE 100
#define E int

//链栈是运算受限的单链表, 只能在链表头部进行操作
typedef struct stkNode {
    E data;
    struct stkNode *next;
}stkNode, *LinkStk;

//判断链栈是否为空
int empty(LinkStk s) {
    return s == NULL;
}

//入栈
void push(LinkStk *s, E e) {
    stkNode *p = (LinkStk)malloc(sizeof(stkNode));
    p->data = e;
    p->next = *s;
    *s = p;
}

//栈顶元素
E top(LinkStk s) {
    if (s == NULL) return -1;
    return s->data;
}

//出栈
void pop(LinkStk *s) {
    if (*s == NULL) return;
    *s = (*s)->next;
}

int main() {
    LinkStk s = NULL;   //初始化一个链栈, 不需要虚拟头结点
    push(&s, 1);
    push(&s, 2);
    pop(&s);
    printf("栈顶元素:%d\n", top(s));

    return 0;
}

顺序队列(循环队列)

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

#define MAXSIZE 2     //最大队列长度
#define E int   //元素类型

//队列的存储结构
typedef struct {
    E *base;    //队列存储空间
    int front;      //头指针
    int rear;       //尾指针
}SqQueue;

//初始化队列
void init(SqQueue *q) {
    q->base = (SqQueue*)malloc(sizeof(SqQueue) * MAXSIZE);
    if (!q->base) return;
    q->front = q->rear = 0;
}

//队列长度(循环队列), 下表从0开始
int getLength(SqQueue q) {
    return (q.rear - q.front + MAXSIZE) % MAXSIZE;
}

//入队, 尾指针会指向到下一次存储的位置, 注意需要多开一个空间
void push(SqQueue *q, E x) {
    if ((q->rear + 1) % MAXSIZE == q->front) {
        printf("队满\n");
        return;
    }
    q->base[q->rear] = x;
    q->rear = (q->rear + 1) % MAXSIZE;
}

//出队
E pop(SqQueue *q) {
    if (q->front == q->rear) {
        printf("队空\n");
        return;
    }
    E x = q->base[q->front];
    q->front = (q->front + 1) % MAXSIZE;
    return x;
}

//取队头元素
E getHead(SqQueue *q) {
    if (q->front != q->rear) return q->base[q->front];
    return -1;
}

int main() {
    SqQueue q;
    init(&q);
    push(&q, 1);
    // int a = pop(&q); int b = pop(&q);
    // printf("a = %d\n", a);
    push(&q, 2);
    printf("队头元素为: %d\n", getHead(&q));
    printf("长度为:%d\n", getLength(q));
    return 0;
}

链式队列

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

#define MAXSIZE 10
#define E int

//链式队列存储结构
typedef struct Node{
    E data;
    struct Node *next;
}QNode, *PQNode;

//头尾指针结构体
typedef struct {
    PQNode front;       //指向存储结构
    PQNode rear;
}Queue, *LinkQueue;

//初始化链式数列
void init(LinkQueue q) {
    q->front = q->rear = (PQNode)malloc(sizeof(QNode));     //初始化队头队尾
    if (!q->front) return;
    q->front->next = NULL;      //头结点指向空
}

//入队, 操作队尾
void push(LinkQueue q, E x) {
    PQNode t = (PQNode)malloc(sizeof(QNode));
    t->data = x;
    t->next = NULL;
    q->rear->next = t;      //队尾加入元素
    q->rear = t;            //走到队尾
}

//出队, 操作队头
void pop(LinkQueue q) {
    if (q->front == q->rear) return ;       //空队
    PQNode t = q->front->next;       //头指针指向的元素
    q->front->next = t->next;
    if (q->rear == t) q->rear = q->front;   //最后一个元素出队后, 尾指针指向头指针
}

//取出队头元素
E getHead(LinkQueue q) {
    if (q->front != q->rear) 
        return q->front->next->data;
    return -1;
}
int main() {
    LinkQueue q = (LinkQueue)malloc(sizeof(Queue));
    init(q);
    push(q, 1);
    printf("队头:%d\n", getHead(q));
    pop(q);
    push(q, 2);
    printf("队头:%d\n", getHead(q));
    return 0;
}

顺序串


链串


块链串


非线性结构



活动打卡代码 AcWing 18. 重建二叉树

codehorse
15天前

t.png

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorder, inorder;
    unordered_map <int, int> pos;

    TreeNode* build(int a, int b, int x, int y) {
        if (a > b) return NULL;
        auto root = new TreeNode(preorder[a]);
        int k = pos[root->val];
        root->left = build(a + 1, k - 1 - x + a + 1, x, k - 1);
        root->right = build(k - 1 - x + a + 1 + 1, b ,k + 1, y);
        return root;
    }

    TreeNode* buildTree(vector<int>& _preorder, vector<int>& _inorder) {
        preorder = _preorder, inorder = _inorder;
        int n  = inorder.size();
        for (int i = 0; i < n; i ++ ) pos[inorder[i]] = i;

        return build(0, n - 1, 0, n - 1);
    }
};


活动打卡代码 AcWing 3756. 筛选链表

codehorse
2个月前
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 * 
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct ListNode* filterList(struct ListNode* head) {
    bool st[10010]={false};
    st[abs(head->val)] = true;
    for (struct ListNode* p = head; p->next; ) {
        int x = abs(p->next->val);
        if (st[x]) {
            struct ListNode* q = p->next; 
            p->next = q->next;
            free(q);
        }
        else {
            p = p->next;
            st[x] = true;
        }
    }

    return head;
}



codehorse
2个月前

C语言题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *findFirstCommonNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *p = headA, *q = headB;
    while (p != q) {
        p = p ? p->next : headB;
        q = q ? q->next : headA;
    }
    return q;
}


新鲜事 原文

codehorse
3个月前
节日快乐!进货快乐!
图片


活动打卡代码 AcWing 53. 最小的k个数

codehorse
6个月前
class Solution {
    public List<Integer> getLeastNumbers_Solution(int[] input, int k) {
        Queue<Integer> heap = new PriorityQueue<>();
        for (int x : input) {
            heap.add(x);
        }

        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < k; i ++ ) {
            res.add(heap.remove());
        }
        return res;
    }
}



codehorse
6个月前
class Solution {
    public int[] findNumbersWithSum(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            int y = target - x;
            if (set.contains(y)) {
                return new int[]{x, y};
            }
            set.add(x);
        }

        return null;
    }
}


活动打卡代码 AcWing 829. 模拟队列

codehorse
6个月前
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        Queue<Integer> que = new LinkedList<>();
        while (m -- > 0) {
            String op = sc.next();
            if ("push".equals(op)) {
                int x = sc.nextInt();
                que.add(x);
            } else if ("pop".equals(op)) {
                que.remove();
            } else if ("query".equals(op)) {
                System.out.println(que.peek());
            } else {
                System.out.println(que.isEmpty() ? "YES" : "NO");
            }
        }
    }
}


活动打卡代码 AcWing 828. 模拟栈

codehorse
6个月前
import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        Stack<Integer> stk = new Stack<>();
        for (int i = 0; i < m; i ++ ) {
            String op = sc.next();

            if ("push".equals(op)) {
                Integer x = sc.nextInt();
                 stk.push(x); 
            } else if ("pop".equals(op)) {
                stk.pop();
            } else if ("query".equals(op)) {
                System.out.println(stk.peek());
            } else {
                System.out.println(stk.empty() ? "YES" : "NO");
            }
        }
    }
}


活动打卡代码 AcWing 862. 三元组排序

codehorse
6个月前
import java.util.Scanner;
import java.util.Arrays;

class Data implements Comparable<Data> {
    int x;
    double y;
    String z;

    public Data(int x, double y, String z) {
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public int compareTo(Data t) {
        return this.x - t.x;
    }

}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Data[] datas = new Data[n];
        for (int i = 0; i < n; i ++ ) {
            int x = sc.nextInt();
            double y = sc.nextDouble();
            String z = sc.next();
            datas[i] = new Data(x, y, z);
        }

        Arrays.sort(datas);
        for (int i = 0; i < n; i ++ ) {
            System.out.printf("%d %.2f %s\n", datas[i].x, datas[i].y, datas[i].z);
        }
    }
}