C语言数据结构（4）单链表专题2.单链表的应用

发布于：2025-08-05 ⋅ 阅读:(15) ⋅ 点赞:(0)

1. 链表经典算法——OJ题目

1.1 单链表相关经典算法OJ题1：移除链表元素

1.2 单链表相关经典算法OJ题2：反转链表

1.3 单链表相关经典算法OJ题3：合并两个有序链表

1.4 单链表相关经典算法OJ题4：链表的中间结点

1.5 循环链表经典应用-环形链表的约瑟夫问题

著名的Josephus问题

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在 第16个与第31个位置，于是逃过了这场死亡游戏。

1.6 单链表相关经典算法OJ题5：分割链表

1.1 移除链表元素

没要求在原地完成移除元素操作。

新链表不创建新的空间，只需要创建两个头尾指针，辅助完成链表内部结点指向的更改。

1.2 反转链表

思路1：遍历+头插

思路2：三指针

传递给head的实参在函数调用结束后，依然指向Node1——传值调用。

需要用在主调函数内使用主调函数内的head，接收函数调用的返回值。

1.3 合并两个有序链表

思路1：将L2插入到L1中，过程中的控制比较复杂。

思路2：创建新链表L3，谁小谁尾插。

1.4 链表的中间结点

双指针法：源宿指针、快慢指针、……

1.5 环形链表的约瑟夫问题

图解分析。

1.5.1 新建结点

typedef struct ListNode ListNode;
ListNode* BuyNode(int x){
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    //可写可不写，一般不会申请失败
    //if(newNode == NULL){
    //    exit(1);
    //}

    newNode->val = x;
    newNode->next = NULL;
    
    return newNode;
}

1.5.2 新建环形链表

ListNode* createList(int n){
    ListNode* phead = BuyNode(1);
    ListNode* ptail = phead;
    for (int i = 2; i <= n; i++){
        ptail->next = BuyNode(i);
        ptail = ptail->next;
    }
    //链表要首尾相连，使其循环起来
    ptail->next = phead;
    return phead;
}

1.5.3 约瑟夫问题

