数据结构与算法01

demo模板
demo模板
demo模板
下面more是分隔符

算法复杂度

时间复杂度——大O标记法

1. 用常数1取代运行中的所有加法常数。
2. 在修改后的运行次数函数中，只保留最高阶项。
3. 如果最高阶项存在，且不是1，则除去其常系数，得到的结果就是大O阶。

// 程序段的执行次数为1+n+1,
// f(n) = n+2, T(n) = O(n)
// 算法的时间复杂度为 O(n)
void func(){
    int i, n = 100, sum = 0; // 执行一次
    for (i = 0; i <= n; i++) {
        sum += i; // 执行 n 次
    }
    printf("%d \n", sum); // 执行一次
}

#时间复杂度 demo: 
(1) x=x+1;  时间复杂度为O(1),称为常量阶
(2) for( i=1,i<=n,i++ ) x=x+1;  时间复杂度为O(n),称为线性阶
(3) for (int i = 0; i <=n; i++)
     for (int j = 0; j <= n; j++)
        x = x + 1;   时间复杂度为O(n^2),成为平方阶

简单的链表

demo,创建链表, 输出链表, 删除链表

//需要引入的文件
#include<stdio.h>
#include<malloc.h>
void Chinese(){ // tip:哪里需要中文可以调用
    system("chcp 65001"); // process.h 这个库解决中文乱码
}

// tip: 这里尽量使用 int 类型写demo, char 类型需要处理回车换行
struct book { // 结构体类型
    int num; // 图书编号
    int price; //  图书价格
    struct book *next; // 记录位置
};

// 创建链表
struct book *creat(int n) {
    struct book *head, *p1, *p2;
    head = p2 = (struct book *) malloc(sizeof(struct book));
    for (int i = 0; i < n; i++) {
        p1 = (struct book *) malloc(sizeof(struct book));
        printf("请输入图书名字、价格,以空格分隔: \n");
        scanf("%d%d", &p1->num, &p1->price);

        p2->next = p1;
        p2 = p1;
    }
    p1->next = NULL;

    return head;
}

// 输出链表
void printBook(struct book *head) {
    struct book *p = head->next;

    do {
        printf("书名:%d, 价格:%d \r\n", p->num, p->price);
        p = p->next;
    } while (p != NULL);

    printf("************************ \n");
}

// 删除链表中一个元素
void deleteBook(struct book *head1, int num) {
    struct book *p = head1->next, *q = head1;
    while (p->next != NULL) {
        if (p->num == num) {
            q->next = p->next;
            break;
        }
        q = q->next;
        p = p->next;
    }
}

int main() {
    Chinese();

    struct book *head;
    // 调用函数建立链表
    head = creat(3);

    // 调用函数输出链表
    printBook(head);

    // 删除链表中num编号为111
    deleteBook(head, 111);
    printBook(head);

    return 0;
}

底部

没有了