01)
参考课程：【（2025版）深入浅出《数据结构（C语言描述）》】 https://www.bilibili.com/video/BV1FyH3zzEcW/?p=2&share_source=copy_web&vd_source=8541a01b50589c05f56714cfb5fda7ff
1.C基础
上文虽然简单入门了C语言，但是也仅限于了解，接下来跟着课程再学学C，以及后面的数据结构。
1.1字符串
1.1.1 字符串占据内存
一个字符在内存中占一个字节，sizeof()计算所占字节。字符串在最后有 "\0"结尾。
#include <stdio.h> int main(int argc, char const *argv[]) { char s[] = "helloworld"; printf("%d",sizeof(s)); return 0; }int占4个字节（每字节8bit），又分为有无符号数不同，取值范围并不一样。
1.1.2内存地址
为每一个字节分配的地址。通常用16进制表达，微机原理里有所提及。
1.2数组与指针
%p表示地址；a在某些情况下隐式为数组首位元素的地址；但是&a是对于整个数组取址。
[]也是可以加在指针后面，而不是单单数组后面。
#include <stdio.h> int main() { int a[] = {1,2,3,4,5}; printf("a = %p\n", a); printf("&a = %p\n", &a); printf("a+1 = %p\n", a+1); printf("&a+1= %p\n", &a+1); printf("sizeof(a) = %zu\n", sizeof(a)); // 20 printf("sizeof(&a)= %zu\n", sizeof(&a)); // 8（64位系统指针大小） return 0; }输出为：
C 语言里所有指针做+n运算，偏移字节 =n × 指针指向类型的大小。
1.3指针
接上面指向类型大小：
1.3.1指针实现交换函数swap
#include <stdio.h> void swap(int*,int*); int main() { int a =10; int b = 5; printf("a=%d\tb=%d\n",a,b); swap(&a,&b); printf("a=%d\tb=%d\n",a,b); return 0; } void swap(int *a ,int *b){ int p; p=*a; *a=*b;*b=p; }int*p是指针变量，存地址；但是*p是取数值。p也是地址？？&a是取地址。
1.4 动态内存分配
一般栈内存是自动分的，堆内存是手动的，所以动态内存分配也是针对堆内存的。
1.4.1 malloc函数简介
void*表示返回的指针可以是任意类型，函数的参数是申请的字节数。
1.4.2 使用
malloc返回指针是void*，所以要转换指针类型。且用sizeof（）计算数据类型对应字节数。
#include <stdio.h> #include <stdlib.h> int main(int argc, char const *argv[]) { int a=5; int *b=(int*)malloc(sizeof(int));/*分配一个int对应的字节数*/ *b=5; printf("%d-%p\n",*b,b); printf("%d-%p\n",a,&a); free(b); return 0; }free（/*首地址*/）最后释放内存；
数据结构内容
2.算法分析
2.1 时间复杂度
主要要与问题规模n有关，n是不确定的，确定的是常数.
2.2 空间复杂度：
曼波
2.3 ADT 抽象数据
某种数据类型的说明，有点像类？实现就是把方法放到外面。
3.线性表
3.1 线性表定义
3.2 顺序表实现
3.2.1 顺序表定义
顺序表通过数组来实现，数组是它实现的工具。相同数据结构的集合，然后用数组来组织集合中元素
3.2.2顺序表定义与初始化
#include<stdio.h> /*线性表最大长度*/ #define MAXSIZE 100 /*线性表内数据元素的数据类型*/ typedef int elemtype; /*线性表类*/ typedef struct { /* data */ elemtype data[MAXSIZE];/*线性表本体*/ int length;/*线性表索引角色*/ }Seqlist; /*线性表初始化函数*/ void initLength(Seqlist * L){ L->length = 0; } int main(int argc, char const *argv[]) { /*创建一个线性表实例*/ Seqlist l1; initLength(&l1); printf("%d\n",l1.length); printf("%zu\n",sizeof(l1.data)); return 0; }3.2.3 顺序表添加元素
length在这里是下一个空白元素的下标，也就是总长度。
#include<stdio.h> #define MAXSIZE 100 typedef int elemtype; typedef struct { /* data */ elemtype data[MAXSIZE]; int length; }Seqlist; int initLength(Seqlist * L){ L->length = 0; return 1; } /*根据实例的length属性添加元素*/ int addelem(Seqlist * L,elemtype e){ if (L->length <= MAXSIZE) { /* code */ L->data[(L->length)] = e; L->length++; return 1; } return 0; } /*输出此线性表实例的组成*/ void listelem(Seqlist *L){ for ( int i = 0; i <= L->length; i++) { printf("%d\n",L->data[i]); } } int main(int argc, char const *argv[]) { Seqlist l1; initLength(&l1); printf("%d\n",l1.length); printf("%zu\n",sizeof(l1.data)); addelem(&l1,12); listelem(&l1); addelem(&l1,22); addelem(&l1,33); listelem(&l1); return 0; }3.2.4 中间插入元素
想要实现在第几个位置（不等于下标）插入特定元素：
新增函数：
/*在第num个位置插入元素e*/ int insertlist(Seqlist *L,int num,elemtype e){ if (num < 0 || num>L->length) { return 0; } else { for (int i = L->length; i >=num; i--) { L->data[i] = L->data[i-1]; } L->data[num-1] = e; L->length++; return 1; } } int main(int argc, char const *argv[]) { Seqlist l1; initLength(&l1); printf("%d\n",l1.length); printf("%zu\n",sizeof(l1.data)); addelem(&l1,12); listelem(&l1); addelem(&l1,22); addelem(&l1,33); listelem(&l1); insertlist(&l1,2,99); listelem(&l1); return 0; }结果为：
3.2.5堆内存实现初始化顺序表
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef int elemtype; typedef struct { elemtype *data;/*指针后面也能加[]，类似于数组 */ int length; }Seqlist; /*函数内部实现实例化与初始化*/ Seqlist * initLength(void){ Seqlist *L1 = (Seqlist*)malloc(sizeof(Seqlist)); L1->data = (elemtype*)malloc(sizeof(elemtype)*MAXSIZE); L1->length = 0; return L1; } /*根据实例的length属性添加元素*/ int addelem(Seqlist * L,elemtype e){ if (L->length < MAXSIZE) { /* code */ L->data[(L->length)] = e; L->length++; return 1; } return 0; } /*输出此线性表实例的组成*/ int listelem(Seqlist *L){ for ( int i = 0; i < L->length; i++) { printf("%d",L->data[i]); } printf("\n"); return 1; } /*在第num个位置插入元素e*/ int insertlist(Seqlist *L,int num,elemtype e){ if (num < 1 || num>L->length) { return 0; } else { for (int i = L->length; i >=num; i--) { L->data[i] = L->data[i-1]; } L->data[num-1] = e; L->length++; return 1; } } int main(int argc, char const *argv[]) { Seqlist* l1 = initLength(); printf("%d\n",l1->data); printf("%zu\n",sizeof(l1->data)); addelem(l1,12); listelem(l1); addelem(l1,22); addelem(l1,33); listelem(l1); insertlist(l1,2,99); listelem(l1); free(l1->data); free(l1); return 0; }一般函数内部的临时变量在调用结束后就会消失，但是存放在malloc创立的堆内的话，除非free释放掉，不然不会消失。所以函数里直接用malloc可以创建一些变量。
3.3 单向链表
3.3.1 链表与节点定义
不同于顺序表的 一个结构体实例能表示整个线性表 ，链表的一个结构体实体仅仅能表示一个节点（数据域加指针域）。
这里定义结构体节点要用完整的struct node，为了让结构体内部的next指针调用类型。
单向链表只能向前，不能回头。
3.3.2 单链表-头节点初始化
头节点不算入线性表内，纯作为起点。
图上这个是只有头节点，链表内还没有数据。完整代码如下：
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef int elemtype; typedef struct node/*链表里的结构体最好定义节点，而不是整个线性表*/ { elemtype data; struct node * next; }Node; /*初始化出头节点于堆内存*/ Node* initlist(){ Node *head = (Node*)malloc(sizeof(Node)); /*这里没有数组，节点内部属性直接在栈设置即可*/ head->data = 0; head->next = NULL; return head; } int main(int argc, char const *argv[]) { Node *head = initlist(); printf("%zu\n",head->data); printf("%p",head->next); free(head); return 0; }结果：
3.3.3 头插法增加链表节点
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef int elemtype; typedef struct node/*链表里的结构体最好定义节点，而不是整个线性表*/ { elemtype data; struct node * next; }Node; /*初始化出头节点于堆内存*/ Node* initlist(){ Node *head = (Node*)malloc(sizeof(Node)); /*这里没有数组，节点内部属性直接在栈设置即可*/ head->data = 0; head->next = NULL; return head; } /*头插法增加新节点*/ void inserthead(Node *L,elemtype e){ Node *p = (Node*)malloc(sizeof(Node)); p->data = e; p->next = L->next; L->next = p; } int main(int argc, char const *argv[]) { Node *head = initlist(); printf("%zu\t",head->data); printf("%p\n",head->next); inserthead(head,22); printf("%zu\t",head->data); printf("%p\n",head->next); printf("%zu\t",head->next->data); printf("%p\n",head->next->next); free(head->next); free(head); return 0; }结果：
3.3.4 链表遍历打印
有点像嵌套的思路，指向指针的指针云云。。。
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef int elemtype; typedef struct node/*链表里的结构体最好定义节点，而不是整个线性表*/ { elemtype data; struct node * next; }Node; /*初始化出头节点于堆内存*/ Node* initlist(){ Node *head = (Node*)malloc(sizeof(Node)); /*这里没有数组，节点内部属性直接在栈设置即可*/ head->data = 0; head->next = NULL; return head; } /*头插法增加新节点*/ void inserthead(Node *L,elemtype e){ Node *p = (Node*)malloc(sizeof(Node)); p->data = e; p->next = L->next; L->next = p; } /*遍历并打印链表各个节点的数据域内容 已知，链表尾部节点指向NULL*/ void listnode(Node *L){ Node* p = L->next; while (p!=NULL) { printf("%zu\t",p->data); p = p->next; } printf("\n"); } int main(int argc, char const *argv[]) { Node *head = initlist(); inserthead(head,22); inserthead(head,33); inserthead(head,44); listnode(head); free(head->next->next->next); free(head->next->next); free(head->next); free(head); return 0; }输出是：
可以发现是倒序的，和插入的顺序相反。下面用尾插来解决：
3.3.5 尾插法增加链表节点
为了获取尾节点地址，结合上面遍历的思路（尾节点的next指针域为NULL）：
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 100 typedef int elemtype; typedef struct node/*链表里的结构体最好定义节点，而不是整个线性表*/ { elemtype data; struct node * next; }Node; /*初始化出头节点于堆内存*/ Node* initlist(){ Node *head = (Node*)malloc(sizeof(Node)); /*这里没有数组，节点内部属性直接在栈设置即可*/ head->data = 0; head->next = NULL; return head; } /*头插法增加新节点*/ void inserthead(Node *L,elemtype e){ Node *p = (Node*)malloc(sizeof(Node)); p->data = e; p->next = L->next; L->next = p; } /*遍历并打印链表各个节点的数据域内容 已知，链表尾部节点指向NULL*/ void listnode(Node *L){ Node* p = L->next; while (p!=NULL) { printf("%zu\t",p->data); p = p->next; } printf("\n"); } /*遍历获取尾节点地址*/ Node* tailnode(Node*L){ Node* p = L->next; while (p->next!=NULL) { p = p->next; } return p; } /*尾插法并且获取尾节点地址*/ Node* inserttail(Node* p,elemtype e){ Node *l = (Node*)malloc(sizeof(Node)); l->data = e; p->next = l; l->next = NULL; return l; } int main(int argc, char const *argv[]) { Node *head = initlist(); inserthead(head,22); inserthead(head,33); inserthead(head,44); Node * tail = tailnode(head); tail = inserttail(tail,88); tail = inserttail(tail,99); listnode(head); free(head->next->next->next->next->next); free(head->next->next->next->next); free(head->next->next->next); free(head->next->next); free(head->next); free(head); return 0; }结果：
3.3.6 指定位置插入
略，还有链表删除；
3.3.7 释放整个链表
用俩指针，一前一后。简单版的快慢指针。
反转链表用三指针实现，设置不同指针的 初始距离、步长等等。
3.4 双向链表
3.4.1 双向链表定义
3.4.2 操作：
（画图更好理解）
头插法
尾插法：
4. 栈和队列
本质是有特殊规则限定的线性表。因此仅做笔记，不再复现代码。
4.1 栈
4.1.1 栈的定义
后进先出
栈只用关注进栈和出栈。
4.1.2 栈的顺序结构-初始化
顺序下，栈也是个数组，top作为栈顶，在这里是最后进入的元素的下标索引，所以当栈里没有元素时，top为-1；进入第一个时，top为0；也用top来判断元素数目。
进栈
出栈
所谓删除实质为下标移动，原本栈顶元素随意操作。
4.1.3 栈的链式结构
对于栈思想，还是顺序结构用的多，但是如果非要链式，头节点那里作为栈顶比较好用。
4.2 队列
先进先出
4.2.1 队列的定义
尾可入，头可出。
4.2.2队列的顺序结构
（1）初始化
（2）判断空队列
（3）出队
（4）入队
（5）调整队列
让队头回到整个数组空间的最前面，即下标0；
（6）队列循环结构
后续了解
4.2.3 队列的链式结构
（1）定义与初始化
队列的定义涉及俩结构体，front是指向头节点（不算入队列里），rear指向尾节点。
然后分别初始化，先初始化头节点再初始化队头、队尾。二者都指向头节点。
（2）尾插法入队
（3）头节点出队
其实出的是头节点的下一个节点。但是做起来，直接让队头front指向第n个即可。
5.递归
感觉像是高中数列的an=f(a(n-1))，但是函数递归会占用大量的栈内存资源。
6.表达式求值
计算机只认识后缀表达式：
6.1 后缀表达式计算
遇到数值入栈，遇到运算符时，俩数值出栈按顺序运算。
6.2 中缀转后缀
略
字符转数字：‘8’-‘0’，ASCI码差距即数字本身
