带头结点的链表的基本操作(超详细）

Jayne ·

更新时间:2024-11-10

· 1377 次阅读

前言

一、链表的定义

二、链表的 C 语言描述

三、链表中基本操作的实现

3.1构造一个带头结点的空链表

3.2取第i个数据元素

3.3在链表中查找值为e的元素

3.3.1返回值类型是节点的地址

3.3.2返回值类型是节点的位置(序号)

3.4在第i位插入数据元素

3.5删除第i个数据元素

3.6 前插建立具有n的元素链表

3.7尾插建立具有n的元素链表

3.8线性表置空

3.9销毁链表

3.10判断链表是否为空

3.11求链表的表长

3.12遍历链表

四、链表代码实现

五、测试结果

六、总结

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

链表是一种动态分配空间的存储结构，能更有效地利用存储空间，通过对单链表基本操作的代码实现，我深刻领悟到以“指针”指示元素的后继，在插入或删除元素时不需要移动元素。但是与此同时，由于链表是“顺序存取”的结构，给随机存取元素和在表尾插入等操作带来不便。，所以接下来我将学习尾指针表示的单链表，双向链表以及循环链表等。

前言

本文参考王卓老师的数据结构视频和严蔚敏老师的《数据结构》

一、链表的定义

用一组地址任意的存储单元存放线性表中的数据元素。

结点 = 数据元素+指针(指后继元素存储位置)

二、链表的 C 语言描述

代码如下（示例）：

//带头结点的单链表
typedef struct LNode {
    int data;
    struct LNode* next;
}Lnode,*LinkList;

三、链表中基本操作的实现 3.1构造一个带头结点的空链表

c++中用new来动态的开辟空间，而c中则是用malloc来开辟空间

我使用new来动态开辟空间

注意:参数是引用型的

代码如下(示例):

void InitList(LinkList& L)
{
L = new Lnode;//L=(LinkList)malloc(sizeof(LNode))
L->next = NULL;
}

3.2取第i个数据元素

结束条件：链表走到空或者i的大小不对，比1小

则while语句判断条件为：while(p&&j<i) p表示当前节点不为空，j<i表示传进来的i是正确的，并且到该点

当此时p为空或者j>i，则返回0，表示未找到

否则把此时节点的data传给引用型参数data，并返回1

代码如下(示例):

int GetElem_L(LinkList L, int i, int& data)
{
int j = 1;
Lnode* p;
p = L->next;
while (p && j < i)
{
p = p->next;
j++;
}
if (!p || j > i)return 0;
data = p->data;
return 1;
}

3.3在链表中查找值为e的元素

时间效率分析：查找次数与位置有关，O(n)

注意，可以按照具体情况来写函数的返回值类型

比如，返回值类型可以是节点的地址，也可以是节点的位置

3.3.1返回值类型是节点的地址

代码如下(示例):

Lnode* LocationElem(LinkList L, int e)
{
Lnode* p = L->next;
while (p && p->data != e)
{
p = p->next;
}
return p;
}

3.3.2返回值类型是节点的位置(序号)

代码如下(示例):

int LocateElem_L(LinkList L, int e)
{
int j = 1;
Lnode* p = L->next;
while (p && p->data != e)
{
p = p->next;
j++;
}
if (p)return j;
else return 0;
}

3.4在第i位插入数据元素

修改指针的时间O(1),但是不知道插在哪里，所以需要查找，查找时间O(n)

代码如下(示例):

void ListInsert_L(LinkList& L, int i, int e)
{
int j = 0;
Lnode* p = L;
while (p && j < i - 1)//即找到i-1的位置
{
p = p->next;
j++;
}
if (!p || j > i - 1)
{
printf("i值错误,i小于1或大于表长\n");
return;
}
Lnode* s = new Lnode;
s->data = e;
s->next = NULL;
s->next = p->next;
p->next = s;//注意两行不能调换位置，否则s指向自己，错误
printf("插入成功\n");
}

3.5删除第i个数据元素

修改指针的时间O(1),但是不知道删除位置，所以需要查找，查找时间O(n)

代码如下(示例):

void ListDelete(LinkList& L, int i, int& e)
{
Lnode* p = L,*q;
int j = 0;
while (p->next && j < i - 1)//找到i-1的节点
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)
{
printf("未找到要删除的节点\n");
return;
}
q = p->next;
e = q->data;
p->next = q->next;
delete q;//释放空间
printf("成功删除\n");
}

