C语言中单链表(不带头结点)基本操作的实现详解

目录
  • 一、单链表的概念
  • 二、单链表的基本操作
    • 1.创建单个结点
    • 2.创建具有n个结点的链表
    • 3.打印单链表
    • 4.尾插
    • 5.尾删
    • 6.头插
    • 7.头删
    • 8.查找某个结点
    • 9.在某个结点后面插入
    • 10.在某个结点前面插入
    • 11.删除某个位置后面的结点
    • 12.删除某个结点
    • 13.销毁单链表
  • 三、测试代码

通过对顺序表的学习,我们可以发现顺序表有以下几点缺陷:

1.空间不够时需要扩容,扩容尤其是用realloc进行异地扩容时,是有一定代价的,其次还可能存在一定空间浪费。

2.头部或者中间插入删除,需要挪动数据,效率低下。

那我们可以对其所具有的缺陷进行优化:可以按需申请空间同时插入删除时不挪动数据。而单链表就符合这些优化所具有特点。但是我们要注意的是单链表具有这些优点并不代表链表就可以完全替代顺序表。

一、单链表的概念

链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

从上图可以看出,链式结构在逻辑上是连续的,但是在物理上不一定连续,物理结构中指针域存储的是下一个结点的地址;而且链式结构的结点一般都是从堆上申请出来的;从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续。链表存储数据的区域可分为数据域和指针域:

用代码表示链表中的数据域和指针域如下:

typedef int STLDataType;
typedef struct SListNode
{
    SLTDataType data;
    struct SListNode* next;
}STLNode;

思考:为什么在申请的时候需要申请堆上的空间?因为堆上申请的空间存储数据的时候不会因为函数销毁而销毁,堆上的空间需要的时候就申请,不需要的时候就释放;函数栈帧上开辟的空间存储的数据会因为函数栈帧的销毁而释放,后面在进行尾插和头插时候新的结点不能链接到表上。

二、单链表的基本操作

1.创建单个结点

SLTNode* BuySLTNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
    if (newnode == NULL)
    {
        perror("BuySLTNode malloc");
        exit(-1);
    }
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

2.创建具有n个结点的链表

SLTNode* CreateSList(int n)
{
    int i = 0;
    SLTNode* ptail = NULL,*phead = NULL;
    for (i = 0; i < n; i++)
    {
        SLTNode* newnode = BuySLTNode(i);
        if (phead == NULL)
        {
            ptail = phead = newnode;
        }
        else
        {
            ptail->next = newnode;
            ptail = newnode;
        }
    }
    return phead;
}
//void CreateSList(SLTNode** pphead, int n)
//{
//    int i = 0;
//    SLTNode* ptail = NULL;
//    for (i = 0; i < n; i++)
//    {
//        SLTNode* newnode = BuySLTNode(i);
//        if (*pphead == NULL)
//        {
//            ptail = *pphead = newnode;
//        }
//        else
//        {
//            ptail->next= newnode;
//            ptail = newnode;
//        }
//    }
//}

上述代码中提供了两种实现方式,没有注释的是返回头指针的,注释内容是没有返回值,形参使用的是二级指针改变头指针指向的地址。

3.打印单链表

void SLTPrint(SLTNode* phead)
{
    SLTNode* tail = phead;
    while (tail)
    {
        printf("%d ", tail->val);
        tail = tail->next;
    }
    printf("\n");
}

4.尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
    SLTNode* tail = *pphead;
    SLTNode* newnode = BuySLTNode(x);
    if (*pphead == NULL)
    {
        *pphead = newnode;
    }
    else
    {
        while (tail->next)
        {
            tail = tail->next;
        }
        tail->next = newnode;
    }
}

尾插时,要注意当单链表的头结点为空的时候,要先将新结点作为头结点。因为当头结点为空时,需要改变头指针,所以传过来的为二级指针(也可以使用一级指针,不过此时要有返回值),要想改变SLTNode*的值,就要传递它的地址即SLTNode**类型。

5.尾删

