数据结构

数据结构（英语：data structure）是计算机中存储、组织数据的方式。

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素集合。它包含三方面的内容，逻辑关系、存储关系及操作。

不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，计算机网络依赖于路由表运作，B 树高度适用于数据库的封装。

数据： 数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合的统称。 数据项： 时数据元素中独立含义的、不可分割的最小标识单位。如描述学生相关信息的姓名、性别、学号等都是数据项 数据元素： 表示一个事物的一组数据。如一条描述一位学生的完整信息的数据记录就是一个数据元素； 数据对象： 数据对象是性质相同的数据元素的集合，是数据的子集。如一个学校的所有学生的集合就是数据对象，空间中所有点的结合也是数据对象。 关键字： 一个数据元素中，能够识别该元素的一个或多个数据项 主关键字： 能够唯一识别数据元素的关键字 结点： 存储一个数据元素的存储单元称为结点，一个结点至少包括：数据域存储数据元素；地址域(也称链)存储前驱或后继元素地址

---

常见的数据结构

栈（Stack）: 栈是一种特殊的线代表，它只能在一个表的一个固定端进行数据节点的插入和删除操作。队列（Queue）：队列和栈类似，也是一种特殊的线代表。和栈不同的是，队列只允许在表的一段进行插入操作，而在另一端进行删除操作。数组（Array）： 数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。链表（Linked List）：链表是一种数据元素按照链式存储结构的数据结构，这种存储结构具有物理上存在非连续的特点。树（Tree）：树是典型的非线性结构，它是包括，2个结点的有穷集合K。图（Graph）：图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。堆（Heap）：堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。散列表（Hash Table）： 散列表源自散列函数（Hash function），其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行操作而直接取得所查记录。

数据结构分类

