三研模拟卷代码题

模拟卷 一

四1、

#include <iostream>
using namespace std
class Base{
    public:
        virtual void disp()const =0;
};

class Triangle:public Base{
    private:
        double base;
        double height;
    public:
        Triangle(double b,double h):base(b),height(h){}
        void disp()const override{
            double area = 0.5*base*height;
            cout<<"三角形面积："<<area<<endl;
        }
}; //请注意这里要写分号

class Square:public Base{
    private:
        double side;
    public:Square(double s):size(s){}
    void disp()const override{
        double area = side*side;
        cout<<"正方形面积："<<area<<endl;
    }
};

class Circle:public Base{
    private:
        double radius;
    public:
        Circle(double r):radius(r){}
        void disp()const override{
            double area = 3.14*radius*radius;
            cout<<"圆面积："<<area<<endl;
        }
        
};

int main(){
    Triangle triangle(3.0,4.0);
    Square square(5.0);
    Circle circle(2.0);
    
    //重点要用父类来接受调用,题目要求的
    Base *shapes[] = {
        &triangle,&square,&circle;
    }

    //调用
    for(int i=0;i<3;i++){
        shapes[i]->disp();
    }
}

四2、

#include <iostream>
using namespace std;

int main(){

    int n,M,temp;
    cout<<"请输入数组个数，和要移动的位数"<<endl;
    cin<<n<<M;
    int arr[n];
    for(int i=0;i<n;i++){
        cin<<arr[i];
    }

    for(int i=0;i<M;i++){
        temp = arr[n-1];
        for(int j=n-1;j>0;j--){
            arr[j]=arr[j-1];
        }
        arr[0] = temp;
    }

    for(int i=0;i<n;i++){
        cout<<" "<<arr[i];
    }
}

四3、

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

typedef struct {
    char name[10];
    char id[10];
    float grades[5];
}Student;

void checkFile(FILE *file){
    if(file == NULL){
        return error("Error");
        exit(1);
    }
}

void intputStudent(Student *student){
    printf("请输入姓名");
    scanf("%s",student->name);
    printf("请输入学生的学号");
    scanf("%s",student->id);
}

void writeStudentInfoToFile(FILE *file,Student *student){
    fprintf(file,"姓名 ：%s\n",student->name);
    fprintf(file,"学号 ：%s\n",student->id);
    fprintf(file,"成绩：");
    for(int i=0;i<5;i++){
        fprintf(file,"%.2f",student->grades[i]);
    }
    fprintf(file,"\n\n");
}


int main(int argc,char *argv[]){
    const char *filename = argv[1];
    FILE *file = fopen(filename,"w");
    checkFile(file);
    Student student[5];
    for(int i=0;i<5;i++){
        intputStudent(&student[i]); //输入
        writeStudentInfoToFile(file,&sutdent[i]); //写入文件
    }

    fclose(file);
}

五、1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MaxNameLen 50
#define MaxAddr 100
#define MaxMajor 200
#define MaxLine 200

typedef struct{
    char name[MaxNameLen];
    int id;
    char gender[10];
    int age;
    char address[MaxAddr];
    char health[20];
    char major[MaxMajor];
} Student;


//将学生信息拿出来，将部分信息放入目标文件
void extracStudentInfo(const char *sourceFile,const char *targetFile){
    FILE *gstudentFile = fopen(sourceFile,"r");
    FILE *studentFile = fopen(targetFIle,"w");
    if(gstudentFile == NULL || studentFile == NULL){
        perror("error openFile");
        exit(1);
    }
    Student studet;

    //读取学生信息
    while(fscanf(gstudentFile,"%s %d %s %d %s %s %s",student.name,&student.id,student.gender,&student.age,student.address,student.health,student.major)!=EOF){
        fprintf(studentFile,"%d %s\n",student.id,student.major);
    }
    fclose(gstudentFile);
    fclose(studentFile);
    printf("简明学生信息已生成至 %s文件\n",targetFile);
}

void deleteStudent(char *filename,int deleteId){
    FILE *studentFile = fopen(filename,"r");
    FILE *tempFile = fopen("temp.txt","w");
    if(studentFile == NULL){
        error("Error open file");
        exit(1);
    }
    int id;
    char major[MaxMajor];
    while(fscanf(studentFile,"%d %s",&id,major)!=EOF){
        if(id != deleteId){
            fprintf(tempFile,"%d %s\n",id,major);
        }
    }
    fclose(studentFile);
    fclose(tempFile);
    remove(filename);
    rename("temp.txt",filename);
    printf("指定学号学生信息已经删除");
}

