线性表——链式存储
  FVOsfHRhTx5x 2023年11月02日 31 0

单链表（有头结点）

#include<stdio.h>
#include<stdlib.h>
//定义
typedef struct LNode{
    int data;        //数据域 
    struct LNode *next;        //指针域指向下一个结点，所以是 struct LNode类型 
}LNode,*LinkList;        //*LinkList用于表示这是一个指向 struct LNode类型的指针 

//初始化（有头结点），只分配一个头结点 
bool InitList(LinkList &L){            //LNode主要强调这是一个结点，而LinkList主要强调这是一个单链表，这里是对单链表进行初始化，所以参数最好使用LinkList 
    L=(LNode *)malloc(sizeof(LNode));        //分配一个头结点的内存 
    if(L==NULL)        //内存不足，分配失败 
        return false;
    L->next=NULL;        //头结点后面暂时没有结点 
    return true; 
}

//单链表的建立——尾插法
LinkList List_TailInsert(LinkList &L){
    //第一步：初始化一个单链表
    L=(LinkList)malloc(sizeof(LNode));    //建立头结点,注意这里强调是单链表，所以是LinkList类型 
    
    LNode *s,*r=L;        //s结点用于存储新元素，r结点为尾结点，永远指向最后一个结点
    int x;        //新元素
    scanf("%d",&x);        //输入新元素的值
    if(x!=999){            //当输入999时结束新元素插入 
        s=(LNode *)malloc(sizeof(LNode));        //为新节点分配内存
        if(s=NULL)        //内存分配失败 
            return NULL;
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);        //输入新元素的值
    } 
    r->next=NULL;        //注意不能忘记 
    return L;
     
}
 
