algotithm

常用

文件

打开文件

FILE* openfile(const char* filename, const char* mode) {    // 打开文件
    FILE *file = fopen(filename, mode);
    if (file == NULL) {
        printf("\n Error opening file\n");
        return NULL;
    }
    printf("\n File %s opened successfully\n", filename);
    return file;
}

栈

顺序栈（下方两个 DFS 迷宫问题使用）

sqstack.h

#pragma once                // 防止被重复引用
#include <stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 100//储存空间初始分配量
#define STACKINCREMENT  10//存储空间分配增量
#define OK 1
#define ERROR 0
typedef struct {
    int x;  //行值
    int y;  //列值
}PosType;  //迷宫坐标位置类型
typedef struct
{
    int ord;      //序号
    int di;       //方向
    PosType seat; //位置

} StackType; //栈元素类型

typedef struct {
    StackType *base;   //在构造之前和销毁之后，base的值为NULL
    StackType *top;    //栈顶指针
    int stacksize;     //当前已分配的存储空间，以元素为单位

}SqStack; //顺序栈

//栈的初始化
int InitStack(SqStack *p) {


    p->base = (StackType*)malloc(STACK_INIT_SIZE * sizeof(StackType));
    if (p->base == NULL)
        return ERROR;  //内存分配失败
    p->top = p->base;     //栈顶与栈底相同表示一个空栈
    p->stacksize = STACK_INIT_SIZE;
    return OK;

}
//判断栈是否为空
int EmptyStack(SqStack *p) {
    //若为空栈 则返回OK，否则返回ERROR
    if (p->top == p->base)
        return OK;
    else return ERROR;
}
//顺序栈的压入
int Push(SqStack *p, StackType e) {
    //插入元素e为新的栈顶元素
    if ((p->top - p->base) >= p->stacksize)   //栈满，追加储存空间
    {
        p->base = (StackType*)realloc(p->base, (p->stacksize + STACKINCREMENT) * sizeof(StackType));
        if (p->base == NULL)
            return ERROR;// 储存空间分配失败
        p->top = p->base + p->stacksize;
        p->stacksize += STACKINCREMENT;
    }
    *(p->top) = e;
    (p->top)++;
    return OK;
}


// 顺序栈的弹出
int Pop(SqStack *p, StackType *e) {
    //若栈不空，则删除p的栈顶元素，用e返回其值
    if (p->top == p->base)
        return ERROR;
    --(p->top);
    *e = *(p->top);
    return OK;


}
//将顺序栈置空 栈还是存在的，栈中的元素也存在，
//如果有栈中元素的地址任然能调用
int ClearStack(SqStack *p) {
    p->top = p->base;
    return OK;
}
//顺序栈的销毁
int DestroyStack(SqStack *p) {
    //释放栈底空间并置空
    free(p->base);
    p->base = NULL;
    p->top = NULL;
    p->stacksize = 0;

    return OK;
}

有趣的小东西

静态链表

待检查

#include <stdio.h>
#define MAXSIZE 1000 // 静态链表的最大长度

typedef struct {
    int data; // 数据域
    int cur; // 游标，指向下一个元素的位置
} Component, StaticLinkList[MAXSIZE];

// 初始化静态链表
void InitList(StaticLinkList space) {
    for (int i = 0; i < MAXSIZE - 1; i++) {
        space[i].cur = i + 1;
    }
    space[MAXSIZE - 1].cur = 0;
}

// 在 L 中第 i 个元素之前插入新的数据元素 e
void ListInsert(StaticLinkList L, int i, int e) {
    int j, k, l;
    k = MAXSIZE - 1;
    if (i < 1 || i > ListLength(L) + 1) {
        return;
    }
    j = Malloc_SLL(L);
    if (j) {
        L[j].data = e;
        for (l = 1; l <= i - 1; l++) {
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;
        L[k].cur = j;
    }
}

// 删除在 L 中第 i 个数据元素 e
void ListDelete(StaticLinkList L, int i) {
    int j, k;
    if (i < 1 || i > ListLength(L)) {
        return;
    }
    k = MAXSIZE - 1;
    for (j = 1; j <= i - 1; j++) {
        k = L[k].cur;
    }
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SSL(L, j);
}

// 返回静态链表的长度
int ListLength(StaticLinkList L) {
    int j = 0;
    int i = L[MAXSIZE - 1].cur;
    while (i) {
        i = L[i].cur;
        j++;
    }
    return j;
}

哨兵节点

字典树

猜字谜游戏

用到了字典树和回溯法

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#define N 10
#define ALPHABET_SIZE 26

char grid[N][N]; // 定义一个 N x N 的字符数组，用于存储字谜游戏的网格
char *dictionary[] = {"ICELAND", "MEXICO", "PANAMA", "ALGERIA", "BELARUS", "FIJI"}; // 定义一个字符串数组，用于存储字典中的单词
int n = sizeof(dictionary) / sizeof(dictionary[0]); // 计算字典中单词的数量

// 定义字典树节点结构体
typedef struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE]; // 定义一个指针数组，用于存储子节点
    bool isEndOfWord; // 定义一个布尔变量，用于标记该节点是否为单词的结尾
} TrieNode;

// 创建一个新的字典树节点
TrieNode *getNode() {
    TrieNode *node = (TrieNode *)malloc(sizeof(TrieNode)); // 分配内存空间
    node->isEndOfWord = false; // 初始化 isEndOfWord 为 false
    for (int i = 0; i < ALPHABET_SIZE; i++)
        node->children[i] = NULL; // 初始化所有子节点为 NULL
    return node;
}

// 向字典树中插入一个单词
void insert(TrieNode *root, char *word) {
    TrieNode *node = root;
    for (int i = 0; i < strlen(word); i++) {
        int index = word[i] - 'A'; // 计算字符在字母表中的索引
        if (!node->children[index])
            node->children[index] = getNode(); // 如果子节点不存在，则创建一个新节点
        node = node->children[index]; // 移动到下一个子节点
    }
    node->isEndOfWord = true; // 标记单词的结尾
}

// 在字典树中搜索一个单词
bool search(TrieNode *root, char *word) {
    TrieNode *node = root;
    for (int i = 0; i < strlen(word); i++) {
        int index = word[i] - 'A'; // 计算字符在字母表中的索引
        if (!node->children[index])
            return false; // 如果子节点不存在，则返回 false
        node = node->children[index]; // 移动到下一个子节点
    }
    return (node != NULL && node->isEndOfWord); // 判断是否找到了单词
}

// 打印字谜游戏的网格
void printGrid() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            printf("%c", grid[i][j]); // 打印每个字符
        printf("\n");
    }
}

// 判断给定位置是否可以放置单词
int isSafe(int row, int col, char *word) {
    int len = strlen(word);

    // 检查单词是否可以水平放置
    if (col + len <= N) {
        for (int i = 0; i < len; i++)
            if (grid[row][col + i] != '-' && grid[row][col + i] != word[i])
                return 0;
        return 1;
    }

    // 检查单词是否可以垂直放置
    if (row + len <= N) {
        for (int i = 0; i < len; i++)
            if (grid[row + i][col] != '-' && grid[row + i][col] != word[i])
                return 0;
        return 2;
    }
    return 0;
}

// 在给定位置放置单词
void placeWord(int row, int col, char *word, int dir) {
    if (dir == 1)
        for (int i = 0; i < strlen(word); i++)
            grid[row][col + i] = word[i]; // 水平放置单词
    else
        for (int i = 0; i < strlen(word); i++)
            grid[row + i][col] = word[i]; // 垂直放置单词
}

