网站开发菜鸟教程,开发小程序平台,重庆工商局官网,wordpress上传主题没有反应1.单链表#xff1a;1.1定义/性质#xff1a;链表是线性表的链式存储方式。单链表通过指针线性遍历#xff0c;删除/增加节点时间复杂度为O(1#xff09;,访问节点时间复杂度为O(n)。单链表分为带头结点和不带头结点两种#xff0c;带头结点是为了方便统一操作#xff08…1.单链表1.1定义/性质链表是线性表的链式存储方式。单链表通过指针线性遍历删除/增加节点时间复杂度为O(1,访问节点时间复杂度为O(n)。单链表分为带头结点和不带头结点两种带头结点是为了方便统一操作删除和插入操作都是通过指next指针来完成的当只有一个节点的时候做删除操作/没有节点的时候做插入操作这两种情况要特殊处理。对节点的描述如下typedef struct LNode{ElemType Data;//数据域struct Lnode next;//指针域
}Node;1.2单链表的操作默认下列情况都有头结点。1.2.1初始化创建该操作初始化头指针和头结点Node* init(){Node* L(Node*)malloc(sizeof(struct LNode));L-nextNULL;return L;
}1.2.2插入操作有头插法和尾插法两种方法对于头插法先插入的在后后插入的在前Node* HeadInsert(){Node* tmp(Node*)malloc(sizeof(struct LNode));//创建新节点tmp-nextL-next;//新节点指向头节点的指向L-nexttmp;//头结点指向新节点return L;
}对于尾插法要设置一个尾指针通过尾指针完成插入1.2.3删除操作删除操作要通过next指针完成并且单链表是单向的所以只能删除遍历到的节点的下一个节点只能改变该节点的指向也就是下一个节点。bool Delete(Node* L,int P){//删除值为p的节点for(Node* iL,i;ii-next){if(L-next-DataP){//如果下一个节点的值为PL-nextL-next-next;return true;}}return false;
}1.2.4反转操作法一空间复杂度O(n)遍历链表并使用头插法建立一个新链表即可。法2空间复杂度O(1)借助两个辅助指针p,q初始p指向头结点pL原指针L指向尾节点的指向(LNULL具体步骤p用于遍历链表每次操作q取出p遍历到的节点并且连接到L的前面包括头结点都逆转了再让L指向q指向的Lq。1.3其他单链表循环单链表尾节点指向头结点而不是NULL判断链表是否为空的方法是尾节点的指针是否等于头结点的指针。2双链表在单链表的基础上每个节点增加了一个指向前驱的指针pre。2.1双链表的操作在做双链表的操作时要注意每一步的先后顺序。对于该双链表2.1.1插入操作在p指针指向的节点后插入一个节点a更新a的前后指针通过a来更新p,q的指针由于我们的指针是p所以先更新q再更新pq要通过p得到。2.1.2删除操作假设a节点已经插入了删除节点a:先更新q再更新p即可。
