C语言数据结构与算法之链表(一)

目录
  • 引言
  • 链表的相关思考
  • 链表结点结构
  • 建立链表
  • 实现插入操作
  • 完整代码

引言

在存储一大波数的时候,我们通常使用的是数组,但是数组有时候又会显得不够灵活,比如下面这个例子:

有一串已经排序好的数 2,3,5,8,9 ,10

如果我们想要往数组中插入6 这个元素,需要把 8 以后的元素全部往后挪一位

这样操作显然很耗费时间,如果使用链表的话则会快很多。那么什么是链表呢?请看下图:

此时如果需要在8前面加入一个6,那么只需要向下图一样更改一下就可以了,而不用向像最开始那样把每个数向后挪。

链表的相关思考

为了实现链表这样的数据结构,我们需要使用指针和malloc这样的函数。

注意 : malloc 函数的返回值是 void * 类型,我们需要对其进行强制类型转换 

使用malloc时需要调用头文件 <stdlib.h>

为什么我们要用这么复杂的办法来储存类型呢?

因为按照之前的方法,我们必须预先准确地知道所需变量的个数,也就是说我们必须我们必须定义出所有的变量。假如说你现在定义了100个变量,而实际上则需要101个变量,那么就不得不对这个程序进行修改。

而有了malloc函数,我们可以在程序运行的过程中根据实际情况来申请空间。

链表结点结构

每一个结点都由两个部分组成。左边的部分用来存放具体的值,那么用一个整型变量就可以;右边的部分则需要储存下一个点的地址,则可以用指针来实现(也称为后继指针)。

这里我们定义一个结构体类型来存储这个结点:

struct node
{
	int date;
	struct node* next;
};

因为下一个结点的类型也是 struct node ,所以我们指针的类型也必须是 struct node * 类型。

建立链表

首先,我们需要一个头指针 head 指向链表的最开始。当链表还没有建立的时候头指针head为空(也可以理解指向空结点)。

struct node* head;
head = NULL;  //头指针初始为空

现在,我们来创立第一个结点,并用临时指针p指向这个结点

struct node* p;
//动态申请一块空间,用来存放一个结点,并用临时指针p指向这个结点
p = (struct node*)malloc(sizeof(struct node));

接下来分别设置新建的结点的左半部分和右半部分

scanf("%d", &a);
p->date = a;	 //将数据存储到当前结点的date域中
p->next = NULL;  //设置当前结点的后继指针为空,也就是当前结点的下一个结点为空

下面来设置头指针并设置新创结点的 *next 指向空 。头指针的作用是方便以后从头遍历整个链表

if (head == NULL)
	head = p;  //如果这是第一个创建的结点,则将头指针指向这个结点
else
	q->next = p;	//如果不是第一个创建的结点,则将上一个结点的后继指针指向当前结点

如果是第一个创立的结点,则将头指针指向这个结点 

如果不是第一个创建的结点,则将上一个结点的后继节点指向当前结点。

最后要将指针q也指向当前结点,因为待会临时指针p将会指向新创建的结点。

q = p;  //指针q也要指向当前结点
#include <stdio.h>
#include <stdlib.h>

//这里创建一个结构体用来表示链表的结点类型
struct node
{
	int date;
	struct node* next;
};

int main()
{
	struct node* head, * p, * q = NULL, * t;
	int i, n, a;
	scanf("%d", &n);
	head = NULL;  //头指针初始化为空
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		//动态申请一块空间,用来存放一个结点,并用临时指针p指向这个结点
		p = (struct node*)malloc(sizeof(struct node));
		p->date = a;
		p->next = NULL; //设置当前结点的后继指针为空,也就是下一个结点为空
		if (head == NULL)
			head = p;	//如果这是第一个创建的结点,则将头指针指向这个点
		else
			q->next = p;//如果不是第一个创建的结点,则将上一个结点的后继节点指向当前结点

		q = p;  //指针q也指向当前结点
	}

	//输出链表中的所有数
	t = head;
	while (t != NULL)
	{
		printf("%d  ", t->date);
		t = t->next;  //继续下一个结点
	}

}

效果图

实现插入操作

首先用一个临时指针t从链表的头部开始遍历

 t = head; //从链表的头部开始遍历

等到指针t的下一个结点的值比6大的时候,将6插到中间。

即 t -> next -> date 大于 6 的时候进行插入

代码实现

	scanf("%d", &a);  //读入待插入的数
	t = head;		  //从链表的头部开始遍历
	while (t != NULL)
	{
		if (t->next->date > a || t->next->next == NULL)
		{
			//如果当前结点是最后一个结点或者下一个结点的值大于待插入的值的时候插入
			p = (struct node*)malloc(sizeof(struct node)); //申请一块空间,来存放新增结点
			p->date = a;
			p->next = t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点
			t->next = p;	  //当前结点的后继指针指向新增结点
			break;			  //插入完毕退出循环

		}
		t = t->next;   //继续下一个结点
	}

