《算法通关村第一关——链表青铜挑战笔记》

这篇具有很好参考价值的文章主要介绍了《算法通关村第一关——链表青铜挑战笔记》。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

第一关——链表

1、青铜挑战——创建+增删改查(c++)

1.1链表的内部结构

链表中每个结点内部的“生态环境”。

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记
数据域存储元素的值,指针域存放指针。
示例:
《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记

1.2链表的定义

struct linkNode
{
	int val;      //代表数据
	struct linkNode *next;  //代表指针
};

1.3理解C 语言里是如何构造出链表

c语言构造链表 可分为三步
1.创建头指针。
2.创建头结点,使头指针指向头结点。
3.循环创建结点,并使前一个结点指向当前结点。
1.)创建结点。
2.)使前一个结点指向当前结点。
3.)前一个结点变为当前节点(为下一次循环准备)。

代码如下:

#include <stdio.h>
#include <stdlib.h>

struct LinkNode
{
	int val;      //代表数据
	struct LinkNode *next;  //代表指针
};

struct LinkNode *initLink()
{
	//1.创建头指针。
	struct LinkNode *p = NULL;
	//2.创建头结点,使头指针指向头结点。
	struct LinkNode *temp = (struct LinkNode *)molloc(sizeof(struct LinkNode));
	p = temp;
	//3.循环创建结点,并使前一个结点指向当前结点。
	for(int i = 0;i < 5;i++)
	{
		 //1.)创建结点。
	 	struct LinkNode *a = (struct LinkNode *)malloc(struct LinkNode);
		a->val = i;
		a->next = NULL;
		//2.)使前一个结点指向当前结点。
		temp->next = a;
		//3.)前一个结点变为当前节点
		temp = temp->next;
	}
	return p;
}

int main()
{
	struct LinkNode * q;
	printf("创建链表1,2,3,4");
	q = initLink();
	return 0;
}

1.4链表增加元素,首部、中间和尾部分别会有什么问题,该如何处理?

1.4.1 首部插入

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记

注意:
要将新插入的结点重新设为head结点。

处理:

NewNode->next = head;
head = NewNode; 

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记

1.4.2 中间插入

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记
注意:
1.要在插入的前一个结点停下(这就好比一边过河一边拆桥,结果自己也回不去了。)
2.要先连要插入位置后面的结点(否则后面的就无法连接了)

处理:

NewNode.next = temp->next;
temp->next = NewNode; 

1.4.3 尾部插入

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记

注意:没什么注意的
处理:

temp->next = NewNode;

1.5链表删除元素,首部、中间和尾部分别会有什么问题,该如何处理?

1.5.1 删除首部

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记

处理:

head = head->next; 

1.5.2 删除中间

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记

注意:用cur.next来比较,找到位置后,将cur->next指针的值更新为cur->next->next。
处理:

cur->next = cur->next->next;

1.5.3 删除尾部

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记
注意:找到要删除位置的前一个结点并判断 是否cur->next = 40
处理:

cur->next = NULL; 

1.6双向链表是如何构造的,如何实现元素的插入和删除

1.6.1 双向链表的如何构造

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记

typedef struct DoubleNode
{
	// 数据域
	int data;
	// 指向下一个结点
	struct DoubleNode *next;
	struct DoubleNode *prev;
}DoubleNode;
//创建新结点
DoubleNode* newNode(int data) 
{
	DoubleNode *newNode = (DoubleNode*)malloc(sizeof(DoubleNode));
	newNode->data = data;
	newNode->next = NULL;
	newNode->prev = NULL;
	return newNode;
}

1.6.1 双向链表的插入

头插

与单链表类似。
注意:
1.让新头结点prev 指向 链表的最后Newhead->prew = head->prew。
2.新头结点next 指向 旧的头结点。
3. 末尾结点next 指向 新头结点
4.旧头结点prev 指向 新头结点。
5.若链表为空,要注意额外处理。


