"use strict"; const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0]; const {useMDXComponents: _provideComponents} = arguments[0]; function _createMdxContent(props) { const _components = { a: "a", annotation: "annotation", blockquote: "blockquote", code: "code", details: "details", div: "div", em: "em", h2: "h2", h3: "h3", li: "li", math: "math", mi: "mi", mn: "mn", mo: "mo", mrow: "mrow", mstyle: "mstyle", msub: "msub", mtable: "mtable", mtd: "mtd", mtext: "mtext", mtr: "mtr", ol: "ol", p: "p", path: "path", pre: "pre", semantics: "semantics", span: "span", strong: "strong", summary: "summary", svg: "svg", ul: "ul", ..._provideComponents(), ...props.components }; return _jsxs(_Fragment, { children: [_jsx(_components.p, { children: "本章结构：" }), "\n", _jsx(_components.span, { className: "katex-display", children: _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", display: "block", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mtext, { children: "线性表" }), _jsxs(_components.mrow, { children: [_jsx(_components.mo, { fence: "true", children: "{" }), _jsxs(_components.mtable, { rowspacing: "0.36em", columnalign: "left left", columnspacing: "1em", children: [_jsx(_components.mtr, { children: _jsx(_components.mtd, { children: _jsx(_components.mstyle, { scriptlevel: "0", displaystyle: "false", children: _jsx(_components.mtext, { children: "顺序存储——顺序表" }) }) }) }), _jsx(_components.mtr, { children: _jsx(_components.mtd, { children: _jsx(_components.mstyle, { scriptlevel: "0", displaystyle: "false", children: _jsxs(_components.mrow, { children: [_jsx(_components.mtext, { children: "链式存储" }), _jsxs(_components.mrow, { children: [_jsx(_components.mo, { fence: "true", children: "{" }), _jsxs(_components.mtable, { rowspacing: "0.36em", columnalign: "left left", columnspacing: "1em", children: [_jsx(_components.mtr, { children: _jsx(_components.mtd, { children: _jsx(_components.mstyle, { scriptlevel: "0", displaystyle: "false", children: _jsx(_components.mtext, { children: "单链表（指针实现）" }) }) }) }), _jsx(_components.mtr, { children: _jsx(_components.mtd, { children: _jsx(_components.mstyle, { scriptlevel: "0", displaystyle: "false", children: _jsx(_components.mtext, { children: "双链表（指针实现）" }) }) }) }), _jsx(_components.mtr, { children: _jsx(_components.mtd, { children: _jsx(_components.mstyle, { scriptlevel: "0", displaystyle: "false", children: _jsx(_components.mtext, { children: "循环链表（指针实现）" }) }) }) }), _jsx(_components.mtr, { children: _jsx(_components.mtd, { children: _jsx(_components.mstyle, { scriptlevel: "0", displaystyle: "false", children: _jsx(_components.mtext, { children: "静态链表（借助数组实现）" }) }) }) })] })] })] }) }) }) })] })] })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "线性表\\begin{cases}\n顺序存储——顺序表 \\\\\n链式存储 \\begin{cases}\n单链表（指针实现） \\\\\n双链表（指针实现） \\\\\n循环链表（指针实现） \\\\\n静态链表（借助数组实现）\n\\end{cases}\n\\end{cases}" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "7.2em", verticalAlign: "-3.35em" } }), _jsx(_components.span, { className: "mord cjk_fallback", children: "线性表" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "minner", children: [_jsx(_components.span, { className: "mopen", children: _jsx(_components.span, { className: "delimsizing mult", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsxs(_components.span, { className: "vlist", style: { height: "3.85em" }, children: [_jsxs(_components.span, { style: { top: "-1.366em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.816em" } }), _jsx(_components.span, { className: "delimsizinginner delim-size4", children: _jsx(_components.span, { children: "⎩" }) })] }), _jsxs(_components.span, { style: { top: "-1.358em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.816em" } }), _jsx(_components.span, { style: { height: "1.816em", width: "0.8889em" }, children: _jsx(_components.svg, { xmlns: "http://www.w3.org/2000/svg", width: "0.8889em", height: "1.816em", style: { width: "0.8889em" }, viewBox: "0 0 888.89 1816", preserveAspectRatio: "xMinYMin", children: _jsx(_components.path, { d: "M384 0 H504 V1816 H384z M384 0 H504 V1816 H384z" }) }) })] }), _jsxs(_components.span, { style: { top: "-3.816em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.816em" } }), _jsx(_components.span, { className: "delimsizinginner delim-size4", children: _jsx(_components.span, { children: "⎨" }) })] }), _jsxs(_components.span, { style: { top: "-4.958em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.816em" } }), _jsx(_components.span, { style: { height: "1.816em", width: "0.8889em" }, children: _jsx(_components.svg, { xmlns: "http://www.w3.org/2000/svg", width: "0.8889em", height: "1.816em", style: { width: "0.8889em" }, viewBox: "0 0 888.89 1816", preserveAspectRatio: "xMinYMin", children: _jsx(_components.path, { d: "M384 0 H504 V1816 H384z M384 0 H504 V1816 H384z" }) }) })] }), _jsxs(_components.span, { style: { top: "-6.766em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.816em" } }), _jsx(_components.span, { className: "delimsizinginner delim-size4", children: _jsx(_components.span, { children: "⎧" }) })] })] }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "3.35em" }, children: _jsx(_components.span, {}) }) })] }) }) }), _jsx(_components.span, { className: "mord", children: _jsx(_components.span, { className: "mtable", children: _jsx(_components.span, { className: "col-align-l", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsxs(_components.span, { className: "vlist", style: { height: "3.85em" }, children: [_jsxs(_components.span, { style: { top: "-7.972em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "5.13em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord cjk_fallback", children: "顺序存储" }), _jsx(_components.span, { className: "mord", children: "——" }), _jsx(_components.span, { className: "mord cjk_fallback", children: "顺序表" })] })] }), _jsxs(_components.span, { style: { top: "-4.41em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "5.13em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord cjk_fallback", children: "链式存储" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "minner", children: [_jsx(_components.span, { className: "mopen", children: _jsx(_components.span, { className: "delimsizing mult", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsxs(_components.span, { className: "vlist", style: { height: "2.95em" }, children: [_jsxs(_components.span, { style: { top: "-1.6em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.15em" } }), _jsx(_components.span, { className: "delimsizinginner delim-size4", children: _jsx(_components.span, { children: "⎩" }) })] }), _jsxs(_components.span, { style: { top: "-1.592em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.15em" } }), _jsx(_components.span, { style: { height: "0.916em", width: "0.8889em" }, children: _jsx(_components.svg, { xmlns: "http://www.w3.org/2000/svg", width: "0.8889em", height: "0.916em", style: { width: "0.8889em" }, viewBox: "0 0 888.89 916", preserveAspectRatio: "xMinYMin", children: _jsx(_components.path, { d: "M384 0 H504 V916 H384z M384 0 H504 V916 H384z" }) }) })] }), _jsxs(_components.span, { style: { top: "-3.15em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.15em" } }), _jsx(_components.span, { className: "delimsizinginner delim-size4", children: _jsx(_components.span, { children: "⎨" }) })] }), _jsxs(_components.span, { style: { top: "-4.292em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.15em" } }), _jsx(_components.span, { style: { height: "0.916em", width: "0.8889em" }, children: _jsx(_components.svg, { xmlns: "http://www.w3.org/2000/svg", width: "0.8889em", height: "0.916em", style: { width: "0.8889em" }, viewBox: "0 0 888.89 916", preserveAspectRatio: "xMinYMin", children: _jsx(_components.path, { d: "M384 0 H504 V916 H384z M384 0 H504 V916 H384z" }) }) })] }), _jsxs(_components.span, { style: { top: "-5.2em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.15em" } }), _jsx(_components.span, { className: "delimsizinginner delim-size4", children: _jsx(_components.span, { children: "⎧" }) })] })] }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "2.45em" }, children: _jsx(_components.span, {}) }) })] }) }) }), _jsx(_components.span, { className: "mord", children: _jsx(_components.span, { className: "mtable", children: _jsx(_components.span, { className: "col-align-l", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsxs(_components.span, { className: "vlist", style: { height: "3.13em" }, children: [_jsxs(_components.span, { style: { top: "-5.13em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.008em" } }), _jsx(_components.span, { className: "mord", children: _jsx(_components.span, { className: "mord cjk_fallback", children: "单链表（指针实现）" }) })] }), _jsxs(_components.span, { style: { top: "-3.69em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.008em" } }), _jsx(_components.span, { className: "mord", children: _jsx(_components.span, { className: "mord cjk_fallback", children: "双链表（指针实现）" }) })] }), _jsxs(_components.span, { style: { top: "-2.25em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.008em" } }), _jsx(_components.span, { className: "mord", children: _jsx(_components.span, { className: "mord cjk_fallback", children: "循环链表（指针实现）" }) })] }), _jsxs(_components.span, { style: { top: "-0.81em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "3.008em" } }), _jsx(_components.span, { className: "mord", children: _jsx(_components.span, { className: "mord cjk_fallback", children: "静态链表（借助数组实现）" }) })] })] }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "2.63em" }, children: _jsx(_components.span, {}) }) })] }) }) }) }), _jsx(_components.span, { className: "mclose nulldelimiter" })] })] })] })] }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "3.35em" }, children: _jsx(_components.span, {}) }) })] }) }) }) }), _jsx(_components.span, { className: "mclose nulldelimiter" })] })] }) })] }) }), "\n", _jsxs(_components.h2, { id: "21-线性表的定义和基本操作", children: [_jsx(_components.a, { className: "heading-link", href: "#21-线性表的定义和基本操作", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.1 线性表的定义和基本操作"] }), "\n", _jsxs(_components.h3, { id: "211-线性表的定义", children: [_jsx(_components.a, { className: "heading-link", href: "#211-线性表的定义", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.1.1 线性表的定义"] }), "\n", _jsxs(_components.p, { children: ["定义：具有", _jsx(_components.strong, { children: "相同数据类型" }), "的 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "n" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" })] }) })] }), " 个数据元素的", _jsx(_components.strong, { children: "有限序列" }), "。"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "n" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" })] }) })] }), " 为表长，", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "≥" }), _jsx(_components.mn, { children: "0" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n\\geq0" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.7719em", verticalAlign: "-0.136em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "≥" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "0" })] })] })] }), "。", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "n" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mn, { children: "0" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "n=0" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "n" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6444em" } }), _jsx(_components.span, { className: "mord", children: "0" })] })] })] }), " 时为空表。"] }), "\n", _jsxs(_components.li, { children: ["用 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "L" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" })] }) })] }), " 表示为：", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "L" }), _jsx(_components.mo, { children: "=" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mn, { children: "1" })] }), _jsx(_components.mo, { separator: "true", children: "," }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mn, { children: "2" })] }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mo, { children: "…" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "i" })] }), _jsx(_components.mo, { separator: "true", children: "," }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "a" }), _jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "i" }), _jsx(_components.mo, { children: "+" }), _jsx(_components.mn, { children: "1" })] })] }), _jsx(_components.mo, { separator: "true", children: "," }), _jsx(_components.mo, { children: "…" }), _jsx(_components.mo, { separator: "true", children: "," }), _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "n" })] }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L=(a_{1},a_{2},\\dots,a_{i},a_{i+1},\\dots,a_{n})" })] }) }) }), _jsxs(_components.span, { className: "katex-html", "aria-hidden": "true", children: [_jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } }), _jsx(_components.span, { className: "mrel", children: "=" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.2778em" } })] }), _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "1" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "2" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "minner", children: "…" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3117em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mathnormal mtight", children: "i" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3117em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsxs(_components.span, { className: "mord mtight", children: [_jsx(_components.span, { className: "mord mathnormal mtight", children: "i" }), _jsx(_components.span, { className: "mbin mtight", children: "+" }), _jsx(_components.span, { className: "mord mtight", children: "1" })] }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.2083em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "minner", children: "…" }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsx(_components.span, { className: "mpunct", children: "," }), _jsx(_components.span, { className: "mspace", style: { marginRight: "0.1667em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.1514em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] }), _jsx(_components.span, { className: "mclose", children: ")" })] })] })] }) }), "\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mn, { children: "1" })] }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "a_{1}" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.5806em", verticalAlign: "-0.15em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3011em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mtight", children: "1" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] })] }) })] }), "：第一个数据元素，也叫", _jsx(_components.strong, { children: "表头元素" }), "。"] }), "\n", _jsxs(_components.li, { children: [_jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "n" })] }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "a_{n}" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.5806em", verticalAlign: "-0.15em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.1514em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mathnormal mtight", children: "n" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] })] }) })] }), "：最后一个数据元素，也叫", _jsx(_components.strong, { children: "表尾元素" }), "。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["逻辑特性：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["除第一个元素外，每个元素有且仅有", _jsx(_components.strong, { children: "一个直接前驱" }), "。"] }), "\n", _jsxs(_components.li, { children: ["除最后一个元素外，每个元素有且仅有", _jsx(_components.strong, { children: "一个直接后继" }), "。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["特点：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["表中元素的", _jsx(_components.strong, { children: "个数有限" }), "。"] }), "\n", _jsxs(_components.li, { children: ["表中元素具有逻辑上顺序性，表中", _jsx(_components.strong, { children: "元素有先后次序" }), "。"] }), "\n", _jsxs(_components.li, { children: ["表中都是数据元素，每个", _jsx(_components.strong, { children: "元素都是单个元素" }), "。"] }), "\n", _jsxs(_components.li, { children: ["表中", _jsx(_components.strong, { children: "元素的数据类型都相同" }), "，也就是说每个元素所占据的存储空间相同。"] }), "\n", _jsxs(_components.li, { children: ["表中元素具有抽象性，", _jsx(_components.strong, { children: "只讨论元素之间的逻辑关系" }), "，不关心元素内容。"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["注意区分", _jsx(_components.strong, { children: "顺序表" }), "和", _jsx(_components.strong, { children: "线性表" }), "，线性表是一种高度抽象的", _jsx(_components.strong, { children: "逻辑结构" }), "，而顺序表是", _jsx(_components.strong, { children: "存储结构" }), "。顺序表和链表在同一层次。"] }), "\n"] }), "\n", _jsxs(_components.h3, { id: "212-线性表的基本操作", children: [_jsx(_components.a, { className: "heading-link", href: "#212-线性表的基本操作", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.1.2 线性表的基本操作"] }), "\n", _jsxs(_components.p, { children: ["基本操作：指一个数据结构", _jsx(_components.strong, { children: "最核心、最基本" }), "的操作。\n其他复杂操作：可调用基本操作来实现。"] }), "\n", _jsx(_components.p, { children: "线性表的主要操作有：" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "InitList(&L)" }), "：初始化表。", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "构造一个空线性表。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "Length(L)" }), "：求表长。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["返回线性表的长度 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "L" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" })] }) })] }), "，即表中的数据个数。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "LocateElem(L, e)" }), "：按值查找操作。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["在表 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "L" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" })] }) })] }), " 中查找具有给定关键字值的元素。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "GetElem(L, i)" }), "：按位查找操作。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["按位查找操作。获取表 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "L" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" })] }) })] }), " 中第 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "i" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) })] }), " 个位置的元素的值。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "ListInsert(&L, i, e)" }), "：插入操作。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["在表 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "L" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" })] }) })] }), " 中的第 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "i" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) })] }), " 个位置上插入指定元素 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "e" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "e" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "e" })] }) })] }), "。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "ListDelete(&L, i, &e)" }), "：删除操作。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["删除表 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "L" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" })] }) })] }), " 中第 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "i" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) })] }), " 个位置的元素，并用 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "e" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "e" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.4306em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "e" })] }) })] }), " 返回删除元素的值。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "PrintList(L)" }), "：输出操作。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["按前后顺序输出线性表 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "L" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" })] }) })] }), " 中的所有元素的值。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "Empty(L)" }), "：判空操作。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["若 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "L" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" })] }) })] }), " 为空表返回 true，否则返回 false。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.code, { className: "language-auto", children: "DestroyList(&L)" }), "：销毁操作。", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["销毁线性表，释放线性表 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "L" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "L" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6833em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "L" })] }) })] }), " 所占用的内存空间。"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["1️⃣基本操作的实现取决于存储结构，存储结构不同算法实现也不同。2️⃣ ", _jsx(_components.code, { className: "language-auto", children: "&" }), " 为 C++中的引用调用。"] }), "\n"] }), "\n", _jsxs(_components.h2, { id: "22-线性表的顺序表示", children: [_jsx(_components.a, { className: "heading-link", href: "#22-线性表的顺序表示", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.2 线性表的顺序表示"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "从字面上就能理解，顺序表是有顺序的线性表，约束条件更强。" }), "\n"] }), "\n", _jsxs(_components.p, { children: ["顺序表：线性表的", _jsx(_components.strong, { children: "顺序存储" }), "。"] }), "\n", _jsx(_components.p, { children: "特点：" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["用", _jsx(_components.strong, { children: "地址连续的存储" }), "单元依次存储线性表中的数据元素。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "逻辑相邻" }), "的两个元素在", _jsx(_components.strong, { children: "物理位置上也相邻" }), "。"] }), "\n", _jsx(_components.li, { children: "物理存储位置与位序成正比，故可以实现随机存取。" }), "\n"] }), "\n", _jsx(_components.p, { children: "优点：" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["可实现", _jsx(_components.strong, { children: "随机访问" }), "，通过首地址+元素序号 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsxs(_components.mrow, { children: [_jsx(_components.mi, { children: "O" }), _jsx(_components.mo, { stretchy: "false", children: "(" }), _jsx(_components.mn, { children: "1" }), _jsx(_components.mo, { stretchy: "false", children: ")" })] }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "O(1)" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "1em", verticalAlign: "-0.25em" } }), _jsx(_components.span, { className: "mord mathnormal", style: { marginRight: "0.0278em" }, children: "O" }), _jsx(_components.span, { className: "mopen", children: "(" }), _jsx(_components.span, { className: "mord", children: "1" }), _jsx(_components.span, { className: "mclose", children: ")" })] }) })] }), " 时间内找到指定元素。"] }), "\n", _jsx(_components.li, { children: "存储密度高，每个节点只能存储数据元素。" }), "\n"] }), "\n", _jsxs(_components.details, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.summary, { "data-callout-title": true, children: "理解" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsxs(_components.p, { children: ["为什么链表不具备随机访问呢？原因在于", _jsx(_components.strong, { children: "顺序表的顺序高度确定" }), "，这种强大的起家条件使得顺序表具备了卓越的查询能力。"] }), "\n"] }), "\n"] }), "\n", _jsx(_components.p, { children: "缺点：" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "插入和删除耗时，可能需要移动大量元素。" }), "\n", _jsx(_components.li, { children: "需要连续空间才能存储，不够灵活。" }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "随机存取就是不需要遍历线性表，直接给出一个位序就可以直接存入。" }), "\n"] }), "\n", _jsxs(_components.p, { children: ["位序：称 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsx(_components.mi, { children: "i" }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "i" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.6595em" } }), _jsx(_components.span, { className: "mord mathnormal", children: "i" })] }) })] }), " 为元素 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "i" })] }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "a_{i}" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.5806em", verticalAlign: "-0.15em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3117em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mathnormal mtight", children: "i" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] })] }) })] }), " 在顺序表中的位序。"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["顺序表中元素的位序从 ", _jsx(_components.code, { className: "language-auto", children: "1" }), " 开始，而数组的下标是从 ", _jsx(_components.code, { className: "language-auto", children: "0" }), " 开始的。"] }), "\n"] }), "\n", _jsxs(_components.details, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.summary, { "data-callout-title": true, children: "数组" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsxs(_components.p, { children: ["线性表强调线性，顺序表强调顺序。", _jsx(_components.strong, { children: "数组" }), "是高级语言中的概念，并非数据结构中的抽象概念，比如 Python 中就只有列表而没有数组。如果说线性表以及它下面的项目是一种思想，则", _jsx(_components.strong, { children: "数组" }), "则更多的是一种实际实现（代码层面对顺序表的实现），而非一种思想。"] }), "\n", _jsxs(_components.div, { "data-callout": true, "data-callout-type": "error", children: ["\n", _jsx(_components.div, { "data-callout-title": true, children: "Error" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsx(_components.p, { children: "这里有一个误区，可能会认为逻辑上数组和顺序表示一样的。实则不然，其他几种数据结构都能用数组来进行实现，比如链表、树🌲、队列、栈都能找到数组的对应实现，浙江的同学可以回忆一下，咱们高中时候学的栈、链表不都是用 Python 中的列表（就是数组）来实现的吗？" }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.details, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.summary, { "data-callout-title": true, children: " 存取方式" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "存取方式" }), "指的是 ", _jsx(_components.code, { className: "language-auto", children: "写/读" }), "，因此顺序表的存取方式是", _jsx(_components.strong, { children: "随机存取" }), "。可以在任何一个随机的位置用 O(1)复杂度读取数据，写入就是：", _jsx(_components.code, { className: "language-auto", children: "arr[2]=4" }), " 这种数组的赋值语句。\n有些同学（比如我）可能一开始会困惑", _jsx(_components.strong, { children: "插入数据" }), "不也是一种写入吗？实际上不是的，", _jsx(_components.strong, { children: "插入操作不能被理解为存取操作中的“存”" }), "。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "静态分配" }), "顺序表的存储结构描述："] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "MaxSize" }), " ", _jsxs(_components.span, { className: "token expression", children: [_jsx(_components.span, { className: "token number", children: "50" }), " "] }), _jsx(_components.span, { className: "token comment", children: "// 定义线性表最大长度" })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType data", _jsx(_components.span, { className: "token punctuation", children: "[" }), "MaxSize", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 顺序表的元素" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " length", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 顺序表的当前长度" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "SqList", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 顺序表的类型定义" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// C语言中分配语句为" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["L", _jsx(_components.span, { className: "token punctuation", children: "." }), "data ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "ElemType", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token function", children: "malloc" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "ElemType", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token operator", children: "*" }), "InitSize", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "动态分配" }), "顺序表的存储结构描述："] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "MaxSize" }), " ", _jsxs(_components.span, { className: "token expression", children: [_jsx(_components.span, { className: "token number", children: "100" }), " "] }), _jsx(_components.span, { className: "token comment", children: "// 表长度初始定义" })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType ", _jsx(_components.span, { className: "token operator", children: "*" }), "data", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 用来动态分配数组的指针" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " MaxSize", _jsx(_components.span, { className: "token punctuation", children: "," }), "length", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 数组最大容量和当前个数" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "SqList", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 动态分配数组顺序表的类型定义" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// C++中动态分配语句为" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["L", _jsx(_components.span, { className: "token punctuation", children: "." }), "data ", _jsx(_components.span, { className: "token operator", children: "=" }), " new ElemType", _jsx(_components.span, { className: "token punctuation", children: "[" }), "InitSize", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n", _jsxs(_components.details, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.summary, { "data-callout-title": true, children: "用法类似于定义一个类" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsx(_components.p, {}), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "include" }), " ", _jsx(_components.span, { className: "token string", children: "" })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "include" }), " ", _jsx(_components.span, { className: "token string", children: "" })] }), "\n"] }), _jsx(_components.span, { className: "code-line", children: " \n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "Books" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "char" }), " title", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "50" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "char" }), " author", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "50" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "char" }), " subject", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "100" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " book_id", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), " Book", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: " \n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "main" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), " ", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" Book book", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: " \n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "strcpy" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), " book", _jsx(_components.span, { className: "token punctuation", children: "." }), "title", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token string", children: "\"C 教程\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "strcpy" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), " book", _jsx(_components.span, { className: "token punctuation", children: "." }), "author", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token string", children: "\"Runoob\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "strcpy" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), " book", _jsx(_components.span, { className: "token punctuation", children: "." }), "subject", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token string", children: "\"编程语言\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" book", _jsx(_components.span, { className: "token punctuation", children: "." }), "book_id ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "12345" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: " \n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), " ", _jsx(_components.span, { className: "token string", children: "\"书标题 : %s\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " book", _jsx(_components.span, { className: "token punctuation", children: "." }), "title", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), " ", _jsx(_components.span, { className: "token string", children: "\"书作者 : %s\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " book", _jsx(_components.span, { className: "token punctuation", children: "." }), "author", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), " ", _jsx(_components.span, { className: "token string", children: "\"书类目 : %s\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " book", _jsx(_components.span, { className: "token punctuation", children: "." }), "subject", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), " ", _jsx(_components.span, { className: "token string", children: "\"书 ID : %d\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " book", _jsx(_components.span, { className: "token punctuation", children: "." }), "book_id", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: " \n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n"] }), "\n"] }), "\n", _jsxs(_components.h3, { id: "231-顺序表的初始化", children: [_jsx(_components.a, { className: "heading-link", href: "#231-顺序表的初始化", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.3.1 顺序表的初始化"] }), "\n", _jsxs(_components.details, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.summary, { "data-callout-title": true, children: "个人实现：" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsx(_components.p, {}), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "include" }), " ", _jsx(_components.span, { className: "token string", children: "" })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "include" }), " ", _jsx(_components.span, { className: "token string", children: "" })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "include" }), " ", _jsx(_components.span, { className: "token string", children: "" })] }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 静态分配大小" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "MaxSize" }), " ", _jsx(_components.span, { className: "token expression", children: _jsx(_components.span, { className: "token number", children: "50" }) })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 动态分配大小" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "InitSize" }), " ", _jsx(_components.span, { className: "token expression", children: _jsx(_components.span, { className: "token number", children: "100" }) })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "ElemType" }), " ", _jsx(_components.span, { className: "token expression", children: _jsx(_components.span, { className: "token keyword", children: "int" }) })] }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "enum" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "false", _jsx(_components.span, { className: "token punctuation", children: "," }), " true", _jsx(_components.span, { className: "token punctuation", children: "}" }), " bool", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "bool" }), " ", _jsx(_components.span, { className: "token expression", children: _jsx(_components.span, { className: "token keyword", children: "int" }) })] }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 静态分配定义" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "struct" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType data", _jsx(_components.span, { className: "token punctuation", children: "[" }), "MaxSize", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType length", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), " SeqList", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 动态分配定义" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "struct" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType ", _jsx(_components.span, { className: "token operator", children: "*" }), "data", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType MaxSizeDynamic", _jsx(_components.span, { className: "token punctuation", children: "," }), " length", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), " SeqListDynamic", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 静态初始化一个顺序表" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "void" }), " ", _jsx(_components.span, { className: "token function", children: "InitList" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "SeqList ", _jsx(_components.span, { className: "token operator", children: "*" }), "L", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "length ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 初始化顺序长度为 0" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 动态初始化一个顺序表" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "void" }), " ", _jsx(_components.span, { className: "token function", children: "InitListDynamic" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "SeqListDynamic ", _jsx(_components.span, { className: "token operator", children: "*" }), "L", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "data ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "ElemType ", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token function", children: "malloc" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "InitSize ", _jsx(_components.span, { className: "token operator", children: "*" }), " ", _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "ElemType", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 分配存储空间" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "length ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "MaxSizeDynamic ", _jsx(_components.span, { className: "token operator", children: "=" }), " InitSize", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 插入操作" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["bool ", _jsx(_components.span, { className: "token function", children: "ListInsert" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "SeqList ", _jsx(_components.span, { className: "token operator", children: "*" }), "L", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " i", _jsx(_components.span, { className: "token punctuation", children: "," }), " ElemType e", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "i ", _jsx(_components.span, { className: "token operator", children: "<" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "main" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" SeqList seq", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "InitList" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "seq", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 静态顺序表" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"=========== 输出静态顺序表初始化结果 ===========\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\">> 长度：%d\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " seq", _jsx(_components.span, { className: "token punctuation", children: "." }), "length", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\">> 数据data[0]：%d\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " seq", _jsx(_components.span, { className: "token punctuation", children: "." }), "data", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "puts" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 动态顺序表" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"=========== 输出动态顺序表初始化结果 ===========\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" SeqListDynamic seqDynamic", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "InitListDynamic" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "seqDynamic", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\">> 长度：%d\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " seqDynamic", _jsx(_components.span, { className: "token punctuation", children: "." }), "length", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\">> 长度上限：%d\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " seqDynamic", _jsx(_components.span, { className: "token punctuation", children: "." }), "MaxSizeDynamic", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\">> 数据data[0]：%d\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " seq", _jsx(_components.span, { className: "token punctuation", children: "." }), "data", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n"] }), "\n"] }), "\n", _jsx(_components.p, { children: "这是根据 wd 书写的一段顺序表的初始化 C 语言代码。" }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["要点在于 ", _jsx(_components.code, { className: "language-auto", children: "malloc()" }), " 函数的使用方法，为了使用 ", _jsx(_components.code, { className: "language-auto", children: "malloc()" }), " 别忘了引入 ", _jsx(_components.code, { className: "language-auto", children: "stdlib.h" }), "。"] }), "\n"] }), "\n", _jsxs(_components.h3, { id: "232-顺序表的插入操作", children: [_jsx(_components.a, { className: "heading-link", href: "#232-顺序表的插入操作", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.3.2 顺序表的插入操作"] }), "\n", _jsx(_components.p, { children: "这里我思考了一个从高中开始就思考过的一个问题：" }), "\n", _jsxs(_components.details, { "data-callout": true, "data-callout-type": "question", children: ["\n", _jsx(_components.summary, { "data-callout-title": true, children: "Little Confusion🤔" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsx(_components.p, { children: "在学习数据结构时，总是在数组下标和位序之间切换，我感觉很难受，老是需要在处理边界条件上花很久的时间，有没有什么好的直观的方法帮我解决这个问题，从而在每次思考这种边界处理时更快？" }), "\n", _jsxs(_components.div, { "data-callout": true, "data-callout-type": "success", children: ["\n", _jsx(_components.div, { "data-callout-title": true, children: "答：" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsxs(_components.p, { children: ["脑中一套体系，手上一次平移；边界画成格，逻辑自然齐。\n", _jsx(_components.strong, { children: "方法一" }), "：算法逻辑统一用 0-based\n", _jsx(_components.strong, { children: "方法二(Recommend)" }), "：算法逻辑全用 1-based 思考，写代码时再对所有下标整体平移，类似于 ", _jsx(_components.code, { className: "language-auto", children: "#define" }), " 的那种味道，这样就很直观了。\n对于边界问题，数格子不数点。"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.details, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.summary, { "data-callout-title": true, children: "个人实现如下：" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsx(_components.p, {}), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-C code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "include" }), " ", _jsx(_components.span, { className: "token string", children: "" })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "include" }), " ", _jsx(_components.span, { className: "token string", children: "" })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "include" }), " ", _jsx(_components.span, { className: "token string", children: "" })] }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 静态分配大小" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "MaxSize" }), " ", _jsx(_components.span, { className: "token expression", children: _jsx(_components.span, { className: "token number", children: "50" }) })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 线性表元素类型" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "ElemType" }), " ", _jsx(_components.span, { className: "token expression", children: _jsx(_components.span, { className: "token keyword", children: "int" }) })] }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "enum" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "false", _jsx(_components.span, { className: "token punctuation", children: "," }), " true", _jsx(_components.span, { className: "token punctuation", children: "}" }), " bool", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "bool" }), " ", _jsx(_components.span, { className: "token expression", children: _jsx(_components.span, { className: "token keyword", children: "int" }) })] }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 静态分配定义" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "struct" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType data", _jsx(_components.span, { className: "token punctuation", children: "[" }), "MaxSize", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType length", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), " SeqList", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 静态初始化一个顺序表" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "void" }), " ", _jsx(_components.span, { className: "token function", children: "InitList" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "SeqList ", _jsx(_components.span, { className: "token operator", children: "*" }), "L", _jsx(_components.span, { className: "token punctuation", children: ")" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "length ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 初始化顺序长度为 0" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token comment", children: "// 插入操作（这里为采用静态定义的线性表）" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["bool ", _jsx(_components.span, { className: "token function", children: "ListInsert" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "SeqList ", _jsx(_components.span, { className: "token operator", children: "*" }), "L", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " i", _jsx(_components.span, { className: "token punctuation", children: "," }), " ElemType e", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"Insert value: %d\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " e", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "i ", _jsx(_components.span, { className: "token operator", children: "<" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), " ", _jsx(_components.span, { className: "token operator", children: "||" }), " i ", _jsx(_components.span, { className: "token operator", children: ">" }), " L", _jsx(_components.span, { className: "token operator", children: "->" }), "length", _jsx(_components.span, { className: "token operator", children: "+" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"Insert Error: Invalid position!\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " false", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 插入到无效的位置" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), " ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "L", _jsx(_components.span, { className: "token operator", children: "->" }), "length ", _jsx(_components.span, { className: "token operator", children: ">=" }), " MaxSize", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"Insert Error: Space full!\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " false", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 已经将分配的空间用尽" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), " ", _jsx(_components.span, { className: "token keyword", children: "else" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " j ", _jsx(_components.span, { className: "token operator", children: "=" }), " L", _jsx(_components.span, { className: "token operator", children: "->" }), "length", _jsx(_components.span, { className: "token punctuation", children: ";" }), " j ", _jsx(_components.span, { className: "token operator", children: ">=" }), " i", _jsx(_components.span, { className: "token punctuation", children: ";" }), " j ", _jsx(_components.span, { className: "token operator", children: "--" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token punctuation", children: "[" }), "j", _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " L", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token punctuation", children: "[" }), "j", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), " ", _jsx(_components.span, { className: "token operator", children: "=" }), " e", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"Insert Successful!\\n\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "length", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " false", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "void" }), " ", _jsx(_components.span, { className: "token function", children: "logList" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "SeqList ", _jsx(_components.span, { className: "token operator", children: "*" }), "p", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"[ \"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "for" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "<" }), " p", _jsx(_components.span, { className: "token operator", children: "->" }), "length ", _jsx(_components.span, { className: "token operator", children: "-" }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " i ", _jsx(_components.span, { className: "token operator", children: "++" }), " ", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 默认认为是 int 类型，并格式化输出。" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"%d \"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " p", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token punctuation", children: "[" }), "i", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "puts" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"]\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsx(_components.span, { className: "code-line", children: "\n" }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "main" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" SeqList seq", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "InitList" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "seq", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 静态顺序表" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"=========== 输出静态顺序表初始化结果 ===========\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\">> 长度：%d\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " seq", _jsx(_components.span, { className: "token punctuation", children: "." }), "length", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "printf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\">> 数据data[0]：%d\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " seq", _jsx(_components.span, { className: "token punctuation", children: "." }), "data", _jsx(_components.span, { className: "token punctuation", children: "[" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "ListInsert" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "seq", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "33" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "ListInsert" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "seq", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "2" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "128" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "ListInsert" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "seq", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "3" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "999" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "ListInsert" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "seq", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "4" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token number", children: "190" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "logList" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token operator", children: "&" }), "seq", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "puts" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"You've successfully insert some values~\\n\"" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " ", _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n"] }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "发现考研的数据结构貌似侧重考察算法的思想，那么一轮暂时先不浪费时间去写代码了，先把知识点弄懂为要。" }), "\n"] }), "\n", _jsxs(_components.h2, { id: "23-线性表的链式表示", children: [_jsx(_components.a, { className: "heading-link", href: "#23-线性表的链式表示", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.3 线性表的链式表示"] }), "\n", _jsxs(_components.h3, { id: "231-单链表的定义", children: [_jsx(_components.a, { className: "heading-link", href: "#231-单链表的定义", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.3.1 单链表的定义"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "定义" }), "：线性表的链式存储也称", _jsx(_components.em, { children: "单链表" }), "。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "优点：" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "解决了顺序表需要大量连续存储单元的缺点。" }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "缺点" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "不能直接找到表中的某个特定结点，寻找特定结点时需要从表头开始遍历（没有索引这个概念了）。" }), "\n", _jsx(_components.li, { children: "附加的指针域浪费空间。" }), "\n", _jsxs(_components.li, { children: ["每个链表节点除了存放元素自身的信息外，还需要存放一个指向其后继的", _jsx(_components.em, { children: "指针" }), "（这里我们可以回忆一下顺序表的元素是只能存放单个元素的，有所不同）。"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.div, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.div, { "data-callout-title": true, children: "头结点与头指针" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsxs(_components.p, { children: ["用", _jsx(_components.em, { children: "头指针 L（或 head）" }), " 来标识一个单链表，指出链表的地址。\n头指针为 NULL 时表示一个空表。"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "带表头结点：头指针 L 指向头结点，头结点可以携带一些链表的信息（如链表长度）。" }), "\n", _jsx(_components.li, { children: "不带表头结点：头指针 L 指向第一个数据结点。" }), "\n", _jsx(_components.li, { children: "表尾结点：指针域为 NULL。" }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.div, { "data-callout": true, "data-callout-type": "question", children: ["\n", _jsx(_components.div, { "data-callout-title": true, children: "为什么要引入头结点？" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsx(_components.p, { children: "引入头结点主要是为了解决空链表的问题。引入头结点后空链表的头指针可以指向头指针，这在逻辑上就和非空链表完全一致了（实现了大一统），在处理上也得到了统一。" }), "\n"] }), "\n"] }), "\n", _jsx(_components.p, { children: "单链表的定义：" }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-C code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "LNode" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// 定义了结点的数据类型" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType data", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 数据域" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token class-name", children: "LNode" }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 指针域" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "LNode", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "*" }), "LinkList", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n", _jsxs(_components.h3, { id: "232-单链表上基本操作的实现", children: [_jsx(_components.a, { className: "heading-link", href: "#232-单链表上基本操作的实现", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.3.2 单链表上基本操作的实现"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "从这里开始均为 WD 书上代码的抄写了，难免会有打错，目的主要是为了通过输出带动自己过一遍。" }), "\n"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "单链表的初始化" }), "\n"] }), "\n", _jsx(_components.p, { children: "这是一个带头结点单链表的初始化，需要创建一个头结点，并让头指针指向头结点，头结点的 next 域初始化为 NULL。" }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-C code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["bool ", _jsx(_components.span, { className: "token function", children: "InitList" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LinkList ", _jsx(_components.span, { className: "token operator", children: "&" }), "L", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// 带头结点的单链表的初始化" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token function", children: "malloc" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 创建头结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 头结点之后暂时没有元素结点，此时头结点就是表尾结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsx(_components.p, { children: "不带头结点的单链表在初始化时，只需要将头指针 L 初始化为 NULL 就可以。" }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-C code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["bool ", _jsx(_components.span, { className: "token function", children: "InitList" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LinkList ", _jsx(_components.span, { className: "token operator", children: "&" }), "L", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["这里的 ", _jsx(_components.code, { className: "language-auto", children: "LinkList" }), " 就是头指针。\n书上 P 31 的 ", _jsx(_components.code, { className: "language-auto", children: "注意" }), " 部分就是一些简单的 C 语言指针语法，这里省略。"] }), "\n"] }), "\n", _jsxs(_components.ol, { start: "2", children: ["\n", _jsx(_components.li, { children: "求表长操作" }), "\n"] }), "\n", _jsx(_components.p, { children: "顾名思义，遍历链表求出表的长度。" }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "int" }), " ", _jsx(_components.span, { className: "token function", children: "Length" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LinkList L", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " len", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), "p", _jsx(_components.span, { className: "token operator", children: "=" }), "L", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "!=" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" p", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" len", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " len", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token comment", children: "// 这段代码简单，不过多说明（lazy）" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.ol, { start: "3", children: ["\n", _jsx(_components.li, { children: "按序号查找结点" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "按照序号搜索结点并返回该结点的指针；" }), "\n", _jsxs(_components.li, { children: ["如果 ", _jsx(_components.code, { className: "language-auto", children: "i" }), " 大于表长，则返回 NULL。"] }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token function", children: "GetElem" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LinkList L", _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), "p", _jsx(_components.span, { className: "token operator", children: "=" }), "L", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " j", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "p", _jsx(_components.span, { className: "token operator", children: "!=" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token operator", children: "&&" }), "j", _jsx(_components.span, { className: "token operator", children: "<" }), "i", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" p", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" j", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " p", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.ol, { start: "4", children: ["\n", _jsx(_components.li, { children: "按值查找表结点" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "从第一个结点开始，从前往后以此比较结点的数据域，若某结点的 data 域等于给定值 e，则返回该结点的指针；" }), "\n", _jsx(_components.li, { children: "若整个单链表中没有这样的结点，则返回 NULL。" }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token function", children: "LocateElem" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LinkList L", _jsx(_components.span, { className: "token punctuation", children: "," }), "ElemType e", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), "p", _jsx(_components.span, { className: "token operator", children: "=" }), "L", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "p", _jsx(_components.span, { className: "token operator", children: "!=" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token operator", children: "&&" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token operator", children: "!=" }), "e", _jsx(_components.span, { className: "token punctuation", children: ")" }), " p", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 从第一个结点开始查找数据域为e的结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " p", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 找到后返回指针否则返回NULL。" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.ol, { start: "5", children: ["\n", _jsx(_components.li, { children: "插入结点操作" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["将值为 x 的新结点插入到单链表的第 ", _jsx(_components.code, { className: "language-auto", children: "i" }), " 个位置。"] }), "\n", _jsxs(_components.li, { children: ["先检查插入位置的合法性，然后找到待插入位置的前驱，即第 ", _jsx(_components.code, { className: "language-auto", children: "i-1" }), " 个结点，再在其后插入。"] }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["bool ", _jsx(_components.span, { className: "token function", children: "ListInsert" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LinkList ", _jsx(_components.span, { className: "token operator", children: "&" }), "L", _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token keyword", children: "int" }), " i", _jsx(_components.span, { className: "token punctuation", children: "," }), "ElemType e", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), "p", _jsx(_components.span, { className: "token operator", children: "=" }), "L", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "//指针p指向当前扫描到的结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " j", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "//记录当前结点的位序，头结点是第0个结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "p", _jsx(_components.span, { className: "token operator", children: "!=" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token operator", children: "&&" }), "j", _jsx(_components.span, { className: "token operator", children: "<" }), "i", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "//循环找到第i-1个结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" p", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" j", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "p", _jsx(_components.span, { className: "token operator", children: "==" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " false", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// i值不合法" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), "s", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token function", children: "malloc" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" s", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token operator", children: "=" }), "e", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" s", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "s", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.div, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.div, { "data-callout-title": true, children: "后插法" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsxs(_components.p, { children: ["上面👆都是前插法，即插到目标结点的前面。前插法中通过找到目标结点的前一个结点来实现。而", _jsx(_components.strong, { children: "后插法" }), "直接找到目标结点并先插到其后面，然后通过交换目标结点和新插入的结点来实现，最终效果和前插法是一样的。"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["s", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "s", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 前两句和前插法一样" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["temp", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 交换数据" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["p", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token operator", children: "=" }), "s", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["s", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token operator", children: "=" }), "temp", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n"] }), "\n"] }), "\n", _jsxs(_components.ol, { start: "6", children: ["\n", _jsx(_components.li, { children: "删除结点操作" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["将单链表的第 ", _jsx(_components.code, { className: "language-auto", children: "i" }), " 个结点删除。"] }), "\n", _jsx(_components.li, { children: "先检查删除位置合法性。" }), "\n", _jsxs(_components.li, { children: ["然后查找 ", _jsx(_components.code, { className: "language-auto", children: "i-1" }), " 个结点，也就是被删结点的前驱。"] }), "\n", _jsxs(_components.li, { children: ["再删除第 ", _jsx(_components.code, { className: "language-auto", children: "i" }), " 个结点。"] }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "都很好理解，不过多赘述。" }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["bool ", _jsx(_components.span, { className: "token function", children: "ListDelete" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LinkList ", _jsx(_components.span, { className: "token operator", children: "&" }), "L", _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " i", _jsx(_components.span, { className: "token punctuation", children: "," }), "ElemType ", _jsx(_components.span, { className: "token operator", children: "&" }), "e", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), "p", _jsx(_components.span, { className: "token operator", children: "=" }), "L", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " j", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token number", children: "0" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "!=" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token operator", children: "&&" }), "j", _jsx(_components.span, { className: "token operator", children: "<" }), "i", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" p", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" j", _jsx(_components.span, { className: "token operator", children: "++" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "if" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "==" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token operator", children: "||" }), "j", _jsx(_components.span, { className: "token operator", children: ">" }), "i", _jsx(_components.span, { className: "token operator", children: "-" }), _jsx(_components.span, { className: "token number", children: "1" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token keyword", children: "return" }), " false", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// j>i-1是为了防御i<=0时的越界情况" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), "q", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 此时p是待删除结点的前驱，q是待删除结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" e", _jsx(_components.span, { className: "token operator", children: "=" }), "q", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "q", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "free" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "q", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " true", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.div, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.div, { "data-callout-title": true, children: "扩展（思想后插法）" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsx(_components.p, { children: "该方法类似于头插法，找到结点后在后部插入。" }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["q", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 此时已经用p指向待删除结点，q指向了待删结点后继" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["p", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 覆盖待删结点数据域" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "q", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 断开链接" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token function", children: "free" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "q", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 释放" }), "\n"] })] }) }), "\n"] }), "\n"] }), "\n", _jsxs(_components.ol, { start: "7", children: ["\n", _jsx(_components.li, { children: "采用头插法建立单链表" }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["使用头插法创建，输入的顺序和链表中结点的顺序相反。插入时头指针保持指向头结点，将新来的元素插到首个数据元素前面。所以我们可以这样去记忆头插法：", _jsx(_components.strong, { children: "利用头指针在头部插入元素，就叫做头插法" }), "。"] }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-C code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["LinkList ", _jsx(_components.span, { className: "token function", children: "List_HeadInsert" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LinkList ", _jsx(_components.span, { className: "token operator", children: "&" }), "L", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), "s", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token keyword", children: "int" }), " x", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L ", _jsx(_components.span, { className: "token operator", children: "=" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token function", children: "malloc" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 创建头结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 空链表" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "scanf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"%d\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "&" }), "x", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "x", _jsx(_components.span, { className: "token operator", children: "!=" }), _jsx(_components.span, { className: "token number", children: "9999" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), " ", _jsx(_components.span, { className: "token comment", children: "// 输入9999结束程序" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" s", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token function", children: "malloc" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 分配结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" s", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token operator", children: "=" }), "x", _jsx(_components.span, { className: "token punctuation", children: ";" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [" s", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "L", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 新结点链接到首个数据结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "s", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 头结点指向的一个数据元素" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "scanf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"%d\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "&" }), "x", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " L", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.ol, { start: "8", children: ["\n", _jsx(_components.li, { children: "采用尾插法建立单链表" }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsxs(_components.p, { children: ["为了保证结点次序与输入时一致可采用尾插法。记忆方式：", _jsx(_components.strong, { children: "利用尾指针在尾部插入新元素，就是尾插法" }), "。"] }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["LinkList ", _jsx(_components.span, { className: "token function", children: "List_TailInsert" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LinkList ", _jsx(_components.span, { className: "token operator", children: "&" }), "L", _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " x", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" L", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token function", children: "malloc" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 头结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), "s", _jsx(_components.span, { className: "token punctuation", children: "," }), _jsx(_components.span, { className: "token operator", children: "*" }), "r", _jsx(_components.span, { className: "token operator", children: "=" }), "L", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// r为尾指针，s用于指向新分配的结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "scanf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"%d\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "&" }), "x", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "while" }), " ", _jsx(_components.span, { className: "token punctuation", children: "(" }), "x", _jsx(_components.span, { className: "token operator", children: "!=" }), _jsx(_components.span, { className: "token number", children: "9999" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" s", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode ", _jsx(_components.span, { className: "token operator", children: "*" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token function", children: "malloc" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token keyword", children: "sizeof" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "LNode", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 创建新结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" s", _jsx(_components.span, { className: "token operator", children: "->" }), "data", _jsx(_components.span, { className: "token operator", children: "=" }), "x", _jsx(_components.span, { className: "token punctuation", children: ";" }), " \n"] }), _jsxs(_components.span, { className: "code-line", children: [" r", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "s", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 尾结点链接到新结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" r", _jsx(_components.span, { className: "token operator", children: "=" }), "s", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 更新尾结点" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token function", children: "scanf" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), _jsx(_components.span, { className: "token string", children: "\"%d\"" }), _jsx(_components.span, { className: "token punctuation", children: "," }), " ", _jsx(_components.span, { className: "token operator", children: "&" }), "x", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" r", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), _jsx(_components.span, { className: "token constant", children: "NULL" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 尾结点指向NULL表示尾部" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "return" }), " L", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), "\n"] })] }) }), "\n", _jsxs(_components.h3, { id: "233-双链表", children: [_jsx(_components.a, { className: "heading-link", href: "#233-双链表", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.3.3 双链表"] }), "\n", _jsx(_components.p, { children: "单链表只能往后，不能往前，为了克服，人类设计出了双链表。" }), "\n", _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "双链表的插入操作" }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["s", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 这一步必须在这里的第四步前面，因为需要使用p->next" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "->" }), "prior", _jsx(_components.span, { className: "token operator", children: "=" }), "s", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["s", _jsx(_components.span, { className: "token operator", children: "->" }), "prior", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "s", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n", _jsxs(_components.ol, { start: "2", children: ["\n", _jsx(_components.li, { children: "双链表的删除操作" }), "\n"] }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: ["p", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "=" }), "q", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: ["q", _jsx(_components.span, { className: "token operator", children: "->" }), "next", _jsx(_components.span, { className: "token operator", children: "->" }), "prior", _jsx(_components.span, { className: "token operator", children: "=" }), "p", _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token function", children: "free" }), _jsx(_components.span, { className: "token punctuation", children: "(" }), "q", _jsx(_components.span, { className: "token punctuation", children: ")" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n", _jsxs(_components.h3, { id: "234-循环链表", children: [_jsx(_components.a, { className: "heading-link", href: "#234-循环链表", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.3.4 循环链表"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "循环单链表" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "循环单链表的表中最后一个结点指向的不是 NULL 而是头结点，单链表自然成环了。" }), "\n", _jsx(_components.li, { children: "单链表的判空方式有所不同，当单链表的尾指针指向头结点时表示链表为空（注意区分头结点和第一个数据结点的概念）。" }), "\n", _jsx(_components.li, { children: "单链表只能从表头开始遍历，才能遍历完整张链表。而循环链表从任意位置开始都能够遍历完整张链表。" }), "\n", _jsxs(_components.li, { children: ["有时对循环单链表仅设尾指针而不设头指针。原因是单链表只能单向遍历，如果设置头指针想要遍历到尾部并插入需要 O(n)复杂度，而设置了尾指针想要遍历到头部只需要往前走一步(", _jsx(_components.code, { className: "language-auto", children: "r->next" }), ")即可 O(1)，同时也能很方便地插入到尾部。"] }), "\n"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "循环双链表" }), "\n"] }), "\n", _jsx(_components.p, { children: "和循环单链表类似。" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["链表头指针的 ", _jsx(_components.code, { className: "language-auto", children: "prior" }), " 还要指向尾结点。"] }), "\n", _jsxs(_components.li, { children: ["循环双链表为空表时，头结点 ", _jsx(_components.code, { className: "language-auto", children: "prior" }), " 域和 ", _jsx(_components.code, { className: "language-auto", children: "next" }), " 域都等于 L。"] }), "\n"] }), "\n", _jsxs(_components.ol, { start: "2", children: ["\n", _jsx(_components.li, { children: "静态链表" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "用数组来描述线性表的链式存储结构，唯一的区别时不需要指针了，将数组索引（按照王道书上说叫做数组的相对地址结构，数组下标）当作地址来用。" }), "\n", _jsx(_components.li, { children: "和顺序表一样，静态链表也需要预先分配一块连续的内存空间。" }), "\n", _jsxs(_components.li, { children: ["以 ", _jsx(_components.code, { className: "language-auto", children: "next==-1" }), " 作为链表结束的标志。"] }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "我个人非常喜欢静态链表这种优雅的写法，相对于计算机分配的地址而言，我认为数组相对索引对程序员来说更加可控。" }), "\n"] }), "\n", _jsx(_components.p, { children: "静态列表的结构类型描述：" }), "\n", _jsx(_components.pre, { className: "language-c", children: _jsxs(_components.code, { className: "language-c code-highlight", children: [_jsxs(_components.span, { className: "code-line", children: [_jsxs(_components.span, { className: "token macro property", children: [_jsx(_components.span, { className: "token directive-hash", children: "#" }), _jsx(_components.span, { className: "token directive keyword", children: "define" }), " ", _jsx(_components.span, { className: "token macro-name", children: "MaxSize" }), " ", _jsxs(_components.span, { className: "token expression", children: [_jsx(_components.span, { className: "token number", children: "50" }), " "] }), _jsx(_components.span, { className: "token comment", children: "// 静态链表的最大长度" })] }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token keyword", children: "typedef" }), " ", _jsx(_components.span, { className: "token keyword", children: "struct" }), " ", _jsx(_components.span, { className: "token punctuation", children: "{" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ElemType data", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 存储的数据元素" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [" ", _jsx(_components.span, { className: "token keyword", children: "int" }), " next", _jsx(_components.span, { className: "token punctuation", children: ";" }), " ", _jsx(_components.span, { className: "token comment", children: "// 下一个元素的数组下标" }), "\n"] }), _jsxs(_components.span, { className: "code-line", children: [_jsx(_components.span, { className: "token punctuation", children: "}" }), " SLinkList", _jsx(_components.span, { className: "token punctuation", children: "[" }), "MaxSize", _jsx(_components.span, { className: "token punctuation", children: "]" }), _jsx(_components.span, { className: "token punctuation", children: ";" }), "\n"] })] }) }), "\n", _jsxs(_components.h3, { id: "236-顺序表和链表的比较", children: [_jsx(_components.a, { className: "heading-link", href: "#236-顺序表和链表的比较", children: _jsx(_components.svg, { xmlns: "http:www.w3.org/2000/svg", fill: "#ab2b65", viewBox: "0 0 20 20", className: "w-5 h-5", children: _jsx(_components.path, { fillRule: "evenodd", clipRule: "evenodd", d: "M9.493 2.853a.75.75 0 00-1.486-.205L7.545 6H4.198a.75.75 0 000 1.5h3.14l-.69 5H3.302a.75.75 0 000 1.5h3.14l-.435 3.148a.75.75 0 001.486.205L7.955 14h2.986l-.434 3.148a.75.75 0 001.486.205L12.456 14h3.346a.75.75 0 000-1.5h-3.14l.69-5h3.346a.75.75 0 000-1.5h-3.14l.435-3.147a.75.75 0 00-1.486-.205L12.045 6H9.059l.434-3.147zM8.852 7.5l-.69 5h2.986l.69-5H8.852z" }) }) }), "2.3.6 顺序表和链表的比较"] }), "\n", _jsxs(_components.ol, { children: ["\n", _jsx(_components.li, { children: "存取方式（读/写方式）" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "顺序表" }), "既可以", _jsx(_components.em, { children: "顺序存取" }), "，也可以", _jsx(_components.em, { children: "随机存取" }), "。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "链表" }), "只能从表头开始依次", _jsx(_components.em, { children: "顺序存取" }), "。"] }), "\n"] }), "\n", _jsxs(_components.ol, { start: "2", children: ["\n", _jsx(_components.li, { children: "逻辑结构与物理结构" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["采用", _jsx(_components.strong, { children: "顺序存储" }), "：逻辑上相邻的元素，对应的物理存储位置也相邻。"] }), "\n", _jsxs(_components.li, { children: ["采用", _jsx(_components.strong, { children: "链式存储" }), "：逻辑上相邻的元素，物理存储位置不一定相邻。"] }), "\n"] }), "\n", _jsxs(_components.ol, { start: "3", children: ["\n", _jsx(_components.li, { children: "查找、插入和删除操作" }), "\n"] }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["对于", _jsx(_components.strong, { children: "按值" }), "查找：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "顺序表" }), "无序时，两者均为 ", _jsx(_components.code, { className: "language-auto", children: "O(n)" }), "；"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "顺序表" }), "有序时，采用折半查找时间复杂度为 ", _jsx(_components.code, { className: "language-auto", children: "O(log2n)" }), "；"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["对于", _jsx(_components.strong, { children: "按序号" }), "查找：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "顺序表" }), "支持随机访问，", _jsx(_components.code, { className: "language-auto", children: "O(1)" }), "；"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "链表" }), "的平均复杂度为 ", _jsx(_components.code, { className: "language-auto", children: "O(n)" }), "；"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["插入、删除操作：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "顺序表" }), "平均要移动半个表长元素。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "链表" }), "只需修改相关结点的指针域。"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsx(_components.p, { children: "4.空间分配" }), "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["顺序存储：", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "静态存储分配" }), "：一旦存储空间满就不能扩充，再加入新元素会导致内存溢出，因此需要预先分配足够的存储空间。分配的过大会导致后部大量闲置；分配过小又会造成溢出。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "动态存储分配" }), "：虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，如果内存中没有更大块的连续存储空间，则会导致分配失败。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["链表：", "\n", _jsxs(_components.ul, { children: ["\n", _jsx(_components.li, { children: "只要由空间就能分配，缺点是需要浪费数据域存放指针，存储密度低。" }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.div, { "data-callout": true, "data-callout-type": "note", children: ["\n", _jsx(_components.div, { "data-callout-title": true, children: "💭在实际中怎样选取存储结构呢？" }), "\n", _jsxs(_components.div, { "data-callout-body": true, children: ["\n", _jsx(_components.p, {}), "\n", _jsxs(_components.ol, { children: ["\n", _jsxs(_components.li, { children: ["基于存储的考虑", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["难以估计长度或规模时，", _jsx(_components.em, { children: _jsx(_components.strong, { children: "不宜采用顺序表" }) }), "；"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "链表" }), "不用实现估计存储规模，但链表存储密度低。"] }), "\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "链式存储结构" }), "的存储密度小于1。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["基于运算的考虑", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: [_jsx(_components.strong, { children: "顺序表" }), "按", _jsx(_components.em, { children: "序号" }), "访问 ", _jsxs(_components.span, { className: "katex", children: [_jsx(_components.span, { className: "katex-mathml", children: _jsx(_components.math, { xmlns: "http://www.w3.org/1998/Math/MathML", children: _jsxs(_components.semantics, { children: [_jsx(_components.mrow, { children: _jsxs(_components.msub, { children: [_jsx(_components.mi, { children: "a" }), _jsx(_components.mi, { children: "i" })] }) }), _jsx(_components.annotation, { encoding: "application/x-tex", children: "a_{i}" })] }) }) }), _jsx(_components.span, { className: "katex-html", "aria-hidden": "true", children: _jsxs(_components.span, { className: "base", children: [_jsx(_components.span, { className: "strut", style: { height: "0.5806em", verticalAlign: "-0.15em" } }), _jsxs(_components.span, { className: "mord", children: [_jsx(_components.span, { className: "mord mathnormal", children: "a" }), _jsx(_components.span, { className: "msupsub", children: _jsxs(_components.span, { className: "vlist-t vlist-t2", children: [_jsxs(_components.span, { className: "vlist-r", children: [_jsx(_components.span, { className: "vlist", style: { height: "0.3117em" }, children: _jsxs(_components.span, { style: { top: "-2.55em", marginLeft: "0em", marginRight: "0.05em" }, children: [_jsx(_components.span, { className: "pstrut", style: { height: "2.7em" } }), _jsx(_components.span, { className: "sizing reset-size6 size3 mtight", children: _jsx(_components.span, { className: "mord mtight", children: _jsx(_components.span, { className: "mord mathnormal mtight", children: "i" }) }) })] }) }), _jsx(_components.span, { className: "vlist-s", children: "" })] }), _jsx(_components.span, { className: "vlist-r", children: _jsx(_components.span, { className: "vlist", style: { height: "0.15em" }, children: _jsx(_components.span, {}) }) })] }) })] })] }) })] }), " 显然快得多。若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。"] }), "\n", _jsxs(_components.li, { children: ["当", _jsx(_components.em, { children: "数据元素信息量较大" }), "且", _jsx(_components.em, { children: "表较长" }), "时，进行插入、删除，显然链表更好。"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["基于环境的考虑", "\n", _jsxs(_components.ul, { children: ["\n", _jsxs(_components.li, { children: ["\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "顺序表" }), "容易实现，任何高级语言都有数组类型。"] }), "\n"] }), "\n", _jsxs(_components.li, { children: ["\n", _jsxs(_components.p, { children: [_jsx(_components.strong, { children: "链表" }), "操作基于指针，相对来讲前者简单。"] }), "\n"] }), "\n"] }), "\n"] }), "\n"] }), "\n", _jsxs(_components.blockquote, { children: ["\n", _jsx(_components.p, { children: "两者各有优劣，通常较稳定的表选择顺序存储，频繁插入、删除操作的线性表选择链式存储。" }), "\n"] }), "\n"] }), "\n"] })] }); } function MDXContent(props = {}) { const {wrapper: MDXLayout} = { ..._provideComponents(), ...props.components }; return MDXLayout ? _jsx(MDXLayout, { ...props, children: _jsx(_createMdxContent, { ...props }) }) : _createMdxContent(props); } return { default: MDXContent };