// 从给定位置移除单词
void removeWord(int row, int col, char *word, int dir) {
    if (dir == 1)
        for (int i = 0; i < strlen(word); i++)
            grid[row][col + i] = '-'; // 移除水平放置的单词
    else
        for (int i = 0; i < strlen(word); i++)
            grid[row + i][col] = '-'; // 移除垂直放置的单词
}

// 解决字谜游戏问题的递归函数
int solvePuzzle(TrieNode *root, int index) {
    if (index == n)
        return 1; // 如果所有单词都已经放置完毕，则返回 1

    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            int dir = isSafe(row, col, dictionary[index]); // 判断给定位置是否可以放置单词
            if (dir) {
                placeWord(row, col, dictionary[index], dir); // 在给定位置放置单词
                if (solvePuzzle(root, index + 1)) // 递归地解决下一个单词
                    return 1;
                removeWord(row, col, dictionary[index], dir); // 回溯，移除刚才放置的单词
            }
        }
    }
    return 0;
}

int main() {
    memset(grid, '-', sizeof(grid)); // 初始化字谜游戏的网格

    TrieNode *root = getNode(); // 创建一个新的字典树节点

    // 将字典中的单词插入到字典树中
    for (int i=0;i<n;i++){
      insert(root,dictionary[i]);
      }

   // 解决字谜游戏问题
   if(solvePuzzle(root,0))
      printGrid(); // 如果找到了解，则打印网格
   else
      printf("No solution exists"); // 否则，打印无解

   return 0;
}

快速求幂算法

快速求幂算法（Fast Exponentiation Algorithm）是一种高效的算法，用于计算幂运算。它可以快速地计算 base^exponent 的值，即使指数 exponent 非常大。该算法的基本思想是将指数拆分为若干个较小的指数之和，然后利用幂运算的结合律将这些较小的幂相乘，从而快速地计算出原来的幂。

原理是将指数拆分为若干个较小的指数之和，然后利用幂运算的结合律将这些较小的幂相乘，从而快速地计算出原来的幂。具体来说，该算法使用了二进制表示法来拆分指数。例如，假设我们要计算 3^13 的值。首先，我们可以将 13 表示为二进制数 1101，即 13 = 8 + 4 + 1。然后，我们可以先计算出 3^1 = 3、3^2 = 9、3^4 = 81 和 3^8 = 6561 的值。最后，我们将这些值相乘，得到 3^13 = 3^8 _ 3^4 _ 3^1 = 6561 _ 81 _ 3 = 1594323。

例如，假设我们要计算 2^13 的值。使用快速求幂算法，我们可以将指数 13 拆分为 8 + 4 + 1。然后，我们可以先计算出 2^1 = 2、2^2 = 4、2^4 = 16 和 2^8 = 256 的值。最后，我们将这些值相乘，得到 2^13 = 2^8 _ 2^4 _ 2^1 = 256 _ 16 _ 2 = 8192。

下面是一个简单的 C 程序，它实现了快速求幂算法：

#include <stdio.h>

int main() {
int result = 1;
int base = 2;
int exponent = 13;

    while (exponent > 0) {
        if (exponent % 2 == 1)
            result *= base;
        base *= base;
        exponent /= 2;
    }

    printf("2^13 = %d\n", result);
    return 0;

}

---

应用：

使用快速求幂算法来计算 (3^100) mod 5 的值。下面是对该程序的详细解释，包括前几次循环的每一步。

#include <stdio.h>

int main() {
    int result = 1; // 初始化结果为 1
    int base = 3; // 底数为 3
    int exponent = 100; // 指数为 100
    int mod = 5; // 模数为 5

    while (exponent > 0) { // 当指数大于 0 时，执行循环
        if (exponent % 2 == 1) // 如果指数为奇数
            result = (result * base) % mod; // 将结果乘以底数，然后取模
        base = (base * base) % mod; // 将底数平方，然后取模
        exponent /= 2; // 将指数除以 2
    }

    printf("(3^100) mod 5 = %d\n", result); // 打印结果
    return 0;
}

在第一次循环迭代中，指数 exponent 的值为 100。因为 100 是偶数，所以不会执行 if 语句中的代码。然后，程序将底数 base 平方，得到 9，并将其模 5 取余，得到 4。最后，程序将指数 exponent 除以 2，得到 50。

在第二次循环迭代中，指数 exponent 的值为 50。因为 50 是偶数，所以不会执行 if 语句中的代码。然后，程序将底数 base 平方，得到 16，并将其模 5 取余，得到 1。最后，程序将指数 exponent 除以 2，得到 25。

在第三次循环迭代中，指数 exponent 的值为 25。因为 25 是奇数，所以会执行 if 语句中的代码。程序将结果 result 乘以底数 base，得到 1 * 1 = 1，并将其模 5 取余，得到 1。然后，程序将底数 base 平方，得到 1 * 1 = 1，并将其模 5 取余，得到 1。最后，程序将指数 exponent 除以 2，得到 <PhoneNumber>。

在接下来的几次循环迭代中，程序会继续执行类似的操作，并最终计算出 (3^100) mod 5 = 1 的结果。

这个算法的原理是基于模运算的性质。根据模运算的定义，如果两个数除以同一个模数，它们的余数相同，那么这两个数在模运算下是等价的。因此，我们可以在每次乘法运算后对结果取模，以保证结果始终小于模数。这样，在最后一次乘法运算后，我们得到的结果就是 (base^exponent) mod mod 的值。

求某数组连续子序列的最大和

一、
设数组为 a[MAXSIZE],定义{A,B,C}为 A,B,C 三者中最大值
伪代码如下：

index = 0

max = cur = a[index]

while ++index < MAXSIZE

	next = a[index]

	if next < 0

		if next > max

			max = cur = next

		else

			cur = 0

	else

		cur += next

		if next == MAX{max, cur, next}

			max = cur = next

		else if cur == MAX{max, cur, next}

			max = cur

print max

---

更简洁的实现模式如下：

#include <stdio.h>

int maxSubArray(int* nums, int numsSize){

    int maxSum = nums[0];

    int currentSum = nums[0];

    for (int i = 1; i < numsSize; i++) {

        currentSum = currentSum > 0 ? currentSum + nums[i] : nums[i];  \\算法核心

        maxSum = currentSum > maxSum ? currentSum : maxSum;
    }
    return maxSum;
}

int main() {

    int nums[] = {-2,1,-3,4,-1,2,1,-5,4};

    int numsSize = sizeof(nums) / sizeof(nums[0]);

    printf("连续子序列最大和为: %d\n", maxSubArray(nums, numsSize));

    return 0;
}

两种方式的时间复杂度相同，核心原理也相同，只是第二种的表述更加简洁

动态规划：
动态规划（Dynamic Programming，简称 DP）是一种用来解决最优化问题的算法思想。它通过将原问题分解为若干个子问题，并将子问题的解存储下来，从而避免重复计算，提高了算法的效率。

动态规划通常用于求解具有重叠子问题和最优子结构性质的问题。所谓重叠子问题，是指在递归求解原问题时，不同的递归分支中会出现重复的子问题。而最优子结构性质是指原问题的最优解可以通过其子问题的最优解来构造。

动态规划算法通常包括两个步骤：定义状态和转移方程。状态表示原问题或子问题的某种性质，转移方程表示如何从一个状态转移到另一个状态。

