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

本文主要是介绍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;
}

#include<string.h>
strrev(str)

#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; // 返回删除值
}

这篇关于408数据结构常考算法基础训练的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！