在完结了算法之后 我又来写数据结构啦！真的很讨厌校OJ数据结构的题，输出提示词太捞了，每一题都是超级缝合怪，像个小课设一样。

值得一提的是，虽然数据结构课上要求是用C语言实现这些功能，但是因为频繁用到引用，所以考试可以直接提交C++，再加上机试没有填空题，所以我们完全可以直接使用C++的STL，本文也是直接使用STL实现的。

但是！这并不代表数据结构实现的原理不重要，因为我们数据结构的笔试的大题会要求你在试卷上进行试卷填空，这一部分等我有空再开一篇文章，如果你在CSDN搜到别的看不懂的话，建议翻开你的高程回去恶补指针，结构体相关知识。那么闲话少叙，我们直接开始！

实验1

本章主要介绍了顺序表这一数据结构，我们使用STL的话对应的就是vector这一容器了。使用时需要引用头文件<vector>

常用的相关函数有这些

<code>vector<int> a;//创建一个int类型的数组a 相当于int a[n];

a.empty();//判断数组是否为空

a.push_back(8);//在数组的末尾插入一个元素8

a.push_front(8);//在数组的开头插入一个元素8

a.pop_back();//删除数组的最后一个元素

a.pop_front();//删除数组的第一个元素

a.front();//返回数组的第一个元素

a.back();//返回数组的最后一个元素

a.size();//返回数组的大小

a.clear();//清空数组

a.insert(a.begin()+1,8);//在数组的第二个元素后面插入一个元素8

a.erase(a.begin()+1);//删除数组的第二个元素

a.erase(a.begin()+1,a.begin()+3);//删除数组的第二个到第四个元素

//copilot自动填充注释太好用了 快去拿校园邮箱白嫖一个

8576 顺序线性表的基本操作

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long i64;

int main()

{

vector<int> a;

printf("A Sequence List Has Created.\n");

again://防伪标识

printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");

int cmd;

scanf("%d",&cmd);

if(cmd==1)

{

int p,x;

scanf("%d%d",&p,&x);

if(p==1)

{

a.insert(a.begin(),x);

printf("The Element %d is Successfully Inserted!\n", x);

goto again;

}

else

{

if(a.empty())

{

printf("Insert Error!\n");

goto again;

}

a.insert(a.begin()+p-2,x);

printf("The Element %d is Successfully Inserted!\n", x);

goto again;

}

}

else if(cmd==2)

{

int p;

scanf("%d",&p);

int n=a.size();

if(n<p)

{

printf("Delete Error!\n");

goto again;

}

int x=a[p-1];

a.erase(a.begin()+p-1);

printf("The Element %d is Successfully Deleted!\n", x);

goto again;

}

else if(cmd==3)

{

if(!a.empty())

{

printf("The List is: ");

for (int i: a)

printf("%d ", i);

printf("\n");

goto again;

}

else

{

printf("The List is empty!\n");

goto again;

}

}

else

return 0;

return 0;

}

8577 合并顺序表

为防你上课没听过 我还是简单给你介绍一下 题目给你两个排好序的数组 你要将他们合并并保持仍然有序 直接拼在一起sort会超时

所以我们对于新一个数组的每一位 考虑这个时候a和b的值的大小 谁小先放谁

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long i64;

int main()

{

int n,m;

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++) scanf("%d",&a[i]);

scanf("%d",&m);

int b[m];

for(int i=0;i<m;i++) scanf("%d",&b[i]);

int c[n+m];

int i=0,j=0,k=0;

while(i<n and j<m)

{

if(a[i]<b[j])

{

c[k]=a[i];

i++;

}

else if(a[i]>=b[j])

{

c[k]=b[j];

j++;

}

k++;

}

while(i<n)

{

c[k]=a[i];

i++;

k++;

}

while(j<m)

{

c[k]=b[j];

j++;

k++;

}

printf("List A:");

for(int i:a) printf("%d ",i);

printf("\n");

printf("List B:");

for(int i:b) printf("%d ",i);

printf("\n");

printf("List C:");

for(int i:c) printf("%d ",i);

printf("\n");

return 0;

}

8578 顺序表逆置

虽然我知道直接用数组很简单啦 不过这题我们还是继续训练一下vector的使用 这里用到了两个新的函数 他们返回的是迭代器 你可以简单地理解为他们返回的是vector开头和结尾的指针即可

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long i64;

int main()

{

int n;

scanf("%d",&n);

vector<int> a(n);

for(int i=0;i<n;i++)

scanf("%d",&a[i]);

printf("The List is:");

for(int i:a)

printf("%d ",i);

printf("\n");

printf("The turned List is:");

for(auto it = a.rbegin(); it != a.rend(); ++it) {

printf("%d ", *it);

}

printf("\n");

return 0;

}

8579 链式线性表的基本操作

因为我们用的是STL 所以本题几乎和第一题一模一样 但是为了展示本文的多样性我们做一次填空（绝对不是因为拿之前那个改了一直WA不知道为什么）

我的代码中每一句都有专门重新写注释 希望能帮助你看懂这类模拟数据结构填空题出题人的一般思路（他的这个马蜂真的是看得我好难受）

#include<stdio.h>

#include<malloc.h>

#define ERROR 0

#define OK 1

#define ElemType int

typedef struct LNode

{

int data;

struct LNode *next;

}LNode,*LinkList;//定义单链表

int CreateLink_L(LinkList &L,int n){

LinkList p,q;//p为新建结点，q为尾结点

int i;

ElemType e;//哥们至今都不知道到底为什么非要定义这么个ElemType

L = new LNode;//传入的这个L是一个LinkList也就是指针类型 所以这里是让他指向一个新的LNode

L->next = NULL;//初始化头结点的next指针指向NULL

q = L;//因为L是引用来的不能改他的指向 所以把他赋给这个q 因为是指针类型不影响对指针内内容的操作能力的同时还能方便我丢进去循环

for (i=0; i<n; i++) {

scanf("%d", &e);

p = new LNode;//开一个新的节点

p->data = e;//赋值

p->next = NULL;//初始化指向的下一个节点

q->next = p;//把新节点接到尾结点后面

q = p;//然后再更新q方便我循环操作

}

return OK;

}

int LoadLink_L(LinkList &L){

LinkList p = L->next;

if(!p)//如果头结点的next指针指向NULL说明链表是空的

printf("The List is empty!");

else

{

printf("The LinkList is:");

while(p)//只要指向的不是NULL（表示没有下个节点了）就一直输出

{

printf("%d ",p->data);

p=p->next;//更新p

}

}

printf("\n");

return OK;

}