例如，在求解连续子序列最大和问题时，我们可以定义状态 dp[i] 表示以第 i 个元素结尾的连续子序列的最大和。转移方程为 dp[i] = max(dp[i-1] + nums[i], nums[i])，表示第 i 个元素可以选择加入前面的连续子序列中，或者单独成为一个新的连续子序列。

---

不使用辅助数组，分离顺序表中的奇偶数

（124567 → 157246）
用两个整数 i,j 当作指针进行操作

秘书问题

只检索一遍，给出使得找到最大值概率最大（37%）的算法

本质情境：所有数据只能读取一次，每次只读取一个单位，进行判断后要么选择它、要么否决它，选择后将停止进程，否决后该单位无法再次被选择，找出一种方法，使得取到最优单位的概率最大。

此时可以取定一个”观察期“ k ， k+1 之前（不包括 k + 1)的单位只读不取，记下这些单位中的最大值，之后只要有比观察期的最大值更大的情况就出手，反之不出手，直到全部读取完毕

观察期 k 的求法 ：

1. 此时取到最优单位的概率等价于      系数为（k/i）的调和级数，i = k 加到 n-1 ，令其取到最大值

2. 求和化简得上式等于 (k/n)ln(n/k) = (lnx)/x     x = n/k

3. 求得当x = e 时有最大值，最大值大约为0.3679   （1/e）

从而可知当 n = ek 时取到最优单位的概率最高

选择问题

选出 n 个数里的第 k 个最大者

方法一 ： 时间复杂度取决于排序算法，如冒泡排序是O(n²)

    放入数组中并排序


方法二  ： 时间复杂度为O(n)

    先取k个数，取的同时使用一个“游标”标记出最小的那个值，游标可以是指针，也可以是变量

    之后再取别的数，

    若后取的数比游标指向的数大，则把游标指向那个数，否则不操作

求正整数 1 到 n 的和

本题启发：
可以用公式算的就尽量减少计算机的运算

int sum = 0, n = 100;

sum = (1 + n) * n / 2;

即等差数列求和

也可用 for 循环或 while 循环逐个求和，或递归求解，但时间复杂度会上升

搜索

子集

递归找出数组全部子集

gitmask 找出全部子集

回溯法找出 n 个物品中权值总和为 T 的全部子集

数组每个元素只与排在它后面的元素构成分支，避免产生重复子集影响效率和准确性；
搜索途中超出范围则剪去分支，减少搜索量；

void backtrack(const int data[],int target[],int n,int T,int count,int total){
    if (total == T){        // 满足条件，输出并结束分支（未必要将分支走完，如8,2,5,3,其中到2便可以返回）
        Print(data,target, n);
        return;
    }
    if (total > T || count == n){   // 分支中途和超出范围或者分支寻找结束
        return;     // 返回上一层
    }
    target[count] = 1;  // 先标记，代表这一层内这个位置的数字被用到了
    backtrack(data,target,n,T,count+1,total+data[count]);   // 加上这个节点的值，进入下一层
    target[count] = 0;  // 违背上面的if条件，回退，不把这个数据加进去，
    backtrack(data,target,n,T,count+1,total);               // 深度优先，count每次只走一步，更安全
    // 如果此时还找不到会自动回溯
}

迷宫（所有解）

DFS 找出迷宫的所有通路

#include<stdio.h>
#include "sqstack.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define m 8     // 迷宫的行
#define n 8     // 迷宫的列

typedef int Status;
typedef int MazeType;           // 迷宫数组定义

PosType dire[4] = { {0,1},{1,0},{0,-1},{-1,0} }; //{行增量，列增量}
PosType start,end;              // 起止位置

MazeType maze[m+2][n+2] = {     // 迷宫数组内容
    {1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,1,1,0,0,1},	// (3,3)位置堵住，结果不变
    {1,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,1,1,0,0,0,1,0,0,1},	// (6,1)位置堵住，结果不变
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,1,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1},
};	// 除上述两点外，与PPT中给出的是同一个迷宫

Status printPath(SqStack *p, int* PathCount);   // 打印函数声明
Status MazePath(int maze[][n+2], int* PathCount, int x, int y, SqStack *p); // 求解函数声明
Status MarkPrint(StackType e);                  // 标记经过路径

Status main() {
	SqStack mazeStack;
	InitStack(&mazeStack);  // 创建、初始化栈

	int PathCount = 0; 		// 路径计数
    start.x = 1;            // 设定起止条件
    start.y = 1;
    end.x = m;
    end.y = n;

	MazePath(maze, &PathCount,start.x,start.y,&mazeStack);    // 求解迷宫

	DestroyStack(&mazeStack);                                 // 销毁栈
    return OK;
}

Status printPath(SqStack *p, int* PathCount) {
	*PathCount += 1;
	printf("Path %d :\n", *PathCount);
	StackType e;
	for (StackType* i = p->base; i < p->top; i++) {
		e = *i;
		printf("(%d,%d)->", e.seat.x, e.seat.y);
	}
	printf("Exit Found!\n\n");
	return OK;
}

// 标记迷宫块不可通过
Status MarkPrint(StackType e)
{
    maze[e.seat.x][e.seat.y] = -1;
    return OK;
}

Status MazePath(int maze[][n+2], int* PathCount, int x, int y, SqStack *p) {

    // 走到终点
	if (x == end.x && y == end.y) {
		maze[x][y] = -1;

		// 将终点存入路径中
		StackType e;
		e.seat.x = x;
		e.seat.y = y;
		Push(p, e);

        //输出路径
		printPath(p, PathCount);

        // 输出完毕
		Pop(p, &e);     // 弹出end point
		maze[x][y] = 0; // 标记end point为未访问

		return TRUE;
	}
	else {
		// 若当前位置为0(未被标记)
		if (maze[x][y] == 0) {
			int di = 0;

            //4个方向都进行试探
			while (di < 4) {

				//储存当前位置
				StackType e;
				e.seat.x = x;
				e.seat.y = y;

				//标记为-1，表示已经走过
 				MarkPrint(e);
				Push(p, e);

				//改变方向
				int i, j;
				i = x + dire[di].x;
				j = y + dire[di].y;

				MazePath(maze, PathCount, i, j, p);

				// 抹除当前位置
				Pop(p, &e);
				maze[x][y] = 0;

				di++;//改变方向
			}
		}
		//不能走的话就返回，回到上一个位置
		else
			return OK;
	}
    return OK;
}

迷宫（最优解）

BFS 找出迷宫最优解

迷宫（可行解）

DFS 找一个迷宫可行解

#include <stdio.h>
#include <stdlib.h>
#include "sqstack.h" //引入顺序栈储存结构及其基本操作
#define MAXLENGTH 10  //设迷宫最大行列为25
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int MazeType; //迷宫数组[行][列]
PosType begin, end;   //迷宫入口坐标，出口坐标
PosType direc[4] = { {0,1},{1,0},{0,-1},{-1,0} }; //{行增量，列增量}，移动方向依次为东南西北
MazeType maze[MAXLENGTH][MAXLENGTH] = {
    {1,1,1,1,1,1,1,1,1,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,1,0,0,0,1,0,1},
    {1,0,0,0,0,1,1,0,0,1},
    {1,0,1,1,1,0,0,0,0,1},
    {1,0,0,0,1,0,0,0,0,1},
    {1,0,1,0,0,0,1,0,0,1},
    {1,0,1,1,1,0,1,1,0,1},
    {1,1,0,0,0,1,0,0,0,1},
    {1,1,1,1,1,1,1,1,1,1},
}; //迷宫数组
int x = 10, y = 10;//迷宫的行，列
int curstep = 1;  //当前足迹，初值在入口处为1
struct SElemType
{
    int ord;  //通道块在路径上的“序号”
    PosType seat;   //通道块在迷宫中的“坐标位置”
    int di;  //从此通道块走向下一通道块的“方向”(0-3表示东-北)
};
void Print() {
    //输出迷宫结构
    int i, j;
    for (i = 0; i < x; i++)
    {
        for (j = 0; j < y; j++)
            printf("%3d", maze[i][j]);
        printf("\n");
    }
}

