备案控制台
探索云世界
开发者社区 人工智能 文章 正文

【数据结构2】链表

2017-01-05 1167
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 1单链表1结点定义2头插法建立单链表3尾插法建立单链表4按序号查找表结点5按值查找表结点6插入结点操作7删除结点操作8合并有序链表2循环双链表1结点定义2插入和删除操作3循环单链表4带尾指针的循环单链表5静态链表由于顺序表的插入和删除操作需要移动大量元素，影响了效率。

由于顺序表的插入和删除操作需要移动大量元素，影响了效率。链式存储不要求逻辑上相邻的两个元素在物理位置上也相邻，而是通过“链”建立起数据元素的逻辑关系。因此，在链表的插入和删除不需要移动元素，只需修改指针。
链式存储的线性表称为链表。其中每个结点（Node）只包含一个数据域和一个指针域的链表称为单链表，首尾相连的单链表称为循环单链表。每个结点只包含一个数据域和两个指针域的链表称为双链表，首尾相连的双链表称为循环双链表。还有一种链表称为静态链表，该链表也有数据域和指针域，这里的指针是结点相对地址（数组下标），又称为游标（cur），静态链表和顺序表一样要预先分配一块连续的内存空间。

1单链表

1.1结点定义

通常用头指针来标识一个单链表，如单链表L（LinkList L;），L=NULL时表示一个空表。因此，为了操作方便就在单链表的首元结点前附加一个结点，即头结点（LinkList L=(LinkList)malloc(sizeof(LNode));）。头结点数据域可以不带今后任何信息，但可记录链表长度，头结点指针域则指向首元结点。此时判断带头结点为空的条件为：L->next==NULL。
这里写图片描述
单链表结点定义为：

typedef struct LNode{   //定义单链表结点类型 
    ElemType data;      //数据域 
    struct LNode *next; //指针域 
}LNode,*LinkList;       //LinkList相当于LNode*，即：struct LNode*

1.2头插法建立单链表

头插法建立单链表

#include<stdio.h>       //NULL
#include<malloc.h>      //malloc
#define ElemType int
typedef struct LNode{   //定义单链表结点类型 
    ElemType data;      //数据域 
    struct LNode *next; //指针域 
}LNode,*LinkList;       //LinkList相当于LNode*，即：struct LNode*
//头插法建立单链表 
LinkList ListCreat_L_FromHead(){
    LinkList L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    int e,length=0;
    printf("请输入插法建立单链表元素（以-1结束）\n");
    scanf("%d",&e);
    while(e!=-1){
        LNode *s=(LNode*)malloc(sizeof(LNode));
        s->data=e;
        s->next=L->next;
        L->next=s;
        length++;
        scanf("%d",&e);
    }
    L->data=length;     //令头结点记录链表长度 
    return L;
}
int main(){
    LinkList L= ListCreat _L_FromHead();
    printf("单链表元素个数：%d 分别是：",L->data);
    for(LNode* N=L->next;N;N=N->next){
        printf("%d ",N->data);
    }
    return 0;
}

1.3尾插法建立单链表

尾插法建立单链表

#include<stdio.h>       //NULL
#include<malloc.h>      //malloc
#define ElemType int
typedef struct LNode{   //定义单链表结点类型 
    ElemType data;      //数据域 
    struct LNode *next; //指针域 
}LNode,*LinkList;       //LinkList相当于LNode*，即：struct LNode*
//尾插法建立单链表 
void ListCreat _L_FromTail(LinkList &L){
    L=(LinkList)malloc(sizeof(LNode));
    L->data=0;L->next=NULL; //L->data为链表长度 
    LNode *r=L;             //r为表尾指针 
    printf("请输入插法建立单链表元素（以-1结束）\n");
    int e;scanf("%d",&e);
    while(e!=-1){
        LNode *s=(LNode*)malloc(sizeof(LNode));
        s->data=e;s->next=NULL;
        r->next=s;
        r=r->next;
        L->data++;          //链表长度+1
        scanf("%d",&e);
    }
}
int main(){
    LinkList L;
    ListCreat _L_FromTail(L);
    printf("单链表元素个数：%d 分别是：",L->data);
    for(LNode* N=L->next;N;N=N->next){
        printf("%d ",N->data);
    }
    return 0;
}

1.4按序号查找表结点

//按序号查找第i个结点 
LNode* ListGetElem_L (LinkList L,int i){
    LNode* p=L->next;       //p为首元结点
    if(i==0)return L;       //返回头结点
    if(i<0)return NULL;     //i无效返回NULL
    for(int j=1;j<i&&p;j++){
        p=p->next;
    } 
    return p;               //返回第i个结点指针；若i>表长则返回的是NULL 
}

