首页 > 其他分享 >线性表——链式存储

线性表——链式存储

时间：2023-09-10 20:33:07浏览次数：39  
标签：存储 return LNode 结点 next LinkList 链式 NULL 线性表

单链表（有头结点）

#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<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<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<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(){
    
}

标签：存储,return,LNode,结点,next,LinkList,链式,NULL,线性表
From： https://blog.51cto.com/u_15789760/7427831

相关文章

  • C语言---数据存储
    我们知道一个变量在内存中存储是要开辟一块内存空间来存储的，那么该为这个变量开辟多大的内存空间呢？这个要依据变量的类型，我们知道int类型的变量大小是4个字节，char类型的变量大小是1个字节，创建一个变量时，根据其类型来为变量申请对应大小的空间。问题：那么不同类型的数据在内存中到底......
  • MinIO对象存储
    MinIO简介MinIO基于ApacheLicensev2.0开源协议的对象存储服务，可以做为云存储的解决方案用来保存海量的图片，视频，文档。由于采用Golang实现，服务端可以工作在Windows,Linux,OSX和FreeBSD上。配置简单，基本是复制可执行程序，单行命令可以运行起来。MinIO兼容亚马逊S3云存储服务接......
  • 支持 range-based for 循环的链式前向星模板
    众所周知，OI中图的存储主要有两种方式：使用std::vector实现的邻接表，以及链式前向星。前者的常数较大，有时候会出现卡不过去的情况，但是支持range-basedfor循环，遍历的时候代码更简洁。可不可以在使用链式前向星的同时，使用range-basedfor循环呢？如以下代码所示：Graphgraph;int......
  • C数据结构-线性表之顺序表
    什么是线性表线性表的插入元素线性表的删除元素线性表顺序存储的缺点线性表的特点1.线性表的实例首先我们创建3个文件，分别如下：liner_data--sqlist.c--sqlist.h--test.csqlist.h//.h文件中定位数据的结构以及函数的方法typedefintdata_t;#defineN128......
  • Scrapy深入使用_存储
    目录Scrapy深入使用-存储scrapy的深入使用学习目标：1、了解scrapy的debug信息2、了解scrapyShell3、settings.py中的设置信息3.1为什么项目中需要配置文件3.2配置文件中的变量使用方法3.3settings.py中的重点字段和含义4、pipeline管道的深入使用4.1使用终端命令行进行存储4.2......
  • 信管知识梳理（二）常规信息系统集成技术（网络协议、网络存储技术、网络工程、数据仓库和中
    一、网络标准与网络协议1.1OSI网络七层架构国际标准化组织（ISO）提出的网络体系结构模型，也叫做开发系统互连参考模型（OSI/RM）,通常叫做OSI参考模型。如下图所示：物理层、数据链路层、网络层：统称为通信子网。是为了联网而附加的通信设备完成数据的传输功能。应用层、表示层、会......
  • 【笔记】二维数组在内存地址中的存储
    最近在学习STM32的ADC和DMA多通道采集过程中有使用到二维数组，姑且记录一下以作备忘。参考：http://c.biancheng.net/view/2022.html举个例子就能很简单的说明了创建一个M行N列的int数组，数组定义如下（例：M=3N=5）#defineM3#defineN5intarr[M][N];给数组按顺序赋值int(*......
  • MySQL事务及常见存储引擎
    一、事务的四特性事务：transaction一个数据库事务由一条或者多条可发生事务的SQL语句构成，它们形成一个逻辑的工作单元。这些SQL语句要么全部执行成功，要么全部执行失败 原子性(Atomicity)A   事务的原子性是指事务中包含的所有操作要么完成（提交），要么不做（回滚）,也就是说所有的活动......
  • 图解RAID存储技术：RAID 0、1、5、6、10、50、60
    下午好，我的网工朋友。硬盘设备是计算机中较容易出现故障的元器件之一，也是网工们最经常接触到的设备之一，用途广泛。但是，硬盘不能像CPU、内存、电源甚至主板那样在出现故障后换新的去解决问题，所以经常会需要让你关注“数据冗余”和“异地备份”这两个模块的工作内容。今天这篇文章就......
  • 服务器数据恢复-EMC存储RAID5磁盘离线热备盘未激活的数据恢复案例
    服务器数据恢复环境：北京某单位有一台EMC某型号存储，有一组由10块STAT硬盘组建的RAID5阵列，另外2块磁盘作为热备盘使用。RAID5阵列上层只划分了一个LUN，分配给SUN小机使用，上层文件系统为ZFS。服务器故障：存储RAID5阵列中有2块硬盘损坏离线，只有一块热备盘激活，RAID5阵列瘫痪，上层LUN无法......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99