C语言的全面介绍7.ppt

8.4 顺序表与链表的比较 上面已经讨论了线性表的两种存储结构：顺序表和链表。在实际应用中，两种方法各有特色，我们究竟选用哪一种作为存储结构呢?这要根据具体问题的要求和性质来决定，一般可以从以下几个方面考虑。 1．基于存储空间的考虑 顺序表的存储空间是静态分配的，程序执行之前必须预先分配。若线性表的长度n变化较大，存储空间难以事先确定，估计过大，将造成大量存储单元的浪费，估计过小时又不能临时扩充存储单元，将使空间溢出机会增多。链表的存储空间是动态分配的，只要内存空间尚有空闲，就不会发生溢出。对于存储空间的考虑，可以用存储密度的大小来衡量。存储密度为结点应占用的存储量除以结点实际占用的存储量。存储密度越大，存储空间利用率越高，反之利用率越低。例如，顺序表的存储密度为100%，单链表为50%（假设指针所占空间与数据域所占空间相同），双向链表的存储密度为33%。 由此可知，当线性表的长度变化不大，存储空间可以事先估计时，采用顺序表作存储结构比较方便；当线性表长度变化较大，存储空间难以事先估计时，采用链表作存储结构比较方便。 2．基于时间的考虑 顺序表是一种随机访问的表，而链表是一种顺序访问的表，因此顺序表的访问较链表方便。若线性表中运算主要为存取、查找运算，采用时间复杂度为O(1)的顺序表比较方便；若线性表中的运算大部分为插入、删除运算，采用时间复杂度为O(1)的链表比较方便；若链表中操作运算都在表尾进行，应采用尾指针所示的单循环链表。 3．基于语言的考虑 有的高级语言无指针数据类型，因此，若用链表作存储结构，则只能用整数代替指针，称这样的链表为静态链表，而一般的链表则称为动态链表（我们所用的链表都为动态链表）。 * * 第八章 线性表 数据结构中的三种关系: 一对一的线性关系(线性结构) 一对多的非线性关系(树形结构) 多对多的非线性关系(图形结构) 线性结构又包含:线性表、栈和队列 8.1 线性表的定义及其运算 8.1.1 线性表的定义 在实际应用中，线性表是最常用而且是最简单的一种数据结构。例如，一副扑克牌的点数是一个线性表，可表示为（2,3,4,5,6,7,8,9,1 0,J,Q,K,A），一些城市的名字是一个线性表，可表示为（Changsha,Beijing,Shanghai,Guangzhou,Wuhan）。 1．线性表的定义 线性表（linear list）是n（n≥0）个数据元素a1，a2，…，an组成的有限序列。其中n 称为数据元素的个数或线性表的长度，当n=0时称为空表，当n0时称为非空表。通常将非空的线性表记为（a1，a2，…，an），其中的数据元素ai（1≤i≤n）是一个抽象的符号，其具体含义在不同情况下是不同的，即它的数据类型可以根据具体情况而定。 2．线性表的特征 从线性表的定义可以看出线性表的特征： （1）有且仅有一个开始结点（表头结点）a1，它没有直接前驱，只有一个直接后继； （2）有且仅有一个终端结点（表尾结点）an，它没有直接后继，只有一个直接前驱； （3）其他结点都有一个直接前驱和直接后继； （ 4）元素之间为一对一的线性关系。 因此，线性表是一种典型的线性结构，用二元组表示为： linear_list=(A,R) 其中 A={ai ∣1≤i≤n,n≥0,ai∈elemtype} R={r} r={ai,ai+1 ∣1≤i≤n-1} 对应的逻辑结构图如下所示。 8.1.2 线性表的运算 给出了线性表的逻辑结构后，就可以直接定义它的一些基本运算，但这些运算要实现，还必须依赖于具体的存储结构。 常见线性表的运算有： （1）置空表 setnull(L)：将线性表L置成空表。 （2）求长度 Length(L)：求给定线性表L的长度。 （3）取元素 Get（L,i）：若1≤i≤length(L)，则取第i个位置上的元素，否则取得的元素为NULL。 （4）求直接前驱 Prior(L,x)：求线性表L中元素值为x的直接前驱，若x为第一个元素，前驱为NULL。 （5）求直接后继 Next（L,x）：求线性表L中元素值为x的直接后继，若x为最后一个元素，后继为NULL。 （6）定位函数 Loca(L,x)：在线性表L中查找值为x的元素位置，若有多个值为x，则以第一个为准，若没有，位置为0。 （7）插入 Inse(L,x,i)：在线性表L中第i个位置上插入值为x的元素。 （8）删除 Dele（L,i）：删除线性表L中第i个位置上的元素。 8.2 线性表的顺序存储结构 8.2.1 顺序表结构 线性表的顺序存储结构，也称为顺序表。其存储方式为：在内存中开辟一片连续存储空间，但该连续存储空间的大小要大于或等于顺序表的长度，然后让线性表中第一个元素存放在连续存储空间的第