3.6 前插建立具有n的元素链表

时间复杂度：O(n)

逆序输入

确保结果与想要的是一致的（与尾插结果一致）

代码如下(示例):

void CreateList_F(LinkList& L, int t[],int n)
{
//创建n个节点
L = new Lnode;
L->next = NULL;
for(int i=n-1;i>=0;i--)
{
Lnode* p =new Lnode;
p->data=t[i];
p->next = L->next;
L->next = p;
}
}

3.7尾插建立具有n的元素链表

正序输入

时间复杂度：O(n)

代码如下(示例):

void CreateList_L(LinkList& L,int a[],int n)
{
//尾指针指向尾节点
L = new Lnode;
L->next = NULL;
Lnode* r = L;//尾指针，开始也指向头节点
for (int i = 0; i < n; i++)
{
Lnode* p = new Lnode;
p->data=a[i];
p->next = NULL;
r->next = p;
r = p;//把尾指针更新到新节点的位置
}
}

3.8线性表置空

从首元节点开始删除，保存了头指针和头节点

头节点的next赋值为空

代码如下(示例):

void CleanList(LinkList& L)
{
Lnode* p = L->next;
Lnode* q;
while (p)
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;
}

3.9销毁链表

所有节点，包括头节点也删掉

代码如下(示例):

void DestoryList(LinkList& L)
{
Lnode* p;
while (L)
{
p = L;
L = L->next;
delete p;
}
}

3.10判断链表是否为空

头节点和头指针还在算空表，返回1

当头节点的next值不为空，即起码有个首元节点，则不算空表，返回0

代码如下(示例):

int isEmpty(LinkList L)
{
if (L->next == NULL)
return 1;
return 0;
}

3.11求链表的表长

用一个int型的length来计算，在循环中，当tmp未走到空的时候，每次都加1

代码如下(示例):

int ListLength(LinkList L)
{
Lnode* tmp = L->next;
int length = 0;
while (tmp != NULL)
{
length++;
tmp = tmp->next;
}
return length;
}

3.12遍历链表

当链表未走到空的时候，依次把所有节点的数据都输出

代码如下(示例):

void ListTraverse(LinkList L)
{
Lnode *tmp=L->next;
int i=0;
while(tmp!=NULL)
{
cout<<"第"<<i+1<<"个元素的数据:"<<tmp->data<<endl; 
i++;
tmp=tmp->next;
}
}

四、链表代码实现

代码如下(示例):

