IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 动态链表整理 -> 正文阅读

[数据结构与算法]动态链表整理

动态链表

链表的定义

前置知识

  • 主要涉及结构体,指针,以及函数的知识

链表的储存

  • 本文章主要采用的是链式储存的方法

  • 需要定义一个结构体,包括数据以及之战两部分

    struct node 
    { 
        int data; //储存当前结点的数值
        struct node * next; //存放下一个结点的地址
    }; 
    
  • 为了方便之后操作我们可以用typedef对结构体类型重命名

    typedef struct node 
    { 
        int data; 
        struct node * next; 
    } Node; 
    
  • 接下来我们试在主函数中,创建空链表

     Node * head = NULL; //指针指向空
    
  • 最后要释放连接

    void freeList(Node ** pHead) 
    { 
        Node * p = *pHead; 
        Node * pre; 
        while (p != NULL) 
        { 
            pre = p; p = p->next;
            free(pre); 
        }
        *pHead = NULL; 
    }
    

按顺序插入数据(尾插)

  • 大致思路为将前一个结点的指针指向新结点
  • 新结点的指针应当指向空结点(成为尾节点)
  • 注意:当原有链表为空时,要将主函数中的头结点指向新结点
//因为要对头结点进行修改,所以传入的时头节点的地址
//头结点地址,加入的数据
void push_back_list(Node ** phead, int data) 
{ 
    //动态链表要申请动态的内存 
    Node * newNode = (Node *)malloc(sizeof(Node)); 
    newNode->data = data; 
    newNode->next = NULL; 
    // 判断原链表是否为空链表 
    if (*phead == NULL) 
    {  
        *phead = newNode; 
    } 
    else 
    { 
        Node * temp = *pHead; 
        // 循环判断寻找尾结点
        while (temp->next != NULL) 
            temp = temp->next; // 原链表尾节点指向新节点 
        temp->next = newNode; 
    } 
}

常见链表操作

链表元素统计与打印
  • 主要依靠循环遍历
void printList(Node * head) 
{ 
    Node * p;
    for (p=head; p!=NULL; p=p->next) 
        printf("%d ", p->data); //等价于 `*p.`
    puts(""); 
}

int size_list(Node *phead)
{
    int cnt = 0;
    Node *p;
    for(p = phead; p != NULL; p = p->next)
        cnt ++;
    
    return cnt;
}
插入结点
  • 含n个结点的链表有n+1个位置可以插入,插到n位置需要n + 1次(找到插入位置之前的结点)
  • 先将新结点的指针指向后结点再将前结点的指针指向新结点
    • 顺序反过来会产生环,而且会丢失数据
      在这里插入图片描述
//头结点地址,插入位置,插入数据
void insert_list(Node **phead,int index, int date)
{
    if(index < 0 || index > size_list(*phead)) 
        return;

    Node *newNode;
    newNode = (Node*)malloc(sizeof(Node));
    newNode -> next = NULL;
    newNode -> data = date;
    
    //特判插入头结点时
    if(index == 0)
    {
        newNode->next = *phead;
        *phead = newNode;
        return;
    }

    Node *p;
    p = *phead;
    int i;
    for(i = 0; i < index - 1; i ++)
        p = p ->next;
    newNode->next = p->next;
    p->next = newNode;
}
删除结点(删除所有出现的某个数)
  • 将需要删除结点a的前一个结点的指针指向a后的一个结点

  • 删除头结点时需特殊处理(不需要再找它前面的结点)

  • 删除第一次出现的某个数思想类似,将循环稍加改动即可
    在这里插入图片描述

//头结点地址以及需要删除的数字
//随删随释放内存
void delete_list(Node **phead, int date)
{
    Node *p = *phead; 

    while(p->next != NULL)
    {
        if(p->next->data == date)
        {
            Node *t = p->next;
            p ->next = t->next;
            free(t);
        }
        else p = p->next;
    }

    p = *phead;
    if(p->data == date)
    {
        *phead = p->next;
        free(p);
    }
}
t = t->next;
            free(t);
        }
        else p = p->next;
    }

    p = *phead;
    if(p->data == date)
    {
        *phead = p->next;
        free(p);
    }
}

练习

实现一个具有如下功能的电话本

-------------------------
      超级电子号码本     
 ------------------------
   1 :添加号码          
   2 :查询号码
   3 :删除号码
   4 :打印所有号码
   5 :退出
 ------------------------
 请选择您好进行的操作:

// 1:  依次输入姓名和号码
// 2、3:  根据姓名查号码
// 4:  按照添加顺序打印
code
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <windows.h>

typedef struct number
{
    char name[100];
    char phone_num[100];
} Number;

typedef struct node
{
    Number data;
    struct node * next;
} Node;


void print_menu()
{
    puts("------------------------");
    puts("   1 :添加号码          ");
    puts("   2 :查询号码");
    puts("   3 :删除号码");
    puts("   4 :打印所有号码");
    puts("   5 :退出");
    puts(" ------------------------");
    printf("请选择您好进行的操作:");
}

void print_list(Node *head)
{
    Node *p;
    for(p = head; p != NULL; p = p->next)
        printf("%s\t%s\n", p->data.name, p->data.phone_num);
}

Node *push_back(Node *head)
{

    Node *p;
    Node * new_node = (Node *)malloc(sizeof(Node));
    new_node->next = NULL;
    puts("请输入需要储存的姓名:");
    scanf("%s", new_node->data.name);
    puts("请输入需要储存的号码:");
    scanf("%s", new_node->data.phone_num);

    if(head == NULL)
    {
        return new_node;
    }

    p = head;
    while(p->next != NULL)
        p = p ->next;

    p->next = new_node;

    return head;
}

void find_list(Node *head)
{
    Node *p = head;
    char name[100];

    if(head == NULL)
    {
        puts("当前电话本为空, 无法进行删除!");
        return ;
    }

    puts("请输入要查询的姓名:");
    scanf("%s", name);
    for(p = head; p != NULL; p = p->next)
    {
        if(strcmp(p->data.name, name) == 0)
            printf("%s\t%s\n", p->data.name, p->data.phone_num);
        return;
    }
    puts("未找到此纪录!");

}

Node *delete_list(Node *head)
{
    char name[100];
    Node *p = head;

    if(head == NULL)
    {
        puts("当前电话本为空, 无法进行删除!");
        return head;
    }
    puts("请输入你需要删除信息的姓名:");
    scanf("%s", name);

    while(p ->next != NULL)
    {
        if(strcmp(p->next->data.name, name) == 0)
        {
            Node *t = p->next;
            p->next = t->next;
            free(t);
        }
        else p = p->next;
    }

    p = head;
    if(strcmp(p->data.name, name) == 0)
    {
        head = p->next;
        free(p);
    }
    puts("删除成功!");

    return head;
}

int main()
{

    Node *head = NULL;
    int op;

    while(1)
    {
        system("cls");
        print_menu();
        scanf("%d", &op);

        switch(op)
        {
            case 1:
                head = push_back(head);
                break;
            case 2:
                find_list(head);
                system("pause");
                break;
            case 3:
                head = delete_list(head);
                system("pause");
                break;
            case 4:
                print_list(head);
                system("pause");
                break;
            case 5:
                puts("欢迎下次使用!");
                return 0;
            default :
                break;
        }
    }
    return 0;
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-21 19:13:41  更:2022-05-21 19:15:56 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年3日历 -2024/3/29 15:53:45-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码