链表的有序构建和查找

叶茂林

发布于 2023-07-30 13:30:33

1710

发布于 2023-07-30 13:30:33

文章被收录于专栏：叶子的开发者社区

题目描述

单链表结点的存储结构包含两部分：数据、下一结点指针（默认为空）。

单链表包含头结点，存储实际数据的结点位置从1开始。

现输入一批无序的整数队列，编写程序完成以下要求

1）构建单链表并且把数据按递增顺序插入到链表中，并且统计非空指针发生变化的次数。

例如在初始只包含头结点的单链表中，依次插入3和2

当把3插入时，是头结点的next指针发生变化，初始头结点的next指针是空的，现在指向3的结点，所以不计入指针变化次数。

当把2插入时，它是插入到头结点和3结点之间，这时候头结点的next指针从指向3变成指向2，因此这次计入指针变化次数。

总之，如果是把一个空的next指针指向新的结点，则不计入变化次数；如果是把一个非空next指针修改指向新结点则计入变化次数。

2）实现对单链表的元素查找。输入一个链表位置，返回该位置对应的数据。如果位置非法则输出提示信息，看样例。

要求：必须使用单链表结构实现上述要求，并且不能用第三方算法库或容器类对象

输入

第一行：第一个数字n表示样本数目，其后跟n个样本。

第二行：查找测试次数m 后跟m个待查找的位置。

输出

第一行输出构建链表过程中，非空指针变化的总次数，格式看样本

第二行输出单链表创建后，从头到尾依次输出链表中元素数据

第三行到第n+1行，对每个查找位置，若结点存在，输出结点数据；否则输出error

输入样例1

6 1 8 5 2 4 3 4 0 2 10 6

输出样例1

非空指针变化4次 1 2 3 4 5 8 error 2 error 8

思路分析

就是链表题，建立单向链表，链表元素的插入和查找。

建立起带头节点的链表，完了之后，记录一下空指针变换的次数即可。

AC代码

#include <iostream>
using namespace std;
struct Node{
    int data;
    Node*next=NULL;
};
class List{
    Node*head=new Node();
    int size=0,count=0;
public:
    void insert(int&data){
        Node*new_one=new Node();
        new_one->data=data;
        Node*h=head;
        while(h->next&&h->next->data<data){
            h=h->next;
        }
        new_one->next=h->next;
        if(h->next)
            count++;
        h->next=new_one;
        size++;
    }
    bool find(int index,int&data){
        if(size<index||index<=0)
            return false;
        Node*h=head;
        while(index&&h->next){
            h=h->next;
            index--;
        }
        data=h->data;
        return true;
    }
    void show(){
        cout<<"非空指针变化"<<count<<"次"<<endl;
        Node*h=head;
        while(h->next->next){
            h=h->next;
            cout<<h->data<<' ';
        }
        cout<<h->next->data<<endl;
    }
};
int main() {
    int t,temp,data;
    List list;
    cin>>t;
    while(t--){
        cin>>temp;
        list.insert(temp);
    }
    list.show();
    cin>>t;
    while(t--){
        cin>>temp;
        if(list.find(temp,data))
            cout<<data<<endl;
        else
            cout<<"error"<<endl;
    }
    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-12-05，如有侵权请联系 cloudcommunity@tencent.com 删除

存储