#mermaid-svg-yKQF1rkQFAlPSTPG .label{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);fill:#333;color:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .label text{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .node rect,#mermaid-svg-yKQF1rkQFAlPSTPG .node circle,#mermaid-svg-yKQF1rkQFAlPSTPG .node ellipse,#mermaid-svg-yKQF1rkQFAlPSTPG .node polygon,#mermaid-svg-yKQF1rkQFAlPSTPG .node path{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-yKQF1rkQFAlPSTPG .node .label{text-align:center;fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .node.clickable{cursor:pointer}#mermaid-svg-yKQF1rkQFAlPSTPG .arrowheadPath{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .edgePath .path{stroke:#333;stroke-width:1.5px}#mermaid-svg-yKQF1rkQFAlPSTPG .flowchart-link{stroke:#333;fill:none}#mermaid-svg-yKQF1rkQFAlPSTPG .edgeLabel{background-color:#e8e8e8;text-align:center}#mermaid-svg-yKQF1rkQFAlPSTPG .edgeLabel rect{opacity:0.9}#mermaid-svg-yKQF1rkQFAlPSTPG .edgeLabel span{color:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .cluster rect{fill:#ffffde;stroke:#aa3;stroke-width:1px}#mermaid-svg-yKQF1rkQFAlPSTPG .cluster text{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:12px;background:#ffffde;border:1px solid #aa3;border-radius:2px;pointer-events:none;z-index:100}#mermaid-svg-yKQF1rkQFAlPSTPG .actor{stroke:#ccf;fill:#ECECFF}#mermaid-svg-yKQF1rkQFAlPSTPG text.actor>tspan{fill:#000;stroke:none}#mermaid-svg-yKQF1rkQFAlPSTPG .actor-line{stroke:grey}#mermaid-svg-yKQF1rkQFAlPSTPG .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .messageLine1{stroke-width:1.5;stroke-dasharray:2, 2;stroke:#333}#mermaid-svg-yKQF1rkQFAlPSTPG #arrowhead path{fill:#333;stroke:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .sequenceNumber{fill:#fff}#mermaid-svg-yKQF1rkQFAlPSTPG #sequencenumber{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG #crosshead path{fill:#333;stroke:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .messageText{fill:#333;stroke:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .labelBox{stroke:#ccf;fill:#ECECFF}#mermaid-svg-yKQF1rkQFAlPSTPG .labelText,#mermaid-svg-yKQF1rkQFAlPSTPG .labelText>tspan{fill:#000;stroke:none}#mermaid-svg-yKQF1rkQFAlPSTPG .loopText,#mermaid-svg-yKQF1rkQFAlPSTPG .loopText>tspan{fill:#000;stroke:none}#mermaid-svg-yKQF1rkQFAlPSTPG .loopLine{stroke-width:2px;stroke-dasharray:2, 2;stroke:#ccf;fill:#ccf}#mermaid-svg-yKQF1rkQFAlPSTPG .note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-yKQF1rkQFAlPSTPG .noteText,#mermaid-svg-yKQF1rkQFAlPSTPG .noteText>tspan{fill:#000;stroke:none}#mermaid-svg-yKQF1rkQFAlPSTPG .activation0{fill:#f4f4f4;stroke:#666}#mermaid-svg-yKQF1rkQFAlPSTPG .activation1{fill:#f4f4f4;stroke:#666}#mermaid-svg-yKQF1rkQFAlPSTPG .activation2{fill:#f4f4f4;stroke:#666}#mermaid-svg-yKQF1rkQFAlPSTPG .mermaid-main-font{font-family:"trebuchet ms", verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG .section{stroke:none;opacity:0.2}#mermaid-svg-yKQF1rkQFAlPSTPG .section0{fill:rgba(102,102,255,0.49)}#mermaid-svg-yKQF1rkQFAlPSTPG .section2{fill:#fff400}#mermaid-svg-yKQF1rkQFAlPSTPG .section1,#mermaid-svg-yKQF1rkQFAlPSTPG .section3{fill:#fff;opacity:0.2}#mermaid-svg-yKQF1rkQFAlPSTPG .sectionTitle0{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .sectionTitle1{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .sectionTitle2{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .sectionTitle3{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .sectionTitle{text-anchor:start;font-size:11px;text-height:14px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG .grid .tick{stroke:#d3d3d3;opacity:0.8;shape-rendering:crispEdges}#mermaid-svg-yKQF1rkQFAlPSTPG .grid .tick text{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG .grid path{stroke-width:0}#mermaid-svg-yKQF1rkQFAlPSTPG .today{fill:none;stroke:red;stroke-width:2px}#mermaid-svg-yKQF1rkQFAlPSTPG .task{stroke-width:2}#mermaid-svg-yKQF1rkQFAlPSTPG .taskText{text-anchor:middle;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG .taskText:not([font-size]){font-size:11px}#mermaid-svg-yKQF1rkQFAlPSTPG .taskTextOutsideRight{fill:#000;text-anchor:start;font-size:11px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG .taskTextOutsideLeft{fill:#000;text-anchor:end;font-size:11px}#mermaid-svg-yKQF1rkQFAlPSTPG .task.clickable{cursor:pointer}#mermaid-svg-yKQF1rkQFAlPSTPG .taskText.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-yKQF1rkQFAlPSTPG .taskTextOutsideLeft.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-yKQF1rkQFAlPSTPG .taskTextOutsideRight.clickable{cursor:pointer;fill:#003163 !important;font-weight:bold}#mermaid-svg-yKQF1rkQFAlPSTPG .taskText0,#mermaid-svg-yKQF1rkQFAlPSTPG .taskText1,#mermaid-svg-yKQF1rkQFAlPSTPG .taskText2,#mermaid-svg-yKQF1rkQFAlPSTPG .taskText3{fill:#fff}#mermaid-svg-yKQF1rkQFAlPSTPG .task0,#mermaid-svg-yKQF1rkQFAlPSTPG .task1,#mermaid-svg-yKQF1rkQFAlPSTPG .task2,#mermaid-svg-yKQF1rkQFAlPSTPG .task3{fill:#8a90dd;stroke:#534fbc}#mermaid-svg-yKQF1rkQFAlPSTPG .taskTextOutside0,#mermaid-svg-yKQF1rkQFAlPSTPG .taskTextOutside2{fill:#000}#mermaid-svg-yKQF1rkQFAlPSTPG .taskTextOutside1,#mermaid-svg-yKQF1rkQFAlPSTPG .taskTextOutside3{fill:#000}#mermaid-svg-yKQF1rkQFAlPSTPG .active0,#mermaid-svg-yKQF1rkQFAlPSTPG .active1,#mermaid-svg-yKQF1rkQFAlPSTPG .active2,#mermaid-svg-yKQF1rkQFAlPSTPG .active3{fill:#bfc7ff;stroke:#534fbc}#mermaid-svg-yKQF1rkQFAlPSTPG .activeText0,#mermaid-svg-yKQF1rkQFAlPSTPG .activeText1,#mermaid-svg-yKQF1rkQFAlPSTPG .activeText2,#mermaid-svg-yKQF1rkQFAlPSTPG .activeText3{fill:#000 !important}#mermaid-svg-yKQF1rkQFAlPSTPG .done0,#mermaid-svg-yKQF1rkQFAlPSTPG .done1,#mermaid-svg-yKQF1rkQFAlPSTPG .done2,#mermaid-svg-yKQF1rkQFAlPSTPG .done3{stroke:grey;fill:#d3d3d3;stroke-width:2}#mermaid-svg-yKQF1rkQFAlPSTPG .doneText0,#mermaid-svg-yKQF1rkQFAlPSTPG .doneText1,#mermaid-svg-yKQF1rkQFAlPSTPG .doneText2,#mermaid-svg-yKQF1rkQFAlPSTPG .doneText3{fill:#000 !important}#mermaid-svg-yKQF1rkQFAlPSTPG .crit0,#mermaid-svg-yKQF1rkQFAlPSTPG .crit1,#mermaid-svg-yKQF1rkQFAlPSTPG .crit2,#mermaid-svg-yKQF1rkQFAlPSTPG .crit3{stroke:#f88;fill:red;stroke-width:2}#mermaid-svg-yKQF1rkQFAlPSTPG .activeCrit0,#mermaid-svg-yKQF1rkQFAlPSTPG .activeCrit1,#mermaid-svg-yKQF1rkQFAlPSTPG .activeCrit2,#mermaid-svg-yKQF1rkQFAlPSTPG .activeCrit3{stroke:#f88;fill:#bfc7ff;stroke-width:2}#mermaid-svg-yKQF1rkQFAlPSTPG .doneCrit0,#mermaid-svg-yKQF1rkQFAlPSTPG .doneCrit1,#mermaid-svg-yKQF1rkQFAlPSTPG .doneCrit2,#mermaid-svg-yKQF1rkQFAlPSTPG .doneCrit3{stroke:#f88;fill:#d3d3d3;stroke-width:2;cursor:pointer;shape-rendering:crispEdges}#mermaid-svg-yKQF1rkQFAlPSTPG .milestone{transform:rotate(45deg) scale(0.8, 0.8)}#mermaid-svg-yKQF1rkQFAlPSTPG .milestoneText{font-style:italic}#mermaid-svg-yKQF1rkQFAlPSTPG .doneCritText0,#mermaid-svg-yKQF1rkQFAlPSTPG .doneCritText1,#mermaid-svg-yKQF1rkQFAlPSTPG .doneCritText2,#mermaid-svg-yKQF1rkQFAlPSTPG .doneCritText3{fill:#000 !important}#mermaid-svg-yKQF1rkQFAlPSTPG .activeCritText0,#mermaid-svg-yKQF1rkQFAlPSTPG .activeCritText1,#mermaid-svg-yKQF1rkQFAlPSTPG .activeCritText2,#mermaid-svg-yKQF1rkQFAlPSTPG .activeCritText3{fill:#000 !important}#mermaid-svg-yKQF1rkQFAlPSTPG .titleText{text-anchor:middle;font-size:18px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG g.classGroup text{fill:#9370db;stroke:none;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family);font-size:10px}#mermaid-svg-yKQF1rkQFAlPSTPG g.classGroup text .title{font-weight:bolder}#mermaid-svg-yKQF1rkQFAlPSTPG g.clickable{cursor:pointer}#mermaid-svg-yKQF1rkQFAlPSTPG g.classGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-yKQF1rkQFAlPSTPG g.classGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG .classLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.5}#mermaid-svg-yKQF1rkQFAlPSTPG .classLabel .label{fill:#9370db;font-size:10px}#mermaid-svg-yKQF1rkQFAlPSTPG .relation{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-yKQF1rkQFAlPSTPG .dashed-line{stroke-dasharray:3}#mermaid-svg-yKQF1rkQFAlPSTPG #compositionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG #compositionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG #aggregationStart{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG #aggregationEnd{fill:#ECECFF;stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG #dependencyStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG #dependencyEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG #extensionStart{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG #extensionEnd{fill:#9370db;stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG .commit-id,#mermaid-svg-yKQF1rkQFAlPSTPG .commit-msg,#mermaid-svg-yKQF1rkQFAlPSTPG .branch-label{fill:lightgrey;color:lightgrey;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG .pieTitleText{text-anchor:middle;font-size:25px;fill:#000;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG .slice{font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG g.stateGroup text{fill:#9370db;stroke:none;font-size:10px;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG g.stateGroup text{fill:#9370db;fill:#333;stroke:none;font-size:10px}#mermaid-svg-yKQF1rkQFAlPSTPG g.statediagram-cluster .cluster-label text{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG g.stateGroup .state-title{font-weight:bolder;fill:#000}#mermaid-svg-yKQF1rkQFAlPSTPG g.stateGroup rect{fill:#ECECFF;stroke:#9370db}#mermaid-svg-yKQF1rkQFAlPSTPG g.stateGroup line{stroke:#9370db;stroke-width:1}#mermaid-svg-yKQF1rkQFAlPSTPG .transition{stroke:#9370db;stroke-width:1;fill:none}#mermaid-svg-yKQF1rkQFAlPSTPG .stateGroup .composit{fill:white;border-bottom:1px}#mermaid-svg-yKQF1rkQFAlPSTPG .stateGroup .alt-composit{fill:#e0e0e0;border-bottom:1px}#mermaid-svg-yKQF1rkQFAlPSTPG .state-note{stroke:#aa3;fill:#fff5ad}#mermaid-svg-yKQF1rkQFAlPSTPG .state-note text{fill:black;stroke:none;font-size:10px}#mermaid-svg-yKQF1rkQFAlPSTPG .stateLabel .box{stroke:none;stroke-width:0;fill:#ECECFF;opacity:0.7}#mermaid-svg-yKQF1rkQFAlPSTPG .edgeLabel text{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .stateLabel text{fill:#000;font-size:10px;font-weight:bold;font-family:'trebuchet ms', verdana, arial;font-family:var(--mermaid-font-family)}#mermaid-svg-yKQF1rkQFAlPSTPG .node circle.state-start{fill:black;stroke:black}#mermaid-svg-yKQF1rkQFAlPSTPG .node circle.state-end{fill:black;stroke:white;stroke-width:1.5}#mermaid-svg-yKQF1rkQFAlPSTPG #statediagram-barbEnd{fill:#9370db}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-cluster rect{fill:#ECECFF;stroke:#9370db;stroke-width:1px}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-cluster rect.outer{rx:5px;ry:5px}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-state .divider{stroke:#9370db}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-state .title-state{rx:5px;ry:5px}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-cluster.statediagram-cluster .inner{fill:white}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-cluster.statediagram-cluster-alt .inner{fill:#e0e0e0}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-cluster .inner{rx:0;ry:0}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-state rect.basic{rx:5px;ry:5px}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-state rect.divider{stroke-dasharray:10,10;fill:#efefef}#mermaid-svg-yKQF1rkQFAlPSTPG .note-edge{stroke-dasharray:5}#mermaid-svg-yKQF1rkQFAlPSTPG .statediagram-note rect{fill:#fff5ad;stroke:#aa3;stroke-width:1px;rx:0;ry:0}:root{--mermaid-font-family: '"trebuchet ms", verdana, arial';--mermaid-font-family: "Comic Sans MS", "Comic Sans", cursive}#mermaid-svg-yKQF1rkQFAlPSTPG .error-icon{fill:#522}#mermaid-svg-yKQF1rkQFAlPSTPG .error-text{fill:#522;stroke:#522}#mermaid-svg-yKQF1rkQFAlPSTPG .edge-thickness-normal{stroke-width:2px}#mermaid-svg-yKQF1rkQFAlPSTPG .edge-thickness-thick{stroke-width:3.5px}#mermaid-svg-yKQF1rkQFAlPSTPG .edge-pattern-solid{stroke-dasharray:0}#mermaid-svg-yKQF1rkQFAlPSTPG .edge-pattern-dashed{stroke-dasharray:3}#mermaid-svg-yKQF1rkQFAlPSTPG .edge-pattern-dotted{stroke-dasharray:2}#mermaid-svg-yKQF1rkQFAlPSTPG .marker{fill:#333}#mermaid-svg-yKQF1rkQFAlPSTPG .marker.cross{stroke:#333} :root { --mermaid-font-family: "trebuchet ms", verdana, arial;} #mermaid-svg-yKQF1rkQFAlPSTPG { color: rgba(0, 0, 0, 0.75); font: ; } 数据结构 逻辑结构 存储结构 线性结构 非线性结构 线性表 栈 队列 串及数组 树形结构 图形结构 顺序存储 链式存储 索引存储 散列存储

