单向链表的实现--插入

一、线性表链式存储结构的特点用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素 ai 与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。这两部分信息组成数据元素ai 的存储映像，称为结点 (node)。它包括两个域：其中存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。n个结点(a,(ai(1 ≤ i ≤ n)的存储映像）链结成一个链表，即为线性表： (a1, a2，...., an) 的链式存储结构。又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。根据链表结点所含指针个数、指针指向和指针连接方式，可将链表分为单链表、循环链表、双向链表、二叉链表、十字链表、邻接表、邻接多重表等。其中单链表、循环链表和双向链表用于实现线性表的链式存储结构，其他形式多用于实现树和图等非线性结构。

下面就来实现单向链表，我们来做一个图书信息管理系统：

出版社有一些图书数据保存在一个文本文件 book.txt 中，为简单起见，在此假设每种图书只包括三部分信息：ISBN (书号）、书名和价格，文件中的部分数据如图 2.1 所示。现要求实现一个图书信息管理系统，包括以下6个具体功能。

(1) 插入：插入现有图书信息或插入新图书信息。

(2) 查找：根据指定的 ISBN 或书名查找相应图书的有关信息，并返回该图书在表中的位置序号。

(3) 删除：删除一种图书信息。

(4) 修改：根据指定的 ISBN, 修改该图书的价格。

(5) 排序：将图书按照价格由低到高进行排序。

(6) 计数：统计图书表中的图书数量。

现有图书信息如下：

ISBN 书名价格
9787302257646 程序设计基础 25
9787302219972 单片机技术及应用 32
9787302203513 编译原理 46
9787811234923 汇编语古程序设计教程 21
9787512100831 计算机操作系统 17
9787302265436 计算机导论实验指导 18
9787302180630 实用数据结构 29
9787302225065 数据结构(C语古版） 38
9787302171676 C#面向对象程齐设计 39
9787302250692 C语言程序设计 42
9787302150664 数据库原理 35
9787302260806 Java编程与实践 56
9787302252887 程序设计与应用教程 39
9787302198505 嵌入式操作系统及编程 25
9787302169666 软件测试 24
9787811231557 Eclipse基础与应用 35

二、插入现有图书信息的实现

1、单向链表前插法

每一个新结点都往头结点后面插入，也就是头结点的Next指向的结点，如下图所示，

用C语言实现如下，

singLinkList.h头文件内容声明和定义：

#ifndef   __SINGLINKLIST_H__
#define   __SINGLINKLIST_H__

#include 
#include 
#include 
#include 
#include 

//图书信息
typedef struct BookIn
{
   char ISBN[14];         //书号
   char bookName[50];     //书名
   uint8_t price;         //价格
}BOOKINFO;

//此单向链表为带头结点的链表
typedef struct  BookList
{
   BOOKINFO bookInfo;//65
   struct BookList *next;
}BOOKLT;


BOOKLT * SingLinkList_Create(void);//创建头结点
int  SingLinkList_HeadInsert(BOOKLT * booklt,uint8_t n,BOOKINFO *myBookInfo);前插法插入节点
void SingLinkList_Traverse(BOOKLT *bookHeadNode);//遍历单向链表
void SingLinkList_Destory(BOOKLT * bookHeadNode);//释放各个结点的内存
#endif //  __SINGLINKLIST_H__

singLinkList.c文件内容实现如下：

#include "singLinkList.h"

extern BOOKLT *myBookInfo;

//创建链表表头
BOOKLT * SingLinkList_Create(void)
{
    BOOKLT * bookHeadNode = (BOOKLT*)malloc(sizeof(BOOKLT));
    if(bookHeadNode == NULL)
    {
       return -1;
    }
    bookHeadNode->next = NULL;
    return bookHeadNode;
}

//前插法插入节点
int  SingLinkList_HeadInsert(BOOKLT *bookHeadNode,uint8_t num,BOOKINFO *myBookInfo)
{
     uint8_t n = 0;

     for(n = 0;n < num;n++)
     {
             BOOKLT * pNode = malloc(sizeof(BOOKLT));//创建新结点pNode
             if(pNode == NULL)
             {
                 return -1;
             }
             //清空节点的数据域，刚刚获得空间，内存不干净会有乱码
             memset(pNode->bookInfo.bookName,0,14);
             memset(pNode->bookInfo.ISBN,0,50);
             pNode->bookInfo.price = 0;

             //myBookInfo赋值给新节点pNode的数据域
             memcpy(pNode->bookInfo.bookName,myBookInfo[n].bookName,strlen(myBookInfo[n].bookName));
             memcpy(pNode->bookInfo.ISBN,myBookInfo[n].ISBN,strlen(myBookInfo[n].ISBN));
             pNode->bookInfo.price = myBookInfo[n].price;
             pNode->next = NULL;   //必须为空

             pNode->next = bookHeadNode->next; //结点的next指向头结点的next
             bookHeadNode->next = pNode;//头结点的next指向结点的首地址
     }
     return true;
}

void SingLinkList_Traverse(BOOKLT *bookHeadNode)
{
     BOOKLT * p = NULL; //创建一个BOOKLT结构类型的指针
     p = bookHeadNode->next; //p指向头结点的next

    while(p)//p->next不为空，继续遍历
    {
         printf("%s,%s,%drn",p->bookInfo.ISBN,p->bookInfo.bookName,p->bookInfo.price);//输出每个结点的数据域内容
         p = p->next;//指向下一个结点
    }
}

//释放结点内存和头结点内存
void SingLinkList_Destory(BOOKLT * bookHeadNode)
{
     BOOKLT * p = NULL; //创建一个BOOKLT结构类型的指针
     BOOKLT * q = NULL;
     p = bookHeadNode; //p指向头结点
     q = p->next;

    while(p->next)//p->next不为空，继续遍历
    {
         q = p->next;
         p->next = q->next;//p跳过q指向的结点，去指向q指向的结点的下一个结点，割开q指向的结点
         free(q);//释放结点内存
         q=NULL; //指针赋值为空
    }
    free(p);//把结点都释放后，只有头结点，把头结点也释放了
    p=NULL; //指针赋值为空
}

main.c主文件内容实现如下：

#include "singLinkList.h"

//目前现有的图书及其信息如下：
BOOKINFO bookStock[16] =
{
    {"9787302257646","程序设计基础",25},
    {"9787302219972","单片机技术及应用",32},
    {"9787302203513","编译原理",46},
    {"9787811234923","汇编语古程序设计教程",21},
    {"9787512100831","计算机操作系统",17},
    {"9787302265436","计算机导论实验指导",18},
    {"9787302180630","实用数据结构",29},
    {"9787302225065","数据结构(C语古版）",38},
    {"9787302171676","C#面向对象程齐设计",39},
    {"9787302250692","C语言程序设计",42},
    { "9787302150664","数据库原理",35},
    {"9787302260806","Java编程与实践",56},
    {"9787302252887","程序设计与应用教程",39},
    {"9787302198505","嵌入式操作系统及编程",25},
    {"9787302169666","软件测试",24},
    {"9787811231557","Eclipse基础与应用",35},
};


int main()
{
    BOOKLT *myBookHeadNode;//定义一个BOOKLT类型的头结点指针

    myBookHeadNode  = SingLinkList_Create();//创建一个头结点
    SingLinkList_HeadInsert(myBookHeadNode,sizeof(bookStock)/sizeof(BOOKINFO),bookStock);//前插法插入节点
    SingLinkList_Traverse(myBookHeadNode);//遍历单向链表
    //free(myBookHeadNode);//有问题，只释放头结点内存，各个结点内存没有删除
    SingLinkList_Destory(myBookHeadNode);//释放各个结点的内存和头结点的内存

    return 0;
}

最后遍历录入的图书信息如下图所示：

2、单向链表后插法

下面用C语言实现单向链表后插法，

singLinkList.h头文件声明后插法方式1和方式2的函数如下：

int  SingLinkList_TailInsert_method1(BOOKLT * booklt,uint8_t n,BOOKINFO *myBookInfo);前插法插入结点
int  SingLinkList_TailInsert_method2(BOOKLT * booklt,uint8_t n,BOOKINFO *myBookInfo);前插法插入结点

singLinkList.c文件内容定义后插法方式1和方式2的函数如下：

//后插法插入节点
int  SingLinkList_TailInsert_method1(BOOKLT *bookHeadNode,uint8_t num,BOOKINFO *myBookInfo)
{
      uint8_t n = 0;
      BOOKLT * p = NULL; //创建一个BOOKLT结构类型的指针
      printf("==========后插法方式1如下==========rn");
     for(n = 0;n < num;n++)
     {
             BOOKLT * pNode = malloc(sizeof(BOOKLT));//创建新结点pNode
             if(pNode == NULL)
             {
                 return -1;
             }
             //清空节点的数据域，刚刚获得空间，内存不干净会有乱码
             memset(pNode->bookInfo.bookName,0,14);
             memset(pNode->bookInfo.ISBN,0,50);
             pNode->bookInfo.price = 0;

             //myBookInfo赋值给新节点pNode的数据域
             memcpy(pNode->bookInfo.bookName,myBookInfo[n].bookName,strlen(myBookInfo[n].bookName));
             memcpy(pNode->bookInfo.ISBN,myBookInfo[n].ISBN,strlen(myBookInfo[n].ISBN));
             pNode->bookInfo.price = myBookInfo[n].price;
             pNode->next = NULL;   //必须为空

             p = bookHeadNode;
             while(p->next)
             {
                  p = p->next;
             }
             pNode->next = p->next;
             p->next = pNode;
     }
     return true;
}

//后插法插入节点--推荐使用这种方式
int  SingLinkList_TailInsert_method2(BOOKLT *bookHeadNode,uint8_t num,BOOKINFO *myBookInfo)
{
     uint8_t n = 0;
     BOOKLT * p = NULL; //创建一个BOOKLT结构类型的指针
     p = bookHeadNode;
     while(p->next) //遍历整个链表先找到尾节点，找到尾节点跳出while循环
     {
          p = p->next;
     }
    printf("rn==========后插法方式2如下==========rn");
     for(n = 0;n < num;n++)
     {
             BOOKLT * pNode = malloc(sizeof(BOOKLT));//创建新结点pNode
             if(pNode == NULL)
             {
                 return -1;
             }
             //清空节点的数据域，刚刚获得空间，内存不干净会有乱码
             memset(pNode->bookInfo.bookName,0,14);
             memset(pNode->bookInfo.ISBN,0,50);
             pNode->bookInfo.price = 0;

             //myBookInfo赋值给新节点pNode的数据域
             memcpy(pNode->bookInfo.bookName,myBookInfo[n].bookName,strlen(myBookInfo[n].bookName));
             memcpy(pNode->bookInfo.ISBN,myBookInfo[n].ISBN,strlen(myBookInfo[n].ISBN));
             pNode->bookInfo.price = myBookInfo[n].price;
             pNode->next = NULL;   //必须为空

             p->next = pNode;//将新节点*pNode插入尾节点p后面
             p = pNode; //p指向新的尾节点*pNode
     }
     return true;
}

main.c主文件内容实现如下：

int main()
{
    BOOKLT *myBookHeadNode;//定义一个BOOKLT类型的头结点指针

    myBookHeadNode  = SingLinkList_Create();//创建一个头结点
    SingLinkList_TailInsert_method1(myBookHeadNode,sizeof(bookStock)/sizeof(BOOKINFO),bookStock);//后插法插入节点
    SingLinkList_Traverse(myBookHeadNode);//遍历单向链表
    SingLinkList_Destory(myBookHeadNode);//释放各个结点的内存和头结点的内存

    myBookHeadNode  = SingLinkList_Create();//上面的链表内存已经被释，重新放创建一个头结点
    SingLinkList_TailInsert_method2(myBookHeadNode,sizeof(bookStock)/sizeof(BOOKINFO),bookStock);//后插法插入节点
    SingLinkList_Traverse(myBookHeadNode);//遍历单向链表
    SingLinkList_Destory(myBookHeadNode);//释放各个结点的内存和头结点的内存

    return 0;
}

最后遍历录入的图书信息如下图所示：

个人观点(如果有理解不对的地方，恳请大佬指点，不甚感激)：

方式1是每创建一个新结点，都会从头结点遍历一次，直到找到最末尾结点，再从最末尾结点插入，如果一次性要创建多个节点，不推荐使用方式1。方式2第一步是先找到最末尾的结点p，新结点插入时，p->next指向新结点，然后再把p指向新结点作为新的尾结点，以上一次性创建多个结点推荐使用方式2，但是如果每一次只创建一个新结点，且是后插入，则可以使用方式1。

3、在指定的结点位置插入新结点

singLinkList.c文件内容定义指定的结点位置插入新结点函数如下：

int  SingLinkList_xPositionInsert(BOOKLT *bookHeadNode,uint8_t x,BOOKINFO *myBookInfo)
{
     BOOKLT * p = NULL; //创建一个BOOKLT结构类型的指针
     uint8_t i = 0;
     p = bookHeadNode;
     while( p && (i < x-1))
     {
         p=p->next;
         i++;
     }

     if((!p) || (i >x-1))
     {
         return -1;
     }

     BOOKLT * pNode = malloc(sizeof(BOOKLT));//创建新结点pNode
     if(pNode == NULL)
     {
         return -1;
     }
     //清空节点的数据域，刚刚获得空间，内存不干净会有乱码
     memset(pNode->bookInfo.bookName,0,14);
     memset(pNode->bookInfo.ISBN,0,50);
     pNode->bookInfo.price = 0;

     //myBookInfo赋值给新节点pNode的数据域
     memcpy(pNode->bookInfo.bookName,myBookInfo->bookName,strlen(myBookInfo->bookName));
     memcpy(pNode->bookInfo.ISBN,myBookInfo->ISBN,strlen(myBookInfo->ISBN));
     pNode->bookInfo.price = myBookInfo->price;
     pNode->next = p->next; //pNode和p指向同一个结点
     p->next = pNode;//p->next指向新节点pNode

     return true;
}

main.c主文件内容实现如下：

BOOKINFO newBookInfo=
{
      "1234567890110","微机原理与接口技术",45
};

int main()
{
    BOOKLT *myBookHeadNode;//定义一个BOOKLT类型的头结点指针

    myBookHeadNode  = SingLinkList_Create();//上面的链表内存已经被释，重新放创建一个头结点
    SingLinkList_TailInsert_method2(myBookHeadNode,sizeof(bookStock)/sizeof(BOOKINFO),bookStock);//后插法插入节点
    printf("===========原所有图书信息：===========rn");
    SingLinkList_Traverse(myBookHeadNode);//遍历单向链表

    printf("rn===========在原有图书信息中的第6个结点插入一个新图书信息===========rn");
    SingLinkList_xPositionInsert(myBookHeadNode,6,&newBookInfo);
    SingLinkList_Traverse(myBookHeadNode);//遍历单向链表

    SingLinkList_Destory(myBookHeadNode);//释放各个结点的内存和头结点的内存

    return 0;
}

最后遍历录入的图书信息如下图所示：

到此，单向链表结点创建和插入方法已经完成，接下来进行图书信息查找方法的实现，下一课再见。

2022.06.12 结

单向链表的实现--插入

C/C++/C#相关栏目本月热门文章