【数据结构】线性表（顺序存储和链式存储）两种方法，细节满满，保你学会（一）-阿里云开发者社区

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

2023-05-10 342

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

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

⭐定义：

线性表（List）:零个或多个数据元素的有限序列

⭐ 理解：

线性表，顾名思义，就是具有像线一样性质的表，元素之间是有顺序的，若元素存在多个，那么第一个元素没有前驱元素，最后一个元素没有后继元素，其他元素既有前驱元素又有后继元素

⭐存储方式：

线性存储

链式存储

⭐顺序存储的优缺点：

优点：

1.表中数据元素可以根据序号随机存取

2. 存储密度大，存储密度为1（存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比）

缺点：

1.做插入、删除操作时，要移动大量元素，因此对很长的线性表操作效率低，插入和删除操作不方便；

2.要预先分配存储空间，预先估计过大，会导致存储空间浪费，估计过小，会造成数据溢出。

⭐链式存储的优缺点：

优点：

1.做插入、删除操作时，不用移动大量元素，相比线性存储方式方便；

2.不用预先分配存储空间。

缺点：

1.表中数据元素不可随机存取

2.存储密度小，存储密度小于1

⭐基本操作

✨顺序存储

🍔存储结构

#define maxsize 100
typedef struct{
  ElemType *elem;//由于这里不知道线性表的具体长度，所以这里就用了指针
                   //可以是elem[maxsize]
  int length;
}SqList;

其中ElemType可以改为其他的数据类型，比如

typedef int ElemType

length表示当前线性表中数据元素的个数，注意数组里面的下标是从0开始的，那么

a1->elem[0]; //注意，用数组表示

a2->elem[1];

a3->elem[2] ;

an->elem[length-1];

🎈初始化

🚕分配空间，建立空表，使空表长度为0

使用引用初始化

int InitList(SqList &L)
{
  L.elem=new ElemType[maxsize];
  if(!L.elem) return -1;      //内存分配失败
  L.length=0;           //空表长度为0
  return 1; 
}

使用指针初始化

int InitList(SqList* L)
{
  L->elem = new int[100];
  if (!L->elem) exit(overflow);
  L->length = 0;
  return OK;
}

🎈添加数字建立表

🚕向空表里面添加数字，从而建立线性表

使用引用

void InputList(SqList& L, int num)
{
  L.elem[k++] = num;
  L.length++;
}

使用指针

void InputList(SqList* L, int num)
{
  L->elem[k++] = num;
  L->length++;
}

🎈输出线性表里面的数

🚕输出线性表里面的数

使用引用

void OutputList(SqList& L)
{
  for (int i = 1; i <= L->length; i++)
  {
    cout << L.elem[i] << " ";
  }
}

使用指针

void OutputList(SqList *L)
{
  for (int i = 1; i <= L.length; i++)
  {
    cout << L->elem[i] << " ";
  }
}

🎈插入数字

🚕顺序存储插入数字，就是找到要插入的数字的位置，从这个位置开始的后面的所有的数字全都后移一位，这样子前面就回空出一个位置，就是要插入的数字的位置

使用引用

void ListInsert(SqList& L, int place, int num)
{
  L.length++;
  for (int i = L.length; i >= place; i--)
  {
    L.elem[i + 1] = L.elem[i];
  }
  L.elem[place] = num;
}

注意：这里是 i = L.length , 不是 i = L.length-1

你想一下，数组下标是从0开始的，所以整个表最后一个位置（L.elem[length]）没有存数

这样把数组后移，到最后刚好可以空出一个位置来存需要插入的数

使用指针

void ListInsert(SqList *L, int place, int num)
{
  L->length++;
  for (int i = L->length; i >= place; i--)
  {
    L->elem[i + 1] = L->elem[i];
  }
  L->elem[place] = num;
}

🎈删除数字

🚕与插入数字类似，删除数字采用的是向前覆盖数字

使用引用

void ListDelete(SqList& L, int place)
{
  for (int i = place; i <= L.length; i++)
  {
    L.elem[i - 1] = L.elem[i];
  }
  L.length--;
}

使用指针

void ListDelete(SqList *L, int place)
{
  for (int i = place; i <= L->length; i++)
  {
    L->elem[i - 1] = L->elem[i];
  }
  L->length--;
}

