面向对象设计与数据结构：USC CSCI104 讲义精华

需积分: 5 137 浏览量更新于2024-06-16 收藏 3.1MB PDF 举报

"USC CSCI104 数据结构和面向对象设计讲义.pdf" 这篇讲义详细介绍了南加州大学CSCI104课程的核心内容，涵盖了数据结构和面向对象设计的基本概念。课程目标是让学生在熟悉C++编程语言的基础上，深入理解数据结构的实现和面向对象设计的方法。首先，讲义提到了学生应具备的基础知识，包括结构化编程、动态内存管理和递归。这些是学习数据结构和面向对象设计的必备技能。对于不熟悉这些概念的学生，课程可能具有一定的挑战性。讲义的内容包括以下几个主要部分： 1. **字符串和流**：这部分简要回顾了字符串的处理和流的概念，这是处理文本数据和输入/输出操作的基础。 2. **内存及其分配**：讲解了变量的作用域、动态内存分配（包括C风格和C++风格）、指针以及如何避免内存泄漏。这部分强调了理解和管理内存的重要性。 3. **递归**：通过计算阶乘、二分查找、N皇后问题等实例，深入浅出地介绍了递归的工作原理和应用。同时，讨论了递归函数的特性及递归定义。 4. **链表**：详细介绍了链表的实现，包括链表操作和递归定义。链表是一种基础但重要的数据结构，它允许动态插入和删除元素。 5. **抽象数据类型**：这是面向对象设计的关键概念，它强调数据和操作的封装。 6. **类和对象**：讲解了如何使用C++的类来创建自定义数据类型，包括头文件和声明、成员函数的实现、构造函数和析构函数的用法，以及this指针的作用。 7. **模板**：介绍了C++的模板机制，使得代码可以泛型化，提高代码的复用性和灵活性。讲义的编写基于2013年秋季学期的课堂笔记，并由多个学生整理和David Kempe扩展。这份资料不仅提供了理论知识，还包含了实践示例，是学习数据结构和面向对象设计的良好资源。尽管它不完全替代专业的数据结构教材，但可以作为理解和掌握这些概念的重要辅助材料。

第3章

内存及其分配

[注意：本章涵盖约1个讲座的内容。]

在物理层面上，计算机内存由大量的触发器组成。每个触发器由几个晶体管组成，能够存储一个位。每

个触发器都可以通过唯一的标识符进行寻址，因此我们可以读取和覆盖它们。因此，从概念上讲，我们可

以将计算机的所有内存视为一个巨大的位数组，我们可以读取和写入。

由于作为人类，我们不太擅长用位来进行思考和算术运算，所以我们将它们分组成更大的组，这些组合

在一起可以用来表示数字。8位被称为1字节；除了字节之外，还有字（有时是16位，有时是32位）。因此

，更常见的是，我们在概念上将计算机的内存视为一个大的（大约2

大小）字节数组。许多东西都存储在

这个内存中。

1. 所有程序使用的变量和其他数据。

2. 还有程序的代码，包括操作系统的代码。

编译器和操作系统一起协同工作，为您处理大部分内存管理工作，

但了解底层发生了什么是很有教益的。

当您编译代码时，编译器可以检查原始数据类型并预先计算它们将需要多少

内存。然后，所需的内存量被分配给程序在堆栈

空间中。例如，考虑以下声明：

int n;

int x[10];

double m;

编译器可以立即看到代码需要 4 + 4 ×10 + 8 = 52 字节

它将插入代码与操作系统交互，请求所需的字节数在堆栈上存储变量。在上面的示例中，编译器知道内

存将如下所示：

它知道每个变量的确切内存地址；实际上，每当我们写入 n时，它在内部被转换为“内存地址 4127963”

之类的东西。

请注意，如果我们在这里尝试访问 x[10]，我们将访问与 m相关联的数据，并可能读取（或覆盖）其中

的一些位。这几乎肯定会对程序的其余部分产生非常不希望的后果。

当函数调用其他函数时，每个函数在被调用时都会获得自己的一块堆栈空间；它在那里保存所有的局部

变量，但也有一个程序计数器，用于记住它在执行中的位置。

1这个空间被称为堆栈空间，因为随着函数的调用，它们的内存被添加到现有内存的顶部。

当它们终止时，它们按照后进先出（LIFO）的顺序被移除。

2这是使用当前整数和双精度浮点数大小的情况。大约20年前，整数通常是2个字节，双精度浮点数是4个字节。

您的代码不应该依赖于基本数据类型的当前大小。

在这里，cout << n << m语句将输出最内层的版本，即值为3和5。通常情况下，当有多个同名变量时，引

用的是包含该变量的最小代码块内的变量。

3.2 动态分配

不幸的是，当我们在编译时不知道一个变量需要多少内存时，事情并不像静态分配的数组那么简单。假设

我们想要做如下操作：

int n;

cin>>n;

// 创建一个包含n个整数的数组a

在编译时，编译器不知道数组需要多少内存。因此，它无法在堆栈上为变量分配空间

。相反，我们的程序

需要在运行时显式地向操作系统请求正确数量的空间。这块内存是从堆空间中分配的

。

静态内存分配和动态内存分配的区别总结在下表中。要完全理解动态内存分配的工作原理，我们需要花

一些时间来学习指针。

静态分配

动态分配

大小必须在编译时知道大小可能在编译时未知

在编译时执行在运行时执行

分配给栈

分配给堆

先进后出没有特定的分配顺序

表3.1：静态分配和动态分配内存的区别。

3.3 指针

指针是指向内存中某个位置的“整数”——具体来说，它是一个字节的地址

。

在C/C++中，通过在常规类型名称后面加上星号‘*’来声明指针类型。因此，int*p; char *q; int **b; v

