广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言超详细讲解线性表
  • 396

0
分享到

C语言超详细讲解线性表

2024-04-02 19:04:59 396人浏览 八月长安
摘要

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

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语言线性表内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！

点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料

--结束END--

本文标题: C语言超详细讲解线性表

本文链接: https://www.lsjlt.com/news/153279.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑，方便收藏和打印～

下载Word文档
去做题
猜你喜欢
  • C语言超详细讲解线性表
    目录1. 顺序表1.1 管理结点1.2 顺序表的插入1.3 顺序表的删除1.4 顺序表的扩容2. 链表2.1 定义2.2 头部插入2.3 尾部插入2.4 任意位置插入2.5 任意位置...
    99+
    2022-11-13
  • C语言超详细讲解数据结构中的线性表
    目录前言一、分文件编写1、分文件编写概念2、代码展示二、动态分布内存malloc1、初识malloc2、使用方法三、创建链表并进行增删操作1、初始化链表2、在链表中增加数据3、删除链...
    99+
    2022-11-13
  • C语言线性表中顺序表超详细理解
    目录一、本章重点二、线性表三、顺序表四、静态顺序表接口实现4.1顺序表初始化4.2顺序表打印4.3顺序表尾插4.4顺序表尾删4.5顺序表头插4.6顺序表头删4.7顺序表任意位置插入4...
    99+
    2022-11-13
  • C语言超详细i讲解双向链表
    目录一、双向链表的概念二、双向链表的实现三、链表与顺序表的差别四、链表oj总结一、双向链表的概念 1、概念：概念：双向链表是每个结点除后继指针外还有⼀个前驱指针。双向链表也有带头结点...
    99+
    2022-11-13
  • C语言哈希表概念超详细讲解
    目录1. 哈希概念2. 哈希冲突3. 哈希实现3.1 闭散列(哈希表)3.1.1 闭散列的细节3.1.2 优化后的闭散列3.2 扩散列(哈希桶)3.2.1 扩散列的细节4. 哈希表和...
    99+
    2023-02-09
    C语言哈希表 C语言哈希概念 C语言哈希实现
  • C语言超详细讲解库函数
    目录1 返回整数的getchar函数2 更新顺序文件3 缓冲输出与内存分配4 库函数练习1 返回整数的getchar函数 代码： #include<stdio.h> ...
    99+
    2022-11-13
  • C语言 超详细讲解链接器
    目录1 什么是链接器2 声明与定义3 命名冲突3.1 命名冲突3.2 static修饰符4 形参、实参、返回值5 检查外部类型6 头文件1 什么是链接器 典型的链接器把由编译器或汇编...
    99+
    2022-11-13
  • C语言数组超详细讲解上
    目录前言1、一维数组的创建和初始化1.1 一维数组的创建1.2 一维数组的初始化1.3 一维数组的使用1.4 一维数组在内存中的存储2、二维数组的创建和初始化2.1 二维数组的创建2...
    99+
    2022-11-13
  • C语言结构体超详细讲解
    目录前言1、结构体的声明1.1 结构的基础知识1.2 结构的声明1.3 结构成员的类型1.4 结构体变量的定义和初始化2、结构体成员的访问2.1 点操作符访问2.2 ->操作符...
    99+
    2022-11-13
  • C语言 struct结构体超详细讲解
    目录一、本章重点二、创建结构体三、typedef与结构体的渊源四、匿名结构体五、结构体大小六、结构体指针七、其他一、本章重点 创建结构体typedef与结构体的渊源匿名结构体结构体大...
    99+
    2022-11-13
  • C语言超详细讲解轮转数组
    目录题目描述实例解题思路1. 先整体逆转2.逆转子数组[0, k - 1]3.逆转子数组[k, numsSize - 1]易错点代码题目描述 给你一个数组，将数组中的元素向右轮转 k...
    99+
    2022-11-13
  • C语言函数超详细讲解上篇
    目录前言1、函数是什么？2、C语言中函数的分类2.1 库函数2.1.1 如何学会使用库函数2.1.2 自定义函数3、函数的参数3.1 实际参数（实参）3.2 形式参数（形参）4、函数...
    99+
    2022-11-13
  • C语言函数超详细讲解下篇
    目录前言函数的声明和定义函数声明函数定义举例简单的求和函数把加法单独改写成函数添加函数声明带头文件和函数声明静态库（.lib）的生成静态库文件的使用方法函数递归什么是递归？递归的两个...
    99+
    2022-11-13
  • C语言指针超详细讲解上篇
    目录前言1、指针是什么1.1 指针变量1.2 指针是内存中一个最小单元的编号2、指针和指针类型2.1 指针±类型2.2 指针的解引用2.2.1 int* 类型的解引用2...
    99+
    2022-11-13
  • C语言指针超详细讲解下篇
    目录前言指针运算指针±整数指针-指针指针的关系运算指针和数组二级指针指针数组举例 1举例 2总结前言 本文接着上一篇内容，继续学习指针相关知识点。 指针运算 指针&pl...
    99+
    2022-11-13
  • C语言超详细讲解顺序表的各种操作
    目录顺序表是什么顺序表的结构体顺序表的接口函数顺序表相关操作的菜单顺序表的初始化添加元素陈列元素往最后加元素往前面加元素任意位置加元素删除最后元素删除前面元素 删除任意元素...
    99+
    2022-11-13
  • C语言超详细讲解双向带头循环链表
    目录一、双向带头循环链表的结构二、双向带头循环链表的函数接口1. 申请结点2. 初识化3. 打印4. 尾插尾删5. 头插头删6. 查找7. 中间插入和删除8. 判空及求链表长度9. ...
    99+
    2023-02-14
    C语言双向带头循环链表 C语言带头循环链表 C语言循环链表
  • C语言数据结构超详细讲解单向链表
    目录1.链表概况1.1 链表的概念及结构1.2 链表的分类2. 单向链表的实现2.1 SList.h（头文件的汇总，函数的声明）2.2 SList.c（函数的具体实现逻辑）2.2.1...
    99+
    2022-11-13
  • C语言超详细讲解字符串相乘
    目录前言一、分析思路二、使用步骤1、代码如下2、memset函数三、总结前言 我们已经知道，正常的两位整形数据通过*相乘，C语言中int为4字节，32bit（字节），其机器码第一位为...
    99+
    2022-11-13
  • C语言超详细讲解指针的使用
    目录指针概述自身类型指向类型代码例子数值型指针字符型指针单字符字符数组字符串型指针字符数组总结指针概述 C语言中指针也可以认为是一种类型，不同于数值型和字符型的类型。推演过去指针变量...
    99+
    2022-11-13
软考高级职称资格查询
软考职称历年真题下载
软考职称资料下载
热门wiki
近期文章
推荐阅读
热门问答
热门标签
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。

  • 官方手机版

  • 微信公众号

  • 商务合作