当前位置：网站首页>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);
}
边栏推荐
- 13. Model saving and loading
- 新库上线 | CnOpenData中国星级酒店数据
- fabulous! How does idea open multiple projects in a single window?
- Deep dive kotlin collaboration (the end of 23): sharedflow and stateflow
- 2.非线性回归
- Cascade-LSTM: A Tree-Structured Neural Classifier for Detecting Misinformation Cascades(KDD20)
- Service Mesh介绍，Istio概述
- 13.模型的保存和载入
- 11.递归神经网络RNN
- C＃中string用法
猜你喜欢
2.非线性回归
ReentrantLock 公平锁源码 第0篇
新库上线 | CnOpenData中国星级酒店数据
C ＃ generics and performance comparison
New library launched | cnopendata China Time-honored enterprise directory
![[OBS] the official configuration is use_ GPU_ Priority effect is true](/img/df/772028e44776bd667e814989e8b09c.png)
[OBS] the official configuration is use_ GPU_ Priority effect is true
8.优化器
Kubernetes static pod (static POD)
Tapdata 的 2.0 版 ，开源的 Live Data Platform 现已发布
Get started quickly using the local testing tool postman
随机推荐
股票开户免费办理佣金最低的券商，手机上开户安全吗
新库上线 | 中国记者信息数据
New library online | information data of Chinese journalists
【愚公系列】2022年7月 Go教学课程 006-自动推导类型和输入输出
Cascade-LSTM: A Tree-Structured Neural Classifier for Detecting Misinformation Cascades(KDD20)
The weight of the product page of the second level classification is low. What if it is not included?
串口接收一包数据
Application practice | the efficiency of the data warehouse system has been comprehensively improved! Data warehouse construction based on Apache Doris in Tongcheng digital Department
Codeforces Round ＃804 (Div. 2)（A~D）
Service mesh introduction, istio overview
The method of server defense against DDoS, Hangzhou advanced anti DDoS IP section 103.219.39 x
Four stages of sand table deduction in attack and defense drill
NVIDIA Jetson test installation yolox process record
Is it safe to speculate in stocks on mobile phones?
基于人脸识别实现课堂抬头率检测
QT adds resource files, adds icons for qaction, establishes signal slot functions, and implements
22年秋招心得
NVIDIA Jetson测试安装yolox过程记录
新库上线 | CnOpenData中国星级酒店数据
接口测试进阶接口脚本使用—apipost（预/后执行脚本）