数据结构第二章.doc

第二章 线性表（Linear List）| 逻辑结构及其基本操作| 线性表的顺序存储结构| 线性表的链式存储结构| 静态链表| 应用实例逻辑结构及其基本操作| 定义：由n个相同类型数据元素a0 a1aian-1 构成的有限序列。z 说明：ai是抽去现实意义的抽象表示符号。typedef int DataType;typedef char DataType;typedef struct student DataType;| 基本操作初始化：Initiate（L) 求长度：ListLength（L） 前插：ListInsert（L,i,x）删除：ListDelete（L,i,x）取元素：ListGet(L,i,x)注：L为线性表| 顺序存储结构：用一组地址连续的存储单元依次存储线性表的各个元素。 线性表的定义：#define MaxSize 1024 /假定线性表的最大长度为1024typedef int DataType; /*定义数据类型*/typedef struct DataType ListMaxSize; int size;SeqList;M注意：这样定义不能对size进行初始化，因此一定要在使用前进行初始化赋值。 | 线性表元素的插入 | 线性表元素的删除 小结：很显然，顺序表的插入和删除一个元素时，其时间主要花费在移动数据元素上。算法的代价分析：插入 删除平均移动结点的次数： 同理可得：E= E=假设结点插入的概率相同，即 Pi=把Pi代入E的计算公式中，则有：E=所以，在顺序表上插入和删除一个元素的时间复杂度是：（n）。 对于取元素和定位操作可以直接实现。| 例：利用线性表的基本运算实现清除L中多余的重复节点。 | 顺序表的优点：简单、常用。无须为表示节点间的逻辑关系而增加额外的存储空间可以方便的随机存取表中的任一节点| 顺序表的缺点插入和删除运算时，需移动大量数据，运行速度受到影响。需预先确定数据元素最大个数。| 线性表的链式存储| 链表（Linked List）：一种物理存储上非连续、非顺序的线性存储结构，数据元素间的逻辑顺序是通过链表中的指针链接次序实现的。| 节点构成：数据域指针域| 单链表结点的定义typedef struct Node DataType data; struct Node *next; SLNode;| 单链表的结点结构的定义（）一般形式的单链表存储结构的结点定义方法 typedef struct Node DataType Data; struct Node *Next SLNode;|typedef int datatype;typedef struct char name10;int age; DataType;节点存储空间的申请 p(SLNode *)malloc(sizeof(SLNode);节点存储空间的释放 free(p);| 单链表中的基本操作初始化int ListInitiate(SLNode * *head) if (*head = (SLNode *)malloc(sizeof(SLNode) = NULL) return 0;用头指针建立了一个空表。(*head) - Next = NULL;return 1; | 单链表中的基本操作前插在单链表h中的第i个元素之前插入一个数据元素x。int ListInsert (SLNode *head, int i , DataType x)SLNode *p,*q;int j;p = h;j = 0;while( p != NULL & j Next;j + +; if (j != i-1) printf(“n插入位置不合理！ ”); return 0; /*申请一空结点*/if (q =(SLNode *)malloc(sizeof(SLNode) = =NULL) return 0;q - Data = x; /*给数据赋值*/q - Next = p - Next;p - Next = s;return 1;| 单链表中的基本操作删除在单链表h中删除第i个结点。| 单链表中的基本操作取元素在单链表h中寻找第i个结点，并返回该结点的数据元素。| 单链表中的操作举例 假设已有单链表la，复制一个具有同样结构的单链表lb。 | 循环单链表循环单链表的定义：循环单链表是单链表的另一种形式,其特点是链表中最后一个结点的指针不再是空的,而是指向头结点或第一个结点,整个链表形成一个环。从表中任一个结点出发，都可找到表中其它结点。| 双向链表双向链表的定义：具有两个方向的指针域的链表叫双向链表，这两个指针域分别指向当前结点的前驱和后继。单链表只能从表头开始沿一个方向查找；而双向链表可以从任一个结点出发，向前或向后查找 。| 双向链表结点的结构定义typedef struct NodeDataType Data；struct Node * Prior，* Next； DLNode； 双向链表前插操作的C语言算法 P-49| 双链表中的基本操作删除 双向链表删除操作的C语言算法 p-50 | 链式存储结构的特点链式存储结构的优点 (1) 结点空间的动态申请和动态释放; (2) 数据元素的逻辑次序用结点的指针域指示，插入