当前位置：网站首页>Su embedded training - Day9
Su embedded training - Day9
2022-07-08 00:59:00 【Light chasing rain】
List of articles
- One Single chain list
- 1.1 Concept
- 1.2 Operation of Single Chain Watch
- 1.2.1 Define the node structure
- 1.2.2 Create an empty single chain table
- 1.2.3 Insert data by head interpolation
- 1.2.4 Traversing a single linked list
- 1.2.5 Tail interpolation inserts data
- 1.2.6 Determine whether the single chain table is empty
- 1.2.7 Delete data by header deletion （ Return deleted data ）
- 1.2.8 Modify the data according to the data
- 1.2.9 Find data by location
- 1.2.10 Find location by data
- 1.2.11 Insert data by location
- 1.2.12 Direct insert sort
- practice ： Realize the inversion of single chain table
- practice : Delete the whole table of the single linked list
- 1.3 The overall code
- Two One way circular list
One Single chain list
1.1 Concept
Single chain list ： Chain storage of linear table
The linear table ： One-to-one relationship
Chain store ： There is no need to open up a continuous memory space in memory , So every data is no longer a basic data , It consists of two parts , Data fields and pointer fields , Data fields hold data , The pointer field saves the address of the next node .
Single chain list ： It's a one-way linked list , The former node can find the latter node , But the latter cannot find the former .
1.2 Operation of Single Chain Watch
1.2.1 Define the node structure
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
// Define data types
typedef int DataType;
// Define the node structure
typedef struct linklist
{
DataType data; // Data fields
struct linklist *next; // Pointer to the domain , In order to operate the following nodes
// So the type of pointer is the type of current structure
}linklist;
#endif
1.2.2 Create an empty single chain table
// Create an empty single chain table
linklist* LinkListCreate()
{
// Define a header node , Open up space in the stack area
linklist *head = (linklist *)malloc(sizeof(linklist));
// The initialization pointer field ID is null
head->next = NULL;
return head;
}
1.2.3 Insert data by head interpolation
// Insert data by head interpolation
void LinkListInsertHead(linklist *head,DataType value)
{
// Open up space , Assign a new node
linklist *tmp = (linklist *)malloc(sizeof(linklist));
tmp->data = value;
tmp->next = NULL;
// Point the pointer field of the node to be inserted to the first node
// The address of the first node ：head->next
// The pointer field of the newly inserted node ：tmp->next
tmp->next = head->next;
// The pointer field of the head node saves the address of the node to be inserted
// Pointer field of the header node ：head->next
// The address of the newly inserted node ：tmp
head->next = tmp;
return;
}
1.2.4 Traversing a single linked list
// Traversing a single linked list
void LinkListPrint(linklist *head)
{
// Define a pointer to save the address of the first node
linklist *p = head->next;
while(p != NULL)
{
// Print data
printf("%d ",p->data);
//p Point to the next node （p Save the address of the next node ）
p = p->next;
}
putchar(10);
}
1.2.5 Tail interpolation inserts data
// Tail interpolation inserts data
void LinkListInsertTail(linklist *head,DataType value)
{
// To apply for space , Assign node structure
linklist *tmp = (linklist *)malloc(sizeof(linklist));
tmp->data = value;
tmp->next = NULL;
// Find the last node
linklist *p = head;
while(p->next != NULL)
{
p = p->next;
}
// Save the newly inserted node after the last node
p->next = tmp;
// Point the pointer field of the newly inserted node to NULL
tmp->next = NULL;
return;
}
1.2.6 Determine whether the single chain table is empty
// Determine whether the single chain table is empty
int LinkListIsEmpty(linklist *head)
{
return head->next == NULL ? 1 : 0;
}
1.2.7 Delete data by header deletion （ Return deleted data ）
// Head deletion , Return deleted data
DataType LinkListDeleteHead(linklist *head)
{
if(LinkListIsEmpty(head))
{
printf(" Delete failed , Single linked list is empty ！\n");
return (DataType)-1;
}
DataType value = head->next->data;
linklist *tmp = head->next;
head->next = head->next->next;
free(tmp);
tmp = NULL;
return value;
}
1.2.8 Modify the data according to the data
void LinkListUpdate(linklist *head,DataType OldValue,DataType NewValue)
{
if(LinkListIsEmpty(head))
{
printf(" Failed to modify data , Linked list is empty. ");
return;
}
linklist *p = head;
int flags = 0;
while(p->next != NULL)
{
p = p->next;
if(p->data == OldValue)
{
p->data = NewValue;
flags = 1;
}
}
if(flags == 0)
{
printf(" data %d non-existent , Modification failed \n",OldValue);
}
return;
}
1.2.9 Find data by location
// Find data by location
DataType LinklistSearchData(linklist *head,int pos)
{
if(LinkListIsEmpty(head))
{
printf(" To find the failure , Linked list is empty. ！\n");
}
if(pos < 1)
{
printf(" The position is wrong ！\n");
}
linklist *p = head;
int i;
for(i = 1; i <= pos;i++)
{
if(p == NULL)
{
printf(" Wrong input position ！\n");
return (DataType)-1;
}
p = p->next;
}
return p->data;
}
1.2.10 Find location by data
// Find location by data
int LinkListSearchPos(linklist *head,DataType value)
{
if(LinkListIsEmpty(head))
{
printf(" Failed to find the location , Linked list is empty. ！\n");
return (DataType)-1;
}
linklist *p = head;
int pos = 0;
while(p->next != NULL)
{
p = p->next;
pos++;
if(p->data == value)
{
return pos;
}
}
printf(" Failed to find the location ！\n");
return (DataType)-1;
}
1.2.11 Insert data by location
// Insert data by location
void LinkListInsertByPos(linklist *head,int pos,DataType value)
{
if(pos < 1)
{
printf(" Error inserting data by position ");
return;
}
linklist *tmp = (linklist *)malloc(sizeof(linklist));
tmp->data = value;
tmp->next = NULL;
if(LinkListIsEmpty(head))
{
tmp->next = head->next;
head->next = tmp;
}
else
{
int i;
linklist *p = head;
for(i = 0 ; i < pos ;i++)
{
if(p->next == NULL)
{
printf(" The position is wrong ！\n");
return;
}
p = p->next;
}
tmp->next = p->next;
p->next = tmp;
}
}
1.2.12 Direct insert sort
// Direct insert sort
void LinkListInsertSort(linklist *head,DataType value)
{
linklist *tmp = (linklist *)malloc(sizeof(linklist));
tmp->data = value;
tmp->next = NULL;
linklist *p = head;
while(p->next != NULL && p->next->data < tmp->data)
{
p = p->next;
}
tmp->next = p->next;
p->next = tmp;
}
practice ： Realize the inversion of single chain table
h1: 10->20->30->40->NULL
…
h2:40->30->20->10->NULL
// Single list flip
void LinkListReverse(linklist *head)
{
if(LinkListIsEmpty(head))
{
printf(" Linked list is empty. , No need to flip ！\n");
return;
}
linklist *h1 = LinkListCreate();
linklist *p = head;
DataType value;
while(p->next != NULL)
{
value = LinkListDeleteHead(head);
LinkListInsertHead(h1,value);
}
head->next= h1->next;
}
// Single list flip 2
void LinkListReverse2(linklist *head)
{
if(LinkListIsEmpty(head))
{
printf(" Linked list is empty. , No need to flip ！\n");
return;
}
// Define two pointer variables to flip the linked list
linklist *p = NULL, *q = NULL;
//p The pointer saves the address of the first node
p = head->next;
// Head node pointing NULL
head->next = NULL;
while(p != NULL)
{
//q Pointer save p The address of the node pointed to
q = p;
p = p->next;
// Head inserting method q Insert into head In the list
q->next = head->next;
head->next = q;
}
}
practice : Delete the whole table of the single linked list
// Delete the whole table of the single linked list
void LinkListClear(linklist *head)
{
linklist *p = NULL,*q = NULL;
p = head->next;
while(p != NULL)
{
q = p->next;
free(p);
p = q;
}
head->next = NULL;
}
1.3 The overall code
1.3.1 linklist.h
// The header file
#ifndef _LINKLIST_H_
#define _LINKLIST_H_
#include <stdio.h>
#include <stdlib.h>
// Define data types
typedef int DataType;
// Define the node structure
typedef struct linklist
{
DataType data; // Data fields
struct linklist *next; // Pointer to the domain , In order to operate the following nodes
// So the type of pointer is the type of current structure
}linklist;
// Create an empty single chain table
linklist* LinkListCreate();
// Insert data by head interpolation
void LinkListInsertHead(linklist *head,DataType value);
// Traversing a single linked list
void LinkListPrint(linklist *head);
// Tail interpolation inserts data
void LinkListInsertTail(linklist *head,DataType value);
// Determine whether the single chain table is empty
int LinkListIsEmpty(linklist *head);
// Head deletion , Return deleted data
DataType LinkListDeleteHead(linklist *head);
// Modify the data according to the data
void LinkListUpdate(linklist *head,DataType OldValue,DataType NewValue);
// Find data by location
DataType LinklistSearchData(linklist *head,int pos);
// Find location by data
int LinkListSearchPos(linklist *head,DataType value);
// Insert data by location
void LinkListInsertByPos(linklist *head,int pos,DataType value);
// Direct insert sort
void LinkListInsertSort(linklist *head,DataType value);
// Single list flip
void LinkListReverse(linklist *head);
// Single list flip 2
void LinkListReverse2(linklist *head);
// Delete the whole table of the single linked list
void LinkListClear(linklist *head);
#endif
1.3.2 linklist.c
// Function function
#include "linklist.h"
// Create an empty single chain table
linklist* LinkListCreate()
{
// Define a header node , Open up space in the stack area
linklist *head = (linklist *)malloc(sizeof(linklist));
// The initialization pointer field ID is null
head->next = NULL;
return head;
}
// Insert data by head interpolation
void LinkListInsertHead(linklist *head,DataType value)
{
// Open up space , Assign a new node
linklist *tmp = (linklist *)malloc(sizeof(linklist));
tmp->data = value;
tmp->next = NULL;
// Point the pointer field of the node to be inserted to the first node
// The address of the first node ：head->next
// The pointer field of the newly inserted node ：tmp->next
tmp->next = head->next;
// The pointer field of the head node saves the address of the node to be inserted
// Pointer field of the header node ：head->next
// The address of the newly inserted node ：tmp
head->next = tmp;
return;
}
// Traversing a single linked list
void LinkListPrint(linklist *head)
{
// Define a pointer to save the address of the first node
linklist *p = head->next;
while(p != NULL)
{
// Print data
printf("%d ",p->data);
//p Point to the next node （p Save the address of the next node ）
p = p->next;
}
putchar(10);
}
// Tail interpolation inserts data
void LinkListInsertTail(linklist *head,DataType value)
{
// To apply for space , Assign node structure
linklist *tmp = (linklist *)malloc(sizeof(linklist));
tmp->data = value;
tmp->next = NULL;
// Find the last node
linklist *p = head;
while(p->next != NULL)
{
p = p->next;
}
// Save the newly inserted node after the last node
p->next = tmp;
// Point the pointer field of the newly inserted node to NULL
tmp->next = NULL;
return;
}
// Determine whether the single chain table is empty
int LinkListIsEmpty(linklist *head)
{
return head->next == NULL ? 1 : 0;
}
// Head deletion , Return deleted data
DataType LinkListDeleteHead(linklist *head)
{
if(LinkListIsEmpty(head))
{
printf(" Delete failed , Single linked list is empty ！\n");
return (DataType)-1;
}
DataType value = head->next->data;
linklist *tmp = head->next;
head->next = head->next->next;
free(tmp);
tmp = NULL;
return value;
}
// Modify the data according to the data
void LinkListUpdate(linklist *head,DataType OldValue,DataType NewValue)
{
if(LinkListIsEmpty(head))
{
printf(" Failed to modify data , Linked list is empty. ");
return;
}
linklist *p = head;
int flags = 0;
while(p->next != NULL)
{
p = p->next;
if(p->data == OldValue)
{
p->data = NewValue;
flags = 1;
}
}
if(flags == 0)
{
printf(" data %d non-existent , Modification failed \n",OldValue);
}
return;
}
// Find data by location
DataType LinklistSearchData(linklist *head,int pos)
{
if(LinkListIsEmpty(head))
{
printf(" To find the failure , Linked list is empty. ！\n");
}
if(pos < 1)
{
printf(" The position is wrong ！\n");
}
linklist *p = head;
int i;
for(i = 1; i <= pos;i++)
{
if(p == NULL)
{
printf(" Wrong input position ！\n");
return (DataType)-1;
}
p = p->next;
}
return p->data;
}
// Find location by data
int LinkListSearchPos(linklist *head,DataType value)
{
if(LinkListIsEmpty(head))
{
printf(" Failed to find the location , Linked list is empty. ！\n");
return (DataType)-1;
}
linklist *p = head;
int pos = 0;
while(p->next != NULL)
{
p = p->next;
pos++;
if(p->data == value)
{
return pos;
}
}
printf(" Failed to find the location ！\n");
return (DataType)-1;
}
// Insert data by location
void LinkListInsertByPos(linklist *head,int pos,DataType value)
{
if(pos < 1)
{
printf(" Error inserting data by position ");
return;
}
linklist *tmp = (linklist *)malloc(sizeof(linklist));
tmp->data = value;
tmp->next = NULL;
if(LinkListIsEmpty(head))
{
tmp->next = head->next;
head->next = tmp;
}
else
{
int i;
linklist *p = head;
for(i = 0 ; i < pos ;i++)
{
if(p->next == NULL)
{
printf(" The position is wrong ！\n");
return;
}
p = p->next;
}
tmp->next = p->next;
p->next = tmp;
}
}
// Direct insert sort
void LinkListInsertSort(linklist *head,DataType value)
{
linklist *tmp = (linklist *)malloc(sizeof(linklist));
tmp->data = value;
tmp->next = NULL;
linklist *p = head;
while(p->next != NULL && p->next->data < tmp->data)
{
p = p->next;
}
tmp->next = p->next;
p->next = tmp;
}
// Single list flip
void LinkListReverse(linklist *head)
{
if(LinkListIsEmpty(head))
{
printf(" Linked list is empty. , No need to flip ！\n");
return;
}
linklist *h1 = LinkListCreate();
linklist *p = head;
DataType value;
while(p->next != NULL)
{
value = LinkListDeleteHead(head);
LinkListInsertHead(h1,value);
}
head->next= h1->next;
}
// Single list flip 2
void LinkListReverse2(linklist *head)
{
if(LinkListIsEmpty(head))
{
printf(" Linked list is empty. , No need to flip ！\n");
return;
}
// Define two pointer variables to flip the linked list
linklist *p = NULL, *q = NULL;
//p The pointer saves the address of the first node
p = head->next;
// Head node pointing NULL
head->next = NULL;
while(p != NULL)
{
//q Pointer save p The address of the node pointed to
q = p;
p = p->next;
// Head inserting method q Insert into head In the list
q->next = head->next;
head->next = q;
}
}
// Delete the whole table of the single linked list
void LinkListClear(linklist *head)
{
linklist *p = NULL,*q = NULL;
p = head->next;
while(p != NULL)
{
q = p->next;
free(p);
p = q;
}
head->next = NULL;
}
1.3.3 main.c
//main.c
#include "linklist.h"
int main(int argc, char const *argv[])
{
linklist *head = LinkListCreate();
int i;
for(i= 0 ; i < 10;i++)
{
LinkListInsertHead(head,i + 1);
}
LinkListPrint(head);
for(; i < 20;i++)
{
LinkListInsertTail(head,i + 1);
}
LinkListPrint(head);
for(i = 0 ; i < 5;i++)
{
LinkListDeleteHead(head);
}
LinkListPrint(head);
LinkListUpdate(head,11,999);
LinkListPrint(head);
printf(" Location 4 The data is %d\n",LinklistSearchData(head,4));
printf(" The data is 999 The location of the for %d\n",LinkListSearchPos(head,9999));
LinkListInsertByPos(head,3,777);
LinkListPrint(head);
LinkListInsertSort(head,9);
LinkListInsertSort(head,188);
LinkListInsertSort(head,12);
LinkListInsertSort(head,0);
LinkListInsertSort(head,6);
LinkListPrint(head);
LinkListReverse(head);
LinkListPrint(head);
LinkListReverse2(head);
LinkListPrint(head);
LinkListClear(head);
LinkListInsertSort(head,9);
LinkListInsertSort(head,188);
LinkListInsertSort(head,12);
LinkListInsertSort(head,0);
LinkListInsertSort(head,6);
LinkListPrint(head);
return 0;
}
Two One way circular list
2.1 Concept
2.2 Operation of one-way circular list
Define the node structure
Create an empty one-way circular linked list
insert data
Print data
Delete header node
Print data
2.2.1 Define the node structure
// Define data types
typedef int DataType;
// Define the node structure
typedef struct looplist
{
DataType data;
struct looplist *next;
}looplist;
2.2.2 Create an empty one-way circular linked list
// Create an empty one-way circular linked list
looplist* LoopListCreate()
{
looplist *head = (looplist *)malloc(sizeof(looplist));
// The initial state is cycle
// The pointer field of the header node stores the address of the header node
head->next = head;
return head;
}
2.2.3 insert data
// insert data
void LoopListInsert(looplist *head,DataType value)
{
looplist *tmp = (looplist *)malloc(sizeof(looplist));
tmp->next = NULL;
tmp->data = value;
tmp->next = head->next;
head->next = tmp;
return;
}
2.2.4 Traversing a one-way circular list
// Traversing a one-way circular list
void LoopListPrint(looplist *head)
{
looplist *p = head;
while(p->next != head)
{
p = p->next;
printf("%d ",p->data);
}
putchar(10);
}
2.2.5 Delete header node
// Delete header node
looplist* LoopListCutHead(looplist *head)
{
looplist *p = head;
while(p->next != head)
{
p = p->next;
}
p->next = head->next;
free(head);
head = NULL;
return p->next;
}
2.2.6 Head node traversal
// Go to the head node to traverse the one-way circular linked list
void LoopListPrint2(looplist *head)
{
looplist *p = head;
while(p->next != head)
{
printf("%d ",p->data);
p = p->next;
}
printf("%d\n",p->data);
}
2.3 Homework joseph problem
Set the numbers as ：1,2…n A circle of individuals , The agreed serial number is k（1 <=k<=n） People count from the beginning , Count to m The people of , His next one is from 1 Start counting , Count to m I'm going out again , By analogy , Until everyone is on the line
for example ：n = 8,k = 3,m = 4
2.4 Complete code
2.4.1 looplist.h
#ifndef _LOOPLIST_H_
#define _LOOPLIST_H_
#include <stdio.h>
#include <stdlib.h>
// Define data types
typedef int DataType;
// Define the node structure
typedef struct looplist
{
DataType data;
struct looplist *next;
}looplist;
// Create an empty one-way circular linked list
looplist* LoopListCreate();
// insert data
void LoopListInsert(looplist *head,DataType value);
// Traversing a single linked list
void LoopListPrint(looplist *head);
// Delete header node
looplist* LoopListCutHead(looplist *head);
// Go to the head node to traverse the one-way circular linked list
void LoopListPrint2(looplist *head);
#endif
2.4.2 main.c
//main.c
#include "looplist.h"
int main(int argc, char const *argv[])
{
looplist *head = LoopListCreate();
int i;
for(i = 0 ; i < 10;i++)
{
LoopListInsert(head,i + 1);
}
LoopListPrint(head);
head = LoopListCutHead(head);
LoopListPrint2(head);
return 0;
}
2.4.3 looplist.c
//looplist.c
#include "looplist.h"
// Create an empty one-way circular linked list
looplist* LoopListCreate()
{
looplist *head = (looplist *)malloc(sizeof(looplist));
// The initial state is cycle
// The pointer field of the header node stores the address of the header node
head->next = head;
return head;
}
// insert data
void LoopListInsert(looplist *head,DataType value)
{
looplist *tmp = (looplist *)malloc(sizeof(looplist));
tmp->next = NULL;
tmp->data = value;
tmp->next = head->next;
head->next = tmp;
return;
}
// Traversing a one-way circular list
void LoopListPrint(looplist *head)
{
looplist *p = head;
while(p->next != head)
{
p = p->next;
printf("%d ",p->data);
}
putchar(10);
}
// Delete header node
looplist* LoopListCutHead(looplist *head)
{
looplist *p = head;
while(p->next != head)
{
p = p->next;
}
p->next = head->next;
free(head);
head = NULL;
return p->next;
}
// Go to the head node to traverse the one-way circular linked list
void LoopListPrint2(looplist *head)
{
looplist *p = head;
while(p->next != head)
{
printf("%d ",p->data);
p = p->next;
}
printf("%d\n",p->data);
}
边栏推荐
- Kubernetes static pod (static POD)
- 3.MNIST数据集分类
- C＃ ?,?.,?? .....
- 完整的模型训练套路
- After going to ByteDance, I learned that there are so many test engineers with an annual salary of 40W?
- 13. Model saving and loading
- 【愚公系列】2022年7月 Go教学课程 006-自动推导类型和输入输出
- [reprint] solve the problem that CONDA installs pytorch too slowly
- [go record] start go language from scratch -- make an oscilloscope with go language (I) go language foundation
- 网络模型的保存与读取
猜你喜欢
11.递归神经网络RNN
Kubernetes Static Pod (静态Pod)
jemter分布式
完整的模型验证(测试,demo)套路
"An excellent programmer is worth five ordinary programmers", and the gap lies in these seven key points
SDNU_ACM_ICPC_2022_Summer_Practice（1~2）
AI遮天传 ML-回归分析入门
AI zhetianchuan ml novice decision tree
Jemter distributed
NVIDIA Jetson测试安装yolox过程记录
随机推荐
FOFA-攻防挑战记录
国外众测之密码找回漏洞
国内首次，3位清华姚班本科生斩获STOC最佳学生论文奖
Service Mesh介绍，Istio概述
Service mesh introduction, istio overview
基础篇——整合第三方技术
Qt不同类之间建立信号槽，并传递参数
手机上炒股安全么？
Service Mesh的基本模式
Introduction to paddle - using lenet to realize image classification method I in MNIST
3 years of experience, can't you get 20K for the interview and test post? Such a hole?
12. RNN is applied to handwritten digit recognition
1293_ Implementation analysis of xtask resumeall() interface in FreeRTOS
跨模态语义关联对齐检索-图像文本匹配（Image-Text Matching）
jemter分布式
Experience of autumn recruitment in 22 years
13. Model saving and loading
Get started quickly using the local testing tool postman
y59.第三章 Kubernetes从入门到精通 -- 持续集成与部署(三二)
新库上线 | CnOpenData中国星级酒店数据