🎈取出数字

🚕就是给出这个数字的位置，就是想当于给出了这个数字在数组里面的位置，然后直接根据这个位置取值

int GetElem(SqList L, int i, int& e)//int *e
{
  if ((i < 1) || (i > L.length)) return -1;
  e = L.elem[i];                  //*e=L.elem[i];
  return 1;
}

int GetElem(SqList *L, int i, int& e)
{
  if ((i < 1) || (i > L->length)) return -1;
  e = L->elem[i];
  return 1;
}

🎈置空

🚕直接L.length=0就可以了

（如果要返回线性表的长度，直接L.length即可）

😎完整代码1

#include<iostream>
using namespace std;
#define OK 1
#define overflow -1
int k=1;
typedef struct{
  int *elem;
  int length;
}SqList;
int InitList(SqList &L)
{
  L.elem=new int[100];
  if(!L.elem) exit(overflow);
  L.length=0;
  return OK;
}
//3
void InputList(SqList &L,int n)
{
  L.elem[k++]=n;
  L.length++;
}
//4
void OutputList(SqList &L)
{
  for(int i=1;i<=L.length;i++)
  {
    cout<<L.elem[i]<<" ";
  }
} 
//5
void ListInsert(SqList &L,int a,int b)
{
  L.length++;
  for(int i=L.length;i>=a;i--)
  {
    L.elem[i+1]=L.elem[i];
  }
  L.elem[a]=b;
}
//6   
 void ListDelete(SqList &L,int x)
 {
  for(int i=x;i<=L.length;i++)
  {
    L.elem[i-1]=L.elem[i];
   }  
  L.length--;
 }
 //7
 int GetElem(SqList L,int i,int &e)
 { 
  if((i<1)||(i>L.length)) return -1;
   e=L.elem[i];
   return OK;
 }
 //8
int ClearList(SqList L)
{
    L.length=0;
    return 1;
}
int main()
{
  SqList L;
  int s,e;
  InitList(L);
  if(InitList) cout<<"成功"<<endl;
  else cout<<"失败"<<endl;
  cout<<"0:退出程序"<<endl;
  cout<<"3:加入数"<<endl;
  cout<<"4:输出线性表里面的数"<<endl;
  cout<<"5:插入数"<<endl;
  cout<<"6:删除数"<<endl;
  cout<<"7:取出某个位置的数"<<endl;
  cout<<"8:置空"<<endl;
  cout<<endl;
  for(;;)
  {
    cout<<"请输入3~8之间的数，代表3~8题,0表示程序结束"<<endl;
    cin>>s;
    if(s==0) return 0;
    switch(s)
    {
    case 3:
      cout<<"请输入需要加入的数的个数:"<<endl;
      int n;
      cin>>n;
      cout<<"请输入需要加入的数:"<<endl;
      for(int i=1;i<=n;i++)
      {
        int t;
        cin>>t;
        InputList(L,t); 
      }
      break;
    case 4:
      OutputList(L);
      cout<<endl;
      break;
    case 5:
      for(int i=1;i<=2;i++)
      {
        cout<<"请输入插入的位置和插入的数是什么:"<<endl;
        int a,b;
        cin>>a>>b;
        ListInsert(L,a,b);
      }
      break;
    case 6:
      cout<<"请输入需要删除哪个位置的数:"<<endl;
      for(int i=1;i<=2;i++)
      {
        int aa;
        cin>>aa;
        ListDelete(L,aa);
      }
      break;  
    case 7:
      cout<<"请输入需要取出哪个位置的数:"<<endl;
      for(int i=1;i<=2;i++)
      {
        int a;
        cin>>a;
        GetElem(L,a,e);
        cout<<"第"<<a<<"个位置的数的值为:"<<e<<endl;
      }
      break;
    case 8:
      if (ClearList(L)) cout << "置空成功" << endl;
      else cout << "置空失败" << endl;
      break;
    }
  }
 }

🚌小细节：什么时候使用引用，什么时候不使用引用

观察代码我们会发现，

有的是SqList L（没有使用引用）

有的是SqList &L（使用了引用）

这是为什么呢