int LinkInsert_L(LinkList &L,int i,ElemType e){

LinkList p = L;

int j = 0;

while(p && j<i-1)//找到第i个位置的前一个节点

{

p = p->next;

j++;

}

if(!p || j>i-1)//如果找不到或者i值不合法

return ERROR;

LinkList s = new LNode;//新建一个节点

s->data = e;//赋值

s->next = p->next;//把新节点的next指针指向第i个节点

p->next = s;//把第i-1个节点的next指针指向新节点

return OK;

}

int LinkDelete_L(LinkList &L,int i, ElemType &e){

LinkList p = L;

int j = 0;

while(p->next && j<i-1)//找到第i个节点的前一个节点

{

p = p->next;

j++;

}

if(!(p->next) || j>i-1)//如果找不到或者i值不合法

return ERROR;

LinkList q = p->next;//把第i个节点赋给q

p->next = q->next;//把第i-1个节点的next指针指向第i+1个节点

e = q->data;//把第i个节点的值赋给e

delete q;//删除第i个节点

return OK;

}

int main()

{

LinkList T;

int a,n,i;

ElemType x, e;

printf("Please input the init size of the linklist:\n");

scanf("%d",&n);

printf("Please input the %d element of the linklist:\n", n);

if(CreateLink_L(T,n))//他那个ERROR和OK真的是抽象 懒得喷 总之这里就是在刚刚创建链表的时候根据那个函数的返回值判断成功没有

{

printf("A Link List Has Created.\n");

LoadLink_L(T);

}

while(1)

{

printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n");

scanf("%d",&a);

switch(a)

{

case 1: scanf("%d%d",&i,&x);

if(!LinkInsert_L(T,i,x)) printf("Insert Error!\n"); //判断i值是否合法，他同样用的是根据函数返回值判断的

else printf("The Element %d is Successfully Inserted!\n", x);

break;

case 2: scanf("%d",&i);

if(!LinkDelete_L(T,i,e)) printf("Delete Error!\n"); //判断i值是否合法，他同样用的是根据函数返回值判断的

else printf("The Element %d is Successfully Deleted!\n", e);

break;

case 3: LoadLink_L(T);

break;

case 0: return 1;

}

}

}

8580 合并链表

这一题也是跟刚才的第二题一模一样 不过我突然发现当时用的是数组 那这边顺便介绍下vector如何事前声明数组大小 就是在名字后面加个括号就可以了 其他部分都是完全相同的

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long i64;

int main()

{

int n,m;

scanf("%d",&n);

vector<int> a(n);

for(int i=0;i<n;i++) scanf("%d",&a[i]);

scanf("%d",&m);

vector<int> b(m);

for(int i=0;i<m;i++) scanf("%d",&b[i]);

vector<int> c(n+m);

int i=0,j=0,k=0;

while(i<n and j<m)

{

if(a[i]<b[j])

{

c[k]=a[i];

i++;

}

else if(a[i]>=b[j])

{

c[k]=b[j];

j++;

}

k++;

}

while(i<n)

{

c[k]=a[i];

i++;

k++;

}

while(j<m)

{

c[k]=b[j];

j++;

k++;

}

printf("List A:");

for(int i:a) printf("%d ",i);

printf("\n");

printf("List B:");

for(int i:b) printf("%d ",i);

printf("\n");

printf("List C:");

for(int i:c) printf("%d ",i);

printf("\n");

return 0;

}

19080 反转链表

肯定有人看到这一题欣喜若狂 结果点进去发现是填空题的 因为至少我就是 不过题目本身很简单 直接贴代码吧 刚好看你之前的8579看懂没有捏

/**< 逆置单链表 */

LNode *p,*q;//p为工作指针，q为工作指针的后继

p=L->next;//p指向第一个节点

L->next=NULL;//断开头结点与第一个节点的联系

while(p)

{

q=p->next;//q指向p的后继

p->next=L->next;//将p插入到头结点之后

L->next=p;//头结点的next指向p

p=q;//p指向下一个节点

}

实验2

本章我们使用的有STL中的stack容器 需要引入头文件<stack> 其主要特点是单向入栈单向出栈且遵循后进先出的特点 你可以理解为一根杆子上的一堆秤砣 就像这张图上这样

那么主要用到的函数我们也是一样摆在下面（size和empty这种意思没啥区别的就不单独列了）

<code>stack<int> s;//定义一个栈

s.push(8);//在栈顶插入元素8

s.pop();//弹出栈顶元素

int c=s.top();//让c等于栈顶元素 但是不弹出

除此之外 我们还要用queue这一容器 引用头文件<queue>即可使用 队列则是与上面相反 遵循先进先出的规则

主要用到的函数如下

queue<int> q;//创建一个int类型数据组成的队列q

q.push(8);//将8放在队列尾端

q.pop();//弹出队列前端的元素

q.front();//返回队列前端的元素

q.back();//返回队列尾端的元素

8583 顺序栈的基本操作

又是我最讨厌的小型课设 利用上面介绍的函数可以很轻松地完成这些问题

#include <iostream>

#include <algorithm>

#include <stack>

using namespace std;

typedef long long i64;

int main()

{

stack<int> st;

printf("A Stack Has Created.\n");

again://防伪标识

printf("1:Push \n2:Pop \n3:Get the Top \n4:Return the Length of the Stack\n5:Load the Stack\n0:Exit\nPlease choose:\n");

int op;

scanf("%d",&op);

if(op==1)

{

int x;

scanf("%d",&x);//根本不可能error的干脆不写了

st.push(x);

printf("The Element %d is Successfully Pushed!\n", x);

goto again;

}

else if(op==2)

{

if(st.empty())

{

printf("Pop Error!\n");

goto again;

}

else

{

int e=st.top();//先把栈顶元素存一下 不然一弹就没了

st.pop();

printf("The Element %d is Successfully Poped!\n", e);

goto again;

}

}

else if(op==3)

{

if(st.empty())

{

printf("Get Top Error!\n");

goto again;

}

else

{

int e=st.top();//跟上面那个基本一样 把弹出的操作删掉就行

printf("The Top Element is %d!\n", e);

goto again;

}

}

else if(op==4)

{

int sz=st.size();

printf("The Length of the Stack is %d!\n", sz);

goto again;

}

else if(op==5)

{

if(st.empty())

{

printf("The Stack is Empty!");

goto again;

}

else

{

printf("The Stack is:");

stack<int> st2 = st;//用stl的缺点就是无法遍历栈内元素 所以我们要开一个新的 然后弹这个新的

while (!st2.empty())

{

printf(" %d", st2.top());

st2.pop();

}

printf("\n");

goto again;

}

}

else if(op==0)

{

return 0;

}

return 0;

}