void SLTPopBack(SLTNode** pphead)//尾删
{
    assert(*pphead);
    if ((*pphead)->next==NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        SLTNode* tail = *pphead;
        SLTNode* prev = NULL;
        while (tail->next)
        {
            prev = tail;
            tail = tail->next;
        }
        free(tail);
        prev->next = NULL;
    }
}

尾删时也要注意区分是否为头结点;同时注意删除后,要将其置空prev->next = NULL。

6.头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
    SLTNode* newnode = BuySLTNode(x);
    newnode->next = *pphead;
    *pphead = newnode;
}

7.头删

void SLTPopFront(SLTNode** pphead)//头删
{
    assert(*pphead);
    SLTNode* nextnode = (*pphead)->next;
    free(*pphead);
    *pphead = nextnode;
}

头插和头删是单链表的优势,尾插和尾删是顺序表的优势。同时在尾删时注意将*pphead加上括号用来区分优先级,否则会报错。

8.查找某个结点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某个数并返回所在位置
{
    SLTNode* tail = phead;
    while (tail)
    {
        if (tail->val == x)
        {
            return tail;
        }
        tail = tail->next;
    }
    return NULL;
}

注意循环条件,当循环条件写为while(tail->next)时,会有空指针的风险,同时还会漏掉最后一个结点。

9.在某个结点后面插入

void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某个结点的后面插入某个数
{
    assert(pos);
    SLTNode* newnode = BuySLTNode(x);
    SLTNode* tail = pos->next;
    pos->next = newnode;
    newnode->next = tail;
}

10.在某个结点前面插入

void SLTInsert(SLTNode** pphead,SLTNode* pos, SLTDataType x)//在某个结点的前面插入某个数
{
    assert(pos);
    SLTNode* newnode = BuySLTNode(x);
    if (pos == *pphead)
    {
        /*newnode->next = *pphead;
        *pphead = newnode;*/
        SLTPushBack(pphead, x);
    }
    else
    {
        SLTNode* tail = *pphead;
        while (tail->next != pos)
        {
            tail = tail->next;
        }
        tail->next = newnode;
        newnode->next = pos;
    }
}

11.删除某个位置后面的结点

void SLTEraseAfter(SLTNode* pos)//删除pos位置之后的那个位置
{
    assert(pos);
    if (pos->next == NULL)
    {
        return;
    }
    else
    {
        SLTNode* tail = pos->next;
        pos->next = tail->next;
        free(tail);
    }
}

12.删除某个结点

void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
{
    assert(pos);
    SLTNode* tail = *pphead;
    if (pos == *pphead)
    {
        SLTNode* nextNode = (*pphead)->next;
        free(*pphead);
        *pphead = nextNode;
    }
    else
    {
        while (tail->next != pos)
        {
            tail = tail->next;
        }
        tail->next = pos->next;
        free(pos);
    }
}

13.销毁单链表

void SLTDestroy(SLTNode** pphead)//销毁
{
    assert(*pphead);
    SLTNode* tail = *pphead;

    while (tail)
    {
        SLTNode* next = tail->next;
        free(tail);
        tail = next;
    }
    *pphead = NULL;
}

注意最后要将头结点置空。

三、测试代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDataType;
typedef struct SList {
	struct Slist* next;
	SLTDataType val;
}SLTNode;
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("BuySLTNode malloc");
		exit(-1);
	}
	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
