专栏首页Pou光明单向链表的一点儿感悟

单向链表的一点儿感悟

最近一段时间学习了挺多的,数据结构看了一点点,略有感悟,和感兴趣的同志分享一下,欢迎大家不吝评论。

除了关于链表的一点感悟,还有最近了解到的工程中遇到的几个实际问题:

①libevent由于阻塞,将所在进程挂起

②使用线程池时由于线程属性没有设置为分离属性,造成内存泄漏

③Linux的共享内存与C++ STL中共享内存的比较

仅供大家参考。

一、链表的分类

学习前先分类,从大的方面来分,链表属于线性表;线性表从存储方式来分可分为顺序存储结构与链式存储结构——即链表。链表根据特点又可以再具体分为单向链表、循环链表和双向链表等。

二、链表的操作

那按照不同的分法简直太多了,20来个。。。这次简单介绍几个,其中重点介绍如何逆转一个链表。

贴程序前先熟悉数据类型:

typedef int ElemType;

typedef struct node{
 ElemType data;
 struct node *link;
}LNode, *LinkList;

1. 创建一个链表

LinkList Create(int n)
{
 int LinearTable[7] = {0,1,2,3,5,8,10};
 LinkList p, r, head = NULL;
 ElemType tmp;
 int i;

 for(i=0; i<n; i++)
 {
  tmp = LinearTable[i];
  p = (LinkList)malloc(sizeof(LNode));
  p->data = tmp;
  p->link = NULL;

  if(NULL == head)
   head = p;
  else
   r->link = p;

  r = p;
//  printf("--%p \n",p);
 }

 return head;
}

把数组中的元素分别放到链表中节点的数据域,注意将表头存储返回。

2. 遍历一个链表

void Traverse(LinkList list)
{
 LinkList p = list;

 while (NULL != p)
 {
  printf(">> %d \n",p->data);
  printf("pointer %p \n",p);
  p = p->link;
//  printf(">> %p",p->link);  //Segmentation fault (core dumped)
 }
}

这个大家应该比较熟悉了。

3. 计算链表的长度

int Length(LinkList list)
{
 LinkList p = list;
 int length = 0;

 while (NULL != p)
 {
  length++;
  p = p->link;
 }

 return length;
}

这个也还好。

4. 查找元素所在地址

LinkList Find(LinkList list, const ElemType item)
{
 LinkList p = list;

 while (NULL != p && item != p->data)
  p = p->link;

 return p;
}

5. 在非空链表第一个节点前插入一个节点

/*************************************************
  名称:
  描述:    insert a item before the first node
         in a not empty linklist
  输入参数:
  输出参数:
  返回值:
*************************************************/
void InsertLinkOne(LinkList *list, const ElemType item)
{
 LinkList p = (LinkList)malloc(sizeof(LNode));

 p->data = item;
 p->link = *list;

 *list = p;
// list = &p;
}

注意如何修改头节点。

6. 在非空链表表尾插入一个节点

/*************************************************
  名称:
  描述:    insert a item after the tail node
         in a not empty linklist
  输入参数:
  输出参数:
  返回值:
*************************************************/
void InsertLinkTwo(LinkList list, const ElemType item)
{
 LinkList p, r;
 r = list;

 while (NULL != r->link)
  r = r->link;

 p = (LinkList)malloc(sizeof(LNode));
 p->data = item;
 p->link = NULL;

 r->link = p;
// list = &p;
}

这个使用到了遍历,因为链表不能随机访问节点,想下哪些操作还需要使用到遍历?

7. 逆转一个链表

void Invert(LinkList *list)
{
 LinkList oriList, newList, tmpList;
 oriList = *list;
 newList = NULL;

 while (NULL != oriList)
 {
  tmpList = newList;
  newList = oriList;
  oriList = oriList->link;
  newList->link = tmpList;
 }

 *list = newList;
}

设计的挺巧妙的,光看就看了好一会儿。

可以类比如何交换两个数的程序,需要使用一个中间变量来进行临时存储:

a, b, c,

c = a;

a = b;

b = c;

第一次执行:

通过tmpList节点来临时存储新链表的节点,

新的节点指向原来链表的头结点,

原来链表移动到下一个节点,

新链表节点的link链向新链表——

第二次执行:

此时tmpList节点存储的是新的链表的指针,此时有一个节点,

获取原来链表的第二个节点,

原来链表移动到下一个节点(功能不变),

新节点的link指向新的链表,此时新链表有两个节点了,且链表尾端是原来的链表的头结点。

多琢磨琢磨,还是挺有意思的。

链表什么样的操作需要用到遍历?

三、总结

拼尽全力去学习,学习,再学习。

上面那句是废话。

学习是要讲究方法的,

由于最近大量的学习一些东西,会迫使自己不断去梳理,去寻找知识点之间的关系,这个过程迫使你去“找规律”、“寻求联系”;相反写程序反而是最简单的,只不过把流程用编程语言表示出来。