1.5按值查找表结点

//按值e查找表结点 
LNode* ListLocate_L (LinkList L,int e){
    LNode* p=L->next;       //p为首元结点
    while(p->data!=e&&p){
        p=p->next;
    } 
    return p;               //返回第i个结点指针；若i>表长则返回的是NULL 
}

1.6插入结点操作

在第i个位置插入结点要先查找插入位置的前驱结点，单链表插入要执行两步必要操作：

  • 把新结点s挂接后继结点并赋值；
  • 把新结点挂在前驱结点p。

这里写图片描述

//在第i个位置插入结点操作 
bool ListInsert_L(LinkList &L,int i,int e){
    LNode* p= ListGetElem_L(L,i-1); //查找插入位置的前驱结点 
    if(p==NULL)return false;    //i定位无效，插入失败返回false 
    LNode* s=(LNode*)malloc(sizeof(LNode)); //为新值分配结点空间 
    s->next=p->next;            //1.把新结点s挂接后继结点p->next
    s->data=e;                  // 新结点赋值
    p->next=s;                  //2.把新结点s挂在前驱结点p
    return true;                //插入成功返回true 
}

1.7删除结点操作

删除第i个结点要先查找删除位置的前驱结点，单链表删除要执行也两步必要操作：

  • 将前驱结点p指向预删除结点的后继结点；
  • 释放预删除结点空间。

这里写图片描述

//删除第i个结点操作 
bool ListDelete_L(LinkList &L,int i,int &e){
    LNode* p=ListGetElem_L(L,i-1);  //查找删除位置的前驱结点 
    if(p||p->next)return false; //i定位无效，删除失败返回false 
    LNode* s=p->next;           //将s指向预删除结点p->next
    e=s->data;                  //将预删除结点s的值赋给e引用传回
    p->next=p->next->next;      //将前驱结点p指向预删除结点的后继结点
    free(s);                    //释放预删除结点空间
    return true;                //删除成功返回true 
}

1.8合并有序链表

将两个有序单链表La和Lb合并为一个有序单链表Lc。

//合并有序链表 
void ListMerge_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    LNode* pa=La->next,*pb=Lb->next;
    LNode* pc=Lc=La;                //用La头结点作为Lc的头结点 
    Lc->data=La->data+Lb->data;     //Lc的长度为La长度与Lb长度之和
    while(pa&&pb){
        if(pa->data<pb->data){      //按非递减归并 
            pc->next=pa;pc=pa;pa=pa->next;
        }else{
            pc->next=pb;pc=pb;pb=pb->next;
        }
    } 
    pc->next=pa?pa:pb;              //插入剩余段 
    free(Lb);                       //释放Lb的头结点 
}

2循环双链表

循环双链表定义头结点要维护循环双链表规则，即：L->next=L->prior=L;。若DLNode *p=L->next;…;p=p->next;，则判断循环双链表为空的条件是p==L;。

2.1结点定义

这里写图片描述

#include<stdio.h>
#include<stdlib.h>
#define ElemType int
typedef struct DLNode{
    ElemType data;
    struct DLNode *prior,*next;
}DLNode,*DLinkList;

int main(int argc,char ** argv ){
    DLinkList L=(DLinkList)malloc(sizeof(DLNode));
    L->next=L->prior=L;     //维护循环双链表规则 
    return 0;
}

2.2插入和删除操作

这里写图片描述

//双循环双链表第i个位置插入e 
bool ListInsert_DL(DLinkList &L,int i,ElemType e){
    if(i<=0)return false;
    DLNode *p=L;
//  for(int j=1;j<i;j++,p=p->next);         //方式一：p是s的前驱 
    for(int j=0;j<i;j++,p=p->next);         //方式二：p是s的后继 
    DLNode* s=(DLNode*)malloc(sizeof(DLNode));
    if(!s)return false;
    s->data=e;
//  s->next=p->next;s->prior=p->next->prior;//方式一：p是s的前驱 
//  p->next->prior=s;p->next=s;
    s->prior=p->prior;p->prior->next=s;     //方式二：p是s的后继 
    s->next=p;p->prior=s;
    return true;
}

3循环单链表

4带尾指针的循环单链表

5静态链表

静态链表的插入、删除操作和动态链表的相同，只需修改指针（游标），而不需移动元素。但静态链表使用没有比单链表的方便，但对于一些不支持指针的高级语言（Basic语言）又是一种巧妙的设计方法。
我们用一个例子来说明静态链表的用法。现求集合(A-B)||(B-A)的元素，即遍历B中元素，如果A中没有该元素则插入A，否则删除从A中该元素。
这里写图片描述