SLTNode* CreateSList(int n)
{
	int i = 0;
	SLTNode* ptail = NULL, * phead = NULL;
	for (i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}
//void CreateSList(SLTNode** pphead, int n)
//{
//	int i = 0;
//	SLTNode* ptail = NULL;
//	for (i = 0; i < n; i++)
//	{
//		SLTNode* newnode = BuySLTNode(i);
//		if (*pphead == NULL)
//		{
//			ptail = *pphead = newnode;
//		}
//		else
//		{
//			ptail->next= newnode;
//			ptail = newnode;
//		}
//	}
//}
void SLTPrint(SLTNode* phead)
{
	SLTNode* tail = phead;
	while (tail)
	{
		printf("%d ", tail->val);
		tail = tail->next;
	}
	printf("\n");
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{
	SLTNode* tail = *pphead;
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPopBack(SLTNode** pphead)//尾删
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		SLTNode* prev = NULL;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//头插
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopFront(SLTNode** pphead)//头删
{
	assert(*pphead);
	SLTNode* nextnode = (*pphead)->next;
	free(*pphead);
	*pphead = nextnode;
}
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找某个数并返回所在位置
{
	SLTNode* tail = phead;
	while (tail)
	{
		if (tail->val == x)
		{
			return tail;
		}
		tail = tail->next;
	}
	return NULL;
}
void SLInsertAfter(SLTNode* pos, SLTDataType x)//在某个结点的后面插入某个数
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	SLTNode* tail = pos->next;
	pos->next = newnode;
	newnode->next = tail;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//在某个结点的前面插入某个数
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	if (pos == *pphead)
	{
		/*newnode->next = *pphead;
		*pphead = newnode;*/
		SLTPushBack(pphead, x);
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = newnode;
		newnode->next = pos;
	}
}
void SLTEraseAfter(SLTNode* pos)//删除pos位置之后的那个位置
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* tail = pos->next;
		pos->next = tail->next;
		free(tail);
	}
}
void SLTErase(SLTNode** pphead, SLTNode* pos)//删除pos位置
{
	assert(pos);
	SLTNode* tail = *pphead;
	if (pos == *pphead)
	{
		SLTNode* nextNode = (*pphead)->next;
		free(*pphead);
		*pphead = nextNode;
	}
	else
	{
		while (tail->next != pos)
		{
			tail = tail->next;
		}
		tail->next = pos->next;
		free(pos);
	}
}
void SLTDestroy(SLTNode** pphead)//销毁
{
	assert(*pphead);
	SLTNode* tail = *pphead;

	while (tail)
	{
		SLTNode* next = tail->next;
		free(tail);
		tail = next;
	}
	*pphead = NULL;
}
void TestSL()
{
	SLTNode* plist = CreateSList(2);
	/*SLTNode* plist = NULL;
	CreateSList(&plist,10);//没有返回值
	SLTPrint(plist);*/
	SLTPushBack(&plist, 600);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPushFront(&plist, 100);
	SLTPushFront(&plist, 200);
	SLTPushFront(&plist, 300);
	SLTPushFront(&plist, 400);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPopFront(&plist);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist, 600);
	if (pos)
	{
		SLInsertAfter(pos, 700);
		SLTInsert(&plist, pos, 500);
		SLTEraseAfter(pos);
		//SLTErase(&plist, pos);

	}
	SLTPrint(plist);
	SLTDestroy(&plist);
	SLTPrint(plist);
}
int main()
{
	TestSL();
	return 0;
}