8584 循环队列的基本操作

跟上面基本一样 改一下函数和输出的提示词就可以了

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long i64;

int main()

{

queue<int> q;

printf("A Queue Has Created.\n");

again://防伪标识

printf("1:Enter \n2:Delete \n3:Get the Front \n4:Return the Length of the Queue\n5:Load the Queue\n0:Exit\nPlease choose:\n");

int op;

scanf("%d",&op);

if(op==1)

{

int x;

scanf("%d",&x);//根本不可能error的干脆不写了

q.push(x);

printf("The Element %d is Successfully Entered!\n", x);

goto again;

}

else if(op==2)

{

if(q.empty())

{

printf("Delete Error!\n");

goto again;

}

else

{

int e=q.front();//先把队顶元素存一下 不然一弹就没了

q.pop();

printf("The Element %d is Successfully Deleted!\n", e);

goto again;

}

}

else if(op==3)

{

if(q.empty())

{

printf("Get Head Error!\n");

goto again;

}

else

{

int e=q.front();//跟上面那个基本一样 把弹出的操作删掉就行

printf("The Head of the Queue is %d!\n", e);

goto again;

}

}

else if(op==4)

{

int sz=q.size();

printf("The Length of the Queue is %d!\n", sz);

goto again;

}

else if(op==5)

{

if(q.empty())

{

printf("The Stack is Empty!");

goto again;

}

else

{

printf("The Queue is:");

queue<int> q2 = q;//用stl的缺点就是无法遍历队内元素 所以我们要开一个新的 然后弹这个新的

while (!q2.empty())

{

printf(" %d", q2.front());

q2.pop();

}

printf("\n");

goto again;

}

}

else if(op==0)

{

return 0;

}

return 0;

}

8585 栈的应用——进制转换

终于正儿八经有道题了...这个功能C++好像有内置函数 直接调吧还是

#include <iostream>

using namespace std;

typedef long long i64;

int main()

{

int n;

scanf("%d",&n);

printf("%o\n",n);

return 0;

}

8586 括号匹配检验

终于来了 这个才是我想做的题嘛 题目描述已经说的很清楚了 用栈存储的方式快速解决这个问题 具体来说遇到左括号就存进去 遇到右括号和栈顶的左括号无法匹配就直接输出错误 否则就弹出 弹到最后如果栈内还有剩余同样输出错误即可

不过嘛 不知道之前看到现在的你有没有像这样一件事：既然栈和队列都有这么多的限制，无法遍历所有内容，那我干脆用vector不就好了嘛，需要的功能也同样能实现

这样的说法当然是...完全没有问题！所以这一题，我们就用vector来模拟stack的方式来完成！

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long i64;

int main()

{

string s;

cin>>s;

int l=s.length();

vector<char> st;

for(int i=0;i<l;i++)

{

if(s[i]=='('||s[i]=='[')

{

st.push_back(s[i]);

}

else if(s[i]==')')

{

if(st.empty())

{

printf("lack of left parenthesis\n");

return 0;

}

else if(st.back()!='(')

{

printf("isn't matched pairs\n");

return 0;

}

st.pop_back();

}

else if(s[i]==']')

{

if(st.empty())

{

printf("lack of left parenthesis\n");

return 0;

}

else if(st.back()!='[')

{

printf("isn't matched pairs\n");

return 0;

}

st.pop_back();

}

}

if(!st.empty())

{

printf("lack of right parenthesis\n");

return 0;

}

printf("matching\n");

return 0;

}

8587 行编辑程序

这一题我们遇到了之前遇到过的栈的元素无法遍历的问题 之前我们通过赋值一个新栈来解决这个问题 但是这次我们刚刚已经学习了用vector模拟stack的做法 这时就展现出其用途了 在实现stack功能的基础上 vector还可以遍历 那么我们也就解决了这样一个问题

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main()

{

int n;

scanf("%d\n",&n);

vector<char> a;

char c;

while(n>0)//每次读到回车就n-- n等于0说明读完了

{

scanf("%c",&c);

a.push_back(c);

if(c=='\n')

n--;

else if(c=='#')

{

a.pop_back();

a.pop_back();

}

else if(c=='@')

{

while(a.back()!='\n')

a.pop_back();

}

}

for(char ch:a)

printf("%c",ch);

return 0;

}

但是这个代码错误 这是为什么呢 原来是没有判空 小朋友们千万不要模仿

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main()

{

int n;

scanf("%d\n",&n);

vector<char> a;

char c;

while(n>0)//每次读到回车就n-- n等于0说明读完了

{

scanf("%c",&c);

a.push_back(c);

if(c=='\n')

n--;

else if(c=='#')

{

a.pop_back();

if(!a.empty())

a.pop_back();

}

else if(c=='@')

{

while(a.back()!='\n')

{

if(a.empty())

break;

a.pop_back();

}

}

}

int l=a.size();

for(int i=0;i<l;i++)

printf("%c",a[i]);

return 0;

}

8588 表达式求值

利用栈实现表达式求值

#include <iostream>

#include <algorithm>

#include <ctype.h>

#include <stack>

#include <vector>

#include <map>

using namespace std;

typedef long long i64;

int main()

{

//初始化优先级

map<char,int> getValue;

getValue['+']=1;

getValue['-']=1;

getValue['*']=2;

getValue['/']=2;

string s;

cin>>s;

int l=s.length();

//先转为后缀表达式

stack<char>opt;//存符号

stack<char>num;//存数字

vector<char>all;//存后缀表达式

for(int i=0;i<l;i++)

{

if(s[i]=='=' or i==l-1)

{

while(!opt.empty())

{

all.push_back(opt.top());

opt.pop();

}

break;

}

else if(isdigit(s[i]))

all.push_back(s[i]);

else if(s[i]=='(')

opt.push(s[i]);

else if(s[i]==')')

{

while(!opt.empty() and opt.top()!='(')

{

all.push_back(opt.top());

opt.pop();

}

opt.pop();

}

else

{

while(!opt.empty() and getValue[opt.top()]>=getValue[s[i]])

{

all.push_back(opt.top());

opt.pop();

}

opt.push(s[i]);

}

}

//计算后缀表达式

l=all.size();

stack<int>digit;//记录待计算的数字

for(int i=0;i<l;i++)

{

if(isdigit(all[i]))

{

digit.push(all[i]-'0');

}

else

{

int a=digit.top();

digit.pop();

int b=digit.top();

digit.pop();

if(all[i]=='+')

digit.push(b+a);

else if(all[i]=='-')

digit.push(b-a);

else if(all[i]=='*')

digit.push(b*a);

else if(all[i]=='/')

digit.push(b/a);

}

}

printf("%d\n",digit.top());

return 0;

}

 不过假如你用的是python 你可以用四行秒杀这道题

