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 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【C语言】链表的一般设计步骤 -> 正文阅读

[数据结构与算法]【C语言】链表的一般设计步骤

一、链表的设计原理（一般建议使用堆空间存放链表）

  1. 设计链表的节点（数据域+指针域）

  2. 创建链表头结点（head）头结点相当于定义这一条链表的起点（钥匙）
    初始化链表头结点（数据域 + 指针域）

  3. 创建链表子节点（node）子节点插入到头结点后面（可以存储更多信息）
    初始化链表子结点（数据域 + 指针域）

  4. 插入节点（insert）将创建的节点放进链表里面，创立完整链表。
    尾插法，将新节点放置链表末尾
    头插法，将新节点放置头结点后一个
    排序插法，可以按冲从小到大，也可以从大到小

  5. 剔除节点（delete）
    将不需要节点删除，将链表不需要的节点从链表中拿出来，从此和链表无关。
    原理是：使用链表头结点，遍历整个链表，将各节点中的数据与待删除数据作用是比对，可找到剔除节点的位置。将该节点从链表中删除。

  6. 修改节点内的数据
    更改节点数据域中的内容

  7. 销毁链表
    如果链表是使用堆空间存储，销毁链表时需使用free函数将每个节点的堆空间释放

二、链表代码设计 （双向循环链表）

  1. 设计链表的节点（数据域+指针域）
typedef struct double_clink_list
{
    int data;							//数据域
    struct double_clink_list * next;	//后继指针
    struct double_clink_list * prev;	//前驱指针

}double_cll,*double_cll_p;				//重命名
  1. 创建链表头结点（head）
/**********************************************************************
**函数    :double_cll_p init_double_cll(void)	
**函数说明 : 创建头结点
**形参说明 :无  
**返回值  :  成功返回 新创建的头结点地址  
			失败返回 空地址
**********************************************************************/
double_cll_p init_double_cll(void)					 	 //创建头节点
{
    double_cll_p head = calloc(1,sizeof(double_cll));	//申请堆空间存放头结点
    if(head == NULL)									//判断申请是否成功
    {
        printf("init_double_cll error\n");        
        return NULL;									//失败直接返回
    }
    head->data = 0;										//初始化数据域
    head->next = head;									//初始化后继指针
    head->prev = head;									//初始化前驱指针
    return head;										//返回头结点地址
}
  1. 创建链表子节点（node）
/**********************************************************************
**函数    :double_cll_p create_node_double_cll(int data)
**函数说明 : 创建子节点
**形参说明 : data 为存放在 子节点数据域的数据 
**返回值  :  成功返回 新创建的子结点地址  
			失败返回 空地址
**********************************************************************/
double_cll_p create_node_double_cll(int data)			//创建子节点
{
    double_cll_p node = calloc(1,sizeof(double_cll));	//申请堆空间存放子节点
    if(node == NULL)									//判断申请是否成功
    {
        printf("create_node_double_cll error\n");        
        return NULL;									//失败直接返回
    }
    node->data = data;									//初始化数据域
    node->next = node;									//初始化后继指针
    node->prev = node;									//初始化前驱指针
    return node;										//返回子结点地址
}
  1. 插入节点（insert）
/**********************************************************************
**函数    :int tail_insert_double_cll(double_cll_p node,double_cll_p head)
**函数说明 : 尾插法，将新节点放置链表末尾
**形参说明 : node 为待插入子节点的地址    head为链表头节点的地址 
**返回值  :  成功返回 0
			失败返回 -1
**********************************************************************/
int tail_insert_double_cll(double_cll_p node,double_cll_p head)//尾插法，将新节点放置链表末尾
{
    if(head == NULL || node == NULL)			//判断头结点与子节点地址是否为空
    {
        printf("tail_insert_double_cll error\n");
        return -1;								//失败直接返回-1
    }
    //以下部分理解不了的自己画个图 或者 看我下面的图
    node->prev = head->prev;					//子节点前驱指针 指向 头结点前驱指针指向的子节点
    node->next = head;							//子节点后继指针 指向 头结点
    head->prev = node;							//头节点前驱指针 指向 子结点
    node->prev->next = node;					//头结点前驱指针 指向 的子节点的后继指针 指向 新子结点
    return 0;									//成功返回0
    
}

