线性表中的链表概述

链表大体的框架线性表逻辑结构基本运算/操作存储/物理结构顺序表顺序存储定义如何用代码实现基本操作的实现链表链式存储单链表定义如何用代码实现基本操作的实现双链表循环链表静态链表单链表的定义和基本操作定义什么是单链表每个节点包括数据和指向下一个元素的指针优点无需连续的存储空间#定义一个单链表(不带头节点typedefstructLNode{//定义单链表节点类型ElemType data;//每个节点存放一个数据元素structLNode*next;//指针指向下一个节点}LNode*LinkList;//LNode强调是一个节点LinkList强调是一个链表LinkList p(LNode*)malloc(sizeof(LNode));//增加一个新的节点并用指针p指向该节点};初始化(不带头节点boolInitList(LinkListL){LNULL;returntrue;}判空不带头节点boolEmpty(LinkList L){if(LNULL)returntrue;elsereturnfalse;}#定义一个单链表带头节点typedefstructLNode{Elemtype data;structLNode*next;}LNode,*LinkList;初始化一个单链表带头节点boolInitList(LinkListL){L(LNode*)malloc(sizeof(LNode));if(LNULL)//内存不足分配失败returnfalse L-nextNULL;//头节点之后暂时还没有节点returntrue;}判空(带头节点)boolEmpty(LinkList L){if(L-nextNULL)returnfalse;elsereturnfalse;}#按位序插入带头结点在第i个位序插入指定元素e头节点可以看作第0个节点boolListInsert(LinkListL,inti,ElemType e){if(i1)//判断输入位序是否合法returnfalse LNode*p;intj0;//位序计数器pL;//头节点是第0个节点while(p!NULLji-1){//循环找到第i-1个节点pp-next;j;if(pNULL)//判断输入位序是否大于链表总长度是否合法returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts;//最后修改第i-1个节点returntrue;}不带头节点第1个位置插入需要特殊处理因为没有头节点boolListInsert(LinkListL,inti,ElemType e){if(i1)returnfalse;if(i1){//插入第一个位序特殊处理LNode*s(LNode*)malloc(sizeof(LNode));s-datae;s-nextL;Ls;//头指针指向新节点returntrue;}LNode*p;//扫描节点intj1;//计数器pL;//从第一个节点开始扫描while(p!NULLji-1){//循环找到第i-1个节点pp-next;j;}if(pNULL)//i值不合法returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts;returntrue;//插入成功#指定元素后插操作bool InsertNextNodeLNode*p,ElemType e){if(pNULL)//输入不合法returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)//内存分配失败returnfalse;s-datae;//套路s-nextp-next;p-nexts;returntrue;}在按位序插入中找到第i-1个节点后直接调用后插函数即可return InsertNextNode(p,e);#前插操作单链表只能往后找wuwuwu只能遍历链表找到指定节点的前驱节点时间复杂度O(n)但其实还有另外一种方法插入元素boolInsertPriorNode(LNode*p,ElemType e){if(pNULL)returnfalse;LNode*s(LNode*)malloc(sizeof(LNode));if(sNULL)returnfalse;s-nextp-next;p-nexts;s-datap-data;p-datae;returntrue;}插入节点boolInsertPriorNode(LNode*p,LNode*s){if(pNULL||sNULL)returnfalse;s-nextp-next;p-nexts;Elemtype tempp-data;p-datas-data s-datatemp;returntrue;}也就是先后插再调换这种方式的时间复杂度是O(1)这中偷天换日的操作还是很骚的#按位序删除boolListDelete(LinkListL,inti,ElemTypee){if(i1)returnfalse;LNode*p;intj0;pL;while(p!NULLji-1){//循环找到第i-1个节点pp-next;j;}if(pNULL)//i不合法returnfalse;if(p-nextNULL)//i-1之后再无其它节点returnfalse;LNode*qp-next;//q指向被删除节点eq-data//e返回删除节点中元素的值p-nextq-next;free(q);returntrue;}#删除指定节点孩子们我们依然找不到前驱节点难道还要用头指针遍历链表吗不牢大有他的小妙招boolDeleteNode(LNode*p){if(pNULL)returnfalse;LNode*qp-next;//令q指向*p的后继节点p-datap-next-data;//和后继节点交换数据域p-nextq-next;//p指向q的后继free(q);//终于删除了原本的preturntrue;}时间复杂度为O(1)那如果要删除的指定节点是最后一个节点呢此时p后面是NULL那我们只能遍历数组#按位序查找//按位查找返回第 i 个元素带头结点LNode*GetElem(LinkList L,inti){if(i0)returnNULL;LNode*p;//指针p指向当前扫描到的结点intj0;//当前p指向的是第几个结点pL;//L指向头结点头结点是第0个结点不存数据while(p!NULLji){//循环找到第 i 个结点pp-next;j;}returnp;}#按值查找//按值查找找到数据域e 的结点LNode*LocateElem(LinkList L,ElemType e){LNode*pL-next;//从第1个结点开始查找数据域为e的结点while(p!NULLp-data!e)pp-next;returnp;//找到后返回该结点指针否则返回NULL}#求表长//求表的长度带头结点intLength(LinkList L){intlen0;//统计表长LNode*pL;while(p-next!NULL){pp-next;len;}returnlen;}#尾插法建立单链表LinkList List_TailInsert(LinkList L){ //正向建立单链表 int x; //设ElemType为整型 L(LinkList)malloc(sizeof(LNode)); //建立头结点 LNode *s,*rL; //r为表尾指针 scanf(%d,x); //输入结点的值 while(x!9999){ //输入9999表示结束 s(LNode *)malloc(sizeof(LNode)); s-datax; r-nexts; rs; //r指向新的表尾结点 scanf(%d,x); } r-nextNULL; //尾结点指针置空 return L; }#头插法建立单链表可以用于链表的逆置LinkListList_HeadInsert(LinkListL){//逆向建立单链表LNode*s;intx;L(LinkList)malloc(sizeof(LNode));//创建头结点L-nextNULL;//初始为空链表防止脏数据scanf(%d,x);//输入结点的值while(x!9999){//输入9999表示结束s(LNode*)malloc(sizeof(LNode));//创建新结点s-datax;s-nextL-next;L-nexts;//将新结点插入表头scanf(%d,x);}returnL;}