线性表

字数统计: 2.4k字   |   阅读时长≈ 10分

数据结构

线性表

线性：说的是数据在逻辑上的排列结构。除了线性还有树形、点状、集合等逻辑结构。

储存结构区分：

1.顺序存储结构的线性表叫顺序表，线性表中的元素储存是一个挨着一个按顺序储存的。

2.链式存储结构的线性表叫链表，线性表中的元素可以储存在任意位置，通过地址来建立元素与元素之间的逻辑关系。

顺序、链式：说的是数据在物理空间（如RAM、FALSH等）的储存结构，数组就是典型的顺序存储结构，一个数据元素在物理空间上挨着另一个数据元素。链式存储就像一条链子一样，一个关联一个，一个数据元素扣一个数据元素的存储。

我们通常说的单链表、双链表、顺序表都是说的数据的物理储存结构，但是他们都是属于线性表。

线性表表示方法：

  • 单链表结构：

1.将线性表L = （a0,a1,…..an-1）中的元素分布在储存器的不同存储块，称为节点。

2.节点与节点之间建立关系，一般通过一个节点保存另一个节点的首地址的方式建立节点之间的关系。

  • 节点包括数据域和指针域

a(i+1)节点叫做a(i)节点的后继节点。

数据与用来保存该节点携带的数据，指针域用来保存与该节点逻辑上相邻的节点的地址。例如 a(i) 节点指针域保存 a(i+1)节点的地址

  • 头结点

1.头结点是链表逻辑上第一个节点，它的数据域通常不用来保存数据，而是用来保存该链表当前的一些信息，比如：链表中当前节点的个数、链表头地址、链表尾地址等链表相关的信息。

2.我们通过头结点就可以很方便的找到整个链表。

3.头结点是恒存在的，不能被删除，空链表中只存在一个头结点，没有其它保存数据用的节点。

4.头结点的类型可以和其他节点的类型可以不一样，设计如下节点类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 链表
struct list
{
    struct list *next;
};
typedef struct list *list_t;

// 用于保存数据的节点类型
struct _node
{
    list_t list;
    struct node_data; // 节点的数据域 struct node_data 自由设计一个数据类型
};
typedef struct _node *_node_t
    
// 头结点类型
struct head_node
{
    list_t list;
    struct _node *head;
    struct _node *tail;
    int node_count;
};
typedef struct head_node *head_node_t;

单链表倒置：

方法一：

1.将 l->next = NULL; p1 = l->next; p2 = l->next->next;

2.tmp = p2->next; (p2下次往前移到到这个tmp保存下)

3.p2 -> next = p1; (p2反方向指，指向p1)

4.p1 = p2; p2 = tmp; (p1、p2分别往前移到一个位置)

5.循环 234步骤，直到 p2 == NULL；跳出。

6.l->next = p1;(头结点指向新的第一个节点)

方法二：

1.p1 = l->next;(p1保存下老链表的第一个节点)，l->next = NULL；置空链表得到一个空链表和一个以p1为头的孤立链表。

2.p2 = p1;(保存下p1的位置之后将这个节点插入到空链表) ，p1 = p1->next；(p1往后移到)

3.p2->next = l->next; l->next = p2;(p2节点插入到空链表)

4.重复23步骤直到p1==NULL移到到老孤立链表的最后。

单链表排序：

1.将要排序的链表拆成两个链表，不带head节点的链表：p = l->next->next，带head节点的链表（链表只有一个节点）：r = l;

2.从不带头结点的链表取节点，tmp = p;

3.把上面取到的节点插入带head的链表的正确位置：首先要遍历带head节点的链表，找到合适位置插入tmp；

4.p指针往下走，从不带头结点的链表取第二个节点，执行3步骤插入操作。

5.循环234步骤，直到p == NULL，到达不带head节点链表尾部。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
// 链表排序的条件可以提供一个方法用来比较的，里面的内容可以自己实现，增加排序灵活性
int pkt_list_by_data_order_with_fun(pkt_node_t l, int (*cmp)(pkt_node_t l1, pkt_node_t l2))
{
    PKT_ASSERT(l);
    if (!l->next || !l->next->next)
    {
        printf("this list node <= 1, no need order\n");
        return -1;
    }
    pkt_node_t p = l->next->next; /* the other list do not have head node */
    pkt_node_t r = l;
    l->next->next = NULL;  /* new list have one node */
    pkt_node_t tmp;

    while (p->next) /* 不带head节点的链表，从头一个一个的取node插入到带head节点的链表 */
    {
        tmp = p;  /* get a node */
        p = p->next; /* move to next node */
        
        /* 寻找满足cmp条件的l链表的正确位置，如果到了最后也没有就把q插到最后位置 */
        r = l;
        while (r->next && !cmp(r->next, tmp))  /* r->next是新拆分带头head节点的那个，q是不带head节点的那个 */
        {
            r = r->next;
        }
        tmp->next = r->next;
        r->next = tmp;
    }

    return 0;
}

// 这个函数可以控制按什么规则来排序
int rule(pkt_node_t l1, pkt_node_t l2)
{
    if (l2->data > l1->data)
    {
        return 0;
    }
    return 1;
}

