lyq1996的博客
dataStructure->LinkList
lyq1996
  2019-08-19 16:00:24   2019-08-19 16:00:24      2k 字  10 分钟  

数据结构之线性表

1
2
3
4
5
6
7
8
9
10
11
12
typedef struct dataStruct
{
    elemType *LinkList;
    elemType *Stack;
    elemType *Queue;
    elemType *String;
    elemType *Array;
    elemType *Tree;
    elemType *Graph;
    elemType *Indexing;
    elemType *Sorting;
}* dataStructure;

线性表

线性表分为顺序表和链表,链表分为单链表、双链表、循环链表(单循环链表和双循环链表)。

顺序表

1
2
3
4
5
6
7
typedef struct
{
    Elemtype *elem;    //数组
    int length;        //当前表的长度
    int listsize;      //表的数组容量
    int incrementsize; //表增容量
} SqList;

顺序表的存储单元是连续的，也就是在内存中，表的元素顺序摆放。过于简单了，随便康康定义就行了。

链表

在存储单元之中不连续，通过指针连接起来，像链条一样故称之为链表

单链表

每个Node包含data和pointer，data存放数据,pointer指向下一个节点

结构体定义

1
2
3
4
5
typedef struct Node
{
    Elemtype data;     // data
    struct Node *next; // pointer
} LNode, *LinkList;

初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LinkList createNode(int n)
{
    LinkList L1; //头节点,next指向null
    L1 = (LinkList)malloc(sizeof(LNode));
    L1->next = NULL;
    LinkList end; //尾节点,next也指向null
    end = L1;
    for (int i = 0; i < n; i++)
    {
        LinkList L = (LinkList)malloc(sizeof(LNode));
        end->next = L;
        end = L;
    }
    end->next = NULL;
    return L1;
}

删除节点,要删除的节点的上一个节点的指针指向删除节点的下一个节点。in是删除节点的上一个节点，ptr是待删除节点，in->next = ptr->next

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void deleteNode(LinkList L1, int n) //删除节点
{
    LinkList ptr;
    ptr = L1;
    LinkList in;
    int i = 0;
    while (i < n && ptr != NULL)
    {
        in = ptr;
        ptr = ptr->next;
        i++;
    }
    if (ptr == NULL)
    {
        printf("Node does not exist.\n");
    }
    else
    {
        in->next = ptr->next;
        free(ptr);
    }
}

双链表

每个节点包含两个指针，一个指向next一个指向prior。
头节点：表中第一个节点。
表头指针：存放双链表中第一个节点的地址的指针。
开始节点：存放双链表的第一个元素的节点。（不是头节点，头节点data域是空的）
表尾节点：双链表中最后一个节点。
可以无头节点。

结构体定义

1
2
3
4
5
6
7
typedef struct dNode
{
    elemType data; //int,win32-(2^15) ~ 2^15 - 1 1000000000000000 ~ 0111111111111111
    dNode *next;
    dNode *pre;
    
}douNode, * dpNode;

初始化

1
2
3
4
5
6
7
8
9
10
11
12
dpNode nodeInit()
{
    dpNode L;
    L = (dpNode)malloc(sizeof(dpNode));
    if (!L)
    {
        exit(1);
    }
    L->pre = NULL;
    L->next = NULL;
    return L;
}

尾插赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void createNode(dpNode L, int n) //尾插
{
    int i = 0;
    elemType d;
    dpNode end;
    end = L;
    while (i < n && end != NULL)
    {
        dpNode p = (dpNode)malloc(sizeof(dpNode));
        printf("data:");
        scanf("%d", &d);
        p->data = d;
        p->next = NULL;
        p->pre = end;
        end->next = p;
        end = p;
        i++;
    }
}

前插节点
将节点插入已有节点之前，不允许插入头节点之前及末尾节点之后(即从1开始)。

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
void insertNode(dpNode L, int n)
{
    if (n < 1)
    {
        printf("invaild!\nn should not less than 1\n");
        return;
    }
    dpNode ptr = L;
    int i = 0;
    while (i < n && ptr)
    {
        ptr = ptr->next;
        i++;
    }
    if (ptr) //  n should not behind the end node
    {
        dpNode newNode;
        newNode = (dpNode)malloc(sizeof(dpNode));
        newNode->next = ptr;
        newNode->data = 9999;
        dpNode in = ptr->pre;
        in->next = newNode;
        newNode->pre = in;
        ptr->pre = newNode;
    }
}

