比较顺序存储结构和链式存储结构 - 副本.doc

1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答： 顺序存储时，相邻数据元素的存放地址也相邻;内存中可用存储单元的地址必须是连续的。优点：存储密度大（1），存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针. 优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入，删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。顺序表与链表的比较 基于空间的比较-存储分配方式：顺序表的存储空间是静态分配的；链表的存储空间是动态分配的 存储密度 = 结点数据本身所占的存储量/结点结构所占的存储总量：顺序表的存储密度 = 1；链表的存储密度 1基于时间的比较存取方式：顺序表可以随机存取，也可以顺序存取；链表是顺序存取的；插入/删除时移动元素个数；顺序表平均需要移动近一半元素；链表不需要移动元素，只需要修改指针顺序表和链表的比较 顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑： 顺序表 链表 基分静态分配。程序执行之前必须明确规 动态分配只要内存空间尚有空闲，于配定存储规模。若线性表长度n变 就不会产生溢出。因此，当线性表空方化较大，则存储规模难于预先确定 的长度变化较大，难以估计其存储间式估计过大将造成空间浪费，估计太 规模时，以采用动态链表作为存储考 小又将使空间溢出机会增多。 结构为好。 虑 存为1。当线性表的长度变化不大 ，next-next 和 rear, 查找时间都是O(1)。 若用头指针来表示该链表，则查找终端结点的时间为O(n)。在链表中设置头结点有什么好处？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。1.队列先进先出，栈先进后出。2.对插入和删除操作的限定。 栈是限定只能在表的一端进行插入和删除操作的线性表。 队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。 从数据结构的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的限定。 栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按后进先出的规则进行操作，而队列必须按先进先出的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。3.遍历数据速度不同。栈只能从头部取数据 也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间，保持数据在遍历前的一致性队列怎不同，他基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。队列（Queue）是限定只能在表的一端进行插入和在另一端进行删除操作的线性表。从数据结构的角度看，它们都是线性结构，即数据元素之间的关系相同。但它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的限定。栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按后进先出的规则进行操作，而队列必须按先进先出的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。递归算法的优缺点: 优点：递归过程结构清晰;程序易读;正确性容易证明 缺点：时间效率低; 空间开销大; 算法不容易优化递归算法转换为非递归算法:采用迭代算法;尾递归的消除;利用栈消除任何递归循环队列: 队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1: front = (front+1) % maxSize; 队尾指针进1: