没有合适的资源?快使用搜索试试~ 我知道了~
浅谈数据结构C++实现中的顺序表与二叉树算法
需积分: 4 0 下载量 104 浏览量
2024-09-14
11:34:01
上传
评论
收藏 2.27MB PDF 举报
温馨提示
内容概要:该资料介绍了多种经典的数据结构与相关的算法。涵盖内容包括但不限于算法复杂度评估、单链表的操作、各类字符串匹配方法(例如Boyer-Moore)、图的各种遍历技术、多种常见的排序技巧(像冒泡排序、快速排序、希尔排序等)、以及诸如Huffman树这样的实用结构。文中通过具体的实例展示了如顺序表等基本数据类型的构建方法和技术要点,并对每一个主题深入探讨了相应的理论背景及具体的应用场景。同时也详细地分析了排序算法的时间和空间复杂度,提供了大量实用性的参考示例代码。 适合人群:有一定程序设计基础知识的初级开发者或是希望进一步理解数据结构的人士。 使用场景及目标:适用于正在探索高级编码技能的学生、自我提升的职业程序员或者想深入研究数据结构特性以优化项目设计的研发工程师们。 阅读建议:推荐学习者跟随书中指引,亲自编写相关代码来进行实际操作测试,有助于深化对各种算法和数据组织方式的理解与掌握。通过书里的案例剖析,逐步掌握高效的数据结构应用方法。
资源推荐
资源详情
资源评论
《浅谈数据结构C++实现》系列分享专栏
简介
浅谈数据结构C++实现,整理来自博客园-不归路
文章
顺序表
数据结构及算法综述
算法复杂度
单链表
浅谈数据结构-字符串匹配
浅谈数据结构-Boyer-Moore算法
浅谈数据结构-树
浅谈数据结构-二叉树
浅谈数据结构-树和二叉树之间关系
Huffman树及其应用
浅析数据结构-图的基本概念
浅析数据结构-图的遍历
浅谈数据结构-最短路径
浅谈数据结构-拓扑排序
浅谈数据结构-查找
浅谈数据结构-顺序表查找
浅谈数据结构-二叉排序树
浅谈数据结构-排序
浅谈数据结构-交换排序(冒泡、快速)
浅谈数据结构-插入排序(直接插入、希尔排序)
浅谈数据结构-选择排序(简单、堆排序)
顺序表
前言
顺序表是在计算机内存中以数组的形式保存的线性表,是指使用一组连续分配存储单元有序的存储数据元素的线性结构。
顺序表还有后面讲的单链表、循环链表、双链表都是链表,根本区别是在内存中存储数据的方式不同,每种方式都有优劣点,这也根据应用场景的不同,决定用什么方式存储数
据。
基本算法
在线性表中算法操作中,异常判断很重要,包括链表是否为空,插入位置是否正确等等。
- 插入数据元素
在顺序表中第n个位置插入新的元素e。
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>
/***********************************************************************************************************************
第一部分,数据结构、宏定义
***********************************************************************************************************************/
#define MAXSIZE 10
typedef enum { // 状态码
OK = 0,
ERROR = 1
} STATU;
typedef enum { // C语言中没有bool型,为方便,自定义一个BOOL型
TRUE = 0,
FALSE = -1
} BOOL;
typedef int ElemType; // 元素类型
typedef struct { // 顺序表的结构类型
ElemType data[MAXSIZE];
int length;
} SqList;
/***********************************************************************************************************************
第二部分,函数实现
***********************************************************************************************************************/
/*******************************************************************************
Funtion : initList
Description : 初始化一个空的顺序表
*******************************************************************************/
void initList(SqList *pList) {
pList->length = 0;
}
/*******************************************************************************
Funtion : createList
Description : 根据数组 elems 构建一个顺序表
*************************************************/
STATU createList(SqList *pList, ElemType elems[], int size) {
int i = 0;
// 判断数组大小是否超过最大限制
if (size > MAXSIZE)
return ERROR;
for (i = 0; i < size; i++) {
for (i = 0; i < size; i++) {
pList->data[i] = elems[i];
}
pList->length = size;
return OK;
}
/*******************************************************************************
Funtion : insertElem
Description : 在顺序表中第 pos 个位置插入元素 elem
*******************************************************************************/
STATU insertElem(SqList *pList, int pos, ElemType elem) {
int i = 0;
// 判断要插入的位置是否合理
if (pos < 0 || pos > pList->length)
return ERROR;
// 将data[pos]及后面的元素都向后移动一个位置
for (i = pList->length - 1; i > pos; i--) {
pList->data[i] = pList->data[i-1];
}
pList->data[pos] = elem;
pList->length++; // 顺序表长度加1
return OK;
}
/*******************************************************************************
Funtion : removeElem
Description : 在顺序表中移除第 pos 个元素,并由 pElem 返回其值
*******************************************************************************/
STATU removeElem(SqList *pList, int pos, ElemType *pElem) {
int i = 0;
// 判断要删除的位置是否合理
if (pos < 0 || pos > pList->length)
return ERROR;
*pElem = pList->data[pos];
// 将data[pos]后面的元素都向前移动一个位置
for (i = pos; i < pList->length; i++) {
pList->data[i] = pList->data[i+1];
}
pList->length--; // 顺序表长度减1
return OK;
}
/*******************************************************************************
Funtion : getElem
Description : 获取顺序表上位置为 pos 的元素,并由 pElem 返回其值
*******************************************************************************/
STATU getElem(SqList list, int pos, ElemType *pElem) {
// 判断位置是否合理
if (pos < 0 || pos > list.length - 1)
return ERROR;
*pElem = list.data[pos];
return OK;
}
}
/*******************************************************************************
Funtion : locateElem
Description : 获取元素 elem 在顺序表上第一次出现的位置,如果不存在返回 -1
*******************************************************************************/
int locateElem(SqList list, ElemType elem) {
int pos = 0;
for (pos = 0; pos < list.length; pos++) {
if (elem == list.data[pos])
return pos;
}
return -1;
}
/*******************************************************************************
Funtion : printList
Description : 打印整个顺序表
*******************************************************************************/
void printList(SqList list) {
int i = 0;
if (0 == list.length) {
printf("SqList is empty\n");
return;
}
printf("SqList:");
for (i = 0; i < list.length; i++) {
printf(" %d", list.data[i]);
}
printf("\n");
}
View Code
综述
顺序的创建的初始化就是相当于对数组的初始化,获取元素和位置,也和数组相同,关键是在删除和插入的时需要元素进行移动。在插入操作时,不能超过最大长度,如果超过
需要扩容。
后面讲详细讲解线性表和链表的应用场景
版权声明:本文为博主原创文章,未经博主允许不得转载。
数据结构及算法综述
1 数据
序号序号名称名称 定义定义 举例举例
1 数据 对客观事物的符号表示,在计算机中就是能被识别的符号集合 数值、图片、视频、音频等形式
2 数据项 数据中具有独立含义,不可分割的最小数据单位,客观实体一种特征数据表示 成员变量
3 数据元素过个相关数据项的集,一个客观实体多种实体特征的数据描述,计算机加工的进本单位类似结构体抽象的数据类型
数据元素按其组成分为简单性数据元素(单个数据项)和复杂性数据元素(多个数据项)
2 数据结构
数据结构:相互之间存在一种或者多种特定关系的数据元素集合。表示为:数据结构=数据+关系。
同一个数据元素集合,逻辑关系不同,构成不同数据结构。
数据结构分为逻辑结构和存储结构。
逻辑结构:对数据及其关系抽象逻辑描述
序号序号名称名称 定义定义 备注备注
1 集合结构数据元素之间未定义任何关的松散集合 图2.1
2 线性结构数据元素之间定义了次序关系的集合(全序集合),描述的是1对1关系 图2.2
3 树形结构数据元素之间定义了层次关系的集合(偏序集合),描述的是1对多关系图2.3
4 图状结构数据元素之间定义了网状关系的集合,描述的是多对多关系 图2.4
图2.1集合结构
剩余65页未读,继续阅读
资源评论
天涯学馆
- 粉丝: 2627
- 资源: 436
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 自己写的一个很小的工具,用于替换文件的扩展名 文件扩展名匹配的才会被替换,如果不指定原始扩展名,将修改所有文件的扩展名为新扩展名 如果新扩展名为空,则替换后文件将没有扩展名
- nginx整合lua脚本demo
- 欧标TYPE 2桩端充电枪
- (22782460)单片机设计(详细教程MSP430.zip
- UE-ORCA.zip
- (11696858)条形码生成打印
- 个人使用资源,请勿下载使用
- (180014056)pycairo-1.21.0-cp37-cp37m-win-amd64.whl.rar
- (3268844)3G无线基本知识.pdf
- 捷米特JM-PN-EIP(Profinet转Ethernet-IP)应用案例.docx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功