AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】线性表（顺序存储和链式存储）两种方法，细节满满，保你学会（二）

2023-05-10 85
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】线性表（顺序存储和链式存储）两种方法，细节满满，保你学会

✨链式存储

🎆一定别忘记生成新结点

🍔存储结构

typedef struct LNode{
  int data;     //数据域
  struct LNode *next; //指针域
}LNode,*LinkList;

LinkList为指向结构体LNode的指针类型

🚥🚥🚥🚥🚥🚥

⭐习惯上用LinkList定义单链表，强调的是某个单链表的头指针，用LNode*定义指向单链表中任意结点的指针变量

例如：

定义LinkList L,那么L为单链表的头指针

定义LNode *p，那么p为指向单链表某个结点的指针，用*p代表该节点

⭐注意区分指针变量和结点变量两个不同的概念

例如

若定义LinkList p或LNode *p

p表示指向某个结点的指针变量，表示该结点的地址

*p表示对应的结点变量，表示该结点的名称

这两种定义方式是等价的

🚥🚥🚥🚥🚥🚥

⭐易错：首元结点VS头节点VS头指针


头节点是首元结点之前附设的结点

头指针是指向链表第一个结点的指针

（如果有头节点，那么头指针指向的结点为头节点）

（如果没有头节点，那么头指针指向的结点为首元结点）

image.png🚥🚥🚥🚥🚥🚥

⭐链表增加头结点的好处


🎈便于首元结点的处理

增加头结点后，首元结点的地址

🎈便于空表和非空表的统一处理

没有头结点，设L为单链表的头指针，L应该指向首元结点，那么当单链表为长度为0的空表时 ，L指针为空（L==NULL）

有头结点，无论链表是否为空，头指针都是指向头节点的非空指针，那么当头结点的指针域为空，（L->next==NULL）如下图所示  

image.png

🚥🚥🚥🚥🚥🚥

在顺序表中，由于相邻的两个元素在物理位置上相邻，那么每个元素的存储位置都可以从线性表的起始位置计算得到

在单链表里面，各个元素的存储位置都是任意的，都是每个元素的存储位置都包含着其直接前驱结点，因为p->next=ai , p->next->next=ai+1 , 那么想要取得第i个数据元素必须从头指针出发顺链寻找

🚥🚥🚥🚥🚥🚥

🎈初始化


生成新结点作为头结点，用头指针 L 指向头结点

头结点的指针域置空

int InitList(LinkList &L)
{
  L=new LNode;
  L->next=NULL;
  return 1;
}

int InitList(LinkList *L)
{
  *L=new LNode;
  (*L)->next=NULL;//必须加上括号
  return 1;
}

为什么必须加上（）：优先级：->大于*

🎈尾插法建立单链表


1.创建一个只有头结点的空链表

2.尾指针 r 初始化，指向头结点

3.根据创建链表包括的元素个数n，循环n次执行以下操作

~生成一个新结点*p

~输入元素并把值赋给新结点*p的数据域

~将新结点*p插入尾结点*r后面

~尾指针r指向新的尾结点*p

（在前面说过，*X表示结点的名称）

image.png

int Create_back(LinkList &L,int num)
{
  L=new LNode;
  LNode *p,*r;    //先建立一个带有头节点的空链表 
  L->next=NULL;   //尾指针r指向头结点
  r=L;
  for(int i=0;i<num;i++)
  {
    p=new LNode;  //生成新结点
    cin>>p->data;
    p->next=NULL;
    r->next=p;    //新结点*p插入尾结点*r后（*X表示结点的名称）
    r=p;      //r指向新的尾结点*p
  } 
  return 1;
}

代码里面的 LNode *p,*r;还可以写为LinkList p,r;具体原因在上面说过了（就是在上面的⭐注意区分指针变量和结点变量两个不同的概念）

int Create_back(LinkList *L,int num)
{
  *L=new LNode;
  LNode *p,*r;    //先建立一个带有头节点的空链表 
  (*L)->next=NULL;    //尾指针r指向头结点
  r=*L;
  for(int i=0;i<num;i++)
  {
    p=new LNode;  //生成新结点
    cin>>p->data;
    p->next=NULL;
    r->next=p;    //新结点*p插入尾结点*r后（*X表示结点的名称）
    r=p;      //r指向新的尾结点*p
  } 
  return 1;
}

