09年自考《数据结构》各章要点一[5]

顺序表和链表的比较

·基于空间

·顺序表的存储空间是静态分配存储密度为适于线性表事先确定其大小时采用

·链表的存储空间是动态分配存储密度<适于线性表长度变化大时采用

·基于时间

·顺序表是随机存储结构当线性表的操作主要是查找时宜采用

·以插入和删除操作为主的线性表宜采用链表做存储结构

·若插入和删除主要发生在表的首尾两端则宜采用尾指针表示的单循环链表

第三章 栈和队列

栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表称插入删除这一端为栈顶另一端称为栈底表中无元素时为空栈栈的修改是按后进先出的原则进行的我们又称栈为LIFO表(Last In First Out)通常栈有顺序栈和链栈两种存储结构

栈的基本运算有六种

·构造空栈InitStack(S)

·判栈空StackEmpty(S)

·判栈满StackFull(S)

·进栈Push(Sx)

·退栈Pop(S)

·取栈顶元素StackTop(S)

[] [] [] [] [] [] [] [] [] [] []