CategoryData Structure

DSACPP – 1:向量

vector类模板的示例代码存放在这个仓库里


概要

  • 前言
  • 声明
  • 属性
  • 方法

前言:为何需要vector?

“升级版”数列

 

声明

  • typedef int Rank; // 约定:将元素的相对位置称为秩,取值范围是[0, _size – 1]
  • #define DEFAULLT_CAPACITY 3 // 默认的初始容量,可调

属性

属性的命名习惯以下划线开头

用于动态空间管理

  • int _capacity:总容量
  • Rank _size:当前的实际规模,_size <= _capacity

指向所有元素的数组指针,用于实现元素访问

  • T* _elem

 

方法

DSACPP – 0.2:抽象数据类型用数据结构实现

抽象数据类型(ADT, Abstract Data Type)用数据结构实现,为分工(向内)和接口(向外)制定了统一的规范,是数据模型实现与应用的中介

  • ADT = 数据类型 + 相关操作
  • 数据结构 = 实现ADT的一套算法

 

数据结构的定义常应用C++中的类模板(class template),这是一种规范(安全、逻辑统一)、可扩展(用于组成新的数据结构)的通用方法

 …

DSACPP – 0.1:C++,加在何处?

题注:DSACPP的教学使用CPP实现。基于C++程序设计语言(第1~3部分)(原书第四版),针对一些可能有用的语法特性摘录如下

本文中“逸兴遄飞”、高屋建瓴的语句大概率是对原文内容的二次排版。在此谨对C++之父 Bjarne Stroustrup 在如此优雅而又强大的混合范式编程语言的创建和推广上的卓越贡献表示敬意

C++是一种通用程序设计语言,它强调富类型、轻量级抽象的设计和使用。C++特别适合开发资源受限的应用,例如可在软件基础设施中发现的那些应用……特别是,C++的设计目标就是足够灵活和通用,以便处理那些连它的设计者都未曾想象过的未来难题。

 

1.3.3 对C程序员的建议

程序员对C语言掌握得越好,似乎就越难避免用C风格编写C++程序,从而失去了很多潜在的优势,我对C程序员学习本书的建议是:

  1. 不要将C++看做增加了一些特性的C(光速打脸2333),你需要采用不同设计和风格
  2. 不要用C++来写C程序,这通常会令可维护性和性能都非常不好
  3. 将C++标准库作为学习新技术和新程序设计风格的老师,注意与C标准库的差异
  4. C++几乎从来不需要宏替换
  5. 在真正需要一个变量的时候再声明它,且声明后立即进行初始化
  6. 不要使用malloc(),new运算符可以完成得更好
  7. 避免使用void*、联合以及强制类型转换,这些特性会限制从类型系统获得的支持,而且会损害性能
  8. 尽量减少数组和C风格字符串的使用,通常可使用标准库中的string、array和vector,写出更简单也更易维护的代码
  9. 避免对指针进行算术运算
  10. 不要认为用C风格写出的程序更为高效,实际情况可能正好相反

菜鸟教程之C++教程内容对本文亦有贡献,在此致谢

 

概要

  • 类、模板
  • 名字空间
  • lambda表达式
  • 内存管理、参数传递、错误处理
  • 泛型程序设计与元编程简介

 

写在前面:

笔者之前接触过一些Python,故作为学习笔记的本文对于面向对象的基本概念没有着墨

本质

类(class)是…

DSACPP – 0:从算法开始

题注:目录 Archives/Computer Science/Data Structure/DSACPP 下存放的是由学堂在线上的清华大学邓俊辉教授开设的数据结构慕课总结而成的学习笔记

 

编程语言Pascal之父、图灵奖获得者Niklaus Wirth有一句名言:

“Algorithm + Data Structures = Programs”(算法 + 数据结构 = 程序)

这句话鲜明地指出了编程的学习路径——学好算法和数据结构。现在就先开始数据结构的学习吧!

 

概要

  • 数据结构与算法的关系
  • 算法模型
  • 衡量算法优劣的“尺子”——复杂度
  • “尺子”上的“刻度”——“大O记号”
  • 算法分析方法
  • 算法设计思想
  • 算法优化思路

 

数据结构与算法的关系

算法依存于数据结构,数据结构最终决定算法的优劣。对于程序运行效率提升的不竭追求,推动着算法和相应的数据结构的更新。借鉴数据结构自然发展的模式,课程也从对算法的简要介绍开始

 

算法模型

在数学、物理等相关学科的学习中,不难发现,实际问题研究中,模型是不可忽缺的。这样才能以较高的抽象程度抓住主要矛盾,研究问题的主要方面

算法也不例外。具体到计算机算法的研究,为了排除实际运行环境的机能差距等干扰、建立统一的算法分析工具与设计模式,有以下两种主要的算法模型