C语言学习

结构体

结构体是用于存储数据的一个集合，支持不同的数据类型。
下面定义一个结构体

#include<stdio.h>
#include<string.h>

tptedef struct data {                       //定义一个全局结构体，类似我们定义了一个变量类型，data为结构体名
    char name[10];
    int age;
    char from[10];
} data;                 //这里我们用typedef定义别名为data，在C语言中，如果不定义别名，在引用结构体时要加struct关键字。

struct data2{                      //结构体名可以省略
    char name[10];
    int age;
    char from[10];
} b1 = { "张三",20,"China" },b2;   //定义结构体并定义变量，且同时赋值

struct data3 {                       //定义一个复合结构体e.a.name可以实现内部结构体的成员访问
    char name[10];
    int age;
    char from[10];
    struct family {
        char name[10];
        int age;
        char from[10];
    } a,b,c,d;
} e,f,g;


typedef data2 dat2;                //我们可以用typedef对已有的变量类型名进行重定义

int struset(D4 input);

int strusetchange(D4* p);

int main(){
    dat2 d1, d2; //用我们重定义的类型定义结构体变量
    
    printf("%x",b1);    //实际上结构体变量存储的是一个指针,指向结构体变量中数据的开始位置


    printf("\n");
    struct data c1, c2, c3;//类似变量类型，我们使用结构体需要定义变量，然后再进行赋值等操作
    c1 = { "jntm",22,"China" };


    struct data a2 = { "马牛逼",22,"China" };   //这种方法可以理解为定义的时候就赋值，类型后面跟一个结构体变量名
    data a1 = {"张三",20,"China"};    //这种赋值方法要先定义data这个结构体，然后就把data当变量类型使用去定义变量就行
    

    data list[3] = {c1, a1,a2 };     //这里是我们把每个结构体变量的指针放入一个数组中，以便我们调用。
    for (int i = 0; i < 3; i++) {
        printf("姓名:%s\n年龄:%d\n国家:%s\n", list[i].name, list[i].age, list[i].from);  //list[i].name类似于指针的解引用
    }
    
    
    strcpy(d2.name, "老六");  //对于结构体内的字符串，或者说是定义后的字符串数组d2.name = "老六";这样的赋值是不允许的，可以用strcpy()实现
    
    printf("\n");

    printf("姓名:%s\n年龄:%d\n国家:%s", b1.name, b1.age, b1.from);
    printf("\n");

    data3 e = { ...{...} }; //可以用二维数组的形式定义一个嵌套的
    return 0;
}

int struset(D4 input) {       //在函数中调用结构体就把结构体名当变量类型定义变量就行
    input.age = 18;
    return 0;
}

int strusetchange(D4* p) {       //在函数中调用结构体就把结构体名当变量类型定义指针变量就行
    (*p).age = 18;           //如果我们要更改原数据我们要定义为指针,且在修改时解引用记得用括号括起来
    return 0;
}

链表

链表是一种用于存储不同信息的数据结构，根据结构特点可分为单向链表、双向链表和循环链表等类型。其中，单向链表是最基本的形式，每个节点包含数据和指向下一个节点的指针；双向链表则在每个节点中增加了一个指针，分别指向前后两个节点；循环链表则通过将最后一个节点的指针指向第一个节点，形成一个环形结构。

作为一种动态数据结构，链表具有以下特点：

1. 动态分配内存：链表中的节点可以在运行时动态创建和释放，链表的大小可以灵活调整。
2. 插入和删除效率高：操作只需调整相关节点的指针，无需像数组那样移动其他元素。
3. 空间利用率高：链表不要求内存的连续性，能够利用零散的内存空间。
4. 无越界问题：链表通过指针访问节点，不存在数组中的索引越界风险。

尽管如此，链表也存在一定的局限性，例如：

• 访问效率低：访问某个特定节点时需要从头节点开始逐个遍历，时间复杂度较高。
• 额外空间开销：每个节点需要额外存储指针信息，与数组相比，空间利用率稍低。

以下解释由gpt得来，有点懒得写了qwq

在 C 语言中，定义一个链表通常涉及到两个步骤：首先定义链表节点的结构体，然后通过指针操作这些节点来构建链表。

1. 定义链表节点的结构体

链表的每个节点通常包含两部分：数据部分和指向下一个节点的指针。以下是一个简单的链表节点结构体定义：

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

// 定义链表节点结构体
struct Node {         //建议用typedef定义一个别名，可以减少输入struct的频率
    int data;           // 数据部分
    struct Node *next;  // 指向下一个节点的指针
};

在这个例子中，Node 结构体包含一个 int 类型的 data，用于存储链表节点的数据，另一个 next 是一个指向下一个 Node 结构体的指针，指示链表的下一节点。