#include<stdio.h>
#define MAXSIZE 11              //减去空闲链表和占用链表两个头指针，有MAXSIZE-2个空闲可以分配 
#define ElemType char
typedef struct{
    ElemType data;              //值域 
    int cur;                    //游标 
}component,SLinklist[MAXSIZE];

    int s;
    SLinklist SL;
void Print();   //声明 Print函数 

/*初始化一维数组space为空闲链表，space[0].cur为头指针*/
void InitSpace_SL(SLinklist &space){
    for(int i=0;i<MAXSIZE;i++)
        space[i].cur=i+1;
    space[MAXSIZE-1].cur=0; 
}
/*从空闲链表分配一个空间以下标i返回,空闲链表空间不够则返回0*/
int Malloc_SL(SLinklist &space){
    int i=space[0].cur;
    if(space[0].cur)space[0].cur=space[i].cur;
    return i;
}
//回收下标为k的空闲结点到空闲链表 
void Free_SL(SLinklist &space,int k){
    space[k].cur=space[0].cur;
    space[0].cur=k;
}

/*求集合(A-B)||(B-A)*/
void difference(SLinklist &space,int &S){
    InitSpace_SL(space);            //初始化空闲链表 
    S=Malloc_SL(space);             //生成占用链表S的头结点 
    int m,n,r=S;                    //r表示占用链表S当前最后结点 
    printf("input the number of A and B: ");
    scanf("%d %d",&m,&n);getchar(); //输入A和B的元素个数 

    /*将A元素加入占用链表 */
    for(int j=1;j<=m;j++){          
        int i=Malloc_SL(space);
        printf("input the data of A one by one with a Enter: ");
        scanf("%c",&space[i].data);getchar();//
        space[r].cur=i;     r=i;
        //Print();//
    }
    space[r].cur=0;                 //尾结点指针域为0 
    Print();//

    /*依次输入B的元素，若不在当前占用链表S中，则插入；否则删除 */
    for(int j=1;j<=n;j++){          
        printf("input the data of B one by one with a Enter: ");
        ElemType b;scanf("%c",&b);getchar();//
        int p=S;
        int k=space[S].cur;
        while(k!=space[r].cur&&space[k].data!=b){
            p=k;k=space[k].cur; //p表示k的前一个元素 
        }
        if(k==space[r].cur){    //该元素不在占用链表S中，插入之 
            int i=Malloc_SL(space);
            space[i].data=b;
            space[i].cur=space[r].cur;
            space[r].cur=i;
            r=i;                //表尾r指向最新元素 
        }else{                  //该元素已在占用链表S中，删除之 
            space[k].data=' ';  //把删除的值清空 
            space[p].cur=space[k].cur;
            Free_SL(space,k);
            if(r==k)r=p;        //若删除的是r所结点，则需修改尾指针 
        }

        Print();//
    }//for
}

int main(int argc,char ** argv){
    difference(SL,s);
    printf("data head index s: %d\n",s);
    return 0;
}

/*定义 Print函数 */
void Print(){
    printf("index:\t");
    for(int i=0;i<MAXSIZE;i++){
        printf("%d\t",i);
    }printf("\n");
    printf("data:\t");
    for(int i=0;i<MAXSIZE;i++){
        printf("%c\t",SL[i].data);
    }printf("\n");
    printf("cur:\t");
    for(int i=0;i<MAXSIZE;i++){
        printf("%d\t",SL[i].cur);
    }printf("\n\n");
    printf(":----------------------------------\n");

}

Wu_Being 博客声明：本人博客欢迎转载，请标明博客原文和原链接！谢谢！
【数据结构系列】《【数据结构2】链表》http://blog.csdn.net/u014134180/article/details/54091157
我的GitHub代码文件：https://github.com/1040003585/Data_Structure

如果你看完这篇博文，觉得对你有帮助，并且愿意付赞助费，那么我会更有动力写下去。
Wu_Being 吴兵博客接受赞助费二维码