我觉得一个知识学会的标志是:很久都不会忘,即使忘了也会记住一些“自己总结出来的易用的技巧”,那个知识点最后是变成了技巧。数学尤其如此,见到一个东西,脑海里立马想出4条路线,发现一个走不通立马换下一个,肯定会有走通的那一条。

本文分享自微信公众号 - Pou光明(pou0230),作者:PouG

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 链表的魅力:两个单向链表的第一个交点

    最近听了左神的算法课,对一些常用数据结构以及算法改进的思路有了更深的理解,特此总结,不定期更新算法题目以及答案总结!笔者使用C++进行算法重现!虽然左神使用的是...

    算法工程师之路
  • 我和AI打了六局王者荣耀,心态崩了

    PVP对战手游王者荣耀在五一节期间上线了一种新玩法——挑战 · 绝悟,也就是5人组队和5个AI对战。

    量子位
  • 一个简单的双向链表(C++实现)

    直接上代码,亲测有用。 #ifndef __DLINK_H__ #define __DLINK_H__ /* [phead] -> [index0] -...

    xcywt
  • 母亲节礼物准备好了吗?这里有份最简单,却最真挚的建议!

    中国人的骨子里有一种含蓄。 我们常以为爱就是一种感觉,把它放在心里,润物细无声间就能浸润对方的心田。 其实爱更是一种行动,只有表达出来,对方才能明了。 今日,借...

    鹅老师
  • 算法:求两个单向链表的最早公共交点

    链接:https://mp.weixin.qq.com/s/A4jjclVpd7Q03yJfARR3DA

    程序员架构进阶
  • 算法:求两个单向链表的最早公共交点

    链表是单向链表,即只有指向下一个节点的指针,而没有反向;公共节点,指地址相同的节点。即假设链表L1中有一个节点node1,L2中有一个节点node2,n...

    程序员架构进阶
  • 腾讯AI击败王者荣耀职业队,全靠自学、策略清奇,一天训练量为人类440年

    一场激烈的对战正在进行,左侧是五位人类职业电竞高手组成的赛区联队,另一方是……嗯?他们的对手没有出场?五个座椅空空荡荡?

    用户1737318
  • 腾讯AI击败王者荣耀职业队,全靠自学、策略清奇,一天训练量为人类440年

    一场激烈的对战正在进行,左侧是五位人类职业电竞高手组成的赛区联队,另一方是……嗯?他们的对手没有出场?五个座椅空空荡荡?

    量子位
  • 七 .Html的表格

    小海怪的互联网
  • 年薪百万的程序员,都是这么开悟的续集

    《编程之道》出自美国一位资深的程序设计师 Geoffrey James 之手。 相传作者早起打太极拳的时候,突然开悟,悟到了编程之道。 上一篇收到热心粉丝启发...

    程序员互动联盟
  • 面向对象之继承

    继上篇博客 https://www.cnblogs.com/qianqian-it/p/9526634.html 简单介绍了有关call和apply的联系和区别...

    用户3159471
  • 李嘉诚和邓小平最爱讲的十个故事

    1、获得胜利的方法故事:有人用玻璃把一条蛇和一只青蛙在水池里隔开。开始时,蛇要吃青蛙,它一次次冲向青蛙,却一次次撞到了玻璃隔板上,它吃不着。过了一会,蛇放弃了努...

    小小科
  • 大师带你开悟高薪程序员之路——《编程之道》番外篇

    程序员见禅师:我学了 hello world 和水仙花数,想自己开发个操作系统,希望大师指点。

    java架构师
  • Undertow 如何自定义SessionId

    说到Session,楼主刚毕业那会儿,第一次踏上北漂的路,面试题其中有一道就是浏览器禁用Cookie,Session还能用吗?为什么?网上很多关于如何自定义Se...

    只喝牛奶的杀手
  • 几万年前,孙悟空大闹地府后删库跑路了!那阎王生死簿又该怎么写呢?

    话说几万年前,有一只猴子在大闹地府删库跑路,导致地府几百年没缓过劲儿来......

    iMike
  • “疯子”优必选,做了一件“暴露”野心的事

    以上土味情话发生在机器人独角兽公司优必选昨日年度发布会现场,进行对话的主体是优必选产品总经理周恒宇与“悟空”机器人,后者是此次发布会的主角之一。

    镁客网
  • 用只含一个链域的节点实现循环链表的双向遍历

    通常来说,要实现循环双向链表,每个节点需要有两个链域:前驱和后继。现在的问题是:如何设计一种环形表,使表的每个结点只包含一个链域而又能够有效地对其进行两个方向的...

    llhthinker
  • 专访唐杰:万亿参数大模型只是一个开始

    图灵写于 1950 年的论述《计算机器与智能》被誉为人工智能的开山之作,他在文中不仅提出了「机器会思考吗?」这一经典问题,还给出了著名的「图灵测试」用以判断一台...

    机器之心
  • 【转】我的技术学习方法 — Anytao

      关于这个问题,也有不少刚刚入行的朋友向我问起。我想可能一千个人就有一千个答案,我不能保证自己的想法适合于所有的人,但是这确实是我自己的体会和经历,希望能给你...

    Edison Zhou

扫码关注云+社区

领取腾讯云代金券