Avatar mrlxl的知识库
关于我
搜索文章...

文档

考研视角下的C语言(下)

2026-01-24

考研视角下的C语言(下)

第十二章_指针

指针是什么？指针保存的是一个地址，是用于存放内存地址的变量，它指向某个对象在内存中的起始地址（首地址）。

12.1 指针变量的初始化

指针变量是依附于另外一个目标而存在的，所以先要给目标申请内存，再来创建一个指针变量。而我们都知道，指针变量存放的是目标在内存中的首地址，为了确定目标的实际大小，所以在创建指针变量的时候还需要确定基类型，以方便编译器在解引用和指针运算时确定访问的字节数。 指针变量初始化 这里解释下上面例子中出现的两个运算符：

  • 解引用符号 * ： 和 = 与 [] 类似，在不同的地方符号的含义不同，在“类型声明”里表示“指针类型”，在“表达式”里表示乘法和根据指针变量存储的地址值和指针的基类型取指向地址里的值
  • 取地址符号 & ： 在声明中只作为类型的一部分或语法连接符出现，本身不表示运算，在表达式里表示 “取某个对象的首地址”（生成一个指针值）

12.2 指针变量的使用

C语言中的指针存在非常多的用法，但是对于初学者来说，只用掌握两种就好了，即指针的传递和指针的偏移：

12.2.1 指针的传递

指针的传递能够用来在被调函数的栈帧里修改主调函数栈帧的数据：

  1. 主调函数给被修改的数据申请内存
  2. 被调函数以数据的指针作为参数
  3. 被调函数用解引用运算符去间接访问内存，修改内容
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void swap(int *pa, int *qb) {
	int temp = *pa;
	*pa = *qb;
	*qb = temp;
}
int main() {
	int a = 5, b = 10;
	printf("swap函数调用前a=%d，b=%d\n", a, b);

	int *pa = &a;
	int *qb = &b;
	swap(pa, qb);
	printf("swap函数调用后a=%d，b=%d\n", a, b);
	return 0;
}

指针传递流程图

12.2.2 指针的偏移

所谓指针的偏移就是对指针的变量做加减法（只能加减整数），实现连续内存单元的访问，通常和数组联系在一起。公式如下：

  • 指针p + n = p里存储的地址 + n * 基类型的大小

和之前讲的 [ ] 运算符很相似 指针的偏移

12.2.3 指针的使用原则

指针的使用原则只有一个：先考虑目标是否存在，再使用指针。 比如下面这段代码，结合 10.2 函数运行的内存原理，10.4 生存期，其实这个局部数组在函数调用完成之后就被销毁了，那指向他的指针解引用也自然会出错： 指针的使用原则

12.3 指针和数组的关系

之前在数组的章节中已经提到过，数组元素在进行赋值，加减，函数调用的时候，除了最外层元素，都会退化成一个指针指向下一维数组的首地址。他们两个其实很像，数组元素能够退化成指针，指针也能去使用方括号运算符： 指针和数组的关系 这里我们只用注意一个点，当我们在用sizeof()求指针和数组名的大小的时候，sizeof(指针p)还是指针变量的大小，而sizeof(数组名)却是整个数组的大小，这是因为sizeof()并不是一个函数，是编译期运算符。 而数组元素只有在在进行赋值，加减，函数调用的时候，除了最外层元素，才退化成一个指针。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void func(int *p) {
	printf("sizeof(p)=%d\n", sizeof(p));
}

int main() {
	int arr[2][4] = { {1,2,3,4},{3,4,5,6} };
	int *p = arr[1];
	printf("sizeof(arr[i])=%d\n", sizeof(arr[1]));
	printf("sizeof(p)=%d\n", sizeof(p));
	func(arr[1]);
	return 0;
}
//自行验证，结果为 ：
//sizeof(arr[i]) = 16
//sizeof(p) = 8
//sizeof(p) = 8

