![](https://csdnimg.cn/release/download_crawler_static/87317665/bg3.jpg)
·查找·按序号:与查找位置有关,平均时间复杂度均为 O(n)。
·按值:与输入实例有关,平均时间复杂度均为 O(n)。
·插入运算:p=GetNode(L,i-1);s->next=p->next;p->next=s;平均时间复杂度均为 O(n)
·删除运算:p=GetNode(L,i-1);r=p->next;p->next=r->next;free(r);平均时间复杂度均为 O(n)
单循环链表是一种首尾相接的单链表,终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于
头指针或尾指针。
采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是 O(1),不用
遍历整个链表。
双链表就是双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域 prior,形成两条不同方
向的链。由头指针 head 惟一确定。
双链表也可以头尾相链接构成双(向)循环链表。
双链表上的插入和删除时间复杂度均为 O (1)。
顺序表和链表的比较: ·基于空间:
·顺序表的存储空间是静态分配,存储密度为 1;适于线性表事先确定其大小时采用。
·链表的存储空间是动态分配,存储密度<1;适于线性表长度变化大时采用。
·基于时间:
·顺序表是随机存储结构,当线性表的操作主要是查找时,宜采用。
·以插入和删除操作为主的线性表宜采用链表做存储结构。
·若插入和删除主要发生在表的首尾两端,则宜采用尾指针表示的单循环链表。
第三章 栈和队列
栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表,称插入、删除这一端为栈顶,另一端称为栈底。
表中无元素时为空栈。栈的修改是按后进先出的原则进行的,我们又称栈为 LIFO 表(Last In First Out)。通常栈有
顺序栈和链栈两种存储结构。
栈的基本运算有六种: ·构造空栈:InitStack(S)
·判栈空: StackEmpty(S)
·判栈满: StackFull(S)
·进栈: Push(S,x)
·退栈: Pop(S)
·取栈顶元素:StackTop(S)