内容简介:点击上方蓝字可直接关注!方便下次阅读。如果对你有帮助,麻烦点个在看或点个赞,感谢~最近一段时间学习了挺多的,数据结构看了一点点,略有感悟,和感兴趣的同志分享一下,欢迎大家不吝评论。
点击上方蓝字可直接关注!方便下次阅读。如果对你有帮助,麻烦点个在看或点个赞,感谢~
最近一段时间学习了挺多的,数据结构看了一点点,略有感悟,和感兴趣的同志分享一下,欢迎大家不吝评论。
除了关于链表的一点感悟,还有最近了解到的工程中遇到的几个实际问题:
① 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 条路线,发现一个走不通立马换下一个,肯定会有走通的那一条。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- golang 单向channel
- angularjs单向数据绑定,可以做角度吗?
- BAT 经典算法笔试题 —— 逆转单向链表
- 利用单向环形链表解决约瑟夫问题
- 用 Swift 中的单向数据流来替代臃肿的视图控制器
- Proxy-Go v6.9 发布,单向TLS , 独立上级密码支持!
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Writing Apache Modules with Perl and C
Lincoln Stein、Doug MacEachern / O'Reilly Media, Inc. / 1999-03 / USD 39.95
Apache is the most popular Web server on the Internet because it is free, reliable, and extensible. The availability of the source code and the modular design of Apache makes it possible to extend Web......一起来看看 《Writing Apache Modules with Perl and C》 这本书的介绍吧!