没有合适的资源?快使用搜索试试~ 我知道了~
首页C++数据结构入门指南:逻辑与存储结构详解
C++数据结构入门指南:逻辑与存储结构详解
需积分: 9 5 下载量 131 浏览量
更新于2024-07-17
2
收藏 1.97MB PDF 举报
数据结构笔记(C++版)是一份深入讲解数据结构基础知识的教程,它涵盖了软件设计中的关键技术和方法。数据结构是计算机科学中的基石,它涉及到如何组织和存储数据,以便高效地解决实际问题。本笔记的重点包括: 1. 研究内容:数据结构涉及抽象数据结构的组织,通过数学模型构建,如线性结构(如数组、链表)、树形结构(如二叉树、堆)、图结构(如图算法如最短路径、拓扑排序)以及集合数据结构。这些结构不仅用于描述数据元素间的逻辑关系,而且是构造求解算法的基础。 2. 术语解析:数据结构的核心概念包括数据(符号集合)、数据元素、数据项或字段,它们构成了数据的基本组成单位。逻辑结构如线性、树形和图,展示了数据在概念层面的组织方式,而存储结构则指数据在内存中的物理布局,强调两者并不总是相同的。 3. 算法介绍:算法被定义为解决特定问题的明确步骤,它具有输入、输出、确定性、有限性和可行性等特点。算法描述可以用自然语言、计算机语言或伪代码表达,如辗转相除法、韩信点兵问题和幻方问题的解决方案。 4. 算法分析:算法的性能评估主要关注时间性能(时间复杂度),即算法执行所需时间;空间性能,即辅助存储空间的大小;以及其他性能指标,如可读性和可移植性。时间复杂度以算法中语句执行次数来衡量,通常用大O表示法表示,它与问题规模的关系是算法性能的关键考虑因素。 通过这份笔记,学习者能够掌握数据结构在C++编程中的应用,理解不同数据结构的实现原理和操作效率,并学会如何根据问题需求选择合适的算法设计和优化策略。这对于理解程序设计的本质,提高编程技能,特别是在解决复杂问题时,具有重要意义。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/10928846/bgf.jpg)
资源由 www.eimhe.com 美河学习在线收集分享
int locate(const elementtype x)const;
error_code insert(const int i, const elementtype x);
error_code delete_element(const int i);
private:
elementtype data[maxlen];
int count;
… …//定义其它成员
};
运算实现:
list::list(){ count = 0; }
int list::length(){ return count; }
error_code list::get_element(const int i, elementtype &x)const{
if ( i <= 0 || i > count ) return range_error;
x = data[i – 1];
return success;
}
int list::locate(const elmenttype x)const{
for ( i = 0; i < length(); i ++ )
if ( data[i] == x ) return ( i + 1 );
return 0;
}
error_code list::insert(const int i,
const elementtype x){
if ( count == maxlen )
return overflow;
if ( i < 1 || i > length() + 1 )
return arrange_error;
for( j = count; j >= i; j -- )
data[j] = data[ j – 1 ];
//大量移动元素
data[j – 1] = x;
count ++;
return success;
}
0 1 2 … i-1 n-1 … maxlen-1
a
1
a
2
a
3
a
i
a
n
条件:顺序表不满;
序号正确,在[1, n+1]中
操作:a
i
~ a
n
后移
填入 x
Count ++
error_code list::delete_element(const int i){
if ( length() == 0 ) return underflow;
if ( i < 1 || i > length() ) return arrange_error;
for ( j = i + 1; j <= length(); j ++ )
data[j - 2] = data[j - 1];
count --;
return success;
}
算法分析:
x
![](https://csdnimg.cn/release/download_crawler_static/10928846/bg10.jpg)
资源由 www.eimhe.com 美河学习在线收集分享
head
a
1
a
2
a
n
∧
… …
插入时
在 i=1,2,…,n+1,元素移动的次数分别为 n,n-1,…,0。
在等概率的情况下,平均移动(n+1)n/2(n+1)=n/2 次
删除时
在 i=1,2,…,n,元素移动的次数分别为 n,n-1,…,0。
在等概率的情况下,平均移动(n-1)n/2n=(n-1)/2 次
结论:n 较大时,大量移动元素,耗时
解决:考虑不移动元素
5.3 链表
存储结构:
头指针 首元素结点 尾结点
插入操作分析:
三种位置:链表中间;链表尾;链表头
链表中间位置插入时,
s = new node;
s -> data = x;
s -> next = p -> next;
p -> next = s;
//两条语句顺序不能颠倒
链表尾位置插入时,
s = new node;
s -> data = x;
s -> next = p -> next;
p -> next = s;
链表头位置插入时,
s = new node;
s -> data = x;
s -> next = p;
p = s;
head = p;
结论:在链表头插入时与其它两种情况操作不一致
解决:引入“头结点”(附加结点),以保证操作的一致性
带头结点的单链表存储结构
class list{
public:
list();
head
a
1
a
2
a
3
a
n
∧
a
4
… …
head
a
1
a
2
a
3
a
n
∧
… …
s
x
p
head
a
1
a
2
a
3
a
n
∧
… …
s
x ∧
p
head
a
1
a
2
a
3
a
n
∧
… …
s
x
p
![](https://csdnimg.cn/release/download_crawler_static/10928846/bg11.jpg)
资源由 www.eimhe.com 美河学习在线收集分享
int length()const;
error_code get_element(const int i, elementtype &x)const;
node * locate(const elmenttype x)const;
error_code insert(const int i, const elmenttype x);
error_code delete_element(const int i);
private:
int count;
node * head;
… …//定义其它成员
};
运算实现:
list::list(){
head = new node;
head -> next = NULL;
count = 0;
}
int list::length()const{
p = head -> next;
n = 0;
while ( p != NULL ){
n ++;
p = p -> next;
}
return n; //若定义 count 成员,则直接返回 count 值即可
}
error_code list::get_element(const int i, element &x)const{
p = head -> next; j= 1;
while ( j != i && p != NULL ){
p = p -> next; j ++;
}
if ( p == NULL ) return arrange_error;
x = p -> data;
return success;
}
(考虑画流程图)
node * list::locate(const elementtype x)const{
p = head -> next;
while ( p != NULL )
if ( p -> data == x ) return p;
else p = p -> next;
return NULL;
}
error_code list::insert(const int i; const elementtype x){
![](https://csdnimg.cn/release/download_crawler_static/10928846/bg12.jpg)
资源由 www.eimhe.com 美河学习在线收集分享
p = head; j = 0;
while ( j != i -1 && p != NULL ){
p = p -> next; j ++;
}
if ( i < 1 || i > count + 1 ) // if ( p == NULL )
return arrange_error;
s = new node;
s -> data = x;
s -> next = p -> next;
p -> next = s;
count ++;
return success;
}
error_code list::delete_element(const int i){
p = head; j = 0;
while ( j != i -1 && p != NULL ){
p = p -> next; j ++;
}
if ( i < 1 || i > count ) // if ( p == NULL )
return arrange_error;
u = p -> next;
p -> next = u -> next;
delete u;
count --;
return success;
}
构造链表
基本方法:
从键盘输入数据,每读入一个元素,产生结点装入,
插入链表中,重复上述操作
讨论:产生结点:s = new node; s->data = x;
插入链表:插入位置如何确定,
有 表头 表尾 两个位置可选
头插法 尾插法
重复上述操作: 何时结束
封装的链表类中增加两个成员函数:
class list{
public:
… …
void create1(); //头插法
void create2(); //尾插法
};
头插法运算实现:
X 是结束
0
非 0
cin >> x
s = new node;
s -> data = x;
s -> next = head ->next;
head -> next =s ;
![](https://csdnimg.cn/release/download_crawler_static/10928846/bg13.jpg)
资源由 www.eimhe.com 美河学习在线收集分享
void list::create1(){
cin >> x;
while ( x != 结束符 ){
count ++;
s = new node;
s -> data = x;
s -> next = head -> next;
head -> next = s;
cin >> x;
}
}
尾插法运算实现:
void list::create2(){
cin >> x;
rear = head;
while ( x != 结束符 ){
count ++;
s = new node;
s -> data = x;
rear -> next = s;
rear = s;
rear -> next = NULL;
cin >> x;
}
}
练习:A、B 链表之间复制
void copy(list A, list &B){
B = new node;
B -> next = NULL;
PA = A -> next;
PB = B;
while ( PA != NULL ){
s = new node;
s -> data = PA -> data;
PB -> next = s;
PB = s;
PB -> next = NULL;
PA = PA -> next;
}
}
练习:
A 表分成奇、偶两个子表 A、B(A 表做删除,B 表做插入)
递增有序链表集合 求 交 并 差 子集,考虑时空复杂度
head
a
1
a
2
a
n
∧
… …
s
x
head
a
1
a
2
a
n
∧
… …
rear
x ∧
s
剩余90页未读,继续阅读
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://profile-avatar.csdnimg.cn/577cd9972cc541d4bd86081e88d66fbf_machen_smiling.jpg!1)
machen_smiling
- 粉丝: 507
- 资源: 1955
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- 中国微型数字传声器:技术革新与市场前景
- 智能安防:基于Hi3515的嵌入式云台控制系统设计
- 手机电量低时辐射真增千倍?解析手机使用谣言
- 56F803型DSP驱动的高精度大功率超声波电源控制策略研究
- ARM与GPRS结合的远程监测系统设计
- GPS与RFID技术结合的智能巡检系统设计
- CPLD驱动的低功耗爆炸场温度测试系统设计
- 基于FPGA的智能驱动控制系统:可扩展设计与工业网络协议
- 基于ATmega128和CH374的嵌入式USB接口设计
- 基于AT89C52的温度补偿超声波测距仪:高精度设计与应用
- MSP430F448单片机在交流数字电压表中的应用
- 提升变频器应用效率的12项实用技巧
- STM32F103在数字电镀电源并联均流系统中的应用
- PSpice仿真下的升压开关电源设计:拓扑分析与CCM稳定性提升
- 轻巧高效:MSP430主导的低成本无线传感器网络节点设计
- FPGA在EDA/PLD中实现LVDS接口的应用解析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)