1． 数据（data）
数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。例如：数字、字母、汉字、图形、图像、声音都称为数据。
2．数据元素（data element）
数据元素是组成数据的基本单位。
数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位。
4 ．数据结构（data structure）
是指相互之间存在一种或多种特定关系的数据元素所组成的集合。具体来说，数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算。数据之间的相互关系称为逻辑结构
数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。
数据结构从逻辑结构角度通常分为四类基本结构：
一、集合结构中的数据元素除了同属于一种类型
外，别无其它关系。
二、线性结构结构中的数据元素之间存在一对一。
的关系。三、树型结构结构中的数据元素之间存在一对。
多的关系。四、图状结构或网状结构结构中的数据元素之间。
存在多对多的关系。
数据结构在计算机中有两种不同的表示方法：
顺序表示和非顺序表示
由此得出两种不同的存储结构：
顺序存储结构和链式存储结构
顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
链式存储结构：在每一个数据元素中增加一个存放地址的指针（pointer ），用此指针来表示数据元素之间的逻辑关系。
算法是对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。
算法具有以下五个特性：
1）有穷性
2）确定性
3）可行性
4）输入 5）输出
1.4.2 算法设计的要求
评价一个好的算法有以下几个标准：
1) 正确性(correctness ) 算法应满足具体问题的需求。
2)可读性(readability) 算法应该好读。以有利于阅读者对程序的理解。
(3)健状性(robustness) 算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果。
4)效率与存储量需求效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般，这两者与问题的规模有关。
线性结构：
线性结构是具有以下特点的数据结构：
1）存在唯一的一个被称作“第一个”的数据元素；
2）存在唯一的一个被称作“最后一个”的数据元素；
3）除第一个外，集合中的每个数据元素均有且只有一个直接前趋；
4）除最后一个外，集合中的每个数据元素均有且只有一个直接后继。
线性表、栈、队列、串都是线性结构。
一、概念：
1．线性表：线性表是n个数据元素的有限序列。
2．线性表的长度：线性表中数据元素的个数n（n≥0）称
为线性表的长度。
3．空表：长度为0的线性表称为空表。
4．位序：在非空数据表中数据元素ai是第i个数据元素，
称i为数据元素ai**性表中的位序。
线性表中每个数据元素的具体含义，在不同情况下各不相同，但是同一线性表中的元素必定具有相同特性，即属同一数据对象，相邻数据元素之间存在序偶关系。
二．顺序表的特点：
以元素在计算机内的“物理位置”来表示线性表中数据元素之间的逻辑关系，也就是存储位置相邻的数据元素就是逻辑关系相邻的数据元素。
由以上式子可看到，顺序表中每个数据元素的存储位置和顺序表的起始位置相差一个和数据元素**性表中的位序成正比的常数，所以只要确定了起始位置，表中任一个数据元素可以随机存取，所以顺序结构是一种随机存取的存储结构。
2．3线性表的链式表示和实现。
顺序存储结构：
优点：可以随机存取表中任意元素。
缺点：在插入、删除元素时，需要大量移动元素。
链式存储结构
优点：在插入、删除元素时，不需要移动元素。
缺点：不能随机存取。
一、线性链表：
1.特点：
线性表的链式存储结构的特点是用一组任意的存储单元（可连续或不连续）存储线性表的数据元素。
5）线性链表（单链表）：
由于上述由n个结点链接成的一个链表中的每个结点中只包含一个指针域，故又称作线性链表或单链表。
6）头指针：
线性链表中，头指针指示链表的第一个结点（即第一个数据元素的存储映像）的存储位置。
7）头结点：
有时我们在单链表的第一个结点之前附设一个结点，称之为头结点。着重讨论带头结点的链表。
8）非顺序存储结构或链式映像：
用链表表示数据结构时，数据间的逻辑关系是由结点中的指针指示的，这种存储结构称为非顺序存储结构或链式映像。
即：指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储位置不要求紧邻。
链表和顺序存储结构不同，它是一种动态结构。整个可用存储空间可为多个链表共享，每个链表占用的空间不虚预先分配划定，而是可由系统需求即时生成。所以，建立链表的过程就是一个动态生成的过程。
也就是从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。
7．对链表的评价：
优点： 1）链表在空间的利用上合理；
2）插入、删除时不需要移动元素；
因此，很多场合下，链表是线性表的首选存储结构。
缺点： 在实现某些基本操作（比如求线性表长度）时，不如顺序表。
另外： 在链表中，数据元素**性表中的“位序”概念已淡化，被元素在链表中的“位置”代替了。
四．顺序表和链表的比较：
在本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。通过对它们的讨论可知它们各有优缺点。
1．顺序存储的优点：
1) 方法简单，各种高级语言中都有数组，容易实现。
2) 不用为表示结点间的逻辑关系而增加额外的存储开销。
3) 顺序表具有按元素序号随机访问的特点。
2．顺序存储的缺点：
1) 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。
(2) 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。
3．链表的优缺点：
链表的优缺点恰好与顺序表相反。
4．在实际中怎样选取存储结构
通常有以下几点考虑：
1）基于存储的考虑
顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说事先对“maxsize”要有合适的设定，过大造成浪费，过小造成溢出。
可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；
链表不用事先估计存储规模，但链表的存储密度较低，存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度是小于１的。
基于运算的考虑
在顺序表中按序号访问ai的时间性能是o(1)，而链表中按序号访问的时间性能o(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；
而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；
在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。
3）基于环境的考虑
顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。
总之，两中存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。
简介： 栈和队列是两种重要的线性结构。
从数据结构角度看：
栈和队列也是线性表，其特殊性在于栈和队列的基本操作是线性表操作的子集，它们是操作受限的线性表，因此，可称为限定性的数据结构。
从数据类型角度看：
栈和队列是和线性表大不相同的两类重要的抽象数据类型。
一．术语与概念：
1）栈（stack）：
栈是限定只在表尾进行插入或删除操作的线性表。
2）栈顶（top）：栈的表尾称为栈顶。
3）栈底（bottom）：栈的表头称为栈底。
4）栈的长度：栈中元素的个数称为栈的长度。
5）空栈：不含元素的栈称为空栈，即长度为0的栈。
6）进栈（push）：
在栈顶插入元素称为进栈（压栈、入栈）。
7）出栈（pop）：
删除栈顶元素称为出栈（退栈、弹栈）。
二．栈的特点：
栈是“后进先出”的线性表。
“后进先出”last in first out（简称lifo）或
“先进后出”first in last out（简称filo）。
栈的基本操作除了在栈顶插入、删除外，还有栈的初始化、判空、取栈顶元素等。
四．栈的表示和实现（ 顺序栈 / 链式栈）
1．栈的顺序表示：（顺序栈）
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。
说明： 顺序栈也是采用动态分配存储空间的办法。
栈的初始化操作就是按设定的初始分配量进行第一次存储分配，base始终指向栈底位置。
如果base=null，表示栈结构不存在，即栈构造之前和销毁以后，base的值都是null。
top初值指向栈底，即top=base可作为栈空的标志。
插入新的栈顶元素时，top增1，
删除栈顶元素时，top减1，
因此，非空栈的栈顶指针始终指向栈顶元素的下一个位置。
4．栈的链式表示：
用链式存储结构实现的栈称为链栈。
通常链栈用单链表表示，因此其结点结构与单链表的结构相同，在此用linkstack表示，即有：
typedef struct node{
datatype data;
线性结构与非线性结构
数据结构 逻辑结构 存储结构。逻辑结构分为四种 数据元素间没有任何关系 集合。数据元素间有线性关系 线性结构。所谓线性关系 除第一个元素外，其他元素有且只有一个前驱 除最后一个元素外，其他元素有且只有一个后继！数据元素间有层状关系 树结构。数据元素间有网状关系 图结构。非线性结构。传统文本 例如书籍...
线性结构在非线性结构中的应用
摘要 数据结构课程中数据的逻辑结构分为线性结构和非线性结构。数据结构中线性结构指的是数据元素之间存在着 一对一 的线性关系的数据结构。相对应于线性结构，非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后驱。关键字 线性表，树，图。1.引言。数据元素相互之间的关系称为结构。有四类基本结构 ...
非线性 非线性结构分析
非线性结构的定义。在日常生活中，会经常遇到结构非线性。例如，无论何时用钉书针钉书，金。属钉书钉将永久地弯曲成一个不同的形状。看图1 1 a 如果你在一个木。架上放置重物，随着时间的迁移它将越来越下垂。看图1 1 b 当在。汽车或卡车上装货时，它的轮胎和下面路面间接触将随货物重量的啬而变化。看图1 1...