单向链表的一点儿感悟

栏目: IT技术 · 发布时间: 4年前

内容简介:点击上方蓝字可直接关注!方便下次阅读。如果对你有帮助,麻烦点个在看或点个赞,感谢~最近一段时间学习了挺多的,数据结构看了一点点,略有感悟,和感兴趣的同志分享一下,欢迎大家不吝评论。

点击上方蓝字可直接关注!方便下次阅读。如果对你有帮助,麻烦点个在看或点个赞,感谢~

单向链表的一点儿感悟

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

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

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 条路线,发现一个走不通立马换下一个,肯定会有走通的那一条。

单向链表的一点儿感悟


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Web标准设计

Web标准设计

刘杰(嗷嗷) / 清华大学出版社 / 2009-1 / 75.00元

一扇经常开启的门的铰链不需要润滑油。 一条湍急的河流不会变得污浊。 无论是声音还是想法都不可能在真空中传播。 Web标准如果不用就会腐朽。 这世界真奇妙! 专题页面:http://www.aoao.org.cn/book/web-standards-design/一起来看看 《Web标准设计》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具