C语言数据结构线性表教程示例详解

目录
  • 线性表
  • 顺序表

线性表

数据结构里我们时常看到什么什么表，线性表是最基本、最简单、也是最常用的一种数据结构，其他各种表的万恶之源就是这个线性表，他是个啥其实顾名思义：

一个线性表是n个具有相同特性的数据元素的有限序列。数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。

说的这么复杂其实就是下面这个模型，线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

而我们说的线性是指他的连续性，并非是内存上连续，而是逻辑上连续，什么又是逻辑上连续？我们说数据结构有两种结构，一是物理结构即在内存中怎么存，二是逻辑结构是我们假想的。物理结构其实非数组即链表，基本都逃不开这俩，但数组有个致命的缺陷就是不知道咱要存多少，我开辟10个空间，若想存第11个就是放屁，那直接给他1000个空间呢？那剩下989个空间直接浪费掉，一句话就是他不能按需所取。

这时链表就应运而生，我们有几个数据就开辟几个空间，众所周知数组我们得到首元素地址，直接遍历就能得到全部成员，那它怎么去串联这些独立零散的空间来建立联系？我们按需所取首先就会选择去堆区申请空间，去堆区不是一定是最好，因为 malloc 函数嘛， 满足要就拿不要就释放。我们对数据寻踪觅迹是通过其对应的地址对吧，不难想到应用指针吧，这样那我们就可以“有备而来”，在开辟数据空间时多开辟4到8个字节来存放指针，最后一个数据我们不需要指针了，直接放一个空指针就行。

顺序表

线性表主要由顺序表示或链式表示。在实际应用中，常以栈、队列、字符串等特殊形式使用。

顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。

我们说过线性表中结构不是物理就是逻辑，我们的顺序表其实就是使用数组来存储数据，本质上来说顺序表就是一个数组。

抛开实际的代码谈概念就是耍流氓,我们采用工程化方式来写一组代码，在.h文件中进行定义：

typedef int type;//便于随时修改类型
#define n 10 //方便定义数组大小
struct SeqList
{
	type a[n];
	int size;
};
void PushBack(struct SeqList* p, type x);
void PopBack(struct SeqList* p, type x);
……
//后面这些为尾插，尾删等接口来处理他们之间的关系

以上的代码就是很多教材上的静态顺序表设计结构，咱跳出来看看就会秒感很low，他是固定大小不能按需所取，其实就是封装了一个数组，我们要变成动态顺序表很简单，增设一个capacity成员即可：

typedef int type;
#define n 10
struct SeqList
{
	type a[n];
	int size;   //有效数据的个数
	int capacity;   //容量，即空间的大小
};
void PushBack(struct SeqList* p, type x);
void PopBack(struct SeqList* p, type x);
……

扩容操作我们手动操作，只需引入 realloc 函数即可，如果是将分配的内存扩大，则有以下情况：

如果当前内存段后面有需要的内存空间，则直接扩展这段内存空间，realloc函数将返回原指针。如果当前内存段后面的空闲字节不够，那么就使用堆中的第一个能够满足这一要求的内存块，将目前的数据复制到新的位置，并将原来的数据块释放掉，返回新的内存块位置。如果申请失败，将返回NULL，此时，原来的指针仍然有效。

