C语言超详细讲解线性表

目录
  • 1. 顺序表
    • 1.1 管理结点
    • 1.2 顺序表的插入
    • 1.3 顺序表的删除
    • 1.4 顺序表的扩容
  • 2. 链表
    • 2.1 定义
    • 2.2 头部插入
    • 2.3 尾部插入
    • 2.4 任意位置插入
    • 2.5 任意位置删除
    • 2.6 虚头结点

1. 顺序表

顺序表是指用一段连续的地址,依次存放数据元素的线性数据结构。此种存储方式使得顺序表的物理结构与逻辑结构都是连续的。

与数组的区别:函数中的数组被存放在栈段中,而栈段有系统限制的大小(可使用ulimit -s查看系统限制的大小,单位为KB),因此顺序表往往使用在堆段中操作管理动态数组的方式实现。

1.1 管理结点

在顺序表中,管理节点内部一般存放:数据域地址(*data)、**总容量(size)以及当前数据量(len)**等等。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct Vector {
	//数据域
	int *data;
	//总容量
	int size;
	//当前元素个数 或 指向末尾元素的后一位
	int len;
} Vector;
//初始化
Vector *initVector(int size){
	Vector *v = (Vector *) malloc(sizeof(Vertor));
	v->data = (int *) malloc(sizeof(int) * size);
	v->len = 0;
	v->size = size;
	return v;
}
//释放
void freeVector(Vector *v){
	if(!v) return;
	free(v->data);
	free(v);
}
int main(){
	//初始化size为10的线性表
	Vector *v = initVector(10)
	return 0;
}

1.2 顺序表的插入

//插入
//将 v->data[idx] 处变成 val
void insert(Vector *v, int idx, int val){
	//判断 v 是否为空 返回
	if(!v) return;
	//判断 idx 是否合法
	if(idx > v->len || idx < 0) return ;
	//判断 v 的容量是否已满
	if(v->len == v->size) return ;
	//维护顺序表的特性  将 idx 及之后的元素后移
	for(int i = v->len; i > idx ;i++){
		v->data[i] = v->data[i - 1];
	}
	//在 idx 处插入数据
	v->data[i] = val;
	//更新当前元素个数
	v->len++;
} 

1.3 顺序表的删除

//删除
//将 v->data[idx] 删除
void delete(Vector *v, int idx){
	if(!v) return ;
	if(idx >= v->len || idx < 0) return ;
	// idx 之后的元素前移
	for(int i = idx; i < v->len-1; i++){
		v->data[i] = v->data[i + 1];
	}
	v->len--;
}

1.4 顺序表的扩容

扩容:新创建 原size * 2 的空间,然后将原数据从原空间迁移到新空间

//倍增法扩容 size -> size + exsize
int expand(Vector *v){
	//扩容为 size + exSize
	int exSize = v->size;
	int *tmp;
	while(exSize){
		//尝试向内存申请空间
		tmp = (int *) realloc(v->data, sizeof(int) * (v->size + exSize));
		//申请成功
		if(tmp) break;
		//申请不成功 exSize/2 继续申请
		exSize >>= 1;
	}
	//彻底失败 未申请到空间
	if(!tmp) return 0;
	//扩容成功
	v->data = tmp;
	v->size += exSize;
	return 1;
}
//插入
//将 v->data[idx] 处变成 val
void insert(Vector *v, int idx, int val){
	...
	if(v->len == v->size) {
		//尝试扩容 扩容成功为 1 失败为 0
		if(!expand(v)) return;
	}
	...
} 

2. 链表

2.1 定义

链表是一种物理结构不连续,但可以依靠结点中的指针实现逻辑结构连续的线性数据结构。

构成链表的数据元素被称为“结点”,节点内部存放数据与指向下一个结点的指针。

//定义结点
typedef struct Node{
	int val;
	struct Node *next;
} Node;
//结点初始化
Node *initNode(int val){
	Node *node = (Node *) malloc(sizeof(Node));
	node->val = val;
	node->next = NULL;
	return node;
}
//释放结点
void freeNode(Node *node){
	if(!node) return ;
	free(node);
}

只有单一结点指针的链表的全程是“单链表”,经常被简称为链表。

链表的管理结点一般仅需要存放头结点指针(*head)。

如果需要频繁获取链表长度,管理结点中可以额外存放链表长度(len)。

//定义链表 管理结点
typedef struct List{
	Node *head;
	int len;
} List;
//初始化链表
List *initList() {
	List *list = (List *) malloc(sizeof(List));
	list->head = NULL;
	list->len = 0;
	return list;
}

