参考课程【2025版深入浅出《数据结构C语言描述》】 https://www.bilibili.com/video/BV1FyH3zzEcW/?p2share_sourcecopy_webvd_source8541a01b50589c05f56714cfb5fda7ff1.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(a1 %p\n, a1); printf(a1 %p\n, a1); printf(sizeof(a) %zu\n, sizeof(a)); // 20 printf(sizeof(a) %zu\n, sizeof(a)); // 864位系统指针大小 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;*bp; }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 a5; int *b(int*)malloc(sizeof(int));/*分配一个int对应的字节数*/ *b5; 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顺序表定义与初始化#includestdio.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在这里是下一个空白元素的下标也就是总长度。#includestdio.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 || numL-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堆内存实现初始化顺序表#includestdio.h #includestdlib.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 || numL-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 单链表-头节点初始化头节点不算入线性表内纯作为起点。图上这个是只有头节点链表内还没有数据。完整代码如下#includestdio.h #includestdlib.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 头插法增加链表节点#includestdio.h #includestdlib.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 链表遍历打印有点像嵌套的思路指向指针的指针云云。。。#includestdio.h #includestdlib.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#includestdio.h #includestdlib.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调整队列让队头回到整个数组空间的最前面即下标06队列循环结构后续了解4.2.3 队列的链式结构1定义与初始化队列的定义涉及俩结构体front是指向头节点不算入队列里rear指向尾节点。然后分别初始化先初始化头节点再初始化队头、队尾。二者都指向头节点。2尾插法入队3头节点出队其实出的是头节点的下一个节点。但是做起来直接让队头front指向第n个即可。5.递归感觉像是高中数列的anf(a(n-1))但是函数递归会占用大量的栈内存资源。6.表达式求值计算机只认识后缀表达式6.1 后缀表达式计算遇到数值入栈遇到运算符时俩数值出栈按顺序运算。6.2 中缀转后缀略字符转数字‘8’-‘0’ASCI码差距即数字本身