int ysf(int n, int m ) {
    //创建不带头单向循环链表
    ListNode* head = createList(n);
    ListNode* pcur = head;
    ListNode* prev = NULL;

    //count==m就删除当前结点，并重置count，继续遍历递增
    int count = 1;                  //一开始pcur指向head，count就应该数了1
                
    //逢m删除节点
    while (pcur->next != pcur) {    //循环条件：不止一个结点
        if(count == m){
            //删除当前节点pcur,
            prev->next = pcur->next;
            free(pcur);
            //删除pcur节点之后，要让pcur走到新的位置，count置为初始值
            pcur = prev->next;
            count = 1;
        }
        else{
            //pcur往后走
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }
    //此时pcur结点就是幸存下来的唯一的一个节点
    return pcur->val;
}

提交代码。

但是自测运行。

问题：若m = 1时，第一次进循环就要删除pcur，而此时prev还是为空？

解决办法: createList方法不返回头结点，而是返回尾结点。既能知道第一个节点的前驱节点，也能够通过尾结点找到第一个节点。

1.6 分割链表

思路1：创建一个新链表，将原链表中小于x的结点头插，大于等于x的结点尾插。

思路2：创建两个新链表，一个大链表，一个小链表，遍历插入完后，小链表尾插大链表。

数组的分割可以从两边向中间遍历，左下标遇到大于等于x的就停下，右下标遇到小于x的就停下，然后交换数据，继续往中间走，while(left < right)。

2. 基于单链表再实现通讯录项目

2.1 单链表头文件

//SList.h
//
// Created by mm on 2023/6/13.
//
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"contact.h"
typedef struct PersonInfo SLTDataType;
//typedef int SLTDataType;

void SLTPrint(SLTNode* phead);
//头部插⼊删除/尾部插⼊删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);

2.2 通讯录头文件


//contact.h
#pragma once
#define NAME_MAX 100
#define SEX_MAX 4
#define TEL_MAX 11
#define ADDR_MAX 100
//前置声明
typedef struct SListNode contact;
//用户数据
typedef struct PersonInfo
{
    char name[NAME_MAX];
    char sex[SEX_MAX];
    int age;
    char tel[TEL_MAX];
    char addr[ADDR_MAX];
}PeoInfo;

//初始化通讯录
void InitContact(contact** con);
//添加通讯录数据
void AddContact(contact** con);
//删除通讯录数据
void DelContact(contact** con);
//展示通讯录数据
void ShowContact(contact* con);
//查找通讯录数据
void FindContact(contact* con);
//修改通讯录数据
void ModifyContact(contact** con);
//销毁通讯录数据
void DestroyContact(contact** con);

2.3 通讯录源文件


//contact.c
#define _CRT_SECURE_NO_WARNINGS
#include"contact.h"
#include"SList.h"

void LoadContact(contact** con) {
    FILE* pf = fopen("contact.txt", "rb");
    if (pf == NULL) {
        perror("fopen error!\n");
        return;
    }
    //循环读取文件数据
    PeoInfo info;
    while (fread(&info, sizeof(info), 1, pf))
    {
        SLTPushBack(con, info);
    }
    printf("历史数据导入通讯录成功！\n");
}

void InitContact(contact** con) {
    LoadContact(con);
}

void AddContact(contact** con) {
    PeoInfo info;
    printf("请输入姓名：\n");
    scanf("%s", &info.name);
    printf("请输入性别：\n");
    scanf("%s", &info.sex);
    printf("请输入年龄：\n");
    scanf("%d", &info.age);
    printf("请输入联系电话：\n");
    scanf("%s", &info.tel);
    printf("请输入地址：\n");
    scanf("%s", &info.addr);

    SLTPushBack(con, info);
    printf("插入成功！\n");
}

contact* FindByName(contact* con, char name[]) {
    contact* cur = con;
    while (cur)
    {
        if (strcmp(cur->data.name, name) == 0) {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

void DelContact(contact** con) {
    char name[NAME_MAX];
    printf("请输⼊要删除的用户姓名：\n");
    scanf("%s", name);
    contact* pos = FindByName(*con, name);
    if (pos == NULL) {
        printf("要删除的用户不存在，删除失败！\n");
        return;
    }
    SLTErase(con, pos);
    printf("删除成功！\n");
}

void ShowContact(contact* con) {
    printf("%-10s %-4s %-4s %15s %-20s\n", "姓名", "性别", "年龄", "联系电话",
    contact* cur = con;
    while (cur)
    {
        printf("%-10s %-4s %-4d %15s %-20s\n",
        cur->data.name,
        cur->data.sex,
        cur->data.age,
        cur->data.tel,
        cur->data.addr);
        cur = cur->next;
    }
}

void FindContact(contact* con) {
    char name[NAME_MAX];
    printf("请输⼊要查找的用户姓名：\n");
    scanf("%s", name);
    contact* pos = FindByName(con, name);
    if (pos == NULL) {
        printf("要查找的用户不存在，查找失败！\n");
        return;
    }
    printf("查找成功！\n");
    printf("%-10s %-4s %-4d %15s %-20s\n",
    pos->data.name,
    pos->data.sex,
    pos->data.age,
    pos->data.tel,
    pos->data.addr);
}

void ModifyContact(contact** con) {
    char name[NAME_MAX];
    printf("请输⼊要修改的用户名称:\n");
    scanf("%s", &name);
    contact* pos = FindByName(*con, name);
    if (pos == NULL) {
        printf("要查找的用户不存在，修改失败！\n");
        return;
    }
    printf("请输入要修改的姓名：\n");
    scanf("%s", pos->data.name);
    printf("请输入要修改的性别：\n");
    scanf("%s", pos->data.sex);
    printf("请输入要修改的年龄：\n");

    scanf("%d", &pos->data.age);
    printf("请输入要修改的联系电话：\n");
    scanf("%s", pos->data.tel);
    printf("请输入要修改的地址：\n");
    scanf("%s", pos->data.addr);
    printf("修改成功！\n");
}

void SaveContact(contact* con) {
    FILE* pf = fopen("contact.txt", "wb");
    if (pf == NULL) {
        perror("fopen error!\n");
        return;
    }
    //将通讯录数据写入文件
    contact* cur = con;
    while (cur)
    {
        fwrite(&(cur->data), sizeof(cur->data), 1, pf);
        cur = cur->next;
    }
    printf("通讯录数据保存成功！\n");
}

void DestroyContact(contact** con) {
    SaveContact(*con);
    SListDesTroy(con);
}

完

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布