不带头结点的链表的基本操作

Bertha 。 2022-05-25 06:35 162阅读 0赞

与带头结点的单链表相比，不带头结点的单链表没有头结点，可以简单的理解为，带头结点的单链表的的头结点一般数据域不存元素，指针域指向第一个结点，头指针（假设为`pHead`）指向头结点，而不带头结点的单链表，头指针指向单链表的第一个结点，如果把链表中的结点进行编号，带头结点的链表的头结点可以理解为是其第0个结点，头指针`pHead`指向头结点即第0个结点，不带头结点的指针指向第1个结点。

##### 源代码 #####

**link\_list.h**不带头结点的链表基本操作的函数声明

#ifndef __LINK_LIST_H__
    #define __LINK_LIST_H__
    
    typedef int DataType;
    
    typedef struct Node
    {
        DataType Data;
        struct Node* Next;
    }Node, *LinkList;
    
    void InitList(LinkList* pHead);   //链表初始化
    int EmptyList(LinkList pHead);    //判断链表是否为空
    void PushFornt(LinkList* pHead, DataType data);  //头插
    int PopFornt(LinkList* pHead, DataType* data);   //头删
    void PushBack(LinkList* pHead, DataType data);   //尾插
    int PopBack(LinkList* pHead, DataType* data);    //尾删
    void DelList(LinkList* pHead, int i, DataType* data);  //删除操作
    void InsList(LinkList* pHead, int i, DataType data);   //插入操作
    Node* Get(LinkList pHead, int i);    //按序号查找
    int Locate(LinkList pHead, DataType data);   //安值查找
    int length(LinkList pHead);    //求表长
    void PrintList(LinkList pHead);  //打印表中元素
    
    
    #endif

**link\_list.c**基本操作函数的实现代码

#include <stdio.h>
    #include "link_list.h"
    
    //初始化，将头指针pHead置空
    void InitList(LinkList* pHead)
    {
        *pHead = NULL;
    }
    
    //判断表是否为空
    
    int EmptyList(LinkList pHead)
    {
        if (pHead == NULL)
        {
            return 1;
        }
        return 0;
    }
    
    
    //头插，在链表的表头插入一个新的元素data
    void PushFornt(LinkList* pHead, DataType data)
    {
        Node* pNewNode = (LinkList)malloc(sizeof(Node));
        if (pNewNode == NULL)
        {
            printf("开辟空间失败!\n");
            return;
        }
        pNewNode->Data = data;     
        pNewNode->Next = *pHead;   
        *pHead = pNewNode;      
    }
    
    //头删，删除链表中的第一个结点
    int PopFornt(LinkList* pHead, DataType* data)
    {
        //判断表是否为空
        if (EmptyList(*pHead))
        {
            printf("表为空！\n");
            return 0;
        }
        //只有一个头结点，将指向头结点的指针置空
        if ((*pHead)->Next == NULL)   
        {
            pHead = NULL;
        }
        Node* pDel = *pHead;        
        *data = pDel->Data;        
        *pHead = pDel->Next;        
        free(pDel);                 
        return *data;
    }
    
    //尾插，在表尾插入一个元素data
    
    void PushBack(LinkList* pHead, DataType data)
    {
        Node* pCur = *pHead;
        Node* pNewNode = (LinkList)malloc(sizeof(Node));
        if (pNewNode == NULL)
        {
            printf("申请空间失败!\n");
        }
        //跳出循环时pCur指向链表的尾结点
        while (pCur->Next != NULL)
        {
            pCur = pCur->Next;
        }
        pNewNode->Data = data;   
        pCur->Next = pNewNode;   
        pNewNode->Next = NULL;   
    }
    
    //尾删，删除链表表尾的元素data
    
    int PopBack(LinkList* pHead, DataType* data)
    {
        Node* pCur = *pHead;
        if (EmptyList(*pHead))
        {
            printf("表为空!\n");
        }
        while (pCur->Next->Next)
        {
            pCur = pCur->Next;
        }
        *data = pCur->Next->Data;  
        pCur->Next = NULL;        
        free(pCur->Next);
        return *data;
    }
    
    //删除操作，i为要删除的元素序号，data为要删除的元素值
    
    void DelList(LinkList* pHead, int i, DataType* data)
    {
        int k = 1;   //第一个结点
        if (EmptyList(*pHead))
        {
            printf("表为空！\n");
            return;
        }
        Node* pCur = *pHead;
        Node* pDel;
        //删除第一个结点元素，调用头删函数
        if (i == 1)
        {
            PopFornt(pHead, data);        
            return;
        }
        while ((!(EmptyList(*pHead))) && k < i - 1)
        {
            k++;
            pCur = pCur->Next;
        }
        pDel = pCur->Next;
        *data = pDel->Data;
        pCur->Next = pDel->Next;
        free(pDel);
    }
    
    //插入操作，在链表的第i个结点插入一个值为data的新结点
    
    void InsList(LinkList* pHead, int i, DataType data)
    {
        int k = 1;
        Node* pCur = *pHead;
        while (!EmptyList(*pHead) && (k < i - 1))
        {
            k++;
            pCur = pCur->Next;
        }
        Node* pNewNode = (Node*)malloc(sizeof(Node));
        pNewNode->Data = data;
        pNewNode->Next = pCur->Next;
        pCur->Next = pNewNode;
    }
    
    //按序号查找，查找链表中第i个元素对应的值
    
    Node* Get(LinkList pHead, int i)
    {
        int k = 1;
        if (i < 0)
        {
            return NULL;
        }
        Node* pCur = pHead;
    
        while ((pCur->Next != NULL) && k < i)
        {
            pCur = pCur->Next;
            k++;
        }
        if (k == i)
        {
            return pCur;
        }
        return 0;
    }
    
    //按值查找，查找data在表中的位置
    
    int Locate(LinkList pHead, DataType data)
    {
        int k = 1;
        if (EmptyList(pHead))
        {
            printf("表为空!\n");
            return NULL;
        }
        Node* pCur = pHead;
        while (pCur)
        {
            while (pCur->Data != data)
            {
                k++;
                pCur = pCur->Next;
            }
            break;
        }
        return k;
    }
    //求表长，求链表中元素的个数
    
    int length(LinkList pHead)
    {
        if (EmptyList(pHead))
        {
            return 0;
        }
        int count = 0;
        Node* p;
        p = pHead;
        while (p)   
        {
            p = p->Next;   
            count++;
        }
        return count;      
    }
    
    //打印表中元素
    
    void PrintList(LinkList pHead)
    {
        Node* pCur = pHead;
        while (pCur)
        {
            printf("%d ", pCur->Data);
            pCur = pCur->Next;
        }
        printf("\n");
    }

