C语言中的链表_链表c语言

目录

一、链表概述

二、链表操作

1、动态创建链表

（1）malloc函数

（2）calloc函数

（3）free函数

2、链表的插入操作

3、链表的删除操作补充内容

三、链表完整代码实现

---

一、链表概述

        链表是一种常见的数据结构，在链表中可以动态的进行内存分配。也可以将链表看成是一个功能强大的数组，它可以在节点中定义多种数据类型，还可以根据需要随意增加，删除，或者插入节点。

        每个链表都有一个头指针，一般以head来表示，存放的是一个地址。链表中的节点分为两类，头结点和一般节点，头结点是没有数据域的。链表中每个节点都分为两部分，一个数据域，一个是指针域。

        简单来说，链表就如同车链子一样，head指向第一个元素：第一个元素又指向第二个元素；……，直到最后一个元素，最后的一个元素不再指向其它元素，它称为“表尾”，它的地址部分放一个“NULL”（表示“空地址”），链表到此结束。

        本文仅对单链表进行介绍。

 

二、链表操作

1、动态创建链表

        链表的创建的是一个动态的过程，动态创建一个节点时，要为其分配内存，相关函数介绍如下：

（1）malloc函数

        函数功能：在内存中动态地分配一块size大小的内存空间。malloc函数会返回一个指针，该指针指向分配的内存空间，如果出现错误则返回NULL。

        malloc函数原型如下：

void *malloc(unsigned int size);

（2）calloc函数

        函数功能：在内存中动态分配n个长度为size的连续内存空间数组。calloc函数会返回一个指针，该指针指向动态分配的连续内存空间地址。当分配空间错误时，返回NULL。

        calloc函数原型如下：

void *calloc(unsigned n, unsigned size);

（3）free函数

        函数功能：使用由指针ptr指向的内存区，使部分内存区能被其他变量使用。ptr是最近一次调用calloc或malloc函数时返回的值。free函数无返回值。（释放内存空间）

        函数原型如下：

void free(void *ptr);

2、链表的插入操作

        链表的插入操作可以在链表的头节点位置进行，也可以在中间节点或者尾结点进行。三种链表的插入操作思路是一样的。

// 链表的插入操作（在链表的头结点插入）
// 该函数将会返回链表的头指针
struct Student *Insert(struct Student *pHead)
{
    struct Student *pNew;                   // 指向新分配的空间
    printf("-------Insert member at first------\n");        // 提示信息
    pNew = (struct Student*)malloc(sizeof(struct Student));  // 分配内存空间，并返回指向该内存空间的指针
 
    scanf("%s",&pNew->cName);               // 输入新加入的学生姓名
    scanf("%d",&pNew->iNumber);             // 输入新加入的学生学号
 
    // 两步操作：1.将原来的头节点地址给到新节点指向的下一级节点；2.将新节点的地址给到头节点。
    pNew->pNext = pHead;                    // 新节点指针指向原来的首节点（将原来的头结点地址给到新加入的节点指向的地址）
    pHead = pNew;                           // 链表头指针指向新节点（新节点变成了头节点）
    iCount++;                               // 增加链表的节点数
    return pHead;                           // 返回链表头指针
}

3、链表的删除操作补充内容

        链表删除过程中，可以对待删除的链表序号进行判断

（1）在对头结点进行赋值过程中，可以先对链表的头结点进行判断，判断当前链表头节点是否为空, 非空情况下再进行后续的头结点赋值操作；

    if (pHead == NULL)                              // 首先判断链表头是否为空，即整个链表是否为空表
    {                                               // 若是空表，则输出空
        printf("\n---The List NULL!---\n");
        return pHead;
    }
    pTemp = pHead;                                  // pHead赋值给pTemp，得到链表的头结点

（2）在执行循环判断语句过程中，可以先判断待删除的节点下标序号是否为pTemp指向的节点；

	while ((iIndex != pTemp->iIndex) && (pTemp->pNext != NULL))     // 当要删除的iIndex不等于pTemp所指向的节点下标且满足pTemp的下一个结点不为空
	{
		pPre = pTemp;                               // 将pTemp赋给pPre;
        pTemp = pTemp->pNext;                       // 再将pTemp指向下一个节点；重复进行，直到找到待删除的节点序号，此时pTemp指向的节点就是所要找的待删除节点
	}

（3）在进行节点删除过程中，可以先判断待删除的节点是否为第一个节点；

	if (iIndex == pTemp->iIndex) 
    {                          
        // 除非链表中不存在要寻找的iIndex，否则这个条件是一定成立的，
		if(pTemp == pHead)
        {                                           // 如果要删除的是第1个节点
			pHead = pTemp->pNext;                   // 则让pHead指向pTemp的下一个节点，也就是第二个节点
		}
		else 
        {
			pPre->pNext = pTemp->pNext;             // 如果要删除的不是第一个节点，则让pPre的next指向pTemp（要删除的结点）的下一个结点，此时则跳过了这个iIndex，即达到删除的效果
		}
		printf("Delete: %d\n", iIndex);
		iCount = iCount - 1;
	}

三、链表完整代码实现

        本节详细链表操作见代码实现，包括链表的动态创建，插入、删除和输出操作。

#include<stdio.h>
#include<stdlib.h>
 
// 创建链表节点结构，表示每一个学生
struct Student
{
    char cName[20];             // 学生姓名
    int iNumber;                // 学号
    struct Student *pNext;      // 指向下一个节点的指针
};
 
int iCount;                     // 全局变量表示链表长度
 
