有关数据结构和编程技术的注意事项

这是CPSC 223：2021年春季学期的数据结构和编程技术的课程信息。本文档有两种格式，两种格式都应包含相同的信息：

可以从文本中的链接下载代码示例，也可以在examples目录中找到代码示例。

上面的链接指向www.cs.yale.edu。如果本机关闭，则可以在https://www.dropbox.com/sh/omg9qcxkxeiam2o/AACRAJOTj8af6V7RC1cXBHjQa?dl=0上找到这些文件的备份副本。

本文档是一项正在进行中的工作，并且可能会随着学期的进行而经常更改。

James Aspnes版权所有©2001-2021。根据Creative Commons Attribution-ShareAlike 4.0 International许可分发：https：//creativecommons.org/licenses/by-sa/4.0/。

数据结构可视化。该文档比ASCII艺术插图（最好）要好得多。 1个

请随时将有关课程或与课程有关的问题或评论发送至[email protected]。

对于有关个人作业的问题，您可以使用Canvas中的Ed Discussions功能更快地得到答复。请注意，您提出的问题如果没有特别标记为“不公开”，则对其他学生是可见的，因此在广播解决方案草稿时要格外小心。

K＆amp; R指的是Kernighan和Ritchie的书。如果尚未更新以下链接，则可以在2021 / lecture下的examples目录中找到来自演讲的示例。

介绍。课程是关于什么的。 C入门：运行编译器，主要功能，一些简单程序，基本整数数据类型。阅读内容：课程管理，Zoo，Linux编程环境，有关在自己的机器上进行开发的一些知识，C程序的结构，基本整数类型； K＆amp; R §§1.1，1.2。演讲中的例子。

C中的算术运算。读数：整数常量，整数运算符； K＆amp; R §§1.4、2.2、2.3、2.5、2.6、2.8、2.9。演讲示例：算术c。 （注意：我们在讲座中并未真正介绍按位运算符，因此稍后我们将更详细地介绍这些内容。）

局部变量和赋值运算符。使用#define定义常量。浮点值和算术运算。 ++和-运算符。读物：变量； K＆amp; R §1.3、1.4、2.1和2.4。演讲示例：算术c。

陈述和控制流程：如果，要，要，要...要，要和切换。使用getchar，putchar和ungetc的I / O。控制流和逻辑运算符：＆amp;＆amp;，||，！，？：和。阅读：其他操作员，语句，读写单个字符； K＆amp; R §§1.5、2.6、2.12； K＆amp; R第3章。示例：calc.c。讲座后又出现了一些例子。

类似于goto的控制语句：break，continue，goto。功能基础。读物：通过函数声明和模块，具有break，continue和goto函数的循环； K＆amp; R §§3.7、3.8、4.1-4.5。演讲中的例子。应该将factor.c和printFactors.c文件与可用的printFactors.h一起编译；其他.c文件是独立的。

指针和数组的开始：指针类型和指针变量。 ＆amp;和*运算符。使用指针从函数中获取值。数组声明。防止使用const修改数组。读物：指向数组的指针； K＆amp; R 5.1–5.4。演讲中的示例：pointers.c。

字符串：以空字符结尾的字符串的基本概念，char *与const char *，数组声明与指针声明，各种涉及*和++的指针黑客。读物：字符串； K＆amp; R 5.5。演讲中的示例：strings.c。

存储分配：malloc，calloc，free和realloc。使用valgrind查找存储分配错误。读物：使用malloc，Valgrind进行运行时存储分配。

有关指针和数组的更多信息：指针，指针数组，多维数组，C99可变长度数组。读物：K＆amp; R §§5.6–5.9。

结构化数据类型：结构，联合和枚举。将接口与实现分开。读物：结构化数据类型； K＆amp; R第6章，第2.5节（适用于枚举）。

有关该课程的在线信息，包括授课时间表，讲义和有关作业的信息，可以在https://www.cs.yale.edu/homes/aspnes/classes/223/notes.html上找到。该文档在本学期将经常更新，并且也以PDF格式提供。

通过Zoom，讲座为MW 13：00–14：15。演讲记录将通过课程媒体库提供，可以通过Canvas访问。

由于该课程没有必需的同步组件，因此即使您的课程与您正在上的另一个课程重叠，您也可以从教师那里获得全面的授课许可。

讲座时间表可以在课程笔记中找到。日历也是可用的。

