正文

线性表

在讲单链表之前，我们先来了解一下单链表的前生，线性表。

线性表的结构

线性表的数据元素可以是各式各样的，但是在同一线性表的元素必须是同一类型，并且相邻的元素存在序偶关系。

线性表又四个特点

若将线性表记为：

（a1,a2,a3,....ai...an）

(1)存在着唯一一个被称为“第一个”的数据元素

(2)存在着唯一一个被称为“最后一个”的数据元素

(3)除了第一个外，集合中的每一个数据元素，有且仅有一个前驱元素

(4)除了最后一个外，集合中的每一个数据元素，有且仅有一个后继元素

（1,5,7,2,4）

这就是一个线性表，现在我们要解决的问题是：

（1）数据要保存

1 5 7 2 4

（2）关系要保存

“逻辑关系”

方法一：要完成以上两个要求，我们用简单的数组就可以完成啦。

int a[] = {1,5,7,2,4}；
int a[0] = 1,a[1] = 5,a[2] = 7,a[3] = 2,a[4] = 4;

存储结构的前后关系，是不是刚刚好可以描述我们的逻辑关系.

而使用数组的话，是不是地址在前的，逻辑关系也在前，刚好满足了我们的两个要求，这样看来，数组简直完美契合呀。不过问题来了，逻辑关系一点要用连续的地址来表示吗，显然完美还能使用指针来描述。

方法2：

存储结构地址不连续

在存储数据的同时，要额外开辟一个指针空间，存逻辑上的下一个元素的地址

线性表结构的实现

线性表又两种结构

一种是我们刚刚使用的数组，也就是“顺序结构”

线性表的顺序结构是指用一组地址连续的存储单元，依次存储线性表的数据元素。

在这种情况下，数据保存啦，数据元素之间的逻辑关系也保存啦

用物理地址的关系来保存逻辑关系

另外一种就是我们要将的重点，也是我们刚刚提出来的 “链式结构”，即链表

保存数据元素时，不需要用地址连续的空间

数据元素的存储单元是不连续的

但是要保存数据元素的同时，额外开辟一个指针空间，来保存它逻辑上的

“下一个”或“上一个”或两者之间都有的元素地址

单链表

回到之前的那个问题，我们使用链表来完成那两个要求（数据要保存，关系要保存），代码是

typedef struct node 
{
  int data;
  struct node *next;
}Node;
int main()
{
  Node a,b,c,d,e,f;
  a.data = 1;a.next = &b;
  b.data = 5;b.next = &c;
  c.data = 7;c.next = &d;
    d.data = 2;d.next = &e;
  e.data = 4;e.next = NULL;
  Node *p = &a;
  while(p)
  {
    printf("%d ",p->data);
    p = p->next;
  }
  printf("\n");
}

输出结构就是 “1 5 7 2 4”,这样一来，也完成了要求。

但问题是，再实际使用中，我们要存储的数据远不止如此，这样输入就显得有些呆板了，所以我们引进新方法，动态分布空间。

动态创建链表结点

在创建节点之前，我们还得先构造一个数据类型把上面的这些数据都存储。

typedef int u4;
typedef struct node 
{
  u4 data;
  struct node *next;
}Node;

int d;
scanf("%d", &d);
Node *p = malloc(sizeof(*p));
p->data = d;
p->next = NULL;//等下一个数据

这样，一个链表节点就创建成功啦。这些准备工作做完后，我们接下来要做的是创建一个单链表啦

创建一个单链表

思路（重点）

step1:每获得一个数据我就创建一个数据结点

step2: 把获得的数据写入到数据结点去

step3:把写入好的数据结点加入到链表中去

3.1:从无到有

3.2:从少到多

这个思路很重要，不管是创建单链表还是之后带头节点的单链表，还是做相关的题目，有了这个思路，就会又很清晰的逻辑了。接下来我将一步一步的解析

step1:每获得一个数据我就创建一个数据结点

实现创建一个链表的相关要素

u4 d;             //定义一个获取输入的数据的变量
Node *pnew = NULL;//指向新创建的结点
Node *head = NULL;//指向链表的首结点
Node *tail = NULL;//指向链表的尾结点

然后获取数据后创建节点

scanf("%d",&d);  //获取一个数据，就创建一个节点
if(d == 0)
  break;          //我们约定输入0结束输入
pnew = malloc (sizeof(*pnew));    //给节点分配空间

step2: 把获得的数据写入到数据结点去

pnew->data = d;
pnew->next = NULL;    //一定要定义为NULL，否则将成为野指针

step3:把写入好的数据结点加入到链表中去

