欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-15 17:33:50
...

        与带头结点的单链表相比,不带头结点的单链表没有头结点,可以简单的理解为,带头结点的单链表的的头结点一般数据域不存元素,指针域指向第一个结点,头指针(假设为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;
}