完整代码

效果图:

#include <stdio.h>
#include <stdlib.h>

//这里创建一个结构体用来表示链表的结点类型
struct node
{
	int date;
	struct node* next;
};

int main()
{
	struct node* head, * p, * q = NULL, * t;
	int i, n, a;
	scanf("%d", &n);
	head = NULL;  //头指针初始化为空
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		//动态申请一块空间,用来存放一个结点,并用临时指针p指向这个结点
		p = (struct node*)malloc(sizeof(struct node));
		p->date = a;
		p->next = NULL; //设置当前结点的后继指针为空,也就是下一个结点为空
		if (head == NULL)
			head = p;	//如果这是第一个创建的结点,则将头指针指向这个点
		else
			q->next = p;//如果不是第一个创建的结点,则将上一个结点的后继节点指向当前结点

		q = p;  //指针q也指向当前结点
	}

	scanf("%d", &a);  //读入待插入的数
	t = head;		  //从链表的头部开始遍历
	while (t != NULL)
	{
		if (t->next->date > a || t->next->next == NULL)
		{
			//如果当前结点是最后一个结点或者下一个结点的值大于待插入的值的时候插入
			p = (struct node*)malloc(sizeof(struct node)); //申请一块空间,来存放新增结点
			p->date = a;
			p->next = t->next;//新增结点的后继指针指向当前结点的后继指针所指向的结点
			t->next = p;	  //当前结点的后继指针指向新增结点
			break;			  //插入完毕退出循环

		}
		t = t->next;   //继续下一个结点
	}

	//输出链表中的所有数
	t = head;
	while (t != NULL)
	{
		printf("%d  ", t->date);
		t = t->next;  //继续下一个结点
	}

}