3.1:从无到有

if(head == NULL)//从无到有
{
  head = pnew;
  tail = pnew;
}

3.2:从少到多

除插入第一个节点外，插入其他地方我们又两种插法，尾插法与头插法

/*尾插法代码*/
else
{
  tail->next = pnew;//tail指向新结点
  tail = pnew;//tail被pnew取代 
}
/*头插法代码*/
else
{
  pnew->next = head;
  head = pnew;//保证head指向第一个
}

这样，我们的单链表就创建成功啦，整体函数为

Node *create_list(void)
{
  u4 d;
  Node *pnew = NULL;    //指向新创建的节点
  Node *head = NULL;    //指向链表的头节点
  Node *tail = NULL;    //指向链表的尾节点
  while(1)
  {
    scanf("%d",&d);   //获取一个数据，就创建一个节点
    if(d == 0)
      break;
    pnew = malloc (sizeof(*pnew));
    pnew->data = d;
    pnew->next = NULL;
    if(head == NULL)    //尾插法
    {
      head = pnew;
      tail = pnew;
    }
    else
    {
      tail->next = pnew;  //tail指向新节点,即上一个节点指向新节点
      tail = pnew;    //pnew 取代tail，即重新将tail指向最后的节点
    }
  }
  //tail->next = head->next;    //将单链表变成环链表
  return head;
}

单链表的增删改毁

增加节点

实现，在链表中找到值为x的结点，在它的前面加入一个值为a的结点，若没有找到，则插到最后，将新链表返回。

添加结点：

算法思路：

1.遍历找到插入的位置

2.插入操作（分情况）

插头

pnew->next = head;
head = pnew;

插尾（没找到）

1.本身就是空链表

head = pnew;

2.本身不是空链表

pre->next = pnew;

插中间

pre->next = pnew;
pnew->next = p;

整体代码为

Node *add_a_node(Node *h,u4 x,u4 a)
{
  Node *p = NULL;//遍历指针
  Node *pre = NULL;//指向P指向节点的前一个节点
  Node *pnew = NULL;//指向新创建的节点
  pnew = malloc(sizeof(*pnew));
  pnew->data = a;
  pnew->next = NULL;
  p = h;
  while(p)
  {
    if(p->data == x)    //找到数值了，就退出
    {
      break;
    }
    pre = p;
    p = p->next;
  }
  if(p != NULL)    //意思是找到了，而非找到最后也没找到
  {
    if(p == h)    //是第一个节点
    {
      pnew->next = h;
      h = pnew;
    }
    else           //是中间节点
    {
      pre->next = pnew;
      pnew->next = p;
    }
  }
  else        //没找到
  {
    if(h == NULL)       //空链表
    {
      h = pnew;
    }
    else                //非空链表
    {
      pre->next = pnew;
    }
  }
  return h;
}

删除节点

删除结点的算法思路：

1.遍历查找要删除的节点的位置

2.删除

1.px == head;//要删除的是第一个结点

head = head->next;
px->next = NULL;
free(px);
px = head;

2.//删除的是中间结点或者最后一个结点

pr->next = px->next;
px->next = NULL;
free(px);
px = pr->next;

完整代码：

List *delete_a_list(List *list,u4 x)
{
  Node *p = list->first;
  Node *pre = NULL;
  while(p)
  {
    if(p->data == x)
    {
      if(p == list->first)
      {
        list->first = list->first->next;
        p->next = NULL;
        free(p);
        p = list->first;
      }
      else if(p->next == NULL)
      {
        list->last = pre;
        pre->next = NULL;
        free(p);
        p = NULL;
      }
      else
      {
        pre->next = p->next;
        p->next = NULL;
        free(p);
        p = pre->next;
      }
      list->NodeNum--;
    }
    else
    {
      pre = p;
      p = p->next;
    }
  }
  return list;
}

修改节点的值

这个相对来说，就简单许多，只需要遍历到要修改的节点，然后将值改变即可。我们就直接上代码吧

销毁链表

void destory_list(List *list)
{
  Node *p = list->first;
  while(p)
  {
    list->first = list->first->next;
    p->next = NULL;
    free(p);
    p = list->first;
  }
  list->last = NULL;
  list->NodeNum = 0;
  free(list);
}

总结

线性表的这些知识都属于基础部分，不过使用以及足够，但是想进入大厂的话，还远远不够，下一篇文章，笔者将总结大厂面试题中最常见的链表题。

数据结构之单链表一生的历程（创建一个线性表，动态分布空间，单链表创建的思路，单链表的增、删、改、毁）

目录

正文

线性表