数据的存储结构：

数据的存储结构主要包括数据元素本身的存储以及数据元素之间关系表示，是数据的逻辑结构在计算机中的表示。

顺序存储结构： 把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，节点之间的逻辑关系由存储单元的邻接关系来体现。 优点：是节省存储空间，因为分配给数据的存储单元全用存放节点的数据，节点之间的逻辑关系没有占用额外的存储空间。缺点： 插入和删除操作需要移动元素，效率低 链式存储结构：数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。 每个结点室友数据域和指针域组成。元素之间的逻辑关系通过存储结点之间的链接关系反映出来。 特点： 比顺序存储结构的存储密度小逻辑上相邻的结点物理上不比相邻插入、删除灵活(不必移动节点，只要改变节点中的指针)查找节点时链式存储要比顺序存储慢 索引存储结构： 除建立存储节点信息外，还建立附加的索引表示来标识节点的地址。比如：图书、字典的目录。散列存储结构：根据节点的关键字直接计算出该节点的存储地址

---

算法

是指令的集合，是为解决特定问题而规定的一系列操作。 它是明确定义的可计算过程，以一个数据集合作为输入，并产生一个数据结合作为输出。

特点：

输入：一个算法应以待解决的问题的信息作为输入。输出：输入对应指令集处理后得到的信息。可行性：算法是可行的，即算法中的每一条指令都是可以实现的，均能在有限的时间内完成。有穷性：算法执行的指令个数是有限的，每个指令又是在有限时间内完成，因此整个算法也是在有限时间内可以结束的。确定性：算法对于特定的合法输入，其对应的输出是唯一的。即当算法从一个特定输入开始，多次执行同一指令集结果总是相同的。

