作者：云梦泽
时间：2013.10.21
出处：http://write.blog.csdn.net/postlist
声明：版权所有，侵犯必究，如有转载请声明出处

前言 先描述一个概念，什么是数据结构？

数据结构就是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

我们在描述这类非数值问题或者说非纯数值问题时，数学模型不再是数学方程，而是诸如表啊，树啊，图啊之类，因为我们已经无法用数学方程的方式去刻画这些“奇葩”问题。但还是没有脱离数学，所以说一些生活皆数学。

一、线性表

`线性表特点

a.存在唯一一个“1号“数据元素

b.存在唯一一个“最后”数据元素

c.除1号元素外，每个数据元素只有一个前驱

d.除最后元素外，每个数据元素只有一个后继

（附：)抽象数据类型(ADT):是指一个数学模型以及在定义在该模型上的一组操作。仅取决于它的一组逻辑特性，与在计算机内部如何表示和实现无关。由于其定义的数学特性相同，在用户看来是无区别的。

抽象数据类型定义格式

ADT 抽象数据类型名｛

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

}ADT 抽象数据类型名

二、抽象数据类型线性表定义

ADT List {

 数据对象：D=｛a1,a2,a3...}

 数据关系：R

 基本操作：

InitList(&L)            //构造一个空的线性表L

DestoryList(&L)   //若L存在，销毁线性表L

ClearList(&L)       //若L存在，置为空表

ListEmpty(L)       //若L存在，判断是否为空

ListLength(L)   //若L存在，返回数据元素个数

GetElem(L,i,&e)  //若L存在用e返回L中第i个数据元素的值

ListInsert(&L,i,e)//若L存在，在L中第i个位置之前插入新的数据元素e,L长度加1

ListDelete(&L,i,&e)//若L存在，非空，删除L的第i个数据元素，用e返回其值，L长度减1

｝ADT List

三、线性表的存储表示和实现

线性表的顺序存储表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。

特点：逻辑相邻元素物理相邻

优点：可随机存取表中任一元素，存储位置表示直观（可公式化）

缺点：插入删除操作需移动大量元素

线性表的链式存储是用一组任意的存储单元存储线性表的数据元素。数据元素之间的逻辑关系由节点中的指针指示

特点：逻辑相邻元素对物理相邻无要求

优点：

a.创建方便，顺序存储通常需要在创建时指定大小

b.节点删除非常方便，不需要像线性结构那样移动数据

c.节点的访问方便，可通过循环或递归方法访问到任意数据

缺点：不可随机存取，平均的访问效率低于线性表

节点=数据域+指针域

头节点：有时我们在单链表的第一个节点之前附设一个头节点，头节点数据域可以不存储任何信息，也可存储线性表的长度等附加信息，头节点的指针域指向第一个节点的指针（即存储位置），若线性表为空，则头节点指针域为空。

这样数据就像一条链子一样串起来，节点的指针域就起到穿线连结的作用。

(下篇：线性表的具体实现+C语言知识=一遍学数据结构一边复习C语言)