2. 创建和初始化链表

创建链表时，你需要动态分配内存给节点，通常通过 malloc() 函数来分配内存。

next.value 和 next->value 的区别在于 next 的类型，即 next 是一个普通变量（结构体类型）还是一个指针（指向结构体的指针）。

// 创建一个新节点并初始化
struct Node* createNode(int value) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("error\n");
        exit(1);  // 内存分配失败时退出程序
    }
    newNode->data = value;  // 设置节点数据  "->"关键字是对指向的指针操作访问成员,"."是普通变量
    newNode->next = NULL;    // 设置节点的 next 指针为 NULL
    return newNode;  //返回创建链表的指针
}

3. 示例：构建一个链表并遍历

以下是一个简单的例子，展示如何创建链表并遍历它：

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

// 定义链表节点结构体
struct Node {
    int data;
    struct Node *next;
};

// 创建新节点
struct Node* createNode(int value) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

// 遍历链表并打印数据
void printList(struct Node *head) {
    struct Node *current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    // 创建一个链表
    struct Node *head = createNode(1);  // 创建链表的头节点
    head->next = createNode(2);         // 创建第二个节点
    head->next->next = createNode(3);   // 创建第三个节点

    // 遍历并打印链表
    printList(head);

    return 0;
}

4. 释放链表内存

在程序结束时，如果链表是动态分配的，应该释放内存，以避免内存泄漏。可以使用 free() 函数来释放每个节点的内存：

void freeList(struct Node *head) {
    struct Node *current = head;
    while (current != NULL) {
        struct Node *temp = current;
        current = current->next;
        free(temp);
    }
}

总结

• 使用 struct 定义链表节点。
• 通过 malloc() 动态分配内存为每个节点。
• 通过指针操作来建立节点之间的连接。
• 最后，记得在程序结束时释放内存，避免内存泄漏。

这个基本结构适用于大多数链表实现，可以在此基础上进一步扩展，如实现插入、删除等操作。

我们自己写一个双向链表来总结一下知识点，并作为常用脚本。

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

typedef struct chain {   //定义一个结构体定义一个链表的一个单位的结构
    struct chain* before;  //上一个节点的地址
    int data;              //节点数据
    struct chain* after;    //下一个节点的地址

} chain;                   //重命名


chain* appendchain(chain* head, int value);   //在末尾添加一个节点
int initchain(chain* ptr, int len);           //初始化一个链表
int printchain(chain* header);                //输出链表
int delchain(chain* header, int value);        //删除一个节点
int addchain(chain* header, int value, int value1, int value2);  //添加一个节点
chain* search(chain* header, int value);       //搜素一个节点数据


int main() {

    chain* header = appendchain(NULL, 0);     //创建节点头部
    initchain(header, 10);        //初始化节点，规定节点长度为10
    printchain(header);           //查看初始化的节点
    addchain(header,999, 1, 2);    //插入一个999的数据到1，和2之间
    //search(header, 2);
    printchain(header);           //查看修改后的节点
    delchain(header, 999);                   //删除999这个数据节点
    printchain(header);
    return 0;
}


chain* appendchain(chain* head, int value) {
    chain* newchain = (chain*)malloc(sizeof(chain));
    if (!newchain) {
        printf("malloc error");
        exit(0);
    }
    newchain->before = head;
    newchain->data = value;
    newchain->after = NULL;
    return newchain;
}

int initchain(chain* ptr, int len) {
    for (int i = 0; i < 10; i++) {
        ptr->after = appendchain(ptr, i);
        ptr = ptr->after;
    }
    return 0;
}

int printchain(chain* header) {
    if (!header)
        return 0;
    while (1) {
        printf("%d-->", header->data);
        if (header->after == NULL) {
            printf("NULL");
            printf("\n");
            return 0;
        }
        header = header->after;
    }
}

int delchain(chain*header,int value) {
    chain* location = search(header,value);
    chain* last = location->before;
    chain* next = location->after;
    free(location);
    last->after = next;
    next->before = last;
    return 0;
}

int addchain(chain* header, int value, int value1, int value2) {
    
    chain* last = search(header, value1);
    chain* next = search(header, value2);
    chain* tmp = last->after;
    last->after = next->before = appendchain(last, value);
    next->before->after = tmp;
    return 0;
}

chain* search(chain* header, int value) {
    int flag = 0;
    if (header == NULL) {
        printf("no\n");
        return NULL;
    }

    while (1) {

        if (header->data == value) {
            printf("Yes in %d \n", flag);
            return header->before->after;
        }
        if (header->after == NULL) {
            printf("no\n");
            break;
        }
        header = header->after;
        flag++;
    }
    return header;
}