首页 > 其他分享 >单链表 基本操作

单链表 基本操作

时间：2024-04-03 19:32:43浏览次数：15  
标签：结点 单链 LNode int next 基本操作 NULL data

目录

初始化

求表长

按序号查找结点

按值查找结点

插入结点（后插）

插入结点（前插）

删除结点（直接删除）

删除结点（间接删除）

头插法建立单链表

尾插法建立单链表

打印单链表

 总代码

测试样例 

初始化
//单链表
typedef int ElemType;
typedef struct LNode{       //这时这个LNode 不能省略，因为在结构体中有结构体指针
    ElemType data;         //数据域
    struct LNode *next;   // 指针域
}LNode,*LinkList;

//单链表初始化
bool InitList(LinkList &L)
{
    L = (LNode*)malloc(sizeof(LNode));
    L->next=NULL;
    return true;
}
求表长
//求表长
int LengthList(LinkList L)
{
    int len=0;
    LNode *p = L->next;
    while(p!=NULL)
    {
        p=p->next;
        len++;
    }
    return len;
}
按序号查找结点
//按序号查找结点
LNode *GetElem(LinkList L,int i)  //头结点代表第 0 个结点
{
    int j=0;
    LNode *p = L;
    while(p!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    return p;
}
按值查找结点
//按值查找表结点
LNode *LocateElem(LinkList L,ElemType e)
{
    LNode *p=L->next;                    //因为头结点中没有值，所以不用找，直接从L—>next 开始遍历
    while(p!=NULL && p->data != e)
    {
        p=p->next;
    }
    return p;
}
插入结点（后插）
// 链表中插入结点 ,这是后插操作
bool ListInsert1(LinkList &L,int i,ElemType e)
{
    LNode *p=L;
    int j=0;
    while(p!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)                   //判断i的合法性
    {
        return false;
    }
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
插入结点（前插）
// 链表中插入结点 ,这是前插操作
bool ListInsert2(LinkList &L,int i,ElemType e)
{
    LNode *p=L;
    int j=0;
    while(p!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)                   //判断i的合法性
    {
        return false;
    }
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    int temp = p->data;
    p->data =  s->data;
    s->data = temp;
    return true;
}
删除结点（直接删除）
//链表中删除结点
//修改前驱结点的指针域，使其指向要删除元素的后继结点，再把要删元素所占用的空间free掉
bool ListDelete1(LinkList &L,int i,ElemType e)
{
    LNode *p = L;
    int j=0;
    while(p!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p == NULL || p->next == NULL )      //p->next的意思是 最后一个位置的后面一个位置没有东西的怎么删
    {
        return false;
    }
    LNode *q = p->next;
    e=q->data;
    p->next = q->next;
    free(q);
    return true;
}
删除结点（间接删除）

要删结点和其后继结点的数据域交换，而后修改指针的值，最后free后继结点

//链表中删除结点
//可以将要删除结点的后继结点赋值给该结点，而后将后继结点free掉就可以
bool ListDelete2(LinkList &L,int i,ElemType e)
{
    LNode *p = L;
    int j=0;
    while(p!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    if(p == NULL)
    {
        return false;
    }
    LNode *q = p->next;
    e=p->data;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return true;
}
头插法建立单链表
//头插法新建单链表
LinkList List_HeadInsert(LinkList &L)
{
    LNode *s;
    int x;
    L = (LNode*) malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LNode*) malloc(sizeof (LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}
尾插法建立单链表

需要一个尾指针不断指向当前位置（即尾结点）

//尾插法新建单链表   必须增加一个尾指针，记录上一个插入节点的位置
LinkList List_TailInsert(LinkList &L)
{
    LNode *s;
    int x;
    L= (LNode*) malloc(sizeof(LNode));
    LNode *r = L;
    L->next = NULL;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LNode*) malloc(sizeof(LNode));
        s->data = x;
        r->next =s;
        r=s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}
打印单链表
//打印单链表
void print(LinkList L)
{
    LNode *s = L;
    while(s->next != NULL)
    {
        s =s->next;
        printf("%d ",s->data);
    }
    printf("\n");
}
 总代码
#include <stdio.h>
#include <stdlib.h>

//单链表
typedef int ElemType;
typedef struct LNode{       //这时这个LNode 不能省略，因为在结构体中有结构体指针
    ElemType data;         //数据域
    struct LNode *next;   // 指针域
}LNode,*LinkList;

//单链表初始化
bool InitList(LinkList &L)
{
    L = (LNode*)malloc(sizeof(LNode));
    L->next=NULL;
    return true;
}

//求表长
int LengthList(LinkList L)
{
    int len=0;
    LNode *p = L->next;
    while(p!=NULL)
    {
        p=p->next;
        len++;
    }
    return len;
}

//按序号查找结点
LNode *GetElem(LinkList L,int i)  //头结点代表第 0 个结点
{
    int j=0;
    LNode *p = L;
    while(p!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    return p;
}

//按值查找表结点
LNode *LocateElem(LinkList L,ElemType e)
{
    LNode *p=L->next;                    //因为tnd 头结点中没有值，所以不用找，直接从L—>next 开始遍历
    while(p!=NULL && p->data != e)
    {
        p=p->next;
    }
    return p;
}

// 链表中插入结点 ,这是后插操作
bool ListInsert1(LinkList &L,int i,ElemType e)
{
    LNode *p=L;
    int j=0;
    while(p!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)                   //判断i的合法性
    {
        return false;
    }
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}
// 链表中插入结点 ,这是前插操作
bool ListInsert2(LinkList &L,int i,ElemType e)
{
    LNode *p=L;
    int j=0;
    while(p!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    if(p==NULL)                   //判断i的合法性
    {
        return false;
    }
    LNode *s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    int temp = p->data;
    p->data =  s->data;
    s->data = temp;
    return true;
}

//链表中删除结点
//修改前驱结点的指针域，使其指向要删除元素的后继结点，再把要删元素所占用的空间free掉
bool ListDelete1(LinkList &L,int i,ElemType e)
{
    LNode *p = L;
    int j=0;
    while(p!=NULL && j<i-1)
    {
        p=p->next;
        j++;
    }
    if(p == NULL || p->next == NULL )      //p->next的意思是 最后一个位置的后面一个位置没有东西的怎么删
    {
        return false;
    }
    LNode *q = p->next;
    e=q->data;
    p->next = q->next;
    free(q);
    return true;
}
//链表中删除结点
//可以将要删除结点的后继结点赋值给该结点，而后将后继结点free掉就可以
bool ListDelete2(LinkList &L,int i,ElemType e)
{
    LNode *p = L;
    int j=0;
    while(p!=NULL && j<i)
    {
        p=p->next;
        j++;
    }
    if(p == NULL)
    {
        return false;
    }
    LNode *q = p->next;
    e=p->data;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return true;
}

//头插法新建单链表
LinkList List_HeadInsert(LinkList &L)
{
    LNode *s;
    int x;
    L = (LNode*) malloc(sizeof(LNode));
    L->next = NULL;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LNode*) malloc(sizeof (LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d",&x);
    }
    return L;
}

//尾插法新建单链表   必须增加一个尾指针，记录上一个插入节点的位置
LinkList List_TailInsert(LinkList &L)
{
    LNode *s;
    int x;
    L= (LNode*) malloc(sizeof(LNode));
    LNode *r = L;
    L->next = NULL;
    scanf("%d",&x);
    while(x!=9999)
    {
        s=(LNode*) malloc(sizeof(LNode));
        s->data = x;
        r->next =s;
        r=s;
        scanf("%d",&x);
    }
    r->next = NULL;
    return L;
}

//打印单链表
void print(LinkList L)
{
    LNode *s = L;
    while(s->next != NULL)
    {
        s =s->next;
        printf("%d ",s->data);
    }
    printf("\n");
}
int main() {
    LinkList L;
    List_TailInsert(L);
    print(L);
    ListInsert1(L,3,8);
    print(L);
    return 0;
}

//7 8 2 5 6 9999
测试样例 

9999 表示结束

注：本文仅个人笔记，欢迎讨论交流

标签：结点,单链,LNode,int,next,基本操作,NULL,data
From： https://blog.csdn.net/m0_73959411/article/details/137258206

相关文章

  • 03 MySQL数据库的基本操作-DDL
    DDL(DataDefinitionLanguage)，数据定义语言，该语言部分包括以下内容对数据库的常用操作对表结构的常用操作修改表结构可以在命令行里面进行如下的操作；也可以在Navicat图形化工具中操作创建数据库createdatabase数据库名[库选项]例如：createdatabase数据库......
  • 单链表-案例-new
    <!DOCTYPEhtml><htmllang="en"><head>  <metacharset="UTF-8">  <metahttp-equiv="X-UA-Compatible"content="IE=edge">  <metaname="viewport"content="width=d......
  • SWUST OJ 952 单链表插入
    一、题目题目描述建立长度为n的单链表，在第i个结点之前插入数据元素data。输入第一行为自然数n，表示链式线性表的长度；第二行为n个自然数表示链式线性表各元素值；第三行为指定插入的位置i；第四行为待插入数据元素data。输出指定插入位置合法时候，输出插入元素后的链式线性......
  • 非关系型数据库——Redis基本操作
    目录一、Redis数据库常用命令1.Set——存放数据 2.Get——获取数据3.Keys——获取符合条件的键值4.Exists——判断键值是否存在5.Del——删除指定键值6.Type——获取键值对应的类型7.Rename——对已有键值重命名（覆盖）8.Renamenx——对已有键值重命名（不覆盖）9.Dbsize—......
  • （自学#Python）Day08-字典的定义及基本操作
    （自学Python）Day08-字典的定义及基本操作一、字典的定义及创建"""字典dict定义：由一系列键值对组成的可变散列容器。操作：创建添加定位删除遍历"""#1.创建#列表善于存储单一......
  • 【数据结构】线性表-单链表
    编程语言：C++前言：节点：节点是链表的一个基本单元，包含两部分——数据域和指针域，数据域用于存储数据，指针域存储下一个节点的地址，形成链结。什么是单链表：n个节点链结成一个链表，即为线性表（a1,a2,a3……）的链式存储结构，每个节点只包含一个指针域的链表叫做单链表。链表组成：头节点、......
  • 6-92 链表基本操作（Python语言描述）
    本题要求在给出的链节点类、和单链表类部分代码的情况下，编写好基本操作的各种python3代码实现，最后调用测试代码检验。函数接口定义：已实现的链节点类、和单链表类部分代码。如下：classSingleNode(object):"""单链表的结点"""def__init__(self,item):#_i......
  • 【数据结构】用C语言实现单链表及其常见操作
    【数据结构】用C语言实现单链表及其常见操作链表是一种常用的基础数据结构，可以快速插入和删除数据，但是不能随机访问。那么它在内存中是怎么存储的呢？它和数组不同，数组在内存中是连续存储的，而链表不一定是连续的，它们之间是通过指针来连接的。指针是C语言中最重要的特性之一。那......
  • FLASK学习记录-sqlite3基本操作
    sqltie3是内置模块，数据库操作，以及表的增删改查参考https://www.runoob.com/sqlite/sqlite-python.html实例创建数据库$sqlite3test.dbSQLiteversion3.34.12021-01-2014:10:07Enter".help"forusagehints.sqlite>.databasesmain:/usr/dog/flask_web/flask-test2......
  • 图像基本操作
    图像基本操作学习图像处理的基本操作，例如缩放、平移、旋转等基本转换。知识点图像的缩放图像的平移图像的旋转图像的翻转基本的图像变换方法图像的变换是运用某些方法将图像从一个图像空间转换到另一个图像空间，同时改变图像中的像素值。图像的变换在视觉领域是比较常见......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99