int main(){
    const char *sourceFile = "gstudent.txt";
    const char *targetFile = "student.txt";
    extracStudentInfo(sourceFile,targetFile);
    deleteStudent(targetFile,3);
    return 0;
}

五、2 力扣 72 题 ->编辑距离

int minDistance(char* word1, char* word2) {
    int len1 = strlen(word1);
    int len2 = strlen(word2);

    int dp[len1+1][len2+1];
    for(int i=0;i<=len1;i++){  //word2为空时，执行删除操作，所以多少个字符就执行多少次
        dp[i][0] = i;
    }
    for(int j=0;j<=len2;j++){  //word1为空时，执行插入操作，所以多少个字符就执行多少次
        dp[0][j] = j;
    }

    //计算dp数组
    for(int i=1;i<=len1;i++){
        for(int j=1;j<=len2;j++){
            if(word1[i-1] == word2[j-1]){ //相等时不用执行操作
                dp[i][j] = dp[i-1][j-1];
            }else{
                dp[i][j] = 1 + fmin(dp[i-1][j-1],fmin(dp[i-1][j],dp[i][j-1])); //不相等执行一次操作+加上前面执行三种才做的最小值
            }
        }
    }
    return dp[len1][len2];

}

模拟卷 二

四 1、最大连续字段和，用递归实现

思路：分治法求两边，然后再跟中间比

#include <stdlib.h>  // 要使用max记得引入这个包
#include <math.h>    // 引入math.h以使用-INFINITY
#include <limits.h>  // 引入limits.h用于INT_MIN

int Aleft(int arr[], int left, int mid) {
    int max_sum = 0;
    int sum = 0;
    for (int i = mid; i >= left; i--) {
        sum = sum + arr[i];
        if (sum >= max_sum) {
            max_sum = sum;
        }
    }
    return max_sum;
}

int Aright(int arr[], int mid, int right) {
    int max_sum = 0;
    int sum = 0;
    for (int i = mid; i <= right; i++) {
        sum += arr[i];
        if (sum > max_sum) {
            max_sum = sum;
        }
    }
    return max_sum;
}

int maxSubSum(int arr[], int left, int right) {
    if (left > right) return -INFINITY;
    if (left == right) return arr[left];  // 修改为arr[left]，而不是arr[0]
    int mid = (left + right) / 2;

    // 左右最大值
    int leftsum = maxSubSum(arr, left, mid);
    int rightsum = maxSubSum(arr, mid + 1, right);

    // 中间部分最大值
    int S1 = Aleft(arr, left, mid);
    int S2 = Aright(arr, mid + 1, right);
    return fmax(fmax(leftsum, rightsum), S1 + S2);  // 使用fmax代替max
}

四 2、输入 A 和 B 两个整数实现输出整数和得 D 进制数。 例如 123+456 -> 八进制数是 1103

#include <stdio.h>
void convertToBaseD(int num,int base){
    int result[32];
    int index = 0;
    if(num == 0){
        printf("0");
        return 0;
    }
    while(num>0){
        result[index++] = num%base;
        num/=base;
    }
    for(int i=index-1;i>=0;i--){
        printf("%d",result[i]);
    }
}

四 3、

#include <stdio.h>

int main(){
    int i;
    for(i=0;;i++){
        if((((i*8+7)*8+1)*8+1) == ((*34+15)*17+4)){
            printf("%d",((34*i)+15)*17+4);break;
        }
    }
    return 0;
}

五 1、

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

#define MaxWordLength 100
#define MaxWords 1000

typedef struct {
    char word[MaxWordLength];
    int count;
} WordCount;

// 转小写
void toLowerCase(char *str){
    for(int i = 0; str[i]; i++){
        str[i] = tolower(str[i]);
    }
}

// 查找单词
int findWord(WordCount words[], int wordCount, char *word){
    for(int i = 0; i < wordCount; i++){
        if(strcmp(words[i].word, word) == 0){
            return i;
        }
    }
    return -1; // 不存在
}