//单链表的建立——头插法，与尾插法同理，只是不需要尾指针，因为头结点代替了他的作用
LinkList List_HeadInsert(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    
    LNode *s;
    int x;
    scanf("%d",&x);
    
    if(x!=999){
        s=(LNode *)malloc(sizeof(LNode));
        if(s=NULL)
            return NULL;
        
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
} 

//指定结点后插操作,在p结点后插入e 
bool InsertNextNode(LNode *p,int e) {
    if(p==NULL)
        return false;
    
    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 
    if(s==NULL)
        return false;        //内存分配失败
    
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

//按位查找,查找第i个元素 
LNode * GetElem(LinkList L,int i){
    if(i<0)
        return NULL;
    LNode *p;        //p指针用于指向当前扫描到的结点
    int j=0;         //j表示当前扫描到了第几个结点,开始是头结点——第0个结点
    p=L;            //p开始指向头结点 
    
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    } 
    return p;
} 

//按值查找
LNode * LocateElem(LinkList L,int e){
    LNode *p=L->next;    //p指向第一个结点
    while(p!=NULL&&p->data!=e){
        p=p->next;
    } 
    
    return p;
    
} 

//插入,在位置i插入结点e ，采用封装思想 
bool ListInsert(LinkList &L,int i,int e){
    if(i<1)
        return false; 
        
//    LNode *p;        //p指针用于指向当前扫描到的结点
//    int j=0;        //j表示当前扫描到了第几个结点
//    p=L;        //p指针最初指向头结点 
//    if(p!=NULL&&j<i-1){        //找到并用p指向第i-1个结点 
//        p=p->next;
//        j++ ; 
//    } 
    LNode *p=GetElem(L,i-1);         //找到第i-1个结点
    
//    if(p==NULL)        //防止i>(链表长度+1) 
//        return false;
//        
//    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配一个结点的内存
//    s->data=e;
//    s->next=p->next;
//    p->next=s;
//    return true; 
    return InsertNextNode(p,e);            //再第i-1个结点后面插入e 
} 

//指定结点前插操作,在p结点前插入e 
bool InsertPriorNode(LNode *p,int e) {
    if(p==NULL)
        return false;
    
    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 
    if(s==NULL)
        return false;        //内存分配失败
    /*
    因为单链表是单向的，只有next指针，所以在进行前插操作时，先把e插入到p的后面，然后再交换二者的数据域 
    */
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=e;
    return true;
}

//按位删除，删除表L中第i个位置的元素，并用e返回删除元素的值 。核心：找到第i-1个元素 
bool ListDelete(LinkList &L,int i,int e){
    if(i<1)
        return false;
    LNode *p;    //指向当前扫描到的结点
    int j=0;        //当前扫描到第几个结点,头结点是第0个结点 
    p=L;        //p开始指向头结点（注意：头结点不存储数据）
         
    while(p!=NULL&&j<i-1){        //找第i-1个元素 
        p=p->next;
        j++;
    } 
    
    if(p==NULL)
        return false;
    if(p->next==NULL)        //说明p是最后一个结点 
        return false;
    
    LNode *q=p->next;        //令q指向被删除的结点 
    e=q->data;                //用e返回删除元素的值
    p->next=q->next; 
    free(q);
    
    return true;
} 

//删除指定结点p。核心：将p后面结点的数据域复制到p中，再将后面的结点删除 
bool DeleteNode(LNode *p){
    if(p=NULL)
        return false;
    LNode *q=p->next;
    p->data=p->next->data;
    p->next=q->next;
    free(q);
    
    return true;
} 
int main(){
    
}

单链表（无头结点）

#include<stdio.h>
#include<stdlib.h>
//定义
typedef struct LNode{
    int data;        //数据域 
    struct LNode *next;        //指针域指向下一个结点，所以是 struct LNode类型 
}LNode,*LinkList;        //*LinkList用于表示这是一个指向 struct LNode类型的指针 

//初始化 （无头结点） 
bool InitList(LinkList &L){
    L=NULL;        //空表，暂时没有任何结点 
    return true; 
} 

//按位查找
LNode * GetElem(LinkList L,int i){
    if(i<0)
        return NULL;
    LNode *p;
    int j=1;    //注意没有头结点所以初始值为1 
    p=L;
    
    while(p!=NULL&&j<i){
        p=p->next;
        j++; 
    } 
    return p;
} 

//按值查找
LNode * LocateElem(LinkList L,int e){
    LNode *p=L;    //p开始指向第一个结点 
    while(p!=NULL&&p->data!=e){
        p=p->next;
    }
    return p;
} 

//指定结点后插操作,在p结点后插入e 
bool InsertNextNode(LNode *p,int e) {
    if(p==NULL)
        return false;
    
    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 
    if(s==NULL)
        return false;        //内存分配失败
    
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

//插入，在位置i插入结点e 
bool ListInsert(LinkList &L,int i,int e){
    if(i<1)
        return false;
    if(i==1){    //使插入的结点成为头结点 
        LNode *s=(LNode *)malloc(sizeof(LNode));    //申请内存 
        s->data=e;
        s->next=L;
        L=s; 
        return true;
    }
    
//    LNode *p;
//    int j=1; 
//    p=L;        //p指向第一个结点，注意不是头结点 
//    
//    while(p!=NULL&&j<i-1){
//        p=p->next;
//        j++;
//    }
    LNode *p=GetElem(L,i-1);
    
//    if(p=NULL)
//        return false;
//         
//    LNode *s=(LNode *)malloc(sizeof(LNode));    //申请内存 
//    s->data=e;
//    s->next=p->next;
//    p->next=s;
//    return true;
    return InsertNextNode(L,e);
} 

//指定结点前插操作,在p结点前插入e 
bool InsertPriorNode(LNode *p,int e) {
    if(p==NULL)
        return false;
    
    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 
    if(s==NULL)
        return false;        //内存分配失败
    /*
    因为单链表是单向的，只有next指针，所以在进行前插操作时，先把e插入到p的后面，然后再交换二者的数据域 
    */
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=e;
    return true;
}



//删除指定结点p。核心：将p后面结点的数据域复制到p中，再将后面的结点删除 
bool DeleteNode(LNode *p){
    if(p=NULL)
        return false;
    LNode *q=p->next;
    p->data=p->next->data;
    p->next=q->next;
    free(q);
    
    return true;
} 
int main(){
    
}

双链表

#include<stdio.h>
#include<stdlib.h>
//只有涉及到参数中有结点就需要判断结点是否为空 
//定义
typedef struct DNode{
    int data;
    struct DNode *prior,*next;
}DNode,*DLinklist;
 
//初始化
bool InitDLinkList(DLinklist &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)
        return false;
    L->next=NULL;
    L->prior=NULL;
    return true;
}
//插入
bool InsertNextDNode(DNode *p,DNode *e){
    if(p==NULL||e==NULL)
        return false;
        
    e->next=p->next;
    if(p->next!=NULL)
        p->next->prior=e;
    e->prior=p;
    p->next=e;
    return true;
        
}
//删除,删除p的后继结点
bool DeleteNextDNode(DNode *p){
    if(p==NULL)        
        return false;
    DNode *q=p->next;
    if(q==NULL)
        return false;
    p->next=q->next;
    if(q->next!=NULL)
        q->next->prior=p;
    free(q);
    return true;
        
} 

//遍历 

int main(){
    
}

循环单链表

#include<stdio.h>
#include<stdlib.h>
//定义
typedef struct LNode{
    int data;        //数据域 
    struct LNode *next;        //指针域指向下一个结点，所以是 struct LNode类型 
}LNode,*LinkList;        //*LinkList用于表示这是一个指向 struct LNode类型的指针 

//初始化（有头结点），只分配一个头结点 
bool InitList(LinkList &L){            //LNode主要强调这是一个结点，而LinkList主要强调这是一个单链表，这里是对单链表进行初始化，所以参数最好使用LinkList 
    L=(LNode *)malloc(sizeof(LNode));        //分配一个头结点的内存 
    if(L==NULL)        //内存不足，分配失败 
        return false;
    L->next=L;        //头结点后面暂时没有结点 
    return true; 
}

//单链表的建立——尾插法
LinkList List_TailInsert(LinkList &L){
    //第一步：初始化一个单链表
    L=(LinkList)malloc(sizeof(LNode));    //建立头结点,注意这里强调是单链表，所以是LinkList类型 
    
    LNode *s,*r=L;        //s结点用于存储新元素，r结点为尾结点，永远指向最后一个结点
    int x;        //新元素
    scanf("%d",&x);        //输入新元素的值
    if(x!=999){            //当输入999时结束新元素插入 
        s=(LNode *)malloc(sizeof(LNode));        //为新节点分配内存
        if(s=NULL)        //内存分配失败 
            return NULL;
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);        //输入新元素的值
    } 
    r->next=NULL;        //注意不能忘记 
    return L;
     
}
 