/* 调用排序函数 */
pkt_list_by_data_order_with_fun(l, rule);

单项循环链表：

循环链表的优点：可以通过遍历找到节点的前驱节点，单项非循环链表只能找自己的后继节点。

两个单向循环链表合并步骤：

1.P = B->next; 保存被合并链表的head节点

2.B->next = A->next; B链表尾指向A链表头

3.A->next = P->next; A链表尾指向B链表第一个节点（除去head节点）

4.free（P）；释放B链表的head节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 循环链表创建
list_node_t pkt_creat_loop_list(void)
{
    list_node_t n;

    n = (list_node_t)malloc(sizeof(struct list_node));
    n->next = n;
    return n;
}

// 合并循环单向链表
int pkt_merge_loop_list(list_node_t des, list_node_t src)
{
    PKT_ASSERT(des);
    PKT_ASSERT(src);
    if (!des->next || !src->next)
    {
        printf("is a empty list!\n");
        return -1;
    }
    list_node_t p = des;
    list_node_t q = src;

    while (p->next != des) // 移到p指针变量到des链表尾
    {
        p = p->next;
    }

    while (q->next != src) // 移到q指针变量到src链表尾
    {
        q = q->next;
    }

    q->next = p->next; // 将src链表尾指向des链表的头部
    p->next = src->next; // 将des链表的尾巴指向src链表的头部（除去head节点）
    free(src); // 释放src的head节点
    return 0;
}

循环链表：

双向循环链表插入操作：

关于双向链表的插入步骤原则：1.先处理新要插入的节点的prev、next指向，再处理p1前一个节点的next指向，再处理p1节点prev的指向。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 创建双向循环链表
dlist_node_t pkt_creat_loop_dlist(void) 
{
    dlist_node_t n;
    n = (dlist_node_t)malloc(sizeof(struct dlist_node));
    n->next = n->prev = n;
    return n;
}

// 向双向循环链表插入一个节点数据
int pkt_insert_loop_dlist(dlist_node_t l, data_type data)
{
    PKT_ASSERT(l);

    dlist_node_t n = (dlist_node_t)malloc(sizeof(struct dlist_node)); // @2
    if (!n)
    {
        printf("malloc failed!\n");
        return -1;
    }
    n->data = data;
    dlist_node_t p = l->next; // @1

    n->next = p; // @3
    n->prev = p->prev; // @4
    p->prev->next = n; // @5
    p->prev = n; // @6
    return 0;
}

// 按数据删除一个双向循环链表的节点
int pkt_remove_loop_dlist(dlist_node_t l, data_type data)
{
    PKT_ASSERT(l);
    dlist_node_t p = l->next;

    while (p->next != l && p->data != data)
    {
        p = p->next;
    }

    if (p->next == l)
    {
        printf("did not find the node\n");
        return -1;
    }

    p->prev->next = p->next; // 删除的时候先处理p前一个节点的next
    p->next->prev = p->prev; // 在处理p后一个节点的prev

    free(p); // p释放虽然它的指next和pre都和原来一样， 但已经没有一个节点指向它了（脱离了链表）
    return 0;
}

1.双向循环链表相比非循环单链表很容易实现头插和尾插：dlist_node_t p = l->next; 头插，在第一个节点前插入，dlist_node_t p = l；尾插，在head节点前插入。

2.如果是非循环单链表和循环单链表都需要先遍历链表，时工作指针移动带链表尾，才可以实现尾部插入节点。

3.循环链表之所以可以很方便实现尾插模式，是因为每个节点都有一个point指向前驱节点。而head节点的前驱节点就是链表的尾节点。

代码仓库：http://gitea.880755.xyz/private/list.git

补充知识：
ringbuffer和message_queue
ringbuffer：一般使用数组通过顺序表实现，用于字节流的储存，储存单元是byte，读取通过read指针和write指针，以及提供要读写的大小，记录位置。
message_queue：通过链表实现，配合动态内存分配，创建时固定每条消息容量，队列多大储存消息数量。最小的储存单元是消息，读队列就是从队列头取一条消息，写队列就是从队列尾写一条消息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// ringbuffer 类型声明
typedef struct __CBUF_STRUCT
{
    cbuf_size_t __head;  // read ponit
    cbuf_size_t __tail;  // wirte ponit
    cbuf_unit_t *  __buf_room;   // mem pool start addr
    cbuf_size_t __buf_size; // mem pool size
}CBUF_STRUCT;

// message_queue 类型声明
struct rt_messagequeue
{
    struct rt_ipc_object parent;                        /**< inherit from ipc_object */

    void                *msg_pool;                      /**< start address of message queue */

    rt_uint16_t          msg_size;                      /**< message size of each message */
    rt_uint16_t          max_msgs;                      /**< max number of messages */

    rt_uint16_t          entry;                         /**< index of messages in the queue */

    void                *msg_queue_head;                /**< list head */
    void                *msg_queue_tail;                /**< list tail */
    void                *msg_queue_free;                /**< pointer indicated the free node of queue */

    rt_list_t            suspend_sender_thread;         /**< sender thread suspended on this message queue */
};
typedef struct rt_messagequeue *rt_mq_t;
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

从事嵌入式开发