void MarkPrint(PosType seat)
{   //标记迷宫块不可通过
    maze[seat.x][seat.y] = -1;
}
Status Pass(PosType b)
{
    //当迷宫m的b点的值为0，return OK;
    //否则return ERROR;
    if (maze[b.x][b.y] == 0)
        return OK;
    else
        return ERROR;
}
void FootPrint(PosType b)
{
//使迷宫m的b点的值变为足迹(curstep),表示经过
    maze[b.x][b.y] = curstep;

}
PosType NextPos(PosType  b,int di)
{
    //根据当前位置b及其移动方向di，修改b为下一位置
    b.x += direc[di].x;
    b.y += direc[di].y;
    return b;
}
Status MazePath(PosType start, PosType end)
{
    //若迷宫m中存在从入口start到出口end的通道
    //则求得一条存放在栈中，并返回TRUE；否则返回FAlSE
    SqStack s,*S; //顺序栈
    S = &s;
    PosType curpos;
    StackType e,*pe;
    pe = &e;
    InitStack(S);
    curpos = start;
    do
    {
        if (Pass(curpos)) //当前可以通过，则是未曾走到的通道块
        {
            FootPrint(curpos); //留下足迹
            e.ord = curstep;  //栈元素序号为当前序号
            e.seat = curpos;  //栈元素位置为当前位置
            e.di = 0;  //从当前位置出发，下一位置为东
            Push(S, e); //入栈当前位置及其状态
            curstep++;   //足迹加1
            if (curpos.x == end.x&&curpos.y == end.y)  //到达出口
                return TRUE;
            curpos = NextPos(curpos, e.di); //由当前位置及移动方向确定下一个当前位置
        }
        else{ //当前位置不能通过
            if (!EmptyStack(S))  //栈不为空
            {
                Pop(S, pe); // 退栈到前一位置
                curstep--;  //足迹减1
                while (e.di == 3 && !EmptyStack(S))  //前一位置处于最后一个方向(北)
                {
                    MarkPrint(e.seat); //留下不能通过的标记(-1)
                    Pop(S, pe); //退一步
                    curstep--; //足迹再减1

                }
                if (e.di < 3)  //没有到最后一个方向(北)
                {
                    e.di++;  //换下一个方向探索
                    Push(S, e); //入栈该位置的下一个方向
                    curstep++;// 足迹加1
                    curpos = NextPos(e.seat, e.di);

                }
            }
        }
    }
    while (!EmptyStack(S));
    return FALSE;


}
int main()
{
    begin.x = 1;
    begin.y = 1;
    end.x = 8;
    end.y = 8;
    if (MazePath(begin, end)) //有通路
    {
        printf("从此迷宫入口到出口的一条路径如下:\n");
        Print();
    }
    else
        printf("此迷宫没有从入口到出口的路径\n");
    return 0;


}

“左手摸墙”找一个迷宫可行解

排序

快速排序

归并排序

堆排序

希尔排序

选择排序

冒泡排序

猴子排序

误

暂无命名

分治法找到数组给定范围中的最大值

数组 array，搜索范围( left,right )，m 为分割位置

int findMaximun(int array[],int left,int right){
    m = (left + right) / 2;     // 分割
    if(left == right){          // 只有一个元素
        return array[left];
    }
    else{
        int u = findMaximun(array,left,m);  // 分治解决前半部分
        int v = findMaximun(array,m,right); // 分治解决后半部分
        x = (u > v) ? u : v;
        return x;
    }
}

启发式搜索

这是代码

分类

树

Hafuman 树为成绩分等级

85~100 A
75~84  B
65~74  C
60~64  D
<60    E
若全使用条件判断语句，正常情况下，80%的数据需要判断 3 次以上（假设大于 65 分的人数约占 80%）
判断次数： 1F + 2D + 3C + 4B + 5A 次，
而使用哈夫曼树可以提高约 31%的效率
示例：

如图

上机题

数据结构 Lab 1_1

函数

源码

（待拆分函数）

1. 链表操作
2. 从一个给定的数据集合中随机、可重复地选取数据元素，并通过尾插法构建一个双向链表，然后设计算法删除该链表中的重复元素。
3. 构建一个单链表和一个无头节点的循环链表，将其链接成一个有环的链表，然后设计算法确定环的入口点，并计算环的长度。
4. 要求所编写的程序应采用 c 或 c++语言：
5. 必须带命令行参数；
6. 必须通过命令行参数指定输入、输出文件的文件名

代码如下

