当前位置:网站首页>C杂讲 动态链表操作 再讲
C杂讲 动态链表操作 再讲
2022-07-06 09:04:00 【Bright-SKY】
目录
知识点1【布局个简单框架】
main.c
#include<stdio.h>
void stu_help(void);
int main(int argc,char *argv[])
{
stu_help();
while(1)
{
char cmd[32]="";
printf("请输入操作指令:");
scanf("%s",cmd);
if(strcmp(cmd,"help") == 0)
{
stu_help();
}
else if(strcmp(cmd,"insert") == 0)
{
printf("-----insert------\n");
}
else if(strcmp(cmd,"print") == 0)
{
printf("-----print------\n");
}
else if(strcmp(cmd,"search") == 0)
{
printf("-----search------\n");
}
else if(strcmp(cmd,"delete") == 0)
{
printf("-----delete------\n");
}
else if(strcmp(cmd,"free") == 0)
{
printf("-----free------\n");
}
else if(strcmp(cmd,"quit") == 0)
{
break;
}
}
return 0;
}
void stu_help(void)
{
printf("################################\n");
printf("#help:打印帮助信息 #\n");
printf("#insert:插入链表节点 #\n");
printf("#print:遍历链表节点信息 #\n");
printf("#search:查询链表节点 #\n");
printf("#delete:删除链表节点 #\n");
printf("#free:释放链表 #\n");
printf("#quit:退出 #\n");
printf("################################\n");
return;
}
链表插入节点 之 头部之前插入
案例:
main.c
#include<stdio.h>
#include<string.h>
#include "link.h"
void stu_help(void);
int main(int argc,char *argv[])
{
//定义一个链表头 注意 一定要赋值为NULL
STU *head=NULL;
stu_help();
while(1)
{
char cmd[32]="";
printf("请输入操作指令:");
scanf("%s",cmd);
if(strcmp(cmd,"help") == 0)
{
stu_help();
}
else if(strcmp(cmd,"insert") == 0)
{
STU tmp;
printf("请输入需要插入的数据:");
scanf("%d %s %f",&tmp.num, tmp.name, &tmp.score);
//将tmp数据 插入到head所指向的链表中
head = insert_link(head, tmp);
}
else if(strcmp(cmd,"print") == 0)
{
print_link(head);
}
else if(strcmp(cmd,"search") == 0)
{
printf("-----search------\n");
}
else if(strcmp(cmd,"delete") == 0)
{
printf("-----delete------\n");
}
else if(strcmp(cmd,"free") == 0)
{
printf("-----free------\n");
}
else if(strcmp(cmd,"quit") == 0)
{
break;
}
}
return 0;
}
void stu_help(void)
{
printf("################################\n");
printf("#help:打印帮助信息 #\n");
printf("#insert:插入链表节点 #\n");
printf("#print:遍历链表节点信息 #\n");
printf("#search:查询链表节点 #\n");
printf("#delete:删除链表节点 #\n");
printf("#free:释放链表 #\n");
printf("#quit:退出 #\n");
printf("################################\n");
return;
}
link.c
#include<stdio.h>
#include<stdlib.h>//calloc
#include"link.h"
STU* insert_link(STU *head, STU tmp)
{
//1、从堆区申请一个待插入的节点空间
STU *pi = (STU *)calloc(1,sizeof(STU));
if(pi == NULL)
{
perror("calloc");
return head;
}
//2、将tmp的值 赋值 给*pi
*pi = tmp;
pi->next = NULL;//注意
//3、将pi插入到链表中
if(head == NULL)//链表不存在
{
head = pi;
//return head;
}
else//链表存在(头部之前插入)
{
//1、让pi 指向就的头
pi->next = head;
//2、head指向新的头节点
head = pi;
//return head;
}
return head;
}
void print_link(STU *head)
{
if(head == NULL)//链表不存在
{
printf("link not find\n");
return;
}
else
{
STU *pb = head;
while(pb != NULL)
{
printf("%d %s %f\n", pb->num, pb->name,pb->score);
//pb指向下一个节点
pb = pb->next;
}
}
return;
}
link.h
//防止头文件重复包含
#ifndef __LINK_H__
#define __LINK_H__
//链表节点类型 定义
typedef struct stu
{
//数据域
int num;
char name[32];
float score;
//指针域
struct stu *next;
}STU;
extern STU* insert_link(STU *head, STU tmp);
extern void print_link(STU *head);
#endif
知识点2【链表的插入】
1、在链表的尾部插入
//链表的尾部插入
STU* insert_link(STU *head, STU tmp)
{
//1、申请待插入的节点
STU *pi = (STU *)calloc(1,sizeof(STU));
if(pi == NULL)
{
perror(calloc);
return head;
}
//2、将tmp的数据 赋值到 *pi
*pi = tmp;
pi->next = NULL;
//3、将节点插入到链表的尾部
if(head == NULL)//链表不存在
{
head = pi;
return head;
}
else//链表存在
{
//a、寻找链表的尾节点
STU *pb = head;
while(pb->next != NULL)//如果不是尾节点
pb = pb->next;//pb就指向下一个节点
//b、用尾结点 pb 链接上 插入的节点pi
pb->next = pi;
return head;
}
return head;
}
2、链表的有序插入(难度)
//链表的有序插入 以num的顺序为准(小--->大)
STU* insert_link(STU *head, STU tmp)
{
//1、给待插入的节点pi 申请 堆区空间
STU *pi = (STU *)calloc(1,sizeof(STU));
if(pi == NULL)
{
perror("calloc");
return head;
}
//2、将tmp的内容 赋值给 *pi
*pi = tmp;
pi->next = NULL;
//3、链表节点pi的插入
if(head == NULL)//链表不存在
{
head = pi;
return head;
}
else//存在
{
//a、寻找插入点
STU *pb = head, *pf = head;
while(pb->num < pi->num && pb->next != NULL)
{
pf = pb;
pb = pb->next;
}
//b、插入点的判断
if(pb->num >= pi->num)//头部 中部插入
{
if(pb == head)//头部之前插入
{
pi->next = head;
head = pi;
return head;
}
else//中部插入
{
pf->next = pi;
pi->next = pb;
return head;
}
}
else//尾部插入
{
pb->next = pi;
return head;
}
}
return head;
}
知识点2【链表查询某个节点】 按姓名 查找
STU* search_link(STU *head, char *name)
{
//1、判断链表是否存在
if(head == NULL)//不存在
{
printf("link not found\n");
return NULL;
}
else//链表存在
{
STU *pb = head;
//逐个将节点中的name 和 name比较 如果不相等 pb=pb->next
while(strcmp(pb->name,name)!=0 && pb->next != NULL)
pb = pb->next;
//判断是否找到
if(strcmp(pb->name,name)==0)//找到
return pb;
else//没找到
return NULL;
}
return NULL;
}
知识点3【删除链表指定节点】
STU* detele_link(STU *head,char *name)
{
//1、判断链表是否存在
if(head == NULL)//不存在
{
printf("link not found\n");
return head;
}
else//存在
{
//2、寻找删除点
STU *pf=head, *pb = head;
while(strcmp(pb->name,name)!=0 && pb->next != NULL)
{
pf = pb;
pb = pb->next;
}
//3、找到删除点
if(strcmp(pb->name,name)==0)//找到删除点
{
//4、判断删除的位置
if(pb == head)//删除头结点
{
head = pb->next;
free(pb);
}
else//中部 或 尾部节点
{
pf->next = pb->next;
free(pb);
}
printf("已成功删除%s的相关节点\n",name);
return head;
}
else//没找到删除点
{
printf("链表中没有%s相关的数据节点信息\n",name);
}
}
return head;
}
知识点4【链表的释放】
STU* free_link(STU *head)
{
//判断链表是否存在
if(head == NULL)
{
printf("link not found\n");
return head;
}
else//链表存在
{
STU *pb = head;
//逐个节点释放
while(pb != NULL)
{
//head保存下一个节点的位置
head = pb->next;
//释放pb指向的节点
free(pb);
//pb 指向 head
pb = head;
}
printf("链表已经释放完毕\n");
return head;
}
return head;
}
知识点5【回顾一下】
链表的插入:头部之前插入 尾部插入 有序插入
1、为插入的节点pi申请空间
2、将tmp的值赋值给*pi *pi = tmp
3、判断链表是否 存在
3-1:不存在 head = pi
3-2: 存在 (尾部插入 有序插入) 寻找插入点 安装具体的位置 插入节点
链表的遍历:
1、判断链表是否存在
1-1:不存在 不执行任何操作
1-2:存在 逐个节点遍历 注意 别越界。
链表的查询:
1、判断链表是否存在
1-1:不存在 不执行任何操作
1-2:存在 逐个节点比较 比较成功返回位置 注意 别越界。
链表节点的删除:
1、判断链表是否存在
1-1:不存在 不执行任何操作
1-2:存在 逐个节点比较 删除指定节点 注意 别越界。
释放链表:
1、判断链表是否存在
1-1:不存在 不执行任何操作
1-2:存在 逐个节点节点释放 注意 别越界
知识点6【链表的逆序】
STU* reverse_link(STU *head)
{
//判断链表是否存在
if(head == NULL)
{
printf("link not founf\n");
return head;
}
else//链表存在
{
//int *p,num;//p为int * , num为int
STU *pb,*pr;//pb为STU * , pr为STU *
//pb保存head->next(原因head->next会置NULL)
pb = head->next;
//将head->next置NULL (原因:头节点变尾节点)
head->next = NULL;
while(pb != NULL)
{
//pr保存pb->next (原因:pb->next会指向head)
pr = pb->next;
//pb->next 指向 head (原因:逆转方向)
pb->next = head;
//保存 逆转方向的代码 可以重复 执行
head = pb;
pb = pr;
}
return head;
}
return head;
}
知识点7【链表的排序】
选择法排序:(以数组实现)
#include<stdio.h>
int main()
{
int arr[10]={0};
int n = sizeof(arr)/sizeof(arr[0]);
int i=0,j=0,min=0;
printf("请输入%d个int数据\n",n);
for(i=0;i<n;i++)
{
scanf("%d",arr+i);
}
//选择法排序
for(i=0;i<n-1; i++)
{
for(min=i,j=min+1; j<n;j++)
{
if(arr[min] > arr[j])
min = j;
}
if(min != i)
{
int tmp = 0;
tmp = arr[i];
arr[i]=arr[min];
arr[min]=tmp;
}
}
for(i=0;i<n;i++)
{
printf("%d ",arr[i]);
}
printf("\n");
return 0;
}
运行结果:
知识点7【链表的排序(选择法)】
void sort_link(STU *head)
{
//1、判断链表是否存在
if(NULL == head)
{
printf("link not found\n");
return;
}
else
{
STU *p_i = head;//i=0
while(p_i->next != NULL)//i<n-1 外层循环
{
STU *p_min = p_i;//min = i;
STU *p_j = p_min->next;//j = min+1
while(p_j != NULL)//j<n 内层循环
{
//寻找成员num最小值的 节点
if(p_min->num > p_j->num)//if(arr[min] > arr[j])
p_min = p_j;//min = j
p_j = p_j->next;//j++
}
if(p_min != p_i)//min != i
{
//只交换数据域(1、节点内容整体交换 2、只交换指针域)
//1、节点内容整体交换(数据域交换第1次 指针域交换第1次)
STU tmp;
tmp = *p_i;
*p_i = *p_min;
*p_min = tmp;
//2、只交换指针域(指针域交换第2次)
tmp.next = p_i->next;
p_i->next = p_min->next;
p_min->next = tmp.next;
}
p_i = p_i->next;//i++
}
}
}
边栏推荐
- Mapreduce实例(七):单表join
- [deep learning] semantic segmentation: paper reading: (2021-12) mask2former
- Competition vscode Configuration Guide
- 068.查找插入位置--二分查找
- 硬件工程师的真实前途我说出来可能你们不信
- Hugo blog graphical writing tool -- QT practice
- Combined search /dfs solution - leetcode daily question - number of 1020 enclaves
- [deep learning] semantic segmentation - source code summary
- 通过bat脚本配置系统环境变量
- [flask] crud addition and query operation of data
猜你喜欢
Mapreduce实例(八):Map端join
大学想要选择学习自动化专业,可以看什么书去提前了解?
Several silly built-in functions about relative path / absolute path operation in CAPL script
Segmentation sémantique de l'apprentissage profond - résumé du code source
Compilation of libwebsocket
Listen to my advice and learn according to this embedded curriculum content and curriculum system
Nc17 longest palindrome substring
Download address of canoe, download and activation of can demo 16, and appendix of all canoe software versions
Mapreduce实例(六):倒排索引
零基础学习单片机切记这四点要求,少走弯路
随机推荐
Some thoughts on the study of 51 single chip microcomputer
[deep learning] semantic segmentation: thesis reading (neurips 2021) maskformer: per pixel classification is not all you need
英雄联盟轮播图手动轮播
068.查找插入位置--二分查找
Tianmu MVC audit I
Combined search /dfs solution - leetcode daily question - number of 1020 enclaves
五月刷题01——数组
MySQL数据库优化的几种方式(笔面试必问)
Day 5 of MySQL learning
Vh6501 Learning Series
MapReduce instance (VI): inverted index
Control the operation of the test module through the panel in canoe (primary)
Regular expressions are actually very simple
MapReduce instance (x): chainmapreduce
嵌入式開發中的防禦性C語言編程
CANoe下载地址以及CAN Demo 16的下载与激活,并附录所有CANoe软件版本
[CV] target detection: derivation of common terms and map evaluation indicators
嵌入式开发中的防御性C语言编程
Detailed explanation of cookies and sessions
Cooperative development in embedded -- function pointer