🎈头插法建立单链表

1.创建一个只有头结点的空链表

2.根据创建链表包括的元素个数n，循环n次执行以下操作

~生成一个新结点*p

~输入元素并把值赋给新结点*p的数据域

~将新结点*p插入到头结点后面

image.png

int Create_front(LinkList &L,int num)
{
  L=new LNode;
  LNode *p;
  L->next=NULL;
  for(int i=0;i<num;i++)
  {
    p=new LNode;    //生成新结点*p
    cin>>p->data;
    p->next=L->next;
    L->next=p;      //将新结点*p插入到头结点后面
  }
  return OK;
}
int Create_front(LinkList *L,int num)
{
  *L=new LNode;
  LNode *p;
  (*L)->next=NULL;
  for(int i=0;i<num;i++)
  {
    p=new LNode;    //生成新结点*p
    cin>>p->data;
    p->next=(*L)->next;
    (*L)->next=p;     //将新结点*p插入到头结点后面
  }
  return OK;
}

🎈插入

注意：插入和前面的前插法尾插法不同，前插法尾插法是建立单链表，而插入是在已经建立好的单链表里面再加入额外的结点

具体步骤如下图所示

image.png

注意：插入操作必须要找到该位置的前驱结点

（这句话看上去理所应当，但是在某些时候是真的特别有用） 

int ListInsert(LinkList &L,int num,int place)
{
  LNode *p,*s;
  p=L;
  int j=0;
  while(p&&j<place-1)        //找到插入位置
  {
    p=p->next;
    j++;
  }
  if(!p||j>place-1) return ERROR;
  s=new LNode;         //生成新结点
  s->data=num;         //数据域赋值
  s->next=p->next;       //结点*s的指针域指向a2
  p->next=s;           //结点*p的指针域指向*s
  return OK;
}
int ListInsert(LinkList *L,int num,int place)
{
  LNode *p,*s;
  p=*L;
  int j=0;
  while(p&&j<place-1)        //找到插入位置
  {
    p=p->next;
    j++;
  }
  if(!p||j>place-1) return ERROR;
  s=new LNode;         //生成新结点
  s->data=num;         //数据域赋值
  s->next=p->next;       //结点*s的指针域指向a2
  p->next=s;           //结点*p的指针域指向*s
  return OK;
}

🎈删除

1.先找到待删除位置a的前驱结点

2.创建临时结点q，保存待删除结点的地址

3.将结点*p的指针域指向a的直接后继结点

4.释放结点a的空间

image.png

int LinkDelete(LinkList &L,int place)
{
  LNode *p,*q;
  p=L;
  int j=0;
  while((p->next)&&(j<place-1))
  {
    p=p->next;
    ++j;
  } 
  if(!(p->next)||(j>place-1) )return ERROR;
  q=p->next;        //创建临时结点q
  p->next=q->next;    //改变待删除结点的前驱结点的指针域
  delete q;       //释放被删除结点的空间
  return OK;
}
int LinkDelete(LinkList *L,int place)
{
  LNode *p,*q;
  p=*L;
  int j=0;
  while((p->next)&&(j<place-1))
  {
    p=p->next;
    ++j;
  } 
  if(!(p->next)||(j>place-1) )return ERROR;
  q=p->next;        //创建临时结点q
  p->next=q->next;    //改变待删除结点的前驱结点的指针域
  delete q;       //释放被删除结点的空间
  return OK;
}

🎈取出元素

找到要取出的元素的位置，然后返回数据域即可

int ListPop(LinkList &L,int num)
{
  LNode *p;
  p=L;
  int j=0;
  while(p&&j<num)
  {
    p=p->next;
    j++;
  }
  if(p)
  return p->data;
  else
  return -1;
}
int ListPop(LinkList *L,int num)
{
  LNode *p;
  p=*L;
  int j=0;
  while(p&&j<num)
  {
    p=p->next;
    j++;
  }
  if(p)
  return p->data;
  else
  return -1;
}

🎈输出链表

void OutputList(LinkList &L)
{
  LNode *p;
  p=L->next;
  while(p)
  {
    cout<<p->data<<' ';
    p=p->next;
  }
  cout<<endl;
}
void OutputList(LinkList *L)
{
  LNode *p;
  p=(*L)->next;
  while(p)
  {
    cout<<p->data<<' ';
    p=p->next;
  }
  cout<<endl;
}

