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

目录
  • 引入
  • 模拟链表介绍
    • 插入代码实现
  • 代码实现  

引入

在上一节的学习中我们介绍了C语言如何实现链表，但是，在这一章，我们将抛开令人头秃的指针和结构体，我们将另外使用一种数组来实现的方式，叫做模拟链表。让我们一起来看看。

模拟链表介绍

链表中的每一个结点都只有两个部分。

我们可以使用一个数组date来储存每序列中的每一个数。那每一个数右边的数是谁，这一点该如何解决呢？在上一章的内容中我们是使用指针来解决的，这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了。具体要怎么做呢？

上面的两个数组中，第一个整型数组date是用来存放序列中的具体数字的，另外一个整型数组right是用来存放当前序列中每一个元素右边的元素在数组date中位置的。

例如right【1】的值为2，就表示当前序列中1号元素右边的元素存放在date【2】 中；如果是0，例如right【9】的值为0，就表示当前序列中9号元素的右边没有元素。

现在需要在8面前插入一个6，只需将6直接存在数组date的末尾即date【10】 = 6.

接下来只需要将right【3】改为10，表明新序列中3号元素右边的元素存放在date【10】中。再将right【10】的值改为4，表示新序列中10号元素右边的元素存放在date【4】中。

这样我们通过right数组就可以从头到尾遍历整个序列了（序列的每个元素的值存放在对应的数组date中），如下

插入代码实现

	//从链表的头部开始遍历
	t = 1;
	while(t != 0)
	{
		//如果当前结点下一个结点的值大于待插入数，将数插到中间
		if(date[right[t]] > date[len])
		{
			right[len] = right[t];   //新插入的数的下一个结点标号等于当前结点的下一个标号
			right[t] = len;			 //当前结点的下一个结点编号就是新插入数的编号
			break;					 //插入完成跳出循环
		}
		t = right[t];
	}

代码实现  

#include <stdio.h>
int main()
{
	int date[101],right[101];
	int i,n,t,len;
	//读入已有的数
	scanf("%d",&n);
	for(i = 1;i <= n;i++)
		scanf("%d",&date[i]);
	len = n;

	//初始化数组right
	for(i = 1;i <= n;i++)
	{
		if(i != n)
			right[i] = i + 1;
		else
			right[i] = 0;
	}

	//直接在数组date的末尾加一个数
	len++;
	scanf("%d",&date[len]);

	//从链表的头部开始遍历
	t = 1;
	while(t != 0)
	{
		//如果当前结点下一个结点的值大于待插入数，将数插到中间
		if(date[right[t]] > date[len])
		{
			right[len] = right[t];   //新插入的数的下一个结点标号等于当前结点的下一个标号
			right[t] = len;			 //当前结点的下一个结点编号就是新插入数的编号
			break;					 //插入完成跳出循环
		}
		t = right[t];
	}

	//输出链表中的所有数
	t = 1;
	while(t != 0)
	{
		printf("%d",date[t]);
		t = right[t];
	}

	return 0;
}

到此这篇关于C语言数据结构与算法之链表(二)的文章就介绍到这了,更多相关C语言数据结构 链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 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语言数据结构之复杂链表的拷贝

    题目: 给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点. 构造这个链表的 深拷贝. 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值.新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态.复制链表中的指针都不应指向原链表中的节点 . 例如,如果原链表中有 X 和 Y 两个节点,其中 X.random --> Y

  • C语言数据结构链表队列的实现

    C语言数据结构链表队列的实现 1.写在前面 队列是一种和栈相反的,遵循先进先出原则的线性表. 本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码. 分解代码没有包含在内的代码如下: #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int QElemtype; typedef int status; 2.代码分解 2.1对队列和节点的结构定义 typedef struct

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

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

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

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

    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语言数据结构旋转链表的实现 实例: 给出链表1->2->3->4->5->null和k=2 返回4->5->1->2->3->null 分析: 感觉很直观,直接把分割点找出来就行,记得k可能大于len,要取模 代码: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • C语言数据结构与算法之时间空间复杂度入门

    C语言数据结构与算法之时间空间复杂度入门

    目录 数据结构与算法 什么是数据结构?什么是算法? 分析维度 大O的渐进表示法 常数阶 线性阶 对数阶 其他时间复杂度指标 空间复杂度 数据结构与算法 终于开始搞这块难啃的骨头了,走上这条漫漫长路之前要明白: 什么是数据结构?什么是算法? 是数据之间存在一种或多种特定关系的数据元素集合,为编写出一个“好”的程序,必须分析待处理对象的特性及各处理对象之间存在的关系,这也就是研究数据结构的意义所在为编写出一个“好”的程序,必须分析待处理对象的特性及各处理对象之间存在的关系这也就是研究数据结构的意义所

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

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

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

随机推荐