#include <iostream>
using namespace std;
const int N=101;
//带头结点的单链表
typedef struct LNode {
int data;
struct LNode* next;
}Lnode,*LinkList;
//链表初始化
//构造一个带头结点的空链表
void InitList(LinkList& L)
{
L = new Lnode;//L=(LinkList)malloc(sizeof(LNode))
L->next = NULL;
}
//判断链表是否为空
//头节点和头指针还在（空表）
int isEmpty(LinkList L)
{
if (L->next == NULL)
return 1;
return 0;
}
//销毁链表
//所有节点，包括头节点也删掉
void DestoryList(LinkList& L)
{
Lnode* p;
while (L)
{
p = L;
L = L->next;
delete p;
}
}
//清空单链表
//清空元素,从首元节点开始删除
void CleanList(LinkList& L)
{
Lnode* p = L->next;
Lnode* q;
while (p)
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;
}
//求链表的表长
int ListLength(LinkList L)
{
Lnode* tmp = L->next;
int length = 0;
while (tmp != NULL)
{
length++;
tmp = tmp->next;
}
return length;
}
//求第i个元素的值
int GetElem_L(LinkList L, int i, int& data)
{
int j = 1;
Lnode* p;
p = L->next;
while (p && j < i)
{
p = p->next;
j++;
}
if (!p || j > i)return 0;
data = p->data;
return 1;
}
//按值查找  返回地址
//时间效率分析：查找次数与位置有关，O(n)
Lnode* LocationElem(LinkList L, int e)
{
Lnode* p = L->next;
while (p && p->data != e)
{
p = p->next;
}
return p;
}
//按值查找，返回位置序号
int LocateElem_L(LinkList L, int e)
{
int j = 1;
Lnode* p = L->next;
while (p && p->data != e)
{
p = p->next;
j++;
}
if (p)return j;
else return 0;
}
//在第i个元素之前插入值为e的节点
//修改指针的时间O(1),但是不知道插在哪里，所以需要查找，查找时间O(n)
void ListInsert_L(LinkList& L, int i, int e)
{
int j = 0;
Lnode* p = L;
while (p && j < i - 1)//即找到i-1的位置
{
p = p->next;
j++;
}
if (!p || j > i - 1)
{
printf("i值错误,i小于1或大于表长\n");
return;
}
Lnode* s = new Lnode;
s->data = e;
s->next = NULL;
s->next = p->next;
p->next = s;//注意两行不能调换位置，否则s指向自己，错误
printf("插入成功\n");
}
//删除  删除第i个节点
//修改指针的时间O(1),但是不知道删除位置，所以需要查找，查找时间O(n)
void ListDelete(LinkList& L, int i, int& e)
{
Lnode* p = L,*q;
int j = 0;
while (p->next && j < i - 1)//找到i-1的节点
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1)
{
printf("未找到要删除的节点\n");
return;
}
q = p->next;
e = q->data;
p->next = q->next;
delete q;//释放空间
printf("成功删除\n");
}
//头插法建立单链表   时间复杂度：O(n)  逆序输入
void CreateList_F(LinkList& L, int t[],int n)
{
//创建n个节点
L = new Lnode;
L->next = NULL;
for(int i=n-1;i>=0;i--)
{
Lnode* p =new Lnode;
p->data=t[i];
p->next = L->next;
L->next = p;
}
}
//尾插法  正序输入 时间复杂度：O(n)
void CreateList_L(LinkList& L,int a[],int n)
{
//尾指针指向尾节点
L = new Lnode;
L->next = NULL;
Lnode* r = L;//尾指针，开始也指向头节点
for (int i = 0; i < n; i++)
{
Lnode* p = new Lnode;
p->data=a[i];
p->next = NULL;
r->next = p;
r = p;//把尾指针更新到新节点的位置
}
}
//遍历 
void ListTraverse(LinkList L)
{
Lnode *tmp=L->next;
int i=0;
while(tmp!=NULL)
{
cout<<"第"<<i+1<<"个元素的数据:"<<tmp->data<<endl; 
i++;
tmp=tmp->next;
}
}
void menu()
{
cout<<"*******************************************"<<endl;
cout<<"1.构造一个带头结点的空链表 "<<endl;
cout<<"2.建立具有n的元素链表"<<endl;
cout<<"3.取第i个数据元素"<<endl;
cout<<"4.在链表中查找值为e的元素"<<endl;
cout<<"5.在第i位插入数据元素"<<endl;
cout<<"6.删除第i个数据元素"<<endl;
cout<<"7.求链表的表长"<<endl;
cout<<"8.判断链表是否为空"<<endl;
cout<<"9.清空链表"<<endl;
cout<<"10.销毁链表"<<endl;
cout<<"11.遍历链表"<<endl;
cout<<"12.退出"<<endl;
cout<<"*******************************************"<<endl;
}
int main()
{
int choice;
LinkList L;
int i2,e2,e,i1,e1;
int t,n,x1;
int x,data;
while(1)
{
menu();
cout<<"请输入你的选择"<<endl;
cin>>choice;
switch(choice)
{
case 1:
InitList(L);
cout<<"成功初始化"<<endl;
break;
case 2:
cout<<"请选择你想要创建链表的方法"<<endl;
cout<<"1.是头插法\t2.是尾插法"<<endl;
cin>>t;
if(t==1)
{
int a1[N];
cout<<"请输入需要多少个节点"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"请输入第"<<i+1<<"个节点的数据"<<endl;
cin>>a1[i];
} 
CreateList_F(L,a1,n);
}
else
{
int a2[N];
cout<<"请输入需要多少个节点"<<endl;
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"请输入第"<<i+1<<"个节点的数据"<<endl;
cin>>a2[i];
} 
CreateList_L(L,a2,n);
}
break;
case 3:
cout<<"输入要查找的位置"<<endl;
cin>>x; 
GetElem_L(L,x,data);
cout<<"第"<<x+1<<"个元素的值为："<<data<<endl;
break;
case 4:
cout<<"输入值"<<endl;
cin>>e;
x1=LocateElem_L(L,e);
cout<<"位置为："<<x1<<endl;
break;
case 5:
cout<<"请输入要插入哪里跟节点的数据"<<endl;
cin>>i1>>e1;
ListInsert_L(L,i1,e1);
break;
case 6:
cout<<"请输入要删除哪个节点"<<endl;
cin>>i2;
ListDelete(L,i2,e2);
cout<<"删除成功，原来的节点的数据为"<<e2<<endl;
break;
case 7:
cout<<"长度为"<<ListLength(L)<<endl;
break;
case 8:
if(isEmpty(L)) cout<<"链表为空"<<endl;
else cout<<"链表不为空"<<endl;
break;
case 9:
CleanList(L);
cout<<"清空成功"<<endl;
break;
case 10:
DestoryList(L);
cout<<"销毁成功"<<endl; 
break; 
case 11:
ListTraverse(L);
break;
case 12:
cout<<"成功退出"<<endl;
exit(0);
default:
cout<<"请重新输入"<<endl; 
break;
}
}
}

