【这就是数据结构】用个“小栗子”来说一说线性表的插入操作

线性表

线性表是最基本、最简单、也是最常用的一种数据结构。我们可以把它理解为“线性排列的数据表”。

线性排列就是按照线性关系排列，线性关系指的是数据一个挨着一个，总体呈线性分布。就像我们在餐厅排队打饭时所排的队伍一样，除了队首和队尾的两个人，每一个人前后都有一个人，这些人之间的分布关系就可以称为线性关系。数据在逻辑结构上如果呈这样的关系分布，数据的存储结构就是线性表。

线性表有详细的分类，比如顺序表、链表，链表中又有单链表、双向链表，单链表和双向链表中又有循环链表。

本次内容我们就通过一个“小栗子”来理解一下顺序表和单链表。

顺序表

顺序表可以简单理解为我们之前学习过的数组（顺序表是从数组下标为1的元素位置开始存储数据的），只不过我们之前在学习数组时没有涉及到的元素的插入和删除操作会在顺序表中学习。

因为数组是元素的集合，所以顺序表也就是元素的集合，比如我们要把一个升序数列1 2 4 5 6存储到顺序表中，那么它的存储形式应该如下：

通过上图我们可以看到数据在顺序表中逻辑关系上的位置和存储上的物理位置是一致的，即逻辑上的第1个数就存在a[1]的位置，逻辑上的第2个数就存在a[2]的位置……逻辑上第5个数就存在a[5]的位置。

单链表

链表可以理解为是结点的集合，结点可以理解为是链表的元素，和数组中的元素不同的是：数组中一个元素里就只有一个数据；而链表中一个结点需要包含多个数据，比如单链表中一个结点就需要包含数值和指针两个数据。（我们把存放数值信息的区域叫做数据域，把存放指针信息的区域叫做指针域）其中指针的作用就是指示逻辑关系上的下一个数字所在结点的地址。如果我们要用单链表存放升序数列1 2 4 5 6的话，那么存放数字2的这个结点里的指针数据就是存放数字4的结点的地址。（在真正的链表中这个地址是内存空间的物理地址，在模拟链表中，这个地址其实就是结点的次序，即第几个结点。至于什么是真正的链表，什么是模拟链表，我们下面再说）

由于链表结点中指针域的存在，所以链表在存放数据时逻辑位置上相邻的两个数字可以存放在物理位置不相邻的两个结点中，比如升序数列1 2 4 5 6中的数字2如果放在第2个结点中，数字4不仅可以存放在第3个结点中还可以存放在链表的其它任意一个结点中，只需要用第2个结点中的指针信息指向数字4所在的结点位置就可以了。

真正的链表中，我们可以用结构体变量来表示结点，比如我们可以用包含两个成员的结构体变量来表示一个单链表的结点，其中一个成员来存放具体数值（比如我们的整型变量），另一个成员存放逻辑上下一个数值所在的结点物理地址（用指针实现），因为我们在信奥中没有具体学习指针，所以此种类型的链表我们不作重点讲解。

我们重点来讲解使用数组实现链表的方式。比如我们定义两个数组：一个value[  ]数组，一个next[  ]数组，我们用value[  ]数组来存放每个节点中的数值信息，用next[  ]数组来存放每个结点中的地址信息（用这种方式表示链表时，地址其实就是逻辑上下个结点的次序），即value[1]和next[1]共同构成结点1，value[2]和next[2]共同构成结点2……我们把这种用数组实现链表的方式可以叫做模拟链表。

根据链表的特点，我们用模拟链表存放升序数列1 2 4 5 6的存放形式可以是这样的：

可以是这样的：

还可以是这样的：

当然还可以是其它样式的，因为有指针域的指向，所以不管数列在链表中怎么存放，我们都可以从存放数值1的结点出发，沿着各结点指针域的指向依次找到升序数列1 2 4 5 6中的各个数值。

那么还有个问题：我们怎么才能知道数值1在哪个结点里呢？定义一个变量存放这个结点的位置不就完美解决了！我们还给这个变量起了一个名字：叫做头结点。

先看简化版

已知一个升序数列：1 2 4 5 6，现插入一个数字num（num=3）进去，要求得到的新数列仍是从小到大的升序数列；编程实现插入操作，输出最后得到的新数列。

输入：两行；

          第一行为现有的升序数列1 2 4 5 6；

          第二行为要插入的数字3;

输出：一行；为最后得到的新数列。

顺序表解题思路：

1.把现有升序数列存入数组a[ ];

2.把4 5 6向后移动一位存放;

3.把num=3存入空出来的a[3]位置；

顺序表参考代码：

#include<iostream>using namespace std;int a[100];int main(){  int n=5; int num=3;  for(int i=1;i<=n;i++) cin>>a[i];//把现有的升序数列存入顺序表 
for(int i=n;i>=3;i--) a[i+1]=a[i];//元素移位，注意要从最后一个开始移动
a[3]=num;//插入 n++;//插入后，数列长度增加 1
for(int i=1;i<=n;i++) cout<<a[i]<<' ';//输出得到的新数列 return 0;}

单链表解题思路：

1.把现有的升序数列存入链表

2.在链表最后增加一个结点，链表长度增加 1，在最后一个结点存储要插入的数值并设置好对应结点的指针指向。

单链表参考代码：

#include<iostream>using namespace std;int value[100],next[100];int main(){  int n=5;  int num=3;  for(int i=1;i<=n;i++)//把现有的升序数列存入单链表   {    cin>>value[i];    if(i!=n) next[i]=i+1;    else next[i]=0;  }
  n++;//在链表最后增加一个结点，链表长度增加 1
  value[n]=num;//在最后一个结点存储插入的数值   next[2]=n;//设置好最后一个结点的指针指向   next[n]=3;
  int i=1;//输出链表中的新数列，定义变量i存储数列中第一个数值所在的结点地址，i此时即为头结点   while(i!=0)  {    cout<<value[i]<<' ';    i=next[i];//寻找后续结点的位置   }  return 0;}