int main(){
    char filename[100];
    printf("请输入文件名：");
    scanf("%s", filename);
    FILE *file = fopen(filename, "r");
    if(file == NULL){
        printf("无法打开文件\n");
        return 1;
    }

    WordCount words[MaxWords] = {0};
    int wordCount = 0;
    char tempWord[MaxWordLength];
    while(fscanf(file, "%s", tempWord) != EOF){
        int j = 0;
        for(int i = 0; tempWord[i]; i++){
            if(isalpha(tempWord[i])){
                tempWord[j++] = tolower(tempWord[i]);
            }
        }
        tempWord[j] = '\0';

        if (strlen(tempWord) > 0) { // 如果单词不为空
            int index = findWord(words, wordCount, tempWord); // 查找单词
            if (index != -1) { // 如果单词已存在
                words[index].count++; // 更新单词计数
            } else if (wordCount < MaxWords) { // 如果单词不存在且数组未满
                strcpy(words[wordCount].word, tempWord); // 保存新单词
                words[wordCount].count = 1; // 初始化计数为1
                wordCount++; // 更新单词数量
            }
        }
    }

    printf("输出结果：\n");
    for(int i = 0; i < wordCount; i++){
        printf("%s: %d\n", words[i].word, words[i].count);
    }

    fclose(file);
    return 0;
}

五 2、零钱兑换

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

int coinChange(int coins[], int coinsSize, int amount) {
    int dp[amount + 1]; // dp[i]表示凑成金额i所需的最少硬币数

    // 初始化动态规划数组，设定一个无法达到的值(amount+1)作为初始值
    for (int i = 0; i <= amount; i++) {
        dp[i] = amount + 1;
    }
    dp[0] = 0;  // 凑成金额0所需硬币数为0

    // 遍历从1到amount的每个金额
    for (int i = 1; i <= amount; i++) {
        // 遍历硬币面值数组
        for (int j = 0; j < coinsSize; j++) {
            // 如果当前金额减去硬币面值不小于0，说明可以使用该硬币
            if (i - coins[j] >= 0) {
                dp[i] = dp[i - coins[j]] + 1 < dp[i] ? dp[i - coins[j]] + 1 : dp[i]; // 更新dp[i]
            }
        }
    }

    // 如果dp[amount]仍然是初始值(amount+1)，说明无法凑出该金额
    if (dp[amount] == amount + 1) {
        return -1;
    } else {
        return dp[amount];
    }
}

int main() {
    int coins[] = {1, 2, 5}; // 定义硬币面值数组
    int amount = 11;         // 目标金额
    int coinsSize = sizeof(coins) / sizeof(coins[0]); // 计算硬币数组长度
    int result = coinChange(coins, coinsSize, amount); // 调用函数计算结果

    // 输出结果
    if (result != -1) {
        printf("凑成%d金额需要：%d枚硬币\n", amount, result);
    } else {
        printf("无法凑出\n");
    }
}


//练习处

模拟卷 三

四 1、

#include <stdio.h>

int compute(int arr[],int n){
    int zhuSum=0,fuSum=0;
    for(int i=0,j=n-1;i<n;i++,j--){
        zhuSum+=a[i][i];
        fuSum+=a[i][j];
    }
    
}

int main(){
    int n;
    printf("请输入方阵的n:");
    scanf("%d",&n);
    int arr[n][n];
    printf("输入方阵的值")
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a[i]);
        }
    }
    compute(arr,n);
}

四2、

#include <stdio.h>

int isSymmetry(int arr[],int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(arr[i][j] != arr[j][i]){
                return false;
            }
        }
    }
    return true;
}

int main(){
    int n;
    printf("请输入方阵的n:");
    scanf("%d",&n);
    int arr[n][n];
    printf("输入方阵的值")
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&a[i]);
        }
    }
    if(isSymmetry(arr,n)){
        printf("YES");
    }else{
        printf("NO");
    }
}

四3、

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