主题包括用C语言编程；数据结构（数组，堆栈，队列，列表，树，堆，图）；分类和搜索；存储分配和管理；数据抽象；编程风格；测试和调试；编写高效的程序。

C语言（第二版），作者Brian W. Kernighan和Dennis M. Ritchie。 Prentice Hall，1988年。ISBN0131103628。C的权威介绍。您应该记住这本书。

如果您在耶鲁大学校园内或正在使用VPN来访问耶鲁的网络，则可以在http://proquest.safaribooksonline.com/book/programming/c/9780133086249上访问此书。除非您愿意，否则无需购买本书的实物副本。

每周十二次作业。在计算最终成绩时，作业将被平均加权，并且总计将占总成绩的100％。

您可以使用Ed Discussions网站提出所有员工都会看到的问题。您也可以使用电子邮件地址[email protected]向课程人员发送垃圾邮件。

詹姆斯·阿斯普尼斯（James Aspnes）（james.aspnes @ gmail.com，http：//www.cs.yale.edu/homes/aspnes/）。我的主页上的日历中列出了办公时间。如果我的办公时间对您不起作用，请发送电子邮件进行预约。

学生可以自由讨论彼此的家庭作业问题和课程资料，并可以与教员或助教进行咨询。但是，提交的解决方案应该是学生自己的工作。如果学生从同学或外部来源获得的提示或解决方案中受益匪浅，则该学生应提交他们的解决方案，但要认可外部来源，我们将相应地分配功劳。使用外部资源解决问题是可以接受的，但是窃是不可接受的。

有时，模棱两可和错误可能会渗透到作业中。有关家庭作业解释的问题，请发送电子邮件至[email protected]。说明将出现在作业的在线版本中。

在截止日期之后提交的没有教务长辩解的作业将自动被视为每小时2％的罚款。

本课程有两个目的：教您使用C编程语言进行编程，以及教您如何选择，实现和使用数据结构和标准编程技术。

它实际上是编程语言的不合标准。 C使您几乎可以完全控制系统，甚至可以赤手空拳地推入各个位。

C对编程风格的约束很少：与高级语言不同，C没有太多的意识形态。用C语言编写的程序很少。

人们实际使用的许多编程语言（Visual Basic，perl，python，ruby，PHP等）都是用C（或C ++，对C的扩展）编写的解释器执行的。

如果您在CPSC 223（仅适用于CS专业）中不能很好地学习C，那么您将无法通过CPSC 323。

另一方面，有很多原因使您在以后的生活中可能不想使用C。它缺少现代程序语言的许多功能，包括：

对于大多数问题，最大限度地减少程序员时间和最大化健壮性比最小化运行时间更为重要，其他语言是更好的选择。但是对于此类，我们将使用C。

如果您想大量了解C的优缺点，请访问http://c2.com/cgi/wiki?CeeLanguage。

对于小型程序，您不需要太多的数据结构方式。但是，一旦您表示出相当复杂的数据，就需要在某个地方存储它。考虑如何存储和组织这些数据可能是组织程序其余部分的一个很好的框架。

许多编程环境将为您提供丰富的内置数据结构集合，作为其标准库的一部分。 C不会：除非您使用第三方库，否则您必须在C中构建自己想要的任何数据结构。对于大多数数据结构，这将需要了解指针和存储分配，而这些机制通常隐藏在其他语言中。了解这些概念将使您对计算机的实际工作方式有更深入的了解，并且既可以让您在没有很多支持的简约环境中工作，又可以了解在其抽象障碍下更方便的环境在做什么。

这同样适用于我们将在本课程中讨论的各种编程技术。虽然出现的某些问题特定于C和类似的低级语言（特别是涉及存储的规范管理的问题），但无论您编写哪种程序，都将应用某些技术，并且所有技术都将有助于理解您的计算机。即使某些细节被隐藏，系统仍在执行。

计算机系的主要本科计算机设施是位于AKW三楼的Zoo。 Zoo包含大量Linux工作站。

您无需在Zoo中为该课程做功课，但这是提交和测试作业的地方，因此，如果您在其他地方进行开发，则需要复制文件并确保文件在那里工作也一样

有关动物园的最佳信息，请访问http://zoo.cs.yale.edu/。以下是与CS223学生特别相关的一些要点。

如果您已经注册了该课程，那么您应该已经有一个Zoo帐户。您的登录名是您的NetID。如果这不起作用，则需要通过[email protected]与ITS联系，以找出问题所在。

如果您具有Zoo帐户，但在/ c / cs223 / class下没有目录（需要提交分配），请使用命令sudo register cs223创建此目录。