// Create函数的功能是创建链表，动态分配内存空间的方式创建链表
// 该函数将会返回链表的头指针
//（在链表的尾结点插入）
struct Student *Create()
{
    struct Student *pHead = NULL;           // 初始换链表头指针为空
    struct Student *pNew, *pEnd;            // pEnd用来指向原来的尾节点，pNew用来指向新创建的节点
    iCount = 0;                             // 表示链表中节点的数量
    pEnd = pNew = (struct Student*)malloc(sizeof(struct Student));     // malloc 函数分配内存，先用pEnd和pNew两个指针都指向第一个分配的内存
    printf("------Please First Enter Name, The Number------\n");
    scanf("%s",&pNew->cName);
    scanf("%d",&pNew->iNumber);
 
    while(pNew->iNumber != 0)
    {
        iCount++;
        // 第一次加入节点，新节点即为首节点，也是最后一个节点，并且需要将新加入的节点的指针指向NULL，即为pHead指向。
        if(iCount == 1)
        {
            pNew->pNext = pHead;            // 使得指针指向为空（新加入的节点为首节点的时候，节点空指针即为pHead指向
            pEnd = pNew;                    // 跟踪新加入的节点（新加入的节点地址即为尾结点地址）
            pHead = pNew;                   // 头指针指向首节点（将新加入的节点的地址给头指针）
        }
        else
        {
            pNew->pNext = NULL;             // 新节点的指针为空（将新加入的节点指针指向空）
            pEnd->pNext = pNew;             // 原来的尾结点指向新节点（原来的尾结点变成了中间节点，需要将新节点地址给原来的尾结点）
            pEnd = pNew;                    // pEnd指向新节点（让新加入的节点成为尾结点）
        }
        pNew = (struct Student*)malloc(sizeof(struct Student));      // 再次分配节点内存空间
        scanf("%s",&pNew->cName);           // 再次输入新的节点进入循环判断，如果满足新节点要求则执行循环继续添加，如果不满足则跳出循环
        scanf("%d",&pNew->iNumber);
    }
    free(pNew);                             // 不满足新节点要求，跳出循环后调用free函数释放未使用的内存空间
    return pHead;                           // 该函数返回链表的头指针
}
 
// 定义打印函数Print
// void 函数没有返回值
void Print(struct Student *pHead)
{
    struct Student *pTemp;                  // 循环所用的临时指针
    int iIndex = 1;                         // 表示链表中节点的序号
 
    printf("======The List Has %d Members:======\n",iCount);
    printf("\n");
    pTemp = pHead;                          // 指针得到首节点的地址
 
    while(pTemp != NULL)
    {
        printf("The NO%d Member is:\n",iIndex);
        printf("The Name is %s\n",pTemp->cName);            // 输出姓名
        printf("The Number is %d\n",pTemp->iNumber);        // 输出学号
        printf("\n");
        pTemp = pTemp->pNext;                               // 移动临时指针到下一个节点
        iIndex++;                                           // 进行自加运算
    }
}
 
// 链表的插入操作（在链表的头结点插入）
// 该函数将会返回链表的头指针
struct Student *Insert(struct Student *pHead)
{
    struct Student *pNew;                   // 指向新分配的空间
    printf("-------Insert member at first------\n");        // 提示信息
    pNew = (struct Student*)malloc(sizeof(struct Student));  // 分配内存空间，并返回指向该内存空间的指针
 
    scanf("%s",&pNew->cName);               // 输入新加入的学生姓名
    scanf("%d",&pNew->iNumber);             // 输入新加入的学生学号
 
    // 两步操作：1.将原来的头节点地址给到新节点指向的下一级节点；2.将新节点的地址给到头节点。
    pNew->pNext = pHead;                    // 新节点指针指向原来的首节点（将原来的头结点地址给到新加入的节点指向的地址）
    pHead = pNew;                           // 链表头指针指向新节点（新节点变成了头节点）
    iCount++;                               // 增加链表的节点数
    return pHead;                           // 返回链表头指针
}
 
// 删除链表节点
// 输入：链表头结点pHead，要删除的节点下标iIndex;dd
void Delete(struct Student *pHead, int iIndex)
{
    int i;                                  // 控制循环变量
    struct Student *pTemp;                  // 临时指针变量，表示要删除的节点
    struct Student *pPre;                   // 表示要删除节点之前 的节点
    pTemp = pHead;                          // pHead赋值给pTemp，得到链表的头结点
    pPre = pTemp;                           // pPre指向pTemp，将pTemp的地址给到pPre
 
    printf("======Delete NO%d member======\n",iIndex);          // 提示待删除节点位置信息
 
    // for语句进行循环操作，使得pTemp指向要删除的节点
    for(i=1; 1<iIndex; i++)
    {
        // 将pTemp赋值给pPre，再将pTemp指向下一个节点，重复进行，直到找到需要定位的iIndex节点，此时pTemp指向的节点就是所要找的待删除的节点
        pPre = pTemp;                       // 定位到要删除的节点pTemp
        pTemp = pTemp->pNext;               // 再将pTemp指向下一个节点
    }
    pPre->pNext = pTemp->pNext;             // 连接待删除节点两边的节点地址（将待删除节点两边的地址相关联）（重点！！！）
    free(pTemp);                            // 释放掉要删除节点的内存空间
    iCount--;                               // 减少链表中元素的个数
}
 
// 定义主函数
int main()
{
    struct Student *pHead;                  // 定义头结点
    pHead = Create();                       // 创建链表节点
    pHead = Insert(pHead);                  // 插入新的节点
    Delete(pHead,2);                        // 删除链表中第二个节点的操作
    Print(pHead);                           // 输出最终的链表
    return 0;
}