当前位置： 首页 > article >正文

C语言学习强化

article 2025/1/29 7:35:46

前言

数据的逻辑结构包括：

常见数据结构：

线性结构：数组、链表、队列、栈

树形结构：树、堆

图形结构：图 

一、链表

链表是物理位置不连续，逻辑位置连续

链表的特点：

1.链表没有固定的长度，可以自由增加节点

2.链表可以快速插入和删除数据

链表和数组的优劣

1.数组查找方便，尾部插入数据效率高，但在开头和中间插入数据效率低，需要移位

2.链表查找麻烦，无论在什么位置插入或删除数据效率都高

1.链表的创建与死亡

（1）定义链表中节点的结构

//在实现链式表之前，先确定表中某一个节点类型
typedef struct MyNode
{
	int data;
	struct MyNode *pNext;
}NODE;

data为数据域，pNext为指针域，指向下一个节点 

（2）定义链表结构

//单向链表的类型定义
typedef struct LinkList
{
	NODE* pHead;		//链表的头节点
	NODE* pEnd;			//链表的尾节点
	int length;			//链表的长度
}LL;

pHead指向链表的头节点，pEnd指向链表的尾节点，length来记录链表的长度

（3）创建单链表

//创建单链表
LL* List_Init()
{
	LL* pTemp = (LL*)malloc(sizeof(LL));
	if (NULL == pTemp)
	{
		return NULL;
	}
	else
	{
		pTemp->pHead = NULL;
		pTemp->pEnd = NULL;
		pTemp->length = 0;
		return pTemp;
	}
}

链表初始化，malloc动态分配内存，将头节点、尾节点、长度初始化后，返回链表的首地址。

（4）创建链表中的一个节点

//创建链表的一个节点
NODE* NODE_Init(int data)
{
	NODE* pTemp = (NODE*)malloc(sizeof(NODE));
	if (NULL == pTemp)
	{
		return NULL;
	}
	else
	{
		pTemp->pNext = NULL;
		pTemp->data = data;
		return pTemp;
	}
}

创建链表中的一个节点，把数据放入节点中，但指向下一个节点的指针仍为空指针，也暂时还没有指针指向该节点，也就是说该节点目前还没有与链表建立联系

（5）链表的死亡

//链表的死亡
void List_Dele(LL **pList)
{
	if (NULL == *pList)
	{
		printf("链表不存在\n");
		return;
	}
	NODE* pTemp = NULL;			//借用临时变量循环遍历链表中的每个节点再进行删除
	while ((*pList)->pHead)		//当头节点为空指针时，链表节点遍历完成
	{
		pTemp = (*pList)->pHead;		//暂存头节点的地址
		(*pList)->pHead = (*pList)->pHead->pNext;			//头节点移至下一节点
		free(pTemp);			//释放节点所占内存
	}
	free(*pList);			//释放链表所占内存
	*pList = NULL;          //将指向链表的指针赋值为空指针
}

利用二级指针可以改变一级指针的内容

int main()
{
	LL* pList = List_Init();
	if (NULL == pList)
	{
		printf("创建失败\n");
	}
	List_Dele(&pList);
	return 0;
}

这里main函数给List_Dele传参时是取了链表指针的地址，于是在函数中，就能修改链表指针的内容

2.链表的插入

（1）链表尾部添加元素

//在链表尾部添加元素
void List_append(LL* pList, int val)
{
	if (NULL == pList)
	{
		printf("链表不存在，添加失败\n");
		return;
	}
	NODE* pTemp = NODE_Init(val);
	if (NULL == pTemp)
	{
		printf("节点创建失败\n");
	}
	if (NULL == pList->pHead)        //检查是否为空链表
	{
		pList->pHead = pList->pEnd = pTemp;        //空链表则头尾指针同时指向该新增元素
	}
	else
	{
		pList->pEnd->pNext = pTemp;            //非空链表情况
		pList->pEnd = pTemp;
	}
	pList->length++;                        //链表长度加1
}

详细分析见注释内容 

（2）链表中插入元素

