第一关——链表
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;
}
尾删文章来源:https://www.toymoban.com/news/detail-609387.html
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模板网!