LikeWater - 1677: 数据结构-静态链表（又是一个怎么也找不到错误的题！！！ヾ(≧へ≦)〃）

363 阅读 9 评论 0 点赞

***————天空是蓝色的，海也是蓝色的，但其实海是反射了天空的颜色才变的蓝，我的答案是正确的，大佬的答案也是正确的，但其实是我copy的大佬的代码，ctrl+x！***
**——————————————————————————————————————————**
#####不是我想copy，实在是调试找错误太难了，比如今天这个静态链表（稍后我附上所有的代码，正确的+自己的，如果能有大佬帮帮找下错误，老夫感激不尽！！），我对着答案那是一个字一个字看，硬是没找到错误在哪，我不就加了一个删除功能，为啥就算我错了，怎么提交怎么错，拿大佬代码提交那就对了，怀疑有歧视！！！但是又没有证据，只能悻悻作罢，但是我的代码在其他ide下运行或者在线测试怎么输入输出都是对的，所以是真的难受，想必很多同学跟我有同样的经历，这种经历十分折磨人，如果有大佬知道如何快速的找到错误，请不吝赐教！多谢大家！❤

**——————————————————————————————————————————**
*虽然是这么说，但是题目还是不太难的，同上一个指针链表相比，静态链表是更加熟悉的数组来进行操作，对于大部分同学来说，数组要比指针更加熟练，这个静态链表自然也就更加简单，下面我指出一下这个题目的重点和难点，同时给出相应的解法。*

1、怎样将字符串类型定义为ElemType呢？形如typedef int num一样，数组或者指针可以放在定义的类型名后面，例如将具有8个字符的姓氏定义为ElemType可以这样定义：typedef char ElemType[8]。
***————PS.起初我并不知道为什么这样定义，还以为是typedef char[8] ElemType;但是发出错，相比是算法这样设计着好看吧，具体原因有知道的大佬可以留在评论区***

2、题目和书中给的算法描述还缺少静态链表的插入、删除以及显示，都需要自己写。
***————插入删除和显示中插入和删除应该是里面最难写的，但是只要结合上次的指针链表，加画图，就能很轻松的编写出来，自己编写也对能力有提升！！***

3、要求每个指令输出后跟20个星号和一个空行。
***————这是一个易出错的点，我开始出错的时候就是因为这个原因，我还觉得欣喜，因为这是个小问题，没想到是我无法见到的深渊，太黑了，我找不到那个该的隐藏在其中的问题！！！***

