数据结构-链表(2)

约瑟夫问题

n 个人围成一个圆圈,首先第1个人从1开始一个人一个人顺时针报数, 报到第m个人,令其出列。然后再从下一个人开始,从1顺时针报数,报到第m个人,再令其出列,…,如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。
例如 n = 8 m = 3

对于这个问题我们用完全可以用循环队列来解决,但是这里我们为了加深一下对链表的操作,我们来用单循环链表来解决。很好类比,单循环链表也是一个圈,我们完全可以用它来模拟这个队伍。

定义结点、

//
typedef struct Node
{
    int data;
    struct Node* pNext;
} Node,*PNODE;
//

为了还原,这里我就没有添加头结点,同时也避免了循环时对头结点的判断,避免了产生与普通数据结点不同的操作,保证所有结点都一样,操作没有差别。

继续阅读

数据结构-链表(1)

定义

链表是线性表的链接存储方式,相比于数组的连续存储

既然说到了线性表就来简单介绍一下,以便和后面的树,图等非线性结构区分开来

同一线性表中元素具有相同特性。
相邻数据元素之间存在序偶关系。
除第一个元素外,其他每一个元素有一个且仅有一个直接前驱元素。
除最后一个元素外,其他每一个元素有一个且仅有一个直接后继元素。

优缺点

优点

对于插入和删除元素,数组的时间复杂度为O(n),而链表为O(1)
链表长度可变,而数组长度不可变

缺点

按序号查找时,数组可以随机访问,时间复杂度为O(1),而链表不支持随机访问,时间复杂度为O(n)
存储密度(结点数据本身所占的存储量/结点结构所占的存储总量)<1
需要动态申请管理内存,处理不当会造成内存泄漏

分类

单链表
静态链表
循环链表
双向链表

专业术语

头节点:第一个有效节点之前的节点数据域不存放数据加头节点的目的主要是方便对链表的操作
首节点:第一个存放数据的节点
尾节点:最后一个存放数据的节点
头指针:指向头节点的指针
尾指针:指向尾节点的指针

继续阅读