数据结构之线性结构

        常见的经性结构有线性表,栈,队列,双阶列,数组,串.

• 数据结构中数据的逻辑结构分为线性结构和非性结构.
• 线性结构就是n个数据元素的有序(次序)集合.
• 线性结构特征:
  1)只有一个首结点
  2)只有一个尾结点
  3)除首尾结点外, 其它结点称为内部结点
  4)首结点只有后继结点,无前趋结点.
  5)尾结点只有前趋结点,元后继结点.
  6)内部结点有一个前趋结点,有一个后继结点.
  
  
• 线性结构中的数据元素存在着"一对一"关系.
• 相对于线性结构,非线性结构中的数据元素间存在"一对多"(树结构)或"多对多"(图结构)的关系.

 

线性表的存储结构

1. 顺序表:用顺序存储方式存储的线性表简称为顺序表.顺序存储是指将线性表元素按照逻辑顺序依次存储在一组连续的地址单元中.
2. 链式表:通过结点中的链域将线性表中n个结点按其逻辑顺序链接在一起. 分为:单向链表, 双向链表,循环链表.

常用线性结构

• 线性表:线性表（Linear List）是由n（n≥0）个数据元素（结点）a₁，a₂，…，a_n组成的有限序列。
• 栈: 限定在表的一端进行插入和删除的线性表.其特点是元素变化按"后进先出"原则进行, 因此又称为"后进先出表"(Last in first out, 简称LIFO).

　　　　栈的术语:

　　　　栈顶:允许插入/删除元素的一端.

　　　　栈底:与栈顶相对的另一端.

　　　　进栈:向栈顶插入元素.

　　　　出栈:删除栈顶元素.

　　　　栈的基本运算:进栈, 出栈, 取栈顶元素, 判栈空, 置栈空

 

• 队列: 限制只能在一端插入元素,在另一端删除元素的线性表.其特点为队列元素变化按"先进先出"原则进行,因此双称"先进先出表" (First in first out:  简称:FIFO).

　　　　队列的术语:

　　　　队对:允许删除元素的一端

　　　　队尾:允许插入元素的一端

　　　　入队:向队列中插入元素

　　　　出队:删除队列中的元素

　　　　队列的基本运算: 入队 出队 取队头元素 判队空 置队空

 

• 串: 串就是字符串,串是一种特殊的线性表(结点由字符组成)

 

参考:

线性结构:http://baike.baidu.com/view/390966.htm

栈:http://baike.baidu.com/subview/38877/12246229.htm#viewPageContent