SCAU期末笔记 - 数据结构（STL版）
在完结了算法之后 我又来写数据结构啦！真的很讨厌校OJ数据结构的题，输出提示词太捞了，每一题都是超级缝合怪，像个小课设一样。
值得一提的是，虽然数据结构课上要求是用C语言实现这些功能，但是因为频繁用到引用，所以考试可以直接提交C++，再加上机试没有填空题，所以我们完全可以直接使用C++的STL，本文也是直接使用STL实现的。
但是！这并不代表数据结构实现的原理不重要，因为我们数据结构的笔试的大题会要求你在试卷上进行试卷填空，这一部分等我有空再开一篇文章，如果你在CSDN搜到别的看不懂的话，建议翻开你的高程回去恶补指针，结构体相关知识。那么闲话少叙，我们直接开始！
实验1
本章主要介绍了顺序表这一数据结构，我们使用STL的话对应的就是vector这一容器了。使用时需要引用头文件
常用的相关函数有这些
vector 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
#include
#include
using namespace std;
typedef long long i64;
int main()
{
vector 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(ndata = 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 && jnext;
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
#include
#include
using namespace std;
typedef long long i64;
int main()
{
int n,m;
scanf("%d",&n);
vector a(n);
for(int i=0;inext=p;//头结点的next指向p
p=q;//p指向下一个节点
}
实验2
本章我们使用的有STL中的stack容器 需要引入头文件 其主要特点是单向入栈单向出栈且遵循后进先出的特点 你可以理解为一根杆子上的一堆秤砣 就像这张图上这样
那么主要用到的函数我们也是一样摆在下面（size和empty这种意思没啥区别的就不单独列了）
stack s;//定义一个栈 s.push(8);//在栈顶插入元素8 s.pop();//弹出栈顶元素 int c=s.top();//让c等于栈顶元素 但是不弹出
除此之外 我们还要用queue这一容器 引用头文件即可使用 队列则是与上面相反 遵循先进先出的规则
主要用到的函数如下
queue q;//创建一个int类型数据组成的队列q q.push(8);//将8放在队列尾端 q.pop();//弹出队列前端的元素 q.front();//返回队列前端的元素 q.back();//返回队列尾端的元素
8583 顺序栈的基本操作
又是我最讨厌的小型课设 利用上面介绍的函数可以很轻松地完成这些问题
#include
#include
#include
using namespace std;
typedef long long i64;
int main()
{
stack 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 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
#include
#include
using namespace std;
typedef long long i64;
int main()
{
queue 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 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
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
#include
#include
using namespace std;
typedef long long i64;
int main()
{
string s;
cin>>s;
int l=s.length();
vector st;
for(int i=0;i0)//每次读到回车就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
#include
#include
using namespace std;
int main()
{
int n;
scanf("%d\n",&n);
vector 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>s;
int l=s.length();
//先转为后缀表达式
stackopt;//存符号
stacknum;//存数字
vectorall;//存后缀表达式
for(int i=0;i=getValue[s[i]])
{
all.push_back(opt.top());
opt.pop();
}
opt.push(s[i]);
}
}
//计算后缀表达式
l=all.size();
stackdigit;//记录待计算的数字
for(int i=0;i>n>>a>>b>>c;
hnt(n,a,b,c);
return 0;
}
实验3
这一章主要讲的就是KMP算法 特别是next值的计算
8591 计算next值
坏消息是学校的next值和常搜到的定义有些许出入 可能需要背一下
#include
#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 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
#include
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;i0 and irchild);// 构造右子树
}
return OK;
} // CreateBiTree
Status PreOrderTraverse(BiTree T)
{
// 前序遍历二叉树T的递归算法
//补全代码,可用多个语句
if(T==NULL)
return 0;
coutlchild);
PreOrderTraverse(T->rchild);
return 1;
} // PreOrderTraverse
Status InOrderTraverse(BiTree T)
{
// 中序遍历二叉树T的递归算法
//补全代码,可用多个语句
if(T==NULL)
return 0;
InOrderTraverse(T->lchild);
coutrchild);
return 1;
} // InOrderTraverse
Status PostOrderTraverse(BiTree T)
{
// 后序遍历二叉树T的递归算法
//补全代码,可用多个语句
if(T==NULL)
return 0;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
coutrchild);// 构造右子树
}
return OK;
} // CreateBiTree
int ans[3]={0};
Status PreOrderTraverse(BiTree T)
{
if(T==NULL)
return 0;
//coutlchild);
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
#include
#include
using namespace std;
typedef long long i64;
int child[10000][2];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i> s2;
int len1 = s1.size();
int len2 = s2.size();
solve(0, len1 - 1, 0, len2 - 1);
return 0;
}
18923 二叉树的直径
看起来这一题是要我们遍历每一个点去两个方向找 但是其实你可以发现我们只需要对一个点左边找最深再右边找最深加起来就可以了 不过dfs应该不用再多说了吧
（虽然后来我发现直径的路径一定经过根节点 但是反正都能过就懒得改了）
#include
#include
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 > x >> y;
if (!child[x][0])
child[x][0] = y;
else
child[x][1] = y;
}
for (int i = 1; i
免责声明：我们致力于保护作者版权，注重分享，被刊用文章因无法核实真实出处，未能及时与作者取得联系，或有版权异议的，请联系管理员，我们会立即处理! 部分文章是来自自研大数据AI进行生成,内容摘自(百度百科,百度知道,头条百科,中国民法典,刑法,牛津词典,新华词典,汉语词典,国家院校,科普平台)等数据,内容仅供学习参考,不准确地方联系删除处理! 图片声明：本站部分配图来自人工智能系统AI生成,觅知网授权图片,PxHere摄影无版权图库和百度，360，搜狗等多加搜索引擎自动关键词搜索配图，如有侵权的图片，请第一时间联系我们，邮箱：ciyunidc@ciyunshuju.com。本站只作为美观性配图使用,无任何非法侵犯第三方意图,一切解释权归图片著作权方,本站不承担任何责任。如有恶意碰瓷者,必当奉陪到底严惩不贷!