12.4 堆空间和动态数组

12.4.1 堆空间

我们再来复习下内存布局，之前在 10.2 函数运行的内存原理 中我们学习了内存中的栈，本小节将讨论的是另一个部分–堆。 内存布局-堆 为了使用户自己决定内存的申请与释放，C语言允许程序在运行过程中从堆区申请和释放内存，那么主要涉及到两个函数：

  1. malloc(memory allocate)：

    语法：
#include<stdlib.h>
void *malloc(size_t size);
    • 添加一个#include<stdlib.h>
    • 函数名是malloc
    • 参数是一个size_t(unsigned long long 8字节无符号整数)用于描述申请空间的大小
    • void * 是基类型还没确定的指针，在解引用和偏移之前必须强转成其他类型，描述的是申请空间的首地址

  2. free：

    语法：
#include<stdlib.h>
void free(void *ptr);
    • 添加一个#include<stdlib.h>
    • 函数名是free
    • free 的参数必须是通过 malloc、calloc 或 realloc 分配得到的内存的起始地址，也就是“这块内存的首地址”。不要传入中间的地址或者偏移后的地址，只要是指向这块内存的首地址的指针就行，不管数据类型和之前分配的是否一致。

使用malloc和free函数申请和释放堆内存，修改 12.2.3 指针的使用原则 中的错误代码： 12.2.3错误代码修改

12.4.2 动态数组

堆内存中申请的空间叫动态数组，不是因为长度可以在运行时随意变动，而是申请长度可以在运行时动态决定：

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

int main(){
    int n;
    scanf("%d", &n);             // 用户输入长度
    int* arr = (int*)malloc(n * sizeof(int));
}

而静态数组如 int arr[3] 的长度在编译时就确定，空间分配在栈上。虽然现在C99标准已经支持如下写法，但是由于栈帧空间比较小，用户输入值过大容易溢出，所以并不推荐，很多编译器也会报错

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

int main(){
    int n;
    scanf("%d", &n);
    int arr[n];   // C99 才支持
}

12.5 空指针和野指针

野指针是指指向不确定或者非法内存地址的指针变量，这类指针如果解引用成功就会造成程序崩溃或者读到垃圾数据等未定义行为，如下：

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

int main() {
	int *p = (int *)0x1234567812345678; //这是一个野指针
	*p = 100;
	printf("*p=%d", *p);

    //这种是常犯的错误
    int *q; //这是一个野指针 
    func(q);
	return 0;
}

空指针就是值为0的指针，因为解引用空指针一定会报错，但是解引用野指针可能不会报错，所以如果创建了一个指针变量，暂时还没有指向，一定将其初始化为空指针，主要就是避免野指针问题。(养成先int *p = NULL; 的好习惯) 空指针

第十三章_C风格字符串

13.1 C风格字符串

C 语言中并不存在原生的字符串类型，所谓“字符串”本质上是以 ‘\0’ 结尾的字符序列，通常存储在字符数组中。 那么字符数组和普通数组有什么不同呢，前面 11.6 数组作为函数参数 提过一维普通数组在传递的时候丢失了长度信息，但是一维字符数组则不会丢失长度信息，原因是字符数组使用\0作为结束符号，首地址+结束符即能够确定整个数组的大小，如下所示： 示意 下图这样其实是会出现一个乱码情况，即字符数组中未为结束符 ‘\0’ 预留空间： 乱码 此时使用 printf("%s", str) 输出时，函数会从 str 的首地址开始，持续向后读取内存，直到偶然遇到某个值为 0 的字节为止，从而造成越界读取，表现为乱码甚至运行时错误。

13.2 字符串常用函数

13.2.1 strlen函数

通过从字符数组的首地址开始，逐字节读取内存，直到\0为止，用于计算字符串的长度 （不包括结束符），是用作计算字符数组的有效大小，而不是整体大小。

语法：
#include<string.h>
size_t strlen(char *str)