void insertFirst(int p)
{
	DoubleNode *NewNode = (DoubleNode *)malloc(sizeof(DoubleNode));
	NewNode->data = p; 
	if(head == NULL)
		head = NewNode;
	else
	{
		NewNode->prev = head->prev;
		NewNode->next = head;
		NewNode->prev->next = NewNode;
		head->prev = NewNode;
	}
}
尾插

与头插类似。
== 旧尾结点last = head->prew==

void insertlast(int p)
{
    DoubleNode *NewNode = (DoubleNode *)malloc(sizeof(DoubleNode));
    NewNode->data = p; 
    if(head == null){
       head = NewNode;
    }
    else
    {
 	  	NewNode->prev = head->prev;
 	  	NewNode->next = head->prev->next;
		NewNode->next->prev = NewNode;
		head->prev->next = NewNode;
	}
    return head;
}
中间插入

《算法通关村第一关——链表青铜挑战笔记》,学习笔记,算法,链表,笔记
在某个元素之前插入元素

/*在第add位置的前面插入data节点*/
DoubleNode * InsertListHead(DoubleNode * head,int add,int data)
{
    /*新建数据域为data的结点*/
    DoubleNode * NewNode=(DoubleNode*)malloc(sizeof(DoubleNode));
    if(temp== NULL)
    {
        printf("创建错误\n");
        return NULL;
    }    
    else
    {
        NewNode->data = data;
        NewNode->prev = NULL;
        NewNode->next = NULL; 
    }
    /*插入到链表头,要特殊考虑*/
    if (add==1)
    {
        NewNode->next = head;
        head->prev = NewNode;
        head = NewNode;
    }
    else
    {
        Node * body = head;
        /*找到要插入位置的前一个结点*/
        for (int i=1; i<add-1; i++)
        {
            body = body->next;
        }
        /*判断条件为真,说明插入位置为链表尾*/
        if (body->next == NULL)
        {
            NewNode->prev = head->prev;
 	  		NewNode->next = head->prev->next;
			NewNode->next->prev = NewNode;
			head->prev->next = NewNode;
        }
        else
        {
            body->next->pre = NewNode;
            NewNode->next = body->next;
            body->next = NewNode;
            NewNode->pre = body;
        }
    }
    return head;
}

1.6.1 双向链表的删除

双向链表的增删改查要比单链表麻烦很多

头尾删除

头删

DoubleNode *deleteFirst(){
    //头节点判空
    if(head == null){
        printf("链表为空,不可删除");
        return null;
    }
    DoubleNode *temp = first;
    //第二个节点的prev指向尾节点,完成前循环
    head->next->prev = head->prev;
    //尾节点的next指向第二个节点
    head->prev->next = head->next;
    //更新头节点
    head = head->next;
    return temp;
}

尾删

DoubleNode *deleteLast(){
    //首先判空
    if(head == null){
        printf("链表为空,无法删除");
        return null;
    }
    //快速获取尾节点
    DoubleNode last = head->prev;
    //头节点prev指向倒数第二个节点,完成前循环
    head->prev = last->prev;
    //倒数第二个next指向head,完成后循环
    last->prev->next = head;
    return temp;
}
删除中间
DoubleNode * DeleteList(DoubleNode * head,int data)
{
    DoubleNode * temp = head;
    /*遍历链表*/
    while (temp)
    {
        /*判断当前结点中数据域和data是否相等,若相等,删除该结点*/
        if (temp->data == data) 
        {
            /*判断是否是头结点*/
            if(temp->pre == NULL)
            {
                head = temp->next;
                temp->next = NULL;
                free(temp);
                return head;
            }
            /*判断是否是尾节点*/
            else if(temp->next == NULL)
            {
                temp->pre->next = NULL;
                free(temp);
                return head;
            }
            else
            {
                temp->pre->next = temp->next;
                temp->next->pre = temp->pre;
                free(temp);
                return head;   
            }
        }
        //不相等就向后移动
        temp =temp->next;
    }
    printf("没有发现 %d!\n",data);
    return head;
}

第一次发博客,如有错误欢迎指正文章来源地址https://www.toymoban.com/news/detail-609387.html

