首页 > 编程语言 >c++单链表(带头结点)

c++单链表(带头结点)

时间:2024-10-09 22:48:42浏览次数:10  
标签:index 结点 单链 return cout int c++ next Linklist

#include<iostream>

using namespace std;

//定义

typedef struct _LinkNode

{

    int data;//结点的数据域

    struct _LinkNode*next;//结点的指针域

}LinkNode,Linklist;

//初始化

bool InitList(Linklist*&L)

{

    L=new LinkNode;

    if(!L)return false;

    L->next=NULL;

    return true;

}

//头插法

bool ListInsert_front(Linklist* &L,LinkNode *node)

{

    if(!L||!node)return false;

    node->next=L->next;

    L->next=node;

    return true;

}

//尾插法

bool ListInsert_back(Linklist*&L,LinkNode*node)

{

LinkNode*last=NULL;

if(!L||!node)return false;

last=L;

while(last->next)

last=last->next;

node->next=NULL;

last->next=node;

return true;

}

//任意位置插入 O(n)

bool ListInsert(Linklist*&L,int i,int e)

{

if(!L)return false;

int j=0;

Linklist*p,*s;

p=L;

while(p&&j<i-1)

{

    p=p->next;

    j++;

}

if(!p||j>i-1)

return false;

s=new LinkNode;

s->data=e;

s->next=p->next;

p->next=s;

return true;

}

//单链表按位置取值

bool Link_GetElem(Linklist *&L, int i, int& e) {

    //在带头节点的单链表L中查找第i个元素

    //用e记录L中第i个元素的值

    int index;

    Linklist* p;

    if (!L || !L->next) return false;

    p = L->next;

    index = 1;

    while (p && index < i) {//链表向后扫描,直到p指向第i个元素或者p为空

        p = p->next;

        index++;

    }

    if (!p || index > i) return false;//i值不合法,i>n或i<=0;

    e = p->data;

    return true;

}

//按值取位

bool Linklist_FindElement(Linklist*L,int e,int &index)

{

    Linklist*p;

    p=L->next;

    index=1;

    if(!L||!L->next)

    {

        index=-1;

        return false;

    }

    while(p&&p->data!=e)

    {

        p=p->next;

        index++;

    }

    if(!p)

    {

        index=-1;

        return false;

    }

    return true;

}

//删除结点O(n)

bool LinklistDelete(Linklist*L,int i)

{

    Linklist*p,*q;

    p=L;

    int index=0;

    if(!L||!L->next)return false;

    while((p->next)&&(index<i-1))

    {

        index++;

        p=p->next;

    }

    if(!p->next||index>i-1)

    return false;

    q=p->next;

    p->next=q->next;

    delete q;

    return false;

}

//销毁链表

void LinklistDestroy(Linklist*&L)

{

    Linklist*p=L;

    while(p)

    {

        p=L;

        delete p;

        L=L->next;

    }

}

//销毁链表

void LinklistDestroy(Linklist*&L)

{

    Linklist*p=L;

    while(p)

    {

        p=L;

        delete p;

        L=L->next;

    }

}

//键盘输入

bool scanfList(Linklist*&L){

    int n;

    int i = 1;

    cin>>n;

    while (n)

    {

        int e;

        cin>>e;

        if (!ListInsert(L, i, e)) return false;

        n--;

    }

    return true;

    }

int main(){

int n;

    Linklist* L=NULL;

    Linklist* s = NULL;


 

    //1.初始化一个空的链表

    InitList(L);


 

    //2.使用前插法插入数据

    cout << "前插法创建单链表" << endl;

    cout << "请输入插入的个数n:";

    cin >> n;

    while (n > 0) {

        s = new LinkNode;//生成新结点s

        cin >> s->data;

        ListInsert_front(L, s);

        n--;

    }


 

    //3.使用尾插法插入数据

    cout << "尾插法创建单链表" << endl;

    cout << "请输入插入的个数n:";

    cin >> n;

    while (n > 0) {

        s = new LinkNode;//生成新结点s

        cin >> s->data;

        ListInsert_back(L, s);

        n--;

    }

   

    //4.单链表的输出

    LinkPrint(L);


 

    //5.任意位置插入元素

    for (int j = 0; j < 3; j++) {

        int i, x;

        cout << "请输入插入元素的位置及值:";

        cin >> i >> x;

        if (ListInsert(L, i, x)) {

            cout << "插入成功" << endl;

        }

        else {

            cout << "插入失败" << endl;

        }

        LinkPrint(L);

    }


 

    //6.单链表取值

    int element;  

    cout << "请输入你要获取值的位置" ;

    cin >> n;

    if (Link_GetElem(L, n, element)) {

        cout << "第" << n << "元素的值为:" << element << endl;

    }

    else {

        cout << "第" <<n<< "个元素的值获取失败!" << endl;

    }


 

    //7.单链表按值查找

    int index = 0;

    cout << "输入你要查询值的位置:";

    cin >> n;

    if (Linklist_FindElement(L, n, index)){

        cout<<"你查询值为"<<n<<"的位置为"<<index<<endl;

    }

    else {

        cout << "你查询值为" << n << "的位置为" << index << endl;

    }


 

    //8.单链表的删除元素

    cout << "请输入你要删除第几个元素:";

    cin >> n;

    if (LinklistDelete(L, n)) {

        cout << "删除第" << n << "元素成功!" << endl;

        LinkPrint(L);

    }

    else {

        cout << "删除第" << n << "元素失败!" << endl;

    }


 

    //9.销毁单链表

    LinklistDestroy(L);


 

    return 0;

}