strlen

13.2.2 strcpy函数

我们之前学的单一变量间能够直接进行赋值，但是数组间是不能直接进行赋值的，那自然C语言中的字符串间也不能直接进行赋值，一般的数组借助存循环一个一个进行拷贝，而字符串间有更简单的方法即strcpy函数。

语法：
#include<string.h>
char *strcpy(char *to,const char *from)

strcpy 但是这个函数也有风险，当to数组长度小于from数组长度时会造成越界访问，比如下面这段代码就会造成栈溢出：

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

int main() {
	char to[5];
	char from[10] = "hello";
	printf("strcpy函数调用前to=%s\n", to);
	strcpy(to, from);
	printf("strcpy函数调用后to=%s\n", to);
	return 0;
}

13.2.3 strcmp函数

主要用来比较字符串的大小，函数按字典序逐个比较两个字符串中对应位置的字符，当出现第一个不相等字符时，以其字符编码值的大小决定字符串的大小关系；若所有对应字符均相等，则根据字符串长度判断，比如"a"<“abandon”<“b”。返回值小于 0、等于 0 或大于 0，分别表示第一个字符串小于、等于或大于第二个字符串。 最主要的使用场景就是判断两个字符串是否完全一致。

语法：
#include<string.h>
int strcpy(const char *str1,const char *str2)

strcmp

13.2.4 strcat函数

用于字符串的拼接

语法：
#include<string.h>
char *strcat(char *str1,const char *str2)

strcat 与strcpy函数同样是没有长度信息且对数组进行修改操作的函数，存在越界风险，比如拼接后的内容大于第一个字符数组的长度就越界。

13.2 字符串的输入

13.2.1 scanf %s

scanf %s 输入一个单词，以空白字符（空格，换行，制表符）作为边界，但是是没有长度信息且对数组进行修改操作的函数，所以当输入长度大于数组长度时存在越界问题，是不安全的。 scanf %s

13.2.2 fgets

fgets 输入一行字符，以换行符作为边界，有长度信息，只要正确把数组的长度传递给该函数，那么这个函数就是安全的。

语法：
char *fgets(char *str, int n, FILE *stream);

这里注意一点，当缓冲区中的数据少于 n-1 或者遇到换行符时，fgets函数还会自动加上一个换行符，不想要去掉就行。具体用法如下： fgets

第十四章_递归和分治

14.1 递归的基本概念

所谓递归，就是一个函数在其内部直接或间接地调用自身，通过不断地将问题分解为规模更小、结构相同的子问题来求解。普通函数与递归函数的压栈示意图如下： 递归概念

但是递归可能会存在栈溢出的问题，由于栈的空间是有限的，无限递归或者大量递归意味着有大量相同的函数压栈造成空间不够栈溢出问题，所以使用递归应该合理设置结束策略，如下示意代码：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void func(int i) {
	printf("i=%d\n", i);
	//设置合理的结束策略防止栈溢出
	if (i <= 0) {
		return;
	}
	else {
		func(i - 1);
	}
}

int main() {
	func(6);
	return 0;
}

14.2 爬楼梯问题

爬楼梯问题是指“有n个台阶，你每次只能爬一阶或者两阶，你有几种爬上去的方法”，要解决这个经典问题最好引入分治的思想，其实还和数学上的数学归纳法相关，那么这分治、数学归纳法、递归分别是什么，有什么关系呢？总的来说：分治是一种把大问题拆成小问题的思想，递归是实现分治的主要编程方式，而数学归纳法是证明递归和分治算法正确性的理论基础。

