vlambda博客
学习文章列表

1.链表概述

链表是一种常见的数据结构。它与常见的数组是不同的，使用数组时先要指定数组包含元素的个数，即为数组的长度，但是如果向这个数组中加入的元素超过了数组的大小时，便不能将内容全部保存。  链表这种存储方式，其元素个数是不受限定的，当进行添加元素的时候存储的个数就会随之改变。

链表一般有两种形式，有空头链表和无空头链表。

2.链表的基本使用

2.0 准备工作

使用链表时，首先应包含一些基本的头文件，因为涉及到内存的操作和字符串的操作。

#include "stdio.h"    
#include "stdlib.h"    //提供malloc()和free()
#include "string.h"    //提供strcpy()等

malloc函数

其函数原型如下：

void *malloc(unsigned int size);

这个函数返回的是个void类型指针，所以在使用时应注意强制类型转换成需要的指针类型。

free函数

其函数原型如下：

void free(void *p);

这个函数是用来释放指针p作指向的内存区。

2.1 创建节点（结构体）

struct Node
{
 int a;    //数据域
 struct Node* next; //指针域(指向节点的指针）
};

2.2 全局定义链表头尾指针 方便调用

struct Node* head= NULL;
struct Node* end = NULL;

2.3 创建链表,实现在链表中增加一个数据（尾添加）————增

void AddListTill(int a )
{
  //创建一个节点
  struct Node* temp=(struct Node*)malloc(sizeof(struct Node));  //此处注意强制类型转换

  //节点数据进行赋值
  temp->a=a;
  temp->next=NULL;  
  
  //连接分两种情况1.一个节点都没有2.已经有节点了，添加到尾巴上
  if(NULL==head)
  { 

   head=temp;
  // end=temp;
  }
  else
  {
  end->next=temp;
 // end=temp;   //尾结点应该始终指向最后一个
  }
  end=temp;   //尾结点应该始终指向最后一个
}

AddListTill函数的功能是尾添加的方式在链表的尾部增加一个节点，其中输入的参数是这个节点的数据。首先创建一个节点并申请一个节点的内存，之后对传入节点的数据进行赋值，注意尾添加的新节点的指针应指向空；此时分两种情况，1是链表中一个节点都没有，那么这个节点既是头结点也是尾结点；2是已经有节点，那么新添加的节点将成为最后一个节点，而之前的节点因为成为了倒数第二个节点了所以它的指针应该指向新添加的节点，之后全局变量尾结点应该指向现在的节点（注意操作的先后顺序不能变）。

2.4 遍历链表 —————查

void ScanList()
{
 struct Node *temp =head;  //定义一个临时变量来指向头
 while (temp !=NULL)
 {
  printf("%d\n",temp->a);
  temp = temp->next;  //temp指向下一个的地址 即实现++操作
 }

}

ScanList函数的功能是遍历这个链表，首先定义一个用于遍历的临时指针，用while循环实现遍历输出等操作。

2.5 查询指定的节点 （遍历 一个个找）

struct Node* FindNode(int a )
{
 struct Node *temp =head;
 while(temp !=NULL)
 {
 if(a == temp->a)
 {
  return temp;
 }
 temp = temp->next;
 }
 //没找到
  return NULL;
} 

FindNode函数的功能仍然是遍历链表，只不过会对每个节点中的数据进行一一判断，若找到则返回该节点，若没找到则返回NULL。

2.6 链表清空——————全部删除

void FreeList()
{
 //一个一个NULL
 struct Node *temp =head;  //定义一个临时变量来指向头
 while (temp !=NULL)
 {
 // printf("%d\n",temp->a);
  struct Node* pt =temp;
  temp = temp->next;  //temp指向下一个的地址 即实现++操作
  free(pt);     //释放当前
 }
 //头尾清空 不然下次的头就接着0x10
 head =NULL;
 end =NULL;
}

FreeList函数仍是采用遍历的方式一个一个的将节点内存释放，最后实现全部删除的效果，但是要注意在最后应该讲头尾节点至NULL否则下次的链表将会接着这次的头尾。

2.7.在指定位置插入节点 ————在指定位置增