/*
./1 input.txt output.txt
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

typedef struct NodeTWL {       // 双向链表的结构 TWL = two way link list
    int data;
    struct NodeTWL *prev;
    struct NodeTWL *next;
} NodeTWL;

typedef struct NodeSE {       // 单向链表的结构 SE = Single
    int data;                 // 循环链表也借用这个结构，就不另行定义了，也方便操作
    struct NodeSE *next;
} NodeSE;


// 仅预先声明在主函数中会用到的函数，其余会在各个功能块内定义
// Python中可以写几个Class拖出去，但是C里我还不会操作

// 1)
FILE* openfile(const char* filename, const char* mode);     // 打开文件并检查是否打开成功
char* readFileIntoString(FILE *file);                       // 将文件读入字符串
int countNumbers(char* str);                                // 计算总的数字数量

NodeTWL* back(FILE* file, char* str, int totalCount);       // 尾插法构造双向链表
void remove_duplicates(NodeTWL *head);                      // 删除双向链表中的重复元素
void write_TWL_List_To_File(NodeTWL* head, FILE* file);     // 向文件输出双向链表
void free_TWL(NodeTWL *head);                               // 释放双链表的内存

// 2)
NodeSE* back_single(FILE* file, char* str, int totalCount);         // 尾插法建立单链表
void write_SE_List_To_File(NodeSE* head, FILE* file);               // 向文件输出单链表

NodeSE* back_circulate(FILE* file, char* str, int totalCount);      // 尾插法建立没有头结点的循环链表
void write_CE_List_To_File(NodeSE* Tail, FILE* file);               // 向文件输出没有头结点的循环链表

NodeSE* link_SE_CE(NodeSE* head, NodeSE* Tail);                     // 链接单链表与循环链表
NodeSE* entrance(FILE* file, NodeSE *head);                         // 确定环的入口
void write_SC_List_To_File(NodeSE* head, NodeSE* entr, FILE* file); // 向文件输出有环链表
void free_SC(NodeSE *head,NodeSE *entr);                            // 释放有环链表的内存

// 尾插法读取文件数值到动态链表中，
// 输入心仪的链表长度num，随机取num个数模数组长度


// 写完了才发现没必要用fread + strtok + 字符串，fscanf + 循环 + 动态分配内存也可以解决问题

/*------------------------------------------------------------------------------------------
--------------------------------------主函数-------------------------------------------------
-------------------------------------------------------------------------------------------*/
int main(int argc, char *argv[]) {
    if (argc != 3) {
        printf("Usage: %s input.txt output.txt\n", argv[0]);
        return 1;
    }
    // 打开文件
    FILE* input_file = openfile(argv[1], "r");      // 打开文件并检查是否打开成功
    FILE* output_file = openfile(argv[2], "w");

    // 定义链表指针
    NodeTWL *two_way_list = NULL;       // 双向链表
    NodeSE *single_list = NULL;         // 单向链表
    NodeSE *circulate_list = NULL;      // 循环链表
    NodeSE *sc_linked_list = NULL;      // 有环链表
    NodeSE *entr = NULL;                // 有环链表的环入口

    // 读取文件内容到字符串中（使用fread函数）
    char* str = readFileIntoString(input_file);
    if(strcmp(str, "EMPTY_FILE") == 0) {
        fclose(input_file);
        fclose(output_file);
        exit(1);    // 文件为空立即关闭文件并结束程序
    }
    int totalNumber = countNumbers(str);                    // 计算数字数量
    fprintf(output_file,"\nYour input is = %s \n", str);    // 测试读取是否正常
    fprintf(output_file,"There are %d numbers in your input.\n\n", totalNumber);
    if(totalNumber == 0){                                   // 当输入为空时
        fprintf(output_file,"\nYour input is empty!\n ");
        return 1;
    }

    // 初始化随机数生成器
    srand(time(NULL));

    fprintf(output_file,"\n --------------------------------- Question 1 ---------------------------------\n \n");

    // 尾插法构建双向链表
    two_way_list = back(output_file,str, totalNumber);
    fprintf(output_file,"\nYour original two way list is:\n ");
    write_TWL_List_To_File(two_way_list, output_file);

    // 删除双向链表中的重复元素
    remove_duplicates(two_way_list);
    fprintf(output_file,"\nList after remove_duplication is:\n ");
    write_TWL_List_To_File(two_way_list, output_file);


    while (two_way_list != NULL)
    {
        NodeTWL *TWL_free_temp = two_way_list;
        two_way_list = two_way_list->next;
        free(TWL_free_temp);
        TWL_free_temp = NULL;
    }

    fprintf(output_file,"\n --------------------------------- Question 2 ---------------------------------\n \n");

    // 尾插法构建单链表
    fprintf(output_file,"\nSingle List:\n");
    single_list = back_single(output_file,str, totalNumber);     // 方便起见，单链表的数据也由input.txt提供
    fprintf(output_file,"\n Your single list is:\n ");
    write_SE_List_To_File(single_list, output_file);

    // 尾插法构建没有头结点的循环链表
    fprintf(output_file,"\n\nCirculate List:\n");
    circulate_list = back_circulate(output_file,str, totalNumber);  // 同样，使用input.txt
    fprintf(output_file,"\n Your non-head-circulate list is:\n ");
    write_CE_List_To_File(circulate_list, output_file);

    // 链接单链表与循环链表
    fprintf(output_file,"\n\nLoop List:\n");
    sc_linked_list = link_SE_CE(single_list, circulate_list);
    if(sc_linked_list == NULL){
        fprintf(output_file,"\n\nCannot link these two lists!\n\n");
    }

    // 寻找环的入口，计算环的长度
    entr = entrance(output_file, sc_linked_list);
    write_SC_List_To_File(sc_linked_list, entr, output_file);   // 输出链表，同时计算出环的长度

    free(str);
    free_TWL(two_way_list);
    free_SC(sc_linked_list,entr);

    fclose(input_file);
    fclose(output_file);

    printf("\n\n Done! \n\n");

    return 0;
}
/*-------------------------------------------------------------------
------------------------------文件操作--------------------------------
----------------------------------------------------------------------*/
FILE* openfile(const char* filename, const char* mode) {    // 打开文件
    FILE *file = fopen(filename, mode);                     // 定义为const加个保障
    if (file == NULL) {
        printf("\n Error opening file\n");
        return NULL;
    }
    printf("\n File %s opened successfully\n", filename);
    return file;
}

char* readFileIntoString(FILE *file) {      // 以字符串形式读取输入文件中的全部内容
    fseek(file, 0, SEEK_END);               // SEEK_END：将文件指针移动到文件末尾加上offset字节的位置
    long length = ftell(file);              // 获取文件长度（文件指针在文件末）
    fseek(file, 0, SEEK_SET);               // 把文件指针移回文件开头

    if(length == 0){
        printf("\n\n File is empty!\n");
        return "EMPTY_FILE";                    // 文件为空返回错误信息
    }

    char* buffer = (char*)malloc(length + 1);   // 为每个字符分配一个字节，再额外分配一个字节来存储字符串结束符\0
    if (buffer) {
        fread(buffer, 1, length, file);
        buffer[length] = '\0';
    }
    else{
        printf("\n\n Error allocating memory\n");
    }

    return buffer;      // 该部分内存最后在主文件中以str的形式被释放
}

int countNumbers(char* str) {      // 计算文件内数字的总个数
    char* str_copy = strdup(str);  // 复制字符串，防止原字符串被改变(strtok会插入\0)
    char* token = strtok(str_copy, " ");
    int count = 0;

    while (token != NULL) {
        if (atoi(token) != 0 || strcmp(token, "0") == 0) { // 检查token是否为数字
            count++;
        }
        token = strtok(NULL, " ");
    }
    free(str_copy);
    return count;
}

// 读取字符串指定位置的数字
int getNumberAtPosition(FILE* file,char* str, int position) {
    char* str_copy = strdup(str);       // 复制字符串，防止原字符串被改变(strtok会插入\0)
    char* token = strtok(str_copy, " ");
    int count = 0;

    while (token != NULL) {
        if (count == position) {
            fprintf (file,"At the position %d we take the number %s\n", position, token);
            count = atoi(token);        // 因为要释放str_copy，token指向的内存会被释放，故需要提前保存
            free(str_copy);
            return count;               // 使用atoi函数处理并返回
        }
        token = strtok(NULL, " ");      // 表示从同一个字符串的上一个标记点开始
        count++;
    }

    printf("There is no number at %d\n", position);
    free(str_copy);
    return -1;
}

void write_TWL_List_To_File(NodeTWL* head, FILE* file) {          // 写双向链表到文件
    NodeTWL* current = head;
    int count = 1;
    if (head == NULL){
        fprintf(file, "\nThe TWL list is empty\n");
        return;
    }
    while (current != NULL) {
        fprintf(file, "Data %d is %d\n", count, current->data);
        current = current->next;
        count++;
    }
}

void write_SE_List_To_File(NodeSE* head, FILE* file) {          // 写单链表到文件
    NodeSE* current = head;
    int count = 1;
    if (head == NULL){
        fprintf(file, "\nThe SE list is empty\n");
        return;
    }
    while (current != NULL) {
        fprintf(file, "Data %d is %d\n",count,current->data);
        current = current->next;
        count++;
    }
}

void write_CE_List_To_File(NodeSE* Tail, FILE* file) {          // 写无头结点的循环链表到文件
    NodeSE* current = Tail;
    int count = 1;

    if (Tail == NULL){
        fprintf(file, "\nThe CE list is empty\n");
        return;
    }
    fprintf(file,"Data %d is %d\n",count,current->data);
    current = current->next;
    count++;
    while (current != Tail) {
        fprintf(file,"Data %d is %d\n",count,current->data);
        current = current->next;
        count++;
    }
    fprintf(file, "The number after the last one is %d\n",current->data);
}

