C 语言_第七章.链表

2023-12-19 19:15:28

第七章链表

7.1 链表的概念

定义

链表是一种物理存储上非连续，数据元素的逻辑顺序通过指针连接的一种线性存储结构。

特点

链表由一系列的节点（链表上的一个元素称为一个节点）组成，节点在运行时动态生成，每个节点包括两个部分：一个是用于存储数据元素的数据域，一个是存储下一个节点地址的指针域。

7.2 链表的创建

typedef struct student
{
    /*	数据域	*/
	int sno;                //	学生学号
	char sname[30];         //	学生姓名
	float source;           //	学生成绩
	
    /*	指针域	*/
	struct student *next;   //	下一个节点的地址
} STU;

int main()
{
    STU* pHeadNode = NULL;	//	头结点, 指向空
    int sno;
    char sname[30] = {0};
    float source;
    
    return 0;
}

7.3 链表插入

7.3.1 头插法

/**
 * @brief  头插法插入数据
 * @param  pHeadNode: 被插入的链表
 * @param  sno: 插入的数据
 * @param  sname[30]: 插入的数据
 * @param  source: 插入的数据
 * @retval 返回插入后的链表头结点
 */
STU *HeadInsertNodeStu(STU *pHeadNode, int sno, char sname[30], float source)
{
    STU *pHeadNewNode = (STU *)malloc(sizeof(STU));

    pHeadNewNode->sno = sno;
    strcpy(pHeadNewNode->sname, sname);
    pHeadNewNode->source = source;
    pHeadNewNode->next = pHeadNode; //  将原链表连接到新的头结点后面

    return pHeadNewNode;
}

7.3.2 尾插法

/**
 * @brief  尾插法插入结点
 * @param  pHeadNode: 被插入的链表
 * @param  sno: 插入的数据
 * @param  sname[30]: 插入的数据
 * @param  source: 插入的数据
 * @retval 返回插入后的链表头结点
 */
STU *EndInsertNodeStu(STU *pHeadNode, int sno, char sname[30], float source)
{
    STU *pHeadNewNode = (STU *)malloc(sizeof(STU));
    STU *pHeadOldNode = pHeadNode;  //  浅拷贝, 用于链表操作

    pHeadNewNode->sno = sno;
    strcpy(pHeadNewNode->sname, sname);
    pHeadNewNode->source = source;
    pHeadNewNode->next = NULL;  //  链表的尾部要指向空

    if (pHeadNode == NULL)
    {
        return pHeadNewNode;
    }
    else
    {
        while (pHeadOldNode->next != NULL)
        {
            pHeadOldNode = pHeadOldNode->next;  //  找到链表尾结点
        }

        pHeadOldNode->next = pHeadNewNode;  //  插入到尾部
    }

    return pHeadNode;
}

7.3.3 按学号升序插入学生

/**
 * @brief  按学号升序插入链表
 * @note   学号唯一
 * @param  pHeadNode: 被插入的链表
 * @param  sno: 插入的数据
 * @param  sname[30]: 插入的数据
 * @param  source: 插入的数据
 * @retval NULL
 */
void InsertUpStuFromSno(STU *pHeadNode, int sno, char sname[30], float source)
{
    STU *pHeadNewNode = (STU *)malloc(sizeof(STU));
    STU *pHeadOldNode = pHeadNode;

    pHeadNewNode->sno = sno;
    pHeadNewNode->source = source;
    strcpy(pHeadNewNode->sname, sname);
    pHeadNewNode->next = NULL;

    if (pHeadNode == NULL)
    {
        pHeadNewNode->next = NULL;
        pHeadNode = pHeadNewNode;
    }
    else
    {
        if (pHeadOldNode->sno > pHeadNewNode->sno)
        {   //  插入的学号小于头结点的学号
            pHeadNewNode->next = pHeadNode;
            pHeadNode = pHeadNewNode;
        }
        else
        {
            while (pHeadOldNode->sno < pHeadNewNode->sno)
            {
                if (pHeadOldNode->next == NULL)
                {   //  如果此时为原链表的尾部
                    pHeadOldNode->next = pHeadNewNode;
                }
                else
                {
                    if (pHeadOldNode->next->sno > pHeadNewNode->sno)
                    {   //  插入的学号 < 下一个节点的学号
                        pHeadNewNode->next = pHeadOldNode->next;
                        pHeadOldNode->next = pHeadNewNode;
                    }
                    pHeadOldNode = pHeadOldNode->next;
                }
            }
        }
    }
}

7.4 链表遍历

/**
 * @brief  打印链表
 * @param  pHeadNode: 被打印的链表
 * @retval NULL
 */
