双链表
产生原因:单链表只有一个指向后继的指针,如果要访问某节点的前驱结点,只能从头遍历,也就是访问后继节点的时间复杂度为1,访问前驱结点的时间复杂度为n。 而引入双链表使得在插入、删除的时间复杂度只为1,缺点就是更加浪费空间。循环链表
和单链表区别在于,最后一个结点的指针不是NULL,而是改为指向头结点。优点是对表头和表尾进行操作的时间复杂度都是1
内核链表 (与普通链表区别,是数据包含节点)
一种链表结构能够操作多种类型的数据对象;
节点包含数据变成数据包含节点。如上图,内核链表头结点结构为:
struct list_head {
struct list_head *next;
struct list_head *prev;
};其余节点为数据包含节点,例如:
typedef struct data {
struct list_head node; //小节点
int data; //数据
}data_t;
其操作代码如下:栈和队列
1.栈和队列是特殊的表状结构
表可以在任意位置插入和删除
栈和队列只允许在固定位置插入和删除2.栈:分为顺序栈(空增栈) 和 链式栈
LIFO 结构
先进后出,后进先出 (Last In First Out)的线性表
栈顶:允许入栈出栈的一端称为栈顶
栈底:不允许入栈和出栈的一端称为栈底
入栈(压栈):将数据元素放入栈顶
出栈(弹栈):将数据元素从栈顶位置取出空栈:不含任何元素的空表。
顺序栈分类:空增栈;空减栈; 满增栈;满减栈(学的是空增栈)
1. 栈的常见基本操作
初始化(InitStack创)->进栈(Push增)->出栈(Pop删)->查栈是否为空(IsEmpty)、 查栈是否已满(IsFull)、销毁栈(DestroyStack销)
2. 空增栈(顺序栈)
其操作代码如下:
//存放数据的类型 typedef int DataType;//标签类型 typedef struct stack {DataType *pData;int Top;int tLen; }SeqStack;
SeqStack *CreateSeqStack(int MaxLen) {SeqStack *pTmpStack = NULL;//1.申请标签空间pTmpStack = malloc(sizeof(SeqStack));if (NULL == pTmpStack){return NULL;}//2.对每个成员赋初值pTmpStack->tLen = MaxLen;pTmpStack->Top = 0;pTmpStack->pData = malloc(MaxLen * sizeof(DataType));if (NULL == pTmpStack->pData){return NULL;}//3.申请存放数据的空间//4.返回标签地址 return pTmpStack; }
int IsFullSeqStack(SeqStack *pTmpStack)//判断栈满、空 {return pTmpStack->tLen == pTmpStack->Top ? 1 : 0; } int IsEmptySeqStack(SeqStack *pTmpStack) {return 0 == pTmpStack->Top ? 1 : 0; }
int PushSeqStack(SeqStack *pTmpStack, DataType TmpData)//进栈操作push {if (IsFullSeqStack(pTmpStack)){return -1;}pTmpStack->pData[pTmpStack->Top] = TmpData;pTmpStack->Top++;return 0; }
DataType PopSeqStack(SeqStack *pTmpStack) //出栈 {if (IsEmptySeqStack(pTmpStack)){return -1;}pTmpStack->Top--;return pTmpStack->pData[pTmpStack->Top]; }
int DestroySeqStack(SeqStack **ppTmpStack)//销毁栈 {free((*ppTmpStack)->pData);free(*ppTmpStack);*ppTmpStack = NULL;return 0; }
3.链式栈
采用链式存储的栈称为链式栈,链栈的优点是便于多个栈共享存储空间和提高其效率,且不存在栈满上溢的情况。通常采用单链表实现,并规定所有操作都是在单链表的表头进行的。这里规定链栈没有头节点,Lhead指向栈顶元素
对于空栈来说,链表原定义是头指针指向空,那么链栈的空其实就是top=NULL的时候。
链栈的结构代码如下:。。。。。
4.性能分析
链式栈的进栈push和出栈pop操作都很简单,时间复杂度均为O(1)。
对比一下顺序栈与链栈,它们在时间复杂度上是一样的,均为O(1)。对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链式栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制。所以它们的区别和线性表中讨论的一样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些