链表的概念、建立、删除与插入

我们知道，数组式计算机根据事先定义好的数组类型与长度自动为其分配一连续的存储单元，相同数组的位置和距离都是固定的，也就是说，任何一个数组元素的地址都可一个简单的公式计算出来，因此这种结构可以有效的对数组元素进行随机访问。

但若对数组元素进行插入和删除操作，则会引起大量数据的移动，从而使简单的数据处理变得非常复杂，低效。

为了能有效地解决这些问题，一种称为“链表”的数据结构得到了广泛应用。

什么是链表：

链表是一种动态数据结构，他的特点是用一组任意的存储单元（可以是连续的，也可以是不连续的）存放数据元素。

链表中每一个元素成为 “结点” ，每一个结点都是由数据域和指针域组成的， 每个结点中的指针域指向下一个结点。

Head 是 “头指针” ，表示链表的开始，用来指向第一个结点，而最后一个指针的指针域为 NULL( 空地址 ) ，表示链表的结束。

可以看出链表结构必须利用指针才能实现，即一个结点中必须包含一个指针变量，用来存放下一个结点的地址。实际上，链表中的每个结点可以用若干个数据和若干个指针。

结点中只有一个指针的链表称为单链表，这是最简单的链表结构。

在 c++ 中实现一个单链表结构比较简单。例如，可定义单链表结构的最简单形式如下

//定义的结构体
 struct LinkNode{
    int Data;
    struct LinkNode *Next;
};

这里用到了结构体类型。其中， *Next 是指针域，用来指向该结点的下一个结点； Data 是一个整形变量，用来存放结点中的数据。当然， Data 可以是任何数据类型，包括结构体类型或类类型，结构中也可以包含多个数据域，而且有且可以包含两个指针域，包含两个指针域的叫做双向链表。

链表有很多种不同的类型：单向链表，双向链表以及双向循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

链表的创建、输出步骤。单链表的创建过程有以下几步：

1 ) 定义链表的数据结构,结构的好处是能存储不同数据类型的数据;

2 ) 创建一个空表;

3 ) 利用malloc ( )函数向系统申请分配一个节点;

4 ) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾;

5 ) 判断一下是否有后续节点要接入链表，若有转到3 )，否则结束;

见实例：

定义的结构体
 struct LinkNode{
    int Data;
    struct LinkNode *Next;
};


 typedef LinkNode Node;

定义节点及节点的类型为结构体类型

建立单链表
 Node *CreateLinkTable(void){
     Node *Head, *A, *B;
     Head = NULL;

定义一个头节点，假设它是空的，说明这是个空链表

下面给空链表添加节点
     A = B  = (Node*)malloc(sizeof(Node));

利用malloc()函数向系统内存申请分配一个节点内存空间。    
     printf("请输入一个整数：");
     scanf_s("%d", &A->Data, sizeof(A->Data));

给节点A的数据域输入数据
     if (Head == NULL){
         Head = A;

如果是空链表，让 Head 节点指向新节点A，做头节点。A的指针域指向下一节点所在的位置         
     }

     A = (Node*)malloc(sizeof(Node));

 A 继续开辟新的节点空间
     printf("请输入一个整数：");
     scanf_s("%d", &A->Data, sizeof(A->Data));

 给新开辟的节点A的数据域输入数据
     B->Next =A;

B 的下一节点指针指向新节点 A
     B = A;

旧节点 B 再指向新的节点 A


     A = (Node*)malloc(sizeof(Node));

 A 继续开辟新的节点空间
     printf("请输入一个整数：");
     scanf_s("%d", &A->Data, sizeof(A->Data));

给新开辟的节点A的数据域输入数据
     B->Next = A;

B 的下一节点指针指向新节点 A
     A->Next = NULL;
     B = A;

新的变成旧节点 B 再指向新的节点 A


     return Head;

 把头节点返回
 }

单链表的输出过程有以下几步：

1) 找到表头;

2) 若是非空表，输出节点的值成员，是空表则退出;

3 ) 跟踪链表的增长，即找到下一个节点的地址;

4) 转到2 ).