以上就是C语言数据结构与算法之链表(一)的详细内容,更多关于C语言数据结构 链表的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言数据结构之顺序表和单链表

    一.顺序表的创建.删除和插入 #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> struct sqlist { int date[10]; int length; }; void InitList(sqlist& L) { for (int i = 0;i < 10;i++) { L.date[i] = 0; } L.length = 0; } void charu(sqlist& L) { for (int j =

  • C语言 数据结构之链表实现代码

    前言 最近在复习数据结构的相关知识,感觉在初学的时候还是有很多东西没有掌握,不过现在终于算是搞得比较有头绪了,所以就在写出来和大家一起分享! 什么是链表 简单的说,链表就是由多个结点离散分配,彼此通过指针相连,每个结点只有一个前驱结点和后继结点.首节点无前驱结点,为结点无后继结点的一种存储结构. 链表的结构 头结点:链表的第一个有效结点前面的结点,头结点并不存放有效数据,也就是数据域为空,加头结点的主要目的是为了方便链表的操作. 首节点:链表的第一个有效结点,结点包含数据域和指针域. 尾结点:尾

  • C语言 数据结构链表的实例(十九种操作)

    C语言 数据结构链表的实例(十九种操作) #include <stdio.h> #include <string.h> #include <stdlib.h> /*************************************************************************************/ /* 第一版博主 原文地址 http://www.cnblogs.com/renyuan/archive/2013/05/21/30915

  • C语言实现通用数据结构之通用链表

    本文实例为大家分享了c语言实现通用数据结构之通用链表的具体代码,供大家参考,具体内容如下 忽然想起来,大概在两年之前学习C语言的时候,曾经用C语言写过一些通用的数据结构.主要也就实现了链表.队列.椎.HashSet,还有HashMap.当时只是知道标准的C语言中没有这方面的类库,后来才知道有很多第三方的类似这样的类库.废话不多说,先把代码粘过来. 下面实现的是通用链表,注意链表中只存储了指针,没有储存实际的数据. 头文件 /************************* *** File m

  • C语言数据结构实现链表去重的实例

    C语言数据结构实现链表去重的实例 题目及分析 链表去重 时间限制 300 ms 内存限制 65536 kB 代码长度限制 8000 B 判题程序 Standard 给定一个带整数键值的单链表L,本题要求你编写程序,删除那些键值的绝对值有重复的结点.即对任意键值K,只有键值或其绝对值等于K的第一个结点可以被保留.同时,所有被删除的结点必须被保存在另外一个链表中.例如:另L为21→-15→-15→-7→15,则你必须输出去重后的链表21→-15→-7.以及被删除的链表-15→15. 输入格式: 输入

  • C语言数据结构之单向链表详解分析

    链表的概念:链表是一种动态存储分布的数据结构,由若干个同一结构类型的结点依次串连而成. 链表分为单向链表和双向链表. 链表变量一般用指针head表示,用来存放链表首结点的地址. 每个结点由数据部分和下一个结点的地址部分组成,即每个结点都指向下一个结点.最后一个结点称为表尾,其下一个结点的地址部分的值为NULL(表示为空地址). 特别注意:链表中的各个结点在内存中是可以不连续存放的,具体存放位置由系统分配. 例如:int *ptr ; 因此不可以用ptr++的方式来寻找下一个结点. 使用链表的优点

  • C语言数据结构与算法之链表(二)

    目录 引入 模拟链表介绍 插入代码实现 代码实现   引入 在上一节的学习中我们介绍了C语言如何实现链表,但是,在这一章,我们将抛开令人头秃的指针和结构体,我们将另外使用一种数组来实现的方式,叫做模拟链表.让我们一起来看看. 模拟链表介绍 链表中的每一个结点都只有两个部分. 我们可以使用一个数组date来储存每序列中的每一个数.那每一个数右边的数是谁,这一点该如何解决呢?在上一章的内容中我们是使用指针来解决的,这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了.具体要怎么

  • C语言数据结构与算法之链表(一)

    目录 引言 链表的相关思考 链表结点结构 建立链表 实现插入操作 完整代码 引言 在存储一大波数的时候,我们通常使用的是数组,但是数组有时候又会显得不够灵活,比如下面这个例子: 有一串已经排序好的数 2,3,5,8,9 ,10 如果我们想要往数组中插入6 这个元素,需要把 8 以后的元素全部往后挪一位 这样操作显然很耗费时间,如果使用链表的话则会快很多.那么什么是链表呢?请看下图: 此时如果需要在8前面加入一个6,那么只需要向下图一样更改一下就可以了,而不用向像最开始那样把每个数向后挪. 链表的

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

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

  • Python实现的数据结构与算法之链表详解

    本文实例讲述了Python实现的数据结构与算法之链表.分享给大家供大家参考.具体分析如下: 一.概述 链表(linked list)是一组数据项的集合,其中每个数据项都是一个节点的一部分,每个节点还包含指向下一个节点的链接. 根据结构的不同,链表可以分为单向链表.单向循环链表.双向链表.双向循环链表等.其中,单向链表和单向循环链表的结构如下图所示: 二.ADT 这里只考虑单向循环链表ADT,其他类型的链表ADT大同小异.单向循环链表ADT(抽象数据类型)一般提供以下接口: ① SinCycLin

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • C语言数据结构与算法之图的遍历(二)

    目录 前言  广度优先搜索过程 主要思想  代码实现   前言  在上一章的内容中我们使用了深度优先搜索来进行遍历,这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下: 广度优先搜索过程 使用广度优先搜索来遍历这个图的过程如下. 首先以一个未被访问过的顶点作为起始顶点,比如以1号点作为起始顶点. 将1号点放到队列中,然后将与1号点相邻的未访问过的顶点 即 2,3,5号顶点依次放入队列中,如下图: 接下来将2号顶点相邻的未访问过的顶点4号放入到队列中.到此所有的顶点都访问过了,遍历

  • C语言数据结构与算法之图的遍历

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • C语言数据结构与算法之排序总结(二)

    目录 一.前言 二.选择类排序 1.简单选择排序 2.树形选择排序 3.堆选择排序 三.归并排序 四.分配类排序 1.多关键字排序 2.链式基数排序 五.总结归纳 一.前言 之前的排序总结(一)对插入类和交换类排序作了比较详细的总结,对于直接插入.希尔排序.冒泡排序.快速排序要求熟练掌握 这篇排序全面总结(二)主要介绍选择类排序中的简单.树形和堆排序,归并排序.分配类排序的基数排序 二.选择类排序 选择类:每次从待排序的无序序列中,选择一个最大或最小的数字,放到前面,数据元素为空时排序结束 1.

  • C语言数据结构与算法之排序总结(一)

    目录 一.前言 二.基本概念 1.排序 2.排序方法的稳定性 3.内部和外部排序 三.插入类排序 1.直接插入排序 2.折半插入排序 3.希尔排序 四.交换类排序 1.冒泡排序 2.快速排序 五.总结比较 一.前言 学习目标: 排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确 理解各种排序算法的定义和特点,并能将代码灵活运用 掌握各种排序方法时间复杂度与空间复杂度 理解排序稳定和不稳定的概念                 重点和难点: 希尔.快速.堆.归并排序这几种快

  • C语言 数据结构与算法之字符串详解

    目录 串的定义 串的比较 串的抽象数据类型 串的初始化 相关定义初始化 定长类初始化 串的堆式顺序存储结构(Heap) 初始化堆字符串 赋值操作 比较两个堆字符串的大小 串的定义 零个或多个字符组成的有限序列 串的比较 串的比较实际上是在比较串中字符的编码 存在某个k < min(n,m),使得ai = bi (i = 1,2,3,4..k) 如果 ak < bk  -->  那么srt1 < srt2 (反之也成立) 除去相等的字符,在第一个不相等的字符位置以Ascii码进行比较

随机推荐