LikeWater

####——链表结构体，特殊结构体的一种，存在指向自身的结构体指针，在我们学过的数据结构中，算是最简单的一种链式结构了，题目考的就是链表的基本功，这种题目写起来可能要花些时间，但是写完了自己对链表这种结构的熟悉程度也会有大大的提高，当然了，题目易写，问题难解，写完题目之后的提交，成为了最令人头疼的事。

****——————这里我先卖个关子，给大家看看一些图片——————****
1、![时间超限的错误](/image_editor_upload/20230302/20230302095048_20216.png "时间超限的错误")
2、![1000个时间超限的同学](/image_editor_upload/20230302/20230302095127_67482.png "1000个时间超限的同学")

———————————————————————————————
**想必大家都知道什么的图片代表什么，这是我遇见过时间超限的同学最多的一道题，几乎和答案错误肩并肩，这也成为了难倒大部分同学的一道坎，明明已经到这里了，各种调试都正确，为什么偏偏时间超限啊！！我相信这是时间超限的同学看到错误之后的第一想法，因为我看到的时候也是这么想的，这简直要了老命了，但是如果你点进去详情，它也只会告诉你你的代码时间超限了，绝不会说是你不该使用cin和cout！！！**

1. 为什么不用cin和cout？？不好用吗？？
1. cin不必scanf好用？什么玩意儿？
1. sb作者