😎完整代码1

#include<iostream>
using namespace std;
#define OK 1
#define ERROR -1
typedef struct LNode
{
  int data;
  struct LNode *next;
}LNode,*LinkList;
//1
int InitList(LinkList *L)
{
  *L=new LNode;
  (*L)->next=NULL;
  return OK;
}
int Create_front(LinkList *L,int num)
{
  *L=new LNode;
  LNode *p;
  (*L)->next=NULL;
  for(int i=0;i<num;i++)
  {
    p=new LNode;    //生成新结点*p
    cin>>p->data;
    p->next=(*L)->next;
    (*L)->next=p;     //将新结点*p插入到头结点后面
  }
  return OK;
}
//3
int ListInsert(LinkList *L,int num,int place)
{
  LNode *p,*s;
  p=*L;
  int j=0;
  while(p&&j<place-1)        //找到插入位置
  {
    p=p->next;
    j++;
  }
  if(!p||j>place-1) return ERROR;
  s=new LNode;         //生成新结点
  s->data=num;         //数据域赋值
  s->next=p->next;       //结点*s的指针域指向a2
  p->next=s;           //结点*p的指针域指向*s
  return OK;
}
//4
int LinkDelete(LinkList *L,int place)
{
  LNode *p,*q;
  p=*L;
  int j=0;
  while((p->next)&&(j<place-1))
  {
    p=p->next;
    ++j;
  } 
  if(!(p->next)||(j>place-1) )return ERROR;
  q=p->next;        //创建临时结点q
  p->next=q->next;    //改变待删除结点的前驱结点的指针域
  delete q;       //释放被删除结点的空间
  return OK;
}
//5
int ListPop(LinkList *L,int num)
{
  LNode *p;
  p=*L;
  int j=0;
  while(p&&j<num)
  {
    p=p->next;
    j++;
  }
  if(p)
  return p->data;
  else
  return -1;
}
void OutputList(LinkList *L)
{
  LNode *p;
  p=(*L)->next;
  while(p)
  {
    cout<<p->data<<' ';
    p=p->next;
  }
  cout<<endl;
}
int main()
{
  LinkList L;
  int n,e;
  cout<<"请输入你的操作"<<endl;
  printf("0:结束程序\n1:建立空表\n2:尾插法建立空表\n3:插入\n4:删除\n5:取出元素\n");
  for(;;)
  {
    cin>>n;
    switch(n)
    {
      case 0:
        return 0;
        break;
      case 1:
        cout<<"建立空表"<<endl;
        if(InitList(&L))
        {
          cout<<"建立成功"<<endl;
        }
        else
        {
          cout<<"建立失败"<<endl;
        }
        break;
      case 2:
        cout<<"输入21 18 30 75 42 56，使用尾插法建立链表"<<endl;
        cout<<"请输入要加入的数字的数量"<<endl;
        int num;
        cin>>num;
        if(Create_front(&L,num)!=0)
        {
           cout<<"请进行下一步操作"<<endl;
           OutputList(&L); 
        }
        else cout<<"失败了"<<endl;
        break;
      case 3:
        cout<<"在第3个位置插入67，在第9个位置插入10"<<endl;
        cout<<"请输入需要插入的数字的个数"<<endl;
        int qqq;
        cin>>qqq;
        for(int i=0;i<qqq;i++)
        {
          cout<<"需要插入的数据和位置"<<endl;
          int nn,mm;
          cin>>nn>>mm;
          if(ListInsert(&L,nn,mm))
          {
            cout<<"插入成功"<<endl;
            OutputList(&L);
          }
          else
          {
            cout<<"插入失败"<<endl;
          }
        }
        break;
      case 4:
        cout<<"删除第6个元素和第8个元素"<<endl;
        cout<<"输入需要删除的元素是哪一个"<<endl;
        int qq;
        cin>>qq;
        if(LinkDelete(&L,qq))
        {
          cout<<"删除成功"<<endl;
          OutputList(&L);
        } 
        else
        {
          cout<<"删除失败"<<endl;
        }
        break;
      case 5:
        cout<<"取出第5个元素和第7个元素"<<endl;
        cout<<"需要取出多少个数"<<endl;
        int cnt;
        cin>>cnt;
        for(int i=0;i<cnt;i++)
        {
          cout<<"需要取出哪个位置的元素"<<endl;
          int _;
          cin>>_;
          if(ListPop(&L,_)==-1) cout<<"取出元素失败"<<endl;
          else  cout<<ListPop(&L,_)<<endl;
        }
        break;
    }
  }
}

