计算机科学及编程导论

计算机科学以程序为基础，而且始于程序，也终于程序。本书是程序类课程学习的先导，也是基于程序的计算机专业知识学习的引领。

本书不是那种概念汇集、等量齐观的概括性模式，而是程序优先、程序生成概念、从低级到高级的实践——认知模式。

程序=算法 数据结构。数据结构是一组有组织的数据和对数据的基本操作，算法是用基本操作表示的对数据处理的有限步骤。数据结构一般都是用程序语言表示的，程序语言是数据结构描述的工具，因此程序也都是某种语言程序。算法越来越复杂，同时要求程序易写、易读、易维护，以及足够高效，这就带动了数据结构及程序语言的发展，发展的程序语言反过来又扩展了算法。算法和数据结构是一对矛盾，它们的相互作用推动了程序设计的发展。因为C和C  是核心程序语言，所以本书从中选择了部分有代表性的程序设计来说明这个发展过程，并以此为基础，引领计算机专业知识的学习。

本书内容概要

（1） 第1章机器语言模式。用若干条虚拟的简单机器指令作为虚拟的计算机，同时用一个简单的求和程序引入存储器、地址、寄存器、程序计数器等概念。然后用一个方程的两种求解程序，说明算法和指令集的相互作用关系，同时引入程序入口地址、子程序调用、断口地址、现场保护、栈、复杂指令集和精简指令集等概念。后，通过分析机器语言的局限性，引入汇编语言、汇编程序等概念。

（2） 第2章C语言模式。为克服机器语言和汇编语言的局限性而进入基于简单类型的C语言模式，并用单个整数的处理程序说明这种语言的编程模式，然后用这个程序的变化来引入输入输出标准函数、循环结构、函数等概念。用一批整数的处理程序引入数组和指针、值传递和指针传递、const型指针、动态数组等概念。（3） 第3章顺序表。数组是有局限性的，为克服它的局限性引入结构和顺序表。

（4） 第4章从C到C  。分析顺序表所暴露出来的C语言固有的局限性，为克服这些局限性引入内联函数、操作符函数、函数重载、引用型、函数模板等C  概念。

（5） 第5章顺序表类。运用第4章引入的C  概念，把C顺序表转换为C  顺序表类。这是一个从C到C  的平滑过渡模型，这曾是很多纠结于C和C  的人所心怀的希望。

（6） 第6章非线性结构与递归。通过斐波那契数列求解的非线性结构引入递归概念，然后通过汉诺塔、快速排序和八皇后问题，引入归纳证明法，它与递归紧密相关。

/计算机科学及编程导论前言/（7） 第7章数据库。通过C  的4个表处理程序引入关系数据库和结构化查询语言SQL。

（8） 第8章程序性能。通过典型程序的语句统计，引入空间复杂度和时间复杂度分析，其中涉及操作计数、步数、渐进记法等概念。

（9） 第9章计算理论。借助一个可以实现加1操作的图灵机，引入丘奇·图灵论题。借助一个通用语言Bare Bones，设计一个不可计算的函数，介绍P问题和NP问题，以及公钥密码学。

（10） 第10章计算机系统。沿着一个hello程序的生命周期，介绍计算机系统的组成和相关的概念，包括进程、线程、虚拟存储器、网络通信、高速缓存、层次存储结构等概念。

教学建议

教学章节教学要求课时

(含实验)第1章

机器语言模式熟悉例1.1和例1.2中的程序。

了解存储器、地址、寄存器、程序计数器、程序入口地址、子程序调用指令、断口地址、现场保护、栈、复杂指令集、精简指令集、汇编语言、汇编程序的概念2第2章

C语言模式熟悉程序2.1～程序2.16，以及函数Josephus。

掌握循环结构。

掌握函数调用过程、函数原型、数组和指针的关系、值传递和指针传递、const型指针8续表

教学章节教学要求课时

(含实验)第3章 

顺序表熟悉程序3.1～程序3.4。

熟悉顺序表声明和实现4第4章 

从C到C  了解C语言本身的问题。

理解内联函数、操作符函数、函数重载、引用型、函数模板等C  概念6第5章 

顺序表类熟悉从C顺序表到C  顺序表类的转换过程。

掌握new和delete操作符。

熟悉类模板的概念4第6章

