408数据结构常考算法基础训练

• 408相关：
  • 408数据结构错题知识点拾遗
    • 408数据结构常考算法基础训练
  • 408计算机组成原理错题知识点拾遗
  • 408操作系统错题知识点拾遗等待完善
  • 408计算机网络错题知识点拾遗
    • 408计算机网络各层协议简记等待完善

该训练营为蓝蓝考研（蓝颜知己）的算法训练营内容，题目来源有经典算法题、408统考算法题等等。分为7weeks共计39days练习，每日一道算法题训练，涵盖基本顺序表、链表和二叉树相关的基础算法，以及部分408真题中数据结构部分的算法题，并未包含图相关的算法，还需要进一步对图算法自行学习。 当然，对于顺序表、链表和二叉树的算法，也需要继续通过课后习题进行练习和巩固。
github项目地址–AlgorithmTrainingCamp

• 目录

如果时间充裕，可以前期进行PC端练习，后期再尝试完全在纸上进行手写练习；如果时间紧张则不建议PC端练习，直接手写。
个人最初是使用的Clion进行coding练习的，所以这些题目是可以成功测试运行的。所涉及的相关结构体及函数定义如下所示：

• 线性表List
  • 顺序表SqList
    • 头文件SqList.h

// SqList.h
// Created by Giperx on 2023/7/24.
//
#ifndef ALGCAMP_SEQLIST_H
#define ALGCAMP_SEQLIST_H
// 顺序表
typedef struct SqList{
   
 int data[100];
 int length;
}SqList;
// 初始化顺序表
void initSqList(SqList &list);
// 打印输出顺序表
void printSqList(SqList &list);
#endif //ALGCAMP_SEQLIST_H

• 线性表List
  • 顺序表SqList
    • SqList.cpp

//SqList.cpp
// Created by Giperx on 2023/7/27.
//
#include <iostream>
#include "SqList.h"
using namespace std;
void initSqList(SqList &list){
   
    cout << "enter length of SqList:";
    cin >> list.length;
    cout << "enter values of SqList:";
    for(int i = 0; i < list.length; i ++) cin >> list.data[i];
}
void printSqList(SqList &list){
   
    cout << "length: " << list.length << endl;
    for(int i = 0; i < list.length; i ++) cout << list.data[i] << ' ';
    cout << endl;
}

• 线性表List
  • 链表LinkList
    • 头文件LinkList.h

//LinkList.h
// Created by Giperx on 2023/8/15.
//
#ifndef ALGCAMP_LINKLIST_H
#define ALGCAMP_LINKLIST_H
typedef struct LNode{
   
    int data;
    struct LNode *next;
    LNode(int val){
   
        data = val;
        next = nullptr;
    }
}LNode, *LinkList;
// 初始化链表，带头结点
bool initLinkList(LinkList& L);
// 计算链表长度(不包括头结点)
int lengthofLinkList(LinkList& L);
// 输出链表信息
void printLinkList(LinkList& L);
#endif //ALGCAMP_LINKLIST_H

• 线性表List
• 链表LinkList
  • LinkList.cpp

//LinkList.cpp
// Created by Giperx on 2023/8/15.
//
#include "LinkList.h"
#include "malloc.h"
#include "iostream"
using namespace std;

// 初始化链表，带头结点
bool initLinkList(LinkList& L){
   
    L = (LNode*)malloc(sizeof (LNode));
    if (!L) return false;
    L->next = nullptr;
    return true;
}
// 计算链表长度(不包括头结点)
int lengthofLinkList(LinkList& L){
   
    int length = 0;
    if (!L){
   
        cout << "nullptr!" << endl;
    } else if (!L->next) {
   
        cout << "have not node!" << endl;
    } else {
   
        LNode *p = L->next;
        while (p){
   
            length++, p = p->next;
        }
    }
    return length;
}
// 输出链表信息
void printLinkList(LinkList& L){
   
    if (!L) cout << "nullptr!" << endl;
    else if (!L->next) cout << "have not node!" << endl;
    else{
   
        cout << "length of LinkList:" << lengthofLinkList(L) << endl;
        LNode *p = L->next;
        while (p){
   
            cout << p->data << ' ';
            p = p->next;
        }
        cout << endl;
    }
}

• 二叉树
  • BiTree.h

//BiTree.h
// Created by Giperx on 2023/8/24.
//
#ifndef ALGCAMP_BITREE_H
#define ALGCAMP_BITREE_H
// 二叉树
typedef struct BiNode{
   
    char data;
    struct BiNode* left, *right;
}BiNode, *BiTree;
#endif //ALGCAMP_BITREE_H

• 二叉树
  • BiTree.cpp

//BiTree.cpp
// Created by Giperx on 2023/8/24.
//
#include "BiTree.h"

• week1 回到目录

day1 累加求和 参考作答

简单的for循环实现累计求和：1+2+3+4+…+10

day2 字符串反转 参考作答

day3 顺序表删除最小并用尾数填补 参考作答

• week2 回到目录

day4 顺序表逆置 参考作答

day5 删除所有值为x的元素 参考作答

day6 删除下标范围内所有元素 参考作答

day7 依照表头元素划分数组为左小右大两半 参考作答

day8 删除给定元素值范围内所有元素 参考作答

day9 有序顺序表去重 参考作答

• • week2小结
    day04 - day09

主要是双指针的运用，day04顺序表逆置，左右交换；

day06删除下标范围内的元素，相当于两顺序表的前后合并；

day05删除所有值为x的元素、day08删除值范围内的元素、day09有序表去重是相同的，双指针，一个负责记录位置，一个负责移动判断。只不过前两个的判定对比是定下来的元素，去重则是每次判定对比的元素可能会发生变化，也就是最近的一个元素；

day07依表头划分左右两半partition实际上是快排算法的基础，通过双指针和哨兵进行比较再交换。

• week3 回到目录

待续……

参考作答

• week1 回到题目

day1 回到题目

#include<stdio.h>
int main(){
   
    int sum = 0;
    for(int i = 1; i <= 10; i ++){
   
        sum += i;
    }
    printf("%d", sum);
    return 0;
}

day2 回到题目

#include<iostream>
#include<cstring>
using namespace std;
int main(){
   
    char str[1001];
    cin >> str;
    for(int i = std::strlen(str) - 1; i >= 0; i --){
   
        cout << str[i];
    }
    return 0;
}

实际上，C语言中可以利用string.h中的strrev(char*)函数进行反转。

#include<string.h>
strrev(str)

C++中algorithm头文件中的reverse(_BIter, _BIter)也可以对stringvector也可以实现反转。

#include<algorithm>
reverse(str.begin(), str.end())

day3 回到题目

思路

• 遍历顺序表，同时记录下每次最小的元素的值和下标位置,最后用尾部元素填补，并返回值。

答案

#include <iostream>
#include <vector>
using namespace std;
int removeMinValue(vector<int>& sequence) {
   
    if (sequence.empty()) {
   
        cerr << "顺序表为空！" << endl;
        return -1; // 返回-1表⽰错误
    }
    int minInd = 0;
    int minVal = sequence[0];
    for (int i = 1; 1 < sequence.size(); i++) {
   
// ⽐较获取最⼩值和其索引
        if(sequence[i] < minVal) {
   
            minVal = sequence[i];
            minInd = i;
        }
    }
    int deletedVal = sequence[minInd];
    sequence[minInd] = squence.back(); // 最后⼀个元素填补删除位
    sequence.pop_back(); //删除最后⼀个元素
    return deletedVal; // 返回删除值
}

待续……