//链表中插入元素
void List_insert(LL* pList, int idx, int val)
{
	if (NULL == pList)
	{
		printf("链表不存在，添加失败\n");
		return;
	}
	NODE* pTemp = NODE_Init(val);
	if (NULL == pTemp)
	{
		printf("节点创建失败，添加失败\n");
	}
	if (idx >= pList->length)            //如果索引超出长度范围，元素添加至尾部		
	{
		pList->pEnd->pNext = pTemp;
		pList->pEnd = pTemp;
	}
	else if (idx <= 0)                    //如果索引小于等于0，元素添加至开头
	{
		pTemp->pNext = pList->pHead;
		pList->pHead = pTemp;
	}
	else                                    //索引不在首尾处
	{
		NODE* pInsertNode = pList->pHead;        //从头节点开始迭代
		for (int i = 0; i < idx - 1; i++)         //指针迭代一次次往后指
		{
			pInsertNode = pInsertNode->pNext;    //一直迭代到指向要插入索引的前面
		}
		pTemp->pNext = pInsertNode->pNext;        //先让插入元素指向索引位置元素
		pInsertNode->pNext = pTemp;                //再让索引位置前的元素指向插入元素
	}
    pList->length++;
}

详细分析见注释内容 

（3）链表中删除元素

//删除单个元素
void List_deleNode(LL* pList, int idx)
{
	if (NULL == pList || 0 == pList->length)
	{
		printf("链表不存在，添加失败\n");
		return;
	}
	if (idx < 0 || idx >= pList->length)
	{
		printf("删除位置不存在\n");
		return;
	}
	NODE* pTemp = NULL;
	if (idx == 0)            //删除位置为开头
	{
		pTemp = pList->pHead;
		pList->pHead = pList->pHead->pNext;
	}
	else                    //删除位置为中间或尾部
	{
		NODE* pCurNode = pList->pHead;
		for (int i = 0; i < idx - 1; i++)
		{
			pCurNode = pCurNode->pNext;        //迭代至指向删除元素的上一个
		}
		pTemp = pCurNode->pNext;
		pCurNode->pNext = pTemp->pNext;
		if (pCurNode->pNext == NULL)
		{
			pList->pEnd = pCurNode;
		}
	}
	free(pTemp);
	pList->length--;
}

二、栈和队列

操作受限的线性表

栈的特点：先进后出

队列的特点：先进先出

1.栈

操作：出栈、入栈、得到栈顶元素、判断栈满或栈空

通过顺序表来实现

#include <stdio.h>
#include <stdlib.h>
#define STACK_LEN 10

typedef struct MyStack
{
	int dataArr[STACK_LEN];
	int top;
}STACK;

//创建
STACK* Stack_Init()
{
	STACK* pStack = (STACK*)malloc(sizeof(STACK));
	if (NULL == pStack)
	{
		printf("栈创建失败\n");
		return NULL;
	}
	pStack->top = 0;
	return pStack;
}

//判断栈是否满
int FullStack(STACK* pStack)
{
	if (pStack->top >= STACK_LEN)
	{
		return 1;
	}
	return 0;
}

//判断栈是否空
int EmptyStack(STACK* pStack)
{
	if (pStack->top == 0)
	{
		return 1;
	}
	return 0;
}
//入栈
void Stack_push(STACK* pStack, int val)
{
	if (NULL == pStack)
	{
		printf("栈不存在，入栈失败\n");
		return;
	}
	if (FullStack(pStack) == 1)
	{
		printf("栈已满，不能入栈\n");
		return;
	}
	pStack->dataArr[pStack->top++] = val;
}

//出栈
void Stack_pop(STACK* pStack)
{
	if (NULL == pStack)
	{
		printf("栈不存在，入栈失败\n");
		return;
	}
	if (EmptyStack(pStack) == 1)
	{
		printf("栈为空，不能入栈\n");
		return;
	}
	pStack->top--;
}

//获取栈顶元素
int Stack_top(STACK* pStack)
{
	//栈为空，或栈不存在都会报错
	return pStack->dataArr[pStack->top - 1];
}

//删除栈
void Stack_clear(STACK** pStack)
{
	if (NULL != *pStack)
	{
		free(*pStack);
		*pStack = NULL;
	}
}