void printf_stu(STU *pHeadNode)
{
	while (pHeadNode != NULL)
	{
		printf("Sno：%d，Sname：%s，Source：%.1f\n", pHeadNode->sno, pHeadNode->sname, pHeadNode->source);
		pHeadNode = pHeadNode->next;
	}

	printf("Over！\n");
}

7.5 节点查找

7.5.1 按学号查询

/**
 * @brief  按学号查询链表的结点
 * @note   学号唯一
 * @param  pHeadNode: 被查询的链表
 * @param  sno: 用于匹配的数据
 * @retval 返回查询到的结点
 */
STU *InquireSno(STU *pHeadNode, int sno)
{
	while (pHeadNode)
	{
		if (pHeadNode->sno == sno)
		{	//	找到了就退出循环
			break;
		}

		pHeadNode = pHeadNode->next;
	}

	return pHeadNode;	//	此时链表的头结点就是要查询的数据
}

7.5.2 按姓名查询

/**
 * @brief  按姓名查询链表的结点
 * @note   姓名不一定唯一
 * @param  pHeadNode: 被查询的链表
 * @param  sno: 用于匹配的数据
 * @retval 返回第一次查询到的结点
 */
STU *InquireSno(STU *pHeadNode, int sno)
{
	while (pHeadNode)
	{
		if (pHeadNode->sno == sno)
		{
			break;
		}

		pHeadNode = pHeadNode->next;
	}

	return pHeadNode;
}

7.6 节点删除

7.6.1 按学号删除

/**
 * @brief  按学号删除链表的结点
 * @note   学号唯一
 * @param  pHeadNode: 被删除的链表
 * @param  result: 用于匹配的数据
 * @retval 成功删除返回 0, 否则返回 1
 */
int DeleteFromSno(STU *pHeadNode, STU *result)
{
	if (pHeadNode == NULL)
	{	//	空链表
		return -1;
	}
    
	while (pHeadNode)
	{
		if (pHeadNode->next == result)
		{
			pHeadNode->next = result->next;	//	将 result 所在结点的上一个结点与下一个节点连接
			free(result);
            
			return 0;
		}
        
		pHeadNode = pHeadNode->next;
	}
    
	return -1;	//	未查询到目标节点
}

7.6.2 按姓名删除

/**
 * @brief  按姓名删除链表的结点
 * @note   姓名不唯一, 删除的是第一个匹配到的节点
 * @param  pHeadNode: 被删除的链表
 * @param  result: 用于匹配的数据
 * @retval 成功删除返回 0, 否则返回 1
 */
int DeleteFromSname(STU *pHeadNode, STU *result)
{
	if (pHeadNode == NULL)
	{
		return -1;
	}
    
	while (pHeadNode)
	{
		if (pHeadNode->next == result)
		{
			pHeadNode->next = result->next;
			free(result);
            
			return 0;
		}
        
		pHeadNode = pHeadNode->next;
	}
    
	return -1;
}

7.7 链表排序

7.7.1 按学号升序

/**
 * @brief  按学号排序链表
 * @note   学号唯一
 * @param  pHeadNode: 用于排序的链表
 * @retval NULL
 */
void SortUpFromSno(STU *pHeadNode)
{
	int num = 0; //  记录结点个数
	int newsno = 0;
	float newsource = 0;
	char newsname[30] = {0};
	STU *pHeadNewNode = pHeadNode;

	if (pHeadNode != NULL)
	{
		if (pHeadNode->next != NULL)
		{
			while (pHeadNode)
			{	//	找到链表的节点数, 用于确定排序次数
				num++;
				pHeadNode = pHeadNode->next;
			}
            
			for (int i = 0; i < num - 1; i++)
			{
				pHeadNode = pHeadNewNode;
                
				for (int j = 0; j < num - i - 1; j++)
				{
					if (pHeadNode->sno > pHeadNode->next->sno)
					{	//	两个结点的数据交换
						newsno = pHeadNode->sno;
						newsource = pHeadNode->source;
						strcpy(newsname, pHeadNode->sname);

						pHeadNode->sno = pHeadNode->next->sno;
						pHeadNode->source = pHeadNode->next->source;
						strcpy(pHeadNode->sname, pHeadNode->next->sname);

						pHeadNode->next->sno = newsno;
						pHeadNode->next->source = newsource;
						strcpy(pHeadNode->next->sname, newsname);
					}
                    
					pHeadNode = pHeadNode->next;
				}
			}
		}
	}
}

7.7.2 逆序

/**
 * @brief  将结点逆序
 * @param  pHeadNode: 被逆序的链表
 * @retval NULL
 */