4、姓氏占8个字符，数字占2个字符，姓氏左对齐，可以这样输出printf("%-8s%2d");对于指令search也要输出占2个字符的数字。
***————printf的格式化输出说实话我都快忘记了，有跟我一样记不清的可以看下这下面的链接：[printf格式化输出](https://baike.baidu.com/item/printf/7467706 "printf格式化输出")***

5、静态链表初始化时将所有内存设为空，可以在InitSpace_SL中使用下面的方法：
memset(space, 0 ,sizeof(space));
***————这个函数我也是查阅之后才知道的，相较于其他方法初始化内存，这个函数应该是最快的方法，下面是它的定义和描述：***
    `void *memset(void *s, int ch, size_t n);`
        `函数解释：将s中当前位置后面的n个字节 （typedef unsigned int size_t ）用 ch 替换并返回s`
        `memset：作用是在一段内存块中填充某个给定的值，它是对较大的结构体或数组进行清零操作的一种最快方法。`
        `memset()函数原型是extern void *memset(void *buffer, int c, int count)`
        `buffer：为指针或是数组,c：是赋给buffer的值,count：是buffer的长度.`

**————基本上到这里，大部分题目已经能够迎刃而解，还有一个昨天的问题，在循环中不要使用cin和cout，不然会时间超限，这个问题昨天已经解释，大家可以再去看看，复习一下，巩固知识点：[LikeWater - 1676: 数据结构-链表的基本操作（本以为一切顺利，没想到只有我是小丑！！！）](https://blog.dotcpp.com/a/94473 "LikeWater - 1676: 数据结构-链表的基本操作（本以为一切顺利，没想到只有我是小丑！！！）")**

⭐⭐⭐下面是我的代码，里面给了十分详细的注释，对于大家理解代码自己编写很有帮助，有需要的可以继续往下翻阅，希望大家能够获得帮助，有需要可以留言，比起一直敲代码，我也喜欢跟大佬交流战况！

```cpp
#include<iostream>
#include<string>
#include<string.h>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MaxSize 11
#define ListSize 9
int length=0;//静态链表大小
int elem;//静态链表头指针地址
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef char ElemType[8]; //ElemType 为可定义的数据类型

typedef struct SNode{
    ElemType name;
    int cur;
    SNode() {}
    SNode(ElemType Name,int CUR){strcpy(name,Name);cur = CUR;}
}SNode,SLinkList[MaxSize];

void InitSpace_SL(SLinkList &space){
    //将一维数组space中各个分量链成一个备用链表，space[0].cur为头指针
    //"0"表示空指针
    memset(space,0,sizeof(space));
    for(int i=0;i<MaxSize-1;i++){
        space[i].cur = i+1;
        strcpy(space[i].name," ");
        strcpy(space[MaxSize-1].name," ");
    }//InitSpace_SL
}

void Show_SL(SLinkList space){
    //展示整个静态链表
    for(int i=0;i<MaxSize;i++){
        printf("%-8s%2d\n",space[i].name,space[i].cur);
    }
    printf("********************\n");
}

int Malloc_SL(SLinkList &space){
    //若备用空间链表非空，则返回分配的结点下标，否则返回0
    int i = space[0].cur;
    if(i)space[0].cur = space[i].cur;//将备用链表的头指针space[0].cur指向下一个备用结点。
    return i;
}//Malloc_SL

void Free_SL(SLinkList &space,int k){
    //将下标为k的空闲结点回收到备用链表中来。
    space[k].cur = space[0].cur;//头插法插入到备用链表中
    space[0].cur = k;//备用链表头指针指向新的备用结点
}//Free_SL

int CreateList_SL(SLinkList &space){
    //创建静态链表，建立静态链表头结点，位置位于数组第2个位置
    //备用链表头指针指向第二备用结点
    elem = Malloc_SL(space);//取得备用链表中的第一个备用结点设为静态链表头结点
    space[elem].cur = 0;
    length = 0;//静态链表长度更新为0
}//CreateList_SL

int GetElem_SL(SLinkList space, ElemType e){
    //在静态链表space中查找第一个值为e的元素
    //若找到，则返回他在L中的位序，否则返回0
    int i = space[1].cur;//i指向静态链表头指针
    while (i && strcmp(space[i].name,e))
    {
        i = space[i].cur;//指向静态链表中的下一个结点
    }
    return i;//如果i最后为0则说明没有找到
    /*
        strcmp(str1, str2)
        str1 > str2 返回 1
        str1 == str2 返回 0
        str1 < str2 返回-1 
    */
}//GetElem_SL

int Insert_SL(SLinkList &space,int a,ElemType e){
    //insert a e代表在第a个姓氏前插入姓氏e
    int i=elem,num=0;//取得静态链表起始位置，计数器归0
    if(a>length+1)return ERROR;//不存在第a个姓氏，报错
    while(num!=a-1){    //找到第a个姓氏前面的姓氏，后插法插入
        i=space[i].cur;
        num++;
    }
    int p = Malloc_SL(space);//申请一个备用结点用于插入新的静态结点
    strcpy(space[p].name,e);//赋值给新结点p
    space[p].cur = space[i].cur;//后插法插入静态链表
    space[i].cur = p;
    length++;//链表长度加1
    return OK;
}//Insert_SL

int Delete_SL(SLinkList &space,int a){
    //删除第a个姓氏，删除成功返回1，否则返回0
    int i=elem,num=0;//取得静态链表起始位置，计数器归0
    if(a>length+1)return ERROR;//不存在第a个姓氏，报错
    while(num!=a-1){    //找到第a个姓氏前面的姓氏
        i=space[i].cur;
        num++;
    }
    int p = space[i].cur;//获取要删除结点的下标
    strcpy(space[p].name,"");//姓氏置空
    space[i].cur = space[p].cur;//
    Free_SL(space,p);
    length--;//链表长度减1
    return OK;
}

int main(){
    SLinkList space;
    ElemType str,e;
    int a;

InitSpace_SL(space);//初始化备用链表
    CreateList_SL(space);//初始化静态链表
    
    while (scanf("%s",str) != EOF)
    {
        if(!strcmp(str,"show")){//展示
            Show_SL(space);
        }
        else if(!strcmp(str,"insert")){//插入
            scanf("%d %s",&a,e);
            Insert_SL(space,a,e);
        }
        else if(!strcmp(str,"search")){//取值
            scanf("%s",e);
            int t = GetElem_SL(space,e);
            printf("%2d\n********************\n",t);
        }
        else if(!strcmp(str,"delete")){//删除
            scanf("%d",&a);
            Delete_SL(space,a);
        }
    }
    
    return 0;
}
```

—————最后是大佬的代码，比我的短，运行的也比我的快，但是我不对，大佬的对了！这是一个熟悉的场景，熟悉的味道，熟悉的配方，只是不一样的题目！~~
大佬代码没有注释，但是跟我写的感觉差不多，有看不懂的地方，可以参考上面的代码，互相观看，来解决自己遇到的问题。

```cpp
    #include <stdio.h>
    #include <string.h>
    #define MAXSIZE 11
    typedef char ElemType[8];
    typedef struct
    {
        ElemType data;
        int cur;
    } NodeType;
    NodeType space[MAXSIZE];
    typedef struct
    {
        int elem;
        int length;
        int listSize;
    } SLinkList;
    int LocateElem_SL(SLinkList& S, ElemType e)
    {
        int i;
        i = S.elem;
        while (i && strcmp(space[i].data, e))
            i = space[i].cur;
        return i;
    }
    void InitSpace_SL()
    {
        memset(space, 0 ,sizeof(space));
        for (int i = 0; i < MAXSIZE - 1; ++i)
            space[i].cur = i + 1;
        space[MAXSIZE - 1].cur = 0;
    }
    int Malloc_SL()
    {
        int i = space[0].cur;
        if (i)
            space[0].cur = space[i].cur;
        return i;
    }
    void Free_SL(int k)
    {
        space[k].cur = space[0].cur;
        space[0].cur = k;
    }
    void Insert_SL(SLinkList& S, int i, ElemType e)
    {
        int cur = S.elem;
        int j=0;
        int newNodeIndex;
        while(j<i-1)
        {
            cur = space[cur].cur;
            ++j;
        }
        newNodeIndex = Malloc_SL();
        strcpy(space[newNodeIndex].data,e);
        space[newNodeIndex].cur = 0;
        space[newNodeIndex].cur = space[cur].cur;
        space[cur].cur = newNodeIndex;
        S.length++;
    }
    void Delete_SL(SLinkList& S, int i)
    {
        int cur = S.elem;
        int j=0;
        int delCur;
        while(j<i-1)
        {
            cur = space[cur].cur;
            ++j;
        }
        delCur = space[cur].cur;
        space[cur].cur = space[delCur].cur;
        Free_SL(delCur);
        S.length--;
    }
    void CreateList_SL(SLinkList& S)
    {
        S.elem = Malloc_SL();
        space[S.elem].cur = 0;
        S.length = 0;
        S.listSize = 9;
    }
    void Show_space()
    {
        int i;
        for(i=0; i<MAXSIZE; i++)
        {
            printf("%-8s%2d\n", space[i].data, space[i].cur);
        }
    }
    int main()
    {
        SLinkList S;
        char str[10];
        int a;
        ElemType e;
        InitSpace_SL();
        CreateList_SL(S); 
        while(scanf("%s", str) != EOF)
        {
            if(strcmp(str, "insert") == 0)
            {
                scanf("%d%s", &a, e);
                Insert_SL(S, a, e);
            }
            else if(strcmp(str, "delete") == 0)
            {
                scanf("%d", &a);
                Delete_SL(S, a);
            }
            else if(strcmp(str, "search") == 0)
            {
                scanf("%s", e);
                printf("%2d\n********************\n", LocateElem_SL(S, e));
            }
            else if(strcmp(str, "show") == 0)
            {
                Show_space();
                puts("********************");
            }
        }
        return 0;
    }

```
***————其实编写文章的中途，我突然想到了一个点，就是114行我把它注释掉后就和大佬运行的代码几乎一样了，但是仍然没找到具体的错误在哪，测试用例几乎用遍，但是错误依然，要是用同学因为我这篇文章写出了这道题目，务必请私信我赐教一番，多谢大佬！！***

***————最后借用屈原[离骚](https://hanyu.baidu.com/shici/detail?from=kg1&highlight=%E8%B7%AF%E6%BC%AB%E6%BC%AB%E5%85%B6%E4%BF%AE%E8%BF%9C%E5%85%AE%EF%BC%8C&pid=9ad3463ac8944527947d959b7c8b1f8e&srcid=51369 "离骚")中的一句结尾：路漫漫其修远兮，吾将上下而求索。————***
——————————⭐⭐加油吧！！！少年！！！⭐⭐——————————

0.0分

1 人评分

本文分类：题解列表
浏览次数：363 次浏览
发布日期：2023-03-03 18:42:41
本文链接：https://blog.dotcpp.com/a/94496

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 9 条评论

LikeWater 1年前回复TA

@计科余定成 嗯，这样好处多多

计科余定成 1年前回复TA

@计科余定成 差不多，建议把常用的容器都学一学

LikeWater 1年前回复TA

@计科余定成 你是说直接用模板库里面的函数，就不用自己写链表了那样吗

计科余定成 1年前回复TA

@计科余定成 但是很方便，大大减少了代码量

LikeWater 1年前回复TA

@计科余定成 噢噢噢噢你是说用双向链表来解决这个问题就不容易出错吗

计科余定成 1年前回复TA

@计科余定成 双向链表

LikeWater 1年前回复TA

@计科余定成 就是广义表吗

计科余定成 1年前回复TA

可以去学习一下STL里的list

LikeWater 1年前回复TA

666666666666666666666666

LikeWater - 1677: 数据结构-静态链表（又是一个怎么也找不到错误的题！！！ヾ(≧へ≦)〃）

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 9 条评论

发表评论 取消回复

评论列表共有 9 条评论

发表评论取消回复