{"payload":{"allShortcutsEnabled":false,"fileTree":{"":{"items":[{"name":"img","path":"img","contentType":"directory"},{"name":"styles","path":"styles","contentType":"directory"},{"name":".gitignore","path":".gitignore","contentType":"file"},{"name":"README.md","path":"README.md","contentType":"file"},{"name":"SUMMARY.md","path":"SUMMARY.md","contentType":"file"},{"name":"cover.jpg","path":"cover.jpg","contentType":"file"},{"name":"donors.md","path":"donors.md","contentType":"file"},{"name":"ex0.md","path":"ex0.md","contentType":"file"},{"name":"ex1.md","path":"ex1.md","contentType":"file"},{"name":"ex10.md","path":"ex10.md","contentType":"file"},{"name":"ex11.md","path":"ex11.md","contentType":"file"},{"name":"ex12.md","path":"ex12.md","contentType":"file"},{"name":"ex13.md","path":"ex13.md","contentType":"file"},{"name":"ex14.md","path":"ex14.md","contentType":"file"},{"name":"ex15.md","path":"ex15.md","contentType":"file"},{"name":"ex16.md","path":"ex16.md","contentType":"file"},{"name":"ex17.md","path":"ex17.md","contentType":"file"},{"name":"ex18.md","path":"ex18.md","contentType":"file"},{"name":"ex19.md","path":"ex19.md","contentType":"file"},{"name":"ex2.md","path":"ex2.md","contentType":"file"},{"name":"ex20.md","path":"ex20.md","contentType":"file"},{"name":"ex21.md","path":"ex21.md","contentType":"file"},{"name":"ex22.md","path":"ex22.md","contentType":"file"},{"name":"ex23.md","path":"ex23.md","contentType":"file"},{"name":"ex24.md","path":"ex24.md","contentType":"file"},{"name":"ex25.md","path":"ex25.md","contentType":"file"},{"name":"ex26.md","path":"ex26.md","contentType":"file"},{"name":"ex27.md","path":"ex27.md","contentType":"file"},{"name":"ex28.md","path":"ex28.md","contentType":"file"},{"name":"ex29.md","path":"ex29.md","contentType":"file"},{"name":"ex3.md","path":"ex3.md","contentType":"file"},{"name":"ex30.md","path":"ex30.md","contentType":"file"},{"name":"ex31.md","path":"ex31.md","contentType":"file"},{"name":"ex32.md","path":"ex32.md","contentType":"file"},{"name":"ex33.md","path":"ex33.md","contentType":"file"},{"name":"ex34.md","path":"ex34.md","contentType":"file"},{"name":"ex35.md","path":"ex35.md","contentType":"file"},{"name":"ex36.md","path":"ex36.md","contentType":"file"},{"name":"ex37.md","path":"ex37.md","contentType":"file"},{"name":"ex38.md","path":"ex38.md","contentType":"file"},{"name":"ex39.md","path":"ex39.md","contentType":"file"},{"name":"ex4.md","path":"ex4.md","contentType":"file"},{"name":"ex40.md","path":"ex40.md","contentType":"file"},{"name":"ex41.md","path":"ex41.md","contentType":"file"},{"name":"ex42.md","path":"ex42.md","contentType":"file"},{"name":"ex43.md","path":"ex43.md","contentType":"file"},{"name":"ex44.md","path":"ex44.md","contentType":"file"},{"name":"ex45.md","path":"ex45.md","contentType":"file"},{"name":"ex46.md","path":"ex46.md","contentType":"file"},{"name":"ex47.md","path":"ex47.md","contentType":"file"},{"name":"ex5.md","path":"ex5.md","contentType":"file"},{"name":"ex6.md","path":"ex6.md","contentType":"file"},{"name":"ex7.md","path":"ex7.md","contentType":"file"},{"name":"ex8.md","path":"ex8.md","contentType":"file"},{"name":"ex9.md","path":"ex9.md","contentType":"file"},{"name":"introduction.md","path":"introduction.md","contentType":"file"},{"name":"postscript.md","path":"postscript.md","contentType":"file"},{"name":"preface.md","path":"preface.md","contentType":"file"}],"totalCount":58}},"fileTreeProcessingTime":14.36974,"foldersToFetch":[],"incompleteFileTree":false,"repo":{"id":159600678,"defaultBranch":"master","name":"lcthw-zh","ownerLogin":"hiekay","currentUserCanPush":false,"isFork":true,"isEmpty":false,"createdAt":"2018-11-29T03:16:13.000Z","ownerAvatar":"https://avatars.githubusercontent.com/u/12382924?v=4","public":true,"private":false,"isOrgOwned":false},"codeLineWrapEnabled":false,"symbolsExpanded":false,"treeExpanded":true,"refInfo":{"name":"master","listCacheKey":"v0:1620202359.313178","canEdit":false,"refType":"branch","currentOid":"331debee3bcd69a1a79cdc99ad5f476d991acfd2"},"path":"ex32.md","currentUser":null,"blob":{"rawLines":null,"stylingDirectives":null,"colorizedLines":null,"csv":null,"csvError":null,"dependabotInfo":{"showConfigurationBanner":false,"configFilePath":null,"networkDependabotPath":"/hiekay/lcthw-zh/network/updates","dismissConfigurationNoticePath":"/settings/dismiss-notice/dependabot_configuration_notice","configurationNoticeDismissed":null},"displayName":"ex32.md","displayUrl":"https://github.com/hiekay/lcthw-zh/blob/master/ex32.md?raw=true","headerInfo":{"blobSize":"15.4 KB","deleteTooltip":"You must be signed in to make or propose changes","editTooltip":"You must be signed in to make or propose changes","ghDesktopPath":"https://desktop.github.com","isGitLfs":false,"onBranch":true,"shortPath":"b41cc5a","siteNavLoginPath":"/login?return_to=https%3A%2F%2Fgithub.com%2Fhiekay%2Flcthw-zh%2Fblob%2Fmaster%2Fex32.md","isCSV":false,"isRichtext":true,"toc":[{"level":1,"text":"练习32：双向链表","anchor":"练习32双向链表","htmlText":"练习32：双向链表"},{"level":2,"text":"数据结构是什么。","anchor":"数据结构是什么","htmlText":"数据结构是什么。"},{"level":2,"text":"构建库","anchor":"构建库","htmlText":"构建库"},{"level":2,"text":"双向链表","anchor":"双向链表","htmlText":"双向链表"},{"level":3,"text":"定义","anchor":"定义","htmlText":"定义"},{"level":3,"text":"实现","anchor":"实现","htmlText":"实现"},{"level":2,"text":"测试","anchor":"测试","htmlText":"测试"},{"level":2,"text":"你会看到什么","anchor":"你会看到什么","htmlText":"你会看到什么"},{"level":2,"text":"如何改进","anchor":"如何改进","htmlText":"如何改进"},{"level":2,"text":"附加题","anchor":"附加题","htmlText":"附加题"}],"lineInfo":{"truncatedLoc":"485","truncatedSloc":"341"},"mode":"file"},"image":false,"isCodeownersFile":null,"isPlain":false,"isValidLegacyIssueTemplate":false,"issueTemplate":null,"discussionTemplate":null,"language":"Markdown","languageID":222,"large":false,"planSupportInfo":{"repoIsFork":null,"repoOwnedByCurrentUser":null,"requestFullPath":"/hiekay/lcthw-zh/blob/master/ex32.md","showFreeOrgGatedFeatureMessage":null,"showPlanSupportBanner":null,"upgradeDataAttributes":null,"upgradePath":null},"publishBannersInfo":{"dismissActionNoticePath":"/settings/dismiss-notice/publish_action_from_dockerfile","releasePath":"/hiekay/lcthw-zh/releases/new?marketplace=true","showPublishActionBanner":false},"rawBlobUrl":"https://github.com/hiekay/lcthw-zh/raw/refs/heads/master/ex32.md","renderImageOrRaw":false,"richText":"\u003carticle class=\"markdown-body entry-content container-lg\" itemprop=\"text\"\u003e\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch1 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e练习32：双向链表\u003c/h1\u003e\u003ca id=\"user-content-练习32双向链表\" class=\"anchor\" aria-label=\"Permalink: 练习32：双向链表\" href=\"#练习32双向链表\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e原文：\u003ca href=\"http://c.learncodethehardway.org/book/ex32.html\" rel=\"nofollow\"\u003eExercise 32: Double Linked Lists\u003c/a\u003e\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cblockquote\u003e\n\u003cp dir=\"auto\"\u003e译者：\u003ca href=\"https://github.com/wizardforcel\"\u003e飞龙\u003c/a\u003e\u003c/p\u003e\n\u003c/blockquote\u003e\n\u003cp dir=\"auto\"\u003e这本书的目的是教给你计算机实际上如何工作，这也包括多种数据结构和算法函数。计算机自己其实并没有太大用处。为了让它们做一些有用的事情，你需要构建数据，之后在这些结构上组织处理。其它编程语言带有实现所有这些结构的库，或者带有直接的语法来创建它们。C需要你手动实现所有数据结构，这使它成为最“完美”的语言，让你知道它们的工作原理。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e我的目标是交给你这些数据结构，以及相关算法的知识，来帮助你完成下面这三件事：\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e理解Python、Ruby或JavaScript的\u003ccode\u003edata = {\"name\": \"Zed\"}\u003c/code\u003e到底做了什么。\u003c/li\u003e\n\u003cli\u003e使用数据结构来解决问题，使你成为更好的C程序员。\u003c/li\u003e\n\u003cli\u003e学习数据结构和算法的核心部分，让你知道在特定条件下哪个最好。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e数据结构是什么。\u003c/h2\u003e\u003ca id=\"user-content-数据结构是什么\" class=\"anchor\" aria-label=\"Permalink: 数据结构是什么。\" href=\"#数据结构是什么\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e“数据结构”这个名称自己就能够解释。它是具有特性模型的数据组织方法。这一模型可能设计用于以新的方法处理数据，也可能只是用于将它们更高效地储存在磁盘上。这本书中我会遵循一些简单的模式来构建可用的数据结构：\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e定义一个结构的主要“外部结构”。\u003c/li\u003e\n\u003cli\u003e定义一个结构的内容，通常是带有链接的节点。\u003c/li\u003e\n\u003cli\u003e创建函数操作它们的函数。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003eC中还有其它样式的数据结构，但是这个模式效果很好，并且对于你创建的大部分数据结构都适用。\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e构建库\u003c/h2\u003e\u003ca id=\"user-content-构建库\" class=\"anchor\" aria-label=\"Permalink: 构建库\" href=\"#构建库\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e对于这本书的剩余部分，当你完成这本书之后，你将会创建一个可用的库。这个库会包含下列元素：\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e为每个数据结构编写的头文件\u003ccode\u003e.h\u003c/code\u003e。\u003c/li\u003e\n\u003cli\u003e为算法编写的实现文件\u003ccode\u003e.c\u003c/code\u003e。\u003c/li\u003e\n\u003cli\u003e用于测试它们确保有效的单元测试。\u003c/li\u003e\n\u003cli\u003e从头文件自动生成的文档。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e你已经实现了\u003ccode\u003ec-skeleton\u003c/code\u003e（项目框架目录），使用它来创建一个\u003ccode\u003eliblcthw\u003c/code\u003e项目：\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-shell notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"$ cp -r c-skeleton liblcthw\n$ cd liblcthw/\n$ ls\nLICENSE Makefile README.md bin build src tests\n$ vim Makefile\n$ ls src/\ndbg.h libex29.c libex29.o\n$ mkdir src/lcthw\n$ mv src/dbg.h src/lcthw\n$ vim tests/minunit.h\n$ rm src/libex29.* tests/libex29*\n$ make clean\nrm -rf build tests/libex29_tests\nrm -f tests/tests.log\nfind . -name \u0026quot;*.gc*\u0026quot; -exec rm {} \\;\nrm -rf `find . -name \u0026quot;*.dSYM\u0026quot; -print`\n$ ls tests/\nminunit.h runtests.sh\n$\"\u003e\u003cpre\u003e$ cp -r c-skeleton liblcthw\n$ \u003cspan class=\"pl-c1\"\u003ecd\u003c/span\u003e liblcthw/\n$ ls\nLICENSE Makefile README.md bin build src tests\n$ vim Makefile\n$ ls src/\ndbg.h libex29.c libex29.o\n$ mkdir src/lcthw\n$ mv src/dbg.h src/lcthw\n$ vim tests/minunit.h\n$ rm src/libex29.\u003cspan class=\"pl-k\"\u003e*\u003c/span\u003e tests/libex29\u003cspan class=\"pl-k\"\u003e*\u003c/span\u003e\n$ make clean\nrm -rf build tests/libex29_tests\nrm -f tests/tests.log\nfind \u003cspan class=\"pl-c1\"\u003e.\u003c/span\u003e -name \u003cspan class=\"pl-s\"\u003e\u003cspan class=\"pl-pds\"\u003e\"\u003c/span\u003e*.gc*\u003cspan class=\"pl-pds\"\u003e\"\u003c/span\u003e\u003c/span\u003e -exec rm {} \u003cspan class=\"pl-cce\"\u003e\\;\u003c/span\u003e\nrm -rf \u003cspan class=\"pl-s\"\u003e\u003cspan class=\"pl-pds\"\u003e`\u003c/span\u003efind \u003cspan class=\"pl-c1\"\u003e.\u003c/span\u003e -name \u003cspan class=\"pl-s\"\u003e\u003cspan class=\"pl-pds\"\u003e\"\u003c/span\u003e*.dSYM\u003cspan class=\"pl-pds\"\u003e\"\u003c/span\u003e\u003c/span\u003e -print\u003cspan class=\"pl-pds\"\u003e`\u003c/span\u003e\u003c/span\u003e\n$ ls tests/\nminunit.h runtests.sh\n$\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e这个会话中我执行了下列事情：\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e复制了\u003ccode\u003ec-skeleton\u003c/code\u003e。\u003c/li\u003e\n\u003cli\u003e编辑Makefile，将\u003ccode\u003elibYOUR_LIBRARY.a\u003c/code\u003e改为\u003ccode\u003eliblcthw.a\u003c/code\u003e作为新的\u003ccode\u003eTARGET\u003c/code\u003e。\u003c/li\u003e\n\u003cli\u003e创建\u003ccode\u003esrc/lcthw\u003c/code\u003e目录，我们会在里面放入代码。\u003c/li\u003e\n\u003cli\u003e移动\u003ccode\u003esrc/dbg.h\u003c/code\u003e文件到新的目录中。\u003c/li\u003e\n\u003cli\u003e编辑\u003ccode\u003e tests/minunit.h\u003c/code\u003e，使它使用所包含的\u003ccode\u003e#include \u0026lt;lcthw/dbg.h\u0026gt;\u003c/code\u003e。\u003c/li\u003e\n\u003cli\u003e移除\u003ccode\u003elibex29.*\u003c/code\u003e中我们不需要的源文件和测试文件。\u003c/li\u003e\n\u003cli\u003e清理所有遗留的东西。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e执行完之后你就准备好开始构建库了，我打算构建第一个数据结构是双向链表。\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e双向链表\u003c/h2\u003e\u003ca id=\"user-content-双向链表\" class=\"anchor\" aria-label=\"Permalink: 双向链表\" href=\"#双向链表\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e我们将要向\u003ccode\u003eliblcthw\u003c/code\u003e添加的第一个数据结构是双向链表。这是你能够构建的最简单的数据结构，并且它拥有针对特定操作的实用属性。单向链表通过指向下一个或上一个元素的节点来工作。“双向”链表持有全部这两个指针，而“单向”链表只持有下一个元素的指针。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e由于每个节点都有下一个和上一个元素的指针，并且你可以跟踪联保的第一个和最后的元素，你就可以快速地执行一些操作。任何涉及到插入和删除元素的操作会非常快。它对大多数人来说也易于实现。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e链表的主要缺点是，遍历它涉及到处理沿途每个单个的指针。这意味着搜索、多数排序以及迭代元素会表较慢。这也意味着你不能直接跳过链表的随机一部分。如果换成数组，你就可以直接索引到它的中央，但是链表不行。也就是说如果你想要访问第十个元素，你必须经过1~9。\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e定义\u003c/h3\u003e\u003ca id=\"user-content-定义\" class=\"anchor\" aria-label=\"Permalink: 定义\" href=\"#定义\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e正如在这个练习的介绍部分所说，整个过程的第一步，是编程一个头文件，带有正确的C结构定义。\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-c notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"#ifndef lcthw_List_h\n#define lcthw_List_h\n\n#include \u0026lt;stdlib.h\u0026gt;\n\nstruct ListNode;\n\ntypedef struct ListNode {\n struct ListNode *next;\n struct ListNode *prev;\n void *value;\n} ListNode;\n\ntypedef struct List {\n int count;\n ListNode *first;\n ListNode *last;\n} List;\n\nList *List_create();\nvoid List_destroy(List *list);\nvoid List_clear(List *list);\nvoid List_clear_destroy(List *list);\n\n#define List_count(A) ((A)-\u0026gt;count)\n#define List_first(A) ((A)-\u0026gt;first != NULL ? (A)-\u0026gt;first-\u0026gt;value : NULL)\n#define List_last(A) ((A)-\u0026gt;last != NULL ? (A)-\u0026gt;last-\u0026gt;value : NULL)\n\nvoid List_push(List *list, void *value);\nvoid *List_pop(List *list);\n\nvoid List_unshift(List *list, void *value);\nvoid *List_shift(List *list);\n\nvoid *List_remove(List *list, ListNode *node);\n\n#define LIST_FOREACH(L, S, M, V) ListNode *_node = NULL;\\\n ListNode *V = NULL;\\\n for(V = _node = L-\u0026gt;S; _node != NULL; V = _node = _node-\u0026gt;M)\n\n#endif\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003e#ifndef\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elcthw_List_h\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003e#define\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elcthw_List_h\u003c/span\u003e\n\n\u003cspan class=\"pl-k\"\u003e#include\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\u0026lt;stdlib.h\u0026gt;\u003c/span\u003e\n\n\u003cspan class=\"pl-k\"\u003estruct\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e;\n\n\u003cspan class=\"pl-k\"\u003etypedef\u003c/span\u003e \u003cspan class=\"pl-k\"\u003estruct\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e {\n \u003cspan class=\"pl-k\"\u003estruct\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003enext\u003c/span\u003e;\n \u003cspan class=\"pl-k\"\u003estruct\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003eprev\u003c/span\u003e;\n \u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003evalue\u003c/span\u003e;\n} \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e;\n\n\u003cspan class=\"pl-k\"\u003etypedef\u003c/span\u003e \u003cspan class=\"pl-k\"\u003estruct\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e {\n \u003cspan class=\"pl-smi\"\u003eint\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003ecount\u003c/span\u003e;\n \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e;\n \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e;\n} \u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e;\n\n\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eList_create\u003c/span\u003e();\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_destroy\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_clear\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_clear_destroy\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n\n\u003cspan class=\"pl-k\"\u003e#define\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_count\u003c/span\u003e(\u003cspan class=\"pl-c1\"\u003eA\u003c/span\u003e) ((A)-\u0026gt;count)\n\u003cspan class=\"pl-k\"\u003e#define\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_first\u003c/span\u003e(\u003cspan class=\"pl-c1\"\u003eA\u003c/span\u003e) ((A)-\u0026gt;first != NULL ? (A)-\u0026gt;first-\u0026gt;value : NULL)\n\u003cspan class=\"pl-k\"\u003e#define\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_last\u003c/span\u003e(\u003cspan class=\"pl-c1\"\u003eA\u003c/span\u003e) ((A)-\u0026gt;last != NULL ? (A)-\u0026gt;last-\u0026gt;value : NULL)\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_push\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003evalue\u003c/span\u003e);\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eList_pop\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_unshift\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003evalue\u003c/span\u003e);\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eList_shift\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eList_remove\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e);\n\n\u003cspan class=\"pl-k\"\u003e#define\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eLIST_FOREACH\u003c/span\u003e(\u003cspan class=\"pl-c1\"\u003eL\u003c/span\u003e, \u003cspan class=\"pl-c1\"\u003eS\u003c/span\u003e, \u003cspan class=\"pl-c1\"\u003eM\u003c/span\u003e, \u003cspan class=\"pl-c1\"\u003eV\u003c/span\u003e) ListNode *_node = NULL;\\\n ListNode *V = NULL;\\\n for(V = _node = L-\u0026gt;S; _node != NULL; V = _node = _node-\u0026gt;M)\n\n\u003cspan class=\"pl-k\"\u003e#endif\u003c/span\u003e\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e我所做的第一件事就是创建两个结构，\u003ccode\u003eListNode\u003c/code\u003e和包含这些节点的\u003ccode\u003eList\u003c/code\u003e。这创建了是将在函数中使用的数据结构，以及随后定义的宏。如果你浏览这些函数，它们看起来非常简单。当我讲到实现时，我会解释他们，但我更希望你能猜出它们的作用。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e这些数据结构的工作方式，就是每个\u003ccode\u003eListNode\u003c/code\u003e都有三个成员。\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e值，它是无类型的指针，存储我们想在链表中放置的东西。\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eListNode *next\u003c/code\u003e指针，它指向另一个储存下一个元素的\u003ccode\u003eListNode \u003c/code\u003e。\u003c/li\u003e\n\u003cli\u003e\u003ccode\u003eListNode *prev\u003c/code\u003e指针，它指向另一个储存上一个元素的\u003ccode\u003eListNode \u003c/code\u003e。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e\u003ccode\u003eList\u003c/code\u003e结构只是这些\u003ccode\u003eListNode\u003c/code\u003e结构的容器，它们互联链接组成链型。它跟踪链表的\u003ccode\u003ecount\u003c/code\u003e，\u003ccode\u003efirst\u003c/code\u003e和\u003ccode\u003elast\u003c/code\u003e元素。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e最后，看一看\u003ccode\u003esrc/lcthw/list.h:37\u003c/code\u003e，其中我定义了\u003ccode\u003eLIST_FOREACH\u003c/code\u003e宏。这是个常见的习语，你可以创建一个宏来生成迭代代码，使用者就不会弄乱了。正确使用这类执行过程来处理数据结构十分困难，所以可以编写宏来帮助使用者。当我讲到实现时，你可以看到我如何使用它。\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch3 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e实现\u003c/h3\u003e\u003ca id=\"user-content-实现\" class=\"anchor\" aria-label=\"Permalink: 实现\" href=\"#实现\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e一旦你理解了它们之后，你很可能理解了双向链表如何工作。它只是带有两个指针的节点，指向链表中前一个和后一个元素。接下来你可以编写\u003ccode\u003esrc/lcthw/list.c\u003c/code\u003e中的代码，来理解每个操作如何实现。\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-c notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"#include \u0026lt;lcthw/list.h\u0026gt;\n#include \u0026lt;lcthw/dbg.h\u0026gt;\n\nList *List_create()\n{\n return calloc(1, sizeof(List));\n}\n\nvoid List_destroy(List *list)\n{\n LIST_FOREACH(list, first, next, cur) {\n if(cur-\u0026gt;prev) {\n free(cur-\u0026gt;prev);\n }\n }\n\n free(list-\u0026gt;last);\n free(list);\n}\n\n\nvoid List_clear(List *list)\n{\n LIST_FOREACH(list, first, next, cur) {\n free(cur-\u0026gt;value);\n }\n}\n\n\nvoid List_clear_destroy(List *list)\n{\n List_clear(list);\n List_destroy(list);\n}\n\n\nvoid List_push(List *list, void *value)\n{\n ListNode *node = calloc(1, sizeof(ListNode));\n check_mem(node);\n\n node-\u0026gt;value = value;\n\n if(list-\u0026gt;last == NULL) {\n list-\u0026gt;first = node;\n list-\u0026gt;last = node;\n } else {\n list-\u0026gt;last-\u0026gt;next = node;\n node-\u0026gt;prev = list-\u0026gt;last;\n list-\u0026gt;last = node;\n }\n\n list-\u0026gt;count++;\n\nerror:\n return;\n}\n\nvoid *List_pop(List *list)\n{\n ListNode *node = list-\u0026gt;last;\n return node != NULL ? List_remove(list, node) : NULL;\n}\n\nvoid List_unshift(List *list, void *value)\n{\n ListNode *node = calloc(1, sizeof(ListNode));\n check_mem(node);\n\n node-\u0026gt;value = value;\n\n if(list-\u0026gt;first == NULL) {\n list-\u0026gt;first = node;\n list-\u0026gt;last = node;\n } else {\n node-\u0026gt;next = list-\u0026gt;first;\n list-\u0026gt;first-\u0026gt;prev = node;\n list-\u0026gt;first = node;\n }\n\n list-\u0026gt;count++;\n\nerror:\n return;\n}\n\nvoid *List_shift(List *list)\n{\n ListNode *node = list-\u0026gt;first;\n return node != NULL ? List_remove(list, node) : NULL;\n}\n\nvoid *List_remove(List *list, ListNode *node)\n{\n void *result = NULL;\n\n check(list-\u0026gt;first \u0026amp;\u0026amp; list-\u0026gt;last, \u0026quot;List is empty.\u0026quot;);\n check(node, \u0026quot;node can't be NULL\u0026quot;);\n\n if(node == list-\u0026gt;first \u0026amp;\u0026amp; node == list-\u0026gt;last) {\n list-\u0026gt;first = NULL;\n list-\u0026gt;last = NULL;\n } else if(node == list-\u0026gt;first) {\n list-\u0026gt;first = node-\u0026gt;next;\n check(list-\u0026gt;first != NULL, \u0026quot;Invalid list, some
8000
how got a first that is NULL.\u0026quot;);\n list-\u0026gt;first-\u0026gt;prev = NULL;\n } else if (node == list-\u0026gt;last) {\n list-\u0026gt;last = node-\u0026gt;prev;\n check(list-\u0026gt;last != NULL, \u0026quot;Invalid list, somehow got a next that is NULL.\u0026quot;);\n list-\u0026gt;last-\u0026gt;next = NULL;\n } else {\n ListNode *after = node-\u0026gt;next;\n ListNode *before = node-\u0026gt;prev;\n after-\u0026gt;prev = before;\n before-\u0026gt;next = after;\n }\n\n list-\u0026gt;count--;\n result = node-\u0026gt;value;\n free(node);\n\nerror:\n return result;\n}\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003e#include\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\u0026lt;lcthw/list.h\u0026gt;\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003e#include\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\u0026lt;lcthw/dbg.h\u0026gt;\u003c/span\u003e\n\n\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eList_create\u003c/span\u003e()\n{\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ecalloc\u003c/span\u003e(\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e, \u003cspan class=\"pl-k\"\u003esizeof\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eList\u003c/span\u003e));\n}\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_destroy\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e)\n{\n \u003cspan class=\"pl-en\"\u003eLIST_FOREACH\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003efirst\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003enext\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003ecur\u003c/span\u003e) {\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003ecur\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003eprev\u003c/span\u003e) {\n \u003cspan class=\"pl-en\"\u003efree\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003ecur\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003eprev\u003c/span\u003e);\n }\n }\n\n \u003cspan class=\"pl-en\"\u003efree\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003efree\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n}\n\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_clear\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e)\n{\n \u003cspan class=\"pl-en\"\u003eLIST_FOREACH\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003efirst\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003enext\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003ecur\u003c/span\u003e) {\n \u003cspan class=\"pl-en\"\u003efree\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003ecur\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003evalue\u003c/span\u003e);\n }\n}\n\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_clear_destroy\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e)\n{\n \u003cspan class=\"pl-en\"\u003eList_clear\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003eList_destroy\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n}\n\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_push\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003evalue\u003c/span\u003e)\n{\n \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ecalloc\u003c/span\u003e(\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e, \u003cspan class=\"pl-k\"\u003esizeof\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eListNode\u003c/span\u003e));\n \u003cspan class=\"pl-en\"\u003echeck_mem\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e);\n\n \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003evalue\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003evalue\u003c/span\u003e;\n\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e) {\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e;\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003enext\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003eprev\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e;\n }\n\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003ecount\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e++\u003c/span\u003e;\n\n\u003cspan class=\"pl-ent\"\u003eerror\u003c/span\u003e:\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e;\n}\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eList_pop\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e)\n{\n \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e;\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e ? \u003cspan class=\"pl-en\"\u003eList_remove\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e) : \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n}\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_unshift\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003evalue\u003c/span\u003e)\n{\n \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003ecalloc\u003c/span\u003e(\u003cspan class=\"pl-c1\"\u003e1\u003c/span\u003e, \u003cspan class=\"pl-k\"\u003esizeof\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eListNode\u003c/span\u003e));\n \u003cspan class=\"pl-en\"\u003echeck_mem\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e);\n\n \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003evalue\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003evalue\u003c/span\u003e;\n\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e) {\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e;\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003enext\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003eprev\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e;\n }\n\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003ecount\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e++\u003c/span\u003e;\n\n\u003cspan class=\"pl-ent\"\u003eerror\u003c/span\u003e:\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e;\n}\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eList_shift\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e)\n{\n \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e;\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e ? \u003cspan class=\"pl-en\"\u003eList_remove\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e) : \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n}\n\n\u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eList_remove\u003c/span\u003e(\u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e)\n{\n \u003cspan class=\"pl-smi\"\u003evoid\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n\n \u003cspan class=\"pl-en\"\u003echeck\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"List is empty.\"\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003echeck\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"node can't be NULL\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e\u0026amp;\u0026amp;\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e) {\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e) {\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003enext\u003c/span\u003e;\n \u003cspan class=\"pl-en\"\u003echeck\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Invalid list, somehow got a first that is NULL.\"\u003c/span\u003e);\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003eprev\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e \u003cspan class=\"pl-k\"\u003eif\u003c/span\u003e (\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e) {\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003eprev\u003c/span\u003e;\n \u003cspan class=\"pl-en\"\u003echeck\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Invalid list, somehow got a next that is NULL.\"\u003c/span\u003e);\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003elast\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003enext\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n } \u003cspan class=\"pl-k\"\u003eelse\u003c/span\u003e {\n \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003eafter\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003enext\u003c/span\u003e;\n \u003cspan class=\"pl-smi\"\u003eListNode\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003ebefore\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003eprev\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003eafter\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003eprev\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003ebefore\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003ebefore\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003enext\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eafter\u003c/span\u003e;\n }\n\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003ecount\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e--\u003c/span\u003e;\n \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003evalue\u003c/span\u003e;\n \u003cspan class=\"pl-en\"\u003efree\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003enode\u003c/span\u003e);\n\n\u003cspan class=\"pl-ent\"\u003eerror\u003c/span\u003e:\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003eresult\u003c/span\u003e;\n}\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e我实现了双向链表上的所有操作，它们不能用简单的宏来完成。比起覆盖文件中的每一行，我打算为\u003ccode\u003elist.h\u003c/code\u003e和\u003ccode\u003elist.c\u003c/code\u003e中的每个操作提供一个高阶的概览。你需要自己阅读代码。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.h:List_count\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e返回链表中元素数量，它在元素添加或移除时维护。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.h:List_first\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e返回链表的首个元素，但是并不移除它。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.h:List_last\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e返回链表的最后一个元素，但是不移除它。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.h:LIST_FOREACH\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e遍历链表中的元素。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.c:List_create\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e简单地创建主要的\u003ccode\u003eList\u003c/code\u003e结构。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.c:List_destroy\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e销毁\u003ccode\u003eList\u003c/code\u003e以及其中含有的所有元素。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.c:List_clear\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e为释放每个节点中的值（而不是节点本身）创建的辅助函数。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.c:List_clear_destroy\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e清理并销毁链表。它并不十分搞笑因为它对每个元素遍历两次。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.c:List_push\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e第一个操作演示了链表的有点。它向链表尾添加新的元素，由于只是一些指针赋值，所以非常快。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.c:List_pop\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e\u003ccode\u003eList_push\u003c/code\u003e的反向版本，它去除最后一个元素并返回它。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.c:List_unshift\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e亦可以轻易对链表执行的另一件事，就是快速地向链表头部添加元素。由于找不到合适的词，这里我把它称为\u003ccode\u003eunshift\u003c/code\u003e。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.c:List_shift\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e类似\u003ccode\u003eList_pop\u003c/code\u003e，但是它移除链表的首个元素并返回。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003elist.c:List_remove\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e当你执行\u003ccode\u003eList_pop\u003c/code\u003e或\u003ccode\u003eList_shift\u003c/code\u003e时，它执行实际的移除操作。在数据结构中移除数据总是看似比较困难，这个函数也不例外。它需要处理一些条件，取决于被移除的位置，在开头、在结尾、开头并且结尾，或者在中间。\u003c/p\u003e\n\u003cp dir=\"auto\"\u003e这些函数大多数都没什么特别的，你应该能够轻易描述出来，并且根据代码来理解它。你应该完全专注于\u003ccode\u003eList_destroy\u003c/code\u003e中的\u003ccode\u003eLIST_FOREACH\u003c/code\u003e如何使用来理解它如何简化通常的操作。\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e测试\u003c/h2\u003e\u003ca id=\"user-content-测试\" class=\"anchor\" aria-label=\"Permalink: 测试\" href=\"#测试\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e在你编译它们之前，需要创建测试来确保它们正确执行。\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-c notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"#include \u0026quot;minunit.h\u0026quot;\n#include \u0026lt;lcthw/list.h\u0026gt;\n#include \u0026lt;assert.h\u0026gt;\n\nstatic List *list = NULL;\nchar *test1 = \u0026quot;test1 data\u0026quot;;\nchar *test2 = \u0026quot;test2 data\u0026quot;;\nchar *test3 = \u0026quot;test3 data\u0026quot;;\n\n\nchar *test_create()\n{\n list = List_create();\n mu_assert(list != NULL, \u0026quot;Failed to create list.\u0026quot;);\n\n return NULL;\n}\n\n\nchar *test_destroy()\n{\n List_clear_destroy(list);\n\n return NULL;\n\n}\n\n\nchar *test_push_pop()\n{\n List_push(list, test1);\n mu_assert(List_last(list) == test1, \u0026quot;Wrong last value.\u0026quot;);\n\n List_push(list, test2);\n mu_assert(List_last(list) == test2, \u0026quot;Wrong last value\u0026quot;);\n\n List_push(list, test3);\n mu_assert(List_last(list) == test3, \u0026quot;Wrong last value.\u0026quot;);\n mu_assert(List_count(list) == 3, \u0026quot;Wrong count on push.\u0026quot;);\n\n char *val = List_pop(list);\n mu_assert(val == test3, \u0026quot;Wrong value on pop.\u0026quot;);\n\n val = List_pop(list);\n mu_assert(val == test2, \u0026quot;Wrong value on pop.\u0026quot;);\n\n val = List_pop(list);\n mu_assert(val == test1, \u0026quot;Wrong value on pop.\u0026quot;);\n mu_assert(List_count(list) == 0, \u0026quot;Wrong count after pop.\u0026quot;);\n\n return NULL;\n}\n\nchar *test_unshift()\n{\n List_unshift(list, test1);\n mu_assert(List_first(list) == test1, \u0026quot;Wrong first value.\u0026quot;);\n\n List_unshift(list, test2);\n mu_assert(List_first(list) == test2, \u0026quot;Wrong first value\u0026quot;);\n\n List_unshift(list, test3);\n mu_assert(List_first(list) == test3, \u0026quot;Wrong last value.\u0026quot;);\n mu_assert(List_count(list) == 3, \u0026quot;Wrong count on unshift.\u0026quot;);\n\n return NULL;\n}\n\nchar *test_remove()\n{\n // we only need to test the middle remove case since push/shift\n // already tests the other cases\n\n char *val = List_remove(list, list-\u0026gt;first-\u0026gt;next);\n mu_assert(val == test2, \u0026quot;Wrong removed element.\u0026quot;);\n mu_assert(List_count(list) == 2, \u0026quot;Wrong count after remove.\u0026quot;);\n mu_assert(List_first(list) == test3, \u0026quot;Wrong first after remove.\u0026quot;);\n mu_assert(List_last(list) == test1, \u0026quot;Wrong last after remove.\u0026quot;);\n\n return NULL;\n}\n\n\nchar *test_shift()\n{\n mu_assert(List_count(list) != 0, \u0026quot;Wrong count before shift.\u0026quot;);\n\n char *val = List_shift(list);\n mu_assert(val == test3, \u0026quot;Wrong value on shift.\u0026quot;);\n\n val = List_shift(list);\n mu_assert(val == test1, \u0026quot;Wrong value on shift.\u0026quot;);\n mu_assert(List_count(list) == 0, \u0026quot;Wrong count after shift.\u0026quot;);\n\n return NULL;\n}\n\n\n\nchar *all_tests() {\n mu_suite_start();\n\n mu_run_test(test_create);\n mu_run_test(test_push_pop);\n mu_run_test(test_unshift);\n mu_run_test(test_remove);\n mu_run_test(test_shift);\n mu_run_test(test_destroy);\n\n return NULL;\n}\n\nRUN_TESTS(all_tests);\"\u003e\u003cpre\u003e\u003cspan class=\"pl-k\"\u003e#include\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"minunit.h\"\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003e#include\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\u0026lt;lcthw/list.h\u0026gt;\u003c/span\u003e\n\u003cspan class=\"pl-k\"\u003e#include\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\u0026lt;assert.h\u0026gt;\u003c/span\u003e\n\n\u003cspan class=\"pl-k\"\u003estatic\u003c/span\u003e \u003cspan class=\"pl-smi\"\u003eList\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003etest1\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"test1 data\"\u003c/span\u003e;\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003etest2\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"test2 data\"\u003c/span\u003e;\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003etest3\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-s\"\u003e\"test3 data\"\u003c/span\u003e;\n\n\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003etest_create\u003c/span\u003e()\n{\n \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_create\u003c/span\u003e();\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Failed to create list.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n}\n\n\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003etest_destroy\u003c/span\u003e()\n{\n \u003cspan class=\"pl-en\"\u003eList_clear_destroy\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n\n}\n\n\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan cla
8000
ss=\"pl-en\"\u003etest_push_pop\u003c/span\u003e()\n{\n \u003cspan class=\"pl-en\"\u003eList_push\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etest1\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_last\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest1\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong last value.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-en\"\u003eList_push\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etest2\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_last\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest2\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong last value\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-en\"\u003eList_push\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etest3\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_last\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest3\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong last value.\"\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_count\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong count on push.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_pop\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest3\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong value on pop.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_pop\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest2\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong value on pop.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_pop\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest1\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong value on pop.\"\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_count\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong count after pop.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n}\n\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003etest_unshift\u003c/span\u003e()\n{\n \u003cspan class=\"pl-en\"\u003eList_unshift\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etest1\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_first\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest1\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong first value.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-en\"\u003eList_unshift\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etest2\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_first\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest2\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong first value\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-en\"\u003eList_unshift\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003etest3\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_first\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest3\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong last value.\"\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_count\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e3\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong count on unshift.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n}\n\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003etest_remove\u003c/span\u003e()\n{\n \u003cspan class=\"pl-c\"\u003e// we only need to test the middle remove case since push/shift\u003c/span\u003e\n \u003cspan class=\"pl-c\"\u003e// already tests the other cases\u003c/span\u003e\n\n \u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_remove\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e, \u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003efirst\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003e-\u0026gt;\u003c/span\u003e\u003cspan class=\"pl-c1\"\u003enext\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest2\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong removed element.\"\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_count\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e2\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong count after remove.\"\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_first\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest3\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong first after remove.\"\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_last\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest1\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong last after remove.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n}\n\n\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003etest_shift\u003c/span\u003e()\n{\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_count\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e!=\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong count before shift.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_shift\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest3\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong value on shift.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e=\u003c/span\u003e \u003cspan class=\"pl-en\"\u003eList_shift\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eval\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-s1\"\u003etest1\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong value on shift.\"\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_assert\u003c/span\u003e(\u003cspan class=\"pl-en\"\u003eList_count\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003elist\u003c/span\u003e) \u003cspan class=\"pl-c1\"\u003e==\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e0\u003c/span\u003e, \u003cspan class=\"pl-s\"\u003e\"Wrong count after shift.\"\u003c/span\u003e);\n\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n}\n\n\n\n\u003cspan class=\"pl-smi\"\u003echar\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003e*\u003c/span\u003e\u003cspan class=\"pl-en\"\u003eall_tests\u003c/span\u003e() {\n \u003cspan class=\"pl-en\"\u003emu_suite_start\u003c/span\u003e();\n\n \u003cspan class=\"pl-en\"\u003emu_run_test\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003etest_create\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_run_test\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003etest_push_pop\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_run_test\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003etest_unshift\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_run_test\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003etest_remove\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_run_test\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003etest_shift\u003c/span\u003e);\n \u003cspan class=\"pl-en\"\u003emu_run_test\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003etest_destroy\u003c/span\u003e);\n\n \u003cspan class=\"pl-k\"\u003ereturn\u003c/span\u003e \u003cspan class=\"pl-c1\"\u003eNULL\u003c/span\u003e;\n}\n\n\u003cspan class=\"pl-en\"\u003eRUN_TESTS\u003c/span\u003e(\u003cspan class=\"pl-s1\"\u003eall_tests\u003c/span\u003e);\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e它简单地遍历了每个操作，并且确保它们有效。我在测试中做了简化，对于整个程序我只创建了一个\u003ccode\u003eList *list\u003c/code\u003e，这解决了为每个测试构建一个\u003ccode\u003eList\u003c/code\u003e的麻烦，但它同时意味着一些测试会受到之前测试的影响。这里我试着是每个测试不改变链表，或实际使用上一个测试的结果。\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e你会看到什么\u003c/h2\u003e\u003ca id=\"user-content-你会看到什么\" class=\"anchor\" aria-label=\"Permalink: 你会看到什么\" href=\"#你会看到什么\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e如果你正确完成了每件事，当你执行构建并且运行单元测试是，你会看到：\u003c/p\u003e\n\u003cdiv class=\"highlight highlight-source-shell notranslate position-relative overflow-auto\" dir=\"auto\" data-snippet-clipboard-copy-content=\"$ make\ncc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG -fPIC -c -o src/lcthw/list.o src/lcthw/list.c\nar rcs build/liblcthw.a src/lcthw/list.o\nranlib build/liblcthw.a\ncc -shared -o build/liblcthw.so src/lcthw/list.o\ncc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG build/liblcthw.a tests/list_tests.c -o tests/list_tests\nsh ./tests/runtests.sh\nRunning unit tests:\n----\nRUNNING: ./tests/list_tests\nALL TESTS PASSED\nTests run: 6\ntests/list_tests PASS\n$\"\u003e\u003cpre\u003e$ make\ncc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG -fPIC -c -o src/lcthw/list.o src/lcthw/list.c\nar rcs build/liblcthw.a src/lcthw/list.o\nranlib build/liblcthw.a\ncc -shared -o build/liblcthw.so src/lcthw/list.o\ncc -g -O2 -Wall -Wextra -Isrc -rdynamic -DNDEBUG build/liblcthw.a tests/list_tests.c -o tests/list_tests\nsh ./tests/runtests.sh\nRunning unit tests:\n----\nRUNNING: ./tests/list_tests\nALL TESTS PASSED\nTests run: 6\ntests/list_tests PASS\n$\u003c/pre\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e确保6个测试运行完毕，以及构建时没有警告或错误，并且成功构建了\u003ccode\u003ebuild/liblcthw.a\u003c/code\u003e和\u003ccode\u003ebuild/liblcthw.so\u003c/code\u003e文件。\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e如何改进\u003c/h2\u003e\u003ca id=\"user-content-如何改进\" class=\"anchor\" aria-label=\"Permalink: 如何改进\" href=\"#如何改进\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cp dir=\"auto\"\u003e我打算告诉你如何改进代码，而不是使它崩溃。\u003c/p\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e你可以使用\u003ccode\u003eLIST_FOREACH\u003c/code\u003e并在循环中调用\u003ccode\u003efree\u003c/code\u003e来使\u003ccode\u003eList_clear_destroy\u003c/code\u003e更高效。\u003c/li\u003e\n\u003cli\u003e你可以为一些先决条件添加断言，使其部结构\u003ccode\u003eNULL\u003c/code\u003e值作为\u003ccode\u003eList *list\u003c/code\u003e的参数。\u003c/li\u003e\n\u003cli\u003e你可以添加不变了，来检查列表的内容始终正确，例如\u003ccode\u003ecount\u003c/code\u003e永远不会\u003ccode\u003e\u0026lt; 0\u003c/code\u003e，如果\u003ccode\u003ecount \u0026gt; 0\u003c/code\u003e，\u003ccode\u003efirst\u003c/code\u003e不为\u003ccode\u003eNULL\u003c/code\u003e。\u003c/li\u003e\n\u003cli\u003e你可以向头文件添加文档，在每个结构、函数和宏之前添加描述其作用的注释。\u003c/li\u003e\n\u003c/ul\u003e\n\u003cp dir=\"auto\"\u003e这些改进执行了防御性编程实践，并且“加固”了代码来避免错误或使用不当。马上去做这些事情，之后找到尽可能多的办法来改进代码。\u003c/p\u003e\n\u003cdiv class=\"markdown-heading\" dir=\"auto\"\u003e\u003ch2 tabindex=\"-1\" class=\"heading-element\" dir=\"auto\"\u003e附加题\u003c/h2\u003e\u003ca id=\"user-content-附加题\" class=\"anchor\" aria-label=\"Permalink: 附加题\" href=\"#附加题\"\u003e\u003csvg class=\"octicon octicon-link\" viewBox=\"0 0 16 16\" version=\"1.1\" width=\"16\" height=\"16\" aria-hidden=\"true\"\u003e\u003cpath d=\"m7.775 3.275 1.25-1.25a3.5 3.5 0 1 1 4.95 4.95l-2.5 2.5a3.5 3.5 0 0 1-4.95 0 .751.751 0 0 1 .018-1.042.751.751 0 0 1 1.042-.018 1.998 1.998 0 0 0 2.83 0l2.5-2.5a2.002 2.002 0 0 0-2.83-2.83l-1.25 1.25a.751.751 0 0 1-1.042-.018.751.751 0 0 1-.018-1.042Zm-4.69 9.64a1.998 1.998 0 0 0 2.83 0l1.25-1.25a.751.751 0 0 1 1.042.018.751.751 0 0 1 .018 1.042l-1.25 1.25a3.5 3.5 0 1 1-4.95-4.95l2.5-2.5a3.5 3.5 0 0 1 4.95 0 .751.751 0 0 1-.018 1.042.751.751 0 0 1-1.042.018 1.998 1.998 0 0 0-2.83 0l-2.5 2.5a1.998 1.998 0 0 0 0 2.83Z\"\u003e\u003c/path\u003e\u003c/svg\u003e\u003c/a\u003e\u003c/div\u003e\n\u003cul dir=\"auto\"\u003e\n\u003cli\u003e研究双向和单向链表，以及什么情况下其中一种优于另一种。\u003c/li\u003e\n\u003cli\u003e研究双向链表的限制。例如，虽然它们对于插入和删除元素很高效，但是对于变量元素比较慢。\u003c/li\u003e\n\u003cli\u003e还缺少什么你能想到的操作？比如复制、连接、分割等等。实现这些操作，并且为它们编写单元测试。\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/article\u003e","renderedFileInfo":null,"shortPath":null,"symbolsEnabled":true,"tabSize":8,"topBannersInfo":{"overridingGlobalFundingFile":false,"globalPreferredFundingPath":null,"showInvalidCitationWarning":false,"citationHelpUrl":"https://docs.github.com/github/creating-cloning-and-archiving-repositories/creating-a-repository-on-github/about-citation-files","actionsOnboardingTip":null},"truncated":false,"viewable":true,"workflowRedirectUrl":null,"symbols":{"timed_out":false,"not_analyzed":false,"symbols":[{"name":"练习32：双向链表","kind":"section_1","ident_start":2,"ident_end":25,"extent_start":0,"extent_end":15808,"fully_qualified_name":"练习32：双向链表","ident_utf16":{"start":{"line_number":0,"utf16_col":2},"end":{"line_number":0,"utf16_col":11}},"extent_utf16":{"start":{"line_number":0,"utf16_col":0},"end":{"line_number":485,"utf16_col":0}}},{"name":"数据结构是什么。","kind":"section_2","ident_start":1032,"ident_end":1056,"extent_start":1029,"extent_end":1652,"fully_qualified_name":"数据结构是什么。","ident_utf16":{"start":{"line_number":14,"utf16_col":3},"end":{"line_number":14,"utf16_col":11}},"extent_utf16":{"start":{"line_number":14,"utf16_col":0},"end":{"line_number":24,"utf16_col":0}}},{"name":"构建库","kind":"section_2","ident_start":1655,"ident_end":1664,"extent_start":1652,"extent_end":3150,"fully_qualified_name":"构建库","ident_utf16":{"start":{"line_number":24,"utf16_col":3},"end":{"line_number":24,"utf16_col":6}},"extent_utf16":{"start":{"line_number":24,"utf16_col":0},"end":{"line_number":69,"utf16_col":0}}},{"name":"双向链表","kind":"section_2","ident_start":3153,"ident_end":3165,"extent_start":3150,"extent_end":10985,"fully_qualified_name":"双向链表","ident_utf16":{"start":{"line_number":69,"utf16_col":3},"end":{"line_number":69,"utf16_col":7}},"extent_utf16":{"start":{"line_number":69,"utf16_col":0},"end":{"line_number":324,"utf16_col":0}}},{"name":"定义","kind":"section_3","ident_start":4162,"ident_end":4168,"extent_start":4158,"extent_end":6383,"fully_qualified_name":"定义","ident_utf16":{"start":{"line_number":77,"utf16_col":4},"end":{"line_number":77,"utf16_col":6}},"extent_utf16":{"start":{"line_number":77,"utf16_col":0},"end":{"line_number":137,"utf16_col":0}}},{"name":"实现","kind":"section_3","ident_start":6387,"ident_end":6393,"extent_start":6383,"extent_end":10985,"fully_qualified_name":"实现","ident_utf16":{"start":{"line_number":137,"utf16_col":4},"end":{"line_number":137,"utf16_col":6}},"extent_utf16":{"start":{"line_number":137,"utf16_col":0},"end":{"line_number":324,"utf16_col":0}}},{"name":"测试","kind":"section_2","ident_start":10988,"ident_end":10994,"extent_start":10985,"extent_end":13987,"fully_qualified_name":"测试","ident_utf16":{"start":{"line_number":324,"utf16_col":3},"end":{"line_number":324,"utf16_col":5}},"extent_utf16":{"start":{"line_number":324,"utf16_col":0},"end":{"line_number":446,"utf16_col":0}}},{"name":"你会看到什么","kind":"section_2","ident_start":13990,"ident_end":14008,"extent_start":13987,"extent_end":14724,"fully_qualified_name":"你会看到什么","ident_utf16":{"start":{"line_number":446,"utf16_col":3},"end":{"line_number":446,"utf16_col":9}},"extent_utf16":{"start":{"line_number":446,"utf16_col":0},"end":{"line_number":469,"utf16_col":0}}},{"name":"如何改进","kind":"section_2","ident_start":14727,"ident_end":14739,"extent_start":14724,"extent_end":15443,"fully_qualified_name":"如何改进","ident_utf16":{"start":{"line_number":469,"utf16_col":3},"end":{"line_number":469,"utf16_col":7}},"extent_utf16":{"start":{"line_number":469,"utf16_col":0},"end":{"line_number":480,"utf16_col":0}}},{"name":"附加题","kind":"section_2","ident_start":15446,"ident_end":15455,"extent_start":15443,"extent_end":15808,"fully_qualified_name":"附加题","ident_utf16":{"start":{"line_number":480,"utf16_col":3},"end":{"line_number":480,"utf16_col":6}},"extent_utf16":{"start":{"line_number":480,"utf16_col":0},"end":{"line_number":485,"utf16_col":0}}}]}},"copilotInfo":null,"copilotAccessAllowed":false,"modelsAccessAllowed":false,"modelsRepoIntegrationEnabled":false,"csrf_tokens":{"/hiekay/lcthw-zh/branches":{"post":"kJgUtxwuRmwl9a4CMpX62PM2Ckq5Rw0RswrRyhHE3u40gOB94-5U2xgYOKByvvh0ioVb_NZRfn9VMShv9nzfrw"},"/repos/preferences":{"post":"KoEuby4LqZmJ0v5TSZTQx_CmH5E2qCKdkoislHPRj6jbzQIrmCVM97Hlyksf5mUU9iAriSWCTK7TkjZqsSVfHQ"}}},"title":"lcthw-zh/ex32.md at master · hiekay/lcthw-zh","appPayload":{"helpUrl":"https://docs.github.com","findFileWorkerPath":"/assets-cdn/worker/find-file-worker-7d7eb7c71814.js","findInFileWorkerPath":"/assets-cdn/worker/find-in-file-worker-1ae9fa256942.js","githubDevUrl":null,"enabled_features":{"code_nav_ui_events":false,"react_blob_overlay":false,"accessible_code_button":true,"github_models_repo_integration":false}}}
You can’t perform that action at this time.