五、测试结果

测试样例：创建4个节点数据分别为1、2、3、4 其余测试基于以上4个节点

图一

图二

图三

图四

图五

图六

图七

图八

图九

图十

图11

图十二

六、总结

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

#ifndef _LIST_h_
#define _LIST_h_
//链表中的数据结构
typedef struct Link_data
{
    int a;   
    int b;
}Node_data;
//链表节点结构
typedef struct Link_node
{
    Node_data    data;   
    struct Link_node  *pNext;
}Node;
Node* CreateList(void);
Node* FindNodeByGlobalIndex(Node *pHead, int iGlobalIndex);
Node* Insert2ListTail(Node *pHead, Node_data  *pAutoInfo);
int RemoveList(Node *pHead);
void  PrintList(Node *pHead);
int DeleteList (Node *pHead,int x);
void ReverseList(Node *pHead);
void SortList(Node *pHead);
#endif

#include <string.h>
#include <malloc.h>
#include<stdio.h>
#include"list.h"
/*************************************************
Function      : CreateList
Description   : 创建链表头节点
Return        : 链表的头指针
*************************************************/
Node* CreateList(void)
{
    Node *pHead = NULL;
    //申请的头指针
    pHead = (Node *)malloc(sizeof(Node));
    //判断是否申请成功
    if (NULL == pHead)
    {
        return NULL;
    }
    //针对具体结构进行初始化
    pHead->data.a = 0;
    pHead->data.b = 0;
    pHead->pNext = NULL;
    return pHead;
}
/*************************************************
Function      : FindNodeByGlobalIndex
Description   : 根据指定参数，查找某个节点
Input         : pHead 链表的头节点指针
                要查找的学生ID
Return        : 正确:返回指定节点的指针
                失败:返回空指针
*************************************************/
Node* FindNodeByGlobalIndex(Node *pHead, int iGlobalIndex)
{
    Node *pNode = NULL;
    if ((NULL == pHead) || (iGlobalIndex < 0))
    {
        return NULL;
    }
    pNode = pHead->pNext;
    while ((NULL != pNode))
    {
        if (pNode->data.a == iGlobalIndex)
        {
            break;
        }
        pNode = pNode->pNext;
    }
    return pNode;
}
/*************************************************
Function      : Insert2ListTail
Description   : 向链表中尾部插入某个节点
Input         : pHead        链表的头节点指针
                pStudentInfo 学生信息
Return        : 正确:返回头节点指针
                失败:返回空指针
*************************************************/
Node* Insert2ListTail(Node *pHead, Node_data  *pAutoInfo)
{
    Node* pNode = NULL;
    Node* pNewNode = NULL;
    if ((NULL == pHead) || (NULL == pAutoInfo))
    {
        return NULL;
    }
    pNode = pHead;
    while (pNode->pNext != NULL)
    {
        pNode = pNode->pNext;
    }
    pNewNode = (Node *)malloc(sizeof(Node));
    if (NULL == pNewNode)
    {
        return NULL;
    }
    pNode->pNext = pNewNode;
    pNewNode->pNext = NULL;
    memcpy(&(pNewNode->data), pAutoInfo, sizeof(Node_data ));
    return pHead;
}
/*************************************************
Function      : RemoveList
Description   : 删除整个链表
Input         : pHead 链表的头节点指针
Return        : 正确: 1
                失败: 0
*************************************************/
int RemoveList(Node *pHead)
{
    Node *pNode = NULL;
    Node *pb = NULL;
    if (NULL == pHead)
    {
        return 0;
    }
    pNode = pHead;
    pb = pNode->pNext;
    if (NULL == pb)
    {
        free(pNode);
    }
    else
    {
        while (NULL != pb)
        {
            free(pNode);
            pNode = pb;
            pb = pb->pNext;
        }
        free(pNode);
    }
    pNode = NULL;
    return 1;
}
/*************************************************
Function      : PrintList
Description   : 打印整个链表
Input         : pHead 链表的头节点指针
Return        : 
*************************************************/
void  PrintList(Node *pHead)
{
    Node *pNode = NULL;
    if (NULL == pHead)
    {
        return ;
    }
    pNode = pHead->pNext;
    while ((NULL != pNode))
    {
        printf("\r\n a is %d   b is  %d",pNode->data.a,pNode->data.b);
        pNode = pNode->pNext;
    }
    return ;
}
/*************************************************
Function      : DeleteList
Description   : 删除链表的一个结点，删除条件该节点的a值与x相同
Input         : 
Return        : 
*************************************************/
int DeleteList (Node *pHead,int x)
{
    Node *pNode = NULL;
    Node *pre = NULL;
    if (NULL == pHead  )
    {
        return 0;
    }
    pNode = pHead->pNext;
    pre = pHead;
    while(pNode)
    {
        if(pNode->data.a == x)//删除条件
        {
            pre->pNext = pNode->pNext;
            free(pNode);
            return 1;
        }
        else
        {
            pre = pNode;
        }
        pNode = pNode->pNext;
    }
    return 0;
}
/*************************************************
Function      : ReverseList
Description   : 链表反转
Input         : 
Return        : 
*************************************************/
void ReverseList(Node *pHead)
{
    Node* p = pHead->pNext;
    Node* q = p->pNext;
    Node* t = NULL;
    if(NULL == pHead || NULL == pHead->pNext)
    {
        return;
    }
    while(NULL != q)
    {
        t = q->pNext;
        q->pNext = p;
        p = q;
        q = t;
    }
    pHead->pNext->pNext = NULL;
    pHead->pNext = p;
}
/*************************************************
Function      : SortList
Description   : 按a值排序
Input         : 
Return        : 
*************************************************/
void SortList(Node *pHead)
{
    Node* pi = pHead->pNext;
    Node* pj = pi->pNext;
    Link_data temp;
    memset(&temp,0,sizeof(Link_data));
    if(NULL == pHead  || NULL == pHead->pNext)
    {
        return;
    }
    for(;pi != NULL;pi=pi->pNext)
    {
        for(pj = pi->pNext;pj != NULL;pj=pj->pNext)
        {
            if(pj->data.a < pi->data.a)
            {
                temp = pj->data;
                pj->data = pi->data;
                pi->data = temp;
            }
        }
    }
}