2.2 头部插入

头插法:将新插入的节点放在 head 后,时间复杂度O(1)

//头部插入
void insertToHead(List *list, int val){
	if(!list) return ;
	Node *node = initNode(val);
	node->next = list->head;
	list->head = node;
	list->len++;
}

2.3 尾部插入

尾插法:找到最后一个结点,将新节点插入。如果没有设计尾指针,则时间复杂度为O(n)。

//尾部插入
void insertToTail(List *list, int val){
	if(!list) return ;
	Node *node = initNode(val);
	//如果list为空 则node为第一个结点 让head等于node
	//判断条件可更改为list->len == 0
	if(list->head == NULL){
		list->head = node;
		list->len++;
		return ;
	}
	Node *p = list->head;
	while(p->next != NUll){
		p = p->next;
	}
	p->next = node;
	list->len++;
}
//测试
int main(){
	List *list1 = initList();
	List *list2 = initList();
	for(int i = 0;i <= 10;i += 2){
		insertToHead(list1,i);
	}
	Node *p = list1->head;
	while(p){
		printf("%d -> ",p->val);
		p = p->next;
	}
	printf("\n");
	for(int i = 1;i <= 10;i += 2){
		insertToTail(list2,i);
	}
	Node *q = list2->head;
	while(q){
		printf("%d -> ",q->val);
		q = q->next;
	}
	printf("\n");
	return 0;
}

输出结果:

2.4 任意位置插入

//任意位置的插入
// idx = 0 待插入结点为头结点
// idx > 0 插入至第 i 个结点后
void insert(List *list, int idx, int val){
	if(!list) return ;
	if(idx > list->len || idx < 0) return ;
	if(idx == 0){
		//头插法
		insertToHead(list,val);
		return;
	}
	Node *node = initNode(val);
	//结点索引为 0
	Node *p = list->head;
	//p 找到第 idx - 1个结点
	// i = 1  结点索引为 1
	// i = 2 结点索引为 2
	// i = idx - 1 结点索引为 idx - 1
	for(int i = 1;i <= idx - 1;i++){
		p = p->next;
	}
	//插入
	node->next = p->next;
	p->next = node;
	list->len++;
}

2.5 任意位置删除

//任意位置的删除
void remove(List *list, int idx){
	if(!list) return ;
	if(idx > list->len || idx < 0) return ;
	//p为0号索引结点
	Node *p = list->head;
	//删除索引为 0 的结点 更改head
	if(idx == 0){
		list->head = p->next;
		list->len--;
		freeNode(p);
		return;
	}
	//找到idx-1个结点
	for(int i = 1;i <= idx - 1;i ++){
		p = p->next;
	}
	Node *node = p->next;
	//删除
	p->next = p->next->next;
	list->len--;
	freeNode(node);
}

2.6 虚头结点

在需要特殊处理头结点的时候,可以实现一个带有虚头结点的链表。在链表初始化或在某些操作执行时,将一个额外的结点放在头指针执行的地方。虚头结点可以使得整个链表永远不空,永远有头。所以拥有虚头结点的链表在处理各类结点操作时会更加便捷。

任意位置插入:不需要特殊考虑插入位置是否在链表头部。

任意位置删除:不需要特殊考虑删除的结点是否是链表的第一个结点。

//结点部分没有改动
//定义结点
typedef struct Node{
	int val;
	struct Node *next;
} Node;
//结点初始化
Node *initNode(int val){
	Node *node = (Node *) malloc(sizeof(Node));
	node->val = val;
	node->next = NULL;
	return node;
}
//释放结点
void freeNode(Node *node){
	if(!node) return ;
	free(node);
}

//定义链表 管理结点
typedef struct List{
	Node *head;
	int len;
} List;
//初始化链表
List *initList() {
	List *list = (List *) malloc(sizeof(List));
	//变动  :初始化的时候赋予一个结点 任意数值都可以
	list->head = initNode(-1);
	list->len = 0;
	return list;
}
//头部插入
void insertToHead(List *list, int val){
	if(!list) return ;
	Node *node = initNode(val);
	// 变动
	node->next = list->head->next;
	// 变动
	list->head->next = node;
	list->len++;
}
//尾部插入
void insertToTail(List *list, int val){
	if(!list) return ;
	Node *node = initNode(val);
	//变动 删除对链表是否为空的判断  可以直接进行插入
	//此处可以谢伟 Node *p = list->head->next;
	Node *p = list->head;
	while(p->next != NULL){
		p = p->next;
	}
	p->next = node;
	list->len++;
}
//任意位置的插入
void insert(List *list, int idx, int val){
	if(!list) return ;
	if(idx > list->len || idx < 0) return ;
	//变动 : 删除对链表是否为空的判断
	Node *node = initNode(val);
	Node *p = list->head;
	for(int i = 1;i <= idx;i++){
		p = p->next;
	}
	//插入
	node->next = p->next;
	p->next = node;
	list->len++;
}
//任意位置的删除
void remove(List *list, int idx){
	if(!list) return ;
	if(idx > list->len || idx < 0) return ;
	Node *p = list->head;
	for(int i = 1;i <= idx;i ++){
		p = p->next;
	}
	Node *node = p->next;
	//删除
	p->next = p->next->next;
	list->len--;
	freeNode(node);
}

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