typedef struct TreeNode{
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode;

TreeNode *buildTree(char inOrder[],char postOrder[],int inStart,int inEnd,int *postInder){
    if(inStart > inEnd){
        return NULL;
    }

    //创建当前树根节点
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = postOrder[*postIndex]; //后序当前值就是根节点
    (*postIndex)--;

    //如果当前字数只有一个结点，直接返回
    if(inStart == inEnd){
        root->left = root->right==NULL;
        return root;
    }

    //中序遍历中找到根节点位置
    int inIndex;
    for(inIndex = inStart;inIndex<=inEnd;inIndex++){
        if(inOrder[inIndex] == root->data){
            break;
        }
    }

    root->right = buildTree(inOrder,postOrder,inIndex+1,InEnd,postIndex);

    root->left = buildTree(inOrder,postOrder,inStart,inIndex-1,postIndex);

    return root;

}

//先序遍历
void perOrder(TreeNode *root){
    if(root==NULL){
        return ;
    }
    printf("%c",root->data);
    perOrder(root->left);
    perOrder(root->right);
}

int main() {
    // 示例输入
    char inOrder[] = {'D', 'B', 'E', 'A', 'F', 'C'};
    char postOrder[] = {'D', 'E', 'B', 'F', 'C', 'A'};
    int length = sizeof(inOrder) / sizeof(inOrder[0]);

    // 从后序数组最后一个元素开始构建二叉树
    int postIndex = length - 1;
    TreeNode *root = buildTree(inOrder, postOrder, 0, length - 1, &postIndex);

    // 验证：前序遍历输出
    printf("前序遍历结果: ");
    preOrder(root);

    return 0;
}

五1、 图连通分量个数 (一次深度遍历表示一个连通分量)

邻接矩阵方式

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

#define MAX_NODES 100 //假设图的最大节点数为100
int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];

int V; //顶点个数

void DFS(int v){
    visited[v] = true;
    for(int i=0;i<V;i++){
        if(graph[v][i] == 1 && !visited[i]){
            DFS[i];
        }
    }
}

//求连通分量个数
int connectedComponents(){
    int count = 0;
    for(int i=0;i<V;i++){
        if(!visited[i]){
            DFS(i);
            count++;
        }
    }
    return count;
}

邻接表的写法

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

#define MAX_V 1000

typedef struct ANode {
    int V;                  // 顶点编号
    struct ANode* next;     // 指向下一个节点
} Node;

Node* adjList[MAX_V];       // 邻接表
int visited[MAX_V];         // 访问标记数组

// 深度优先搜索
void DFS(int v) {
    visited[v] = 1;         // 标记当前顶点已访问
    Node* temp = adjList[v];
    while (temp != NULL) {
        int u = temp->V;    // 获取当前邻接顶点
        if (!visited[u]) {  // 如果未访问，继续递归
            DFS(u);
        }
        temp = temp->next;
    }
}

// 计算连通分量数量
int connectedComponents(int n) {
    int count = 0;
    for (int i = 0; i < n; i++) {
        visited[i] = 0;     // 初始化访问标记
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {  // 如果顶点未访问
            DFS(i);         // 从当前顶点开始DFS
            count++;        // 连通分量计数加一
        }
    }
    return count;
}

// 辅助函数：添加边
void addEdge(int u, int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->V = v;
    newNode->next = adjList[u];
    adjList[u] = newNode;

    // 如果是无向图，还需要添加反向边
    newNode = (Node*)malloc(sizeof(Node));
    newNode->V = u;
    newNode->next = adjList[v];
    adjList[v] = newNode;
}

int main() {
    int n = 6; // 顶点数
    for (int i = 0; i < n; i++) {
        adjList[i] = NULL; // 初始化邻接表
    }

    // 添加边
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(3, 4);
    addEdge(5, 5); // 顶点5单独形成一个连通分量

    int components = connectedComponents(n);
    printf("连通分量的数量是: %d\n", components);

    return 0;
}

五2、N皇后问题

#include <iostream>
#include <vector>  //使用动态数组需要引入<vector>    一般定义 vector<int> nums;    二维定义：vector<vector<string>> result;     push_back()来添加数据
using namespace std;
vector<vector<string>> result;    //二维动态数组<这里是类型>   利用push_back添加数据

bool isvalid(int n,int row,int col,vector<string> &chessboard);

void backtracking(int n,int row,vector<string> &chessboard){ 
    if(row == n){
        result.push_back(chessboard);
        return;
    }
    for(int col=0;col<n;col++){
        if(isvalid(n,row,col,chessboard)){
            chessboard[row][col] = 'Q';
            backtracking(n,row+1,chessboard);
            chessboard[row][col] = '.'; //回溯后撤销
        }
    }
}
bool isvalid(int n,int row,int col,vector<string> &chessboard){ //检查是否可以插入

    for(int i=0;i<row,i++){ //检查行和列
        if(chessboard[i][col] == 'Q'){
            return false;
        }
    }

    for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){ //主对角
        if(chessboard[i][j] == 'Q'){
            return false;
        }
    }

    for(int i=row-1,j=col+1;i>=0&&j<n;i--;j++){ //副对角
        if(chessboard[i][j] == 'Q'){
            return false;
        }
    }

    return true;
}

