【数据结构】期中考试一把梭(通宵版上)

news/2025/1/11 8:17:17/

前言

红中(Hong_zhong)
CSDN内容合伙人、2023年新星计划web安全方向导师、
吉林师范大学网安大一的一名普通学生、摸鱼拿过大挑校二、
华为MindSpore截至目前最年轻的优秀开发者、IK&N战队队长、
阿里云专家博主、华为网络安全云享专家、腾讯云自媒体分享计划博主、

划了半个学期的水，明天下午C的数据结构期中考试。

众所周知，让我学C==让我s->True。

没办法，之前学Python的数据结构直接学的排序查找二叉树，这几个玩意还在后面几章。

链表啥的听都没听过。

我只想不挂，简单熬个夜。

开干

链表

链表的初步印象

链表，即链式存储结构。

 DATA是咱自定义的数据类型，NEXT为指向下一个链表的指针。当我们访问NEXT时，被引导到链表下一个节点的位置。

抽象点就类似于火车车厢

 一节车厢前面是节点，后面是指针，中间连接即指针指向的位置。

链表与数组的差别

那这玩意相较于数组，插入删除等操作变得更加容易。

为啥这么说捏？

打个比方，现在有这样一个数组：

[1,2,3,4,5,6,7,8]

我想在“1”之后插入一个”9“，那就意味着”1“之后的所有元素都需要向后挪一位，然后再整一块新的内存空间，把”9“塞里。麻烦死

但如果是链表，先抽象说说，想在火车车厢间加一节，只需要把车厢之间的链子解开，后面的先挂到新车厢上，前面再挂，完事了。

不需要整体/大部分数据去调整，改变指针所指向的DATA就行了，确实方便。