原因：我们发现，使用引用的代码段里面都会有分配空间的操作，而没有使用引用的代码段里面就没有分配空间的操作

分配一段空间，使整个程序改变了，所以要使用引用，而如果不分配空间，那么就直接使用就行了，不需要引用

😎完整代码2

#include<iostream>
using namespace std;
#define OK 1
#define overflow -1
int k = 1;
typedef struct {
  int* elem;
  int length;
}SqList;
int InitList(SqList* L)
{
  L->elem = new int[100];
  if (!L->elem) exit(overflow);
  L->length = 0;
  return OK;
}
//3
void InputList(SqList* L, int n)
{
  L->elem[k++] = n;
  L->length++;
}
//4
void OutputList(SqList* L)
{
  for (int i = 1; i <= L->length; i++)
  {
    cout << L->elem[i] << " ";
  }
}
//5
void ListInsert(SqList *L, int place, int num)
{
  L->length++;
  for (int i = L->length; i >= place; i--)
  {
    L->elem[i + 1] = L->elem[i];
  }
  L->elem[place] = num;
}
//6   
void ListDelete(SqList *L, int place)
{
  for (int i = place; i <= L->length; i++)
  {
    L->elem[i - 1] = L->elem[i];
  }
  L->length--;
}
//7
int GetElem(SqList L, int i, int& e)
{
  if ((i < 1) || (i > L.length)) return -1;
  e = L.elem[i];
  return OK;
}
//8
int ClearList(SqList *L)
{
  L->length=0;
    return 1;
}
int main()
{
  SqList L;
  int s, e;
  InitList(&L);
  if (InitList) cout << "成功" << endl;
  else cout << "失败" << endl;
  cout << "0:退出程序" << endl;
  cout << "3:加入数" << endl;
  cout << "4:输出线性表里面的数" << endl;
  cout << "5:插入数" << endl;
  cout << "6:删除数" << endl;
  cout << "7:取出某个位置的数" << endl;
  cout << "8:置空" << endl;
  cout << endl;
  for (;;)
  {
    cout << "请输入3~8之间的数，代表3~8题,0表示程序结束" << endl;
    cin >> s;
    if (s == 0) return 0;
    switch (s)
    {
    case 3:
      cout << "请输入需要加入的数的个数:" << endl;
      int n;
      cin >> n;
      cout << "请输入需要加入的数:" << endl;
      for (int i = 1; i <= n; i++)
      {
        int t;
        cin >> t;
        InputList(&L, t);
      }
      break;
    case 4:
      OutputList(&L);
      cout << endl;
      break;
    case 5:
      for (int i = 1; i <= 2; i++)
      {
        cout << "请输入插入的位置和插入的数是什么:" << endl;
        int a, b;
        cin >> a >> b;
        ListInsert(&L, a, b);
      }
      break;
    case 6:
      cout << "请输入需要删除哪个位置的数:" << endl;
      for (int i = 1; i <= 2; i++)
      {
        int aa;
        cin >> aa;
        ListDelete(&L, aa);
      }
      break;
    case 7:
      cout << "请输入需要取出哪个位置的数:" << endl;
      for (int i = 1; i <= 2; i++)
      {
        int a;
        cin >> a;
        GetElem(L, a, e);
        cout << "第" << a << "个位置的数的值为:" << e << endl;
      }
      break;
    case 8:
      if (ClearList(&L)) cout << "置空成功" << endl;
      else cout << "置空失败" << endl;
      break;
    }
  }
}

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

⭐定义：

⭐ 理解：

⭐存储方式：

⭐顺序存储的优缺点：

⭐链式存储的优缺点：

⭐基本操作

🎈添加数字建立表

🎈输出线性表里面的数

🎈插入数字

🎈删除数字

🎈取出数字

🎈置空

😎完整代码1

😎完整代码2

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

⭐定义：

⭐ 理解：

⭐存储方式 ：

⭐顺序存储的优缺点：

⭐链式存储的优缺点：

⭐基本操作

🎈添加数字建立表

🎈输出线性表里面的数

🎈插入数字

🎈删除数字

🎈取出数字

🎈置空

😎完整代码1

😎完整代码2

热门文章

最新文章

相关课程

相关电子书

⭐存储方式：