C++在C的基础上深加了对面向对象编程和泛型编程的支持。

C++面向对象的新技术是：对象、类、封装、数据隐藏、多态、继承。

C++融合了3种不同的编程方式，C代表的过程性语言，C++在C语言基础上添加的类代表的面向对象语言、C++模板支持的泛型编程。

使用C++的原因之一是为了利用其面向对象的特征，要利用这种特征，必须对C语言有较深入的了解。因为它提供了基本类型、运算符、控制结构和语法规则。从C过渡到C++的时候不再是仅仅学习更多的关键字（学习C的过程就是学习关键字的过程）和新的数据结构，从C过渡到C++的学习量就像从头学习C的内容一样大，在过渡到C++的时候，必须摒弃一些编程习惯，学习C++需要更多的拓展思维。

20世纪70年代，贝尔实验室的Dennis Ritche致力于开发UNIX操作系统，希望有一种语言能将低级语言的效率、硬件访问能力和高级语言的通性、可移植性融合在一起，于是他在旧语言的基础上开发了C语言。其所遵循的旧理念是强调程序的算法方面。从概念上说过程化编程首先要确定计算机应采用的操作，然后使用编程语言来实现这些操作。C语言还采用了结构化编程和自顶向下的设计（C将大型程序分解为小型、编辑管理的任务）

面向对象编程（OOP）强调的是数据，OOP不同于过程性语言试图使问题满足语言的过程新方法，而是试图让语言来满足问题的要求。其理念是设计与问题本质特性相对应的数据格式。

在C++中，类是一种规范，它描述了这种新型数据格式对象是根据这种规范构造的特定数据结构。

类规定了可使用哪些数据来表示对象，以及可以对这些数据执行哪些操作。

OOP程序设计方法首先设计类，他们准确的表示了程序要处理的东西，然后设计一个使用这些类的对象的程序，从低级组织（如类）到高级组织（如程序）的处理过程叫做自下向上的编程。

**OOP程序设计不仅仅是将数据和方法合并为类定义。**多态能够为数算符和函数创建多个定义（通过编程上下文来确定使用哪个定义），继承让能使用旧类派生出新类。

OOP引入了很多新的理念，使用的编程方法不同于过程性编程。它不是将重点放在任务上，而是放在表示概念上。

设计有用、可靠的类是一项很艰巨的任务，幸运的是在编程中可以使用已有的类（STL），C++真正的优点之一是：可以方便的重（chong）用和修改现有的经过只系测试过的代码。

泛型编程强调的是独立于特定数据结构，和OOP侧重点不同，OOP是一个管理大型项目的工具，而泛型编程提供了执行常见任务的工具。术语泛型指的是创建独立于类型的代码。

OOP不凡赋予了C++语言将问题所涉及的感念联系起来的能力。C部分则赋予了C++语言紧密联系硬件的能力。如果忽略C++面向对象的特性，将错过很多有用的东西。

数据结构第二章便讲了线性表，其实我们常说线性表一般为数组和链表，熟不知线性表其实是一种逻辑结构，而链表和数组分别是两种存储结构（非顺序和顺序映像）。

先说线性结构，线性结构是在数据元素的非空有限集中：

1.存在唯一的一个被称作“第一个”的数据元素；

2.存在惟一的一个被称作“最后一个”的数据元素；

3.除了第一个之外，集合中的每一个数据元素均只有一个前驱；

4.除了最后一个之外，集合中每个数据元素均只有一个后继。

其实以上四条便是线性表的特征，这四句罗利啰嗦的话就是描述了一条线性的，有前驱后继的数据结构。

线性表是n个数据元素的有限序列，在稍复制的线性表中，一个数据元素（一个结点）可以由多个数据项组成。

线性表中元素的个数n（n>=0）定义为线性表的长度，n=0时称为空表。在非空表中的每一个数据元素都有一个确定的位置（只有这样才方便查找）。

线性表是一种非常灵活的数据结构，它的长度可以根据需要而变化，对线性表的数据元素，不仅可以询问、修改，还可以插入和删除（如果这几个功能线性表都不能完成，还学它何用？）。其实对于线性表，或者说包括其他各种数据结构，建立和访问是基础，不会建立和访问可以说对这种数据结构完全不懂，加上会修改可以说能用这种数据结构，再加上会删除才可以说会用这种数据结构，再加上能抽象出自己的应用模型、活用才能说掌握了这一种数据结构。