#include<stdio.h>
#include<string.h>
#include"list.h"
Node * g_LinkHead = NULL;
int main()
{
    Node_data data1;
    Node_data data2;
    Node_data data4;
    Node *data3 = NULL;
    memset(&data1, 0, sizeof(Node_data));
    memset(&data2, 0, sizeof(Node_data));
    memset(&data4, 0, sizeof(Node_data));
    data1.a=3;
    data1.b=3;
    data2.a=2;
    data2.b=4;
    data4.a=5;
    data4.b=6;
    g_LinkHead=CreateList();
    Insert2ListTail(g_LinkHead,&data1);
    Insert2ListTail(g_LinkHead,&data2);
    Insert2ListTail(g_LinkHead,&data4);
    PrintList(g_LinkHead);
    //data3 = FindNodeByGlobalIndex(g_LinkHead, 2);
    //printf("\r\n data3.a %d data3.b %d",data3->data.a,data3->data.b);
    printf("\n\n");
    //(void) ReverseList(g_LinkHead);
    (void) SortList(g_LinkHead);
    PrintList(g_LinkHead);
    /*if(DeleteList (g_LinkHead,4))
    {
        PrintList(g_LinkHead);
    }
    PrintList(g_LinkHead);*/
    /*if(RemoveList(g_LinkHead))
    {
        g_LinkHead = NULL;
    }
    PrintList(g_LinkHead);*/
    return 0;
}

到此这篇关于带头结点的链表的基本操作(超详细）的文章就介绍到这了,更多相关带头结点的链表内容请搜索软件开发网以前的文章或继续浏览下面的相关文章希望大家以后多多支持软件开发网！

链表

1024 个赞