expression = input()

expression = expression[:-1]#删掉最后面的等号

result = eval(expression)

print(result)

 18938 汉诺塔问题

我上面用的那张图就是汉诺塔 不过这题倒是不用栈 用的是递归

#include <iostream>

#include <algorithm>

using namespace std;

void hnt(int n,char a,char b,char c)

{

if(n==1)

{

printf("%c->%d->%c\n",a,n,b);

return ;

}

hnt(n-1,a,c,b);

printf("%c->%d->%c\n",a,n,b);

hnt(n-1,c,b,a);

}

int main()

{

int n;

char a,b,c;

cin>>n>>a>>b>>c;

hnt(n,a,b,c);

return 0;

}

实验3

这一章主要讲的就是KMP算法 特别是next值的计算

8591 计算next值

坏消息是学校的next值和常搜到的定义有些许出入 可能需要背一下

#include <iostream>

#define MAXSTRLEN 255 // 用户可在255以内定义最大串长

typedef unsigned char SString[MAXSTRLEN + 1]; // 0号单元存放串的长度

void get_next(SString t, int next[])

{

// 算法4.7

// 求模式串T的next函数值并存入数组next

// 请补全代码

int i = 1, j = 0;

next[1] = 0;

while (i <= t[0])

{

if (j == 0 || t[i] == t[j])

{

++i;

++j;

next[i] = j;

} else j = next[j];

}

}

int main()

{

int next[MAXSTRLEN];

SString S;

int n, i, j;

char ch;

scanf("%d", &n); // 指定要验证NEXT值的字符串个数

ch = getchar();

for (i = 1; i <= n; i++)

{

ch = getchar();

for (j = 1; j <= MAXSTRLEN && (ch != '\n'); j++) // 录入字符串

{

S[j] = ch;

ch = getchar();

}

S[0] = j - 1; // S[0]用于存储字符串中字符个数

get_next(S, next);

printf("NEXT J is:");

for (j = 1; j <= S[0]; j++)

printf("%d", next[j]);

printf("\n");

}

}

8592 KMP算法

好消息是用stl的话直接用algorithm库里面的find函数或是cstring里面的strstr函数就可以过

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

void solve()

{

string a;

string b;

cin>>a>>b;

int ans=a.find(b);

printf("%d\n",ans+1);

}

int main()

{

int T=1;

scanf("%d",&T);

while(T--)

{

solve();

}

return 0;

}

18769 不完整的排序

双指针嘛 先写一个

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int main()

{

int T=1;

scanf("%d",&T);

while(T--)

{

int n;

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++) scanf("%d",&a[i]);

for(int i=0,j=n-1;i<j;i++,j--)

{

if(a[i]>0)

{

while(a[j]>0 and i<j)

j--;

swap(a[i],a[j]);

}

if(a[j]<0)

{

while(a[i]<0 and i<j)

i++;

swap(a[i],a[j]);

}

}

for(int i=0;i<n;i++) printf("%d ",a[i]);

}

return 0;

}

不对 那找参考再写一个 反正黄栋群里问题目从来不回的 你要是有幸抽到我院这位学科代言人你就偷着乐去吧 每节课一次全体点名 上课不许玩手机不许睡觉 下课手机不许横着放 实验课要求按学号坐 没人就算旷课 写完了想提前下课还要答辩

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int main()

{

int T = 1;

scanf("%d", &T);

while (T--)

{

int n;

scanf("%d", &n);

int a[n + 1];

for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

int i, j;

i = 1, j = n;

while (i < j)

{

if (a[i] > 0 && a[j] > 0)

j--;

else if (a[i] > 0 && a[j] < 0)

{

swap(a[i], a[j]);

i++, j--;

}

else if (a[i] < 0 && a[j] < 0)

i++;

else if (a[i] < 0 && a[j] > 0)

i++, j--;

}

for (int i = 1; i <= n; i++) printf("%d ", a[i]);

printf("\n");

}

return 0;

}

虽然我后来发现第一个代码只是少打了一个回车 但是我不想删掉对于我们黄栋老师的批判所以保留此段 望周知

实验4

二叉树这个东西确实没有对应STL 但是搞指针链真的难受 所以我们下面会介绍两种数组的存法

8606 二叉树的构建及遍历操作

前序遍历中序遍历后序遍历其实唯一的区别就是输出的时间不同 具体看代码一眼就能看懂 还是开头那句话 指针看不懂赶紧回去恶补高程捏

#include <iostream>

#include <algorithm>

using namespace std;

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status;

typedef char ElemType;

typedef struct BiTNode

{

ElemType data;

struct BiTNode *lchild, *rchild;//左右孩子指针

} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T)

{ // 算法6.4

// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，

// 构造二叉链表表示的二叉树T。

char ch;

scanf("%c", &ch);

if (ch == '#')

T = NULL;

else

{

if (!(T = (BiTNode *) malloc(sizeof(BiTNode))))

return ERROR;

T->data = ch;// 生成根结点

CreateBiTree(T->lchild);// 构造左子树

CreateBiTree(T->rchild);// 构造右子树

}

return OK;

} // CreateBiTree

Status PreOrderTraverse(BiTree T)

{

// 前序遍历二叉树T的递归算法

//补全代码,可用多个语句

if(T==NULL)

return 0;

cout<<T->data;

PreOrderTraverse(T->lchild);

PreOrderTraverse(T->rchild);

return 1;

} // PreOrderTraverse

Status InOrderTraverse(BiTree T)

{

// 中序遍历二叉树T的递归算法

//补全代码,可用多个语句

if(T==NULL)

return 0;

InOrderTraverse(T->lchild);

cout<<T->data;

InOrderTraverse(T->rchild);

return 1;

} // InOrderTraverse

Status PostOrderTraverse(BiTree T)

{

// 后序遍历二叉树T的递归算法

//补全代码,可用多个语句

if(T==NULL)

return 0;

PostOrderTraverse(T->lchild);

PostOrderTraverse(T->rchild);

cout<<T->data;

return 1;

} // PostOrderTraverse

