阿里云虚拟主机做淘客网站,最好的ui设计培训,网站建设东莞长安镇,政务网站队伍建设情况汇报单链表理论知识详解 文章目录 单链表理论知识详解1.单链表的定义2.单链表的初始化3.单链表的插入和删除3.1 单链表的插入3.1.1 按位序插入3.1.2 在指定结点的前后插入一.后插操作二.前插操作 4.单链表的删除4.1 按位序删除4.2 指定结点的删除 5.单链表的查找5.1 按位序查找5.2 …单链表理论知识详解 文章目录 单链表理论知识详解1.单链表的定义2.单链表的初始化3.单链表的插入和删除3.1 单链表的插入3.1.1 按位序插入3.1.2 在指定结点的前后插入一.后插操作二.前插操作 4.单链表的删除4.1 按位序删除4.2 指定结点的删除 5.单链表的查找5.1 按位序查找5.2 按值查找补充一个:求表的长度 6. 单链表的建立(带头结点的建立)6.1 尾插法建立单链表6.2 头插法建立单链表 本文完整代码 1.单链表的定义
线性表的链式存储. 优点:不要求大片连续空间,改变容量方便 缺点:不可随机存取,要耗费一定空间存放指针
typedef struct LNode{int data;struct LNode *next;
}LNode, *LinkList;typedef 取别名 将struct LNode 取别名为别的方便书写 比如我们要声明一个该结构体的时候 由原先的struct LNode a; 可以直接写为LNode a; 由原先的struct LNode *p; 可以直接写为LinkList a; 2.单链表的初始化
带头结点的初始化,头结点就是多一个结点,指向第一个存放数据的结点. 不带头结点,会使处理数据的逻辑更复杂,对空表和非空表需要不同的代码逻辑. 单链表的初始化本质:为头结点分配一个堆空间,将头结点指针域置为空,加上判断内存是否能分配
#include stdio.h
#include stdlib.h
//这是带有头结点的单链表初始化
void InitList() {LinkList L;//定义头指针变量 L(LNode*)malloc(sizeof(LNode));//头指针指向分配的头结点内存空间 L-nextNULL;return true;
}
int main()
{InitList( );
}3.单链表的插入和删除
3.1 单链表的插入
3.1.1 按位序插入
按位序插入,比如说有5个元素,插入到第三个元素的位置 注意在有头结点时,位序5,意味着是结点6 假如我们要插入的位序是3,意味着我们要寻找的是位序2,也就是结点3,当ji-1时我们跳出循环,先操作,后j,j代表当前结点值从0开始,也就是我们在j3的时候应该跳出循环,所以先操作,后j,就是ji-1,ji的时候就跳出循环 传入什么? 表插入位置插入的值 分为几步? 首先是非法操作的判断,是否合法. 第二步是,寻找要插入的位置,插入第几个位置,就找到他前一个位置即i-1,让此时的指针p落在该点处,即我们可以操作他的next域 第三步,先判断吐过p指向空,插入操作不合法,若合法,分配堆空间给一个新的结点s,s的数据域是传入值e,s的指针域指向原先的i(i-1的next域,即p当前的next域),然后将i-1的next域指向新的i 核心思想先连后断
bool ListInsert(LinkList L,int i,int e)
{if(i1)return false;LNode *pL; //为什么需要p指针,因为我们不能动表头指针int j0; //用来判断当前指针在第几个结点处,j0,意思是在头结点处while(p!NULLji-1) //P不能为空,为空咋插入啊,操作不合法,ij的时候跳出循环{pp-next; j; } //通过这个循环我们就能找到A的指向B的next域在他俩中间插入Cif(pNULL)return false; //上个循环判断它是否为空为空不执行为空的具体操作写在了这为空就结束LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts;return true;
}3.1.2 在指定结点的前后插入
一.后插操作 分两步 判断操作是否合法(p指针是否为空s是否能分配) 插入元素操作 InsertNextNode(LNode *p,int e)
{if(pNULL)return false;LNode *s(LNode *)malloc(sizeof(LNode)); if(sNULL)return false;s-datae;s-nextp-next;p-nexts;return true;
}二.前插操作
前插操作我们这里不讨论从前遍历一遍,到最后的那种方法 而是考虑,用后插法再交换他们的数据域这种形式可以将时间复杂度降低到o(1)
bool InsertPriorNode(LNode *p,int e)
{if(pNULL)return false;LNode *s(LNode *)malloc(sizeof(LNode)); if(sNULL)return false;s-nextp-next;p-nexts;s-datap-data;p-datae;return true;
}4.单链表的删除
4.1 按位序删除 第一步与之前的查找的相同的,现查找位序-1的点 然后再进行删除操作 bool ListDelete(LinkList L,int i,int e)
{if(i1)return false;LNode *pL; //为什么需要p指针,因为我们不能动L头指针int j0; //用来判断当前指针在第几个结点处,j0,意思是在头结点处while(p!NULLji-1) //P不能为空,为空咋插入啊,操作不合法,ij的时候跳出循环{pp-next; j; } if(pNULL) return false;if(p-nextNULL) return false;LNode *qp-next; //方便操作搞出了一个q,直接用p也行,就是写起来不直观eq-data;p-nextq-next;free(q);return true;
}4.2 指定结点的删除
指定删除结点p,我们思考,给你结点p删除它,需要找到前一个结点,但是那样做太麻烦了,不如交换指定结点和后一个结点的数据域,再删除新的后继结点
bool DeleteNode(LNode *p)
{if(pNULL)return false;LNode *qp-next;p-dataq-data;p-nextq-next;free(q);return true;
}5.单链表的查找
5.1 按位序查找
返回值是位序结点的指针
LNode * GetElem(LinkList L,int i)
{if(i0)return NULL;LNode *pL;int j0;while(p!NULLji){pp-next;j;}return p;} 5.2 按值查找
LNode * LocateElem(LinkList L,int e)
{LNode *pL-next; //从第一个结点处开始查值while(p!NULLp-data!e){pp-next;}return p;
}补充一个:求表的长度
int Length(LinkList L){int len0; //不包括头结点 LNode *pL;while(p-next!NULL){pp-next;len;}return len;
}6. 单链表的建立(带头结点的建立) 单链表的建立包括了头结点的建立(初始化) 6.1 尾插法建立单链表
- 在尾插法中,LNode *s,*rL;这个写法,其实是为了简化代码,实际上*s不需要赋值,
- 因为在接下来的代码中会给结点s分配堆空间,结点s的位置就会变成随机的,
- 实际上,我们只需要让rL就行,声明一个s即可声明输入值x,分配头结点,声明s和r指针循环分配s结点再把它加入链表,再循环的输入x值链表尾指针置空
LinkList List_Tailnsert(LinkList L)
{int x;L(LinkList)malloc(sizeof(LNode)); //初始化头结点LNode *s,*rL; //定义上表尾指针和待随机分配的结点指针scanf(%d,x);while(x!9999) //输出9999表示结束{s(LNode *)malloc(sizeof(LNode));s-datax;r-nexts;rs;scanf(%d,x);}r-nextNULL;return L;
}6.2 头插法建立单链表
头插法相比于尾插法,我们要把头指针置空,因为分配的头指针很可能指向神秘的空间有脏数据
LinkList List_Headlnsert(LinkList L)
{int x;L(LinkList)malloc(sizeof(LNode));L-nextNULL; //初始链表头指针指向NULLLNode *s;scanf(%d,x);while(x!9999) //输出9999表示结束{s(LNode *)malloc(sizeof(LNode));s-datax;s-nextL-next;L-nexts;scanf(%d,x);}return L;
}本文完整代码
#include stdio.h
#include stdlib.h
typedef struct LNode{int data;struct LNode *next;
}LNode ,*LinkList;void InitList() {LinkList L;//定义头指针变量 L(LNode*)malloc(sizeof(LNode));//头指针指向分配的头结点内存空间 L-nextNULL;return true;
}
bool ListInsert(LinkList L,int i,int e)
{if(i1)return false;LNode *pL; //为什么需要p指针,因为我们不能动L头指针int j0; //用来判断当前指针在第几个结点处,j0,意思是在头结点处while(p!NULLji-1) //P不能为空,为空咋插入啊,操作不合法,ij的时候跳出循环{pp-next; j; } if(pNULL)return false;LNode *s(LNode *)malloc(sizeof(LNode));s-datae;s-nextp-next;p-nexts;return true;
}InsertNextNode(LNode *p,int e)
{if(pNULL)return false;LNode *s(LNode *)malloc(sizeof(LNode)); if(sNULL)return false;s-datae;s-nextp-next;p-nexts;return true;
}
bool InsertPriorNode(LNode *p,int e)
{if(pNULL)return false;LNode *s(LNode *)malloc(sizeof(LNode)); if(sNULL)return false;s-nextp-next;p-nexts;s-datap-data;p-datae;return true;
}bool ListDelete(LinkList L,int i,int e)
{if(i1)return false;LNode *pL; //为什么需要p指针,因为我们不能动L头指针int j0; //用来判断当前指针在第几个结点处,j0,意思是在头结点处while(p!NULLji-1) //P不能为空,为空咋插入啊,操作不合法,ij的时候跳出循环{pp-next; j; } if(pNULL) return false;if(p-nextNULL) return false;LNode *qp-next; //方便操作搞出了一个q,直接用p也行,就是写起来不直观eq-data;p-nextq-next;free(q);return true;
}bool DeleteNode(LNode *p)
{if(pNULL)return false;LNode *qp-next;p-dataq-data;p-nextq-next;free(q);return true;
}LNode * GetElem(LinkList L,int i)
{if(i0)return NULL;LNode *pL;int j0;while(p!NULLji){pp-next;j;}return p;
}
LNode * LocateElem(LinkList L,int e)
{LNode *pL-next; //从第一个结点处开始查值while(p!NULLp-data!e){pp-next;}return p;
}int Length(LinkList L){int len0; //不包括头结点 LNode *pL;while(p-next!NULL){pp-next;len;}return len;
}
LinkList List_Tailnsert(LinkList L)
{int x;L(LinkList)malloc(sizeof(LNode));LNode *s,*rL;scanf(%d,x);while(x!9999) //输出9999表示结束{s(LNode *)malloc(sizeof(LNode));s-datax;r-nexts;rs;scanf(%d,x);}r-nextNULL;return L;
}LinkList List_Headlnsert(LinkList L)
{int x;L(LinkList)malloc(sizeof(LNode));LNode *s;scanf(%d,x);while(x!9999) //输出9999表示结束{s(LNode *)malloc(sizeof(LNode));s-datax;s-nextL-next;L-nexts;scanf(%d,x);}return L;
}int main()
{InitList();int e-1;
}