oid *v;都声明了指针。原则上，所有这些只是某个内存位置的地址，C/C++不关心我们在那里存储什么

。用类型（如int）声明它们主要是为了程序员的利益：它可以防止我们搞乱存储在该位置的数据的使用。

它还影响了对内存位置进行的某些算术运算的方式，我们将在下面解释。

“常规”变量和指针之间常见的两种交互方式如下：

1. 我们想要找出变量在内存中的位置，即获取指向该变量位置的指针。

2. 我们想要将指针指向的位置视为变量，即通过读取或覆盖来访问该位置的数据。

下面的代码片段展示了其中一些情况，以及我们可能遇到的陷阱。

3从技术上讲，这并不完全正确。一些现代编译器允许您定义动态大小的数组，但我们建议不要使用此功能，而是按照我们在这些

笔记中写的方式进行操作。

4这被称为堆空间，因为它可以从尚未分配的任何部分中选择。

虽然堆中的内存保持整齐有序，但堆中的内存往往更加混乱且分散。因此得名。

5这意味着所有指针的大小相同，并且计算机使用的指针大小限制了其可以寻址的内存大小。例如，使用典型的32位指针的计算机

只能使用高达2

字节或4 GB的内存。现代64位架构的转变将其扩大到2

字节，这将足够长一段时间。

int* p, *q; //指向两个整数的指针

int i, j;

i = 5; j = 10;

p = &i; //获取i的地址并将其保存到p中

cout << p; //打印p的值（即i的地址）

cout << *p; //打印p指向的整数的值（即i的值）

*p = j; //将p指向的位置（即i）的值替换为j的值

*q = *p; //将q指向的位置的值替换为p指向的位置的值

q = p; //将指针p替换为q，使它们指向同一个位置

这里有几个值得注意的地方。

1. 最后两个命令都使 *p等于 *q，但方式不同。在第一种情况下，我们将一个位置的值复制到另一个位

置，而在第二种情况下，我们使两个指针都指向同一个位置。

2. 倒数第二个命令非常危险，很可能会导致运行时错误。我们还没有初始化

q，所以它指向一个任意的内存位置，很可能是位置0。我们正在尝试覆盖它，

这很可能是程序不允许的。该位置可能属于操作系统

或其他程序

。

3. NULL是我们用于未初始化的指针变量，或者表示指针没有指向任何地方的特殊指针。. 如果我们在p ==

NULL时尝试写入 *p，会导致运行时错误。从某种意义上说， NULL实际上只是另一种表示0的方式；

我们之前说过指针只是数字，而 NULL指针指向内存位置0。在C++11中，有一个新的关键字用于表示

这一点，即 nullptr。如果你将编译器标志设置为编译C++11，你可以/应该使用 nullptr代替 NULL

。

4. 事实上，早期对未初始化指针的观察表明，每当你有一个指针变量时，你总是在声明时立即将其赋值

为NULL。所以在我们的例子中，我们应该写成int *p = NULL, *q = NULL;这样，如果我们后来忘记在解

引用之前赋值，至少它会导致我们的程序崩溃，而不是可能处理一些从该位置读取的垃圾。这是减少

调试时间的良好编码实践。

5. &和 *是彼此的反函数。. 因此，&*p和*&p与p是相同的。（例外情况是，当应用于p==NULL时，&*p会

引发运行时错误，而不是等于p。）

一般来说，指针很容易出错。一些经验法则（我们在课堂上讨论过）可以排除常见错误，但总的来说，

很容易忘记正确地赋值指针，导致运行时错误。

我们之前讨论过指针基本上就是整数。它们的不同之处在于算术运算有些不同。当你有一个指向整数的

指针 p，并且你写 p+1时，编译器会假设你想要的是下一个整数开始的地址，即比当前地址多4个字节。因

此，通过写 p+1来引用的实际地址实际上是在 p的地址之后4个字节。

这就是指针类型的重要性，正如我们之前提到的。当你有一个 void*时，加法实际上是指添加单个字节

。对于其他所有类型，当你写 p+k，其中 p是指针，k是整数，这引用的是内存位置p+k*size(<type>)，其

中 <type>是指针 p的类型。

3.4 动态内存分配

为了动态分配和释放内存，有两对函数，一对是C风格的，一对是C++风格的。在C中，分配内存的函数是

malloc，释放内存的函数是 free。在C++中，函数是 new和 delete。我们首先讨论C风格，因为它更接

近实际的低级实现；然后我们会看到C++风格，它屏蔽了一些低级细节。

幸运的是，现在，你的程序只会抛出一个运行时错误。过去，操作系统经常允许你进行这样的覆盖操作，这种情况下通常会发生

一些系统崩溃。

剩余205页未读，继续阅读

绝不原创的飞龙

粉丝: 4w+
资源: 1083

面向对象设计与数据结构：USC CSCI104 讲义精华

数据结构考研讲义.pdf

Data Structures and Object Oriented Design Lecture Notes (USC CSCI104)

面向对象设计与数据结构：USC CSCI104讲义

csci572:usc csci 572作业库

JavaBattleShip:USC CSCI201

ThinkTank:USC CSCI 201 最终项目

food-war:USC CSCI526类项目

csci585:USC 的 CSCI585 作业

game_dragonflight:USC CSCI 102 - 2013 年Spring - 最终项目。 我的避障游戏实现

aiichironakano.Github.io：PHYS 516 https：aiichironakano.github.iophys516-CSCI 596 https：aiichironakano.github.iocs596-CSCI 653 https：aiichironakano.github.iocs653-CSCI 699 https：aiichironakano.github.iocs699

最新资源

game_dragonflight:USC CSCI 102 - 2013 年Spring - 最终项目。我的避障游戏实现