数据结构复习(1~3)

第一章绪论

 第一章的主要的还是概念居多，我根据自己的理解写了个思维导图

 导图链接点这里

第二章 基本的线性结构

这章链表代码的理解是重点，先来看顺序表吧（我的理解全写在注释里了xixi）

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
struct seq
{
    int date[maxn],last;
};
seq *init()
{
    seq *l;       ///联想一下seq的基本组成应该不会遗漏
    l=(seq *)malloc(sizeof(seq));
    l->last=-1;
}
int insert(seq *l,int i,int x)///注意这个*，将主函数中的顺序表引用
{
    if(i==l->last-1){      ///算法健壮性的思路来源于函数参数，思考一下函数参数
        printf("表满\n");    ///是否合法就能理解写出 /滑稽
        return -1;
    }
    if(i<1||i>l->last+2)      ///注意i的含义不是指数组下标，而是位置（从一开始算起）
    {                        ///将i-1，转化成数组下标好理解一些
        printf("位置错误\n");
        return 0;
    }
    int j;
    for(j=l->last;j>=i-1;--j)  ///倒序的思想其实就是优先让数组最后一个元素填补空位
        l->date[j+1]=l->date[j];    ///防止元素覆盖
    l->date[j-1]=i;
    ++l->last;                     ///不要忘了last的更新
    return 1;
}
int Delete(seq *l,int i)
{
    if(i<1||i>l->last+1)  ///将i减1其实就是数组下标范围
    {
        printf("不存在第i个元素\n");
        return 0;
    }
    for(int j=i;j<=l->last;++j)   ///注意第i个元素对应的数组下标就是i-1，顺序思想：以后面元素覆盖第i个元素
        l->date[j-1]=l->date[j];
    --l->last;
    return 1;
}
int location(seq *l,int x)
{
    int i=0;
    while(i<=l->last&&l->date[i]!=x)///在while的括号中就已经添加了判断条件
        ++i;
    if(i>l->last)
        return -1;
    else
        return i;
}
void part(seq *l)
{
    int x=l->date[0],y;        ///x既临时存储了比较对象，又是交换date[0]和date[i]的中间变量
    for(int i=1;i<=l->last;++i)
    {
        if(l->date[i]<x)
        {
            y=l->date[i];      ///最后还是要用的，所以先存一波
            for(int j=i-1;j>=0;--j)///逆序覆盖下标为i的位置（下标从0到i-1的那一排数整体后移）
                l->date[j+1]=l->date[j];
            l->date[0]=y;      ///比x小的填在了x的前面
        }
    }
}
int main()
{
    seq *l;
    l=init();
}

再来看一波链表，这个是再刘波学长代码的基础上打了一波注释

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
typedef struct node
{
    int data;
    struct node *next;
} LNode,*LinkList;       ///要使用到malloc函数
LinkList L;
LNode *head=(LNode *)malloc(sizeof(LNode));  ///百度一波malloc函数用法，以void*类型返回分配的内存区域地
LNode *creat_L()                             ///不难理解为什么定义了一个指针
{
    L=head;
    LNode *r=head;
    printf("请输入数字用以创建链表，输入0结束\n");
    int num;
    scanf("%d",&num);
    while(num!=0)
    {
        LNode *p=(LNode*)malloc(sizeof(LNode));
        p->data=num;        ///存数
        r->next=p;         ///尾插结点
        r=p;               ///尾结点更新
        scanf("%d",&num);  ///跟循环迭代更新差不多
    }
    r->next=NULL;
    return L;
}
void show_L(LinkList L)  ///循环遍历更新
{
    if(L->next==NULL)    ///考虑遍历的前提条件表不空
    {
        printf("Link is empty");
    }
    else
    {
        LNode *p=L->next;
        printf("%d",p->data);
        while(p->next!=NULL)///循环遍历
        {
            p=p->next;      ///迭代更新
            printf(" %d",p->data);
        }
        printf("\n");
    }
}
LNode *get_L(LinkList L,int location)
{
    LNode *p=L;
    int i=0;
    while(p->next!=NULL&&i<location)
    {
        p=p->next;
        i++;
    }
    if(i==location)
        return p;
    else
        return NULL;
}
int delete_L(LinkList L,int location)
{
    LNode *p,*s;
    p=get_L(L,location-1);
    if(p==NULL||p->next==NULL)
        return 0;
    else
    {
        s=p->next;         ///第三步要用，先存一波
        p->next=s->next;   ///成功绕过s连根线
        free(s);           ///释放结点，节省空间嘛
        return 1;
    }
}
int insert_L(LinkList L,int location,int num)
{
    LNode *p,*s;
    p=get_L(L,location-1);  ///找到位置的前一个结点，后面就进行前插
    if(p==NULL)
        return 0;
    else
    {
        s=(LNode *)malloc(sizeof(LNode));///建立结点
        s->data=num;                     ///存数
        s->next=p->next;    ///注意顺序（其实陈兴华老师的气球理论可以理解，先将新加入的气球的尾部
        p->next=s;          ///连接后面的气球（防止先将p气球的尾部连接新加入的气球后，后面的气球飞了））
        return 1;
    }
}
int main()
{
    L=creat_L();
    char str[20];
    printf("请输入相关指令，包括：insert，show，delete，get\n");
    while(~scanf("%s",str))
    {
        if(strcmp(str,"insert")==0)
        {
            printf("请输入你所要插入的地址及数值\n");
            int location;
            int num;
            scanf("%d%d",&location,&num);
            int flag=insert_L(L,location,num);
            if(flag==1)
            {
                printf("insert OK\n");
                printf("插入成功，插入后的链表为：\n");
                show_L(L);
            }
            else
                printf("insert fail\n");
        }
        if(strcmp(str,"show")==0)
        {
            printf("链表为：\n");
            show_L(L);
        }
        if(strcmp(str,"delete")==0)
        {
            printf("请输入需要删除的位置:\n");
            int location;
            scanf("%d",&location);
            int flag=delete_L(L,location);
            if(flag==1)
            {
                printf("delete OK\n");
                show_L(L);
            }
            else
                printf("delete fail\n");
        }
        if(strcmp(str,"get")==0)
        {
            printf("请输入你想要得到数值的位置:\n");
            int location;
            scanf("%d",&location);
            LNode *p=get_L(L,location);
            if(p==NULL)
            {
                printf("get fail\n");
            }
            else
            {
                printf("获取成功,其数值为：\n");
                printf("%d\n",p->data);
            }
        }
    }
    return 0;
}

第二章中的栈和队列其实跟链表差不多，我就不重复了（qwq）

第二章中前缀表达式和后缀表表达式----先插一句，其实我也没听懂老师在讲什么，但人是活的嘛，一题多解很正常，有一个更简单的添括号法可以解决（hahaha）------按照乘除优先和从左至右的顺序添加括号（反正有多少个运算符就有多少个括号），求前缀表达式就把所有运算符提到括号前，再把括号去掉，同理可得后缀表达式。详情点这里

第三章 线性结构的扩展

可能这章最难最是kmp了吧qwq

先来搞定next数组

想要理解next数组必须要先弄懂next数组的定义 /滑稽

先来解读一波：j=1时next数组的值为0；存在公共前后缀时，next数组的值为模式串下标为1~j-1最长公共前后缀的长度加一（看第二行表达式，最长公共前后缀长度=k-1，所以变换一下，k就是最长公共前后缀的长度加1呀）；模式串下标为1到j-1中不存在最长公共前后缀这种情况，这时next数组的值就是1，套上这层理论，书上next数组的值就能推出来了

如果还不懂得话，用上述理论操作一波  /斜眼笑

谈谈我对kmp算法得理解

kmp算法其实对模式串有要求：其从下标为1开始得某一字串存在最长公共前后缀，正应为如此下图中画圈的部分已经默认比较了一次，所以只需要移动模式串到3的位置即可进行下步操作，所以next数组的存在就是寻找回溯的位置

 最后，发波代码，再帮你理解一波 qwq

#include<bits/stdc++.h>
using namespace std;
char zc[1000],msc[10000];  ///zc就是主串的拼音的首字母，msc就是模式串的首字母
int next[1000];
void getnext()   ///发现没有，这个代码跟kmp函数有点像，可以理解成两个模式串的匹配
{
    int j=1,k=0,ls=strlen(msc+1);///模式串的长度求法需要注意一下，因为输入就是从下标为1开始输入的
    next[1]=0;            ///next数组的定义赋初值
    while(j<ls)
    {
        if(k==0||msc[j]==msc[k]) ///k==0，next数组定义的第三条：不存在最长公共前后缀
            ++j,++k,next[j]=k;   ///k的含义在上步就是最长公共前后缀
        else
            k=next[k];           ///回溯到next[k]的位置
    }
}
int kmp()
{
    int i=1,j=1,len1=strlen(zc+1),len2=strlen(msc+1);
    while(i<=len1&&j<=len2)
    {
        if(j==0||msc[j]==zc[i])
            ++i,++j;
        else j=next[j];
    }
    if(j>len2) return i-len2;
    else return 0;
}
int main()
{
    scanf("%s",zc+1);///字符串从下标从1开始
    cout<<"模式串为"<<endl;
    while(~scanf("%s",msc+1)){
    getnext();
    //printf("%d\n",strlen(msc+1));
    cout<<"next数组的值"<<endl;
    for(int i=1;i<=strlen(msc+1);++i)
        cout<<next[i]<<' ';
    cout<<endl;
    cout<<"模式串为"<<endl;
    }
    //cout<<(kmp())<<endl;
}

稀疏矩阵的转置

再插一句-----直接遍历date数组中的元素不就完事了，干嘛搞得这么复杂，其实转置后的存的时候date数组是按第一列第一个非0元素，第一列第二个非0元素，第三列……按顺序存的，所以聪明的计算机大佬就发明了num数组和cpot数组来实现原数组下标和转置后date中的下标进行转换，就可以实现我起初的异想天开。我把我的理解全放在代码的注释里了，注意看哦

#include<bits/stdc++.h>
using namespace std;
const int maxn=1024;
int n,m;
struct spnode
{
    int i,j,x;
};
struct sp
{
    int h,l,num_;   ///h是行的拼音首字母，l是列的首字母，num_是非零元素的个数
    spnode date[maxn];
};
sp *zhuanzhi(sp *a)
{
    sp *b;
    b=(sp *)malloc(sizeof(sp));
    b->h=a->l,b->l=a->h,b->num_=a->num_;  ///行列交换一下
    int num[n+1],cpot[n+1];
    if(b->num_>0)
    {
        for(int i=1; i<=a->l; ++i)  ///赋初值
            num[i]=0;
        for(int i=1; i<=a->num_; ++i)    ///遍历date数组，统计a中各列非零元的个数
        {
            int j=a->date[i].j;
            num[j]++;
        }
        cpot[1]=1;                   ///赋初值
        for(int i=2; i<=a->l; ++i)
            cpot[i]=cpot[i-1]+num[i-1];
        for(int i=1; i<=a->num_; ++i)
        {
            int j=a->date[i].j;      ///date数组中每个元素的位置
            int k=cpot[j];           ///转置后该元素在b->date中的位置
            b->date[k].i=a->date[i].j;
            b->date[k].j=a->date[i].i;
            b->date[k].x=a->date[i].x;
            ++cpot[j];               ///a矩阵中每一列可能有多个元素，cpot[j]+1,表示这一列下一个元素在b->date中的位置
        }
    }
    return b;
}
int main()
{
    sp *a,*c;
    a=(sp *)malloc(sizeof(a));
    cin>>m>>n;
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=m; ++j)
        {
            int z;
            scanf("%d",&z);
            if(!z)
                a->date[++a->num_].x=z,a->date[a->num_].i=i,a->date[a->num_].j=j;
        }
    c=zhuanzhi(a);
}

总结：

数据结构的学习最好自己将代码写一遍，便于发现问题

多画图来理解代码，特别是学习树和图的时候

后面的练习题还是可以写一写滴

注：有什么不懂的可以在评论区留言，欢迎提问哦 haha