当前位置: 首页 > news >正文

(C语言版)链表(三)——实现双向链表创建、删除、插入、释放内存等简单操作...

上午写了下单向循环链表的程序,今天下午我把双向链表的程序写完了。其实双向链表和单向链表也是有很多相似的地方的,听名字可以猜到,每个节点都包含两个指针,一个指针指向上一个节点,一个指针指向下一个节点。这里有两个特殊的地方,第一就是头节点的一个指针指向NULL空指针(没有前驱节点),第二就是尾节点的一个指针指向NULL指针(没有后继节点)。

我们可以看下双向链表的示意图(自己画的比较难看):

所以,我们在编程序的时候,这两个指针的控制就是我们的难点,因为我们始终要让这个链表保持这样的链接不管是在创建的时候、插入的时候、删除的时候等,一定要让节点的两个指针指向正确的节点。下面我们来看下双向链表的代码。

DbLinkList.h  头文件——包含节点结构的定义和各种操作函数的声明。

 

#ifndef DOUBLY_LINKED_LIST_H  
#define DOUBLY_LINKED_LIST_H  
  
typedef struct Node  
{  
    int data;  
    struct Node *pNext;  
    struct Node *pPre;  
}NODE, *pNODE;  
  
//创建双向链表  
pNODE CreateDbLinkList(void);  
  
//打印链表  
void TraverseDbLinkList(pNODE pHead);  
  
//判断链表是否为空  
int IsEmptyDbLinkList(pNODE pHead);  
  
//计算链表长度  
int GetLengthDbLinkList(pNODE pHead);  
  
//向链表插入节点  
int InsertEleDbLinkList(pNODE pHead, int pos, int data);  
  
//从链表删除节点  
int DeleteEleDbLinkList(pNODE pHead, int pos);  
  
//删除整个链表,释放内存  
void FreeMemory(pNODE *ppHead);  
  
#endif  

 

DbLinkList.cpp 双向链表的源文件——包含了各种操作函数的定义。

 

(1)这部分是创建双向链表,和单向链表很相似,但是呢,有些地方还是得注意,就是每创建一个节点的时候都要注意初始化它的两个指针。

#include <stdio.h>  
#include <stdlib.h>  
#include "DbLinkList.h"  
  
//创建双向链表  
pNODE CreateDbLinkList(void)  
{  
    int i, length = 0, data = 0;  
    pNODE pTail = NULL, p_new = NULL;  
    pNODE pHead = (pNODE)malloc(sizeof(NODE));  
  
    if (NULL == pHead)  
    {  
        printf("内存分配失败!\n");  
        exit(EXIT_FAILURE);  
    }  
      
    pHead->data = 0;  
    pHead->pPre = NULL;  
    pHead->pNext = NULL;  
    pTail = pHead;  
  
    printf("请输入想要创建链表的长度:");  
    scanf("%d", &length);  
  
    for (i=1; i<length+1; i++)  
    {  
        p_new = (pNODE)malloc(sizeof(NODE));  
  
        if (NULL == p_new)  
        {  
            printf("内存分配失败!\n");  
            exit(EXIT_FAILURE);  
        }  
  
        printf("请输入第%d个元素的值:", i);  
        scanf("%d", &data);  
  
        p_new->data = data;  
        p_new->pNext = NULL;  
        p_new->pPre = pTail;  
        pTail->pNext = p_new;  
        pTail = p_new;  
    }  
  
    return pHead;  
}  

 


(2)这部分是获得双向链表的信息,这里和单向链表基本一致,因为遍历的时候只用到了一个指针。

 

 

[cpp]  view plain  copy
 
 在CODE上查看代码片派生到我的代码片
  1. //打印链表  
  2. void TraverseDbLinkList(pNODE pHead)  
  3. {  
  4.     pNODE pt = pHead->pNext;  
  5.   
  6.     printf("打印链表如:");  
  7.     while (pt != NULL)  
  8.     {  
  9.         printf("%d ", pt->data);  
  10.         pt = pt->pNext;  
  11.     }  
  12.     putchar('\n');  
  13. }  
  14.   
  15. //判断链表是否为空  
  16. int IsEmptyDbLinkList(pNODE pHead)  
  17. {  
  18.     pNODE pt = pHead->pNext;  
  19.   
  20.     if (p == NULL)  
  21.         return 1;  
  22.     else  
  23.         return 0;  
  24. }  
  25.   
  26. //计算链表的长度  
  27. int GetLengthDbLinkList(pNODE pHead)  
  28. {  
  29.     int length = 0;  
  30.     pNODE pt = pHead->pNext;  
  31.   
  32.     while (pt != NULL)  
  33.     {  
  34.         length++;  
  35.         pt = pt->pNext;  
  36.     }  
  37.     return length;  
  38. }  


