1. Toy模板网首页
  2. > Toy博客

【数据结构】单链表(一)

8月前 作者：日出等日落 分类：Toy博客 阅读(30) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】单链表(一)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

作者：日出等日落

专栏：数据结构

想变成仲夏夜的一只萤火虫，只要抓住你的注意力，就已经满足了。

【数据结构】单链表(一)

目录

前言：

 单链表的结构 ：

 逻辑结构：

物理结构：

BuySLTNode（动态申请一个结点）： 

 CreateSList(//循环创建结点)：

SLTPrint（单链表打印）：

 单链表的功能： 

SLTPushBack尾插:

plist不为NULL：

 plist为NULL：

SLTPopBack（尾删）：

SLTPushFront（头插）：

SLTPopFront（头删）：

SLTFind(查找)：

SLTInsertAfter（在pos位置之后插入）：

  SLTInsertFront（在pos位置之前插入）：

SLTEraseAfter（删除pos之后的位置）：

 SLTErase（删除pos位置）：

SLTDestory（释放空间）： 

完整代码： 

text.c：

SList.c:

SList.h:

前言：

我们之前学习了顺序表，那么，朋友们知道顺序表有什么缺陷吗？

顺序表的缺陷：

  1. 空间不够的时候，需要扩容。扩容（尤其是异地扩容）是由一定价值的。其次还可能存在一定的空间浪费。
  2. 头部或者中部插入删除，需要挪动数据，效率低下。

优化方案：

  1. 按需申请释放
  2. 不需要挪动数据

这就需要链表来实现

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

简单来说，单链表是一种链式存取的 数据结构 ，用一组地址任意的存储单元 存放线性表中的数据元素。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素) + 指针 (指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的 地址 数据。 链表中的数据是以结点来表示的，每个结点的构成：元素 ( 数据元素 的映象) + 指针 (指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。 以“结点的序列”表示线性表称作 线性链表 （单链表），单链表是链式存取的结构。 链接方式存储的线性表简称为链表（Linked List）。 ② 链表中结点的逻辑次序和物理次序不一定相同。

 单链表的结构 ：

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;//数据元素
	struct SListNode* next;//指向下一个与本结构体相同的结构体变量的指针
}SLTNode;

 逻辑结构：

【数据结构】单链表(一)

物理结构：

【数据结构】单链表(一)

BuySLTNode（动态申请一个结点）： 

函数实现：

//动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	return newnode;
}

 CreateSList(//循环创建结点)：

【数据结构】单链表(一)

首先，为了防止最后找不到头指针，我们再定义一个结构体变量ptail来进行后续的操作实现

【数据结构】单链表(一)

这个图中的代码是四个结点连接的操作，可以结合图理解一下。

那么在实际操作中，实现n个创建利用for循环来实现，利用BuyTNode创建动态结构体，我们再将下一个结构体的地址传给结构体的next指针以此类推.....

下面是循环创建结点的代码实现：

 函数实现：

//循环创建结点
SLTNode* CreateSList(int n)
{
	SLTNode* phead = NULL, * ptail = NULL;
	for (int i = 0; i < n; ++i)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (phead == NULL)
		{
			phead = ptail = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}

SLTPrint（单链表打印）：

// 单链表打印
void SLTPrint(SLTNode *phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

 单链表的功能： 

SLTPushBack尾插:

plist不为NULL：

尾插需要先找尾部，即NULL的地方，然后将newnode插到null后面

注：

  • tail为NULL和tail->next为NULL对于循环条件来说是不一样的。
  • tail为NULL代表没有这个结构体
  • tail->next为NULL代表没有下一个结构体了
void SLTPushBack(SLTNode* phead, SLDataType x)
{//尾插

    SLTNode* newnode = BuySLTNode(x);
    SLTNode* tail = phead;
    while (tail->next)
    {
        tail = tail->next;
    }
        tail->next = newnode;
}

 plist为NULL：

注：这里要传地址

因此我们要改变NULL这个指针，我们需要传SLTNode**pphead进去，那我们*pphead就可以改变NULL的值了！

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

		tail->next = newnode;
	}
}

SLTPopBack（尾删）：

找到尾部next指向为NULL的，将其释放掉，然后创建结构体第三变量prev记录前一个位置的next，将prev->next=NULL；

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);

	if ((*pphead) == 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;
	}
}