void write_SC_List_To_File(NodeSE* head, NodeSE* entr, FILE* file) {          // 写有环链表到文件
    NodeSE* current = head;
    int count = 1;
    int count_entr = 0;

    if (head == NULL){
        fprintf(file, "\nThe SC list is empty\n");
        return;
    }

    // 写出单链部分
    while (current != NULL && current != entr) {
        fprintf(file,"Data %d is %d\n",count,current->data);
        current = current->next;
        count++;
    }

    // 写出环部分
    fprintf(file,"Data %d is *%d*    This is the entrance of loop!\n",count,current->data);  // 给环入口加上特殊标识
    current = current->next;
    count_entr = count;
    count++;
    while (current != entr) {
        fprintf(file,"Data %d is %d\n",count,current->data);
        current = current->next;
        count++;

    }
    fprintf(file, "\n\nThe length of the loop is %d\n",count-count_entr);
}
/* -------------------------------------------------------------------------
------------------------双向链表操作-----------------------------------------
---------------------------------------------------------------------------*/

// 创建新节点并初始化
NodeTWL* createNodeTWL(int data) {
   NodeTWL *newNode = (NodeTWL*)malloc(sizeof(NodeTWL));
   if (newNode == NULL) {
       printf("Memory allocation failed!\n");
       exit(1);
   }

   newNode->data = data;
   newNode->next = NULL;
   newNode->prev = NULL;
   return newNode;
}

// 尾插法建立双向链表
NodeTWL* back(FILE* file,char* str, int totalCount) {
    NodeTWL *head = createNodeTWL(0);  // 虚拟头结点
    NodeTWL *temp = NULL;              // 用于暂存新产生的节点
    NodeTWL *L = head;                 // 保存新节点的前驱结点

    int num = -1;                      // 需要创建的节点数量
    printf("\n Enter the number of NodeTWLs you want:");
    scanf("%d", &num);                 // 可以单独拉出一个函数用strtok()进行防呆处理，但是懒得写了

    if(!num ){
        free(head);
        head = NULL;
        return head;
    }
    else{
        for(int i = 0; i < num; i++){
            temp = createNodeTWL(getNumberAtPosition(file,str, rand() % totalCount));    // 随机抽取一个数创建节点
            L->next = temp;
            temp->prev = L;
            L = L->next;
        }
    }
    L = head->next;
    L->prev = NULL;
    free(head);
    head = NULL;    // 避免指针悬空
    temp = NULL;
    return L;
}

// 移除链表中的重复节点
void remove_duplicates(NodeTWL *head) {
   NodeTWL *current = head;
   NodeTWL *temp = NULL;

   while (current != NULL) {
       temp = current;
       while (temp->next != NULL) {
           if (temp->next->data == current->data) {
               NodeTWL* next = temp->next;  // 指向应该被删除的节点
               temp->next = next->next;
               if (temp->next != NULL) {
                   temp->next->prev = temp;
               }
               free(next);                  // 删除的同时将那部分内存也释放掉
           }
           else {
               temp = temp->next;
           }
       }
       current = current->next;
   }
}

void free_TWL(NodeTWL *head){
    NodeTWL *temp = head;
    while(head){
        temp = head;
        head = head->next;
        free(temp);
    }
    printf("\n\nfree_TWL successed!\n");
}

/*
----------------------------------------------------------------------------------
--------------------------单链表的操作---------------------------------------------
----------------------------------------------------------------------------------*/
// 创建新节点并初始化
NodeSE* createNodeSE(int data) {
   NodeSE *newNode = (NodeSE*)malloc(sizeof(NodeSE));
   if (newNode == NULL) {
       printf("Memory allocation failed!\n");
       exit(1);
   }

   newNode->data = data;
   newNode->next = NULL;
   return newNode;
}

// 尾插法建立单链表
NodeSE* back_single(FILE* file, char* str, int totalCount) {
    NodeSE *head = createNodeSE(0);   // 虚拟头结点
    NodeSE *temp = NULL;              // 用于暂存新产生的节点
    NodeSE *L = head;                 // 保存新节点的前驱结点

    int num = -1;                     // 需要创建的节点数量
    printf("\n Enter the number of NodeSEs you want:");
    scanf("%d", &num);                // 可以单独拉出一个函数用strtok()进行防呆处理，但是懒得写了

    if(!num ){
        free(head);
        head = NULL;
        return NULL;
    }
    else{
        for(int i = 0; i < num; i++){
            temp = createNodeSE(getNumberAtPosition(file,str, rand() % totalCount));    // 随机抽取一个数创建节点
            L->next = temp;
            L = L->next;
        }
    }
    L = head->next;
    free(head);
    head = NULL;
    temp = NULL;
    return L;
}

// 尾插法建立无头结点的循环链表
NodeSE* back_circulate(FILE* file, char* str, int totalCount) {
    NodeSE *tail = createNodeSE(0);   // 虚拟结点
    NodeSE *temp = NULL;              // 用于暂存新产生的节点
    NodeSE *L = tail;                 // 保存新节点的前驱结点

    int num = -1;                     // 需要创建的节点数量
    printf("\n Enter the number of NodeCEs you want:");
    scanf("%d", &num);                // 可以单独拉出一个函数用strtok()进行防呆处理，但是懒得写了

    if(!num ){
        free(tail);
        tail = NULL;
        return NULL;
    }
    else{
        for(int i = 0; i < num; i++){
            temp = createNodeSE(getNumberAtPosition(file,str, rand() % totalCount));    // 随机抽取一个数创建节点
            L->next = temp;
            L = L->next;
        }
    }
    L->next = tail->next;   // 绕开虚拟节点，将链表闭环
    L = tail->next;
    free(tail);
    tail = NULL;            // 避免指针悬空
    temp = NULL;
    return L;
}

NodeSE* link_SE_CE(NodeSE* head, NodeSE* Tail){     // 链接单链表与循环链表
    NodeSE* p = head;
    if(head == NULL || Tail == NULL){
        printf("Cannot link these two lists!");
        return NULL;
    }
    while(p->next != NULL){
        p = p->next;
    }
    p->next = Tail;
    return head;
}

NodeSE* entrance(FILE* file, NodeSE *head) {        // 寻找环的入口
   if (!head || !head->next) {
       fprintf(file,"\n\n Cannot calculate length for empty list or only one node\n");
       return NULL;
   }

   NodeSE* slow = head;     // 定义快慢指针
   NodeSE* fast = head;

   // 快慢指针相遇时，慢指针走过的距离是环长度的两倍
   while (fast && fast->next) {
       slow = slow->next;
       fast = fast->next->next;

       if (slow == fast) {
           break;
       }
   }

   if (!fast || !fast->next) {
       fprintf(file,"\n\nNo cyccle here!\n\n");
       return NULL;
   }

   slow = head;
   while (slow != fast){
        slow = slow->next;
        fast = fast->next;
   }
    fprintf(file,"\n\nThe entrance of the loop is: *%d*\n\n", fast->data);
   return slow;     // slow 和 fast 随便返回一个
}

void free_SC(NodeSE *head,NodeSE *entr){
    NodeSE *temp = head;
    if(head == NULL){
        return;
    }
    while(head != entr){        // 释放单链部分
        temp = head;
        head = head->next;
        free(temp);
    }
    while(head && head != entr){        // 释放环部分
        temp = head;
        head = head->next;
        free(temp);
    }
    if(head)
        free(head);
    printf("\nfree_SC successed!\n\n");
}

数据结构 Lab1_4

