【数据结构】知识点总结(C语言)

news/2024/3/28 19:23:43/文章来源:https://blog.csdn.net/qq_59572329/article/details/129229883

线性表栈和队列串、数组和广义表树和二叉树查找排序


线性表

线性表(顺序表示)

线性表是具有相同特性元素的一个有限序列,数据元素之间是线性关系,起始元素称为线性起点,终端元素称为线性终点。

线性表的顺序表示又称为顺序存储结构或者顺序映像。顺序存储的定义:把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

顺序表的特点是:1、以物理位置表示相邻的逻辑关系;2、任意的元素均可以快速访问,故称为随机存取。

顺序表(Sequence List)的类型定义模板:

//顺序表定义模板
#define LIST_INIT_SIZE 100        //顺序表存储空间的初始分配
typedef struct {ElemType* elem;            //数据指针,动态分配存储空间int length;        //当前的长度
} SqList;

使用类型定义模板的案例:

//头文件包含
#include <stdio.h>
#include <stdlib.h>
//函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
//Status 是函数的类型,其值是函数结果状态代码
typedef int Status;
typedef char ElemType;
//顺序表的定义
#define MAXSIZE 100
typedef struct {ElemType* elem;int length;
} SqList;//顺序表的初始化函数
Status InitList_Sq(SqList* L)
{L->elem = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));if (!L->elem)exit(OVERFLOW);L->length = 0;return OK;
}
//销毁线性表
void DestroyList_Sq(SqList* L)
{if (L->elem)free(L->elem);L = NULL;
}
//清空线性表
void ClearList(SqList* L)
{L->length = 0;
}
//求线性表的长度
int GetLength(const SqList* L)
{return L->length;
}
//判断线性表是否为空
Status IsEmpty(const SqList* L)
{if (L->length == 0)return TRUE;elsereturn FALSE;
}
//线性表取第i个值
Status GetElem(const SqList* L, int i, ElemType e)
{if (i<1 || i>L->length)return ERROR;else{e = L->elem[i - 1];return OK;}
}
//线性表按值顺序查找
Status LocateElem(const SqList* L, const ElemType e)
{int i;for (i = 0; i <= L->length - 1; i++){if (L->elem[i] == e)return i + 1;        //查找成功返回元素位置}return 0;        //查找失败返回0
}
//顺序表的插入
Status InsertList_Sq(SqList* L, int n, const ElemType e)
{int i;if (n >= 1 && n <= L->length + 1)    //判断插入位置是否合法{if (L->length == MAXSIZE)        //判断存储空间是否已满return ERROR;for(i=L->length-1; i>=n-1; i--)        //插入位置及之后元素后移{L->elem[i+1] = L->elem[i];}L->elem[n - 1] = e;L->length += 1;return OK;}return ERROR;
}
//顺序表删除
Status DeleteElem(SqList* L, int n)
{int i;if (n >= 1 && n <= L->length){L->elem[n - 1] = 0;        //删除指定元素for (i = n - 1; i <= L->length - 1; i++)        //剩余元素移位{L->elem[i] = L->elem[i + 1];}L->length--;        //顺序表长度-1return OK;}return ERROR;
}
//顺序表显示
void ShowList_Sq(const SqList* L)
{if (L->length == 0)puts("The SqList is empty!");else{int i;for (i = 0; i < L->length; i++){printf("%d ", L->elem[i]);}putchar('\n');printf("The length of SqList is %d\n", L->length);}
}
//合并两个顺序表,将L2合并到L1中
Status MergeList_Sq(SqList* L1, const SqList* L2)
{if (L1->length == 0 || L2->length == 0){puts("Length must be non-zero!");return ERROR;}else if (L1->length + L2->length > MAXSIZE){puts("Overflow");return OVERFLOW;}else {int i;for (i = 0; i <= L2->length - 1; i++){L1->elem[i + L1->length] = L2->elem[i];}L1->length += L2->length;return OK;}
}
int main(void)
{SqList my_list;ElemType a, b, c, d, e, f;a = 1;b = 2;c = 3;d = 4;e = 5;f = 6;SqList my_list2;InitList_Sq(&my_list);InsertList_Sq(&my_list, 1, a);InsertList_Sq(&my_list, 2, b);InsertList_Sq(&my_list, 3, c);InsertList_Sq(&my_list, 1, d);InsertList_Sq(&my_list, 2, e);InsertList_Sq(&my_list, 3, f);//printf("%d\n", LocateElem(&my_list, a));//ShowList_Sq(&my_list);//DeleteElem(&my_list, 2);ShowList_Sq(&my_list);InitList_Sq(&my_list2);InsertList_Sq(&my_list2, 1, a);InsertList_Sq(&my_list2, 2, b);InsertList_Sq(&my_list2, 3, c);ShowList_Sq(&my_list2);MergeList_Sq(&my_list, &my_list2);ShowList_Sq(&my_list);return 0;
}
顺序表的优缺点
优点:1、存储密度大;2、可以随机存取表中任一元素。
缺点:1、在插入、删除某一元素时,需要移动大量其他元素;2、浪费大量存储空间;3、属于静态存储形式,数据元素的个数不能够自由扩充。

线性表(链式表示)

链式存储结构的特点
1、结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序映像或链式映像。
2、访问时只能通过头指针进入链表,并通过每个结点的指针域依次向后顺序扫描其余结点,所以寻找第一个结点和最后一个结点所花费的时间不等,这种存取元素的方式称为顺序存取。

链表(Link List)的分类:单链表、双链表、循环链表

a、单链表的实现
// 链表定义模板
typedef struct Lnode {ElemType data;struct Lnode* next;            //注意这里需要struct关键字
}Lnode, *LinkList;

单链表基本操作的实现

单链表实现完整算法

//头文件导入
#include <stdio.h>
#include <stdlib.h>
//函数结果状态代码
#define OK 1
#define ERROR 0
//Status 是函数的类型,其值是函数结果状态代码
typedef int Status;
typedef int ElemType;
//单链表
typedef struct Signle_Link_List{ElemType data;struct LNode* next;
} LNode, *LinkList;//创建空链表
Status InitLinkList(LinkList* L)
{*L = (LinkList)malloc(sizeof(LNode));if (*L == NULL)return ERROR;(*L)->next = NULL;return OK;
}
//判断链表是否为空
int IsEmptyLinkList(const LinkList* L)
{if ((*L)->next == NULL)return 1;elsereturn 0;
}
//单链表的销毁
Status DestoryLinkList(LinkList* L)
{LNode* p;while (*L != NULL){p = *L;*L = (*L)->next;free(p);}return OK;
}
//清空单链表
Status ClearLinkList(LinkList* L)
{LNode* p, * q;q = (*L)->next;while (q != NULL){p = q;q = q->next;free(p);}(*L)->next = NULL;return OK;
}
//求单链表的表长
int LenLinkList(const LinkList* L)
{LNode* p;p = (*L)->next;int i = 0;while (p){i++;p = p->next;}(*L)->data = i;            //将长度存储到L头结点的数据域中return i;
}
//取出单链表中第i个元素
Status LocateElem(const LinkList *L, int i, ElemType *e)
{int j = 1;LNode* p;p = (*L)->next;while (p && j < i){j++;p = p->next;}if (!p || j > i)        //如果待查找的元素大于链表长度或者小于1,查找错误return ERROR;*e = p->data;return OK;
}
//单链表按值查找,返回LNode
LNode* LocateElem_V_LNode(const LinkList *L, ElemType value)
{LNode* p;p = (*L)->next;while (p && p->data != value)        //p不为空指针,并且没找到{p = p->next;}return p;            //找到返回结点的地址,没找到返回NULL
}
//单链表按值查找,返回元素位置
int LocateElem_V_Index(const LinkList *L, ElemType value)
{int j = 1;LNode* p;p = (*L)->next;while (p && p->data != value){j++;p = p->next;}if (!p)return 0;        //没找到,返回0elsereturn j;        //找到,返回第几个结点
}
//单链表插入,在第i个结点之前插入一个结点
Status InsertLinkList(LinkList *L, int i, ElemType value)
{LNode* p;p = (*L)->next;int j = 1;while (p && j < i - 1)        //找到第i-1个结点{j++;p = p->next;}if (!p || j > i - 1)        //i大于表长+1,或者小于1,插入位置非法return ERROR;LNode* newlnode;newlnode = (LNode*)malloc(sizeof(LNode));newlnode->data = value;newlnode->next = p->next;p->next = newlnode;return OK;
}
//单链表删除,删除第i个结点
Status DeleteLinkList(LinkList *L, int i)
{LNode* p, * q;int j = 1;p = (*L)->next;while (p && j < i - 1){j++;p = p->next;}if (!p || j > i - 1)return ERROR;q = p->next;p->next = q->next;free(q);return OK;
}
//单链表建立-头插法
void CreateLinkList_H(LinkList* L, int n)
{*L = (LinkList)malloc(sizeof(LNode));(*L)->next = NULL;                    //先建立一个头结点int i;for (i = n; i > 0; i--){LNode* newlnode;newlnode = (LNode*)malloc(sizeof(LNode));printf("Enter the node data:_____\b");scanf("%d", &newlnode->data);newlnode->next = (*L)->next;(*L)->next = newlnode;}
}
//单链表建立-尾插法
void CreateLinkList_R(LinkList *L, int n)
{*L = (LinkList)malloc(sizeof(LNode));(*L)->next = NULL;                    //先建立一个头结点LNode* p;p = *L;int i;for (i = n; i > 0; i--){LNode* newlnode;newlnode = (LNode*)malloc(sizeof(LNode));printf("Enter the node data:___\b");scanf("%d", &newlnode->data);newlnode->next = NULL;p->next = newlnode;p = p->next;}
}
//显示单链表
void ShowLinkList(const LinkList* L)
{LNode* p;p = (*L)->next;if (!p){puts("The LinkList is empty");return;}int i = 1;while (p){printf("%d : %d\n", i, p->data);i++;p = p->next;}putchar('\n');
}
//测试函数
int main(void)
{LinkList my_list;my_list = NULL;ElemType answer = 0;//InitLinkList(my_list);//CreateLinkList_H(&my_list, 3);        //测试头插法建立链表CreateLinkList_R(&my_list, 3);            //测试尾插法建立链表//ClearLinkList(&my_list);                //测试清空链表ShowLinkList(&my_list);//DestoryLinkList(&my_list);                //测试销毁链表printf("%s\n",IsEmptyLinkList(&my_list) >0?"LinkList is Empty":"LinkList isn't Empty");        //测试判断链表函数printf("The length of LinkList is %d\n", LenLinkList(&my_list));        //测试求长度函数LocateElem(&my_list, 3, &answer);printf("The %d elem is %d\n", 3, answer);        //测试取元素函数LNode *answer1;answer1 = LocateElem_V_LNode(&my_list, 2);printf("The answer is %d\n", answer1->data);        //测试取元素函数printf("The Index of 3 is %d\n", LocateElem_V_Index(&my_list, 3));            //测试取元素函数InsertLinkList(&my_list, 2, 10);        //测试增加结点函数ShowLinkList(&my_list);DeleteLinkList(&my_list, 3);            //测试删除结点函数ShowLinkList(&my_list);                    return 0;
}
b、单向循环链表的实现
c、双向链表的实现
//双向链表的定义
typedef struct DuLNode {ElemType data;struct DuLNode* prior, * next;
} DuLNode, *DuLinkList;

双向链表的操作

  1. 双向链表的插入

  1. 双向链表的删除

d、双向循环链表的实现
链表的优缺点

各种链表的比较

栈和列队

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_74707.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

sed 功能详解

介绍sedsed是一种流编辑器&#xff0c;它一次处理一行内容&#xff0c;把当前处理的行存储在临时缓冲区中&#xff08;buffer&#xff09;,称为"模式空间"&#xff0c;接着sed命令处理缓冲区中的内容&#xff0c;处理完成后&#xff0c;把缓冲区的内容送往屏幕&#…

RCEE: Event Extraction as Machine Reading Comprehension 论文解读

RCEE: Event Extraction as Machine Reading Comprehension 论文&#xff1a;Event Extraction as Machine Reading Comprehension (aclanthology.org) 代码&#xff1a;jianliu-ml/EEasMRC (github.com) 期刊/会议&#xff1a;EMNLP 2020 摘要 事件提取(Event extraction,…

哪个品牌蓝牙耳机性价比高?性价比高的平价蓝牙耳机推荐

现如今&#xff0c;随着蓝牙技术的进步&#xff0c;蓝牙耳机在人们日常生活中的便捷性更胜从前。越来越多的蓝牙耳机品牌被大众看见、认可。那么&#xff0c;哪个品牌的蓝牙耳机性价比高&#xff1f;接下来&#xff0c;我给大家推荐几款性价比高的平价蓝牙耳机&#xff0c;一起…

软件测试面试问答

笔试 笔试的话我们需要揣测具体会考什么内容&#xff0c;我们可以通过招聘信息去了解该公司需要什么样的技能&#xff0c;以此来准备笔试。一般必考的内容会有编程&#xff0c;测试用例设计&#xff0c;工作流程&#xff0c;逻辑思维等内容&#xff0c;除此之外每个公司可能还会…

移动端监听物理返回

业务场景&#xff1a;用户没有填完数据却不小心点到了回退按钮&#xff0c;此时需要展示确认弹框项目场景&#xff1a;vue2 uni-app Chrome Dev调试工具代码片段&#xff1a;onLoad(options){// 将当前url地址添加到浏览器的历史记录中window.history.pushState(null, null, …

OSI和TCP/IP网络模型细讲

文章目录一、OSI七层参考模型二、TCP/IP体系结构三、TCP/IP参考模型四、沙漏计时器形状的TCP/IP协议族五、两种国际标准对比相似之处不同之处一、OSI七层参考模型 OSI参考模型共分为7层&#xff0c;低三层面向通信&#xff0c;可用软硬件实现&#xff1b;高三层面向信息处理&am…

一个基于 LKM 的 Linux 内核级 rootkit 的实现

博客已迁移至&#xff1a;https://gls.show/ GitHub链接 演示Slides overview rootkit是一种恶意软件&#xff0c;攻击者可以在获得 root 或管理员权限后安装它&#xff0c;从而隐藏入侵并保持root权限访问。rootkit可以是用户级的&#xff0c;也可以是内核级的。关于rootk…

Android 实现菜单拖拽排序

效果图简介本文主角是ItemTouchHelper。它是RecyclerView对于item交互处理的一个「辅助类」&#xff0c;主要用于拖拽以及滑动处理。以接口实现的方式&#xff0c;达到配置简单、逻辑解耦、职责分明的效果&#xff0c;并且支持所有的布局方式。功能拆解功能实现4.1、实现接口自…

ARM的工作模式和37个寄存器

一、ARM的工作模式 ARM一共有7种工作模式 模式含义User非特权模式&#xff0c;大部分任务执行在这种模式FIQ当一个高优先级&#xff08;fast) 中断产生时将会进入这种模式IRQ当一个低优先级&#xff08;normal) 中断产生时将会进入这种模式Supervisor当复位或软中断指令执行时…

CISP注册信息安全专业人员证书

一、什么是“CISP”&#xff1f; 注册信息安全专业人员(Certified Information Security Professional&#xff0c;简称“CISP”)&#xff0c;是安全行业最为权威的安全资格认证&#xff0c;由中国信息安全测评中心统一授权组织&#xff0c;中国信息安全测评中心授权培训机构进…

GMP洁净净化车间布局建设|喜格净化设计建设

GMP洁净净化车间布局建设方案应该根据具体的生产流程、工艺要求和产品特点进行设计。以下喜格SICOLAB基本的设计原则和注意事项&#xff1a;&#xff08;1&#xff09;设计洁净度级别&#xff1a;根据产品特点和生产工艺要求&#xff0c;确定洁净度级别&#xff0c;一般分为100…

OpenCV 图像轮廓检测

本文是OpenCV图像视觉入门之路的第15篇文章&#xff0c;本文详细的介绍了图像轮廓检测的各种操作&#xff0c;例如&#xff1a;轮廓检索模式、轮廓逼近算子等操作。 图像轮廓是具有相同颜色或灰度的连续点的曲线&#xff0c;轮廓在形状分析和物体的检测和识别中很有用。图像轮廓…

2023年鞋服配饰行业如何玩转全域经营?

2023年&#xff0c;鞋服配饰行业私域已进入深水区&#xff0c;这就对私域运营提出了更高的挑战和目标&#xff0c;企业纷纷发力以私域为基石、以消费者为核心的全域经营。 不过&#xff0c;虽然鞋服配饰行业私域起步早&#xff0c;玩法多。但在迈向全域经营的过程中&#xff0…

IntelliJ插件开发教程之新建项目

JetBrains公司系列产品IDEA、WebStrom、PyCharm、CLion、GoLand等都是基于IntelliJ Platform开发而成&#xff0c;掌握IntelliJ插件开发技能便能拥有提升开发效率的终极武器。本教程Demo源码请微信公众号“开发效率”进行获取。阅读原文如果您是JetBrains产品的用户&#xff0c…

【打卡】图分析与节点嵌入

背景介绍 图&#xff08;Graphs&#xff09;是一种对物体&#xff08;objects&#xff09;和他们之间的关系&#xff08;relationships&#xff09;建模的数据结构&#xff0c;物体以结点&#xff08;nodes&#xff09;表示&#xff0c;关系以边&#xff08;edges&#xff09;…

【数电基础】——数制和码制

目录 1.概述 1.信号&#xff08;电路&#xff09;的功能 2.信号的分类&#xff1a; 3.数字信号的输入和输出的逻辑关系表示方法 2.数制 1.十进制&#xff08;D/d&#xff09; 2.二进制(B/b) 3.八进制&#xff08;O/o&#xff09; 4.十六进制&#xff08;H/h&#xff09;…

腾讯TIM实现即时通信 v3+ts实践

目录 初始化sdk 功能描述 初始化 准备 SDKAppID 调用初始化接口 监听事件 发送消息 创建消息 创建文本消息 登录登出 功能描述 登录 登出 销毁 登录设置 获取会话列表 功能描述 获取会话列表 获取全量的会话列表 历史消息 功能描述 拉取消息列表 分页拉取…

C++ Primer Plus 第6版 读书笔记(2)第2章 开始学习 C++

C是在 C 语言基础上开发的一种集面向对象编程、泛型编程和过程化编程于一体的编程语言&#xff0c;是C语言的超集。本书是根据2003年的ISO/ANSI C标准编写的&#xff0c;通过大量短小精悍的程序详细而全面地阐述了 C的基本概念和技术&#xff0c;并专辟一章介绍了C11新增的功能…

Telnet 基础实验2: SSH 实验

Telnet 基础实验2&#xff1a; SSH 实验 本实验只能使用 eNSP中 AR 系统的路由器做 拓扑图 SSH &#xff1a; Secure Shell 是一个网络安全协议&#xff0c;基本于 TCP 协议 22 端口传输数据&#xff0c;通过对网络数据的加密&#xff0c;使其能够在一个不安全的网络环境中&a…

浅析Tomcat架构上的Valve内存马(内存马系列篇十一)

写在前面 这篇也是在Tomcat容器上面构造的内存马(收回之前说的不搞Tomcat了)&#xff0c;这是建立在Tomcat的管道上面做文章的一个内存马的实现方式。这是内存马系列的第十一篇文章了。 前置 什么是Pipeline-Valve管道&#xff1f; 根据前面Tomcat架构的相关知识&#xff0…