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

吉师散养基地

发布于 2023-04-27 15:06:24

1900

发布于 2023-04-27 15:06:24

文章被收录于专栏：我奏是太阳我奏是太阳

前言

划了半个学期的水，明天下午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节点数据域中的值等于a
            p->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;                                //插入的结点为p
    p = (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;//为空栈
    else
        return 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]//将栈顶值保存至x
    S->top--;//移动栈顶指针
    return (x);
}

读取栈顶元素

DataType GetTop(LinkStack * Top)

{
    if (Top == NULL)
        printf("\n栈空");
    else
        return 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

我是笨比，不会写。