标签:index,结点,单链,return,cout,int,c++,next,Linklist
From: https://blog.csdn.net/2301_79727388/article/details/142579878

相关文章

  • 【题目解析】蓝桥杯23国赛C++中高级组 - 斗鱼养殖场
    【题目解析】蓝桥杯23国赛C++中高级组-斗鱼养殖场题目链接跳转:点击跳转前置知识:了解过基本的动态规划。熟练掌握二进制的位运算。题解思路这是一道典型的状压动态规划问题。设\(dp_{i,j}\)表示遍历到第\(i\)行的时候,当前行以\(j_{(base2)}\)的形式排列乌龟可以构......
  • codeforces round 974(div.3)E(优先队列实现dijstra算法,devc++的优先队列用greater报
    解题历程:看到两边同时移动,计算最终的相遇时间,我就想到两边同时计算各点到起点的最短距离,就是使用dijstra算法,最后所有节点取两次计算的最大值,再对所有节点取最小值,就是最终答案了,可是这个思路没有考虑有马的情况,思考一番后发现可以多列一个数组记录有马的情况下的行走最短路,然后......
  • C++类
    C++类类//public成员提供类的接口,暴漏给外界,供外界使用//private:提供各种实现类功能的细节方法,但不暴漏给使用者,外界无法使用//注意:struct是成员默认为public的class、class成员默认是privateclassstudent{public:intnumber;charname[100];};c......
  • 实验一 现代C++基础编程
    1.实验任务1task1.cpp1//现代C++标准库、算法库体验2//本例用到以下内容:3//1.字符串string,动态数组容器类vector、迭代器4//3.函数模板、const引用作为形参56#include<iostream>7#include<string>8#include<vector>9#include<algorithm>......
  • 实验1 现代C++编程初体验
    实验任务1:task1.cpp:1//现代C++标准库、算法库体验2//本例用到以下内容:3//1.字符串string,动态数组容器类vector、迭代器4//2.算法库:反转元素次序、旋转元素5//3.函数模板、const引用作为形参67#include<iostream>8#include<string>......
  • 实验1 现代C++编程初体验
    任务1 task1.cpp1//现代C++标准库、算法库体验2//本例用到以下内容:3//1.字符串string,动态数组容器类vector、迭代器4//2.算法库:反转元素次序、旋转元素5//3.函数模板、const引用作为形参67#include<iostream>8#include<string>......
  • 实验1 现代C++基础编程
    任务1:源代码task1.cpp1#include<iostream>2#include<string>3#include<vector>4#include<algorithm>56usingnamespacestd;78//声明9//模板函数声明10template<typenameT>11voidoutput(constT&c);1213......
  • ROS通信方式之Topic话题与Message消息的关系与C++实现
    ros由于其分布式模块化的设计理念,会将一个完整任务分解成多个节点去实现,这些节点之间的协作通过topic话题和message消息.相关概念有节点(Nodes):节点是一个可执行文件,它可以通过ROS来与其他节点进行通信。消息(Messages):订阅或发布话题时所使用的ROS数据类型。话题(Topics):节点可以将......
  • 【C++】string (STL)
    string介绍字符串是表示字符序列的类标准的字符串类提供了对此类对象的支持,其接口类似于标准字符容器的接口,但添加了专门用于操作单字节字符字符串的设计特性。string类是使用char(即作为它的字符类型,使用它的默认char_traits和分配器类型(关于模板的更多信息,请参阅basic_s......
  • 【C++】类和对象(3)(默认成员函数--拷贝构造&赋值重载)
    引言前文介绍了C++中默认成员函数中的构造函数和析构函数,相信已经对它们的功能与用法有了基本认识,本文接着介绍也很常见的拷贝构造函数和赋值重载函数,便于对C++进一步的学习。拷贝构造函数补充知识:深浅拷贝深拷贝和浅拷贝是C++中对象拷贝的两种不同方式。浅拷贝是指将......