//单链表的建立——头插法，与尾插法同理，只是不需要尾指针，因为头结点代替了他的作用
LinkList List_HeadInsert(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));
    L->next=L;
    
    LNode *s;
    int x;
    scanf("%d",&x);
    
    if(x!=999){
        s=(LNode *)malloc(sizeof(LNode));
        if(s=NULL)
            return NULL;
        
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
} 

//指定结点后插操作,在p结点后插入e 
bool InsertNextNode(LNode *p,int e) {
    if(p==NULL)
        return false;
    
    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 
    if(s==NULL)
        return false;        //内存分配失败
    
    s->data=e;
    s->next=p->next;
    p->next=s;
    return true;
}

//按位查找,查找第i个元素 
LNode * GetElem(LinkList L,int i){
    if(i<0)
        return NULL;
    LNode *p;        //p指针用于指向当前扫描到的结点
    int j=0;         //j表示当前扫描到了第几个结点,开始是头结点——第0个结点
    p=L;            //p开始指向头结点 
    
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    } 
    return p;
} 

//按值查找
LNode * LocateElem(LinkList L,int e){
    LNode *p=L->next;    //p指向第一个结点
    while(p!=NULL&&p->data!=e){
        p=p->next;
    } 
    
    return p;
    
} 

//插入,在位置i插入结点e ，采用封装思想 
bool ListInsert(LinkList &L,int i,int e){
    if(i<1)
        return false; 
        
//    LNode *p;        //p指针用于指向当前扫描到的结点
//    int j=0;        //j表示当前扫描到了第几个结点
//    p=L;        //p指针最初指向头结点 
//    if(p!=NULL&&j<i-1){        //找到并用p指向第i-1个结点 
//        p=p->next;
//        j++ ; 
//    } 
    LNode *p=GetElem(L,i-1);         //找到第i-1个结点
    
//    if(p==NULL)        //防止i>(链表长度+1) 
//        return false;
//        
//    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配一个结点的内存
//    s->data=e;
//    s->next=p->next;
//    p->next=s;
//    return true; 
    return InsertNextNode(p,e);            //再第i-1个结点后面插入e 
} 