常用算法

数据结构研究的内容：就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。

检索： 检索就是在数据结构李查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值得节点。插入： 往数据结构中增加新的节点。删除： 把指定的结点从数据结构中去掉。更新： 改变指定节点的一个或多个字段的值。排序： 把节点按某种指定的顺序重新排列。例如递增或递减。

时间复杂度(Time Complexity)

指算法的执行时间随问题规模的增长而增长的趋势

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)= O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

最坏时间复杂度和平均时间复杂度：

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。 在最坏情况下的时间复杂度为T(n)=O(n)，它表示对于任何输入实例，该算法的运行时间不可能大于O(n)。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

难计算有很多算法的平均情况和最差情况的复杂度是一样的

所以一般讨论最坏时间复杂度

为了经一部说明算法的时间复杂度，定义了O、Ω、Θ符号

最坏时间复杂度，T(n) = O(n^2)最好时间复杂度，T(n) = Ω(n^2)平均时间复杂度，T(n) = Θ(n^2)

时间复杂度计算

根本没有必要计算时间频度，即使计算处理还要忽略常量、低次幂和最高次幂的系数，所以可以采用如下简单方法；

找出算法中的基本语句 算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。 计算基本语句的执行次数的数量级 只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。 用大O符号表示算法的时间性能 将基本语句执行次数的数量级放入大O符号中。