引入分治的思想之后，我们再来分析这个数学问题，先说结论：f(n) = f(n-1) + f(n-2)，为什么呢，因为到n阶台阶的所有方法都被分成了两类–最后一步走一节台阶和最后一步走两阶台阶。这就相当于从n-1阶台阶到n-2阶台阶都只有一种走法，自然满足上述结论。下面举例说明下：

  • 第一阶 (1) –> f(1) = 1
  • 第二阶 (1+1) (2) –> f(2) = 2
  • 第三阶 (1+1+1) (2+1) (1+2) –> f(3) = 3 注意：第三阶的方法来自第二阶的每种方法+1，来自第一阶的每种方法+2
  • 第四阶 (1+1+2) (2+2) (1+1+1+1) (2+1+1) (1+2+1) –> f(4) = 5 注意：第四阶的方法来自第三阶的每种方法+1，来自第二阶的每种方法+2

那么如何使用递归的代码实现这种分治的思想呢，只需要遵循两个原则：

  1. 怎么把大问题转换成小问题
  2. 怎么解决最小问题

解决代码示例如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int func(int n) {
	//大问题 --> 小问题 --> 递归
	if (n > 2) {
		int result = func(n - 1) + func(n - 2);
		return result;
	}

	//解决最小问题
	if (n == 2) {
		return 2;
	}

	if (n == 1) {
		return 1;
	}
}

int main() {
	int result = func(4);
	printf("result=%d", result);
	return 0;
}

这段代码的函数的具体计算顺序（即压栈顺序）如下，遵循从左到右的顺序，类似数据结构中的前序遍历：

func(4)
 ├─ func(3)
 │   ├─ func(2) → return
 │   └─ func(1) → return
 │   → func(3) return
 └─ func(2) → return
 → func(4) return

14.3 汉诺塔问题

汉诺塔问题也是一个经典的递归和分治问题，题目示意如下： 汉诺塔问题 解决这个问题也采用分治的思想，主要分三步：

  1. 将A的上面n-1个通过某种策略移动到B位置（这一步本质上是规模更小的汉诺塔问题）
  2. 将A位置剩下的第n个移动到C位置（这一步是解决最小问题）
  3. 将B位置的n-1个通过某种策略移动到C位置（这一步本质也是规模更小的汉诺塔问题）

示例代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void hannota(int n, char from, char buffer, char to) {
	//from是原来位置
	//buffer是中间的缓冲位置
	//to是要移动到的目标位置
	if (n > 1) {
		hannota(n - 1, from, to, buffer);//第一步：将原来位置上面n-1个移动到缓冲位置
		hannota(1, from, buffer, to);//第二步：将原来位置最下面的第n个移动到目标位置
		hannota(n - 1, buffer, from, to);//第三步：将缓冲位置的n-1个移动到目标位置
	}

	if (n == 1) {
		printf("move %c-->%c\n", from, to);//如果只有一个，直接从原来位置移动到目标位置
	}
}

int main() {
	int n = 4;
	hannota(n, 'A', 'B', 'C');
	return 0;
}

函数调用过程如下：

hannota(4, A, B, C)
├─ hannota(3, A, C, B)
│  ├─ hannota(2, A, B, C)
│  │  ├─ hannota(1, A, C, B)
│  │  ├─ hannota(1, A, B, C)
│  │  └─ hannota(1, B, A, C)
│  ├─ hannota(1, A, C, B)
│  └─ hannota(2, C, A, B)
│     ├─ hannota(1, C, B, A)
│     ├─ hannota(1, C, A, B)
│     └─ hannota(1, A, C, B)
├─ hannota(1, A, B, C)
└─ hannota(3, B, A, C)
   ├─ hannota(2, B, C, A)
   │  ├─ hannota(1, B, A, C)
   │  ├─ hannota(1, B, C, A)
   │  └─ hannota(1, C, B, A)
   ├─ hannota(1, B, A, C)
   └─ hannota(2, A, B, C)
      ├─ hannota(1, A, C, B)
      ├─ hannota(1, A, B, C)
      └─ hannota(1, B, A, C)

14.4 归并排序

14.4.1 归并操作

为了理解这个排序，我们先来引入归并操作：两个有序的数组怎么合并成一个大的有序的数组？ 归并