//指定结点前插操作,在p结点前插入e 
bool InsertPriorNode(LNode *p,int e) {
    if(p==NULL)
        return false;
    
    LNode *s=(LNode *)malloc(sizeof(LNode));    //分配内存 
    if(s==NULL)
        return false;        //内存分配失败
    /*
    因为单链表是单向的，只有next指针，所以在进行前插操作时，先把e插入到p的后面，然后再交换二者的数据域 
    */
    s->next=p->next;
    p->next=s;
    s->data=p->data;
    p->data=e;
    return true;
}

//按位删除，删除表L中第i个位置的元素，并用e返回删除元素的值 。核心：找到第i-1个元素 
bool ListDelete(LinkList &L,int i,int e){
    if(i<1)
        return false;
    LNode *p;    //指向当前扫描到的结点
    int j=0;        //当前扫描到第几个结点,头结点是第0个结点 
    p=L;        //p开始指向头结点（注意：头结点不存储数据）
         
    while(p!=NULL&&j<i-1){        //找第i-1个元素 
        p=p->next;
        j++;
    } 
    
    if(p==NULL)
        return false;
    if(p->next==L)        //说明p是最后一个结点 
        return false;
    
    LNode *q=p->next;        //令q指向被删除的结点 
    e=q->data;                //用e返回删除元素的值
    p->next=q->next; 
    free(q);
    
    return true;
} 

//删除指定结点p。核心：将p后面结点的数据域复制到p中，再将后面的结点删除 
bool DeleteNode(LNode *p){
    if(p=NULL)
        return false;
    LNode *q=p->next;
    p->data=p->next->data;
    p->next=q->next;
    free(q);
    
    return true;
} 
int main(){
    
}

循环双链表

#include<stdio.h>
#include<stdlib.h>
//只有涉及到参数中有结点就需要判断结点是否为空 
//定义
typedef struct DNode{
    int data;
    struct DNode *prior,*next;
}DNode,*DLinklist;
 
//初始化
bool InitDLinkList(DLinklist &L){
    L=(DNode *)malloc(sizeof(DNode));
    if(L==NULL)        //分配内存失败 
        return false;
    L->next=L;
    L->prior=L;
    return true;
}
//插入
bool InsertNextDNode(DNode *p,DNode *e){
    if(p==NULL||e==NULL)
        return false;
        
    e->next=p->next;
    p->next->prior=e;
    e->prior=p;
    p->next=e;
    return true;
        
}
//删除,删除p的后继结点
bool DeleteNextDNode(DLinklist &L,DNode *p){
    if(p==NULL)        
        return false;
    DNode *q=p->next;
    if(q==L)
        return false;
    p->next=q->next;
    q->next->prior=p;
    free(q);
    return true;
        
} 

//遍历 

int main(){
    
}

 