尾插图解
在这里插入图片描述

/**********************************************************************
**函数    :int head_insert_double_cll(double_cll_p node,double_cll_p head)
**函数说明 : 头插法，将新节点放置头结点后一个
**形参说明 : node 为待插入子节点的地址    head为链表头节点的地址 
**返回值  :  成功返回 0
			失败返回 -1
**********************************************************************/
int head_insert_double_cll(double_cll_p node,double_cll_p head)//头插法，将新节点放置头结点后一个
{
    if(head == NULL|| node == NULL)				//判断头结点与子节点地址是否为空
    {
        printf("head_insert_double_cll error\n");
        return -1;								//失败直接返回-1
    }
     //以下部分理解不了的自己画个图 
    node->next = head->next;			//子节点后继指针 指向 头结点后继指针指向的子节点
    head->next = node;					//头节点后继驱 指针 指向子结点
    node->prev = head;					//子节点前驱指针 指向 头结点
    node->next->prev = node;			//头结点后继指针 指向 的子节点的前驱指针 指向 新子结点
    return 0;							//成功返回0
	
	//或者
    //将新节点插入到head->next的前面 
    //tail_insert_double_cll(node,head->next);
}

/**********************************************************************
**函数    :int sort_insert_double_cll(double_cll_p node,double_cll_p head)
**函数说明 : 排序插法，可以按从从小到大排序插入，也可以从大到小排序插入
**形参说明 : node 为待插入子节点的地址    head为链表头节点的地址 
**返回值  :  成功返回 0
			失败返回 -1
**********************************************************************/
int sort_insert_double_cll(double_cll_p node,double_cll_p head)//排序插法，可以按冲从小到大，也可以从大到小
{
    if(head == NULL || node == NULL)				//判断头结点与子节点地址是否为空
    {
        printf("sort_insert_double_cll error\n");
        return -1;									//失败直接返回-1
    }
    double_cll_p  p = head;						//定义一个指针变量存放头结点地址
    for(;p->next != head;p = p->next)			//遍历整个链表，如果指针p再次指向head地址，说明已经遍历完
    {
        if(p->next->data > node->data)			//从小到大排序 插入
        {
            node->next = p->next;
            p->next = node;
            node->next->prev = node;
            node->prev = p;
            return 0;							//插入成功返回0
        }
    //     if(p->next->data < node->data)		//从大到小排序插入
    //     {
    //         node->next = p->next;
    //         p->next = node;
    //         node->next->prev = node;
    //         node->prev = p;
    //         return 0;						//插入成功返回0
    //     }
    }
    //如果链表只有头结点，那么子节点直接插入即可		
    node->next = p->next;
    p->next = node;
    node->next->prev = node;
    node->prev = p;
    return 0;					//插入成功返回0
}
  1. 剔除节点（delete）
/**********************************************************************
**函数    :int del_double_cll(double_cll_p p,double_cll_p head)
**函数说明 : 删除指定地址的节点
**形参说明 : p 为待剔除子节点的地址    head为链表头节点的地址 
**返回值  :  成功返回 0
			失败返回 -1
**********************************************************************/
int del_double_cll(double_cll_p p,double_cll_p head)//删除指定地址的节点
{
    if(p == NULL || head == NULL)			//判断头结点与子节点地址是否为空
    {
        printf("del_double_cll error\n");
        return -1;							//失败直接返回-1
    }
    p->next->prev = p->prev;				//将要删除的子节点断链
    p->prev->next = p->next;				//将要删除的子节点断链
    p->next = NULL;							//将要删除的子节点后继指针 指向 空
    p->prev = NULL;							//将要删除的子节点前驱指针 指向 空
    free(p);								//释放子节点的堆空间
    return 0;   							//剔除成功返回0
}
  1. 查找对应数据节点并返回该节点地址