void print(Node *head){     //参数为链表返回的头节点
     Node *Temp = head;      //设置一个节点指针指向头节点，
     while (Temp != NULL){   //如果这个头节点不为空，那就开始输出一个节点的信息
         printf("Temp=%d,  Temp->Data=%d,  Temp->Next=%d 
", Temp, Temp->Data, Temp->Next);
         printf("
");
         Temp = Temp->Next;  //指针沿着 Next指针域指向下一个节点再输出
     }
 }

下面在源文件中进行调用输出：

int _tmain(int argc, _TCHAR* argv[])
{
    print(CreateLinkTable());

    system("Pause");
    return 0;
}

如图：

工作原理流程如下图：

单链表的节点删除：

想要删除链表中的某个节点，就需要借助两个临时的节点指针：

如：p1、p2

p1：用来判断指向的节点是不是要删除的节点（用于寻找）；

p2: 用来暂存指向p1的前驱结点指针地址。

示意图：

代码如下：

Node *DeleteNode(Node *Head, int Data){
     Node *p1, *p2;  //定义两个临时节点来辅助对节点的删除
     p1 = p2 = (Node*)malloc(sizeof(Node));
     if (Head == NULL){
         printf("这是个空链表"); goto a;
     }
     else{
         p1 = Head;
         while (Data!=p1->Data && p1->Next!=NULL){
             p2 = p1; p1 = p1->Next;     //前驱地址保存在p2里面，p1往下跳到后继地址继续找
         }
         if (Data == p1->Data){     //找到了
             if (p1 == Head){      //判断找到的是不是头节点
                 Head = p1->Next;  //如果是，就不头节点的下一个地址作为头节点的指向（也就是P1->Next指向的地址)
                 printf("删除指定的节点成功");
             }
             else{       //如果不是，就把找到的地址的下一个地址（p1->Next)和临时保存的（前驱地址p2->Next）链接起来（赋值）
                 p2->Next = p1->Next;
                 printf("删除指定的节点成功");
             }
         }
         else{
             printf("没有找到指定的节点");
         }
     }
 a:     return Head;
 }

现在在源文件进行调用：

int _tmain(int argc, _TCHAR* argv[])
{

    int wf;

    Node *temp = CreateLinkTable();

    printf("请输入要删的的数据：");
    scanf_s("%d", &wf, sizeof(&wf));
    DeleteNode(temp,wf);
    system("Pause");
    return 0;
}

结果如图：

单链表节点的插入：

向链表中插入节点：将一个节点插入到已有的链表中。

插入原则：

1、插入的操作不应破坏原链接表的关系。

2、插入的节点应该在它该在的位置。

实现方法：应该有一条查找可插入点位置的语句。

这时会出现三种情况：

1、待插入节点可能比链表中的节点都要小；

2、待插入节点可能比链表中的节点都要大；

3、待插入节点可能刚好能成为链表的中间节点。

不巧，同删除方法基本相同，需要几个临时节点指针：我们用三个来进行比较，p0、p1、p2。

p0：用来表示待插入的节点；

p1：用来表示将要在p1之前（p1的前驱）进行插入p0；

p2：用来临时保存前驱节点的指针，好让p1进行下跳后，也不至于丢失了前驱的地址而导致断链！

如：已有一个链表，它是按节点中的整数域从大到小的顺序排列的，现在要向里面插入一个节点，该节点的整数为50。

代码如下：

在顺序链表中插入某个节点：  
 Node *Insert(Node *Head, Node *DNode){

参数1为链表的头节点，参数2为待插入的节点
     Node *p0, *p1, *p2;      
     p0 = p1 = p2 = (Node*)malloc(sizeof(Node));
     p0 = DNode; p1 = Head; 
     if (p0 ->Data<p1->Data||Head==NULL){   
         if (Head == NULL){

如果是空链表，            
             Head = p0;

就把p0作为链表的新头节点
             p0->Next = NULL;

再把p0的指向下一节点的指针设为空标志链表到此结束
             return Head;

返回新的头节点
         }
         else{
             p0->Next = p1;

如果不为空，就把p1插入最前面，
             Head=p0;

把p0作为链表的新头节点
         }
         return Head;

返回新的头节点
     }

注意，当头节点被改变时，一定要重新指明哪个为新的头节点，因为返回是要返回它头节点的
     else{
         while (p0->Data>p1->Data&&p1->Next!=NULL){

如果上面的条件都不成立，那就在链表的中间找
             p2 = p1; p1 = p1->Next;

//p1每跳一步，就把p1给p2进行暂时保存，p1继续偏移查找

//当上面的条件不成立，那只有两种情况，1、在链表的中间找到比p1小的；2

、链表的中间节点都比p0小。
         if (p0->Data < p1->Data){

如果在链表的中间找到比p1小的
             p2->Next = p0;

就把p2暂存的前驱指向这个要插入的节点p0
             p0->Next = p1;

然后把这个要插入的节点p0指向比p0大的p1。
         }

向中间插入成功！
         else{

 链表的中间节点都比p0小,那p0就是最大的，因为While语句在链表中找了一圈，也没找到比待插入节点小的
             p1->Next = p0;

把p0插入到最后
             p0->Next = NULL;

把p0的指针赋值为空，表示链表到此结束
         }

注意：不管我是插入在中间，还是插入到最后，都没改变头节点，所以不用更新头节点。
         return Head;
     }
     
 }

然后，在源文件进行调用：

int _tmain(int argc, _TCHAR* argv[])
{
  
    Node *dNode=(Node*)malloc(sizeof(Node));

待插入的节点   
    Node *temp = CreateLinkTable();

给链表赋值后把返回的头节点赋给缓存节点
    printf("请输入要插入的节点的数据：");
    scanf_s("%d", &dNode->Data, sizeof(&dNode->Data));

给待插入的节点赋值
    temp = Insert(temp, dNode);

插入后，把链表的头节点返回给缓存节点，供我查看
    print(temp);

读取节点    

    system("Pause");
    return 0;
}

结果如图，向链表的中间插入节点：

向链表的最前面插入节点：

向链表的最后面插入节点：