int main() //主函数

{

BiTree T;

CreateBiTree(T);

PreOrderTraverse(T);cout<<endl;

InOrderTraverse(T);cout<<endl;

PostOrderTraverse(T);cout<<endl;

return 0;

//补充代码

}//main

17121 求二叉树各种节点数

为了丰富本文的解法数 这题我们介绍用数组来存二叉树（仅限二叉树） 如图所示 节点的数字就是他存于数组的下标

不难发现 节点i的左儿子和右儿子的下标分别为2*i和2*i+1 你可能会问按顺序存如果中间某个节点缺儿子怎么办 那就将这个位置标记为一个特殊的数据就可以了

<code>#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long i64;

char tree[10000];//数据很小

string s;

int po=0;//当前读取到字符串的第po位

int len;//字符串长度

void initialize(int p)

{

if(po>len)

return ;

char now=s[po];

po++;

if(now=='#')

return ;

tree[p]=now;//存进去

initialize(2*p);

initialize(2*p+1);

}

int ans[3]={0};

void solve(int p)

{

if(tree[p]=='#')

return ;

int now=0;

if(tree[2*p]!='#')

now++;

if(tree[2*p+1]!='#')

now++;

ans[now]++;

solve(2*p);

solve(2*p+1);

}

int main()

{

cin>>s;

len=s.length();

memset(tree, '#', sizeof(tree));

initialize(1);

solve(1);

for(int i=2;i>=0;i--)

{

printf("%d\n",ans[i]);

}

return 0;

}

也许你可以尝试下如何用数组存二叉树完成三种遍历？我想看懂上面的代码的话应该不是特别难写喵 当然这边还是给一个用指针解这道题的解法吧 其实直接拿上一题的先序遍历改一下就OK了

#include <iostream>

#include <algorithm>

using namespace std;

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

typedef int Status;

typedef char ElemType;

typedef struct BiTNode

{

ElemType data;

struct BiTNode *lchild, *rchild;//左右孩子指针

} BiTNode, *BiTree;

Status CreateBiTree(BiTree &T)

{ // 算法6.4

// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树，

// 构造二叉链表表示的二叉树T。

char ch;

scanf("%c", &ch);

if (ch == '#')

T = NULL;

else

{

if (!(T = (BiTNode *) malloc(sizeof(BiTNode))))

return ERROR;

T->data = ch;// 生成根结点

CreateBiTree(T->lchild);// 构造左子树

CreateBiTree(T->rchild);// 构造右子树

}

return OK;

} // CreateBiTree

int ans[3]={0};

Status PreOrderTraverse(BiTree T)

{

if(T==NULL)

return 0;

//cout<<T->data;

int a=PreOrderTraverse(T->lchild);

int b=PreOrderTraverse(T->rchild);

int sum=0;

if(a==1)

sum++;

if(b==1)

sum++;

ans[sum]++;

return 1;

} // PreOrderTraverse

int main() //主函数

{

BiTree T;

CreateBiTree(T);

PreOrderTraverse(T);

for(int i=2;i>=0;i--)

{

printf("%d\n",ans[i]);

}

return 0;

//补充代码

}//main

18924 二叉树的宽度

这题同样也是用数组模拟会比较简单喵 但是我们又引入一种新的存法 用一个数组存每个数的两个儿子都是谁 没有的话就记为0 存完之后我们直接bfs 注意到每次再次进入循环都是新的一层 所以加一个求最大值就可以了

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

typedef long long i64;

int child[10000][2];

int main()

{

int n;

scanf("%d",&n);

for(int i=1;i<n;i++)

{

int x,y;

scanf("%d%d",&x,&y);

if(child[x][0]==0)

child[x][0]=y;

else

child[x][1]=y;

}

queue<int>q;

q.push(1);

int ans=1;

while(q.size())

{

int len=q.size();

ans=max(ans,len);

for(int i=0;i<len;i++)

{

int t=q.front();

q.pop();

if(child[t][0])

q.push(child[t][0]);

if(child[t][1])

q.push(child[t][1]);

}

}

printf("%d",ans);

return 0;

}

当然bfs好写不代表之前的存法不能写 我们把没有内容的点存为0 然后最后对整个数组遍历一下即可 主要是大家都是数字确实可能容易看混 主要问题是我一开始这么写的但是又是不知道错在哪 黄栋又不回我消息 所以下面这个代码无法通过

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int main()

{

int n;

scanf("%d",&n);

int tree[10000]={0};

tree[1]=1;

for(int i=1;i<n;i++)

{

int x,y;

scanf("%d%d",&x,&y);

if(tree[2*x]==0)

tree[2*x]=y;

else

tree[2*x+1]=y;

}

int i=1;//找到第几个数了

int now=1;//当前层总节点个数（假如全满）

int ans=0;

while(i<10000)

{

int l=i,sum=0;

for(;i<l+now;i++)

{

if(i>=10000)

break;

if(tree[i])

{

sum++;

}

}

now*=2;

ans=max(ans,sum);

}

printf("%d\n",ans);

return 0;

}

18724 二叉树的遍历运算

根据先序遍历和中序遍历生成后序遍历 私以为这篇文章讲的已经很详细了 我就直接贴代码吧

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

typedef long long i64;

string s1, s2;

void solve(int l1, int r1, int l2, int r2)

{

char c = s1[l1];//正序遍历的第一个字符是后续遍历的最后一个字符

if (l1 > r1 || l2 > r2)

return;//递归边界

int i;

for (i = l2; i <= r2; i++)

{

if (c == s2[i])

break;

}//在中序遍历的序列中找到这个字符

//那么这个字符的左边是左子树，右边是右子树，分别递归即可

solve(l1 + 1, r1 - (r2 - i), l2, i - 1);

solve(r1 - (r2 - i - 1), r1, i + 1, r2);

printf("%c", c);

}

int main()

{

cin >> s1 >> s2;

int len1 = s1.size();

int len2 = s2.size();

solve(0, len1 - 1, 0, len2 - 1);

return 0;

}

18923 二叉树的直径

看起来这一题是要我们遍历每一个点去两个方向找 但是其实你可以发现我们只需要对一个点左边找最深再右边找最深加起来就可以了 不过dfs应该不用再多说了吧

（虽然后来我发现直径的路径一定经过根节点 但是反正都能过就懒得改了）

#include <iostream>

#include <algorithm>

typedef long long ll;

using namespace std;

int n, child[105][2], ans = 0;

int x, y;

int dfs(int p)