不过这玩意占用相较于数组大了不只一点(真特么难写

链表常见类型

单链表、双链表、循环单链表

 图片来源：一口气搞懂「链表」，就靠这20+张图了 - 知乎

单链表

单链表概念的代码表述：

typedef struct Node{//定义单链表的结点类型int data;//数据域，随便写哪种类型都可以struct Node *next;//指针域}Node,*LinkList;//Node表示结点的类型，LinkedList表示指向Node结点类型的指针类型

链表的初始化

LinkedList listinit(){Node *L;L=(Node*)malloc(sizeof(Node));//申请开辟空间if(L==NULL){printf("申请失败");//判断是否开辟成功}L->next=NULL;//指针指向NULL
}

申请开辟空间那块咱也不到是啥，背下来就完了。

头插法

这玩意其实挺好理解的

准备一张图用到s

 这是一个节点，头插即从头插。假设我再来一个节点，即可以把新节点的指针指向原节点的DATA处。原节点始终排在后面，即到最后整条链表的顺序为倒序。

代码实现：

LinkedList LinkedListCreate(){Node *L;L=(Node *)malloc(sizeof(Node));L->next=NULL;int x;//x为链表中的数据while (scanf("%d",&x!=EOF)){Node *p;//定义p的指针域p=(Node *)malloc(sizeof(Node));//申请空间p->data=x;//将x赋给p节点的数据域p->next = L->next;//将头指针所指向的下一个结点的地址，赋给新创建结点的next L->next = p;//将新创建的结点的地址赋给头指针的下一个结点}return L;
}

尾插法

尾插法同样的理解，原节点的指针指向新节点的DATA域。

不解释，直接写代码：

LinkedList LinkedListCreate(){Node *L;//申请指针域L=(Node *)malloc(sizeof(Node));//申请头节点空间L->next=NULL;//初始化一个空链表Node *r;r=L;//r始终指向尾节点，开始时指向头节点int x;//x为链表DATA中的数据while (scanf("%d",&x)!=EOF){Node *p;//申请指针域p=(Node *)malloc(sizeof(Node));//申请新的节点p->data=x;r->next=p;r=p;//r始终指向尾节点}r=next=NULL;return L;
}

修改

LinkedList LinkedListReplace(LinkedList L,int a,int b) {Node *p=L->next;//定义指针域指向节点指针指向int i=0;while(p){if(p->data==a){//如果p节点数据域中的值等于ap->data=b;//将p节点数据域中的值a改成b}p=p->next;//节点指针依旧指向后面}return L;
}

插入

LinkedList LinkedListInsert(LinkedList L,int i,int x) {Node *pre;                      //pre为前驱结点pre = L;int tempi = 0;for (tempi = 1; tempi < i; tempi++) {pre = pre->next;                 //查找第i个位置的前驱结点}Node *p;                                //插入的结点为pp = (Node *)malloc(sizeof(Node));p->data = x;//给p赋个值p->next = pre->next;//将前驱节点之前指向的地址赋给插入节点并让其指向pre->next = p;//将前驱节点指针指向引导到新节点头上return L;
}

删除

LinkedList LinkedListDelete(LinkedList L,int x) {Node *p,*pre; //pre为前驱结点，p为查找的结点。p = L->next;while(p->data != x) {//查找值为x的元素pre = p;p = p->next;}pre->next = p->next;//删除操作，将其前驱next指向其后继。free(p);//free函数释放掉return L;
}

双链表不写，赌他不考。

习题

 第一题、第二题：随便举几个推值代数。

第三题直接带。第四题看图嘛

真-用到s

 第五题：涉及概念

存储密度，在计算机中是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，计算公式：存储密度 = （结点数据本身所占的存储量）/（结点结构所占的存储总量）

 第六题：顺序表简单了解下

 第十/十一题：带头单链表就是指针域指向空，不带头就自己是空。

感觉没啥好讲的，直接填空看看

 

 简单过过知识点，没啥难点，

栈

原理/概念

之前学过Python的栈，简单聊聊原理，看看代码实现，做点题就过了。

栈这个东西类似于一个桶形书架。

刚开始书架是空的，我们放里面一本《母猪的产后护理》，好，栈内已经有一本书了

现在我们再往里放一本《我是如何因为CTF毁掉自己人生的》，现在栈内有两本书

 如果我们想看《母猪的产后护理》，又不能直接从栈底抽出来，就只能先把

《我是如何因为CTF毁掉自己人生的》拿出来，再得到我们想要的书。

那这里的顺序就是一个栈的特性：先进后出

反正我就记得这一个，再说也说不了啥了，看代码实现。

代码实现

不难

置空栈

void InitStack(SeqStack *S){S->top=-1;
}

判定栈空否

int EmptyStack(SeqStack * S){if (S->top<0)return 1;//为空栈elsereturn 0;//不为空栈
}

进栈

int Push(SeqStack * S,DataType x){if (S->top>=MAXSIZE-1)//{    printf("栈满不能进栈");return 0;}S->top++;//移动栈顶指针S->data[S->top]=x;//元素x进栈return (1);
}

出栈

和入栈差不多嘛

int Push(SeqStack * S){if (S->top《=MAXSIZE-1)//{    printf("栈空不能出栈");exit(0);}x=S->data[S->top]//将栈顶值保存至xS->top--;//移动栈顶指针return (x);
}

读取栈顶元素

DataType GetTop(LinkStack * Top){if (Top == NULL)printf("\n栈空");elsereturn Top->data;
}

完整代码及示例：

#include<bits/stdc++.h>
using namespace std;#define MaxSize 100 //定义栈中元素的最大个数
typedef struct SqStack{int data[MaxSize]; //存放栈中的元素int top; //栈顶指针
}SqStack;//初始化
void InitStack(SqStack &S){S.top = -1;
}//判栈空
bool Empty(SqStack S){if(S.top == -1){return true;}else{return false;}
}//入栈
void Push(SqStack &S, int x){if(S.top == MaxSize-1){cout<<"栈满"<<endl;return;}S.data[++S.top] = x;
}//出栈
void Pop(SqStack &S, int &x){if(S.top == -1){cout<<"栈空"<<endl;return;}x = S.data[S.top--];
}//读栈顶元素
int GetTop(SqStack S){if(S.top == -1){cout<<"栈空"<<endl;return -1;}else{return S.data[S.top];}
}//遍历栈
void PrintStack(SqStack S){while(S.top != -1){cout<<S.data[S.top--]<<" ";}cout<<endl;
}//销毁栈
void DestroyStack(SqStack &S){S.top = -1;
}int main(){SqStack S;InitStack(S);Push(S,1);//入栈Push(S,2);Push(S,3);Push(S,4);cout<<"栈顶元素为："<<GetTop(S)<<endl;cout<<"出栈顺序为：";PrintStack(S);int x;Pop(S,x);cout<<x<<"出栈"<<endl;cout<<"栈中剩余元素：";PrintStack(S);Pop(S,x);cout<<x<<"出栈"<<endl;cout<<"栈中剩余元素：";PrintStack(S);if(!Empty(S)){cout<<"当前栈不为空"<<endl;}else{cout<<"当前栈为空"<<endl;}return 0;
}

来自栈——栈的定义及基本操作（初始化、判空、进栈、出栈、遍历栈、销毁栈等）_薛定谔的猫ovo的博客-CSDN博客w

 我是笨比，不会写。

习题

 第一题特性，第二题栈顶。

链栈虽然没说，但是通过链表的学习也差不多了。

第三题有点问题，第四题先把值保存在x里，然后改指针域。

家人们谁懂啊，明天再写，累了


http://www.ppmy.cn/news/47179.html

相关文章

推动开发者平台本土化，高通加速中国XR内容生态发展

推动开发者平台本土化，高通加速中国XR内容生态发展

随着VR和AR技术快速发展&#xff0c;产品不断成熟&#xff0c;体验也变得越来越优秀。据悉&#xff0c;Meta Quest系列VR头显出货量超2000万台&#xff0c;基本证明了VR开始在消费类电子产品中占据一席之地。与此同时&#xff0c;近两年AR眼镜也在逐渐升温&#xff0c;成为了创…
阅读更多...
并发编程之五FutureTask

并发编程之五FutureTask

futureTask实现了Runnable, Future接口&#xff0c;Future接口有如下定义&#xff1a; /*** 取消任务&#xff0c;如果任务已经在执行&#xff0c;mayInterruptIfRunning为true&#xff0c;则* 向执行线程发送interrupt事件&#xff0c;否则任由任务执行完毕。* 返回值为是否取…
阅读更多...
VMware开机自启虚拟机系统

VMware开机自启虚拟机系统

一、前提 wmware开机自启&#xff0c;安装完毕wmware不用管&#xff0c;默认该软件以及相关服务就是开机自启准备waware虚拟机&#xff08;一般都linux&#xff0c;我用centos7&#xff0c;你随意&#xff09; 二、脚本 脚本命令如下&#xff0c;等待30秒&#xff08;给服务自启…
阅读更多...
计算机组成原理——第五章中央处理器（上）

计算机组成原理——第五章中央处理器（上）

半生风雨半生伤&#xff0c;半醉半醒半心凉 文章目录 前言5.1 CPU的功能和基本结构5.2 指令周期的数据流5.3.1 单总线结构5.3.2 专用通路结构 前言 之前我们就说过CPU主要包括两个部分&#xff0c;运算器和控制器&#xff0c;运算器主要是实现算数运算.逻辑运算&#xff0c; 运…
阅读更多...
Memory Analyzer Mat

Memory Analyzer Mat

目录 一、JDK 、JRE和JVM 的关系 二、Java进程内存占用查询命令 2.1JAVA 代码是如何执行的 2.2何时用hrpof文件分析内存 三、Memory Analyzer Mat 3.1Memory Analyzer Mat安装 3.2 Overview视图 3.2.1直方图视图&#xff08;histogram&#xff09; 3.2.2 Dominator Tr…
阅读更多...
字典树p8036

字典树p8036

Description 给定 &#xfffd;n 个模式串 &#xfffd;1,&#xfffd;2,…,&#xfffd;&#xfffd;s1​,s2​,…,sn​ 和 &#xfffd;q 次询问&#xff0c;每次询问给定一个文本串 &#xfffd;&#xfffd;ti​&#xff0c;请回答 &#xfffd;1∼&#xfffd;&#xfff…
阅读更多...
NetSuite GPT的辅助编程实践

NetSuite GPT的辅助编程实践

作为GPT综合症的一种表现&#xff0c;我们今朝来探究下GPT会不会抢了我们SuiteScript的编程饭碗&#xff0c;以及如何与之相处。以下内容来自我个人的实践总结。 我们假设一个功能场景&#xff1a; 为了让用户能够在报价单上实现“一键多行”功能&#xff0c;也就是在报价中可…
阅读更多...
learn_C_deep_1 (C程序补充知识、变量的声明和定义、声明和定义的区别)

learn_C_deep_1 (C程序补充知识、变量的声明和定义、声明和定义的区别)

目录 C程序补充知识 变量的声明和定义 1.什么是变量&#xff1f; 2.变量的本质是什么&#xff1f; - 所有的变量都要在内存的某个位置开辟空间 3.变量的定义和声明形式、初始化和赋值的区别 4.为什么要定义变量 声明和定义的区别 C程序补充知识 先让我们来看一段C语言…
阅读更多...
最新文章

Copyright @ 2022~2023