常见的时间复杂度级别

常数阶O(1)对数阶O(log₂n)线性阶O(n)线性对数阶O(n*log₂n)平方价O(n²)

空间复杂度（Space Complexity）

算法的存储量包括：

程序本身所占空间输入数据所占空间辅助变量所占空间

输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作： S(n) = O(g(n))

int fun(int n){ //n为问题规模 int i, j, k, s; s = 0; for(i=0; i<=n; i++){ for(j=0; j<=i; j++){ for(k=0; k<=j; k++){ s++; } } } return(s); }

无论问题规模怎么变，算法运行所需的内存空间都是固定的常量，算法空间复杂度为: S(n) = O(1)

---

线性表

线性表是n个类型相同数据元素组成的有限序列，通常记作(a0，a1，a2…，an-1)

相同数据类型 可以看到从a0到an-1的n个数据元素是具有相同属性的元素相同数据类型意味着在内存中存储时，每个元素会占用相同的内存空间，便于后续的查询定位 序列（顺序性） 在线性表的相邻数据元素之间存在着序偶关系即ai-1是ai的直接前驱，a i是a i-1的直接后续除了表头和表尾元素外，任何一个元素都有切仅有一个直接前驱和直接后续。 有限 线性表中数据元素的个数n定义为线性表的长度，即n是一个有限值。

线性表的存储结构

顺序表——顺序存储结构 数组：存储具有相同数据类型的元素集合。顺序表： 线性表的顺序存储结构称为顺序表。优点： 节省存储空间，因为分配给数据的存储单元全用存放结点的数据，结点之间的逻辑关系没有占用额外的存储空间。索引查找效率高，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。 缺点： 插入和删除操作需要移动元素，效率较低。必须提前分配固定数量的空间，如果存储元素少，可能导致空闲浪费。按照内容查询效率低，因为需要逐个比较判断 线性链表——链式存储结构 数据元素的存储对应的是不连续的存储空间，每个存储结点对应一个需要存储的数据元素。每个结点只有一个地址域的线性链表称为单链表 链表的第一个及结点和最后一个结点，分别称为链表的首节点和尾结点单链表的一个重要特性就是只能通过前驱结点找到后续结点，而无法从后续结点找到前驱结点 。 在单链表进行查找操作，只能从链表的首节点开始，通过每个结点的next引用来一次访问链表中的每个结点以完成相应的查找操作 单链表中结点的存储空间是在插入和删除过程中动态申请和释放的，不需要预先给单链表分配存储空间，从而避免了顺序表因存储空间不足需要扩充空间和复制元素的过程，提高了运行效率和存储空间的利用率。为了使程序更加简洁，通常在单链表的最前面添加一个哑元结点，也称为头结点（head）。 在头结点中不存储任何实质的数据对象，其next域指向线性表中0号元素所在的结点， 可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便空单链表的头指针head为null，一条单链表最后一个结点的地址域为null，表示其后不再有结点。

顺序表的实现

// 线性表接口 public interface List{ //返回线性表的大小，即数据元素的个数 public int size(); //返回线性表中序号为i的数据元素 public Object get(int i); //如果线性表为空返回true，否则返回false public boolean isEmpry(); //判断线性表是否包含数据元素e public boolean contains(Object e); //返回数据元素e在线性表中的序号 public int indexOf(Object e); //将数据元素e插入到线性表中i号位置 public void add(int i, Object e); //将数据元素e插入到线性表末尾 public void add(Object e); //将数据元素e插入到元素obj之前 public boolean addBefore(Object obj, Object e); //将数据元素e插入到元素obj之后 public boolean addAfter(Object obj, Object e); //删除线性表中序号为i的元素，并返回之 public Object remove(int i); //删除线性表中第一个与e 相同的元素 public boolean remove(Object e); //替换线性表中序号为i的数据元素为e，返回原数据元素 public Object replace(int i, Object e); } public class ArrayList implements List{ private Object[] elementData; //对象数组存储顺序表的数据元素，保护成员 private int size; // 顺序表元素个数（长度） public ArrayList() { // TODO Auto-generated constructor stub this(4); //elementData = new Object[] {}; } public ArrayList(int initialCapacity) { //给数组分配指定数量的空间 elementData = new Object[initialCapacity]; //指定顺序表的元素个数，默认是0 //size=0; } @Override public int size() { // TODO Auto-generated method stub return this.size; } @Override public Object get(int i) { // TODO Auto-generated method stub if (i>=0 && i<size) { return this.elementData[i]; }else { return null; } } @Override public boolean isEmpry() { // TODO Auto-generated method stub return size == 0; } @Override public boolean contains(Object e) { // TODO Auto-generated method stub return false; } @Override public int indexOf(Object e) { // TODO Auto-generated method stub return 0; } @Override public void add(int i, Object e) { // TODO Auto-generated method stub if(size == elementData.length) { elementData = Arrays.copyOf(elementData, elementData.length*2); } //后移i以及其后元素，从最后一个元素开始 for(int j=size; j<i; j--) { elementData[j] = elementData[j-1]; } //给数组第i个位置赋值 elementData[i] = 0; size++; } @Override public void add(Object e) { this.add(size, e); // //数组满了，就扩容 // if(size == elementData.length) { // elementData = Arrays.copyOf(elementData, elementData.length*2); // } // // //给数组赋值 // elementData[size] = e; // size++; } @Override public boolean addBefore(Object obj, Object e) { // TODO Auto-generated method stub return false; } @Override public boolean addAfter(Object obj, Object e) { // TODO Auto-generated method stub return false; } @Override public Object remove(int i) { // TODO Auto-generated method stub return null; } @Override public boolean remove(Object e) { // TODO Auto-generated method stub return false; } @Override public Object replace(int i, Object e) { // TODO Auto-generated method stub return null; } }

单链表的实现

栈

栈是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。（后进先出）允许操作的一端称为栈顶（Top），不允许操作的一端称为栈底（Bottom）。栈中插入元素的操作称为入栈（push），删除元素的操作称为（Pop）。没有元素的栈称为空栈。采用顺序栈存储结构的栈称为顺序栈（Sequential Stack）。采用链式结构存储的栈称为链式栈（Linked Stack）。

队列

队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。向队列中插入元素的过程称为入队（Enqueue），删除元素的过程称为出队（Dequeue）。允许入队的一段称为队尾（Rear），允许出队的一段称为队头（Front）。没有元素的队列称为空队列。

---

未完待续