**main.c**函数的简单测试代码

#include <stdio.h>
    #include <stdlib.h>
    #include <Windows.h>
    #include "link_list.h"
    
    int main()
    {
        LinkList L;
        DataType data;
    
        //初始化链表
        InitList(&L);
        //头插
        PushFornt(&L, 1);
        PushFornt(&L, 2);
        PushFornt(&L, 3);
        PushFornt(&L, 4);
        PushFornt(&L, 5);
        printf("表中元素有：");
        // 打印表中元素
        PrintList(L);
        //打印表中元素个数
        printf("表长length = %d\n", length(L));
        printf("\n");
    
        //尾插
        PushBack(&L, 6);
        PushBack(&L, 7);
        PushBack(&L, 8);
        PushBack(&L, 9);
        printf("表中元素有：");
        PrintList(L);
        printf("表长length = %d\n", length(L));
        printf("\n");
    
        //头删
        PopFornt(&L,&data);
        printf("删除的元素是：%d\n", data);
        PopFornt(&L,&data);
        printf("删除的元素是：%d\n", data);
        //尾删
        PopBack(&L,&data);
        printf("删除的元素是：%d\n",data);
        PopBack(&L,&data);
        printf("删除的元素是：%d\n",data);
    
        printf("表中元素有：");
        PrintList(L);
        printf("表长length = %d\n", length(L));
        printf("\n");
        printf("删除表中的第3个元素\n");
        //删除操作
        DelList(&L, 3, &data);
        printf("删除的元素是：%d\n", data);
        //插入操作
        InsList(&L, 3, 8);
        InsList(&L, 2, 9);
        printf("表中元素有：");
        PrintList(L);
        printf("表长length = %d\n", length(L));
        printf("\n");
    
        //按序号查找
        Node *p=Get(L, 3);
        printf("表中的第三个元素是：%d\n", p->Data);
        //按值查找
        printf("8在表中的位置为：%d\n", Locate(L, 8));
    
        system("pause");
        return 0;
    }