文档章节

单链表的基本操作(初始化,建表,遍历,增加,删除,查找,逆序)等操作

种地瓜
 种地瓜
发布于 2015/10/21 23:29
字数 907
阅读 914
收藏 5

    单链表是学习数据结构的基础,一些简单的操作还是要熟练掌握

    头文件list.h

//list.h
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include <iostream>
using namespace std;

//定义节点结构体
typedef struct LNode
{
    int data;
    struct LNode * next;
}LNode,*LinkList;

//函数声明
LinkList LinkListInit();
void showmeu();
void CreateList(LNode *);
void printList(LNode *);
void addNode(LNode *);
void deleteNode(LNode *);
void searchNode(LNode *);
void reverList(LNode *);
void select(LNode *);

    源文件

//list.cpp
#include "list.h"
//list practice

//main函数
int main()
{
    LinkList head=LinkListInit();
    select(head);

    return 0;
}

//链表初始化
LinkList LinkListInit()
{
    LinkList pHead;
    pHead=(LinkList)malloc(sizeof(LNode));

    if(pHead==NULL)
    {
        cout<<"初始化失败!";
        exit(-1);
    }
    //初始化成功
    cout<<"初始化链表成功!"<<endl;
    pHead->next=NULL;
    
    return pHead;
}

void showmeu()
{
    cout<<endl<<"***************菜单,选择操作**********************"<<endl;
    cout<<"1.新建链表"<<endl;
    cout<<"2.遍历链表"<<endl;
    cout<<"3.添加节点"<<endl;
    cout<<"4.删除节点"<<endl;
    cout<<"5.查找节点"<<endl;
    cout<<"6.逆序链表"<<endl;
    cout<<"7.退出"<<endl;
    cout<<"******************************************************"<<endl;
}

void select(LNode *head)
{
    int selection;
    while(1)
    {
//        system("cls");//清屏
        showmeu();
        cout<<endl<<"请选择你的操作:";
        cin>>selection;
        switch(selection)
        {
            case 1:
                CreateList(head);break;
            case 2:
                printList(head);break;
            case 3:
                addNode(head);break;
            case 4:
                deleteNode(head);break;
            case 5:
                searchNode(head);break;
            case 6:
                reverList(head);break;
            case 7:
                exit(-1);
                
        }

    }

}

//创建链表
void CreateList(LNode * head)
{
    int n;
    int x;
    LinkList p=head;
    cout<<"请输入节点个数:";
    cin>>n;
    if(n<=0)
        exit(-1);
    for(int i=1;i<=n;i++)
    {
        LinkList q=(LinkList )malloc(sizeof(LNode));
        
        cout<<"请输入第"<<i<<"个节点值:";
        cin>>x;
        q->data=x;
        q->next=NULL;
        //关键的两句,用尾插法
        p->next=q;
        p=q;
    }
    cout<<"创建链表成功!"<<endl;
}

//遍历链表
void printList(LNode * head)
{
    LinkList p=head->next;
    if(p==NULL)
        cout<<"该链表还没有节点元素"<<endl;
    cout<<"遍历的结果是:"<<endl;
    while(p!=NULL)
    {
        cout<<p->data<<"  ";
        p=p->next;
    }
}
int getlistlong(LNode * head)
{
    LinkList p=head->next;
    int n=0;
    if(p==NULL)
        return 0;
    while(p!=NULL)
    {
        n++;
        p=p->next;
    }
    return n;
}