线性表的顺序表示是指用一组地址连续的存储单元依次存储线性表的数据元素（就像数组）。

第i+1个数据元素的存储位置LOC（ai+1）和第i个数据元素的存储位置LOC（ai）之间满足：

LOC（ai+1）=LOC（ai）+ l；

一般来说，线性表的第i个数据元素ai的存储位置为

LOC（ai）=LOC（a1）+ l*（i-1）；

（l为每个元素的需占的存储单元，LOC（a1）为线性表的第一个元素的存储位置，通常被称作相性表的起始位置（废话）和基地址）。

线性表的这种机内表示称作线性表的顺序存储结构或顺序映像。通常称这种存储结构的线性表为顺序表，其特点是为表中相邻的元素ai和ai+1赋以相邻的存储位置LOC(ai)LOC(ai+1)。（其实就是通过元素在计算机内物理位置相邻来表示线性表中的数据元素之间的逻辑关系）。

数据结构一半是怎么存储，一半是怎么运用（算法），线性表的基本操作包括插入，删除。插入就是把元素x插入i位置后，其i到n的元素向后移动1个单位；删除：把第i个元素x删除后，第i+1到n元素向前移动1个单位。

当顺序存储结构的线性表中某个位置上插入或删除一个数据元素时，其时间消耗主要在移动元素上（换句话说，移动元素的操作为估计算法时间复杂度的基本操作），而移动元素的次数取决于插入或者删除元素的位置。

线性表的顺序存储结构可以方便的存取任一元素，但也造成了做插入删除操作时需要移动大量元素的缺点。

而链式存储结构，由于不要求逻辑上相邻的元素也在物理位置也相邻，没有顺序存储结构如上所具有的弱点，但同时也失去了快速的、直接访问的优点。

每个结点包括数据域，存储后继存储元素位置的域称之为指针域。

因为每个结点只包括一个指针与，故又称线性链表或单链表。

在研究链表的时候，我们只关心其逻辑顺序而不管实际机内位置。

关于链表的操作，插入：只需要修改第i-1个元素结点的指向地址和要插入的数据元素x的指向地址；删除，只需要修改第i-1个元素的指向地址，然后释放结点。

操作有点泛泛而谈，其实链表有很多活用的地方，甚至连建立链表也有头插法（逆向建链表）和尾插法（正向建链表）之分。

如果不用指针，可以使用游标来代替指针指示结点在数组中的相对位置，但这种存储结构需要分配出一个足够大的内存空间，为了和指针型链表相区别，我们给这种用数组来描述的链表起名叫做静态链表（前向星便是基于静态链表）。

对于静态链表，如果在删除操作之后，需要辨明数组中那些分量未被使用，解决的办法是将所有未使用的以及删除的用游链表或者一个备用链表每当进行插入时便可以从备用链表上取得第一个结点作为待插入的新结点。（类似专用来记录未被使用的元素下标的栈）。

尾巴指向头的链表为循环链表，当然静态链表也可以用去模来实现循环链表。

因为单链表有着只能从头到尾的单向性，在某些情况，会造成不便，因此，双向链表诞生了。其只不过是多了一个指向前一个结点的指针，操作比单向链表多了一点操作。

一元多项式的表示和相加（线性表的一个应用）

在数学上，一个余元多项式Pn（x）可按升幂写成：

Pn（x） = p0+p1x+p2x^2+.....+pn*n^n;

它可由n+1个系数来唯一确定。因此，在计算机里，它可用一个线性表p表示：p = （p0,p1,...,pn）;

不失一般性，多项式的相加减便可以用一对线性表来表示计算

但这样计算也有弊端，比如计算

S（x） = 1 + 3 * x^10000 + 2 * 3 * x^20000时，将浪费大量的内存（p1-p9999都是0）。这时，如果采用每个数据元素有系数和指数两个数据，那么将节省大量内存，当然，也会浪费查找带来的时间。

当然，这只是提供了一个思路，也算相性表的一个应用，线性表是一种十分灵活的数据结构，至于怎么用，全靠编程者个人，这也是为什么可以说数据结构可以成为使用者的艺术。