void ReveserStu(STU *pHeadNode)
{
	STU *pHeadNewNode = pHeadNode;
	STU *pHeadOldNode = NULL;

	if (pHeadNode)
	{
		if (pHeadNode->next)
		{	//	两层 if 去掉链表为空和链表节点数为 1, 两种情况
			pHeadNewNode = pHeadNewNode->next;
			pHeadNode->next = NULL;
			
			while (pHeadNode)
			{
				pHeadOldNode = pHeadNewNode;
				pHeadNewNode = pHeadNewNode->next;
				pHeadOldNode->next = pHeadNode;
				pHeadNode = pHeadOldNode;
			}
		}
	}
}

7.8 主函数

int main()
{
	STU *pHeadNode = NULL;      //  链表头指针
	int sno;                    //  学生学号
	char sname[30] = {0};       //  学生姓名
	float source;               //  学生成绩
	int opt = -1;               //  选项

	option();					//	功能菜单

	while (1)
	{
		//printf("Please enter opt: \n");
		scanf("%d", &opt);

		if (opt == 0)
		{
			system("cls");	//	Linux 下换成 system("clear");
			option();
		}

		if (opt == 1)
		{
			system("cls");
			option();
			printf_stu(pHeadNode);
		}

		if (opt == 2)
		{
			system("cls");
			option();
			printf("Please enter Sno Sname Source: \n");
			scanf("%d %s %f", &sno, sname, &source);

			pHeadNode = HeadInsertNodeStu(pHeadNode, sno, sname, source);

			printf("Over!\n");
		}

		if (opt == 3)
		{
			system("cls");
			option();
			printf("Please enter Sno Sname Source: \n");
			scanf("%d %s %f", &sno, sname, &source);

			pHeadNode = EndInsertNodeStu(pHeadNode, sno, sname, source);

			printf("Over!\n");
		}

		if (opt == 4)
		{
			system("cls");
			option();
			printf("Please enter Sno: \n");
			scanf("%d", &sno);

			STU *result_inquire = InquireSno(pHeadNode, sno);

			if (result_inquire == NULL)
			{
				printf("Doesn't find!\n");
			}
			else
			{
				printf("Sno: %d, Sname: %s, Source: %.1f\n", result_inquire->sno, result_inquire->sname, result_inquire->source);
			}
		}

		if (opt == 5)
		{
			system("cls");
			option();
			printf("Please enter Sname: \n");
			scanf("%s", sname);

			STU *result = InquireSname(pHeadNode, sname);

			if (result == NULL)
			{
				printf("Doesn't find!\n");
			}
			else
			{
				printf("Sno: %d, Sname: %s, Source: %.1f\n", result->sno, result->sname, result->source);
			}
		}

		if (opt == 6)
		{
			system("cls");
			option();
			printf("Please enter Sno: \n");
			scanf("%d", &sno);

			STU *result_inquire = InquireSno(pHeadNode, sno);

			int result_delete = DeleteFromSno(pHeadNode, result_inquire);

			if (result_inquire == NULL)
			{
				printf("Doesn't find!\n");
			}
			else if (result_delete == 0)
			{
				printf("Over!\n");
			}
		}

		if (opt == 7)
		{
			system("cls");
			option();
			printf("Please enter Sname: \n");
			scanf("%s", sname);

			STU *result_inquire = InquireSname(pHeadNode, sname);

			int result_delete = DeleteFromSno(pHeadNode, result_inquire);

			if (result_inquire == NULL)
			{
				printf("Doesn't find!\n");
			}
			else if (result_delete == 0)
			{
				printf("Over\n");
			}
		}

		if (opt == 8)
		{
			system("cls");
			option();
			printf("Please enter Sno: \n");
			scanf("%d", &sno);

			STU *result_modify = InquireSno(pHeadNode, sno);

			if (result_modify == NULL)
			{
				printf("Doesn't find!\n");
			}
			else
			{
				printf("Please enter Sno Sname Source: \n");
				scanf("%d %s %f", &sno, sname, &source);

				result_modify->sno = sno;
				result_modify->source = source;
				strcpy(result_modify->sname, sname);
				printf("Over!\n");
			}
		}

		if (opt == 9)
		{
			system("cls");
			option();
			SortUpFromSno(pHeadNode);

			printf("Over!\n");
		}

		if (opt == 10)
		{
			system("cls");
			option();
			printf("Please enter Sno Sname Source: \n");
			scanf("%d %s %f", &sno, sname, &source);
			InsertUpStuFromSno(pHeadNode, sno, sname, source);
			printf("Over!\n");
		}

		if (opt == 11)
		{
			system("cls");
			option();
			FreeStu(pHeadNode);
			pHeadNode = NULL;
			printf("Over!\n");
		}

		if (opt == 12)
		{
			system("cls");
			option();
			ReveserStu(pHeadNode)
			printf("Over!\n");
		}

		opt = -1;
	}
    
	return 0;
}