SLTPushFront（头插）：

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

SLTPopFront（头删）：

void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;

}

SLTFind(查找)：

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

SLTInsertAfter（在pos位置之后插入）：

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

【数据结构】单链表(一)

  SLTInsertFront（在pos位置之前插入）：

有两种情况：

  • pos为链表第一个，那就相当于头插；
  • 【数据结构】单链表(一)
  • 除去第一个以外的位置：

         

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

SLTEraseAfter（删除pos之后的位置）：

找pos位置的下一个位置将它赋给一个指针nextNode，将pos的next连接到nextNode的下一个结构体的位置，这样就跳过这个指针了，最后释放这个被跳过的空间！！！

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode);
	}
}

 SLTErase（删除pos位置）：

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

SLTDestory（释放空间）： 

void SLTDestory(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur=next;
	}
	*pphead = NULL;
}

完整代码： 

首先，我将通讯录分成了三个部分：

1、text.c                   //通讯录的菜单以及主函数

2、SList.h             //结构体和函数的声明，以及头文件的引用

3、SList.c              //通讯录各种功能函数的实现  文章来源地址https://www.toymoban.com/news/detail-428284.html

text.c：

#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"
TextSList1()
{
	SLTNode* plist = CreateSList(10);
	SLTPrint(plist);

}

TextSList2()
{
	SLTNode* plist =NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);

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


}

TextSList3()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 100);
	SLTPushFront(&plist, 200);
	SLTPushFront(&plist,500);
	SLTPushFront(&plist, 800);
	SLTPrint(plist);
	SLTPopFront(&plist);
	SLTPrint(plist);

}

TextSList4()
{
	SLTNode* plist = NULL;
	SLTPushFront(&plist, 100);
	SLTPushFront(&plist, 200);
	SLTPushFront(&plist, 500);
	SLTPushFront(&plist, 800);
	SLTPrint(plist);
	SLTNode* pos = SLTFind(plist,200);
	if (pos)
	{
		printf("找到了\n");
	}
	else
	{
		printf("找不到\n");
	}
}

TextSList5()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPrint(plist);
	SLTNode* p = SLTFind(plist, 200);
	if (p)
	{
		SLTInsertAfter(p, 2);
		printf("找到了\n");
		SLTPrint(plist);
		SLTEraseAfter(p);
		SLTPrint(plist);
		SLTErase(&plist, p);
		SLTPrint(plist);
		
	}
	else
	{
		printf("找不到\n");
	}

}
TextSList6()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 100);
	SLTPushBack(&plist, 200);
	SLTPushBack(&plist, 300);
	SLTPushBack(&plist, 400);
	SLTPrint(plist);
	SLTNode* p = SLTFind(plist, 200);
	if (p)
	{
		SLTInsert(&plist, p, 1);
		SLTPrint(plist);
		SLTDestory(&plist);
		SLTPrint(plist);
	}
	else
	{
		printf("找不到了\n");
	}
}

int main()
{
	TextSList6();
	return 0;
}

SList.c:

#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"
//动态申请一个结点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail:");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	return newnode;
}

//循环创建结点
SLTNode* CreateSList(int n)
{
	SLTNode* phead = NULL, * ptail = NULL;
	for (int i = 0; i < n; ++i)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (phead == NULL)
		{
			phead = ptail = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}
// 单链表打印
void SLTPrint(SLTNode *phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

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

		tail->next = newnode;
	}
}

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);

	if ((*pphead) == 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* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;

}

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode);
	}
}
// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPushFront(pphead,x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	if (pos==*pphead)
	{
		SLTPopFront(pphead);	
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

void SLTDestory(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur=next;
	}
	*pphead = NULL;
}

SList.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

SLTNode* BuySLTNode(SLTDataType x);
SLTNode* CreateSList(int n);
void SLTPrint(SLTNode* phead);

void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopFront(SLTNode** pphead);

SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SLTEraseAfter(SLTNode* pos);

// 在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
// 删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos);

void SLTDestory(SLTNode** pphead);

