当前位置: 首页 > news >正文

线性结构之链表

离散存储[链表]:

  定义:

    n个结点的离散分配

    彼此通过指针相连

    每个结点只有一个前续结点

    每个结点只有一个后续结点

    首结点没有前续结点

    尾结点没有后续结点

  专业术语:

    首结点:第一个有效结点,存放第一个有效数据

    尾结点:最后一个有效结点,存放最后一个有效数据

    头结点:在首结点之前的一个结点,既不存放有效数据,也不存放有效结点的个数,加头结点的主要目的是为了方便对链表的操作,头结点的数据类型和其他结点的数据类型是一样的

    头指针:指向头结点的指针变量,存放了头结点的地址

    尾指针:指向尾结点的指针变量,存放了尾结点的地址

  确定一个链表至少需要哪些参数:

    只需要一个参数:头指针

    因为我们通过头指针就可以推出链表的其他所有信息

  链表的分类:

    单链表:每一个结点只有一个指针域

    双链表:每一个结点有两个指针域

    循环链表:能通过任何一个结点找到其他所有的结点

    非循环链表

 

  算法:

    狭义的算法是与数据存储方式密切相关的

    广义的算法与数据存储方式无关

    泛型:你用某种技术达到的效果就是:不同的存储方式,执行的操作是一样的


/*
@file      main.c
@brief     线性结构之链表
@author    EricsT (EricsT@163.com)
@version   v1.0.0
@date      2025-09-21
@history   2025-09-21 EricsT - 新建文件2025-09-22 EricsT - 新增 CreateList\TraverseList2025-09-22 EricsT - 新增 isEmptyList\GetLenthList\InsertList\DeleteList\SortList
*/#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>typedef struct Node
{int data;//数据域Node* ptrNext;//指针域
}* PtrNode, NODE;//NODE 相当于 Node NODE//ptrNode 相当于 Node* ptrNodePtrNode CreateList();//创建链表
void TraverseList(const PtrNode ptrNode);//遍历链表
bool isEmptyList(const PtrNode ptrNode);//是否为空
int GetLenthList(const PtrNode ptrNode);//获取链表长度
bool InsertList(PtrNode ptrNode, int insertPos, int insertData);//插入结点
bool DeleteList(PtrNode ptrNode, int deletePos);//删除结点
void SortList(PtrNode ptrNode);//排序int main(void)
{PtrNode ptrNode = NULL;ptrNode = CreateList();TraverseList(ptrNode);if (isEmptyList(ptrNode))printf("链表为空\n");elseprintf("链表非空\n");printf("链表长度为:%d\n", GetLenthList(ptrNode));int insertPose;printf("请输入插入位置");scanf("%d", &insertPose);int insertValue;printf("请输入插入数值");scanf("%d", &insertValue);InsertList(ptrNode, insertPose, insertValue);TraverseList(ptrNode);int deletePose;printf("请输入删除位置");scanf("%d", &deletePose);DeleteList(ptrNode, deletePose);TraverseList(ptrNode);SortList(ptrNode);TraverseList(ptrNode);return 0;
}PtrNode CreateList()
{int len;printf("请输入结点个数len = ");scanf("%d", &len);int addr = 0;PtrNode ptrNodeFirst = (PtrNode)malloc(sizeof(NODE));//头结点if (NULL == ptrNodeFirst){printf("分配失败\n");exit(-1);}PtrNode ptrNodeLast = ptrNodeFirst;//尾结点ptrNodeLast->ptrNext = NULL;for (int i = 0; i < len; ++i){PtrNode ptrNode = (PtrNode)malloc(sizeof(PtrNode));//新的尾结点if (NULL == ptrNodeFirst){printf("分配失败\n");exit(-1);}ptrNodeLast->ptrNext = ptrNode;//新的尾结点挂在旧的尾结点后面printf("请输入%d个结点的数值", i + 1);scanf("%d", &ptrNode->data);ptrNode->ptrNext = NULL;ptrNodeLast = ptrNode;//更新尾结点}return ptrNodeFirst;
}void TraverseList(const PtrNode ptrNode/*头结点*/)
{PtrNode ptrNode_ = ptrNode->ptrNext;//首节点while (NULL != ptrNode_)//结点为空,则是尾结点{printf("%d ", ptrNode_->data);ptrNode_ = ptrNode_->ptrNext;//下一结点}printf("\n");
}bool isEmptyList(const PtrNode ptrNode)
{PtrNode ptrNode_ = ptrNode->ptrNext;//首节点if (NULL == ptrNode->ptrNext)return true;return false;
}int GetLenthList(const PtrNode ptrNode)
{int iLen = 0;PtrNode ptrNode_ = ptrNode->ptrNext;//首节点while (NULL != ptrNode_)//结点为空,则是尾结点{ptrNode_ = ptrNode_->ptrNext;//下一结点iLen++;}return iLen;
}bool InsertList(PtrNode ptrNode, int insertPos, int insertData)
{if (insertPos < 1)return false;if (insertPos > (GetLenthList(ptrNode) + 1))return false;PtrNode ptrNodeInsert = (PtrNode)malloc(sizeof(Node));ptrNodeInsert->data = insertData;PtrNode ptrNodeCur = ptrNode;for (int i = 1; i < insertPos; ++i)ptrNodeCur = ptrNodeCur->ptrNext;ptrNodeInsert->ptrNext = ptrNodeCur->ptrNext;ptrNodeCur->ptrNext = ptrNodeInsert;return true;
}bool DeleteList(PtrNode ptrNode, int deletePos)
{if (deletePos < 1)return false;if (deletePos > GetLenthList(ptrNode))return false;PtrNode ptrNodeCur = ptrNode;for (int i = 1; i < deletePos; ++i)ptrNodeCur = ptrNodeCur->ptrNext;ptrNodeCur->ptrNext = ptrNodeCur->ptrNext->ptrNext;return true;
}void SortList(PtrNode ptrNode)
{int iLen = GetLenthList(ptrNode);PtrNode ptrNodeCur = ptrNode;//头结点for (int i = 0; i < iLen; ++i){ptrNodeCur = ptrNodeCur->ptrNext;PtrNode ptrNodeNext = ptrNodeCur->ptrNext;while (NULL != ptrNodeNext){if (ptrNodeCur->data > ptrNodeNext->data){int temp = ptrNodeCur->data;ptrNodeCur->data = ptrNodeNext->data;ptrNodeNext->data = temp;}ptrNodeNext = ptrNodeNext->ptrNext;}}
}

 

