C语言链表与单链表详解

链表是什么及链表的优势

链表是一种介于数组的另外一种数据结构:

我们知道数组可以存放很多的元素,这些元素都是呈线性排列,也就是一个挨着一个连续存放

但是当元素足够多时,还能继续正常的存放吗?

事实上的不可以的,虽然系统的内存足够大,但是这些内存不都是连续的,这就导致会出现没有足够的空间去存储这些元素。

其次就是数组的大小需要你去申请,如果你申请的空间足够大,就会导致内存的浪费

而链表就很好的解决了这两个问题

链表的组成

链表的作用就是相当与数组一样,储存你数据的

但又不同于数组,链表把每一个游离的数据进行连接,连接的方法通过的是指针,也就是地址,

每一个链表都是由一个个结点组成,结点包含,一个是为我们存放数据的空间,另一个是存放下一个结点地址的空间,也就是所谓的数据域和地址域。

链表有时候包括了头结点,它是为了方便而设计的结点,这个头结点一般只包含地址域,也就是结点1的地址,一般情况下,头结点的数据域一般无意义。

最后的结点,指向的是NULL,用来限制链表的大小

单向链表结点的定义

说完链表的组成是结点,那单向链表的结点是如何定义的呢

struct  Node  //链表的结点 

{

             int data;                   //结点的值

             struct Node  *next;    //下一个结点的地址

};

单项链表的创建

//创建所需的结点
struct Node* createList(int n)
{
	struct Node* first, * t, * last; int i;
	first = (struct Node*)malloc(sizeof(struct Node));
	//给第一个结点数据赋个值
	scanf_s("%d", &first->data);
	last = first ;
	//在创建其他的结点
	for (i = n - 1; i > 0; i--)
	{
		//再首尾中间插入结点.并赋值
		t= (struct Node*)malloc(sizeof(struct Node));
		scanf_s("%d", &t->data);
		last->next = t;
		last=t;
	}
	last->next = NULL;//防止野指针的存在
	return first;
}

其中的first,last,还有t,都是指针变量,用来存放各个节点的地址

sizeof(struct listnode)函数返回结构体Node类型占用的字节数

malloc(sizeof(struct Node))函数功能:系统从内存的空闲空间中,申请存放一个结点的存储空间。

(struct listnode *)malloc(sizeof(struct Node)),函数返回一个指针(地址),指向刚分配给结构体的第一个字节的地址。

malloc函数在头文件stdlib.h中定义

打印出链表各个结点的数据

