当前位置：网站首页>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);
}
边栏推荐
- 炒股开户怎么最方便，手机上开户安全吗
- Interface test advanced interface script use - apipost (pre / post execution script)
- 国外众测之密码找回漏洞
- fabulous! How does idea open multiple projects in a single window?
- [Yugong series] go teaching course 006 in July 2022 - automatic derivation of types and input and output
- 利用GPU训练网络模型
- 网络模型的保存与读取
- Service Mesh的基本模式
- Binder core API
- They gathered at the 2022 ecug con just for "China's technological power"
猜你喜欢
完整的模型验证(测试,demo)套路
Password recovery vulnerability of foreign public testing
3.MNIST数据集分类
Codeforces Round ＃804 (Div. 2)（A~D）
利用GPU训练网络模型
How does starfish OS enable the value of SFO in the fourth phase of SFO destruction?
What does interface testing test?
1293_ Implementation analysis of xtask resumeall() interface in FreeRTOS
第一讲：链表中环的入口结点
Deep dive kotlin synergy (XXII): flow treatment
随机推荐
接口测试进阶接口脚本使用—apipost（预/后执行脚本）
Which securities company has a low, safe and reliable account opening commission
Hotel
How is it most convenient to open an account for stock speculation? Is it safe to open an account on your mobile phone
22年秋招心得
Marubeni official website applet configuration tutorial is coming (with detailed steps)
After going to ByteDance, I learned that there are so many test engineers with an annual salary of 40W?
Semantic segmentation model base segmentation_ models_ Detailed introduction to pytorch
ReentrantLock 公平锁源码 第0篇
NTT template for Tourism
A network composed of three convolution layers completes the image classification task of cifar10 data set
Is it safe to speculate in stocks on mobile phones?
1.线性回归
New library online | information data of Chinese journalists
Application practice | the efficiency of the data warehouse system has been comprehensively improved! Data warehouse construction based on Apache Doris in Tongcheng digital Department
8.优化器
y59.第三章 Kubernetes从入门到精通 -- 持续集成与部署(三二)
The method of server defense against DDoS, Hangzhou advanced anti DDoS IP section 103.219.39 x
股票开户免费办理佣金最低的券商，手机上开户安全吗
国内首次，3位清华姚班本科生斩获STOC最佳学生论文奖