http://www.hskmm.com/?act=detail&tid=13861

相关文章:

  • 二叉树最近公共祖先
  • AI 编程“效率幻觉”:为何你感觉快了,项目却慢了?
  • lc1033-移动石子直到连续
  • 一些正在制作的“格林达姆”测试项目,以及“假无损”
  • 个人项目
  • 北京 意大利学签 北京意大利签证中心 贵宾 vip vfs
  • 第1周
  • 多商家在线客服系统 - 客服用户表设计方案
  • 九月22号
  • 25.9.22 继续MySQL
  • 使用python读取windows注册表
  • 当日总结
  • 3123004481
  • 使用python读取windows日志表
  • 开机RAM分析调试SOP
  • 9.20 模拟赛 T4
  • 2025.9.21 测试 (a1a2a3a4a5)
  • 原码、反码和补码
  • Русский язык
  • 基于Hex Editor Neo的二进制文件模板
  • 【F#学习】字符
  • kubebuilder创建Operator示例
  • 集训总结(八)
  • 使用try-finally结构执行状态重置
  • java03预习
  • x6831卡顿分析
  • 实测对比:权威榜单之微信排版软件Top5(含详细测评)
  • 【F#学习】布尔运算优先级
  • 粘连字符验证码的分割与识别思路
  • 深入解析:【Spark+Hive+hadoop】基于spark+hadoop基于大数据的人口普查收入数据分析与可视化系统