7.9 双向链表

#include <stdio.h>
typedef struct doublestudent
{
    int num;
    char name[30];
    float score;

    struct doublestudent *font;	//	上一个结点
    struct doublestudent *next;	//	下一个节点
} DSTU;

void Help(void)
{
    printf("00. 帮助!!\n");
    printf("01. 遍历查看!!\n");
    printf("02. 有序插入法插入一个学生结点信息!!\n");
    printf("03. 根据学号进行查找!!\n");
    printf("04. 根据学号删除进行查找!!\n");
    printf("05. 释放链表!!\n");
}

void Print_Link(DSTU *pNode)
{
    while (pNode != NULL)
    {
        printf("Num: %d, Name: %s, Score: %.2f\n", (*pNode).num, (*pNode).name, (*pNode).score);
        pNode = pNode->next;
    }
    
    printf("Over!\n");
}

void SquInsertDSTUNode(DSTU **ppNodeDSTU, int num, char *name, float score)
{
    DSTU *pMidNodeDSTU = (DSTU *)malloc(sizeof(DSTU));

    DSTU *pMidNodeDSTU1 = *ppNodeDSTU;
    pMidNodeDSTU->num = num;
    pMidNodeDSTU->score = score;
    strcpy(pMidNodeDSTU->name, name);
    pMidNodeDSTU->next = NULL;
    pMidNodeDSTU->font = NULL;
    
    if (NULL == *ppNodeDSTU)
    {
        *ppNodeDSTU = pMidNodeDSTU;
    }
    else
    {
        if (pMidNodeDSTU1->num > num)
        { 
            pMidNodeDSTU->next = pMidNodeDSTU1;
            pMidNodeDSTU1->font = pMidNodeDSTU;
            pMidNodeDSTU->font = NULL;
            *ppNodeDSTU = pMidNodeDSTU;
        }
        else
        {
            while (pMidNodeDSTU1->next != NULL)
            {
                if ((pMidNodeDSTU1->num < num) && (pMidNodeDSTU1->next->num > num))
                { 
                    pMidNodeDSTU->next = pMidNodeDSTU1->next;
                    pMidNodeDSTU1->next->font = pMidNodeDSTU;
                    pMidNodeDSTU->font = pMidNodeDSTU1;
                    pMidNodeDSTU1->next = pMidNodeDSTU;
                    
                    return ;
                }
                
                pMidNodeDSTU1 = pMidNodeDSTU1->next;
            }
            if (pMidNodeDSTU1->next == NULL)
            {
                 pMidNodeDSTU1->next = pMidNodeDSTU;
                 pMidNodeDSTU->font = pMidNodeDSTU1;
                 pMidNodeDSTU->next = NULL;
                 printf("BB\n");
            }
        }
    }
}

void FreeLink(DSTU **ppNodeDSTU)
{
    DSTU *pMidNodeDSTU = *ppNodeDSTU;
    
    if (pMidNodeDSTU == NULL)
    {
        return;
    }
    
    while (*ppNodeDSTU != NULL)
    {
        pMidNodeDSTU = *ppNodeDSTU;
        *ppNodeDSTU = (*ppNodeDSTU)->next;
        free(pMidNodeDSTU);
    }
}

int main()
{
    DSTU *pHeadNodeDSTU = NULL;
    intUserCmd = -1;
    intnum = 0;
    char name[30] = {0};
    float score = 0;
    
    Help();
    
    while (1)
    {
        scanf("%d", &UserCmd);
        
        if (0 == UserCmd)
        {
            Help();
        }
        
        if (1 == UserCmd)
        {
            Print_Link(pHeadNodeDSTU);
        }
        
        UserCmd = -1;
    }
    
    return 0;
}

码农公寓

第七章 链表

7.1 链表的概念

7.2 链表的创建

7.3 链表插入

7.3.1 头插法

7.3.2 尾插法

7.3.3 按学号升序插入学生

7.4 链表遍历

7.5 节点查找

7.5.1 按学号查询

7.5.2 按姓名查询

7.6 节点删除

7.6.1 按学号删除

7.6.2 按姓名删除

7.7 链表排序

7.7.1 按学号升序

7.7.2 逆序

7.8 主函数

7.9 双向链表

相关文章

第七章链表