14.4.2 归并排序

既然要进行排序，那么就是要求排序一个无序的大数组，怎么使用分治思想进行排序呢？我们知道，如果一个数组只有一个数，那么他天然就是有序的。既然如此，那么分治思想的两个条件就都能完成了：

  1. 把大问题怎么拆分成小问题：将一个包含多个元素的数组不断拆分成左右两个子数组，直到每个子数组中只剩下一个元素
  2. 最小问题怎么解决：当子数组中只有一个元素时，不需要任何处理，它本身就是有序的。

在递归返回的过程中，会逐层出现如下情况： 数组 arr 在区间 [left, mid] 和 [mid+1, right] 内已经分别有序。此时，通过一次归并（merge）操作，可以将这两个有序子数组合并成一个更大的有序数组。

从逆向角度来看，归并排序的过程可以理解为： 最初由单个元素组成的有序数组，不断通过归并操作合并成规模更大的有序数组，最终合并成一个整体有序的大数组。

示例代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>


//归并操作函数
void merge(int* arr, int* temp, int left, int mid, int right) {
	int i = left;
	int j = mid + 1;
	int k = left;
	//将arr数组备份到temp数组里
	for (int i = left; i <= right; i++) {
		temp[i] = arr[i];
	}
	//用i遍历左边用j遍历右边,k是用来记录这次循环修改arr数组的位置下标
	for (i = left, j = mid + 1, k = left; i <= mid && j <= right; k++) {
		if (temp[i] <= temp[j]) {
			arr[k] = temp[i];
			i++;
		}
		else {
			arr[k] = temp[j];
			j++;
		}
	}

	//由于mid左右两边的数组可能会有没有分配的元素
	//但是肯定是最大的那一列且在一个数组中（升序排序）
	//所以两边都把他合并上去
	while (i <= mid) {
		arr[k] = temp[i];
		i++;
		k++;
	}

	while (j <= right) {
		arr[k] = temp[j];
		j++;
		k++;
	}
}

void mergesort(int* arr, int* temp, int left, int right) {
	//left<right是证明有两个及以上元素才用排序
	if (left < right) {
		int mid = (left + right) / 2;
		mergesort(arr, temp, left, mid); //递归排序左边数组
		mergesort(arr, temp, mid + 1, right); //递归排序右边数组
		merge(arr, temp, left, mid, right);
	}
}
int main() {
	int arr[] = { 12,3,5,3,6,7,2,1,21,66 };
	int temp[10];

	mergesort(arr, temp, 0, 9);
	for (int i = 0; i < 10; i++) {
		printf("%d ", arr[i]);
	}
	return 0;
}

第十五章_结构体及补充知识

15.1 结构体的类型定义和变量定义

结构体（Structure） 是 C 语言中一种用户自定义的数据类型，用于把若干个不同数据类型的变量组合在一起，作为一个整体来使用，以便描述具有多个属性的对象。 类型和变量定义代码如下，较为简单不多做阐述：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

struct student_s {
	int age;
	char name[10];
	double Chinese;
	double Math;
	double English;
    // struct student_s stu; //不能包含自身，这是错的
}students2; //分号不能省略，在定义结构体的同时定义变量
int main() {
    students2 = {20,"Jeoge",100,90,90};
	struct student_s students1 = { 18,"LuoShine",100,90,80 };
	return 0;
}

值得注意的是：编译器必须能够确定其所占的内存大小，结构体才能被定义，因此结构体不能包含自身类型的成员，是因为会导致结构体大小无法确定，形成无限递归定义。

15.2 结构体变量的使用

这一小节主要介绍两个运算符：

  1. . 运算符：用于访问结构体中的成员
  2. -> 运算符：用于结构体指针访问结构体中的成员，先解引用后访问成员，是为了代替麻烦的(*pstu).age这种写法
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