(3)这部分是向双向链表插入节点,也跟单向链表很多相似的地方。我们先来看下插入节点时的示意图:

 

从图中可以看到,每次我们添加一个节点都有很多地方要调节的,也就是每个节点的那两个指针,一定要认真仔细自己动手写一遍,有可能有些细节就会出错。这里有一个地方需要注意,是和单向链表不同的地方,单向链表在插入节点的时候不需要判断最后一个节点是否为空,因为这不影响程序的结果,但是对于双向链表就不一样了,因为我们后面要用到最后一个节点的一个指针指向前一个节点,如果最后一个节点是空的话(就是程序中的pt),就不存在pt->pPre了,那么程序运行到这里时就会报错,所以我们要加个判断,判断此时节点是NULL的话就不需要控制它的指针了。

 

[cpp]  view plain  copy
 
 在CODE上查看代码片派生到我的代码片
  1. //向双向链表中插入节点  
  2. int InsertEleDbLinkList(pNODE pHead, int pos, int data)  
  3. {  
  4.     pNODE pt = NULL, p_new = NULL;  
  5.   
  6.     if (pos > 0 && pos < GetLengthDbLinkList(pHead)+2)  
  7.     {  
  8.         p_new = (pNODE)malloc(sizeof(NODE));  
  9.   
  10.         if (NULL == p_new)  
  11.         {  
  12.             printf("内存分配失败!\n");  
  13.             exit(EXIT_FAILURE);  
  14.         }  
  15.   
  16.         while (1)  
  17.         {  
  18.             pos--;  
  19.             if (0 == pos)  
  20.                 break;  
  21.             pHead = pHead->pNext;  
  22.         }  
  23.           
  24.         pt = pHead->pNext;  
  25.         p_new->data = data;  
  26.         p_new->pNext = pt;  
  27.         if (NULL != pt)  
  28.             pt->pPre = p_add;  
  29.         p_new->pPre = pHead;  
  30.         pHead->pNext = p_new;  
  31.           
  32.         return 1;  
  33.     }  
  34.     else  
  35.         return 0;  
  36. }  


(4)这部分是从链表中删除节点,当然这里和单向链表差不多,要注意的地方和插入节点时是一样的,上面已经说明了。

 

 

[cpp]  view plain  copy
 
 在CODE上查看代码片派生到我的代码片
  1. //从链表中删除节点  
  2. int DeleteEleDbLinkList(pNODE pHead, int pos)  
  3. {  
  4.     pNODE pt = NULL;  
  5.   
  6.     if (pos > 0 && pos < GetLengthDbLinkList(pHead) + 1)  
  7.     {  
  8.         while (1)  
  9.         {  
  10.             pos--;  
  11.             if (0 == pos)  
  12.                 break;  
  13.             pHead = pHead->pNext;  
  14.         }  
  15.   
  16.         pt = pHead->pNext->pNext;  
  17.         free(pHead->pNext);  
  18.         pHead->pNext = pt;  
  19.         if (NULL != pt)  
  20.             pt->pPre = pHead;  
  21.   
  22.         return 1;  
  23.     }  
  24.     else  
  25.         return 0;  
  26. }  


(5)这部分是用来释放内存的,注意的地方和上面一样。

 

 

[cpp]  view plain  copy
 
 在CODE上查看代码片派生到我的代码片
  1. //删除整个链表,释放内存  
  2. void FreeMemory(pNODE *ppHead)  
  3. {  
  4.     pNODE pt = NULL;  
  5.   
  6.     while (*ppHead != NULL)  
  7.     {  
  8.         pt = (*ppHead)->pNext;  
  9.         free(*ppHead);  
  10.         if (NULL != pt)  
  11.             pt->pPre = NULL;  
  12.         *ppHead = pt;  
  13.     }  
  14. }  


main.cpp 测试程序源文件——通过简单的交互信息来测试各个函数功能是否正确。

 

 