非线性结构与递归熟悉汉诺塔、快速排序和八皇后算法。

掌握递归概念和归纳证明方法4第7章

数据库熟悉程序7.1~程序7.4。

了解关系模型和查询语言SQL的基本语句2第8章 

程序性能了解操作计数、步数、渐进记法等概念4第9章

计算理论   熟悉“可以实现加1操作的图灵机”。

   掌握Bare Bones通用语言。

   了解丘奇·图灵论题、不可计算的函数，P问题和NP问题以及公钥密码学4第10章

计算机系统了解进程、线程、虚拟存储器、网络通信、高速缓存、层次存储结构等概念2总课时40致读者

与本书配套的教材有《C/C  与数据结构（第4版）》（上下册），王立柱主编，清华大学出版社出版。上册内容是C和C  ，下册内容是数据结构，它们是本书在程序设计方面的深入展开，本书把它们逻辑关联起来，帮助读者总体地把握。

读者如有问题，可以直接和作者联系。

第1章机器语言模式

1.1模拟机器指令集与程序设计举例

1.2机器语言的局限性

问题与练习

第2章C语言模式

2.1基于基本类型的编程模式

2.2对操作符的扩充--函数

2.3函数原型和函数定义

2.4代码抽象

2.5对基本类型的扩充--数组和指针

2.5.1数组

2.5.2指针

2.5.3数组和指针的深入讨论

2.5.4选择排序

2.5.5顺序搜索和二分搜索

2.5.6值传递和指针传递

2.5.7const型指针

2.5.8动态数组及其应用

问题与练习47/

第3章顺序表

3.1数组的局限性

3.2结构体

3.3顺序表的声明与实现

3.3.1顺序表声明

3.3.2顺序表的实现

3.4数据抽象和封装

问题与练习63第4章从C到C  

4.1C语言固有局限性

4.2内联函数

4.3操作符重载和函数重载

4.3.1操作符重载

4.3.2函数重载

4.4引用型

4.4.1概念的由来

4.4.2引用型及其应用

4.5函数模板

4.6提取符和插入符

4.7默认参数

问题与练习85第5章顺序表类

5.1从C顺序表到C  顺序表类

5.2变量和对象

5.3new和delete操作符

5.4需要增加的成员函数

5.5顺序表类的声明和实现

5.6类和类模板

5.7基本类型的赋值形式扩展

问题与练习

第6章非线性结构与递归

6.1树形结构与递归

6.2C  递归函数

6.3汉诺塔问题

6.4快速排序

6.5八皇后

问题与练习

第7章数据库

7.1文件的读写操作

7.2数据库的设计实例

7.3关系数据库

问题与练习

第8章程序性能

8.1什么是程序性能

8.2空间复杂度

8.3时间复杂度

8.3.1操作计数

8.3.2好、坏和平均操作计数

8.3.3步数

8.3.4渐进记法

问题与练习

第9章计算理论

9.1函数及其计算

9.2图灵机原理和丘奇·图灵论题

9.3通用程序设计语言--Bare Bones（基本要素）语言

9.4一个不可计算的函数

9.5迭代结构与递归结构的等价性

9.6P问题和NP问题

9.7公钥密码学

9.7.1模表示法

9.7.2RSA公钥密码系统

问题与练习

第10章计算机系统

10.1信息=位 上下文

10.2编译系统

10.3指令的读取和解释

10.3.1系统的硬件组成

10.3.2执行hello程序

10.4操作系统

10.4.1进程

10.4.2线程

10.4.3虚拟存储器

10.4.4文件

10.5网络通信

10.6抽象

10.7高速缓存

10.8存储设备层次结构

问题与练习

参考文献

本书作者王立柱老师是一位非常有想法的老师！

本书目的明确。为程序设计类课程的学习提供先导，为基于程序设计的计算机专业知识的学习做出引领。

本书代码优先。不从概念出发，而从程序设计实例出发。

本书线路清晰。用一个从C到C  的平滑过渡模型把C模式和C  模式连接起来；在非线性算法设计中讲解递归；通过C  语言程序的设计与抽象来了解关系数据库的概念；基于设计实例的剖析来学习程序性能的分析方法；借助语言Bare Bone学习计算理论的基本概念；沿着一个hello程序的生命周期，介绍计算机系统的组成和相关的概念。