int main(){
    int N;
    cin>>N;
    vector<string> chessboard(N,string(N,'.'));
    backtracking(N,0,chessboard);
    for(int i=0;i<result.size();i++){
        for(int j=0;result.size();j++){
            cout<<"["<<result[i][j]<<"]"<<endl;
        }
        cout<<endl;
    }
    return 0;
}

模拟卷四

四1、

#include <stdio.h>

void reverse(char arr[]){
    int len = 0;
    while(arr[len] != '\0'){
        len++;
    } 
    int head=0,tail=len-1;
    char temp;
    for(head=0;head<tail;head++,tail--){
        temp = arr[head];
        arr[head] = arr[tail];
        arr[tail] = temp;
    }
}

void toggle(char arr[]){
    int i=0;
    while(arr[i]!='\0'){
        if(arr[i]>='A' && arr[i]<='Z'){
            arr[i]+=32;
        }
        if(arr[i]>='a' && arr[i]<='z'){
            arr[i]-=32;
        }
        i++;
    }
}

int main(){
    double (* funStr)(char *);
    char arr[]="123ABcde";
    funStr = reverse;
    (* funStr)(arr);
    printf("反转后：%s",arr);
    funStr = toggle;
    (* funStr)(arr);
    printf("大小写转换后：%s",arr);
}

四2、

#include <stdio.h>

int fun(int n){
    if(n==1){
        return 1;
    }else{
        return n*fun(n-1);
    }
}

int main(){
    int count = fun(5);
    printf("五的阶层：",count);
}

四3、

#include <stdio.h>

int main(){
    int num;
    printf("请输入不超过三位的正整数")；
    scanf("%d",&num);
    int nums[3],int k=0;
    num[0] = num/100;
    num[1] = num/10%10;
    num[2] = num%10;
    for(int i=0;i<nums[0];i++){
        printf("B");
    }
    for(int i=0;i<num[1];i++){
        printf("S");
    }
    for(int i=1;i<=num[2];i++){
        printf("%d",i);
    }
}

五、1

#include <stdio.h>

typedef struct TreeNode{
    char data;
    struct TreeNode *firstChild; //左孩子
    struct TreeNode *nextSilibing; //右兄弟
}TreeNode;

int countLeafNodes(TreeNode *root){
    if(root == NULL){
        return 0;
    }
    if(root->firstChild == NULL){
        return 1+countLeafNodes(root->nextSilibing); //当前结点是叶子结点+兄弟的叶子结点
    }
    return countLeafNodes(root->fristChild)+countLeafNodes(root->nextSilibing);  //左孩子叶子结点+兄弟叶子结点
}

五2、

模拟卷 五

四1、

#include <stdio.h>

int main(){
    char filename1[10],filename2[10];
    printf("请输入两个文件名字：");
    scanf("%s %s",filename1,filename2);

    FILE *file1 = fopen(filename1,"r");
    FILE *file2 = fopen(filename2,"w");

    if(file1 == NULL || file2==NULL){
        printf("文件打开失败");
        return 0;
    }

    char arr[1024];
    int lineCount = 0;
    while(fgets(arr,1024,file1) !=NULL){
        lineCount++;
        fscanf(file2,"第%d行：%s",&lineCount,arr);
    }

    fclose(file1);
    fclose(file2);

    return 0;
}

四2、最小公倍数

#include <stdio.h>

// 计算两个数的最大公约数（递归实现）
int gcd(int a,int b){
    return b == 0 ? a : gcd(b, a % b);
}

// 计算两个数的最小公倍数
int lcm(int a, int b) {
    return (a / gcd(a, b)) * b;  // 先除后乘避免溢出
}

int main() {
    int a, b;
    printf("请输入两个正整数: ");
    scanf("%d %d", &a, &b);

    if (a <= 0 || b <= 0) {
        printf("输入的数必须是正整数。\n");
        return 1;
    }

    printf("最小公倍数是: %d\n", lcm(a, b));

    return 0;
}

