数据结构-第二章 线性表.ppt

"数据结构-第二章 线性表" 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括数据元素、数据项、数据对象、逻辑结构和存储结构（物理结构）。算法的五个重要特性是：算法效率的度量、事前统计、事后分析。 数据结构的第二章讲解了线性表的概念和实现。线性表是最常用且最简单的一种数据结构。它是n（n>=0）个性质相同的数据元素构成的有限序列。线性表的特点是：存在唯一的“第一个”数据元素；存在唯一的“最后一个”数据元素；除第一个外，每个数据元素均有且只有一个前驱元素；除最后一个外，每个数据元素均有且只有一个后继元素。 线性表的类型定义包括线性表的基本运算，如表的初始化、求表长、存取表中的结点、查找结点、插入结点和删除结点。线性表的抽象数据类型（ADT）包括数据对象、数据关系和基本操作。 线性表的基本操作包括InitList(&L)、DestroyList(&L)、ClearList(&L)、ListEmpty(L)、ListLength(L)、GetElem(L, i, &e)、LocateElem(L, e, compare())、PriorElem(L, cur_e, &pre_e)、NextElem(L, cur_e, &next_e)、ListInsert(&L, i, e)、ListDelete(&L, i, &e)和ListTraverse(&L, visited())。 InitList(&L)操作结果是构造一个空的线性表L。DestroyList(&L)操作结果是销毁线性表L。ClearList(&L)操作结果是将线性表L重置为空表。ListEmpty(L)操作结果是判断线性表L是否为空。 线性表的实现方式有顺序表示和链式表示。顺序表示是将所有数据元素存储在一块连续的存储空间中。链式表示是将每个数据元素存储在一个独立的存储空间中，并使用指针将它们连接起来。链式表示又可以分为单链表、循环链表和双向链表等。 时间复杂度是衡量算法效率的一种度量方式。时间复杂度的计算可以使用事前统计和事后分析。例如，执行下面程序，执行S语句的时间复杂度为O(n^2)： for( int i=1; i<=n; i++ ) for ( int j=1; j<i; j++ ) S; 数据结构的第二章讲解了线性表的概念、类型定义、基本操作和实现方式，并且介绍了时间复杂度的计算方法。