😎完整代码2 

#include<iostream>
using namespace std;
#define OK 1
#define ERROR -1
typedef struct LNode
{
  int data;
  struct LNode *next;
}LNode,*LinkList;
//1
int InitList(LinkList &L)
{
  L=new LNode;
  L->next=NULL;
  return OK;
}
//2
int Create_back(LinkList &L,int num)
{
  L=new LNode;//头节点 
  LNode *p,*r;
  L->next=NULL;
  r=L;
  for(int i=0;i<num;i++)
  {
    p=new LNode;
    cin>>p->data;
    p->next=NULL;
    r->next=p;
    r=p;  
  } 
  return OK;
}
//3
int ListInsert(LinkList &L,int num,int place)
{
  LNode *p,*s;
  p=L;
  int j=0;
  while(p&&j<place-1)
  {
    p=p->next;
    j++;
  }
  if(!p||j>place-1) return ERROR;
  s=new LNode;
  s->data=num;
  s->next=p->next;
  p->next=s;
  return OK;
}
//4
int LinkDelete(LinkList &L,int place)
{
  LNode *p,*q;
  p=L;
  int j=0;
  while((p->next)&&(j<place-1))
  {
    p=p->next;
    ++j;
  } 
  if(!(p->next)||(j>place-1) )return ERROR;
  q=p->next;
  p->next=q->next;
  //e=p->data;
  delete q;
  return OK;
}
//5
int ListPop(LinkList &L,int num)
{
  LNode *p;
  p=L;
  int j=0;
  while(p&&j<num)
  {
    p=p->next;
    j++;
  }
  if(p)
  return p->data;
  else
  return -1;
}
void OutputList(LinkList &L)
{
  LNode *p;
  p=L->next;
  while(p)
  {
    cout<<p->data<<' ';
    p=p->next;
  }
  cout<<endl;
}
int main()
{
  LinkList L;
  int n,e;
  cout<<"请输入你的操作"<<endl;
  printf("0:结束程序\n1:建立空表\n2:尾插法建立空表\n3:插入\n4:删除\n5:取出元素\n");
  for(;;)
  {
    cin>>n;
    switch(n)
    {
      case 0:
        return 0;
        break;
      case 1:
        cout<<"建立空表"<<endl;
        if(InitList(L))
        {
          cout<<"建立成功"<<endl;
        }
        else
        {
          cout<<"建立失败"<<endl;
        }
        break;
      case 2:
        cout<<"输入21 18 30 75 42 56，使用尾插法建立链表"<<endl;
        cout<<"请输入要加入的数字的数量"<<endl;
        int num;
        cin>>num;
        if(Create_back(L,num)!=0)
        {
           cout<<"请进行下一步操作"<<endl;
           OutputList(L); 
        }
        else cout<<"失败了"<<endl;
        break;
      case 3:
        cout<<"在第3个位置插入67，在第9个位置插入10"<<endl;
        cout<<"请输入需要插入的数字的个数"<<endl;
        int qqq;
        cin>>qqq;
        for(int i=0;i<qqq;i++)
        {
          cout<<"需要插入的数据和位置"<<endl;
          int nn,mm;
          cin>>nn>>mm;
          if(ListInsert(L,nn,mm))
          {
            cout<<"插入成功"<<endl;
            OutputList(L);
          }
          else
          {
            cout<<"插入失败"<<endl;
          }
        }
        break;
      case 4:
        cout<<"删除第6个元素和第8个元素"<<endl;
        cout<<"输入需要删除的元素是哪一个"<<endl;
        int qq;
        cin>>qq;
        if(LinkDelete(L,qq))
        {
          cout<<"删除成功"<<endl;
          OutputList(L);
        } 
        else
        {
          cout<<"删除失败"<<endl;
        }
        break;
      case 5:
        cout<<"取出第5个元素和第7个元素"<<endl;
        cout<<"需要取出多少个数"<<endl;
        int cnt;
        cin>>cnt;
        for(int i=0;i<cnt;i++)
        {
          cout<<"需要取出哪个位置的元素"<<endl;
          int _;
          cin>>_;
          if(ListPop(L,_)==-1) cout<<"取出元素失败"<<endl;
          else  cout<<ListPop(L,_)<<endl;
        }
        break;
    }
  }
}