到了这里，关于【数据结构】单链表(一)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 数据结构入门——单链表

    目录 前言 链表的定义 链表的创建 头插法创建链表 尾插法创建链表 链表的删除 在头部删除元素 在尾部删除元素 查找固定元素 在链表中插入元素 在pos位置前插入 在pos位置后插入 删除链表结点 删除pos位置的结点 删除pos后的结点 链表的销毁 写在最后 前面我们学习了顺序表

    2024年02月20日
    浏览(29)
  • 数据结构·单链表

    数据结构·单链表

            不可否认的是，前几节我们讲解的顺序表存在一下几点问题：         1. 中间、头部的插入和删除，需要移动一整串数据，时间复杂度O(N)         2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗         3. 增容一般是2倍的增长，这势

    2024年01月25日
    浏览(64)
  • 【数据结构】单链表（超全）

    【数据结构】单链表（超全）

    前言：  上一次我们分享了线性表中的一种结构顺序表，它存在着一些其缺点，比如：在中间位置或者头部进行元素插入或者删除的时候时间复杂度是 O ( N ) O(N) O ( N ) 效率比较低，并且顺序表在扩容的时候也存在时间和空间上的消耗，由于我们每次都是按照二倍来扩的，那

    2024年02月11日
    浏览(30)
  • 数据结构-单链表

    数据结构-单链表

    概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。  从以上图片可以看出： 1.链式结构在逻辑上是连续的，但在物理上不一定是连续的。 2.现实中的节点一般是在堆上申请出来的。 3.从堆上申请的空间，

    2024年02月05日
    浏览(30)

  • 数据结构:单链表

    单链表的全称为\\\"不带头单向不循环链表\\\" 注意:         下文提到的头节点与带头链表时两个概念,文中的头节点指的是第一个有效节点,二带头节点中的头指的是第一个无效节点 链表和顺序表一样,都是线性表,逻辑结构上是线性的,但不同的是,链表在物理结构上不是线性的

    2024年01月21日
    浏览(30)
  • 数据结构--单链表

    数据结构--单链表

    目录 1.单链表的定义： 单链表基本操作的实现： 2.单链表的初始化（构造带头结点的空表） 2.将头结点的指针域置空 3.链表是否为空： 4.单链表的销毁： 5.单链表的清空: 6.求单链表的表长： 7.   取值  取单链表第i个元素： 8按值查找 根据指定数据查找指定数据所在位置序

    2024年02月15日
    浏览(26)
  • 数据结构单链表

    数据结构单链表

    单链表 1 链表的概念及结构 概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 。 在我们开始讲链表之前，我们是写了顺序表，顺序表就是类似一个数组的东西，它的存放是连续的，优点有很多，比如支持

    2024年02月12日
    浏览(30)
  • 数据结构——单链表（下）

    数据结构——单链表（下）

    🌇个人主页：_麦麦_ 📚今日名言：年轻时候的我以为坚持是永不动摇，到这个年纪明白了坚持就是犹疑着，退缩着，心猿意马着，一步三停着，还在往前走。——《十二月历》 目录 一、引言  二、单链表剩余功能的实现         1.单链表的查找         2. 单链表指定位

    2024年01月17日
    浏览(26)
  • 数据结构——单链表（上）

    数据结构——单链表（上）

    🌇个人主页：_麦麦_ 📚今日名言：“生活总是让我们遍体鳞伤，但到后来，那些受伤的地方一定会变成我们最强壮的地方。”        ——海明威《永别了武器》 目录 ​编辑 一、前言 二、正言  3.1链表的概念及结构 3.2链表的分类 3.3链表的实现【无头单向非循环】 3.

    2024年02月02日
    浏览(30)
  • 数据结构 - 单链表

    数据结构 - 单链表

    目录 文章目录 一、什么是链表? 线性表: 顺序表: 二、链表的分类和实现 分类: 实现: 1.创建节点类 2.创建单链表  1.addTail(尾增)   2.删除节点值为key的第一个节点  3.插入节点(在指定位置) 4.获取链表长度  总结 前言 大家好,这篇博客给大家讲一下什么是链表以及单链表的实现

    2024年02月09日
    浏览(30)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包