文章标签：
负载均衡
机器学习/深度学习
Perl
网络协议
SDN
存储
关键词：
数据结构链表
链表数据结构
相关实践学习
部署高可用架构
本场景主要介绍如何使用云服务器ECS、负载均衡SLB、云数据库RDS和数据传输服务产品来部署多可用区高可用架构。
负载均衡入门与产品使用指南
负载均衡（Server Load Balancer）是对多台云服务器进行流量分发的负载均衡服务，可以通过流量分发扩展应用系统对外的服务能力，通过消除单点故障提升应用系统的可用性。 本课程主要介绍负载均衡的相关技术以及阿里云负载均衡产品的使用方法。
wu_being
目录
相关文章
吹吹晚风
|
22天前
|
存储 缓存 算法
数据结构-链表(一)
链表（Linked List）是一种常见的数据结构，用于存储和组织数据。与数组不同，链表的元素（节点）在内存中不必连续存储，而是通过指针链接在一起。 链表由多个节点组成，每个节点包含两部分：数据（存储实际的元素值）和指针（指向下一个节点的引用）。链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针通常指向空值（null）。
吹吹晚风
31 1
小林熬夜学编程
|
24天前
|
存储 C++
数据结构第六弹---带头双向循环链表
数据结构第六弹---带头双向循环链表
小林熬夜学编程
30 0
起飞的风筝
|
1月前
|
存储
【单链表】数据结构单链表的实现
【单链表】数据结构单链表的实现
起飞的风筝
32 0
程序员林小鹿
|
1月前
|
C++
从0开始回顾数据结构---链表与堆
#include <iostream> #include <algorithm> #include <string.h> using namespace std; const int N = 100010; int h[N], ph[N], hp[N], cnt; void heap_swap(int a, int b) { swap(ph[hp[a]],ph[hp[b]]); swap(hp[a], hp[b]); swap(h[a], h[b]); } void down(int u) { int t = u; if (u * 2 <= cnt &&
程序员林小鹿
28 2
卫卫周大胖
|
1月前
|
存储
【数据结构】双向带头循环链表的实现
【数据结构】双向带头循环链表的实现
卫卫周大胖
24 1
卫卫周大胖
|
1月前
【数据结构】单链表之--无头单向非循环链表
【数据结构】单链表之--无头单向非循环链表
卫卫周大胖
24 2
鲜于言悠
|
1月前
|
存储 缓存 算法
数据结构从入门到精通——链表
链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的一个显著特点是，它不需要在内存中连续存储，因此可以高效地插入和删除节点。这种灵活性使得链表在许多应用中成为理想的选择，尤其是在需要动态调整数据结构大小的场景中。
鲜于言悠
72 0
喵~来学编程啦
|
5天前
数据结构—链表（超详细）(山东大学）（数据结构实验三）
数据结构—链表（超详细）(山东大学）（数据结构实验三）
喵~来学编程啦
6 0
吐个泡泡。。。。
|
7天前
数据结构|双向链表|带头结点|头插|尾插|尾删|头删
数据结构|双向链表|带头结点|头插|尾插|尾删|头删
吐个泡泡。。。。
7 0
Mylvzi
|
7天前
数据结构--链表刷题(一)快慢指针（上）
数据结构--链表刷题(一)快慢指针
Mylvzi
14 0

热门文章

最新文章

  • 1
    C++链表解析：从基础原理到高级应用，全面掌握链表的使用
  • 2
    线性表，双向链表，静态链表，循环链表(约瑟夫环)（上）
  • 3
    【C/C++ 链表结构】探索链表迭代器：C++实现的深入分析与优化策略
  • 4
    【链表】还不会用C++实现链表？一文教会你各种链表的实现
  • 5
    【C++ 数据结构与算法 一站式备考指南】一文掌握 数据结构与算法课程 知识点（二）
  • 6
    Java 学习路线：基础知识、数据类型、条件语句、函数、循环、异常处理、数据结构、面向对象编程、包、文件和 API
  • 7
    C++关联容器深度解析：提升数据结构操作的艺术
  • 8
    【数据结构】【版本2.0】【树形深渊】——二叉树入侵
  • 9
    【C/C++ 数据结构 】从零开始实现哈希表：C++实践指南
  • 10
    19 删除链表的倒数第 N 个结点
  • 1
    【手撕数据结构】二分查找(好多细节)
    16
  • 2
    【数据结构与算法】—— 手撕红黑树
    34
  • 3
    【排序算法】数据结构排序详解
    41
  • 4
    【链式二叉树】数据结构链式二叉树的（万字详解）
    35
  • 5
    【堆】数据结构堆的实现（万字详解）
    50
  • 6
    【树和二叉树】数据结构二叉树和树的概念认识
    23
  • 7
    【双向链表】数据结构双向链表的实现
    20
  • 8
    数据结构——单链表的基本操作
    11
  • 9
    数据结构——排序算法之快速排序
    33
  • 10
    数据结构——二叉树的链式结构
    34

    • 相关课程

    更多
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 如何使用Tair增强数据结构构建丰富在线实时场景
  • Apache Flink 流式应用中状态的数据结构定义升级
  • 低代码开发师（初级）实战教程
    • 下一篇
    阿里云oss简介和使用流程