社区 › 科技 › 线性结构之链表[基于郝斌课程]

愆蟠唉 发表于 2025-9-24 11:12:16

线性结构之链表[基于郝斌课程]

离散存储[链表]：
  定义：
    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\TraverseList
         2025-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* ptrNode

PtrNode 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");
        else
                printf("链表非空\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;
                }
        }
} 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

格恳绌 发表于 前天 01:00

谢谢分享，辛苦了

查看完整版本: 线性结构之链表[基于郝斌课程]