🥰如果大家有不明白的地方，或者文章有问题，欢迎大家在评论区讨论，指正🥰

Code over！

文章标签：
C++
人工智能
存储
关键词：
数据结构存储
数据结构线性表
数据结构方法
数据结构线性表存储
数据结构链式
在下小吉.
目录
相关文章
龙大吉
|
2月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理，包括初始化、数据点分配与簇中心更新等步骤，以及如何在Python中实现该算法，最后讨论了其优缺点及应用场景。
龙大吉
146 4
RossyYan
|
1天前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储（头歌实践教学平台习题）【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系，邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵，预期输出为Prim算法求解结果。通关代码提供了完整的C++实现，包括输入、构建和打印邻接矩阵与邻接表的功能。
RossyYan
23 10
RossyYan
|
1天前
|
存储 算法 测试技术
【C++数据结构——线性表】求集合的并、交和差运算（头歌实践教学平台习题）【合集】
本任务要求编写程序求两个集合的并集、交集和差集。主要内容包括： 1. **单链表表示集合**：使用单链表存储集合元素，确保元素唯一且无序。 2. **求并集**：遍历两个集合，将所有不同元素加入新链表。 3. **求交集**：遍历集合A，检查元素是否在集合B中存在，若存在则加入结果链表。 4. **求差集**：遍历集合A，检查元素是否不在集合B中，若满足条件则加入结果链表。 通过C++代码实现上述操作，并提供测试用例验证结果。测试输入为两个集合的元素，输出为有序集合A、B，以及它们的并集、交集和差集。 示例测试输入： ``` a c e f a b d e h i ``` 预期输出：
RossyYan
25 7
RossyYan
|
1天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】单链表的基本运算（头歌实践教学平台习题）【合集】
本内容介绍了单链表的基本运算任务，涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法，并提供了测试说明、通 - **任务描述**：实现单链表的基本运算。 - **相关知识**：包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**：平台会对你编写的代码进行测试，提供测试输入和预期输出。 - **通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了测试通过后的预期输出结果。 开始你的任务吧，祝你成功！
RossyYan
19 5
RossyYan
|
1天前
|
机器学习/深度学习 存储 C++
【C++数据结构——线性表】顺序表的基本运算（头歌实践教学平台习题）【合集】
本文档介绍了线性表的基本运算任务，涵盖顺序表和链表的初始化、销毁、判定是否为空、求长度、输出、查找元素、插入和删除元素等内容。通过C++代码示例详细展示了每一步骤的具体实现方法，并提供了测试说明和通关代码。 主要内容包括： - **任务描述**：实现顺序表的基本运算。 - **相关知识**：介绍线性表的基本概念及操作，如初始化、销毁、判定是否为空表等。 - **具体操作**：详述顺序表和链表的初始化、求长度、输出、查找、插入和删除元素的方法，并附有代码示例。 - **测试说明**：提供测试输入和预期输出，确保代码正确性。 - **通关代码**：给出完整的C++代码实现，帮助完成任务。 文档
RossyYan
19 5
肾透侧视攻城狮
|
2月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二（5）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
28 0
游客zi3qmblbcdexu
|
3月前
|
存储
ES6中的Set数据结构的常用方法和使用场景
ES6中的Set数据结构的常用方法和使用场景
游客zi3qmblbcdexu
26 0
ephemerals__
|
2月前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
256 9
那年春天
|
2月前
|
存储 算法
非递归实现后序遍历时，如何避免栈溢出？
后序遍历的递归实现和非递归实现各有优缺点，在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
那年春天
41 1
RossyYan
|
1天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算（头歌实践教学平台习题）【合集】
本关任务：编写一个程序实现顺序栈的基本运算。开始你的任务吧，祝你成功！​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念：初始化栈是为栈的使用做准备，包括分配内存空间（如果是动态分配）和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈，通常需要定义一个数组来存储栈元素，并设置一个变量来记录栈顶位置；对于链式栈，需要定义节点结构，包含数据域和指针域，同时初始化栈顶指针。 示例（顺序栈）： 以下是一个简单的顺序栈初始化示例，假设用C语言实现，栈中存储
RossyYan
110 75