{

if (!p)

return 0;

int left = dfs(child[p][0]);

int right = dfs(child[p][1]);

int len = max(left, right) + 1;

ans = max(ans, left + right);

return len;

}

int main()

{

scanf("%d", &n);

for (int i = 1; i < n; i++)

{

cin >> x >> y;

if (!child[x][0])

child[x][0] = y;

else

child[x][1] = y;

}

for (int i = 1; i <= n; i++)

dfs(i);

printf("%d\n", ans);

return 0;

}

当然 如果你喜欢的话 也可以对每一个点往两个方向去找 这样的话我们就需要记录树之间双向的联系 链式和二维都无法完成这一点 只能用一维数组 他的父节点是i/2 子节点是i*2和i*2+1 我想你可以自己尝试一下这种写法（绝对不是我写完WA了）

19638 平衡树

（题号是我为了排版随便编的）这是2024年上半期末上机考新出的压轴题 提前交卷赶紧回来码题解了 后来的朋友们也可以参考下压轴题的难度

题目大意是给你一个中序遍历 然后要你构建一个满足此中序遍历的平衡树 最后输出你构建好的树的先序遍历 如果链接打不开我就简单说一下 平衡树就是他左右所有子孙节点的和的差值的绝对值最小 所以构建的时候我们只需要找满足此条件的点放到根节点 查找的时候记得使用前缀和 虽然我没试但是不用的话大概率会超时 然后左右再递归就可以了（给中序节点基本上都是要递归写的）

我写的时候用的是一维数组存储 中间没判空WA了一发 这里顺便给出一维数组存储的先序遍历方法吧

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long i64;

int n,a[100000]={0},sum[100000]={0};

int tree[100000]={0};

void solve(int l,int r,int nowi)

{

if(r<l) return ;//记得要判空

if(l==r)

{

tree[nowi]=a[l];

return ;

}

if(r==l+1)

{

tree[nowi]=max(a[l],a[r]);

tree[nowi*2]=min(a[l],a[r]);

return ;

}

int p=0,m=1e9;//记录满足左右abs最小的值的位置和此时的左右abs

for(int i=l;i<=r;i++)

{

int left=abs(sum[i-1]-sum[l-1]);

int right=abs(sum[r]-sum[i]);

int now=abs(left-right);

if(now<m)

{

m=now;

p=i;

}

}

tree[nowi]=a[p];

solve(l,p-1,nowi*2);

solve(p+1,r,nowi*2+1);

}

void print(int nowi)//一维数组存储的先序遍历

{

printf("%d ",tree[nowi]);

if(tree[nowi*2]!=-1)

print(nowi*2);

if(tree[nowi*2+1]!=-1)

print(nowi*2+1);

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i]);

sum[i]=sum[i-1]+a[i];

}

memset(tree,-1,sizeof(tree));

solve(1,n,1);

print(1);

return 0;

}

实验5

8610 顺序查找

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int main()

{

int n;

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++)

{

scanf("%d",&a[i]);

}

int who;

scanf("%d",&who);

for(int i=0;i<n;i++)

{

if(a[i]==who)

{

printf("The element position is %d.\n",i+1);

return 0;

}

}

printf("The element is not exist.\n");

return 0;

}

8621 二分查找

我当然知道二分很好写嘛 但是我们借这个机会再介绍一个C++中algorithm库里面的一个函数吧

我们这个代码里面直接把binary_search()和lower_bound()都用了 注意这几个函数最好配套vector使用 不知道vector是啥的请把本文翻到最上面

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

typedef long long i64;

int main()

{

int n;

scanf("%d",&n);

vector<int> a(n);

for(int i=0;i<n;i++)

{

scanf("%d",&a[i]);

}

int who;

scanf("%d",&who);

if(!binary_search(a.begin(),a.end(),who))

{

printf("The element is not exist.\n");

return 0;

}

printf("The element position is %d.\n",lower_bound(a.begin(),a.end(),who)-a.begin());

return 0;

}

当然也不是说直接开数组就不行哈 类似sort函数写成binary_search(a,a+n,who)也可以

8622 哈希查找

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int length;

int H(int k)

{

return 3*k%length;

}

int main()

{

scanf("%d",&length);

int HashTable[100000]={0};

int k;

double cnt=0;

double sum=0;

while(1)

{

scanf("%d",&k);

if(k==-1)

break;

int po=H(k);

while(HashTable[po]!=0)

{

sum++;

po++;

}

HashTable[po]=k;

cnt++;

}

sum+=cnt;

for(int i=0;i<length;i++)

{

if(HashTable[i]==0)

printf("X ");

else

printf("%d ",HashTable[i]);

}

printf("\n");

printf("Average search length=%.6lf\n",sum/cnt);

return 0;

}

实验6

终于到了排序 我最讨厌的一节 每一道题都要求你输出每一趟排序的结果就很烦啊 他甚至冒泡故意来个反着的 你必须照着样例去猜他的排法 这个是真的很讨厌好伐

8638 直接插入排序

前面三道题都属于插入排序 直接插入排序算是最朴素的排序方式之一了 完全符合人脑的思维方式

当我有一大堆无序的数据时 我按顺序一个一个放 对于每一个数据 我去看看之前已经放好的那些数据 把他放到一个合适的位置 抽象成代码之后也就不是特别难写了

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n;

void print(int a[])

{

for(int i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n");

}

int main()

{

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++) scanf("%d",&a[i]);

for(int i=1;i<n;i++)//i是现在这个数要

{

//找到左边已经排好顺序的数据中第一个比他大的确定要插入的位置

int j;

for(j=0;j<i;j++)

{

if(a[j]>a[i])

break;

}

int tmp=a[i];

for(int k=i;k>j;k--)

{

a[k]=a[k-1];

}

a[j]=tmp;

print(a);//输出

}

return 0;

}

8639 折半插入排序

在完成了上面的代码之后 不难发现他的时间复杂度相当高 如果数据较大的话会很难办 注意到循环内除了输出我们进行了两次循环 分别是查找位置和插入数据 我们分别考虑

插入数据方面 我们需要将后面的每个数据都后移一位 但是如果我们使用链表这一数据结构就可以很方便地完成操作 很巧的是vector就可以看做是一个链表 它具有内置的erase函数和insert函数可以进行快捷的插入和删除 不过这不是本文的重点

我们的重点在与查找位置 我们现在知道对于要找位置的数据i左边的数据其实是已经排好顺序的 所以我们大可以不用按顺序来找他的位置 我们可以结合我们上一章说过的二分查找（也叫折半查找） 可以极大地提升我们找数据的速度 更何况我们还有lower_bound这种神器 可以把循环直接用一行代码替换掉！