struct student_s {
	int age;   //4
	char name[10];   //10
	double Chinese;  //8
	double Math;     //8
	double English;  //8
}; //分号不能省略
int main() {
	struct student_s students1 = { 18,"LuoShine",100.0,90.0,80.0 };
	struct student_s students2 = students1;//结构体变量能够直接进行赋值，即使里面有不能直接进行赋值的数组

	//使用 . 运算符直接访问结构体成员
	printf("students2的age = %d\n", students2.age);
	//但是如果是一个结构体指针，会出现一个问题，. 运算符优先级大于 * 导致必须要使用括号，显得麻烦
	struct student_s* pstu = &students1;
	//使用 -> 运算符访问结构体成员
	printf("pstu->age = %d,(*pstu).age = %d\n", pstu->age, (*pstu).age); 
	return 0;
}

15.3 对齐问题

结构体的大小，大于等于其内部包含的所有数据类型的变量的大小之和，等于很正常，那为什么会大于？这其中涉及到内存对齐问题，比如下图，我们能看见结构体中的不同数据类型变量的大小之和只有38，但是结构体的大小确有40： 对齐问题 这是因为CPU读内存通常是按字长读的（四字节或者八字节），结构体末尾只需要补到“最大对齐单位的整数倍”即可，如上图最大对齐单位是double=8,所以补到40即可。

这里本质上是计算机组成原理的知识，不做过多阐述，知道这么对齐即可。

15.4 补充知识

15.4.1 typedef

这是用于重命名数据类型，注意重命名结构体有两种方法，其中“定义结构体的同时定义变量”和“定义结构体的同时重命名”有些相似，代码示例用法如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
typedef int aaa; //给int类型起别名叫做aaa

typedef struct student_s {
	aaa age;   //指的是int类型
	char name[10];   
	double Chinese;  
	double Math;     
	double English;  
}student_s; //struct student_s重命名为student_s

//下面这种写法也行
//typedef struct student_s student_s;
int main() {
	student_s students1 = { 18,"LuoShine",100.0,90.0,80.0 };
	return 0;
}

15.4.2 C++的引用

在C++中为了简化指针的阅读难度，引入引用的用法，本质上是受约束、不可为空、不可重新绑定的指针，用于“给已有对象起别名”，凡是需要“操作原对象而不是副本”的地方都可以用。 简单了解即可，代码示例如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