函数

源码

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

FILE* openfile(const char* filename, const char* mode);
void backtrack(FILE* output_File,const int data[],int target[],int n,int T,int count,int total);
void Print(FILE* output_file,const int data[],int target[], int n);

int main(int argc, char *argv[]) {
    // 检查输入
    if (argc != 3) {
        printf("Usage: %s <input_file> <output_file>\n", argv[0]);
        return 1;
    }

    // 打开文件
    FILE *input_file = openfile(argv[1], "r");
    FILE *output_file = openfile(argv[2], "w");

    // 定义变量
    int T = 0;   // 背包总体积
    int n = 0;   // 物品的数量

    // 读取背包体积及物品数量
    fscanf(input_file, "%d %d", &T, &n);                // fscanf会自动忽略空格以及换行
    fprintf(output_file, "T: %d \nn: %d\n\n",T,n);      // 读取检查（测试）

    // 申请空间，创建物品数组、标记数组
    int *w = malloc(n * sizeof(int));                   // 此时n已经给定，直接用来申请数组空间即可
    int *target_mark = malloc((n + 1) * sizeof(int));   // 每组解之内的物品个数不可能大于n+1

    // 读取物品体积
    for (int i = 0; i < n; i++) {
        fscanf(input_file, "%d", &w[i]);
        fprintf(output_file, "w[%d]: %d\n", i, w[i]);   // 读取检查（测试）
        if(w[i] > T){
            w[i] = -1;  // 本身比需求大的就不考虑了，节省算力
        }
    }

    // 求解
    fprintf(output_file, "\nSolution:\n");
    backtrack(output_file,w,target_mark,n,T,0,0);

    free(w);
    free(target_mark);

    fclose(input_file);
    fclose(output_file);

    printf("\n Done!\n");

    return 0;
}

FILE* openfile(const char* filename, const char* mode) {    // 打开文件
    FILE *file = fopen(filename, mode);
    if (file == NULL) {
        printf("\n Error opening file\n");
        return NULL;
    }
    printf("\n File %s opened successfully\n", filename);
    return file;
}

// 数组中的每个元素只能与排在它后面的元素构成分支
void backtrack(FILE* output_File,const int data[],int target[],int n,int T,int count,int total){
    if (total == T){        // 满足条件，输出并结束分支（未必要将分支走完，如8,2,5,3,其中到2便可以返回）
        Print(output_File,data,target, n);
        return;
    }
    if (total > T || count == n){   // 分支中途和超出范围或者分支寻找结束
        return;     // 返回上一层
    }
    target[count] = 1;  // 先标记，代表这一层内这个位置的数字被用到了
    backtrack(output_File,data,target,n,T,count+1,total+data[count]);   // 加上这个节点的值，进入下一层
    target[count] = 0;  // 违背上面的if条件，回退，不把这个数据加进去，
    backtrack(output_File,data,target,n,T,count+1,total);               // 深度优先，count每次只走一步，更安全
    // 如果此时还找不到会自动回溯
}

void Print(FILE* output_file,const int data[],int target[], int n){
    for(int i = 0;i < n;i++){
        if(target[i] == 1){     // 每次找到符合条件的分支就打印出来
            fprintf(output_file,"%d ",data[i]);
        }
    }
    fprintf(output_file,"\n");
}

/*
./4 input.txt output.txt
*/

计算机程序设计 Lab 10 & 11

大一入学第一个学期写的代码，当时的编程能力还不强

函数

功能等待拆分

1. 链表结构

struct stu{
    int num;// 内容
    struct stu *next;
};

2. 头插法

struct stu *my_head()       //头插法
{
    struct stu *head = NULL,*p = NULL;
    int n = 0;

    printf("\n请输入学生学号(输入-1结束）：");
    scanf("%d",&n);

    while(n != -1){
        p = (struct stu *)malloc(sizeof(struct stu));

        if(p == NULL){      //判断是否申请内存成功，好习惯之一
            printf("error");
            exit(1);
        }

        p->num = n;
        p->next = head;
        head = p;

        printf("\n请输入学生学号(输入-1结束）：");
        scanf("%d",&n);
    }
    return head;
}

4. 尾插法

struct stu *back()      //尾插法
{
    struct stu *head = NULL,*rear = NULL,*p = NULL;
    int n = 0;

    printf("\n请输入学生学号(输入-1结束）：");
    scanf("%d",&n);

    while(n != -1){
        p = (struct stu *)malloc(sizeof(struct stu));
        if(p == NULL){
            printf("error");
            exit(1);
        }

        p->next = NULL;
        p->num = n;
        if(!head)
            head = p;
        else
            rear->next = p;
        rear = p;

        printf("\n请输入学生学号(输入-1结束）：");
        scanf("%d",&n);
    }
    return head;
}

5. 从文件提取内容

struct stu *fromfile()
{
    void preserve(struct stu *head);    //声明可能会用到的保存函数
    struct stu *head = NULL,*s = NULL,*p = NULL;
    char filename[1024];        //实际并不需要那么多
    FILE *fp;

    printf("请输入您想读入(目前只接受.dat后缀)的文件路径及名称(如D:\\\\student_imformation.dat)\n");
    fflush(stdin);      //刷新缓冲区
    scanf("%s",filename);
    if(!(fp = fopen(filename,"rb"))){   //表明文件不存在,b即binary
        int flag=0; //只在这个语句里用的局部变量

        printf("can't find the file\n");
        printf("你想要现在创建一个吗？(输入0表示不需要)\n");
        scanf("%d",&flag);

        if(!flag){
            fclose(fp);
            return NULL;
        }
        if(flag){
            head = back();  //用尾插法建立，读取更方便
            preserve(head);
            fclose(fp);
            return head;
        }
    }
    //读取文件中的数据
    while(!feof(fp)){
            if(!head){
                p = (struct stu *)malloc(sizeof(struct stu));
                if(p == NULL){
                    printf("error");
                    exit(1);
                }
                lenth++;
                fread(p,sizeof(struct stu),1,fp);
                if(feof(fp)){
                    printf("文件为空\n\n");
                    fclose(fp);
                    return NULL;
                }
             head = s = p;
            }
        p = (struct stu *)malloc(sizeof(struct stu));
        fread(p,sizeof(struct stu),1,fp);

        if(feof(fp)){   //读取结束
            s->next = NULL;
            break;
        }

        s->next = p;
        s = p;
        p->next = NULL;
    }
    fclose(fp);
    printf("已为您读取.dat文件中的内容(可在菜单中选择存为.txt文件)\n");
    return head;

}

struct stu *judge(struct stu *head)    //判断链表是否有序
{
    struct stu *q = NULL,*p = NULL;
    int flag = -1;    //判断是否有序/开关变量
    int f1 = 0,f2 = 0;     //分别代表大于、小于的数量