int main()
{
	STACK* pStack = NULL;
	pStack = Stack_Init();

	Stack_clear(&pStack);
	return 0;
}

2.队列

操作：出栈、入栈、得到队头、得到队尾

通过链式表来实现

#include <stdio.h>
#include <stdlib.h>

typedef struct MyNode
{
	int data;
	struct MyNode* pNext;
}NODE;


typedef struct MyQueue
{
	NODE* pHead;		
	NODE* pEnd;			
}QUEUE;

QUEUE* Queue_Init()
{
	QUEUE* pTemp = (QUEUE*)malloc(sizeof(QUEUE));
	if (NULL == pTemp)
	{
		printf("队列创建失败\n");
		return NULL;
	}
	else
	{
		pTemp->pHead = NULL;
		pTemp->pEnd = NULL;
		return pTemp;
	}
}

NODE* NODE_Init(int data)
{
	NODE* pTemp = (NODE*)malloc(sizeof(NODE));
	if (NULL == pTemp)
	{
		printf("节点创建失败\n");
		return NULL;
	}
	else
	{
		pTemp->pNext = NULL;
		pTemp->data = data;
		return pTemp;
	}
}

//入队
void Queue_push(QUEUE* pQue, int val)
{
	if (NULL == pQue)
	{
		printf("链表不存在，添加失败\n");
		return;
	}
	NODE* pTemp = NODE_Init(val);
	if (NULL == pQue->pHead)
	{
		pQue->pHead = pQue->pEnd = pTemp;
	}
	else
	{
		pQue->pEnd->pNext = pTemp;
		pQue->pEnd = pTemp;
	}
}

//出队
void Queue_pop(QUEUE* pQue)
{
	if (NULL == pQue || NULL == pQue->pHead)
	{
		printf("队列不存在\n");
		return;
	}
	NODE* pTemp = NULL;
	pTemp = pQue->pHead;
	pQue->pHead = pQue->pHead->pNext;
	if (NULL == pQue->pHead)
		pQue->pEnd = NULL;
}

int Queue_front(QUEUE* pQue)
{
	return pQue->pHead->data;
}

int Queue_back(QUEUE* pQue)
{
	return pQue->pEnd->data;
}

void Queue_clear(QUEUE** pQue)
{
	if (NULL != *pQue)
	{
		free(*pQue);
		*pQue = NULL;
	}
}

总体跟链表类似


http://www.kler.cn/a/520995.html

相关文章：

  • DirectShow过滤器开发-读MP4视频文件过滤器（再写）
  • DAY02 final关键字、static关键字、接口
  • TCP三次握手和四次挥手
  • 如何使用 DeepSeek API 结合 VSCode 提升开发效率
  • Excel分区间统计分析（等步长、不等步长、多维度）
  • Python3 【高阶函数】项目实战：5 个学习案例
  • 一文讲解Java中的接口和抽象类
  • 保定学院寒假第一次训练赛题解
  • C语言初阶牛客网刷题—— HJ34 图片整理【难度：中等】
  • 01机器学习入门
  • jQuery阶段总结
  • 数据结构：二叉树—面试题（二）
  • Microsoft Entra ID允许普通用户更新自己的UPN
  • 【Linux】统计文本中每行指定位置出现的字符串的次数
  • 进程控制的学习
  • 微服务学习-Nacos 配置中心实战
  • 在 AMD GPU 上使用 vLLM 的 Triton 推理服务器
  • OpenAI 发布首个 AI 智能体
  • [ Spring ] Spring Cloud Alibaba Aliyun OSS 2025
  • 电梯系统的UML文档11
  • 字节跳动发布UI-TARS，超越GPT-4o和Claude，能接管电脑完成复杂任务
  • 蓝桥杯备考：哈希表和unorderd_set
  • 算法每日双题精讲 —— 二分查找（寻找旋转排序数组中的最小值，点名）
  • ＜ OS 有关 ＞ 阿里云：轻量应用服务器 的使用 ：轻量化 阿里云 vpm 主机
  • 从单体应用到微服务的迁移过程
  • 基于LangGraph、Groq和Tavily打造可以调用外部搜索引擎工具的对话机器人（核心代码 万字详解）