删除节点，删除节点比插入节点略微简单,8允许删除头节点。 

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
void deleteNode(dpNode L, int n)
{
    if (n < 1)
    {
        printf("invaild!\nshould not delete head node\n");
    }
    int i = 0;
    dpNode ptr = L;
    while (i < n && ptr)
    {
        ptr = ptr->next;
        i++;
    }
    if (!ptr)
    {
        return;
    }
    if (ptr->next) //not the end node
    {
        dpNode in = ptr->pre;
        dpNode ou = ptr->next;
        in->next = ou;
        ou->pre = in;
        free(ptr);
    }
    else //end node
    {
        dpNode in = ptr->pre;
        in->next = NULL;
        free(ptr);
    }
}

销毁双链表，最简单的，遍历然后free即可。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void destoryNode(dpNode L)
{
    dpNode ptr = L;
    dpNode in;
    int i = 0;
    while(ptr != NULL)
    {
        printf("current pointer: %d\n",i);
        i++;
        in = ptr;
        ptr = ptr -> next;
        free(in);
    }
}

双向循环链表

循环列表分为单向和双向，以双向为例。
循环指的是，头节点的前指针指向end node，end node前一节点指向head node。

初始化

1
2
3
4
5
6
7
8
9
10
11
12
/*Head node init*/
cListPtr listInit()
{
    cListPtr head;
    head = (cListPtr)malloc(sizeof(cListPtr));
    if (!head)
    {
        exit(1);
    }
    head -> next = head;
    head -> pre = head;
}

建立node
只要记得处理好end node和head node的指针域即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void createNode(cListPtr head, int n)
{
    cListPtr ptr = head;
    int i = 0;
    while (i < n)
    {
        cListPtr node = (cListPtr)malloc(sizeof(cListPtr));
        cout << "input data:" << endl;
        cin >> node->data;
        ptr->next = node;
        node->pre = ptr;
        ptr = node;
        i++;
    }
    ptr->next = head;
    head->pre = ptr;
}

插入节点
与上面单向链表不同，这次在指定node的后面插入新的node，超过最大node数就在最后加上新节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/*insert new node behind of the n node*/
void insertNode(cListPtr head, int n)
{
    cListPtr ptr = head;
    if (n < 0)
    {
        cout << "invaild" << endl;
        return;
    }
    int i = 0;
    while (i < n && ptr->next != head)  //if delete ptr->next != head, it will loop insertion.
    {
        ptr = ptr->next;
        i++;
    }
    cListPtr newNode = (cListPtr)malloc(sizeof(cListPtr));
    newNode->data = 99999;
    newNode->pre = ptr;
    newNode->next = ptr->next;
    ptr->next->pre = newNode;
    ptr->next = newNode;
}

删除节点
so easy，做一个限制不允许删除头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void deleteNode(cListPtr head, int n)
{
    cListPtr ptr = head;
    if (n < 1)
    {
        cout << "invaild" << endl;
        return;
    }
    int i = 0;
    while (i < n && ptr->next != head)
    {
        ptr = ptr->next;
        i++;
    }
    ptr->pre->next = ptr->next;
    ptr->next->pre = ptr->pre;
    free(ptr);
}

销毁列表
头节点最后销毁。 

1
2
3
4
5
6
7
8
9
10
11
12
13
void destoryList(cListPtr head)
{
    cListPtr ptr = head;
    cListPtr in;
    ptr = ptr->next;
    while (ptr!= head)
    {
        in = ptr;
        ptr = ptr->next;
        free(in);
    }
    free(head);
}

输出链表长度
遍历即可

1
2
3
4
5
6
7
8
9
10
11
int lenList(cListPtr head)
{
    int i = 1;
    cListPtr ptr = head;
    while(ptr->next != head)
    {
        ptr = ptr->next;
        i++;
    }
    return i;
}

FULL debug code

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
#define elemType int

typedef struct CLinkedList
{
    elemType data;
    CLinkedList *next;
    CLinkedList *pre;
} cList, *cListPtr;