/**********************************************************************
**函数    :double_cll_p find_double_cll(int data,double_cll_p head)
**函数说明 : 查找对应数据节点并返回该节点地址
**形参说明 : data 为待查找数据    head为链表头节点的地址 
**返回值  :  成功返回 待查找数据节点地址
			失败返回 空地址
**********************************************************************/
double_cll_p find_double_cll(int data,double_cll_p head)//查找对应数据节点并返回该节点地址
{
    if(head == NULL)						//判断头结点地址是否为空
    {
        printf("find_double_cll error\n");
        return NULL;					//失败直接返回空地址
    }
    double_cll_p p = head->next;		//定义一个指针变量 存放 头结点后继指针指向节点 的地址
    for(;p != head; p = p->next)		//遍历整个链表，如果指针p再次指向head地址，说明已经遍历完
    {
        if(p->data == data)   			//遍历的过程中，如果子节点数据 等于 待查找数据，则返回该子节点地址
            return p;					//返回子节点地址
    }
    return NULL;						//找不到返回 空地址
}
  1. 销毁链表
/**********************************************************************
**函数    :int free_double_cll(double_cll_p head)
**函数说明 : 释放链表所有内存
**形参说明 : head为链表头节点的地址 
**返回值  :  成功返回 0
			失败返回 -1
**********************************************************************/
int free_double_cll(double_cll_p head)//释放链表所有内存
{
    if(head == NULL)					//判断头结点地址是否为空
    {
        printf("double_cll not exist\n");
        return -1;						//失败直接返回-1
    }
    double_cll_p p = head;				//定义一个指针变量 存放 头结点 的地址
    for(;p->next != head;)				//遍历整个链表，如果指针p再次指向head地址，说明已经遍历完
    {
        p = p->next;					//变量p指向下一个节点
        free(p->prev);					//释放前一个节点的 堆空间（断链）
    } 
    free(p);							//释放头节点 堆空间
    return 0;							//链表销毁成功返回 0
}

完整 C程序 和 头文件

//双向循环链
#include "double_cll.h"

int main(int argc,char *argv[])
{
    double_cll_p head = init_double_cll();//创建头结点
    int data;//输入数据
    double_cll_p q = NULL;//存放需要删除节点的地址
    while(1)
    {
        scanf("%d",&data);//从键盘读取一个数据
        if(data>0)
        { 
            if(NULL==find_double_cll(data,head))//禁止输入重复的数据
            {
                double_cll_p node = create_node_double_cll(data);//创建子节点
                sort_insert_double_cll(node,head);//使用排序插入方式将子节点插入到链表   
            }
            else
            {
                printf("data repetition \n");
            }
            show_double_cll(head); //使用链表正顺序输出  

        }
        else if(data ==0)
            break; 
        else
        {
            if((q=find_double_cll(-data,head))!=NULL)//查找是否存在需要删除的数据
            {
                del_double_cll(q,head);//删除指定节点地址的 整个节点
            }
            else
            {
                printf("data absence \n"); 
            }
            show_double_cll(head);//使用链表正顺序输出  
        }
    }
    free_double_cll(head);//释放内存
    return 0;
}


double_cll_p init_double_cll(void)//创建头节点
{
    double_cll_p head = calloc(1,sizeof(double_cll));
    if(head == NULL)
    {
        printf("init_double_cll error\n");        
        return NULL;
    }
    head->data = 0;
    head->next = head;
    head->prev = head;
    return head;
}

double_cll_p create_node_double_cll(int data)//创建子节点
{
    double_cll_p node = calloc(1,sizeof(double_cll));
    if(node == NULL)
    {
        printf("create_node_double_cll error\n");        
        return NULL;
    }
    node->data = data;
    node->next = node;
    node->prev = node;
    return node;
}

int tail_insert_double_cll(double_cll_p node,double_cll_p head)//尾插法，将新节点放置链表末尾
{
    if(head == NULL || node == NULL)
    {
        printf("tail_insert_double_cll error\n");
        return -1;
    }
    node->prev = head->prev;
    node->next = head;
    head->prev = node;
    node->prev->next = node;
    return 0;
}

