DS复习提纲模版
数组的插入删除
int SeqList::list_insert(int i, int item) { //插入
if (i < 1 || i > size + 1 || size >= maxsize) {
return 0; // Invalid index or list is full
}
for (int j = size-1; j >= i-1; j--) { // Shift elements to the right
list[j+1] = list[j];
}
list[i - 1] = item; // Insert the item at position i-1
size++; // Increase size
return 1;
}
int SeqList::list_del(int i) { //删除
if (i < 1 || i > size) {
return 0; // Invalid index
}
for (int j = i; j < size; j++) { // Shift elements to the left
list[j-1] = list[j];
}
size--; // Decrease size
return 1;
}链表操作
#include <iostream>
using namespace std;
#define ok 0
#define error -1
//链表结点类定义
class ListNode {
public:
int data;
ListNode* next;
ListNode() : data(0), next(NULL) {}
};
//带头结点的单链表定义
class LinkList {
public:
ListNode* head;
int len;
LinkList() : head(new ListNode()), len(0) {}
~LinkList();
ListNode* LL_index(int i);
int LL_get(int i);
int LL_insert(int i, int item);
int LL_del(int i);
void LL_display();
};
LinkList::~LinkList() {
ListNode* p, * q;
p = head;
while (p != NULL) {
q = p;
p = p->next;
delete q;
}
len = 0;
head = NULL;
}
void LinkList::LL_display() {
ListNode* p = head->next;
while (p) {
cout << p->data << ' ';
p = p->next;
}
cout << endl;
}
ListNode* LinkList::LL_index(int i) {
int h = 0;
ListNode* p = head;
while (p && h < i) {
p = p->next;
h++;
}
return p;
}
int LinkList::LL_insert(int i, int item) {
if (i < 0 || i > len)
return error;
ListNode* p = head;
for (int h = 0; h < i; ++h) {
p = p->next;
}
ListNode* s = new ListNode();
s->data = item;
s->next = p->next;
p->next = s;
++len;
return ok;
}
int LinkList::LL_get(int i) {
if (i < 1 || i > len)
return error;
ListNode* p = head->next;
for (int h = 1; h < i; ++h) {
p = p->next;
}
return p->data;
}
int LinkList::LL_del(int i) {
if (i < 1 || i > len)
return error;
ListNode* p = head;
for (int h = 0; h < i - 1; ++h) {
p = p->next;
}
ListNode* s = p->next;
p->next = s->next;//头尾相等 空
delete s;
--len;
return ok;
}
//两个节点交换位置 需要交换这两个节点的前驱跟后继指针来完成
void LinkList::swap(ListNode* p, ListNode* q) {
// 找到p和q的前驱节点
ListNode* prevP = head;
while (prevP != NULL && prevP->next != p) {
prevP = prevP->next;
}
ListNode* prevQ = head;
while (prevQ != NULL && prevQ->next != q) {
prevQ = prevQ->next;
}
// 如果p或q不在链表中，或者它们是头节点（没有前驱），则无法交换
if (prevP == NULL || prevQ == NULL) {
return;
}
if (p == NULL || q == NULL)
return;
//p q是相邻的
if (p->next == q) {
p->next = q->next;
q->next = p;
prevP->next = q;
}
else {
// 交换prevP和prevQ的下一个节点的指针
ListNode* temp = p->next;
p->next = q->next;
q->next = temp;
// 交换p和q的指针
temp = prevP->next;
prevP->next = prevQ->next;
prevQ->next = temp;
}
}
//链表的合并
ListNode* LL_merge1(ListNode* p, ListNode* q) {
ListNode* preHead = new ListNode();
ListNode* prev = preHead;
while (p && q) {
if (p->data < q->data) {
prev->next = p;
p = p->next;
}
else if (p->data > q->data) {
prev->next = q;
q = q->next;
}
else {
prev->next = q;
p = p->next;
q = q->next;
}
prev = prev->next;
}
prev->next = q ? q : p;//更长的那一段的剩余的直接截取接至新链表
//pre->next = p ? p : q;
return preHead->next;
}
//删除链表相同元素--与先存进来的元素互异后才可存入链表
#include<iostream>
using namespace std;
// 定义链表节点结构体LNode
typedef struct LNode {
int data; // 节点存储的数据
struct LNode* next; // 指向下一个节点的指针
} LNode, * Linklist; // LNode为节点类型，Linklist为指向节点的指针类型
int main() {
int t;
cin >> t; // 读取测试用例的数量
while (t--) { // 对每个测试用例进行处理
int n;
cin >> n; // 读取链表长度
Linklist L;
L = new LNode; // 创建头节点
L->next = NULL; // 初始化头节点的next指针为NULL
LNode* r = L; // r指针用于指向链表的最后一个节点
// 循环读取n个数据，并插入到链表中
for (int i = 0; i < n; i++) {
int num;
cin >> num; // 读取一个数据
LNode* tmp = L; // tmp指针用于遍历链表 L是一整个链表
bool dup = false; // 标记是否发现重复数据
// 遍历链表，检查num是否已存在
while (tmp) {
if (tmp->data == num) {
dup = true; // 发现重复数据
break; // 退出循环
}
tmp = tmp->next;
}
// 如果num已存在，则跳过插入操作
if (dup) {
continue;
}
else {
// 创建新节点并插入到链表末尾
r->next = new LNode;
r->next->data = num; // 设置新节点的数据
r = r->next; // 更新r指针
r->next = nullptr; // 设置新节点的next指针为NULL
}
}
// 计算链表长度
int len = 0;
LNode* p = L->next; // p指针用于遍历链表
LNode* q = L->next; // q指针也用于遍历链表
while (q != NULL) { // 遍历链表计算长度
q = q->next;
len++;
}
// 这里删除q是错误的，因为q已经是NULL，不需要删除
// delete q;
// 输出链表长度和链表数据
cout << len << ":";
while (p != NULL) { // 遍历链表并输出数据
cout << " " << p->data;
p = p->next;
}
// 这里删除p是错误的，因为p指向的是头节点的下一个节点
// 应该遍历整个链表并删除每个节点
// delete p;
cout << endl;
// 释放链表内存
LNode* toDelete = L;
while (toDelete != NULL) {
LNode* next = toDelete->next;
delete toDelete;
toDelete = next;
}
}
return 0;
}
栈（先进后出）
// 行编辑
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
string str;
cin >> str; // 把输入的字符串保存在变量str中
int len = str.length(); // 获取输入字符串的长度
stack<char> s;
for (int m = 0; m < len; m++) {
char ch = str[m]; // 读取当前字符
if (ch != '#') {
s.push(ch); // 如果不是 '#'，则压入栈 s
}
else if(ch=='#'&& !s.empty()){
s.pop();
}
}
if (s.empty()) {
cout << "NULL" << endl;
}
while (!s.empty()) {
cout << s.top();
s.pop();
}
cout << endl;
}
return 0;
}波兰式与逆波兰式
#include<iostream>
#include<string>
#include<stack>
using namespace std;
class Solution
{
private:
stack<string> nums; // 存储操作数, 实际上会存储操作符的
stack<char> op; // 存储操作符
// 逆向遍历时判断操作符优先级
bool opcmpRight(char op1, char op2)
{
// + - 的时候，只需要判断栈顶是否同级，逆序，同级新的优先级更高
if (op1 == '+' || op1 == '-')
{
return op2 == '+' || op2 == '-';
}
// * / 直接入栈
return true;
}
// 正向遍历时判断操作符优先级
bool opcmpLeft(char op1, char op2)
{
// 正向的时候，同级新的优先级会低
if (op1 == '*' || op1 == '/')
{
return op2 != '*' && op2 != '/';
}
return false;
}
public:
string poland(string s)// 求解波兰式
{
int len = s.length();
for (int i = len - 1; i >= 0; --i)
{
if (s[i] >= '0' && s[i] <= '9')
{
string num = "";
num += s[i];
while (i - 1 >= 0 && s[i - 1] >= '0' && s[i - 1] <= '9')
{
num = s[--i] + num;
}
nums.push(num);
}
else if (op.empty() || s[i] == ')' || op.top() == ')')
{
op.push(s[i]);
}
else if (s[i] == '(')
{
while (!op.empty() && op.top() != ')')
{
string ops = "";
ops += op.top();
nums.push(ops);
op.pop();
}
op.pop();
}
else if (opcmpRight(s[i], op.top()))
{
op.push(s[i]);
}
else
{
while (!op.empty() && !opcmpRight(s[i], op.top()))
{
string ops = "";
ops += op.top();
nums.push(ops);
op.pop();
}
op.push(s[i]);
}
}
while (!op.empty())
{
string ops = "";
ops += op.top();
nums.push(ops);
op.pop();
}
string ans = "";
while (!nums.empty())
{
ans += nums.top() + (nums.size() > 1 ? " " : "");
nums.pop();
}
return ans;
}
string antiPoland(string s)
{
int len = s.size();
string ans = "";
for (int i = 0; i < len; ++i)
{
if (s[i] >= '0' && s[i] <= '9')
{
ans += s[i];
while (i + 1 < len && s[i + 1] >= '0' && s[i + 1] <= '9')
{
ans += s[++i];
}
ans += " ";
}
else if (op.empty() || s[i] == '(' || op.top() == '(')
{
op.push(s[i]);
}
else if (s[i] == ')')
{
while (!op.empty() && op.top() != '(')
{
ans += op.top();
ans += " ";
op.pop();
}
op.pop();
}
else if (opcmpLeft(s[i], op.top()))
{
op.push(s[i]);
}
else
{
while (!op.empty() && !opcmpLeft(s[i], op.top()))
{
ans += op.top();
ans += " ";
op.pop();
}
op.push(s[i]);
}
}
while (!op.empty())
{
ans += op.top();
ans += op.size() > 1 ? " " : "";
op.pop();
}
return ans;
}
};
int main()
{
int t;
cin >> t;
while (t--)
{
Solution sol;
string s;
cin >> s;
cout << sol.poland(s) << endl;
cout << sol.antiPoland(s) << endl << endl;
}
return 0;
}
队列（先进先出）
#include<iostream>
#include<queue>
#include<utility>
#include<vector>
#include<iomanip>
#include<algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
// 用户队列
queue<pair<int, int>> customer;
for (int i = 0; i < n; i++)
{
int time1, time2;
cin >> time1 >> time2;
customer.push({ time1, time2 });
}
int k;
cin >> k;
// 初始化窗口
vector<int> windows(k, 0);
// 总时间，完成时间，和最大等待时间
int totalWaitTime = 0, finishTime = 0, maxWaitTime = 0;
while (!customer.empty())
{
int arriveTime = customer.front().first;
int takenTime = customer.front().second;
// 默认最早空闲的窗口的最小下标
int minIndex = 0;
for (int i = 0; i < k; ++i)
{
// 窗口在到达时间之前空闲
if (windows[i] <= arriveTime)
{
minIndex = i;
break;
}
// 动态更新下标
if (windows[i] < windows[minIndex])
{
minIndex = i;
}
}
// 最早空闲的窗口先于到达时间
if (windows[minIndex] <= arriveTime)
{
windows[minIndex] = arriveTime + takenTime;
}
// 否则则需要等待
else
{
int wait = windows[minIndex] - arriveTime;
windows[minIndex] += takenTime;
totalWaitTime += wait;
maxWaitTime = max(maxWaitTime, wait);
}
// 完成时间取最大值
finishTime = max(finishTime, windows[minIndex]);
customer.pop();
}
cout << fixed << setprecision(1) << (double)(totalWaitTime * 1.0 / n)
<< " " << maxWaitTime << " " << finishTime << endl;
return 0;
}串
//真前后缀
#include <iostream>
#include <string>
using namespace std;
string matchedPrefixPostfix(string str) {
int n = str.length();
string result = "empty";
if (n > 1) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= n - i - 1; ++j) {
string prefix = str.substr(0, i + 1);//提取子串 正向
string postfix = str.substr(n - j - 1, j + 1);// 提取子串 逆向
if (prefix == postfix) {
result = prefix;
}
}
}
}
return result;
}
int main() {
int t;
cin >> t;
while (t--) {
string str;
cin >> str;
cout << matchedPrefixPostfix(str) << endl;
}
return 0;
}查找
//直接插入排序
void InsertSort(int array[], int length) {
for (int i = 1; i < length; i++) { //第1个数是有序的，所以从第2个数开始遍历，依次插入
int j = i - 1; //前i-1个数都是有序序列(由小到大)，只要a[j]比temp大，就将此数后移
int temp = array[i]; //先将当前的数存储在temp后，以免后面移位被覆盖
for (j = i - 1; j >= 0 && array[j] > temp; j--) {//a[j]小于 temp 时循环结束，结束后应将 temp 赋值给a[j+1]
array[j + 1] = array[j]; //将 a[j] 后移一位
}
array[j + 1] = temp; //将 temp 赋值给a[j+1]
Print(array, length);
}
}
//希尔排序
void find(int* a, int n) {
int b = n / 2;
while (b >= 1) {
for (int i = b; i < n; i++) {
int tmp = a[i];
int j = i;
while (j >= b && a[j - b] < tmp) {
a[j] = a[j - b];
j -= b;
}
a[j] = tmp;
}
for (int i = 0; i < n-1; i++) {
cout << a[i] << " ";
}
cout << a[n-1]<<endl;
b = b / 2;
}
}
//冒泡排序
void bubble_sort(int * arr, int len)
{
int i, j;
int k = 0;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1])
{
swap(arr[j], arr[j + 1]);
k++;
}
cout << k << endl;
}
//快速排序
int Partition(int * &array, int low, int high){
int mid_key= array[low];//记录枢轴的值
while(low< high){
while(low< high&&array[high]>= mid_key )
high--;
array[low]= array[high];//大于枢轴的值前移
while(low< high&&array[low]<= mid_key)
low++;
array[high]= array[low]; //小于枢轴的值后移
}
array[low]= mid_key;//最后才将枢轴的值记录到位
return low; //返回枢轴的位置
}
void print(int * &array){//打印输出
for(int i= 1; i<= n; i++){
cout<<array[i];
if(i!= n)
cout<<' ';
else
cout<<endl;
}
}
void Qsort(int* &array, int low, int high){//快速排序
if(low< high){
int mid= Partition(array, low, high);
print(array);
Qsort(array, low, mid- 1);//将数组分成[low,mid-1]和[mid,high]两个区间
Qsort(array, mid+ 1, high);//
}
}树--叶子
//二叉树找父子节点
#include <iostream>
#include<queue>
using namespace std;
typedef struct BitNode {
char data;
BitNode* lchild, * rchild;
}BitNode, * BitTree;
void CreatTree(BitTree& T) {
char ch;
cin >> ch;
if (ch == '/0') { return; }
if (ch == '0') { T = NULL; }
else {
T = new BitNode;
T->data = ch;
/*先左后右保存数据**/
CreatTree(T->lchild);
CreatTree(T->rchild);
}
}
int FindLeaf(BitTree& T, queue<char>& child, queue<char>& parent) {
if (!T) { return 1; }
int flag = 0;//统计叶子
if (T) {
int item = FindLeaf(T->lchild, child, parent);//记录左儿子是不是叶子
if (item == 0) {
parent.push(T->data);
}
else if (item == 1) {
flag++;
}
item = FindLeaf(T->rchild, child, parent);
if (item == 0) {
parent.push(T->data);
}
else if (item == 1) {
flag++;
}
}
if (flag == 2) {
child.push(T->data);
return 0;
}
return -1;//未找到叶子
}
//统计左叶子
void LeftLeaf(BitTree& T,int & cnt,bool isleft) {
//是否为空
//是否为叶子
//对左叶子进行布尔值改变
//对右叶子不做布尔值变化
if (!T) { return ; } //空的标记return
if (!T->lchild&&!T->rchild) {
if(isleft)
cnt++;
}
LeftLeaf(T->lchild, cnt, true);
LeftLeaf(T->rchild, cnt,false);
}
树的遍历
#include <iostream>
#include<queue>
using namespace std;
typedef struct BitNode {
char data;
BitNode* lchild, * rchild;
}BitNode, * BitTree;
void CreatTree(BitTree& T) {
char ch;
cin >> ch;
if (ch == '/0') { return; }
if (ch == '0') { T = NULL; }
else {
T = new BitNode;
T->data = ch;
/*先左后右保存数据**/
CreatTree(T->lchild);
CreatTree(T->rchild);
}
}
// 层序遍历
void LevelOrder(BitTree t) {
queue<BitNode*> q;//结点指针
BitNode* p = t;
q.push(t);
while (!q.empty()) {
p = q.front();
q.pop();
cout << p->data << endl;
if (p->lchild) {
q.push(p->lchild);
}
if (p->rchild) {
q.push(p->rchild);
}
}
}
//前序遍历
void PreOrder(BitNode* t) {
if (t) {
cout << t->data;
PreOrder(t->lchild);
PreOrder(t->rchild);
}
}
//中序遍历
void InOrder(BitNode *t) {
if (t) {
InOrder(t->lchild);
cout << t->data;
InOrder(t->rchild);
}
}
//后序遍历
void PostOrder(BitNode* t) {
if (t) {
PostOrder(t->lchild);
PostOrder(t->rchild);
cout << t->data;
}
}
//获取树的高度
int getheight(BitNode *p){
if(p==NULL)
return 0;
int left = getheight(p->lchild);
int right = getheight(p->rchild);
return max(left,right)+1;
}
//非递归后序遍历
void PostOrderTraverse()
{
stack<Binary_tree_node*> s1; // 栈s1用于存储树节点
stack<int> s2; // 栈s2用于标记节点是否已经被访问过（0表示未访问，1表示已访问）
Binary_tree_node* p = root; // p指向树的根节点
do
{
// 当p不为NULL时，遍历左子树
while (p != NULL)
{
s1.push(p); // 将当前节点压入s1栈
s2.push(0); // 在s2栈中压入0，表示该节点未访问过
p = p->LeftChild; // 移动到当前节点的左孩子
if (s1.empty()) // 如果栈s1为空，表示树为空，跳出循环
{
break;
}
}
// 如果p为NULL（意味着当前节点没有左孩子）时，开始处理节点
if (!p == NULL) // `!p`的条件使得该程序块在p为NULL时执行
{
if (s2.top() == 0) // 如果s2栈顶为0，表示当前节点没有被访问过
{
s2.top() = 1; // 将栈顶的0改为1，标记当前节点已访问过
p = s1.top()->RightChild; // 转向当前节点的右孩子，准备遍历右子树
}
else if (s2.top() == 1) // 如果s2栈顶为1，表示当前节点已访问过，且其左右子树都已处理
{
p = s1.top(); // 获取当前节点
s1.pop(); // 从s1栈中弹出该节点
s2.pop(); // 从s2栈中弹出对应的标记
cout << p->data; // 输出当前节点的值
p = NULL; // 将p置为NULL，表示当前节点已经处理完毕
}
}
} while (!s1.empty()); // 当栈s1不为空时，继续遍历
cout << endl; // 输出换行符
}
哈夫曼树编码与解码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<deque>
#define error -1
#define ok 1
using namespace std;
struct BitNode {
BitNode* lchild;
BitNode* rchild;
int data;
char ch;
string str;
}*BitTree;
bool cmp(BitNode* a, BitNode* b) {
return a->data < b->data;
}
//哈夫曼编码
void huffman(BitNode* t) {
if (t->lchild) {
t->lchild->str = t->str + '0';
}
if (t->rchild) {
t->rchild->str = t->str + '1';
}
if (t->lchild)
huffman(t->lchild);
if (t->rchild)
huffman(t->rchild);
}
//哈夫曼解码
int decode(string code, char txt[], BitNode* t) {
int len = code.length();
BitNode* curr = t;
int index = 0;
for (int i = 0; i < len; i++) {
if (code[i] == '0') {
curr = curr->lchild;
}
else
curr = curr->rchild;
if (!curr->lchild && !curr->rchild) {
txt[index++] = curr->ch;
curr = t;
}
}
txt[index] = '\0'; // 确保字符串正确终止！！！
if (curr != t)
return error;
else return ok;
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
deque<BitNode*>p;
deque<BitNode*>q;
for (int i = 0; i < n; i++) {
BitNode* T = new BitNode();
T->str = "";
cin >> T->data;
p.push_back(T);
q.push_back(T);
}
for (int i = 0; i < n; i++) {
cin >> p[i]->ch;
}
while (p.size()!=1) {
sort(p.begin(), p.end(), cmp);
BitNode* a = p.front(); p.pop_front();
BitNode* b = p.front(); p.pop_front();
BitNode* c = new BitNode();
c->lchild = a;
c->rchild = b;
c->data = a->data + b->data;
p.push_back(c);
}
BitNode* d = p.front();
huffman(d);
//输出编码
for (int i = 0; i < q.size(); i++) {
cout << q[i]->data << "-" << q[i]->str << endl;
}
//输出解码
int m;
cin >> m;
while (m--) {
string dcode;
cin >> dcode;
char txt[1000];
decode(dcode, txt, d);
if (decode(dcode, txt, d) == error)
cout << "error" << endl;
else
cout << txt << endl;
}
}
return 0;
}AVL平衡二叉树
#include <iostream>
using namespace std;
#define LH 1 // 左高
#define EH 0 // 等高
#define RH -1 // 右高
int max(int a, int b) {
return a > b ? a : b;
}
class BiNode {
public:
int key; // 关键值
int bf; // 平衡因子
BiNode* lChild, * rChild;
BiNode(int kValue, int bValue = EH)
{
key = kValue;
bf = bValue;
lChild = NULL;
rChild = NULL;
}
};
int getheight(BiNode* t) {
if (t == NULL) {
return 0;
}
return max(getheight(t->lChild), getheight(t->rChild)) + 1;
}
// 二叉排序树
class BST {
private:
BiNode* root; // 根结点指针
void rRotate(BiNode*& p);
void lRotate(BiNode*& p);
void leftBalance(BiNode*& t);
void rightBalance(BiNode*& t);
void insertAVL(BiNode*& t, int key); // 插入元素并做平衡处理
void inOrder(BiNode* p); // 中序遍历
int countNodes(BiNode* p); // 计算树中节点的数量
public:
BST();
void insertAVL(int key); // 二叉排序树插入元素
~BST();
void inOrder(); // 中序遍历
void inOrderHelper(BiNode* p, int& currentNode, int totalNodes);
};
void BST::lRotate(BiNode*& p)//右旋 LL
{
BiNode* q = p->lChild;
p->lChild = q->rChild;
q->rChild = p;
p = q; // p变为新的根结点
// 旋转后更新平衡因子
p->bf = getheight(p->lChild) - getheight(p->rChild);
p->rChild->bf = getheight(p->rChild->lChild) - getheight(p->rChild->rChild);
}
void BST::rRotate(BiNode*& p)//左旋 RR
{
BiNode* q = p->rChild;
p->rChild = q->lChild;
q->lChild = p;
p = q; // p变为新的根结点
// 旋转后更新平衡因子
p->bf = getheight(p->lChild) - getheight(p->rChild);
p->lChild->bf = getheight(p->lChild->lChild) - getheight(p->lChild->rChild);
}
void BST::leftBalance(BiNode*& t)//左旋左孩子再右旋 LR
{
rRotate(t->lChild);
lRotate(t);
}
void BST::rightBalance(BiNode*& t)//右旋右孩子再左旋 RL
{
lRotate(t->rChild);
rRotate(t);
}
void BST::insertAVL(BiNode*& t, int key) {
if (t == NULL) {
t = new BiNode(key);
return;
}
if (key < t->key) {
insertAVL(t->lChild, key);
if (getheight(t->lChild) - getheight(t->rChild) == 2) {
if (key < t->lChild->key) {
lRotate(t); // LL
}
else {
leftBalance(t); // LR
}
}
}
else if (key > t->key) {
insertAVL(t->rChild, key);
if (getheight(t->rChild) - getheight(t->lChild) == 2) {
if (key > t->rChild->key) {
rRotate(t); // RR
}
else {
rightBalance(t); // RL
}
}
}
// 更新平衡因子
if (t != NULL) {
t->bf = getheight(t->lChild) - getheight(t->rChild);
}
}
// 中序遍历
void BST::inOrder(BiNode* p)
{
if (p)
{
inOrder(p->lChild);
cout << p->key << ":" << p->bf;
inOrder(p->rChild);
}
}
int BST::countNodes(BiNode* p)
{
if (p == NULL)
return 0;
return 1 + countNodes(p->lChild) + countNodes(p->rChild);
}
void BST::inOrder()
{
int totalNodes = countNodes(root); // 获取树中总节点数
int currentNode = 0; // 当前节点计数器
// 中序遍历时判断是否为最后一个节点
inOrderHelper(root, currentNode, totalNodes);
cout << endl; // 输出结束后换行
}
//消除最后一个节点及其平衡因子的空格
void BST::inOrderHelper(BiNode* p, int& currentNode, int totalNodes)
{
if (p)
{
inOrderHelper(p->lChild, currentNode, totalNodes);
cout << p->key << ":" << p->bf;
currentNode++;
if (currentNode < totalNodes)
cout << " "; // 如果不是最后一个节点，输出空格
inOrderHelper(p->rChild, currentNode, totalNodes);
}
}
BST::BST()
{
root = NULL;
}
BST::~BST()
{
root = NULL;
}
void BST::insertAVL(int key)
{
insertAVL(root, key);
}
int main(void)
{
int t;
cin >> t;
while (t--)
{
int n, elem;
cin >> n;
BST tree;
while (n--)
{
cin >> elem;
tree.insertAVL(elem);
}
tree.inOrder();
}
return 0;
}
图的连通
#include <iostream>
using namespace std;
void DFS(int** m, int n, int* visit, int temp)
{
for (int j = 0; j < n; j++)
{
if (m[temp][j] == 1 && visit[j] == 0)
{
visit[j] = 1;
DFS(m, n, visit, j);
}
}
}
void isconmected(int n)
{
int** m;
m = new int* [n];
for (int i = 0; i < n; i++)
{
m[i] = new int[n];
for (int j = 0; j < n; j++)
cin >> m[i][j];
}
int* visit = new int[n];
for (int i = 0; i < n; i++)
visit[i] = 0;
int flag = 0;
for (int i = 0; i < n; i++)
{
visit[i] = 0;
DFS(m, n, visit, i); //对每个顶点都调用DFS
for (int j = 0; j < n; j++)
{
if (visit[j] == 0) //然后判断此顶点能否到达其它顶点，visit[j]=0代表不能到达
{
flag = 1;
break;
}
else
visit[j] = 0;
}
if (flag == 1)
break;
}
if (flag == 0)
cout << "Yes" << endl;
else
cout << "No" << endl;
delete[]m;
}
int main()
{
int t;
cin >> t;
int n;
while (t--)
{
cin >> n;
isconmected(n);
}
return 0;
}图的广度遍历
#include <iostream>
#include <queue>
#include <cstring> // For memset
using namespace std;
const int MAX = 20;
class Map {
private:
bool Visit[MAX]; // 访问标记数组
int Matrix[MAX][MAX]; // 邻接矩阵
int Vexnum; // 顶点数
void BFS(int v); // 广度优先搜索
public:
void SetMatrix(int vnum, int mx[MAX][MAX]); // 设置邻接矩阵
void BFSTraverse(); // 广度优先遍历图
void ResetVisit(); // 重置访问标记数组
};
// 设置邻接矩阵
void Map::SetMatrix(int vnum, int mx[MAX][MAX]) {
Vexnum = vnum;
// 清空矩阵
memset(Matrix, 0, sizeof(Matrix));
// 复制输入的邻接矩阵
for (int i = 0; i < Vexnum; i++) {
for (int j = 0; j < Vexnum; j++) {
Matrix[i][j] = mx[i][j];
}
}
}
// 广度优先遍历
void Map::BFSTraverse() {
// 每次遍历前清空 Visit 数组
ResetVisit();
// 遍历所有未被访问的顶点
for (int i = 0; i < Vexnum; i++) {
if (!Visit[i]) {
BFS(i);
cout << endl; // 每个 BFS 完成后换行
}
}
}
// BFS 从顶点 v 开始进行广度优先搜索
void Map::BFS(int v) {
queue<int> Q; // 队列存储待访问的顶点
Visit[v] = true; // 标记当前顶点为已访问
cout << v << " "; // 打印当前顶点
Q.push(v); // 将当前顶点入队
while (!Q.empty()) {
int u = Q.front(); // 获取队头元素
Q.pop(); // 出队
// 遍历顶点 u 的所有邻接顶点
for (int i = 0; i < Vexnum; i++) {
if (Matrix[u][i] == 1 && !Visit[i]) { // 如果 u 到 i 有边且 i 未被访问
Visit[i] = true; // 标记 i 为已访问
cout << i << " "; // 打印邻接点
Q.push(i); // 将 i 入队
}
}
}
}
// 重置访问标记数组
void Map::ResetVisit() {
memset(Visit, false, sizeof(Visit)); // 将 Visit 数组全部置为 false
}
int main() {
int t;
cin >> t; // 输入测试用例数量
while (t--) {
int n;
cin >> n; // 输入图的顶点数
int ver[MAX][MAX];
// 输入邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> ver[i][j];
}
}
Map a;
a.SetMatrix(n, ver); // 设置图的邻接矩阵
a.BFSTraverse(); // 进行广度优先遍历
}
return 0;
}
图的深度遍历
#include<iostream>
using namespace std;
const int max_vertex_number = 20;
class Map {
int vertex_number = 0;
bool visited[max_vertex_number] = { false };
int matrix[max_vertex_number][max_vertex_number];
public:
Map() {
cin >> vertex_number;
for (int i = 0; i < vertex_number; i++)
for (int j = 0; j < vertex_number; j++)
cin >> matrix[i][j];
}
void DFS(int cur) {
if (visited[cur])
return;
cout << cur << ' ';
visited[cur] = true;
for (int i = 0; i < vertex_number; i++)
if (matrix[cur][i])
DFS(i);
}
void Traverse() {
for (int i = 0; i < vertex_number; i++)
if (visited[i] == false)
DFS(i);
cout << endl;
}
};
int main() {
int t;
cin >> t;
while (t--) {
Map test;
test.Traverse();
}
return 0;
}