当前位置：网站首页>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);
}
边栏推荐
- 接口测试要测试什么？
- Reentrantlock fair lock source code Chapter 0
- letcode43:字符串相乘
- Thinkphp内核工单系统源码商业开源版 多用户+多客服+短信+邮件通知
- New library online | information data of Chinese journalists
- 9. Introduction to convolutional neural network
- Letcode43: string multiplication
- tourist的NTT模板
- Leetcode brush questions
- Cve-2022-28346: Django SQL injection vulnerability
猜你喜欢
Kubernetes Static Pod (静态Pod)
Get started quickly using the local testing tool postman
《因果性Causality》教程，哥本哈根大学Jonas Peters讲授
After going to ByteDance, I learned that there are so many test engineers with an annual salary of 40W?
What if the testing process is not perfect and the development is not active?
Password recovery vulnerability of foreign public testing
网络模型的保存与读取
4.交叉熵
7.正则化应用
AI zhetianchuan ml novice decision tree
随机推荐
Codeforces Round ＃804 (Div. 2)（A~D）
【GO记录】从零开始GO语言——用GO语言做一个示波器（一）GO语言基础
国内首次，3位清华姚班本科生斩获STOC最佳学生论文奖
丸子官网小程序配置教程来了（附详细步骤）
基于卷积神经网络的恶意软件检测方法
Course of causality, taught by Jonas Peters, University of Copenhagen
Analysis of 8 classic C language pointer written test questions
SDNU_ACM_ICPC_2022_Summer_Practice（1~2）
y59.第三章 Kubernetes从入门到精通 -- 持续集成与部署(三二)
9. Introduction to convolutional neural network
[Yugong series] go teaching course 006 in July 2022 - automatic derivation of types and input and output
They gathered at the 2022 ecug con just for "China's technological power"
New library online | information data of Chinese journalists
[OBS] the official configuration is use_ GPU_ Priority effect is true
接口测试进阶接口脚本使用—apipost（预/后执行脚本）
What does interface testing test?
German prime minister says Ukraine will not receive "NATO style" security guarantee
英雄联盟胜负预测--简易肯德基上校
13.模型的保存和载入
5g NR system messages