【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载，内容版权归原作者所有。本网站的目的在于传递更多信息，不拥有版权，亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@moduyun.com
  1. 分享：
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  xaeiTka4h8LY   2024年05月17日   31   0   0 算法数据结构leetcode
  SJ5vu6Cv0eSe   2023年12月08日   22   0   0 二叉搜索树子树二叉搜索树结点子树结点
  rNKBBI46q2Gq   2023年12月06日   39   0   0 代码示例数据结构代码示例redisredis数据结构
  xaeiTka4h8LY   2024年04月26日   43   0   0 算法数据结构Java
  xaeiTka4h8LY   2024年04月26日   43   0   0 算法数据结构
  xaeiTka4h8LY   2024年04月26日   74   0   0 算法数据结构
  xaeiTka4h8LY   2024年05月31日   43   0   0 算法数据结构Java
  xaeiTka4h8LY   2024年05月17日   39   0   0 算法数据结构leetcode
  boGhnYbtqybm   2023年12月12日   51   0   0 数据结构redisredis数据结构
  xaeiTka4h8LY   2024年05月31日   29   0   0 数据结构
  SjplS62NUFLN   2023年12月12日   22   0   0 微信公众号链表视频教程视频教程微信公众号链表
  97SvV4BTXbIM   2023年12月07日   28   0   0 查找算法数据结构数据数据集数据集数据查找算法数据结构
  xaeiTka4h8LY   2024年05月31日   30   0   0 数据结构数组
  Gjs2egXd7m0h   2023年12月11日   30   0   0 有序向量算法算法有序向量C++二分查找数据结构c++二分查找数据结构
  xaeiTka4h8LY   2024年05月31日   44   0   0 数据结构C
  xaeiTka4h8LY   2024年05月17日   63   0   0 二叉树数据结构
  xaeiTka4h8LY   2024年05月17日   40   0   0 二叉树数据结构
FVOsfHRhTx5x
FVOsfHRhTx5x
作者其他文章 更多
个人博客项目笔记_01

2024-04-08

狂神说Java——Mybatis学习笔记

2024-03-11

线性表——链式存储

2023-11-02

字符串匹配算法

2023-11-02

队列——顺序存储

2023-11-02

栈——顺序存储

2023-11-02

设计并实现大数类 BigNum

2023-11-02

Yolov5——训练目标检测模型详解（含完整源码）

2023-11-02

学习笔记——Python基础

2023-11-02

Yolov5代码详解——detect.py

2023-11-01

最新推荐 更多
考研数据结构之线性表（1.7）——练习题之逆置单链表（C表示）

2024-05-31

考研数据结构之数组（5.3）——使用三元组法表示稀疏矩阵（C表示）

2024-05-31

基于nchan 构建可靠的websocket 服务

2024-05-31

一文带你精通MongDB

2024-05-31

深入理解ClickHouse 的高性能与高可用原理

2024-05-31

redis的数据类型，命令以及应用场景

2024-05-31

java面试知识点整理之扩展系列

2024-05-31

redis简介以及安装

2024-05-31

java面试知识点整理之数据结构算法（待完善）

2024-05-31

【HBase】HBase深度解析：特性、实战应用及核心流程全景

2024-05-31

【HBase】HBase高性能架构：如何保证大规模数据的高可用性

2024-05-31

ClickHouse入门篇:一文带你学习ClickHouse

2024-05-31

【数据结构】时间复杂度和空间复杂度

2024-05-31

387. 字符串中的第一个唯一字符.py-----leetcode刷题（python解题）

2024-05-31

345. 反转字符串中的元音字母-----leetcode刷题（python解题）

2024-05-31

434. 字符串中的单词数

2024-05-31

hive常用命令记录

2024-05-31

Django rest froamwork-HyperlinkedModelSerializer

2024-05-31

mysql-字段值的约束

2024-05-31

【MySQL】表设计与范式设计

2024-05-31

常用标签
数据数据数据数据javalinuxlinuxpythonCentOSredisJavapython区块链技术区块链信息系统字符串MySQL资讯项目管理mysql教程MySQL