void swap1(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

void swap2(int& a, int& b) {
	int temp = a;
	a = b;
	b = temp;
}

int main() {
	int a = 1; 
	int b = 2;
	swap1(&a, &b);
	swap2(a, b);
	return 0;
}

第十六章_链表

链表是考研中重要的知识点，属于数据结构这一部分，本章通过C语言的方式对链表进行简单讲解。

16.1 线性表，数组和链表

我们之前介绍过数组，数组是在内存中一段连续存储的内存单元，每个元素都具有相同的大小，每个元素都有前驱节点或者后驱节点，就像一条绳子一样，我们也称其为线性表。但是呢，数组这种线性表存在一个很大的缺点：当我想在数组中间进行插入或删除操作时，需要移动其后所有元素的位置，从而导致时间开销较大。 为了解决这一问题，引入了链表这种线性表结构。 链表模型 上图介绍的其实就是一种最简单的链表结构–单链表，每个节点由数据域和指针域组成，指针用于存放下一个节点的起始地址。这样在插入和删除的时候只需要改相关节点的指针即可，而无需移动大量元素。 链表这样的线性表结构相较于数组，访问速度会变慢，使用空间会增大，但是方便进行插入和删除。本质是空间换时间。

16.2 链表的类型定义

了解模型之后，具体怎么进行链表的定义呢？我们将每个节点使用结构体来实现，具体代码如下：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

typedef struct node_s {
	//数据域
	int data;
	//指针域
	//struct node_s next; 这样是不行的，前面结构体讲过，无线递归无法确定大小。
	struct node_s* next;
}node_t;

typedef struct link_list_s {
	node_t* phead; //指向第一个节点
	node_t* ptail; //指向最后一个节点
}link_list_t;

int main() {
	return 0;
}

16.3 链表的插入方法

16.3.1 头插法

所谓头插法，就是插入数据只在链表的头部插入，本节采用头指针和尾指针同时管理链表的结构，根据链表是否为空，可分为以下两种情况：

  1. 链表中无节点（指向头结点和尾节点的指针都为空）： 此时链表中不存在任何节点。插入新节点时，头指针和尾指针同时指向该新节点，并将新节点的指针域置为 NULL。 因此，头插法并非始终只修改头指针，在空链表情况下，尾指针同样需要更新。
  2. 链表中有节点（指向头结点和尾节点的指针的值都不为空）： 此时链表中已有数据。插入新节点时，只需令新节点指针指向原头结点，再更新头指针指向新节点即可，尾指针保持不变。

链表插入的示意图和头插法代码如下： 头插法

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef struct node_s {
	//数据域
	int data;
	//指针域
	//struct node_s next; 这样是不行的，前面结构体讲过，无线递归无法确定大小。
	struct node_s* next;
}node_t;

//这个结构体里的两个指针作为辅助指针
typedef struct link_list_s {
	node_t* phead; //指向第一个节点
	node_t* ptail; //指向最后一个节点
}link_list_t;

void head_insert(link_list_t* plist, int data) {
	//给新节点申请内存并初始化
	node_t* newnode = (node_t*)malloc(sizeof(node_t)); //必须要开在堆区，栈区函数调用结束就销毁了
	newnode->data = data;
	newnode->next = NULL; //初始化时候新节点的指针总是指向空

	//分类讨论
	if (plist->phead == NULL && plist->ptail == NULL) {
		plist->phead = newnode;
		plist->ptail = newnode;
	}
	else {
		newnode->next = plist->phead;
		plist->phead = newnode;
	}
}

//遍历打印函数
void print_list(link_list_t* plist) {
	node_t* mark = plist->phead;
	while (mark != NULL) {
		printf("%d\n", mark->data);
		mark = mark->next;
	}
}
int main() {

	link_list_t plist;
	//初始化
	plist.phead = NULL;
	plist.ptail = NULL;
	//插入操作
	head_insert(&plist, 2);
	head_insert(&plist, 3);
	head_insert(&plist, 4);
	//遍历打印操作
	print_list(&plist);
	return 0;
}

16.3.2 尾插法

这是平常写代码用到的最多的插入方法，一般写代码能够用尾插法就用尾插法，除非是在没有尾指针的管理方式下。实现和头插法差不多，只修改了插入函数中的分类讨论中的else部分：

void tail_insert(link_list_t* plist, int data) {
	//给新节点申请内存并初始化
	node_t* newnode = (node_t*)malloc(sizeof(node_t)); //必须要开在堆区，栈区函数调用结束就销毁了
	newnode->data = data;
	newnode->next = NULL; //初始化时候新节点的指针总是指向空

	//分类讨论
	if (plist->phead == NULL && plist->ptail == NULL) {
		plist->phead = newnode;
		plist->ptail = newnode;
	}
	else {
		plist->ptail->next = newnode;
		plist->ptail = newnode;
	}
}

16.3.3 链表的有序插入法

如果链表本身是有序的，那么如何保证新节点插入之后，链表仍然有序呢？一开始你可能会想到对链表节点挨个做遍历直到找到比新节点数据域大（或者小）的第一个节点，但是如果我们需要在一个节点前面做插入，关键是修改该节点前驱的指针域和新节点本身的指针域。

需要注意的是，在单链表中，节点只包含指向后继节点的指针，无法通过当前节点直接访问其前驱节点。因此我们使用双指针法：两个指针一前一后的进行链表的遍历，分三种情况进行讨论：

  1. 没有节点的情况： 直接插入即可。
  2. 第一个位置就符合条件的情况： 退化成头插法。
  3. 第一个位置不符合的情况： 采用双指针法，遍历节点，找到符合条件的位置，将插入位置的前驱节点指针指向新节点，新节点指针指向插入位置的后驱节点。若没有符合条件的位置，则退化成尾插法。

升序插入代码如下：

void sort_insert(link_list_t* plist, int data) {
	//给新节点申请内存并初始化
	node_t* newnode = (node_t*)malloc(sizeof(node_t)); //必须要开在堆区，栈区函数调用结束就销毁了
	newnode->data = data;
	newnode->next = NULL; //初始化时候新节点的指针总是指向空


	//分类讨论（双指针法，至少要有一个节点)
	if (plist->phead == NULL && plist->ptail == NULL) { //没有节点的情况，不能使用双指针
		plist->phead = newnode;
		plist->ptail = newnode;
	}
	else if(plist->phead->data > data){ //如果第一个节点的data比插入节点的data小（或者大）就退化成头插法
		newnode->next = plist->phead;
		plist->phead = newnode;
	}
	else { //采用双指针法
		node_t* pre = plist->phead; //慢指针
		node_t* cur = pre->next; //快指针
		while (cur != NULL) {
			if (cur->data > data) {
				pre->next = newnode;
				newnode->next = cur;
				break;
			}
			pre = pre->next;
			cur = pre->next;
		}

		//链表中找不到比新插入节点更小（或者大）的节点，于是采用尾插法
		if (cur == NULL) {
			plist->ptail->next = newnode; //这里不能写cur=newnode哦，因为cur此时只是最后一个节点的副本
			plist->ptail = newnode;
		}
	}
}

16.4 链表的删除

链表的删除和链表的插入一样，其核心都是修改节点之间的指针关系。根据链表状态和删除位置的不同，可分为以下几种情况：

  1. 链表为空： 不用修改，直接打印出错就行。
  2. 删除头节点： 头指针指向删除节点的后驱节点。若链表只有一个节点（头指针和尾指针相同）： 则头指针和尾指针置空。
  3. 链表不止一个节点，删除非头节点： 由于单链表无法直接访问前驱节点，所以采用双指针法，将删除节点的前驱节点指针指向删除节点的后驱节点，若为尾指针，则删除节点的前驱节点指针置为空，并同步修改尾指针。

三种情况代码如下：

void delete_list(link_list_t* plist, int data) {

	node_t* cur = plist->phead; //快指针，cur用来记录被删除节点的位置
	if (plist->phead == NULL && plist->ptail == NULL) {  //链表为空
		printf("Error:链表为空，无法删除\n");
		return;
	}
	else if (cur->data == data) { //删除头节点
		plist->phead = cur->next;
		cur->next = NULL;
		if (plist->phead == NULL) { //删除之后，链表为空，是只有一个节点的情况
			plist->ptail = NULL;
		}
        
        free(cur);
        cur = NULL;
        return;
	}
	else { //链表不止一个节点，删除非头节点
		node_t* pre = plist->phead; //慢指针
		cur = pre->next; //快指针
		while (cur != NULL) {
			if (cur->data == data) {
				if (cur == plist->ptail) { //删除的节点是尾节点
					plist->ptail = pre;
					pre->next = NULL;
					break;
				}
				pre->next = cur->next;
				cur->next = NULL;
				break;
			}

			pre = pre->next;
			cur = pre->next;
		}

		if (cur == NULL) {
			printf("Error:要删除的节点不存在！\n");
			return;
		}
        
        free(cur);
        cur = NULL;
        return;
	}

}

附言

以上便是考研C语言会涉及到的全部的基础内容，C语言是408的基础，学习408的时候一定要边学边敲代码。接下来将进行C专题练习的文章讲解。

总是在探索未知

大纲

ESC 关闭 ↑↓ 选择 Enter 跳转