今天就到这里吧，摸了家人们，更多关于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语言编程数据结构线性表之顺序表和链表原理分析

    目录 线性表的定义和特点 线性结构的特点 线性表 顺序存储 顺序表的元素类型定义 顺序表的增删查改 初始化顺序表 扩容顺序表 尾插法增加元素 头插法 任意位置删除 任意位置添加 线性表的链式存储 数据域与指针域 初始化链表 尾插法增加链表结点 头插法添加链表结点 打印链表 任意位置的删除 双向链表 测试双向链表(主函数) 初始化双向链表 头插法插入元素 尾插法插入元素 尾删法删除结点 头删法删除结点 doubly-Linked list.c文件 doubly-Linkedlist.h 线性表的定

  • 用C语言举例讲解数据结构中的算法复杂度结与顺序表

    用C语言举例讲解数据结构中的算法复杂度结与顺序表

    数据结构算法复杂度 1.影响算法效率的主要因素 (1)算法采用的策略和方法: (2)问题的输入规模: (3)编译器所产生的代码: (4)计算机执行速度. 2.时间复杂度 // 时间复杂度:2n + 5 long sum1(int n) { long ret = 0; \\1 int* array = (int*)malloc(n * sizeof(int)); \\1 int i = 0; \\1 for(i=0; i<n; i++) \\n { array[i] = i + 1; } for(

  • C语言线性表的顺序表示与实现实例详解

    1.概述 通常来说顺序表是在计算机的内存中以数组的形式保存的线性表,是用一组地址连续的存储单元依次存储数据元素的线性数据结构.线性表采用顺序存储的方式存储就称之为顺序表.顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中. 将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构就是顺序结构. 采用顺序存储结构的线性表简称为" 顺序表".顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L 1≤

  • C语言线性表顺序存储结构实例详解

    C语言线性表顺序存储结构实例详解 1. 什么是顺序存储结构? 用一段地址连续的存储单元依次存储线性表的数据元素. 2.线性表的顺序存储结构 #include<stdio.h> #include<stdlib.h> #define Max 80 //存储空间初始分配量 #define Increment 10 //存储空间分配增量 typedef struct { int *elem; // 存储空间基地址,此处为int型,视情况而定 int length; // 元素表当前长度 i

  • C语言数据结构线性表教程示例详解

    C语言数据结构线性表教程示例详解

    目录 线性表 顺序表 线性表 数据结构里我们时常看到什么什么表,线性表是最基本.最简单.也是最常用的一种数据结构,其他各种表的万恶之源就是这个线性表,他是个啥其实顾名思义: 一个线性表是n个具有相同特性的数据元素的有限序列.数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部.比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点). 说的这么复杂其实就是

  • C语言实现线性表的基本操作详解

    C语言实现线性表的基本操作详解

    目录 前言 一.实训名称 二.实训目的 三.实训要求 四.实现效果 五.顺序存储代码实现 六.链式存储代码实现 前言 这里使用的工具是DEV C++ 可以借鉴一下 一.实训名称 线性表的基本操作 二.实训目的 1．掌握线性表的基本概念 2．掌握线性表的存储结构(顺序存储与链式存储) 3．掌握线性表的基本操作 三.实训要求 1.线性表可以顺序表也可以用单链表实现,鼓励大家用两种方式实现. 2.创建线性表时,数据从键盘输入整形数据 3.线性表类型定义和或各种操作的实现,可以用教材给出的方法,也可以自

  • Java 数据结构线性表之顺序存储详解原理

    Java 数据结构线性表之顺序存储详解原理

    目录 线性表的定义 线性表的基本运算 线性表的存储之顺序存储 定义线性表 添加元素 查找元素 删除元素 打印线性表 实现的完整代码 测试一下 线性表的定义 线性表的逻辑特征: ①有且仅有一个称为开始元素的a1,她没有前趋,仅有一个后继结点a2: ②有且仅有一个称为终端元素的an,他没有后继,只有一个直接前驱a(n-1): ③其余元素ai(2≤i≤n-1)称为内部元素,他们都有且仅有一个直接前驱a(i-1)和直接后继a(i+1). 线性表的图像表示 线性表的基本运算 线性表初始化 求表长 按索引值

  • Go语言数据结构之希尔排序示例详解

    Go语言数据结构之希尔排序示例详解

    目录 希尔排序 算法思想 图解算法 Go 代码实现: 总结 希尔排序 在插入排序中,在待排序序列的记录个数比较少,而且基本有序,则排序的效率较高. 1959 年,Donald Shell 从“减少记录个数” 和 “基本有序” 两个方面对直接插入排序进行了改进,提出了希尔排序算法. 希尔排序又称为“缩小增量排序”.即将待排序记录按下标的一定增量分组(减少记录个数),对每组记录使用直接插入排序算法排序(达到基本有序): 随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1,整个序列基本有序,再对

  • Go语言数据结构之选择排序示例详解

    Go语言数据结构之选择排序示例详解

    目录 选择排序 动画演示 Go 代码实现 总结 选择排序 选择排序(selection sort)是一种原地(in-place)排序算法,适用于数据量较少的情况.由于选择操作是基于键值的且交换操作只在需要时才执行,所以选择排序长用于数值较大和键值较小的文件. 思想: 对一个数组进行排序,从未排序的部分反复找到最小的元素,并将其放在开头. 给定长度为 nnn 的序列和位置索引i=0 的数组,选择排序将: 遍历一遍序列,寻找序列中的最小值.在 [i...n−1] 范围内找出最小值 minValue

  • C语言数据结构顺序表中的增删改(头插头删)教程示例详解

    C语言数据结构顺序表中的增删改(头插头删)教程示例详解

    目录 头插操作 头删操作 小结 头插操作 继上一章内容(C语言数据结构顺序表中的增删改教程示例详解),继续讲讲顺序表的基础操作. 和尾插不一样,尾插出手阔绰直接的开空间,咱头插能开吗?好像没听说过哪个接口可以在数据前面开一片空间吧,那我们思路就只有一个了——挪数据.那应该从第一位开始挪吗?注意,这和 memcpy 函数机制是一样的,并不意味着后面数据一起挪动,也不会彼此独立,而是相互影响,挪动的数据会对后面数据进行覆盖. 那我们的逻辑就应该是从后往前挪,那我们就直接定一个下标,指向这段空间的最后

  • C语言*与&在操作线性表的作用详解

    在数据结构线性表一章,对线性表有这些操作方法(Operation): /*Operation*/ Initlist(*L);/*初始化操作,建立一个空的线性表L*/ ListEmpty(L):/*判断线性表是否为空表,若线性表为空,返回值为true,否则返回false*/ ClearList(*L):/*将线性表清空*/ GetElem(L,i,*e):/*性表L中的第i个位置元素值返回给e*/ LocateElem(L,e):/*在线性表L中查找与给定值e相等的元素,如果查找成功,返回该元素在

  • C语言指针教程示例详解

    C语言指针教程示例详解

    目录 指针 内存 指针类型 指针运算 二级指针 指针数组 指针 指针提供了对地址操作的一种方法,因此,使用指针可使得 C 语言能够更高效地实现对计算机底层硬件的操作.另外,通过指针可以更便捷地操作数组.在一定意义上可以说,指针是 C 语言的精髓. 概念解释就不去搬原定义了,又臭又长不好理解,精炼两点就是: 1.指针是内存中的一个最小单元的编号,也就是地址: 2.平时我们说的指针,通常是指指针变量,用来存储内存地址的变量 也就是说:指针就是地址,口语中指针通常是指针变量 内存 要搞明白指针首先要搞

  • C++语言io流处理基本操作教程示例详解

    C++语言io流处理基本操作教程示例详解

    目录 一.输入输出流对象 流对象常用的处理函数 流控制字符 二.字符流操作 sstream 三. 文件流流类 四.文件指针定位 一.输入输出流对象 cout:标准输出流 cerr:标准出凑  和cout(只是用于如果是错误时要输出的) cin  :   标准输入 流对象常用的处理函数 输出字符 put() 输入字符:get() 输出字符串:write() 输入字符串getline() char ch; cin.get(ch); cout << ch<<endl; cout.put(

  • C语言实现冒泡排序算法的示例详解

    C语言实现冒泡排序算法的示例详解

    目录 1. 问题描述 2. 问题分析 3. 算法设计 动图演示 4. 程序设计 设计一 设计二 结论 5. 流程框架 6. 代码实现 7. 问题拓展 1. 问题描述 对N个整数(数据由键盘输入)进行升序排列. 2. 问题分析 对于N个数因其类型相同,我们可利用 数组 进行存储. 冒泡排序是在 两个相邻元素之间进行比较交换的过程将一个无序表变成有序表. 冒泡排序的思想:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小. 若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,

随机推荐