四4、

#include <stdio.h>

typedef struct LNode{
    int data;
    struct LNode *next;

}LNode,*LinkList;

bool hasCycle(LinkList L){
    LNode *fast = L;
    LNode *slow = L;
    while(fast!=NULL && fast->next!=NULL){
        fast=fast->next->next;
        slow = slow->next;
        if(fast == slow){
            return true;
        }
    }
    return false
}

四 5、

#include <stdio.h>

struct TreeNode{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
}


int deepMax(struct TreeNode *root){
    if(root==NULL){
        return 0;
    }
    int leftCount = deepMax(root->left);
    int rightCount = deepMax(root->right);
    return (leftCount>rightCount?leftCount:rightCount)+1;
}

四6、

这也算题，三研 真是天才

#include <iostrem>

class ShapeCalculator{
    public:
        float CaculatorAreaOfCircle(float r) return 3.14*r*r;
        float CaculatorPerimeterOfRectangle(float width,float length) reutrn 2*(width+length);
        float CaculatorAreaCube(float length) return length*length*length;
}

五1、旋转矩阵

旋转九十度

思路：先转置，再中心对称过去即可，用代码实现即可

#include <stdio.h>


void rotate(int arr[][],n){
    int temp;
    for(int i=0;i<n;i++){    //转置
        for(int j=i;j<n;j++){
            temp = arr[i][j];
            arr[i][j] = arr[j][i];
            arr[j][i] = temp;
        }
    }

    for(int i=0;i<n;i++){ //中间对称过去
        int l=0,r = n-1;
        while(l<r){
            temp = arr[i][l];
            arr[i][l] = arr[i][r];
            arr[i][r] = temp;
        }
    }
}

int main(){
    int n;
    scanf("%d",&n);
    int arr[n][n];
    printf("请输入矩阵数据");
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            scanf("%d",&arr[i][j]);
        }
    }

    rotate(arr,n);
}

五2、

写烦了不想写了

模拟卷 六

四1、

思想：当快慢指针相遇，让其中一个指针指向头节点，两个指针依次向后移动相遇时就是环的入口

#include <stdio.h>


typedef struct LNode{
    int data;
    struct LNode *next;    
}LNode,*LinkList;

LNode* entcircle(LinkList L){
    LNode *fast=L,*slow=L;
    while(fast!=NULL && fast->next !=NULL){
        fast=fast->next->next;
        slow=slow->next;
        if(slow == fast){ //有环
            slow = L;
            while(slow!=fast){
                slow=slow->next;
                fast=fast->next;
                if(slow==fast){
                    return slow;
                }
            }
        }
    }

    return NULL;
}

int main(){

    LinkList L;
    entcircle(L);
    return 0;
}

四2、

搜索树：左 小于 中，右 大于 中

递归遍历将值传递进去

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
}

bool isSearch(TreeNode *root,int min,int max){
    if(root == NULL){
        return true;
    }
    if(root->left-val >min || root->right->val <max){
        return false;
    }
    return isSearch(root->left,min,root->val) && isSearch(root->right,root->val,max);
}

四3、

平衡二叉树：左右子树深度差不超过1

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
}

int deep(TreeNode *root){
    if(root == NULL){
        return 0;
    }
    int leftDeep = deep(root->left);
    int rightDeep = deep(root->right); 
    return (leftDeep>rightDeep?leftDeep:rightDeep)+1;
}

bool isbalance(TreeNode *root){
    if(root == NULL){
        return true;
    }
    int leftDeep = deep(root->left);
    int rightDeep = deep(root->right);
    int num = leftDeep-rightDeep;
    if(abs(num)>1){
        return false;
    }
    return isbalace(root->left) && isbalace(root->right);
}

五1、

就是搞一个结构体，里面存放函数指针，然后不同的类型复制不同的函数实现

函数指针 类型 (* funname)(参数列表);

#include <stdio.h>

typedef struct ImageProcessor{
    void (*readImage)(const char* filename);
    void (*displayImage);
}

void readJEPGImage(const char *filename){
    printf("读取JPEG image:%s",filename);
}
void displayJPEGImage(){
    printf("展示JPEGimage image.\n");
}
void readPNGImage(const char* file){
    printf("读取PNG图像文件");
}
void displayPNGImage(){
    printf("展示PNG文件");
}