int head_insert_double_cll(double_cll_p node,double_cll_p head)//头插法，将新节点放置头结点后一个
{
    if(head == NULL|| node == NULL)
    {
        printf("head_insert_double_cll error\n");
        return -1;
    }
    node->next = head->next;
    head->next = node;
    node->prev = head;
    node->next->prev = node;
    return 0;

    //将新节点插入到head->next的前面
    //tail_insert_double_cll(node,head->next);
}

int sort_insert_double_cll(double_cll_p node,double_cll_p head)//排序插法，可以按冲从小到大，也可以从大到小
{
    if(head == NULL || node == NULL)
    {
        printf("sort_insert_double_cll error\n");
        return -1;
    }
    double_cll_p  p = head;
    for(;p->next != head;p = p->next)
    {
        if(p->next->data > node->data)//从小到大排序插入
        {
            node->next = p->next;
            p->next = node;
            node->next->prev = node;
            node->prev = p;
            return 0;
        }
    //     if(p->next->data < node->data)//从大到小排序插入
    //     {
    //         node->next = p->next;
    //         p->next = node;
    //         node->next->prev = node;
    //         node->prev = p;
    //         return 0;
    //     }
    }
    node->next = p->next;
    p->next = node;
    node->next->prev = node;
    node->prev = p;
    return 0;
}

int show_double_cll(double_cll_p head)//按链表正顺序输出
{
    if(head == NULL)
    {
        printf("show_double_cll error\n");
        return -1;
    }
    double_cll_p p = head;
    for(;p->next!=head;p = p->next)
    {
        printf("%d\t",p->next->data);
    }
    printf("\n");
    return 0;
}

double_cll_p find_double_cll(int data,double_cll_p head)//查找对应数据节点并返回该节点地址
{
    if(head == NULL)
    {
        printf("find_double_cll error\n");
        return NULL;
    }
    double_cll_p p = head->next;
    for(;p != head; p = p->next)
    {
        if(p->data == data)   
            return p;//重复返回1
    }
    return NULL;//没有重复
}

int free_double_cll(double_cll_p head)//释放链表所有内存
{
    if(head == NULL)
    {
        printf("double_cll not exist\n");
        return -1;
    }
    double_cll_p p = head;
    for(;p->next != head;)
    {
        p = p->next;
        free(p->prev);
    } 
    free(p);
    return 0;
}

int del_double_cll(double_cll_p p,double_cll_p head)//删除指定地址的节点
{
    if(p == NULL || head == NULL)
    {
        printf("del_double_cll error\n");
        return -1;
    }
    p->next->prev = p->prev;
    p->prev->next = p->next;
    p->next = NULL;
    p->prev = NULL;
    free(p);
    return 0;   
}

#ifndef __double_cll_h__
#define __double_cll_h__

#include<stdio.h>
#include <stdlib.h> 

typedef struct double_clink_list
{
    int data;
    struct double_clink_list * next;
    struct double_clink_list * prev;

}double_cll,*double_cll_p;


double_cll_p init_double_cll(void);//创建头节点
double_cll_p create_node_double_cll(int data);//创建子节点

int tail_insert_double_cll(double_cll_p node,double_cll_p head);//尾插法，将新节点放置链表末尾
int head_insert_double_cll(double_cll_p node,double_cll_p head);//头插法，将新节点放置头结点后一个
int sort_insert_double_cll(double_cll_p node,double_cll_p head);//排序插法，可以按冲从小到大，也可以从大到小

int show_double_cll(double_cll_p head);//按链表正顺序输出
double_cll_p find_double_cll(int data,double_cll_p head);//查找对应数据节点并返回该节点地址
int free_double_cll(double_cll_p head);//释放链表所有内存
int del_double_cll(double_cll_p p,double_cll_p head);//删除指定地址的节点

#endif

结束语：需要完整C程序的私信我发邮箱
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-08-05 17:36:08  更:2021-08-05 17:37:24 
 
开发: 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年11日历 -2024/11/25 18:30:45-

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