动物园位于Arthur K Watson Hall的三楼，朝向建筑物的正面。如果您是耶鲁大学的学生，则您的身份证应该可以带您进入建筑物和房间。如果您不是学生，则需要在AKW 008a中验证您的ID，以便下班后进入。

有几种可供远程使用Zoo的选项。最简单的方法是使用ssh，如以下部分所述。这将为您提供一个终端会话，如果您不想做任何花哨的事情，它足以运行您需要执行的任何操作。相关程序scp可用于上载和下载文件。

Unix最好的部分是什么都不会改变。下面的说明仍然有效，并且将为您提供Zoo的终端窗口：

日期：2004年12月13日星期一14:34:19 -0500（美国东部时间）发件人：吉姆·福克纳＆lt; [email protected]>主题：访问ZooHello，我被要求写一个快速的如何访问Zoo中的Linux计算机的指南。对于那些需要此信息的人，请继续阅读。有两种方法可以访问Zoo节点，一种是向上访问并登录到控制台（计算机位于AKW的三楼），另一种是通过以下方式远程连接： SSH。不允许Telnet访问。此处提供了用于各种操作系统的SSH客户端：http：//www.yale.edu/software/Mac OSX默认情况下带有SSH客户端。如果您运行Microsoft Windows，则SSH客户端的不错选择是PuTTY：http：//www.chiark.greenend.org.uk/~sgtatham/putty/除了少数传统帐户外，Zoo会在整个校园范围内使用用于登录访问的NetID和密码。但是，在允许访问之前，您必须注册一个Zooaccount。要注册Zoo帐户，请访问以下网页：http：//zoo.cs.yale.edu/accounts.html然后使用校园范围的NetID和密码登录。您可以选择其他外壳程序，也可以设置您的帐户以注册一个适合您的班级，但是没有必要。只需单击“提交”。一个小时之内，您将创建Zoo帐户，并且您将通过电子邮件收到有关如何访问Zoo的更多信息。用户无法直接登录zoo.cs.yale.edu（中央文件服务器），他们必须登录进入Zoo节点之一。以下是Zoo节点列表：aphid.zoo.cs.yale.edu lion.zoo.cs.yale.edubumblebee.zoo.cs.yale.edu macaw.zoo.cs.yale.educardinal.zoo.cs.yale。 edu猴子.zoo.cs.yale.educhameleon.zoo.cs.yale.edu newt.zoo.cs.yale.educicada.zoo.cs.yale.edu孔雀.zoo.cs.yale.educobra.zoo.cs.yale .edu perch.zoo.cs.yale.educricket.zoo.cs.yale.edu python.zoo.cs.yale.edufrog.zoo.cs.yale.edu rattlesnake.zoo.cs.yale.edugator.zoo.cs。 yale.edu rhino.zoo.cs.yale.edugiraffe.zoo.cs.yale.edu scorpion.zoo.cs.yale.edugrizzly.zoo.cs.yale.edu swan.zoo.cs.yale.eduhare.zoo.cs .yale.edu白蚁.zoo.cs.yale.eduhippo.zoo.cs.yale.edu tick.zoo.cs.yale.eduhornet.zoo.cs.yale.edu tiger.zoo.cs.yale.edujaguar.zoo。 cs.yale.edu tucan.zoo.cs.yale.edukoala.zoo.cs.yale.edu turtle.zoo.cs.yale.eduladybug.zoo.cs.yale.edu viper.zoo.cs.yale.eduleopard.zoo .cs.yale.edu zebra.zoo.cs.yale.edu如果已经创建了帐户，则可以直接SSH到上述计算机之一，并使用校园范围的NetID和密码登录。您也可以SSH到node.zoo.cs.yale.edu，它将连接到随机的Zoo节点。如果对Zoo有任何疑问，请随时与我联系。谢谢，Jim FaulknerZoo系统管理员

如果出于某种原因您真的想在自己的远程计算机上复制完整的Zoo体验，则可以尝试运行X服务器并转发连接。

-如果您使用的是Linux，则您可能已经在运行X服务器。-对于OSX，您可能需要安装[XQuartz]（https://xquarz.org/）。-对于Windows，某些选项是[XMing] （http://www.straightrunning.com/XmingNotes/）或XWin-32，可通过Yale软件库获得。