//插入节点
void addNode(LNode * head)
{
    int n;
    int x;
    int length=getlistlong(head);
    if(head==NULL)
        cout<<"请先创建头节点"<<endl;
    else
    {
        cout<<"请输入要插入的位置:";
        cin>>n;
        if(n>length)
        {    cout<<"因为要插入的位置比最后的位置还要大,已经为你插入到最后的位置"<<endl;
            n=length+1;
        }

        if(n<=0)
            cout<<"请输入大于0的位置"<<endl;

        cout<<"请输入要插入的值:";
        cin>>x;
        LinkList p=(LinkList)malloc(sizeof(LNode));
        p->data=x;

        LinkList q=head;

        for(int i=1;i<n;i++)
        {
            q=q->next;
        }
        p->next=q->next;
        q->next=p;

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

//删除节点
void deleteNode(LNode * head)
{
    LinkList p;    //要删除的元素
    int n;
    if(head==NULL || head->next==NULL)
        cout<<"链表为空或长度为0,不能删除链表"<<endl;
    else
    {
        cout<<"请输入要删除的位置:";
        cin>>n;
        if(n<=0)
            cout<<"链表为空或长度为0,不能删除链表"<<endl;
        else
        {
            LinkList q=head;
            for(int i=1;i<n;i++)
            {
                q=q->next;
            }
            p=q->next;
            q->next=q->next->next;
            cout<<"删除的元素是:"<<p->data<<endl;
        }        
    }
}

//查找节点
void searchNode(LNode * head)
{
    LinkList p=head;
    int n=0;
    int x;
    cout<<"输入你要寻找的节点:";
    cin>>x;
    if(head==NULL || head->next==NULL) //若头节点为空,或后面也指向一个空的节点
        cout<<"链表为空,没有你要找的节点:"<<endl;
    else
    {
        while(p->next!=NULL)
        {
            if(p->data==x)
            {
                cout<<"找到你要找的节点的位置了,它在"<<n<<"个位置"<<endl;
                break;
            }
            else
            {
                p=p->next;
                n++;
            }
            if(p==NULL)
                cout<<"没有找到你要的这个节点!"<<endl;
        }
    }
}

//链表逆序
void reverList(LNode * head)
{
    LinkList p=NULL;
    LinkList q=NULL;
    if(head == NULL)
    {
        cout<<"链表为空,不需逆序!"<<endl;
    }
    p=head->next;
    while(p->next != NULL)
    {
        q=p->next;
        p->next=q->next;
        q->next=head->next;
        head->next=q;
    }
    cout<<"逆序成功,现在的链表的顺序是:"<<endl;
    printList(head);
    
}

运行结果:


© 著作权归作者所有

共有 人打赏支持
种地瓜
粉丝 9
博文 177
码字总数 45450
作品 0
深圳
程序员
私信 提问
数据结构与算法--链表(单向链表)

为什么需要链表 顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充时又需要进行数据的搬迁,所以使用起来并不是很灵活。 链表结构可以充分利用计算机内存空间,实现灵活的...

墨痕hz
05/28
0
0
数据结构第4-2讲双向链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢? 可以给每个元素附加一个指针域,指向下一个元素的存储位置。这种链表称为...

rainchxy
2017/11/21
0
0
JAVA容器-自问自答学HashMap

前言 这次我和大家一起学习,我们在工作中经常会使用,而且面试中也很频繁会问到,因为它里面蕴含着很多知识点,可以很好的考察个人基础。但一个这么重要的东西,我为什么没有在一开始就去学...

liangzzz
2017/10/19
0
0
数据结构 第4讲 单链表

链表是线性表的链式存储方式,逻辑上相邻的数据在计算机内的存储位置不一定相邻,那么怎么表示逻辑上的相邻关系呢?可以给每个元素附加一个指针域,指向下一个元素的存储位置。如图所示: 从...

rainchxy
2017/12/22
0
0
对线性表理解以及C语言实现链表的插入删除等操作。

我们首先用一个结构体定义链表的储存结构,代码如下。 在链表L中第i个元素之前插入一个新的元素:我们需要找到第i-1个结点,然后修改其指向后继的指针。假设新插入的元素e,新生成的结点为s...

奔跑的码农
2016/03/23
113
0

没有更多内容

加载失败,请刷新页面

加载更多

解析JQuery中each方法的使用

each() 方法规定为每个匹配元素规定运行的函数。写的十分的全面细致,具有一定的参考价值,对此有需要的朋友可以参考学习下。如有不足之处,欢迎批评指正。 概述: each() 方法规定为每个匹配...

前端攻城小牛
9分钟前
1
0
深入解析Vue开发动态刷新Echarts组件的教程

需求背景:dashboard作为目前企业中后台产品的“门面”,如何更加实时、高效、炫酷的对统计数据进行展示,是值得前端开发工程师和UI设计师共同思考的一个问题。今天就从0开始,封装一个动态渲...

peakedness丶
22分钟前
3
0
memcached

memcached 为了避免内存碎片化(传统的内存管理方式是,使用完通过malloc分配的内存后通过free来回收内存,这种方式容易产生内存碎片并降低操作系统对内存的管理效率),采用了 slab allocatio...

Cobbage
23分钟前
2
0
keepalived的介绍及配置高可用集群

12月19日任务 18.1 集群介绍 18.2 keepalived介绍 18.3/18.4/18.5 用keepalived配置高可用集群 集群介绍 根据功能划分为2类:高可用和负载均衡 高可用集群:通常为两台服务器,一台工作,另外...

robertt15
23分钟前
5
0
WiFi攻击的三种方式

导读 WiFi的安全问题已经引起了不少的使用者重视,甚至已经出现草木皆兵的现象。那么黑客到底是如何做到绕过身份验证来获取WiFi使用权的呢?主要有以下三种方式,其中最后一种方式十分简单。 ...

问题终结者
38分钟前
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部