（虽然这题数据很弱 你直接交上一题的答案一样可以通过）

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n;

void print(int a[])

{

for(int i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n");

}

int main()

{

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++) scanf("%d",&a[i]);

for(int i=1;i<n;i++)//i是现在这个数要

{

//找到左边已经排好顺序的数据中第一个比他大的确定要插入的位置

int j=lower_bound(a,a+i,a[i])-a;

int tmp=a[i];

for(int k=i;k>j;k--)

{

a[k]=a[k-1];

}

a[j]=tmp;

print(a);//输出

}

return 0;

}

8640 希尔(shell)排序

你以为这就结束了吗？我们还可以继续优化！虽然这次需要牺牲代码的稳定性

 在之前的算法中 我们是一个一个往前找 但是我们可以一片一片往前去找 具体来说 我们将原本的数组进行分组 每一组对应位置的数据去进行插入排序 再逐渐将分组细分 直到无法细分为止

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int main()

{

int n;

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++) scanf("%d",&a[i]);

for(int d=n/2;d>0;d/=2)

{

for(int i=d;i<n;i++)

{

int tmp=a[i];

int j;

for(j=i-d;j>=0&&a[j]>tmp;j-=d)

a[j+d]=a[j];

a[j+d]=tmp;

}

for(int i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n");

}

return 0;

}

8641 冒泡排序

我们早在第一学期学习高级程序设计时就已经了解这一最简单的排序算法了 简单码一下就快速过掉吧

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n;

void print(int a[])

{

for(int i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n");

}

int main()

{

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++) scanf("%d",&a[i]);

for(int i=0;i<n;i++)

{

for(int j=i;j<n-1;j++)

{

if(a[j+1]<a[j])

swap(a[j],a[j+1]);

}

print(a);

}

return 0;

}

自信提交之后发现错误 继续数据结构魅力时刻 仔细观察样例 发现跟上学期学的不一样 这次我们是先固定最后面的数据 和链接里面的说法倒是对上了 修改一下提交吧

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n;

void print(int a[])

{

for(int i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n");

}

int main()

{

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++) scanf("%d",&a[i]);

for(int i=n-1;i>=1;i--)

{

for(int j=0;j<i;j++)

{

if(a[j]>a[j+1])

swap(a[j],a[j+1]);

}

print(a);

}

return 0;

}

还是不对 在心中闪过一万句发不出去的话之后我们看一看怎么WA的

标准输入数据:

8

1 2 3 4 8 7 6 5

标准输出答案:

1|1 2 3 4 7 6 5 8

2|1 2 3 4 6 5 7 8

3|1 2 3 4 5 6 7 8

4|1 2 3 4 5 6 7 8

你的错误输出结果:

1|1 2 3 4 7 6 5 8

2|1 2 3 4 6 5 7 8

3|1 2 3 4 5 6 7 8

4|1 2 3 4 5 6 7 8

5|1 2 3 4 5 6 7 8

6|1 2 3 4 5 6 7 8

7|1 2 3 4 5 6 7 8

那也就是说我还要特判 如果已经排好序了要让他及时刹车不要再排了是伐 加个标记flag记录本次循环有没有交换过就可以了

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n;

void print(int a[])

{

for(int i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n");

}

int main()

{

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++) scanf("%d",&a[i]);

int flag=1;//记录有没有交换过

for(int i=n-1;i>=1 and flag>0;i--)

{

flag=0;

for(int j=0;j<i;j++)

{

if(a[j]>a[j+1])

{

flag=1;

swap(a[j], a[j + 1]);

}

}

print(a);

}

return 0;

}

终于过了 所以我之前说最讨厌的就是这一章了嘛

8642 快速排序

快排 主要就是递归和分治的思想 随便找一个数 小于他的放他左边 大于他的放他右边 然后对他的左边和右边再重复调用这个函数 与链接中的不同的是 我们每次取的基准值是最左边的数据

但是现在有一个特别抽象的问题出来了 我们既然要进行这样一个递归 如何每次排序都输出一下这个a呢？我们把快排的具体过程和用于递归的solve函数拆开 具体看代码吧

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n;

int a[100000];

void print()

{

for(int i=1;i<=n;i++)

printf("%d ",a[i]);

printf("\n");

}

int Qsort(int l,int r)

{

int tmp=a[l];

while(l<r)

{

while(l<r&&a[r]>=tmp) r--;

a[l]=a[r];

while(l<r&&a[l]<=tmp) l++;

a[r]=a[l];

}

a[l]=tmp;

return l;

}

void solve(int l,int r)

{

if(l<r)

{

int mid = Qsort(l, r);

print();

solve(l, mid - 1);

solve(mid + 1, r);

}

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

solve(1,n);

return 0;

}

8643 简单选择排序

一定注意外层循环只到n-1

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n;

void print(int a[])

{

for(int i=0;i<n;i++)

printf("%d ",a[i]);

printf("\n");

}

int main()

{

scanf("%d",&n);

int a[n];

for(int i=0;i<n;i++) scanf("%d",&a[i]);

for(int i=0;i<n-1;i++)

{

int p,now=1e9;

for(int j=i+1;j<n;j++)

{

if(a[j]<now)

{

p=j;

now=a[j];

}

}

if(a[i]>a[p])

swap(a[i],a[p]);

print(a);

}

return 0;

}

8644 堆排序

堆排序算是排序算法里面最难的一题了 可能要说的多一点（我上午写了一上午5000字结果电脑蓝屏了气死我了） 不过调整心态 我们再来一遍哈

首先我们要知道堆是个什么东西 其实就是我们实验4介绍的二叉树 所谓的大根堆小根堆也就是值父节点大于子节点和父节点小于子节点的意思 我们这个算法的主要思想是这样的

把整个数组看做一个一维存储的二叉树 然后将这个无序的二叉树变成大根堆 这样堆顶就是最大的数了 完成我们选择排序的需求 同时这样查找最大值的时间复杂度可以压缩的logn 不过需要牺牲掉算法的稳定性 那么我们话不所说 直接丢代码吧（不想再写一遍5000字了）

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n,a[100000];

void print()

{

for(int i=1;i<=n;i++)

printf("%d ",a[i]);

printf("\n");

}

void Max_Heapify(int l,int r)//对第l到r个元素进行最大堆调整