以上就是C语言中单链表(不带头结点)基本操作的实现详解的详细内容,更多关于C语言单链表的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言实现单链表的基本操作分享

    目录 导语 单链表 单链表的特点 定义 初始化操作 头插法 尾插法 删除第i个元素 在第i个位置插入 导语 无论是顺序存储结构还是链式存储结构,在内存中进行存放元素的时候,不仅需要存放该元素的相关信息,还需要存放该元素和其他元素之间的关系,而我们之前所学的顺序表“与生俱来”的物理结构自然地能够表达出元素和元素之间的关系,不需要额外的信息去表达元素和元素之间的关系,而对于链式存储这种非顺序存储的结构,需要额外附加指针去表示这种关系. 单链表 每个结点除了存放数据元素外,还要存储指向下一个节点的指针

  • C语言单链表常见操作汇总

    C语言的单链表是常用的数据结构之一,本文总结了单链表的常见操作,实例如下: #include<stdio.h> #include<stdlib.h> //定义单链表结构体 typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; }LNode,*LinkList; //创建单链表 void Build(LinkList L) { int n; LinkList p,q; p=L; pr

  • 用C语言实现单链表的各种操作(二)

    上一篇文章<用C语言实现单链表的各种操作(一)>主要是单链表的一些最基本的操作,下面,主要是一些其他的典型的算法和测试程序. 复制代码 代码如下: /* 对单链表进行排序处理*/struct LNode *sort(struct LNode *head){  LinkList *p;  int n,i,j;  int temp;  n = ListLength(head);  if(head == NULL || head->next == NULL)    return head; 

  • ​​​​​​​C语言实现单链表基本操作方法

    目录 存储结构 基本功能 头插法创建单链表 尾插法创建单链表 获取指定位置的元素 在指定位置插入元素 删除指定位置的元素 获取单链表的长度 合并两个非递减的单链表 晴链表 遍历打印单链表 附上完整代码 存储结构 typedef int dataType://爱护据类型 typedef struct Node { DataType data; // 结点数据 struct Node *next; // 指向下一个结点的指针 } Node, *LinkList; 基本功能 头插法创建单链表void

  • 用C语言实现单链表的各种操作(一)

    最近,从新复习了一下数据结构中比较重要的几个部分,现在把自己的成果记录下来,主要就是仿照严蔚敏的<数据结构>(C 语言版),中的例子和后面的习题进行改编的.首先,是单链表的各种实现,其中,包含了一些常考的知识点.例如,单链表的逆置,单链表的合并,找到单链表的中间节点等的算法实现.下面这个是单链表的结构体的定义: 复制代码 代码如下: typedef struct LNode{ ElemType data; struct LNode *next;}LinkList; 下面的基本的单链表的操作:其

  • C语言数据结构之单链表操作详解

    目录 1.插入操作 2.删除操作 3.查找操作 4.修改操作 5.完整代码 1.插入操作 (1)创建一个新的要插入的结点 (2)将新结点的 next 指针指向插入位置后的结点 (3)将插入位置前的节点指针 next 指向新的结点 注意:步骤(2)(3)的顺序不能颠倒,否则会导致插入位置后的部分链表丢失. 插入位置一共分三种,分别是头部插入.中间插入和尾部插入. 如图: 代码: link* insertElem(link* p,int elem,int pos){ link* temp = p;/

  • C语言中单链表(不带头结点)基本操作的实现详解

    目录 一.单链表的概念 二.单链表的基本操作 1.创建单个结点 2.创建具有n个结点的链表 3.打印单链表 4.尾插 5.尾删 6.头插 7.头删 8.查找某个结点 9.在某个结点后面插入 10.在某个结点前面插入 11.删除某个位置后面的结点 12.删除某个结点 13.销毁单链表 三.测试代码 通过对顺序表的学习,我们可以发现顺序表有以下几点缺陷: 1.空间不够时需要扩容,扩容尤其是用realloc进行异地扩容时,是有一定代价的,其次还可能存在一定空间浪费. 2.头部或者中间插入删除,需要挪动

  • C语言中单链表的基本操作指南(增删改查)

    目录 1.链表概述 2.链表的基本使用 2.0 准备工作 2.1 创建节点(结构体) 2.2 全局定义链表头尾指针 方便调用 2.3 创建链表,实现在链表中增加一个数据(尾添加)----增 2.4 遍历链表 -----查 2.5 查询指定的节点 (遍历 一个个找) 2.6 链表清空------全部删除 2.7.在指定位置插入节点 ----在指定位置增 2.8尾删除----删 2.9 删除头------删 2.10 删除指定节点 3. 测试主程序 总结 1.链表概述 链表是一种常见的数据结构.它与

  • C语言中带头双向循环链表基本操作的实现详解

    目录 一.概念与结构 二.基本操作的实现 1.创建结点 2.初始化链表 3.打印链表 4.尾插 5.尾删 6.头插 7.头删 8.查找某个数并返回其指针 9.在某个位置之前插入 10.删除某个位置 11.判断链表是否为空 12.计算链表中有效值的个数 13.销毁链表 三.测试代码 一.概念与结构 无头单向非循环链表结构简单,一般不会单独用来存数据.实际中更多的是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.而带头双向循环链表的结构较为复杂,一般用在单独存储数据.实际中使用的链表数据结构,都

  • 详解Go语言中单链表的使用

    目录 链表 单链表结构 创建节点 遍历链表 头插法 尾插法 遍历方法 链表长度 链表转数组 数组转链表 链表 一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域.使用链表结构可以避免在使用数组时需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理.但是链表失去

  • C语言实现顺序表的基本操作的示例详解

    目录 一.认识顺序表 1.线性表 2.顺序表的概念及结构 二.顺序表的基本操作(接口实现) 1.初始化顺序表 2.打印顺序表 3.尾插 4.尾删 5.扩容 6.头插 7.头删 8.任意位置插入 9.任意位置删除 10.查找某个数的位置 三.顺序表演示及代码(含源码) 1.演示效果 2.完整源代码 一.认识顺序表 1.线性表 线性表是n个具有相同特性的数据元素的有限序列,线性表是一种在实际中广泛使用的数据结构,常见的线性表有顺序表.链表.栈.队列.字符串……线性表在逻辑上是线性结构,也就是说是一条

  • C语言线性表的链式表示及实现详解

    目录 前言 代码实现 1. 单链表的结点构造 2. 构造一个空的头结点 3. 对线性表进行赋值 4.对线性表进行销毁 5.对线性表进行重置 6.判断线性表是否为空 7.获取线性表的长度 8.获取线性表某一位置对应的元素 9.在线性表某一位置插入元素 10.删除线性表某一位置的元素 11.求线性表某一元素的前驱 12.求线性表某一元素的后继 13.打印线性表 运行结果演示 源码 前言 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,而线性表的链式存储特点则是用一组任意的存储

  • C++实现带头双向循环链表的示例详解

    目录 一.双向循环链表与顺序表的区别 二.List.h 三.List.c 1.带头双向循环链表的初始化 2.带头双向循环链表的销毁 3.带头双向循环链表的打印 4.动态开辟一个节点 5.带头双向循环链表的判空 6.带头双向循环链表的尾插.尾删 7.带头双向循环链表的头插.头删 8.带头双向循环链表的长度 9.带头双向循环链表的查找.任意位置插入.删除 一.双向循环链表与顺序表的区别 不同点 顺序表 双向带头循环链表 在内存中的存储方式 连续存储 不一定连续 随机访问 支持随机访问 不支持随访问

  • C语言 数据结构之数组模拟实现顺序表流程详解

    目录 线性表和顺序表 线性表 顺序表 静态顺序表 动态顺序表 代码已经放在Gitee上,需要可以小伙伴可以去看看 用C语言数组模拟实现顺序表 Gitee 线性表和顺序表 线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列,这是我们广泛使用的数据结构. 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储. 常见的线性表:顺序表.链表.栈.队列.字符串- 顺序表 顺序表是用一段物理地址连

  • C语言数据结构二叉树之堆的实现和堆排序详解

    目录 一.本章重点 二.堆 2.1堆的介绍 2.2堆的接口实现 三.堆排序 一.本章重点 堆的介绍 堆的接口实现 堆排序 二.堆 2.1堆的介绍 一般来说,堆在物理结构上是连续的数组结构,在逻辑结构上是一颗完全二叉树. 但要满足 每个父亲节点的值都得大于孩子节点的值,这样的堆称为大堆. 每个父亲节点的值都得小于孩子节点的值,这样的堆称为小堆. 那么以下就是一个小堆. 百度百科: 堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆. 若将和此次序列对应的一维数

  • C语言顺序表的基本结构与实现思路详解

    目录 一.顺序表的概念与结构 1.线性表的解释 2.顺序表概念解释 二.顺序表的思路及代码实现详解 1.静态顺序表的实现 2.动态顺序表思路及代码实现 2.1 动态顺序表的整体思路 2.2 定义结构体的实现 2.3 初始化结构体 2.4 结构体打印 2.5 检查数组容量 2.6 头插 2.7 尾插 2.8 头删 2.9 尾删 2.10 任意删除 2.11 任意插入 2.12 空间释放 三.顺序表代码整合 SeqList.h SeqList.c test.c 一.顺序表的概念与结构 1.线性表的解

随机推荐