/*Head node init*/
cListPtr listInit()
{
    cListPtr head;
    head = (cListPtr)malloc(sizeof(cListPtr));
    if (!head)
    {
        exit(1);
    }
    head->next = head;
    head->pre = head;
    return head;
}

void createNode(cListPtr head, int n)
{
    cListPtr ptr = head;
    int i = 0;
    while (i < n)
    {
        cListPtr node = (cListPtr)malloc(sizeof(cListPtr));
        cout << "input data:" << endl;
        cin >> node->data;
        ptr->next = node;
        node->pre = ptr;
        ptr = node;
        i++;
    }
    ptr->next = head;
    head->pre = ptr;
}

/*insert new node behind of the n node*/
void insertNode(cListPtr head, int n)
{
    cListPtr ptr = head;
    if (n < 0)
    {
        cout << "invaild" << endl;
        return;
    }
    int i = 0;
    while (i < n && ptr->next != head) //if delete ptr->next != head, it will loop insertion.
    {
        ptr = ptr->next;
        i++;
    }
    cListPtr newNode = (cListPtr)malloc(sizeof(cListPtr));
    newNode->data = 99999;
    newNode->pre = ptr;
    newNode->next = ptr->next;
    ptr->next->pre = newNode;
    ptr->next = newNode;
}

void deleteNode(cListPtr head, int n)
{
    cListPtr ptr = head;
    if (n < 1)
    {
        cout << "invaild" << endl;
        return;
    }
    int i = 0;
    while (i < n && ptr->next != head) //if greater than max, delete the end node.
    {
        ptr = ptr->next;
        i++;
    }
    ptr->pre->next = ptr->next;
    ptr->next->pre = ptr->pre;
    free(ptr);
}

void destoryList(cListPtr head)
{
    cListPtr ptr = head;
    cListPtr in;
    ptr = ptr->next;
    while (ptr != head)
    {
        in = ptr;
        ptr = ptr->next;
        free(in);
    }
    free(head);
}

int lenList(cListPtr head)
{
    int i = 1;
    cListPtr ptr = head;
    while(ptr->next != head)
    {
        ptr = ptr->next;
        i++;
    }
    return i;
}

int main()
{
    cListPtr h = listInit();
    int num;
    int index;
    cout << "How many node do u want?" << endl;
    cin >> num;
    createNode(h, num);

    num = lenList(h);
    cout << "current length of list:" << num << endl;
    cListPtr ptr = h;
    for (int i = 1; i < num; i++)
    {
        ptr = ptr->next;
        cout << ptr->data << endl;
    }

    cout << "insert behind which node?" << endl;
    cin >> index;
    insertNode(h, index);

    num = lenList(h);
    cout << "current length of list:" << num << endl;
    ptr = h;
    for (int i = 1; i < num; i++)
    {
        ptr = ptr->next;
        cout << ptr->data << endl;
    }

    cout << "delete which node?" << endl;
    cin >> index;
    deleteNode(h, index);

    num = lenList(h);
    cout << "current length of list:" << num << endl;    
    ptr = h;
    for (int i = 1; i < num; i++)
    {
        ptr = ptr->next;
        cout << ptr->data << endl;
    }
    destoryList(h);
}

总结

表在一定程度上，充当的是一个变长数组的作用，不像数组在定义之后不可扩充，还是很简单和很方便的。

dataStructure->LinkList
2019/08/19/linklist/
作者
lyq1996
发布于
2019-08-19 16:00
许可
 评论
评论插件加载失败
正在加载评论插件
  1. 1. 数据结构之线性表
    1. 1.1. 线性表
      1. 1.1.1. 顺序表
      2. 1.1.2. 链表
        1. 1.1.2.1. 单链表
      3. 1.1.3. 双链表
      4. 1.1.4. 双向循环链表
    2. 1.2. 总结
© 2016 - 2024    lyq1996
由 Hexo 驱动 & 主题 Keep
本站由 提供部署服务
访客数 访问量
  1. 1. 数据结构之线性表
    1. 1.1. 线性表
      1. 1.1.1. 顺序表
      2. 1.1.2. 链表
        1. 1.1.2.1. 单链表
      3. 1.1.3. 双链表
      4. 1.1.4. 双向循环链表
    2. 1.2. 总结