    p = head;
    if(p != NULL){
        q = p->next;
    }
    while((p != NULL)&&(q != NULL)){
    if((p->num) > (q->num))
        f1++;
    else if((p->num) < (q->num))
        f2++;
    if(f1*f2) {flag=0;break;}   //两者相乘不为零，说明大于和小于同时出现了

        p = p->next;
        q = q->next;
    }
    if(flag == 0) {
        printf("链表无序，您想要排序吗？(不需要请输入0)");
        scanf("%d",&flag);
        if(flag){
            printf("已为您排好升序\n");
            head=my_sort(head);
        }
    }
    return head;
}
struct stu *decision(struct stu *head) //决定在哪里插入
{
    struct stu *p = NULL;
    int i = 0,n = 0;
    p = head;
    printf("您想要在哪里插入(输入*（）*中的序号）：");
    while(p){
        printf("*(%d)*学号:%d  ",i++,p->num);
        p = p->next;
        if(!p) printf("*(%d)*\n",i);
    }
    scanf("%d",&n);
    p = head; //把指针拉回来
    for(i = 0;i < lenth;i++){
        if(n == i)
            break;
        p = p->next;
        if((n != lenth)&&(i == lenth-1)){printf("选择错误！");exit(1);}
    }
    return p;
}
struct stu *my_insert(struct stu *head)    //插入函数 主函数
{
    struct stu *p = NULL,*q = NULL,*temp = NULL;
    p = head;
    head = judge(head);
    p = head;
    q = decision(p);

        temp = (struct stu *)malloc(sizeof(struct stu));
        if(temp == NULL){
            printf("error");
            exit(1);
        }
        printf("\n请输入学生学号：");   //输入要插入的链表的信息
        scanf("%d",&temp->num);
        printf("请输入学生名字:");
        getchar();  //吃空格
        gets((temp->name));
        printf("请输入学生性别");
        gets(&(temp->sex));
        printf("请输入学生年龄");
        scanf("%d",&temp->age);
        printf("请输入学生成绩");
        scanf("%lf",&temp->grade);
        temp->next = NULL;

    p = head;
    if(q == p){  //在表头
        temp->next = head;
        head = temp;
    }
    else if(q == NULL){ //在末尾
        while(p->next) {p = p->next;} //将指针移到表的末尾
        p->next = temp;
    }
    else{
        while(p->next != q) {p = p->next;}
        p->next = temp;
        temp->next = q;
    }
    lenth++;    //表示已经插入了一次,总链表长度增加
    return head;
}
//--------------------------------------------------------------------------------------------------------------------------------
int my_print(struct stu *head)
{
    struct stu *p = NULL;

    p = head;
    while(p){
        printf("\n学号：%d",p->num);
        printf("\n姓名："); puts(p->name);
        printf("性别：");puts(&p->sex);
        printf("年龄：%d\n",p->age);
        printf("成绩：%lf\n",p->grade);
        p = p->next;
    }
    return 2;
}
void preserve(struct stu *head)
{
    struct stu *p = NULL;
    char filename[1024];
    int flag = 0;
    FILE *fp;
    p = head;

    printf("您想存为  txt（1）  文件还是  dat（2）  文件？");
    scanf("%d",&flag);
    printf("请输入您想存入的文件路径及名称(如选择（2）时可写D:\\\\student_imformation.dat)\n");
    scanf("%s",filename);

    if((flag == 1)&&((filename[strlen(filename)-2]) == 'x')){   //x 的意思是，倒数第二个字符为x，也即txt
            if(!(fp = fopen(filename,"w"))){
                printf("开不了\n"); exit(1);
            }
    }
    else if((flag == 2)&&((filename[strlen(filename)-2]) == 'a')){
            if(!(fp = fopen(filename,"wb"))){
                printf("开不了\n"); exit(1);
            }
    }
    else{
        printf("输入不匹配\n\n");
        p = NULL;
    }

    while(p){
            if(flag == 1){
                fprintf(fp,"******************\n学号：%d\n",p->num);
                fprintf(fp,"姓名：");      fputs(p->name,fp);
                fprintf(fp,"\n性别：");    fputs(&p->sex,fp);
                fprintf(fp,"\n年龄：%d\n",p->age);
                fprintf(fp,"成绩：%lf\n",p->grade);
                p = p->next;
            }
            else if(flag == 2){
                fwrite(p,sizeof(struct stu),1,fp);
                p = p->next;
            }
    }
    fclose(fp);
}
void print_choose(struct stu *head)
{
    int flag=0;
    printf("1、屏幕输出\n");
    printf("2、保存链表至文件\n");
    printf("0、返回主菜单\n");
    printf("\n您想选择哪项功能？\n");
    scanf("%d",&flag);

    switch(flag){
        case 1:
            my_print(head);break;
        case 2:
            preserve(head);break;
        default:
            break;      //这一步放给用户了，输入错误也返回主菜单
    }
}
//---------------------------------------------------------------------------------------------------------------------------------
struct stu *my_search(struct stu *head,int n,int flag)
{
    struct stu *p = NULL,*q = NULL; //q用于暂时存储节点
    int len = 0;  //len用于判断函数是否是被多次调用
    p = head;

    while(p){
        if((p->num) == n){
            if(flag == 5) {     //表示此时在 choose函数中被使用
                q = p->next;    //本程序中自定义的输出函数会输出后续所有的链表
                p->next = NULL; //所以用q来存储断开的节点，将p设置为最后一个节点
                my_print(p);
                p->next = q;      //将链表还原
            }
            return p;
        }
        p = p->next;    //移动指针
        len++;
    }
    if(((flag == 5)||(flag == 6))&&(len == lenth)) //表明是查询或者第一次删除
        printf("\n您查询的学号不存在\n");    //能走到这一步肯定就是找不到了
    return NULL;
}
struct stu *my_delete(struct stu *head)
{
    struct stu *shead = NULL;
    struct stu *p = NULL,*t = NULL;  //用于暂时存储节点
    int n = 0;    //n即num
    int flag = 6;     //判断是第几次调用search函数(值为6时表示第一次）
    printf("\n请输入您要删除的学号：");
    scanf("%d",&n);

    shead = (struct stu *)malloc(sizeof(struct stu));
    shead->next = head; //虚拟头节点
    shead->num = -1;    //初始化
    p=shead;
    while(p->next != NULL){       //当移动到链表末尾时结束

        if(p->next->num == n){
            t = p->next;
            p->next = p->next->next;
            lenth--;    //说明已经完成了一次删除
        }
        else {p = p->next;}
    }
    head = shead->next;
    free(shead);
    return head;
}

void choose()
{
    int n = 1,inum = 0;    //用于选择功能
    static int count = 0;
    struct stu *head = NULL;
    struct stu *p = NULL;    //只用于多次调用my_search函数,其实可以直接在函数里的while里解决，找到一个输出一个，可以减少不少代码量和复杂度

    while(n){

    menu();     //展示菜单
    printf("\n请选择功能：");
    scanf("%d",&n);
    if((count == 0)&&(n != 1)&&(n != 0)&&(n != 9)) {n = -1;} //第一次只能先建立链表、清屏或者退出

        switch(n){
            case 1:
                head = my_make();break;   //以下三个函数都会改变head
            case 2:
                head = my_insert(head);break;
            case 3:
                head = my_delete(head);break;
            case 4:
                print_choose(head);break;
            case 5:
                p = head;
                printf("\n请输入您要查询的学号：");
                scanf("%d",&inum);
                while(p){       //可能出现多个相同学号
                   p = my_search(p,inum,n);
                   if(!p) break;    //查不到时指针为空，p->next未知,故if要放在前一步
                    p = p->next;
                }
                break;
            case 6:
                head = my_sort(head);break;
            case 9:
                system("cls");break;            //函数存在 stdlib.h 头文件中，不需要再写
            default:
                if(n != 0) printf("输入错误\n");
        }
        if(n == -1)
            count = 0;      //保险起见加一个赋值，无伤大雅
        else if(head)
            count++;    //第一步的  必选   限制解除
     }
     printf("\n\n程序结束\n");

}
void main()
{
    printf("More features await development!\n\n");
    choose();
}

源码