**我写到这里的时候也有这种奇怪的疑问，当然了我这个疑问是在我copy了[Manchester](https://blog.dotcpp.com/wenyajie/ "Manchester")和[浅枫](https://blog.dotcpp.com/a1105054657/ "浅枫")两位大佬的代码之后才发现的，我就很疑惑，什么都一样为什么提交就时间超限，这dotcpp是不是有问题，但是总归于和大佬的代码不一样，还是得自纠。终于！！！我在一篇网站上找到了答案！！
[c语言和c++读入区别](https://blog.csdn.net/weixin_42240667/article/details/103596532 "c语言和c++读入区别")**
读完这篇文章我终于知道我的问题在哪里了：
1、cin是流输入，不同于C语言的scanf，它的输入需要缓冲区，就像飞机需要起跑道一样，不能像scanf标准输入流那样直接输入，每次跑跑道都需要远大于直接输入的时间，累积起来时间自然就长了。
2、cout同样的，不同于printf，输出流也需要缓冲区，它不管和cin哪个用的多了都得时间超限。

**其实到这里我还没死心，因为string字符串的比较运算符太好用了，我想把string保留下来，就是用scanf来读入string，我在上面链接的文章找到的答案是重写string的大小，然后取其首地址再读入，但是我怎么写都会出现问题，于是就搁置了，如果有大佬懂得，希望可以私信我，讨论讨论。**

*比起如何用scanf读入string，更折磨我的是跟时间超限死磕的过程，其实上面的1000个时间超限是我贡献的，原本只有9百多个，我一直提交，最后给它凑了个整数哈哈哈哈哈！:bowtie:*

***以前总绝对cout比printf方便，但当要控制格式输出的时候，我才发现printf的好，以前总觉得cin比scanf方便，今天才知道cin也有它的弊端，scanf不愧经典，如果我将两者结合使用会不会更好？***
我通过实践测试了单C语言读入的速度和c和c++结合的速度，有时候灵活多变比死板更靠谱！
![C语言读入速度](/image_editor_upload/20230302/20230302101714_79879.png "C语言读入速度")

![两者结合的速度](/image_editor_upload/20230302/20230302101806_51142.png "两者结合的速度")

**最后附上各种代码，希望能够给大家带来帮助！**
***1、不会时间超限的代码***
```cpp
#include<iostream>
#include<string>
#include<string.h>
#include<iomanip>
using namespace std;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型

typedef struct LNode {
    ElemType data; //结点的数据域
    struct LNode *next; //结点的指针域
} LNode, *LinkList; //LinkList为指向结构体LNode的指针类型
/* 输入格式
输入数据只有一组，第一行有n+1个整数，
第一个整数是这行余下的整数数目n，后面是n个整数。
这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，
也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。
第二行有一个整数m，代表下面还有m行。每行有一个字符串，
字符串是“get”，“insert”，“delete”，“show”中的一种。
如果是“get”或者“delete”，则其后跟着一个整数a，代表获得或者删除第a个元素；
如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e；
“show”之后没有整数。
输出格式
如果获取成功，则输出该元素；如果删除成功则输出“delete OK”；
如果获取失败或者删除失败，则输出“get fail”以及“delete fail”。
如果插入成功则输出“insert OK”，否则输出“insert fail”。
如果是“show”则输出列表中的所有元素，
如果列表是空的，则输出“Link list is empty”。注：所有的双引号均不输出。
*/

int main(){
    int n,m;
    scanf("%d",&n);
    LinkList L;
    InitList_L(L);//创建头结点，建立空表
    CreateList_H(L,n);//前插法输入数据，倒序输入
    scanf("%d",&m);
    int a,e;
    char str[10];
    while (m--)
    {
        scanf("%s",str);
        if(!strcmp(str,"show")){
            Show_L(L);
            printf("\n");
        }
        else if(!strcmp(str,"get")){
            scanf("%d",&a);
            if(GetElem_L(L,a,e)){
                printf("%d\n",e);
            }
            else printf("get fail\n");
        }
        else if(!strcmp(str,"delete")){
            scanf("%d",&a);
            if(ListDelete_L(L,a)){
                printf("delete OK\n");
            }
            else printf("delete fail\n");
        }
        else if(!strcmp(str,"insert")){
            scanf("%d",&a);scanf("%d",&e);
            if(ListInsert_L(L,a,e)){
                printf("insert OK\n");
            }
            else printf("insert fail\n");
        }
    }
    
    return 0;
}

Status InitList_L(LinkList &L) { //算法2.6 单链表的初始化
	//构造一个空的单链表L
	L = new LNode; //生成新结点作为头结点，用头指针L指向头结点
    int length=0;//头结点不计入长度
    L->data = length;
	L->next = NULL; //头结点的指针域置空
	return OK;
}//InitList_L

void CreateList_H(LinkList &L , int n){//创建新结点，连接成新链表
    //逆位序输入n个元素的值，建立到头结点的单链表L
	LinkList p;
    int length = L->data;
    while(n--){
        p = new LNode;//用结构体指针p指向新生成结点
        cin >> p->data;
        p->next = L->next;
        L->next = p;
        length++;//同时对链表长度进行统计
    }
    L->data = length;
}//CreateList_H

void CreateList_R(LinkList &L, int n) { //算法2.12 后插法创建单链表
	//正位序输入n个元素的值，建立带表头结点的单链表L 
	LinkList p, r;//定义尾指针，方便后插法插入
    r->next = L->next;
    while (n--)
    {
        p = new LNode;
        cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;
        L->data++;
    }
} //CreateList_R

void Show_L(LinkList L){//展示链表
    LinkList p;
    p=L->next;
    if(!p) cout << "Link list is empty";
    while (p)
    {
        cout << p->data << " ";
		p=p->next;
    }
}
Status GetElem_L(LinkList L, int i, ElemType &e) { //算法2.7 单链表的取值
	//在带头结点的单链表L中查找第i个元素
	//用e返回L中第i个数据元素的值
	int j;
	LinkList p;
    p = L->next;
    j = 1; //初始化，p指向第一个结点，j为计数器
    if(i > L->data)return ERROR;//如果超出链表长度，直接返回错误
	while (j < i && p) { //顺链域向后扫描，直到p指向第i个元素或p为空
		p = p->next; //p指向下一个结点
		++j; //计数器j相应加1
	}
	if (!p || j > i)
		return ERROR; //i值不合法i＞n或i<=0
	e = p->data; //取第i个结点的数据域
	return OK;//return OK 表示查找成功
} //GetElem_L

Status ListInsert_L(LinkList &L, int i, ElemType e){//算法2.9 单链表的插入
	//在带头结点的单链表L中第i个位置插入值为e的新结点
	int j;
	LinkList p,s;
	p = L;
	j = 0;
	while (p && j < i - 1) {
		p = p->next;
		++j;
	}//查找第i-1个结点，p指向该结点
	if (!p || j > i - 1)
		return ERROR; //i＞n+1或者i＜1
	s = new LNode; //生成新结点*s 
	s->data = e; //将结点*s的数据域置为e
	s->next = p->next; //将结点*s的指针域指向结点ai
	p->next = s; //将结点*p的指针域指向结点*s
	L->data++;
	return OK;
}//ListInsert_L

Status ListDelete_L(LinkList &L, int i){//算法2.9 单链表的删除
	//在带头结点的单链表L中，删除第i个位置	
	LinkList p, q;
	int j;
	p = L;
	j = 0;
	while ((p->next) && (j < i - 1)) //查找第i-1个结点，p指向该结点
	{
		p = p->next;
		++j;
	}
	if (!(p->next) || (j > i - 1))
		return ERROR; //当i>n或i<1时，删除位置不合理 
	q = p->next; //临时保存被删结点的地址以备释放
	p->next = q->next; //改变删除结点前驱结点的指针域 
	delete q; //释放删除结点的空间 
	L->data--;
	return OK;
} //ListDelete_L
```

***2、纯c++的代码***
```cpp
#include<iostream>
#include<string>
#include<string.h>
#include<iomanip>
#include"MyLinkList.h"
using namespace std;
int main(){
    int n,m;
    cin >> n;
    // scanf("%d",&n);
    LinkList L;
    InitList_L(L);//创建头结点，建立空表
    CreateList_H(L,n);//前插法输入数据，倒序输入
    
    cin >> m;
    // scanf("%d",&m);
    string str;
    int a,e;
    while (m--)
    {
        cin >> str;
        if(str == "show"){
            Show_L(L);
            cout << endl;
        }
        else if(str == "get"){
            cin >> a;
            if(GetElem_L(L,a,e)){
                cout << e << endl;
            }
            else cout << "get fail" << endl;
        }
        else if(str == "delete"){
            cin >> a;
            if(ListDelete_L(L,a)){
                cout << "delete OK" << endl;
            }
            else cout << "delete fail" << endl;
        }
        else if(str == "insert"){
            cin >> a;cin >> e;
            if(ListInsert_L(L,a,e)){
                cout << "insert OK" << endl;
            }
            else cout << "insert fail" << endl;
        }
    }

return 0;
}
```

***3、以及我的头文件，函数实现上面包含了我就不再赘述了***
```cpp
#ifndef _MYLINKLIST_H
#define _MYLINKLIST_H
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型

typedef struct LNode {
    ElemType data; //结点的数据域
    struct LNode *next; //结点的指针域
} LNode, *LinkList; //LinkList为指向结构体LNode的指针类型

Status InitList_L(LinkList &L);
void CreateList_H(LinkList &L, int n);
void CreateList_R(LinkList &L, int n);
void Show_L(LinkList L);
Status GetElem_L(LinkList L, int i, ElemType &e);
Status ListInsert_L(LinkList &L, int i, ElemType e);
Status ListDelete_L(LinkList &L, int i);
#endif#ifndef _MYLINKLIST_H
#define _MYLINKLIST_H
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。
typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型

typedef struct LNode {
    ElemType data; //结点的数据域
    struct LNode *next; //结点的指针域
} LNode, *LinkList; //LinkList为指向结构体LNode的指针类型

Status InitList_L(LinkList &L);
void CreateList_H(LinkList &L, int n);
void CreateList_R(LinkList &L, int n);
void Show_L(LinkList L);
Status GetElem_L(LinkList L, int i, ElemType &e);
Status ListInsert_L(LinkList &L, int i, ElemType e);
Status ListDelete_L(LinkList &L, int i);
#endif
```
***—————能够提出问题就能够解决问题，大家一起努力！！—————***

0.0分

10 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

wjw

一定不能使用cin和cout吗，我也是时间超限

2024-10-31 20:07:56

hzc一hho

牛

2023-08-04 23:42:19

LikeWater

6666666666666666666666

2023-03-02 22:22:50

LikeWater

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言考试练习题_排列（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C++代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

LikeWater - 1676: 数据结构-链表的基本操作（本以为一切顺利，没想到只有我是小丑！！！）

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-进制转换（C语言代码）

最长单词（C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【亲和数】（C语言代码）

LikeWater

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

C语言考试练习题_排列 （C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C++代码）

C语言程序设计教程（第三版）课后习题6.3 （Java代码）

LikeWater - 1676: 数据结构-链表的基本操作（本以为一切顺利，没想到只有我是小丑！！！）

评论区

精彩推荐

2005年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C二级辅导-进制转换 （C语言代码）

最长单词 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【亲和数】 （C语言代码）

C语言考试练习题_排列（C++代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

　　评论区

C二级辅导-进制转换（C语言代码）

最长单词（C语言代码）

【亲和数】（C语言代码）