void AddListRand(int index,int a)
{ 

    if (NULL==head)
 {
  printf("链表没有节点\n");
  return;
 } 
    struct Node* pt =FindNode(index);
 if(NULL==pt)    //没有此节点
 {
  printf("没有指定节点\n");
  return;
 }
    //有此节点
    //创建临时节点，申请内存
 struct Node* temp =(struct Node *)malloc(sizeof(struct Node));
 //节点成员进行赋值
 temp->a=a;
 temp->next=NULL;
 //连接到链表上 1.找到的节点在尾部 2.找到的节点在中间 
 if (pt == end)
 {
 //尾巴的下一个指向新插入的节点
 end->next=temp;
 //新的尾巴
 end=temp;
 }else
 {
 // 先连后面 （先将要插入的节点指针指向原来找到节点的下一个）
 temp->next=pt->next;
 //后连前面
 pt->next=temp;
 }

}

首先要知道在指定节点插入的过程就像手拉手得人在一条线，这时来了一个新人，他要求站在甲之后，首先要找到甲的位置，如果链表为空或者没有甲则无法插入，如果链表不为空并且甲在这个链表中，则还要看甲是在链表中间还是甲就在最后的尾巴上，如果在尾巴上则新插入的即为尾巴如图1，若在甲乙之间则需要先连上后面乙再连上前面的甲，如图2。

2.8尾删除————删

void DeleteListTail()
{ 
 if (NULL == end)
 {
  printf("链表为空，无需删除\n");
  return;
 }
 //链表不为空 
 //链表有一个节点
  if (head==end)
  {
   free(head);
   head=NULL;
   end=NULL; 
  }
  else
  {
  //找到尾巴前一个节点
   struct Node* temp =head;
   while (temp->next!=end)
   {
    temp = temp->next;
   }
   //找到了，删尾巴
  //释放尾巴
   free(end);
   //尾巴迁移
   end=temp;
   //尾巴指针为NULL
   end->next=NULL;
  }

}

尾删除的过程和前面一样首先应判断这个链表是不是为空或者只有一个节点，若只有一个节点则直接置NULL，若不为空，则先通过遍历找到倒数第二个节点，安徽将最后一个节点释放内存，再讲倒数第二个节点设置为end，然后将它的指针指向NULL。

2.9 删除头——————删

void DeleteListHead()
{ //记住旧头
 struct Node* temp=head;
 //链表检测 
 if (NULL==head)
 {
   printf("链表为空\n");
   return;
 }

 head=head->next;//头的第二个节点变成新的头
 free(temp);

}

先定义一个临时变量指向旧的头，将头的第二个记为新的头指针head，之后将旧的头释放

2.10 删除指定节点

void DeleteListRand(int a)
{

 //链表判断 是不是没有东西
 if(NULL==head)
 {
 printf("链表没东西\n");
 return;
 }
    //链表有东西，找这个节点
 struct Node* temp =FindNode(a);
 if(NULL==temp)
 {
 printf("查无此点\n");
 return;
 }
 //找到了,且只有一个节点
 if(head==end)
 {
 free(head);
 head=NULL;
 end=NULL;
 }
 else if(head->next==end) //有两个节点
 {
 //看是删除头还是删除尾
 if(end==temp)
  { DeleteListTail(); }
 else if(temp==head)
  { DeleteListHead(); } 
 }
 else//多个节点
 {
  //看是删除头还是删除尾
  if(end==temp)
   DeleteListTail();
  else if(temp==head)
   DeleteListHead(); 
  else //删除中间某个节点
  { //找要删除temp前一个，遍历
   struct Node*pt =head;
   while(pt->next!=temp)
   {
   pt=pt->next;
   }
   //找到了
   //让前一个直接连接后一个 跳过指定的即可
    pt->next=temp->next;
    free(temp);
  
  }
 }
 

}

情况与前面增加类似不再赘述，具体见图

3. 测试主程序

下面是测试用的主程序，主要实现了链表的增删查改等基本操作。

void main ()
{ 
 struct Node *pFind ;
 //创建5个节点
 for(i=0;i<6;i++)
 AddListTill(i);
 
// AddListRand(4,14);  //在指定位置4增加节点14
// DeleteListTail();  //删除一个尾结点
 DeleteListRand(4);  //删除4节点
 ScanList();    //便利输出链表
 FreeList();    //删除链表
/* pFind = FindNode(5); //查找5节点

 if (pFind !=  NULL)
 {
  printf("找到%d\n",pFind->a); //找到节点并且输出该节点数据
 }
 else
 {
  printf("No Find!\n");
 }

*/

}

有关无空头的单链表的基本操作就总结到这里，当然还有双链表等更复杂的数据结构，以及遍历和查找的优化算法也有待进一步探索与学习。