int main(){
    const char *jpegFilename = "image.jpg";
    const char *pngFilename = "image.png";
    ImageProcessor jpegProcessor = {readJEPGImage,displayJPEGImage};
    jpegProcessor.readImage(jpegFilename);
    jpegProcessor.displayImage(jpegFilename);

    ImageProcessor pngProcessor = {readPNGImage,displayPNGImage};
    jpegProcessor.readImage(pngFilename);
    jpegProcessor.displayImage(pngFilename);
}

六2、

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

int main(){
    
    char str[100];
    printf("请输入");
    scanf("%s",str);
    int n = strlen(str);

    int dp[n][n];
    for(int i=0;i<n;i++) dp[i][i] = 1; //初始化为1
    for(int i=n-1;i>=0;i--){
        for(int j=i+1;j<n;j++){
            if(s[i] == s[j]) dp[i][j] =dp[i+1][j-1]+2;
            else dp[i][j] = dp[i][j-1]>dp[i+1][j]?dp[i][j-1]:dp[i+1][j];
        }
    }

    printf("%d",dp[0][n-1]);
    return 0;
}

模拟卷 七

四1、

#include <stdio.h>

struct TreeLinkNode{
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
}

struct TreeLinkNode* getmindNext(struct TreeLinkNode* pNode){
    struct TreeLinkNode *temp;
    if(!pNode) return pNode;
    if(pNode->right == NULL){
        temp = pNode->next;
        if(pNode == temp->left) return pNode->next;
        pNode = pNode->next;
    }else{ //右子树最左结点
        temp = pNode->right;
        while(temp){
            temp = tmep->left;
        }
    }
}

四2、

#include <stdio.h>

typedef struct node{
    int weight;
    struct node *left;
    struct node *right;
}Tree;

int getWPL(Tree root,int deepth){
    if(root==NULL){
        return 0;
    }
    if(root->left && root->right){
        return root->weight*deepth;
    }
    return getWPL(root->left,deepth+1) + getWPL(root->right,deepth+1);
}

四3、 邻接矩阵转换邻接表

请仔细理解这下面得结构体


// 邻接表中的边结点结构体
typedef struct ANode {
    int adjvex;            // 边所指向的结点的编号（顶点位置）
    struct ANode *nextarc; // 指向下一个边结点的指针，用于链接其他边
} ANode, *Node;             // ANode是边结点结构体的别名，Node是指向ANode的指针类型

// 邻接表中的顶点结点结构体
typedef struct {
    int data;              // 顶点的数据（例如顶点的标识）
    ANode *firstarc;       // 指向该顶点的第一条边（邻接点）的指针
} Vnode;

// 图结构体，使用邻接表表示
typedef struct {
    int numver, numedg;    // numver表示顶点数，numedg表示边数
    Vnode adjList[maxsize]; // 邻接表数组，存储图中所有顶点和它们的边
} Graph;

// 邻接矩阵结构体
typedef struct {
    int numver, numedg;               // numver表示顶点数，numedg表示边数
    int verticle[maxsize];            // 存储顶点的数组
    int Edge[maxsize][maxsize];       // 邻接矩阵，存储图中顶点之间的边（0表示无边，非0表示有边）
} mGraph;




void MattoList(MGraph A,ALGraph *B){
    B->verNum = A.verNum;
    B->edgNum = A.edgNum;
    
    for(int i=0;i<A.verNum;i++){
        B->adjList[i].vertex = A.vex[i];
        B->adjList[i].first = NULL;
    }

    for(int i=0;i<A.verNum;i++){
        for(int j=0;j<A.verNum;j++){
            if(A.verticle[i][j] != 0){  
                ANode *p = (ANode *)malloc(sizeof(ANode));
                p->adjvex = j;
                p->next = B->adjlist[i].first;  //头插法
                B->adjList[i].first = p;
            }
        }
    }


}

五1、

#include <stdio.h>

struct TreeNode{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
}

struct TreeNode* getCommon(struct TreeNode *root,int o1,int o2){
    if(root==NULL){
        return NULL;
    }
    if(root->val == o1 || root->val == o2){
        return root;
    }
    struct TreeNode *letCommon = getCommon(root->left,o1,o2);
    struct TreeNode *rightCommon getCommon(root->right,o1,o2);
    if(leftCommon && rightCommon){
        return root;
    }
    return letCommon?letCommonL:rightCommon;
}