(0)

相关推荐

  • C语言超详细讲解数据结构中的线性表

    目录 前言 一.分文件编写 1.分文件编写概念 2.代码展示 二.动态分布内存malloc 1.初识malloc 2.使用方法 三.创建链表并进行增删操作 1.初始化链表 2.在链表中增加数据 3.删除链表中指定位置数据 四.代码展示与运行效果 1.代码展示 2.运行效果 总结 前言 计算机专业都逃不了数据结构这门课,而这门课无疑比较难理解,所以结合我所学知识,我准备对顺序表做一个详细的解答,为了避免代码过长,采用分文件编写的形式,不仅可以让代码干净利落还能提高代码可读性,先解释部分代码的含义,

  • 一起来看看C语言线性表的线性链表

    目录 定义 1.插入 2.建立线性链表 1)头插法 2)尾插法 3.删除 4.查找 5.求线性链表的表长 总结 定义 链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域.因此n个元素的线性表通过每个结点的指针域连接成了一个“链条”,称为链表.若此链表的每个结点中只包含一个指针域,则被称为线性链表或单链表. 线性表的链式存储结构,它不需要用地址连续的存储单元来实现,因为它不要求逻辑上相邻的两个数据元素物理位置

  • C语言线性表全面梳理操作方法

    线性表:零个或多个数据元素的有限序列 强调几点: 首先它是一个序列.也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他都有一个前驱和后继. 其次线性表强调是有限的. 线性表有两种物理结构,第一种是顺序存储结构,另一种是链式存储结构. 线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素.用c语言的一维数组来实现顺序存储结构. 线性表顺序存储结构的优缺点 优点:可以快速地读取表中任一位置的元素 无需为表示表中元素之间的逻辑关系而增加额

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

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

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

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

  • C语言线性表之双链表详解

    目录 定义 1.删除 2.插入 3.建立 4.查找 总结 定义 链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域.因此n个元素的线性表通过每个结点的指针域连接成了一个“链条”,称为链表.若此链表的每个结点中包含两个指针域,则被称为双链表. 双链表的结点结构定义如下: typedef struct node { DataType data; struct node *llink; struct node *

  • C语言的线性表之顺序表你了解吗

    目录 线性表 —— 顺序表 (C语言) 1. 顺序表的储存结构 2. 顺序表的基本操作 2.1 顺序表的插入 2.2 顺序表的查找 2.3 顺序表的删除 总结 线性表 —— 顺序表 (C语言) 概念 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表中的数据元素,这种表示也称做线性表的顺序储存结构或顺序映像.通常,称这种存储结构的线性表为顺序表 (Sequential List) .其特点是,逻辑上相邻的数据元素,其物理次序也是相邻的. 1. 顺序表的储存结构 #include <st

  • C语言线性表中顺序表超详细理解

    目录 一.本章重点 二.线性表 三.顺序表 四.静态顺序表接口实现 4.1顺序表初始化 4.2顺序表打印 4.3顺序表尾插 4.4顺序表尾删 4.5顺序表头插 4.6顺序表头删 4.7顺序表任意位置插入 4.8顺序表任意位置删除 五.动态顺序表接口实现 5.1顺序表的初始化 5.2顺序表打印 5.3顺序表尾插 5.4顺序表尾删 5.5顺序表头插 5.6顺序表头删 5.7顺序表任意位置插入 5.8顺序表任意位置删除 六.在线0j练习 一.移除元素(力扣) 二.合并两个有序数组(力扣) 一.本章重点

  • C语言超详细讲解线性表

    目录 1. 顺序表 1.1 管理结点 1.2 顺序表的插入 1.3 顺序表的删除 1.4 顺序表的扩容 2. 链表 2.1 定义 2.2 头部插入 2.3 尾部插入 2.4 任意位置插入 2.5 任意位置删除 2.6 虚头结点 1. 顺序表 顺序表是指用一段连续的地址,依次存放数据元素的线性数据结构.此种存储方式使得顺序表的物理结构与逻辑结构都是连续的. 与数组的区别:函数中的数组被存放在栈段中,而栈段有系统限制的大小(可使用ulimit -s查看系统限制的大小,单位为KB),因此顺序表往往使用

  • C语言超详细讲解顺序表的各种操作

    目录 顺序表是什么 顺序表的结构体 顺序表的接口函数 顺序表相关操作的菜单 顺序表的初始化 添加元素 陈列元素 往最后加元素 往前面加元素 任意位置加元素 删除最后元素 删除前面元素 删除任意元素 整体代码(fun.h部分) 整体代码(fun.cpp部分) 整体代码(主函数部分) 结果展示 顺序表是什么 顺序表是在计算机内存中以数组的形式保存的线性表,线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素.使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中,即通过数

  • C语言超详细讲解栈的实现及代码

    目录 前言 栈的概念 栈的结构 栈的实现 创建栈结构 初始化栈 销毁栈 入栈 出栈 获取栈顶元素 获取栈中有效元素个数 检测栈是否为空 总代码 Stack.h 文件 Stack.c 文件 Test.c 文件 前言 栈的概念 栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作.进行数据插入和删除操作的一端称为栈顶,另一端称为栈底.栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则.有点类似于手枪弹夹,后压进去的子弹总是最先打出,除非枪坏了. 压栈:栈的插入

  • C语言超详细讲解队列的实现及代码

    目录 前言 队列的概念 队列的结构 队列的应用场景 队列的实现 创建队列结构 队列初始化 队列销毁 入队列 出队列 队列判空 获取队列元素个数 获取队列头部元素 获取队列尾部元素 总代码 Queue.h 文件 Queue.c 文件 Test.c 文件 前言 队列的概念 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾 出队列:进行删除操作的一端称为队头 队列和前文所学的栈

  • C++ 数据结构超详细讲解顺序表

    目录 前言 一.顺序表是什么 概念及结构 二.顺序表的实现 顺序表的缺点 几道练手题 总结 (●’◡’●) 前言 线性表是n个具有相同特性的数据元素的有限序列.线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表.链表.栈.队列.字符串. 线性表在逻辑上是线性结构,也就是说连续的一条直线,但是在物理结构并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储. 本章我们来深度初体验顺序表 一.顺序表是什么 概念及结构 顺序表是一段物理地址连续的存储单元依次存储数据元素的线性

  • C语言 超详细讲解链接器

    目录 1 什么是链接器 2 声明与定义 3 命名冲突 3.1 命名冲突 3.2 static修饰符 4 形参.实参.返回值 5 检查外部类型 6 头文件 1 什么是链接器 典型的链接器把由编译器或汇编器生成的若干个目标模块,整合成一个被称为载入模块或可执行文件的实体–该实体能够被操作系统直接执行. 链接器通常把目标模块看成是由一组外部对象组成的.每个外部对象代表着机器内存中的某个部分,并通过一个外部名称来识别.因此,==程序中的每个函数和每个外部变量,如果没有被声明为static,就都是一个外部

  • C语言超详细讲解数据结构中双向带头循环链表

    目录 一.概念 二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表 三.主要功能 3.1.在pos节点前插入数据 尾插 头插 3.2.删除pos处节点数据 尾删 头删 3.3.查找数据 四.总代码 List.h 文件 List.c 文件 Test.c 文件 五.拓展 一.概念 前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带

  • C语言超详细讲解函数指针的运用

    目录 前言 计算器的例子 回调函数 转移表 前言 前面我们学习了各种各样的指针类型,有些指针可以说是稀奇百怪,特别是函数指针,有些朋友可能觉得,函数指针有些多余,调用函数为什么要用指针调用,直接调用不好吗? 接下来我们从具体的实例来回答同学们的问题,加深对函数指针的理解. 计算器的例子 接下来我们写一个简单的计算器程序,完成不同的计算功能比如加减乘除: #include <stdio.h> //相加函数 int add(int a, int b) { return a + b; } //相减函

  • C语言 超详细讲解库函数

    目录 1 返回整数的getchar函数 2 更新顺序文件 3 缓冲输出与内存分配 4 库函数 练习 1 返回整数的getchar函数 代码: #include<stdio.h> int main() { char c; while((c = getchar())!=EOF)//getchar函数的返回值为整型 putchar(c); return 0; } 上述代码有三种可能: 某些合法的输入字符在被"截断"后使得c的取值与EOF相同,程序将在复制的中途停止. c根本不可能

随机推荐