再看正式版

在一个长度为n（n<100）的升序数列中插入一个数字num进去，要求得到的新数列仍是从小到大的升序数列；编程实现插入操作并输出最后得到的新数列。

输入：三行；

          第一行为n；

          第二行为一个长度为n的升序数列；

          第三行为要插入的数字num;

输出：一行；为最后得到的新数列。

样例输入1：

样例输出1：

样例输入2：

样例输出2：

样例输入3：

样例输出3：

顺序表解题思路：

与简化版例子不同的是，在这个例子中，数列长度n和要插入的数值num都是未知的，所以要想插入num后还是一个升序数列，我们需要查找num应该插入的位置。所以解题思路为：

1.把输入的升序数列存入数组a[ ]；

2.根据输入的数值num从顺序表的开头开始查找其应插入的位置；

情况①：在原始数列中找到了第一个大于等于num的元素a[i],那么把num插入到a[i]之前即可保证得到的还是一个升序数列。

情况②：在原始数列中没有找到大于等于num的元素a[i]，那么此时我们就可以直接把num插入到顺序表的最后，得到的就是一个新的升序数列。

顺序表参考代码：

#include<iostream>using namespace std;int a[100];int main(){  int n,num; cin>>n; for(int i=1;i<=n;i++) cin>>a[i];//输入一个长度为n的升序数列 cin>>num;//输入要插入的数字 //在原始数列中从第一个元素开始检查，如果能找到第一个比num大或等于num的数，把num插入到这个数之前 int w=0;//定义变量存储位置,初始化为 0可以在之后用作判断 for(int i=1;i<=n;i++)//从顺序表中的第一个元素开始检查，查找第一个比num大或等于num的数的位置w { if(a[i]>=num)//如果找到了 { w=i;//记录位置 break; } } n++;//数列长度增加 1 if(w==0) a[n]=num;//如果循环结束w还为0，说明原始数列中没有一个元素是大于或等于num的，那么直接把num放在原始数列的最后就可得到一个新的升序数列 else { for(int i=n;i>=w;i--) a[i+1]=a[i];//第w个元素以后的元素都要往后移一位 a[w]=num;//插入num } for(int i=1;i<=n;i++) cout<<a[i]<<' ';//输出得到的新数列 return 0;}

单链表解题思路：

因为在这个例子中，数列长度n和要插入的数值num都是未知的，所以要想插入num后还是一个升序数列，我们需要查找num应该插入的位置。所以解题思路为：

1.把输入的升序数列存入链表；

2.在链表末位增加一个结点，把输入的数值num直接存放在这个结点的数据域中；

3.从链表的头结点开始查找哪个结点数据域中存放的数值在逻辑关系上是第一个小于等于num的，记录这个结点的位置，然后改变对应结点指针的指向。

情况①：在原始链表中找到了第一个数据域数值大于等于num的结点i,设置结点i-1和结点n(即num所在的最后一个结点)的指针指向即可。

情况②：在原始链表中没有找到了数据域数值大于等于num的结点，那么结点n就应是逻辑上的最后一个结点，此时直接设置结点n-1和结点n的指针指向即可。

单链表参考代码：

#include<iostream>using namespace std;int value[100],next[100];int main(){  int n,num;  cin>>n;   for(int i=1;i<=n;i++)//把一个长度为n的升序数列存入单链表   {    cin>>value[i];//输入数据域     if(i!=n) next[i]=i+1;//设置指针域     else next[i]=0;//最后一个结点指针域为空   }
  cin>>num;//输入要插入的数值   n++;//链表增加一个结点，长度增加 1   value[n]=num;//把数值num存放到最后一个结点n的数据域   //从头结点开始检查链表，寻找num所在的结点n逻辑位置上应在哪个结点之前，找到这个结点w   int w=0;//结点w初始化为0，后面可用作判断
  /*   for(int i=1;i<=n;i++)//现在前n-1结点的物理位置和逻辑关系位置还是统一的，这样查找也是没有问题的   {                      //这种查找方法只适用于结点物理位置和逻辑关系位置统一的链表                    if(value[i]>=num)    //后面还有一个任何单链表都适用的查找方法，注意观察理解     {      w=i;//num应该插入到第w个结点之前,因为n是长度增加过以后的n，所以肯定能找到w       break;    }  }  */
  //从下一行开始是任何单链表都适用的查找方法，注意观察理解   int i=1;//从头结点开始找到逻辑上的第一个结点，然后开始检查，寻找第一个数据域中数值大于等于num的结点w，找到后num所在的结点逻辑上应该插入到结点w之前   while(i!=0)  {    if(value[i]>=num)//如果在原始数列所在的链表中找到了结点w     {      w=i;//记录结点位置       break;    }    i=next[i];//把下一个结点的位置给i   }  if(w==0) w=n;//循环结束w还等于0说明在原始数列所在的链表中没有找到结点w，证明num比原始数列中的数都大，num所在结点的逻辑位置就是最后一个结点，与现在的物理位置相同
  next[n]=next[w-1];  next[w-1]=n;//这两行就是我们通过改变指针域指向实现插入的过程，注意理解
  int j=1;//输出链表中的新数列，从头结点找到逻辑上的第一个结点，然后开始依次输出   while(j!=0)  {    cout<<value[j]<<' ';    j=next[j];//把下一个结点的位置给j   }  return 0;}