//再创建函数进行打印出各个结点的值
void printList(struct Node* first)
{
	//把每一个字节数据域的都打印出来
	struct Node* p = first;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

其中传入函数的是结构体指针

从第一个结点的数据域开始打印,到最后的NULL结束

(访问下一个数据域不能用p++,因为链表不是连续的,地址也不是连续的,如果要访问下一个数据,需要用p = p->next)

释放向系统申请的空间

void destoryList(struct Node* first)
{
	struct Node* p = first, *tmp;

	while (p != NULL)
	{
		tmp = p->next;
		free(p);
		p = tmp;
	}
}

这里的 struct Node* p = first, *tmp;

就相当于 struct Node*p=first;

struct Node *tmp;

例题

从键盘输入一组整数,创建单向链表,并输出链表中的数据。

样例输入:2  5  7  6  3  4

样例输出:2  5  7  6  3  4

解答如下:

#include<stdio.h>
#include<stdlib.h>
#define N 6
//链表
struct Node
{
	int data;
	struct Node* next;
};
//创建所需的结点
struct Node* createList(int n)
{
	struct Node* first, * t, * last; int i;
	first = (struct Node*)malloc(sizeof(struct Node));
	//给第一个结点数据赋个值
	scanf_s("%d", &first->data);
	last = first ;
	//在创建其他的结点
	for (i = n - 1; i > 0; i--)
	{
		//再首尾中间插入结点.并赋值
		t= (struct Node*)malloc(sizeof(struct Node));
		scanf_s("%d", &t->data);
		last->next = t;
		last=t;
	}
	last->next = NULL;//防止野指针的存在
	return first;
}
//再创建函数进行打印出各个结点的值
void printList(struct Node* first)
{
	//把每一个字节数据域的都打印出来
	struct Node* p = first;
	while (p != NULL)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}
//释放头结点申请的空间
void destoryList(struct Node* first)
{
	struct Node* p = first, *tmp;

	while (p != NULL)
	{
		tmp = p->next;
		free(p);
		p = tmp;
	}
}

int main()
{
	struct Node* list;
	list = createList(N);
	printList(list);//输出头节点为list的链表   、、、、、、
	destoryList(list);
	printf("\n");
	return 0;
}

到此这篇关于C语言链表与单链表详解的文章就介绍到这了,更多相关C语言 链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • C语言实现单链表的基本功能详解

    1.首先简单了解一下链表的概念: 要注意的是链表是一个结构体实现的一种线性表,它只能从前往后,不可以从后往前(因为next只保存下一个节点的地址).在实现单链表的操作时,需要用指针来操作.很简单,注释写的很详细,欢迎大家指正哈哈哈哈~之前写的太烂了重新写了一下..... 2.代码展示: #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef struct linklist { int data

  • 详解C语言之单链表

    目录 一.思路步骤 1. 定义结构体 2.初始化 3.求当前数据元素的个数 4.插入 5.删除 6.释放内存空间 二.代码 总结 一.思路步骤 1. 定义结构体 a.数据域:用来存放数据 b.指针域:用来存放下一个数据的位置 2.初始化 申请头结点,并将其初始化为空 3.求当前数据元素的个数 a.设置一个指针变量p指向头结点和计数变量size等于0 b.循环判断p->next是否为空,如果不为空,就让指针p指向它的直接后继结点,并让size自增 c.返回size 4.插入 a.设置两个指针,一个

  • C语言数据结构单链表接口函数全面讲解教程

    目录 前言 一.链表的概念及结构 1.概念 二.链表的使用 1.遍历整个链表 2.尾插 3.头插 4.头删 5.尾删 6.任意位置插入数据 7.任意位置删除数据 后记 前言 上一期数据结构专栏我们学习了顺序表后:C语言数据结构顺序表 在运用时,细心的同学可能会发现,如果要头插.尾插或者任意位置.如果原先的空间已经被占满了,你是需要扩容的,动态链表扩容往往是2倍,但是扩容后,如果后面没有使用完全扩容后空间就会造成空间浪费,为了解决这个问题,我们今天将学习链表. 提示:以下是本篇文章正文内容,下面案

  • C语言用循环单链表实现约瑟夫环

    用循环单链表实现约瑟夫环(c语言),供大家参考,具体内容如下 源代码如下,采用Dev编译通过,成功运行,默认数到三出局. 主函数: main.c文件 #include <stdio.h> #include "head.h" #include "1.h" int main() { Linklist L; int n; printf("请输入约瑟夫环中的人数:"); scanf("%d",&n); Create

  • C语言使用单链表实现学生信息管理系统

    本文实例为大家分享了C语言使用单链表实现学生信息管理系统,供大家参考,具体内容如下 初学数据结构,记录一下学习过程. 运行结果如图: 1.运行界面 2.录入学生信息 3.按照总分进行排序 代码如下: #define ERROR 0 #define OK 1 #define OVERFLOW -1; typedef int ElemType; typedef int Status; #include<stdio.h> #include<stdlib.h> #include<ma

  • 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.中间插入(在pos后面进行插入) 7.中间删除(在pos后面进行删除) 8.单独打印链表和从头到尾打印链表 9.test.c 总结 一.单链表与顺序表的区别: 一.顺序表: 1.内存中地址连续 2.长度可以实时变化 3.不支持随机查找 4.适用于访问大量元素的,而少量需要增添/删除的元素的程序 5

  • C语言数据结构与算法之单链表

    目录 基本概念 读取数据元素 获取第i个结点的数据元素 插入数据元素  初始化链表 打印链表 顺序表查空 顺序表的删除  删除第i个结点及其数据元素 情况1:当删除的是第一个元素 情况2:除第一个结点外 完整代码 删除单链表整表 单链表VS顺序表 基本概念 链表的每一个结点中只包含一个指针域 优点 : 储存空间利用高效 举例来说: typedef struct student{ int id; //学生编号 char* name; //学生名称 //指向下一结点的指针 struct Studen

  • C语言实现单链表的快速排序算法

    目录 背景 设计思路 算法主要步骤 快速排序算法实现 整个程序源代码 测试案例 总结 背景 传统QuickSort算法最大不足之处在于,由于其基于可索引存储结构设计(一般为数组或索引表),因而无法用于链式存储结构,而链式存储结构的实际应用非常广泛,例如动态存储管理.动态优先级调度等等,故本文针对于单向链表,以QuickSort的分治策略为基础,提出一种可用于单向链表的快速排序算法. 设计思路 将单向链表的首节点作为枢轴节点,然后从单向链表首部的第二个节点开始,逐一遍历所有后续节点,并将这些已遍历

  • C语言链表与单链表详解

    链表是什么及链表的优势 链表是一种介于数组的另外一种数据结构: 我们知道数组可以存放很多的元素,这些元素都是呈线性排列,也就是一个挨着一个连续存放 但是当元素足够多时,还能继续正常的存放吗? 事实上的不可以的,虽然系统的内存足够大,但是这些内存不都是连续的,这就导致会出现没有足够的空间去存储这些元素. 其次就是数组的大小需要你去申请,如果你申请的空间足够大,就会导致内存的浪费 而链表就很好的解决了这两个问题 链表的组成 链表的作用就是相当与数组一样,储存你数据的 但又不同于数组,链表把每一个游离

  • C语言实现无头单链表详解

    目录 链表的结构体描述(节点) 再定义一个结构体(链表) 断言处理 & 判空处理 创建链表 创建节点 头插法 打印链表 尾插法 指定位置插入 头删法 尾删法 指定位置删除 查找链表 删除所有指定相同的元素 总结 再封装的方式,用 c++ 的思想做无头链表 链表的结构体描述(节点) #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DataType; //节点 typede

  • C语言数据结构之单链表存储详解

    目录 1.定义一个链表结点 2.初始化单链表 3.输出链表数据 4.完整代码 如果说,顺序表的所占用的内存空间是连续的,那么链表则是随机分配的不连续的,那么为了使随机分散的内存空间串联在一起形成一种前后相连的关系,指针则起到了关键性作用. 单链表的基本结构: 头指针:永远指向链表第一个节点的位置. 头结点:不存任何数据的空节点,通常作为链表的第一个节点.对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题. 首元结点:首个带有元素的结点. 其他结点:链表中其他的节点. 1.定义一

  • 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;/

  • Go语言数据结构之单链表的实例详解

    目录 任意类型的数据域 实例01 快慢指针 实例02 反转链表 实例03 实例04 交换节点 实例05 任意类型的数据域 之前的链表定义数据域都是整型int,如果需要不同类型的数据就要用到 interface{}. 空接口 interface{} 对于描述起不到任何的作用(因为它不包含任何的method),但interface{}在需要存储任意类型的数值的时候相当有用,因为它可以存储任意类型的数值. 一个函数把interface{}作为参数,那么它可以接受任意类型的值作为参数:如果一个函数返回i

  • C语言之复杂链表的复制方法(图示详解)

    什么是复杂链表? 复杂链表指的是一个链表有若干个结点,每个结点有一个数据域用于存放数据,还有两个指针域,其中一个指向下一个节点,还有一个随机指向当前复杂链表中的任意一个节点或者是一个空结点.今天我们要实现的就是对这样一个复杂链表复制产生一个新的复杂链表. 复杂链表的数据结构如下: typedef int DataType; //数据域的类型 //复杂链表的数据结构 typedef struct ComplexNode { DataType _data ; // 数据 struct Complex

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

  • Java数据结构之环形链表和约瑟夫问题详解

    目录 一.环形链表 1.创建结点 2.添加小结点 3.显示循环链表 二.约瑟夫问题 1.问题描述 2.首先确定圈大小及开始位置 3.出圈操作 4.出圈方法完整代码 总结 一.环形链表 1.创建结点 环形链表其实也很好理解,就是将单链表的头和尾连接起来,就形成了环形链表. public class Node { public int data; public Node next; public Node(int data) { this.data = data; } @Override publi

随机推荐