到了这里,关于《算法通关村第一关——链表青铜挑战笔记》的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法通关村第一关--链表青铜挑战笔记

    开始时间:2023年7月16日20:45:26 什么是链表,链表是一种通过指针串联在一起的线性结构,每一个节点由两部分组成,一个是数据域一个是指针域(存放指向下一个节点的指针),最后一个节点的指针域指向null(空指针的意思)。 链表的入口节点称为链表的头结点也就是hea

    2024年02月17日
    浏览(44)
  • [Go版]算法通关村第一关青铜——链表青铜挑战笔记

    单向链表图示: 双向链表图示: 环形单向链表图示: 环形双向链表图示: 源码地址: GitHub-golang版本 如果是单向的,需要将当前节点 定位到要插入节点的前一个节点 ,否则一旦过了将无法回头找到前一个节点 如果是双向的,将当前节点 定位到要插入节点的前一个节点、

    2024年02月13日
    浏览(39)
  • 算法通关村第一关——链表青铜挑战笔记(单链表)

    在LeeCode中一般这样创建链表 要注意创建一个变量来遍历,不要把head丢掉了 count position - 1可以方便操作,还能防止下标越界(cur为null)

    2024年02月15日
    浏览(38)
  • 【无标题】算法通关村第一关——链表青铜挑战笔记

    算法通关村第一关——链表青铜挑战笔记 C语言是如何构造出链表的 0.定义节点结构 1.建立头指针 2.建立temp指针 3.将节点连起来 3.1 把p指向temp 3.2 设立循环节点a+temp指向a+temp变为a

    2024年02月15日
    浏览(36)
  • [Go版]算法通关村第一关——链表青铜挑战笔记

    单向链表图示: 双向链表图示: 环形单向链表图示: 环形双向链表图示: 源码地址: GitHub-golang版本 如果是单向的,需要将当前节点 定位到要插入节点的前一个节点 ,否则一旦过了将无法回头找到前一个节点 如果是双向的,将当前节点 定位到要插入节点的前一个节点、

    2024年02月15日
    浏览(46)
  • 算法通关存第一关------链表青铜挑战笔记

    如上代码其实就已经构造出了一个链表。 定义一个Node结点类,他有两个属性var,和next。由于next是Node类型,这时候next又会指向同为Node类型的对象,这个对象也拥有var,和next两个属性,由此构造出一个链表。 文章最后会有构造链表实例,完整代码。   2.1 插入结点 在插入链

    2024年02月15日
    浏览(35)
  • 编程导航算法通关村第一关|青铜|链表基础

    JVM有栈区和堆区 栈区:存引用,就是指向实际对象的地址。。 堆区:存的是创建的对象。 定义 规范的链表定义 LeetCode算法题中常用 遍历 插入 删除 结点 结构遍历 插入 从头插入 从尾插入 从某个值为key的节点后面插入 删除 删除头结点 删除尾结点 按值删除

    2024年02月15日
    浏览(41)
  • 算法通关村|青铜挑战----链表

    前言:数据结构的基础:创建+增删改查 学习目标:单链表的创建+增删改查,双链表的创建+增删改查 数据域+指针域 数据域:当前节点的元素值 指针域:当前节点保存的下一个节点的元素的地址,其中最后一个元素的指针域指向null 标准的面向对象的节点的定义: LeetCode中节

    2024年02月15日
    浏览(35)
  • 算法通关村第一关——链表经典问题之双指针笔记

    基本结构 1.寻找中间结点 2.寻找倒数第k个元素 3.旋转链表

    2024年02月14日
    浏览(39)
  • 算法通关村第一关——链表经典问题之双指针专题笔记

    我一直觉得双指针是一个非常好用的方法,在链表中可以使用,在数组中依然可以,很灵活。 1. 寻找中间结点         用两个指针 slow 与 fast 一起遍历链表。slow 一次走一步, fast 一次走两步。那么当 fast 到达链表的末尾时,slow 必然位于中间。 2. 寻找倒数第K个元素 在这

    2024年02月15日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包