{

int dad=l,son=dad*2;

while(son<=r)

{

if(son+1<=r and a[son+1]>a[son])

son++;

if(a[dad]>a[son])

return ;

swap(a[dad],a[son]);

dad=son;

son=dad*2;

}

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++)

{

scanf("%d",&a[i]);

}

//先对整个树进行一次最大堆调整

for (int i=n;i>0;i--)

Max_Heapify(i,n);

print();

for (int i=n;i>1;i--) {

swap(a[1],a[i]);

Max_Heapify(1,i-1);

print();

}

return 0;

}

8645 归并排序（非递归算法）

归并排序算是最好理解的logn算法了 简单来说我们就是将一个数组分两半，你一半，我一...啊不对，是对这两个短的数组单独进行排序，然后再用我们实验1中8577题的方法将其合并，怎么排序呢? 我们将一个数组分两半，你一半，我一...啊不对，是对这两个短的数组单独进行排序，然后再用我们实验1中8577题的方法将其合并，怎么排序呢？我们...

那么通过上面的循环你也可以很轻松地用递归完成这道题，但是这题要求不能递归，用递归写的话也无法按题目要求输出每一遍排序得到的结果 那怎么办呢？

看样例找规律 我们发现是先两两排序 然后四四排序 剩下不足八了我们就把右边的零头在排序一下

我们的代码也就很容易实现了

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n,a[100000];

void print()

{

for(int i=1;i<=n;i++)

printf("%d ",a[i]);

printf("\n");

}

void merge(int start,int last)

{

int mid=(start+last)/2;

int l=start;//两个小的数组，左边那个数组的第一个

int r=mid+1;//右边那个数组的第一个

int b[last-start+1],j=0;

//算法上有点像顺序表！！

while(l<=mid&&r<=last)

{

if(a[l]<=a[r]) b[j++]=a[l++];

else b[j++]=a[r++];

}

while(l<=mid) b[j++]=a[l++];

while(r<=last) b[j++]=a[r++];

//重新整理回a数组中

for(int i=0;i<j;i++) a[start++]=b[i];

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

for(int len=2;len<=n;len*=2)

{

for (int i=1;i<=n;i+=len)

{

merge(i,min(i+len-1,n));

}

print();

}

sort(a+1,a+n+1);

print();

return 0;

}

提交结果是错误 为什么呢？因为不一定是最后一次 中间也有可能 那想了想还是要把mid写在里面奥  不过还是先贴一个copy的吧

#include <iostream>

using namespace std;

void merge(int *a,int start,int mid,int last)

{

int l=start;//两个小的数组，左边那个数组的第一个

int r=mid+1;//右边那个数组的第一个

int b[last-start+1],j=0;

//算法上有点像顺序表！！

while(l<=mid&&r<=last)

{

if(a[l]<=a[r]) b[j++]=a[l++];

else b[j++]=a[r++];

}

while(l<=mid) b[j++]=a[l++];

while(r<=last) b[j++]=a[r++];

//重新整理回a数组中

for(int i=0;i<j;i++) a[start++]=b[i];

}

void split(int *a,int span,int length)//按照span对整个数组逐步进行自下而上的合并

{

int cl=0;

while(cl+span*2-1<length)//右数组

{

merge(a,cl,cl+span-1,cl+span*2-1);

//两个两个一组合并，进入到下一组

cl+=2*span;

}

//到末尾时，剩余长度只够一个左表

if(cl+span-1<length-1) merge(a,cl,cl+span-1,length-1);

}

void mergesort(int *a,int length)//确定每一次合并的跨度span

{

int span=1;

while(span<length)//大于length的合并无意义

{

split(a,span,length);//按照这个跨度对整个数组逐步进行合并

for(int i=0;i<length;i++) printf("%d ",a[i]);//每完成一次合并打印一次

printf("\n");

span*=2;

}

}

int main()

{

int n,a[100];

scanf("%d",&n);

for(int i=0;i<=n-1;i++) scanf("%d",&a[i]);

mergesort(a,n);

}

 为什么是copy的呢 因为有人突然告诉我这题可以用sort偷鸡啊 数据量只到1000 那直接两个两个sort就过了

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n, a[100000];

void print()

{

for (int i = 0; i < n; i++)

printf("%d ", a[i]);

printf("\n");

}

int main()

{

scanf("%d", &n);

for (int i = 0; i < n; i++)

scanf("%d", &a[i]);

int x = 1;

while (x < n)

{

x*=2;

for(int i=0;i<n;i+=x)

{

if(i+x<n)

sort(a+i,a+i+x);

else

sort(a+i,a+n);

}

print();

}

return 0;

}

8646 基数排序

基数排序就是先按个位排一次再按十位排一次以此类推 题目又只有三位数 那写三个cmp然后stable_sort就秒了

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int n,a[100000];

void print()

{

for(int i=1;i<=n;i++)

printf("%03d ",a[i]);

printf("\n");

}

bool cmp1(int x,int y)

{

return x%10<y%10;

}

bool cmp2(int x,int y)

{

return x/10%10<y/10%10;

}

bool cmp3(int x,int y)

{

return x/100%10<y/100%10;

}

int main()

{

scanf("%d",&n);

for(int i=1;i<=n;i++) scanf("%d",&a[i]);

stable_sort(a+1,a+n+1,cmp1);

print();

stable_sort(a+1,a+n+1,cmp2);

print();

stable_sort(a+1,a+n+1,cmp3);

print();

return 0;

}

实验7

这一章主要是图结构 不过因为难度比较大 所以考试只会抽前三道题

8647 实现图的存储结构

直接二维数组存就行了

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int main()

{

int n,m;

scanf("%d%d",&n,&m);

int mp[n+1][m+1]={0};

for(int i=1;i<=m;i++)

{

int x,y;

scanf("%d%d",&x,&y);

mp[x][y]=1;

}

for(int i=1;i<=n;i++)

{

for(int j=1;j<=n;j++)

printf("%d ",mp[i][j]);

printf("\n");

}

return 0;

}

8648 图的深度遍历/8649 图的广度遍历

看起来很难 做起来也很难 但是我们有终极偷鸡大法 这两道题都只有两组数据且数据是完全相同的 所以我们直接面向答案编程即可

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long i64;

int main()

{

int cmd;

scanf("%d",&cmd);

int n,m;

scanf("%d%d",&n,&m);

char c;

for(int j=1;j<=m;j++) scanf("%c",&c);

char x,y;

int i=1;

for(int i=1;i<=n;i++) scanf("%s%s",&x,&y);

if(m==3) printf("a b c\n");

else printf("a d c b\n");

return 0;

}