第二步是使用ssh转发X连接。在Linux，OSX或WSL终端窗口中键入“ ssh -X [email protected]”应转发X连接，从而允许您从Zoo上的命令行运行X客户端并拥有Windows显示在您的本地计算机上。但是我本人仅取得了有限的成功，因此没有希望。

因为C是高度可移植的，所以您很有可能可以在自己的计算机上开发分配解决方案，然后仅将其上传到Zoo进行最终测试和提交。因为那里有许多不同种类的机器，所以我只能提供有关如何执行此操作的非常一般的建议。 2个

您将需要一个文本编辑器。我喜欢Vim，它几乎可以在任何东西上运行，但是您应该使用任何自己喜欢的东西。

您还需要一个可以处理C99的C编译器。理想情况下，您将拥有一个看起来像Linux的环境，您也可以运行其他命令行工具，例如gdb，make以及git。如何获得此功能取决于您的基础操作系统。

几乎所有Linux发行版都可以立即提供此功能。您可能需要运行软件包管理器来安装缺少的实用程序，例如gcc C编译器。

OSX不是Linux，但实际上是Unix。您将需要一个终端仿真器（内置的Terminal程序可以运行，但是我喜欢iTerm2。您还需要设置XCode以获得命令行开发人员工具。执行此操作的方法似乎取决于XCode的版本你有。

您可能最终以c99指向clang而不是gcc。您最有可能看到的唯一区别是错误消息的详细信息。记得在Zoo上用gcc进行测试。

可以使用Homebrew安装其他软件包。如果您是Mac人士，那么您可能已经比我更了解这一点。

对于Windows 10，您可以安装Windows Subsystem for Linux。这使您能够在控制台窗口中输入bash并获得完整的Linux安装。您将需要选择Linux发行版：如果您没有偏好，建议您使用Ubuntu。您将需要使用apt程序来安装gcc之类的东西。如果您使用的是Ubuntu，则在键入无法识别的命令时会建议安装哪些软件包。

您还可以从Windows运行ubuntu.exe，以获得比默认控制台窗口更好的终端模拟器。 对于其他版本的Windows，您可以安装虚拟化程序（如VirtualBox或VMware）并在其中运行Linux。 您也许还可以使用Cygwin在Windows中进行本机开发，但这可能比其他选项难，并且在将代码移至Linux时可能会产生令人惊讶的可移植性问题。 有关特定命令的详细信息，请参见有关如何使用Zoo的章节。 基本步骤是 使用您选择的文本编辑器创建程序。 （对于长程序，我喜欢vim；对于很短的程序，我喜欢cat。） 如果这些步骤中的任何一个失败，则下一步是调试。 我们将在其他地方讨论调试。 使用您喜欢的文本编辑器。 程序文件的名称应为foo.c形式； 最后的.c告诉C编译器内容是C源代码。 这是一个典型的C程序：

第一行是用于编译程序的命令。美元符号是我的提示，系统会打印出来，告诉我它正在等待命令。该命令使用参数-g3（启用最大调试信息），-o（指定可执行文件名，否则默认为a.out），count（实际的可执行文件名）和count.c（源文件）将ccc调用为c99。编译）。这告诉gcc我们应该编译count.c以在C99模式下进行计数，并在可执行文件中包含最大的调试信息。

第二行运行输出文件计数。调用./count是必需的，因为默认情况下，shell（解释您键入内容的程序）仅在某些标准系统目录中查找程序。为了使它在当前目录中运行程序，我们必须包括目录名称。

＃include＆lt; stdio.h＆gt;在第1行中。这是标准的C样板，将出现在您看到的进行输入或输出的任何程序中。意思是告诉编译器在您的程序中包含文件/usr/include/stdio.h的文本，就好像您自己在其中键入了该文本一样。该特定文件包含程序中使用的标准I / O库函数的声明，例如puts（放置字符串）和printf（打印格式）。如果您不将其放入，则您的程序可能会也可能不会编译。还是做吧。

第3行是注释；它的开始和结束由/ *和* /字符标记。注释会被编译器忽略，但对于其他查看您代码的程序员（包括您自己，忘记了编写内容的原因）可能会有所帮助。

第5和6行声明了main函数。每个C程序都必须具有完全以此方式声明的main函数-这是操作系统在执行该程序时所调用的函数。第3行上的int表示main返回的是int类型的值（我们将在函数章节中对此进行详细说明），并且它接受两个参数：int类型的argc，传递给int类型的参数数目。命令行中的程序和argv，我们最终会得到一个指针类型，它是参数的数组（基本上是命令行中的所有单词，包括

......