- 外文名
- Singly Linked List
- 类 型
- 数据结构元素
- 建立过程
- 申请空间、得到数据、建立链接
- 中文名
- 单链表
- 简 介
- 地址任意的存储单元存放数据元素
- 实 质
- 一种链式存取的数据结构
-
单链表
2019-08-05 15:50:59带头结点和不带头结点的单链表 带头结点的单链表,头指针head指向头结点,头结点的值域不包含任何信息,从头结点之后的结点开始存储信息。 头指针head不等于NULL,head->next等于NULL时,链表为空。 ...一、基本概念
带头结点和不带头结点的单链表
带头结点的单链表,头指针head指向头结点,头结点的值域不包含任何信息,从头结点之后的结点开始存储信息。
头指针head不等于NULL,head->next等于NULL时,链表为空。
单链表结点定义
typedef struct LNode{
int data; //data存放结点数据域
struct LNode *next; //指向后继结点的指针
}LNode; //定义单链表结点类型
引入头结点的好处:(1)无论链表是否为空,头指针总指向头结点的非空指针,(2)开始结点的位置存放在头结点的指针域中,所以链表的第一个位置上的操作和其他位置一致,方便
1. 建立单链表
(1)头插法
从一个空表开始,生成新结点,将读到的数据存放到新结点的数据域,然后将新结点插入到当前两边的表头,即头结点之后
(头插法生成的链表中结点的次序和输入数据的顺序不一致)
关键代码:
LNode *s;int x; L=(LinkList)malloc(sizeof(LNode)); //创建头结点 L->next=NULL; //初始链表为空 /*....*/ s=(LNode)malloc(sizeof(LNode)); //创建新结点 s->data=x; s->next=L->next; L->next=s; //将新结点插入表中,L尾头指针
(2)尾插法
将新结点插入到当前链表的表尾,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。
int x; L=(LinkList)malloc(sizeof(LNode)); LNode *s,*r=L; //r为表尾指针 /***/ while(x!=maxSize){ s=(LNode *)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; //r指向新的表尾结点 } r->next=NULL; //尾节点置空 return L;
2.按序号查找结点值(O(n))
在单链表中从第一个结点出发,顺指针next域逐个往下搜索,直到找到第i个结点为止,否则返回最后一个结点指针域NULL;
LNode *GetElem(LinkList L,int i){ int j=1; //计数,初始为1 LNode *p=L->next; //头结点指针赋给p if(i==0) return L; //若i等于0,返回头结点 if(i<1) return NULL; //若i无效,返回NULL while(p&&j<i){ //从第1个结点查找第i个结点 p=p->next; j++; } return p; }
3.按值查找(O(n))
从单链表第一个结点开始,由前往后依次比较表中个结点数据域的值,若某个结点数据域的值等于给定值e,则返回该结点指针;若整个单链表无值相等的结点,则返回NULL;
LNode *Locate(LinkList L,ElemType e){ LNode *p=L->next; while(p!=NULL &&p->data!=e) //从第1个结点开始查找data域为e的结点 p=p->next; return p; //找到后返回该结点指针,否则返回NULL }
4.插入(O(n))
要把x插入到第i个位置,先检查位置是否合法,然后找到待插入位置的前驱结点,即第i-1个结点,再往其后插入新结点
步骤(1)调用序号查找算法GetElem 查找第i-1个结点。假设返回的第i-1个结点为*p
(2)令新结点*s的指针域指向*p的后继结点,
(3)再令结点*P的指针域指向新插入的结点*s
p=GetElem(L,i-1);//查找插入为止的前驱结点 s->next=p->next; //图中1 p->next=s; //图中2
5.删除(O(n))
要删除第i个结点。先检查删除位置的合法性,然后查找表中第i-1个位置,即被删除结点的前驱结点,再将其删除
假设结点*p为找到的被删除结点的前驱结点,为实现这一操作的逻辑关系的变化,仅需修改*p的指针域,即将*p的指针域next指向*q的下一结点
p=GetElem(L,i-1); //查找删除位置的前驱结点 q=p->next; //令q指向被删除结点 p->next=q->next; //将*q结点从链中断开 free(q); //释放结点的存储空间
拓展删除指定结点:
先从表头结点开始顺序找到其前驱结点,然后执行删除
p=p->netx; //令q指向*p的后继结点
p->data=p->next->data; //和后继结点交换数据域
p->next=q->next; //将*q结点从链中断开
free(q)
6.求表长操作
实质为计算数据结点(不含头结点)的个数,需要从第一个开始遍历全部结点。
*p=first->link; int count=0; while(p!=NULL){ p->link;count++; } return count;
#include <stdio.h> #include <stdlib.h> //头插法 #define SIZE 5 #define ERROR 1 #define OK 0 /* 数据元素类型 */ typedef int ListType; /* 单链表结点定义 */ typedef struct LNode { ListType data; // 数据域 struct LNode *next; // 指针域,指向直接后继元素 }LNode; /* 函数的声明 */ LNode *HeadCreateList(void);// 使用头插法创建一个单链表 LNode *TailCreateList(void);// 使用尾插法创建一个单链表 void PrintfList(LNode *L); // 打印输出链表 int main(void) { LNode *L1 = NULL; LNode *L2 = NULL; /* 使用头插法创建单链表 */ L1 = HeadCreateList(); printf("头插法创建的链表为:"); PrintfList(L1); return 0; } LNode *HeadCreateList(void)//头插法 { int i; LNode *L; // 头结点 LNode *s; // 新结点 L->next = NULL; // 此时链表为空 // 创建链表 for (i = 0; i < 5; i++) { // 创建新结点 s = (LNode*)malloc(sizeof(LNode)); s->data = i; // 使用头插法把新元素插入到链表中 s->next = L->next; // 新结点的next指针指向头结点 L->next = s; // 头结点的next指针指向新结点 } return L; } void PrintfList(LNode *L) { LNode *temp = L; while(temp->next) { temp = temp->next; printf("%d ",temp->data); } printf("\n\n"); }
-
创建单链表的头插法与尾插法详解
2018-09-26 20:54:30创建单链表 关于数据结构的入门,就是从顺序表和单链表开始。 我们不讲顺序表,直接从单链表开始我们的数据结构和算法的学习之路。 单链表就是一种特殊的结构体组合而成的数据结构,关于单链表的创建方法有很多种,...创建单链表
关于数据结构的入门,就是从顺序表和单链表开始。
我们不讲顺序表,直接从单链表开始我们的数据结构和算法的学习之路。单链表就是一种特殊的结构体组合而成的数据结构,关于单链表的创建方法有很多种,但都大同小异。
正如这幅图中所表示的那样,单链表就是由可能不连续的数据所组合而成的数据结构。 其中每个数据分为两部分,一部分是数据存储的位置,称为数据域,另外指针所存储的地方,称为指针域。
typedef struct Node { int data; // 存储链表数据 struct Node *next; // 存储结点的地址 }LNode,*Linklist;
在进入创建链表之前,我们先写好主函数的用来输出的输出函数。
void Illustrate(Linklist head) { Linklist tem = head; // 将头指针的地址赋给临时的指针 while (tem->next != NULL) { // 指向最后一个结点的指针域时会停止 tem = tem->next; // 结点不断向后移动 printf("%d\n", tem->data); } } int main() { Linklist head = NULL; // 链表的头指针 head = Creat_list(head); // 创建链表 Illustrate(head); // 输出每个结点的数据域 system("pause"); return 0; }
头插法创建单链表
头插法代码:
Linklist Creat_list(Linklist head) { head = (Linklist)malloc(sizeof(Lnode)); // 为头指针开辟内存空间 Lnode *node = NULL; // 定义新结点 int count = 0; // 创建结点的个数 head->next = NULL; node = head->next; // 将最后一个结点的指针域永远保持为NULL printf("Input the node number: "); scanf("%d", &count); for (int i = 0; i < count; i++) { node = (Linklist)malloc(sizeof(Lnode)); // 为新结点开辟内存空间 node->data = i; // 为新结点的数据域赋值 node->next = head->next; // 将头指针所指向的下一个结点的地址,赋给新创建结点的next head->next = node; // 将新创建的结点的地址赋给头指针的下一个结点 } return head; }
头插法创建链表的根本在于深刻理解最后两条语句
node->next = head->next; // 将头指针所指向的下一个结点的地址,赋给新创建结点的next head->next = node; // 将新创建的结点的地址赋给头指针的下一个结点
创建第一个结点
执行第一次循环时,第一次从堆中开辟一块内存空间给node,此时需要做的是将第一个结点与 head 连接起来。而我们前面已经说过,单链表的最后一个结点指向的是 NULL。
因此插入第一个结点时,我们需要将头指针指向的 next 赋给新创建的结点的 next , 这样第一个插入的结点的 next 指向的就是 NULL。 接着,我们将数据域,也就是 node 的地址赋给 head->next, 这时 head->next 指向的就是新创建的 node的地址。而 node 指向的就是 NULL。
接着我们创建第二个结点
因为使用的头插法,因此新开辟的内存空间需要插入 头指针所指向的下一个地址,也就是新开辟的 node 需要插入 上一个 node 和 head 之间。 第一个结点创建之后,head->next 的地址是 第一个 node 的地址。 而我们申请到新的一块存储区域后,需要将 node->next 指向 上一个结点的首地址, 而新node 的地址则赋给 head->next。 因此也就是 node->next = head->next 。
这样便将第一个结点的地址赋给了新创建地址的 next 所指向的地址。后两个结点就连接起来。接下来再将头结点的 next 所指向的地址赋为 新创建 node 的地址。 head->next = node ,这样就将头结点与新创建的结点连接了起来。 此时最后一个结点,也就是第一次创建的结点的数据域为0,指针域为 NULL。
创建更多的结点也就不难理解。
执行一次:
会发现,头插法创建链表时候,就相当于后来居上。 后面的结点不断往前插,而最后创建的结点在第一个结点处, 第一个创建的结点变成了尾结点。
尾插法创建单链表
尾插法代码:
Linklist Creat_list(Linklist head) { head = (Linklist)malloc(sizeof(Lnode)); // 为头指针开辟内存空间 Linklist node = NULL; // 定义结点 Linklist end = NULL; // 定义尾结点 head->next = NULL; // 初始化头结点指向的下一个地址为 NULL end = head; // 未创建其余结点之前,只有一个头结点 int count = 0 ; // 结点个数 printf("Input node number: "); scanf("%d", &count); for (int i = 0; i < count; i++) { node = (Linklist)malloc(sizeof(Lnode)); // 为新结点开辟新内存 node->data = i; // 新结点的数据域赋值 end->next = node; end = node; } end->next = NULL; }
尾插法深刻理解:
end->next = node; end = node;
尾插法创建第一个结点
刚开始为头结点开辟内存空间,因为此时除过头结点没有新的结点的建立,接着将头结点的指针域 head->next 的地址赋为 NULL。因此此时,整个链表只有一个头结点有效,因此 head此时既是头结点,又是尾结点。因此将头结点的地址赋给尾结点 end 因此:end = head。 此时end 就是 head, head 就是 end。 end->next 也自然指向的是 NULL。
尾插法创建第二个结点
创建完第一个结点之后,我们入手创建第二个结点。 第一个结点,end 和 head 共用一块内存空间。现在从堆中心开辟出一块内存给 node,将 node 的数据域赋值后,此时 end 中存储的地址是 head 的地址。此时,end->next 代表的是头结点的指针域,因此 end->next = node 代表的就是将上一个,也就是新开辟的 node 的地址赋给 head 的下一个结点地址。
此时,end->next 的地址是新创建的 node 的地址,而此时 end 的地址还是 head 的地址。 因此 end = node ,这条作用就是将新建的结点 node 的地址赋给尾结点 end。 此时 end 的地址不再是头结点,而是新建的结点 node。
一句话,相当于不断开创新的结点,然后不断将新的结点的地址当做尾结点。尾结点不断后移,而新创的结点时按照创建的先后顺序而连接的。先来新到。
尾插法创建单链表,结点创建完毕
最后,当结点创建完毕,最后不会有新的结点来替换 end ,因此最后需要加上一条 end->next = NULL。将尾指针的指向为 NULL。
创建更多结点也自然容易理解了一些。
执行一次:
总结
由上面的例子以及比较,我们可以看见:
- 头插法相对简便,但插入的数据与插入的顺序相反;
- 尾插法操作相对复杂,但插入的数据与插入顺序相同。
两种创建的方法各有千秋,根据实际情况选择不同的方法。
关于链表的相关其他操作,请浏览相关文档。
-
无环单链表+有环单链表(有环单链表+无环单链表)
2020-06-03 16:35:16 -
Java基础--单链表的实现
2019-03-25 20:57:42Java内部也有自己的链表--LinkedList,但是我们今天不是讨论LinkedList,而是自己来实现一个单链表,包括简单的增删查改,以及使用链表来实现栈和队列这两种数据结构,涉及的方面如下: 单链表的结构 单链表的...Java内部也有自己的链表--LinkedList,但是我们今天不是讨论LinkedList,而是自己来实现一个单链表,包括简单的增删查改:
- 单链表的结构
- 单链表的基本操作
- 虚拟头结点的使用
整个类的设计如下:
public class Linked <T>{ private class Node{ private T t; private Node next; public Node(T t,Node next){ this.t = t; this.next = next; } public Node(T t){ this(t,null); } } private Node head; //头结点 private int size; //链表元素个数 //构造函数 public Linked(){ this.head = null; this.size = 0; } }
单链表的结构
一种链式存取的数据结构,单链表中的数据是以结点的形式存在,每一个结点是由数据元素和下一个结点的存储的位置组成。单链表与数组相比的最大差别是:单链表的数据元素存放在内存空间的地址是不连续的,而数组的数据元素存放的地址在内存空间中是连续的,这也是为什么根据索引无法像数组那样直接就能查询到数据元素。
[单链表结构图]链表存储的结点
private class Node{ private T t; private Node next; public Node(T t,Node next){ this.t = t; this.next = next; } public Node(T t){ this(t,null); } }
链表的基本操作
包括链表的增删查改,以及判别某结点是否存在链表中链表结点的增加
进行结点的添加的时候,是根据索引来进行操作的,由于成员变量size记录了当前链表的元素个数,进行某个索引位置的结点插入就会很方便了。先找到该目标索引的前一个结点,记录为pre,把要插入的结点node的下一个结点node.next指向pre的下一个结点pre.next;再把pre.next指向node结点。如果先进行pre.next指向要插入的结点,再进行node.next指向pre.next的话,无疑是要插入的结点自己指向了自己,无法连接上整个链表,在链表的操作中,有时候顺序的执行会带来不一样的结果。
//链表头部添加元素 public void addFirst(T t){ Node node = new Node(t); //节点对象 node.next = this.head; this.head = node; //this.head = new Node(e,head);等价上述代码 this.size++; } //向链表尾部插入元素 public void addLast(T t){ this.add(t, this.size); } //向链表中间插入元素 public void add(T t,int index){ if (index <0 || index >size){ throw new IllegalArgumentException("index is error"); } if (index == 0){ this.addFirst(t); return; } Node preNode = this.head; //找到要插入节点的前一个节点 for(int i = 0; i < index-1; i++){ preNode = preNode.next; } Node node = new Node(t); //要插入的节点的下一个节点指向preNode节点的下一个节点 node.next = preNode.next; //preNode的下一个节点指向要插入节点node preNode.next = node; this.size++; }
链表结点的删除
//删除链表元素 public void remove(T t){ if(head == null){ System.out.println("无元素可删除"); return; } //要删除的元素与头结点的元素相同 while(head != null && head.t.equals(t)){ head = head.next; this.size--; } /** * 上面已经对头节点判别是否要进行删除 * 所以要对头结点的下一个结点进行判别 */ Node cur = this.head; while(cur != null && cur.next != null){ if(cur.next.t.equals(t)){ this.size--; cur.next = cur.next.next; } else cur = cur.next; } }
在进行链表的结点删除时候,要分情况讨论:
当要删除的结点位于头结点的时候:如下图要删除的元素1的结点位于头结点,先进行while判断头结点是否为null且判断该结点的元素是否为要删除的元素,如果是把head指向head.next即可,直接跳过头结点,直到头结点不是要删除的元素就结束循环。[要删除的元素1位于头结点]
当要删除的结点不在头结点的时候:如下图删除元素为3的结点,由于上面已经判断了头结点不是要删除的元素,所以我们从头结点的下一个结点开始循环,即cur.next,当cur.next是要被删除的元素时,直接cur.next = curr.next.next就能直接跳过cur.next,断开。
[要删除结点的元素为3的结点]
删除链表的头结点的元素和删除链表的尾结点的元素
//删除链表第一个元素 public T removeFirst(){ if(this.head == null){ System.out.println("无元素可删除"); return null; } Node delNode = this.head; this.head = this.head.next; delNode.next =null; this.size--; return delNode.t; } //删除链表的最后一个元素 public T removeLast(){ if(this.head == null){ System.out.println("无元素可删除"); return null; } //只有一个元素 if(this.getSize() == 1){ return this.removeFirst(); } Node cur = this.head; //记录当前结点 Node pre = this.head; //记录要删除结点的前一个结点 while(cur.next != null){ pre = cur; cur = cur.next; } pre.next = cur.next; this.size--; return cur.t; }
经过上面在进行链表的结点删除的时候,会发现在删除的过程中很麻烦,还得考虑头结点(因为我们在删除结点的时候,都是先找到待删除结点del的前一个结点pre,然后直接进行跳过操作,即pre.next = pre.next.next,但是删除结点头结点的时候就无法操作),给我们添加了麻烦,为此我们可以给链表添加一个虚拟的头结点,说白了就是重新new一个结点对象,该结点对象的下一个结点指向了我们之前的头结点,让我们在删除结点的时候,无须再考虑之前的头结点了!
虚拟头结点删除链表元素的实现
//加入虚拟头结点的链表进行删除 public void removeElt(T t){ //构造虚拟头结点,并且下一个结点指向head Node dummy = new Node(t,this.head); //声明结点指向虚拟头结点 Node cur = dummy; //从虚拟头结点的下一个结点开始遍历 while(cur.next != null){ if(cur.next.t.equals(t)){ cur.next = cur.next.next; this.size--; } else cur = cur.next; } //去除虚拟头结点 this.head = dummy.next; }
使用虚拟头结点进行链表的插入
刚开始那部分的结点添加是基于索引的情况实现,当我们无法知道一个结点的位于链表的哪个位置时候,只知道要插入在某个元素的前面,下面的代码基于上述情况实现。
/** * * @param t:插入在t元素的位置 * @param des:要插入的元素 */ public void insert(T t,T des){ //构造虚拟头结点,并且下一个结点指向head Node dummy = new Node(null,this.head); //构造要插入的结点 Node dNode = new Node(des); //声明变量cur指向虚拟头结点 Node cur = dummy; while(cur.next != null){ if(cur.next.t.equals(t)){ dNode.next = cur.next; cur.next = dNode; this.size++; break; } else cur = cur.next; } this.head = dummy.next; }
查找某个元素是否在链表的结点上
//链表中是否包含某个元素 public boolean contains(T t){ Node cur = this.head; while(cur != null){ if(cur.t.equals(t)){ return true; } else cur = cur.next; } return false; }
完整的代码实现:
package LinkedList; public class Linked <T>{ private class Node{ private T t; private Node next; public Node(T t,Node next){ this.t = t; this.next = next; } public Node(T t){ this(t,null); } } private Node head; //头结点 private int size; //链表元素个数 //构造函数 public Linked(){ this.head = null; this.size = 0; } //获取链表元素的个数 public int getSize(){ return this.size; } //判断链表是否为空 public boolean isEmpty(){ return this.size == 0; } //链表头部添加元素 public void addFirst(T t){ Node node = new Node(t); //节点对象 node.next = this.head; this.head = node; // this.head = new Node(e,head);等价上述代码 this.size++; } //向链表尾部插入元素 public void addLast(T t){ this.add(t, this.size); } //向链表中间插入元素 public void add(T t,int index){ if (index <0 || index >size){ throw new IllegalArgumentException("index is error"); } if (index == 0){ this.addFirst(t); return; } Node preNode = this.head; //找到要插入节点的前一个节点 for(int i = 0; i < index-1; i++){ preNode = preNode.next; } Node node = new Node(t); //要插入的节点的下一个节点指向preNode节点的下一个节点 node.next = preNode.next; //preNode的下一个节点指向要插入节点node preNode.next = node; this.size++; } //删除链表元素 public void remove(T t){ if(head == null){ System.out.println("无元素可删除"); return; } //要删除的元素与头结点的元素相同 while(head != null && head.t.equals(t)){ head = head.next; this.size--; } /** * 上面已经对头节点判别是否要进行删除 * 所以要对头结点的下一个结点进行判别 */ Node cur = this.head; while(cur != null && cur.next != null){ if(cur.next.t.equals(t)){ this.size--; cur.next = cur.next.next; } else cur = cur.next; } } //删除链表第一个元素 public T removeFirst(){ if(this.head == null){ System.out.println("无元素可删除"); return null; } Node delNode = this.head; this.head = this.head.next; delNode.next =null; this.size--; return delNode.t; } //删除链表的最后一个元素 public T removeLast(){ if(this.head == null){ System.out.println("无元素可删除"); return null; } //只有一个元素 if(this.getSize() == 1){ return this.removeFirst(); } Node cur = this.head; //记录当前结点 Node pre = this.head; //记录要删除结点的前一个结点 while(cur.next != null){ pre = cur; cur = cur.next; } pre.next = cur.next; this.size--; return cur.t; } //链表中是否包含某个元素 public boolean contains(T t){ Node cur = this.head; while(cur != null){ if(cur.t.equals(t)){ return true; } else cur = cur.next; } return false; } @Override public String toString() { StringBuffer sb = new StringBuffer(); Node cur = this.head; while(cur != null){ sb.append(cur.t+"->"); cur = cur.next; } sb.append("NULL"); return sb.toString(); } public static void main(String[] args) { Linked<Integer> linked = new Linked(); for(int i = 0; i < 10; i++){ linked.addFirst(i); System.out.println(linked); } linked.addLast(33); linked.addFirst(33); linked.add(33, 5); System.out.println(linked); linked.remove(33); System.out.println(linked); System.out.println("删除第一个元素:"+linked.removeFirst()); System.out.println(linked); System.out.println("删除最后一个元素:"+linked.removeLast()); System.out.println(linked); } }
总结:学链表是一种痛苦,但是痛苦并快乐着,希望能够坚持下去,把链表的全家桶都学习了,而不是这么简单的增加和删除。上述如有说的不对的地方欢迎指正!下篇文章将进行用链表实现栈和队列。
-
qBittorrentEE_v4.3.1.11_便携版.zip
-
聊聊nacos-coredns-plugin的UDPServer
-
Algorithm_BaekJoon:백준리즘제문-源码
-
Web前端开发规范手册.rar
-
《Unix/Linux编程实践教程》chapter8 进程和程序:编写命令解释器sh
-
OC.Gen-X.2.9.2.dmg
-
安卓开发淘宝抢购界面!史上最全的Android面试题集锦,附带学习经验
-
项目经理成长之路
-
2014阿里巴巴校园招聘数据分析师职位笔试题目(回忆版).pdf
-
鸿蒙系统Harmonyos源码架构分析-第1期第2课
-
docker-compose搭建高可用redis哨兵集群读写分离,并用SpringBoot连接CRUD
-
存疑PATA1059(已解决)哈希素数表范围
-
neuqacm技术组周会-python爬虫实战
-
数据研究必备:国内40个免费数据源.pdf
-
凡客诚品 微博营销实践暨品牌创新.ppt
-
计算工资
-
安卓开发面试自我介绍!Android中高级面试必知必会,持续更新中
-
MySQL 性能优化(思路拓展及实操)
-
安卓开发环境配置!十年开发经验Android架构师,最强技术实现
-
svg_pnf_Selector-源码