[cpp]  view plain  copy
 
 在CODE上查看代码片派生到我的代码片
  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include "DbLinkList.h"  
  4.   
  5. int main(void)  
  6. {  
  7.     int flag = 0, length = 0;  
  8.     int position = 0, value = 0;  
  9.     pNODE head = NULL;  
  10.   
  11.     head = CreateDbLinkList();  
  12.   
  13.     flag = IsEmptyDbLinkList(head);  
  14.     if (flag)  
  15.         printf("双向链表为空!\n");  
  16.     else  
  17.     {  
  18.         length = GetLengthDbLinkList(head);  
  19.         printf("双向链表的长度为:%d\n", length);  
  20.         TraverseDbLinkList(head);  
  21.     }  
  22.   
  23.     printf("请输入要插入节点的位置和元素值(两个数用空格隔开):");  
  24.     scanf("%d %d", &position, &value);  
  25.     flag = InsertEleDbLinkList(head, position, value);  
  26.     if (flag)  
  27.     {  
  28.         printf("插入节点成功!\n");  
  29.         TraverseDbLinkList(head);  
  30.     }     
  31.     else  
  32.         printf("插入节点失败!\n");  
  33.   
  34.     flag = IsEmptyDbLinkList(head);  
  35.     if (flag)  
  36.         printf("双向链表为空,不能进行删除操作!\n");  
  37.     else  
  38.     {  
  39.         printf("请输入要删除节点的位置:");  
  40.         scanf("%d", &position);  
  41.         flag = DeleteEleDbLinkList(head, position);  
  42.         if (flag)  
  43.         {  
  44.             printf("删除节点成功!\n");  
  45.             TraverseDbLinkList(head);  
  46.         }     
  47.         else  
  48.             printf("删除节点失败!\n");  
  49.     }  
  50.   
  51.     FreeMemory(&head);  
  52.     if (NULL == head)  
  53.         printf("已成功删除双向链表,释放内存完成!\n");  
  54.     else  
  55.         printf("删除双向链表失败,释放内存未完成!\n");  
  56.   
  57.     return 0;  
  58. }  


PS:相信对很多人来说链表的相关知识其实不难,很快能把这个程序编出来。但是还是有很多细节的问题要自己编过才知道的,我自己在学习的过程中就遇到过,所以我不让大家再走弯路。

转载于:https://www.cnblogs.com/Ph-one/p/6367417.html

相关文章:

  • 双链表插入 删除详解
  • 存储数据的大小端模式
  • ppp点对点协议
  • MPEG2、MPEG4、H264的差异
  • 可以参考的几个英文论坛
  • 强烈推荐的一个博客 图灵官方博客
  • H264 介绍[1]
  • H264 层次构成[2]
  • H264编码技术[3]
  • H264--1--编码原理以及I帧B帧P帧[4]
  • H264--2--语法及结构[5]
  • H264--3--NAL层的处理[6]
  • H264--4--H264编码[7]
  • H264--5--H264解码[8]
  • 静态编译与动态编译的区别
  • C++11: atomic 头文件
  • css属性的继承、初识值、计算值、当前值、应用值
  • Dubbo 整合 Pinpoint 做分布式服务请求跟踪
  • iOS | NSProxy
  • Joomla 2.x, 3.x useful code cheatsheet
  • JS笔记四:作用域、变量(函数)提升
  • Mac 鼠须管 Rime 输入法 安装五笔输入法 教程
  • maven工程打包jar以及java jar命令的classpath使用
  • MySQL Access denied for user 'root'@'localhost' 解决方法
  • Ruby 2.x 源代码分析:扩展 概述
  • supervisor 永不挂掉的进程 安装以及使用
  • vagrant 添加本地 box 安装 laravel homestead
  • 分享一份非常强势的Android面试题
  • 搞机器学习要哪些技能
  • 诡异!React stopPropagation失灵
  • 好的网址,关于.net 4.0 ,vs 2010
  • 如何用vue打造一个移动端音乐播放器
  • 数据仓库的几种建模方法
  • 云栖大讲堂Java基础入门(三)- 阿里巴巴Java开发手册介绍
  • 整理一些计算机基础知识!
  • ​​​​​​​​​​​​​​Γ函数
  • #pragma 指令
  • $L^p$ 调和函数恒为零
  • (14)Hive调优——合并小文件
  • (ZT)薛涌:谈贫说富
  • (附源码)计算机毕业设计ssm电影分享网站
  • (三) prometheus + grafana + alertmanager 配置Redis监控
  • (三)elasticsearch 源码之启动流程分析
  • (算法二)滑动窗口
  • (转)linux下的时间函数使用
  • .equal()和==的区别 怎样判断字符串为空问题: Illegal invoke-super to void nio.file.AccessDeniedException
  • .NET Core中的去虚
  • .net 怎么循环得到数组里的值_关于js数组
  • .net 逐行读取大文本文件_如何使用 Java 灵活读取 Excel 内容 ?
  • .net中应用SQL缓存(实例使用)
  • [ SNOI 2013 ] Quare
  • [ 蓝桥杯Web真题 ]-Markdown 文档解析
  • [100天算法】-实现 strStr()(day 52)
  • [AIGC 大数据基础]hive浅谈
  • [android] 看博客学习hashCode()和equals()