数据结构-线性表

Posted on | In |

基本操作

链表技巧

  1. 理解指针或引用的含义
  2. 警惕指针丢失和内存泄漏
  3. 利用哨兵简化实现难度
  4. 重点留意边界条件处理
    1. 如果链表为空时，代码是否能正常工作？
    2. 如果链表只包含一个结点时，代码是否能正常工作？
    3. 如果链表只包含两个结点时，代码是否能正常工作？
    4. 代码逻辑在处理头结点和尾节点的时候，是否能正常工作？
  5. 举例画图、辅助思考
  6. 多写、多练
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
//数据结构
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct ListNode {
    struct ListNode *next;
    int val;
}SingleLinkListNode;


//带头结点，便于插入和删除统一操作

#pragma mark - 链表操作

/**
 创建头结点
 
 @return 链表
 */
SingleLinkListNode *single_link_list_create(void);

/**
 链表是否空
 
 @param head 链表
 @return 链表是否空
 */
bool single_link_list_is_empty(SingleLinkListNode *head);

/**
 链表遍历
 
 @param head 链表
 */
void single_link_list_dump_head(SingleLinkListNode *head);

/**
 链表遍历 不带头结点
 
 @param head 链表
 */
void single_link_list_dump(SingleLinkListNode *head);

/**
 头部插入
 
 @param head 链表
 @param data 插入数据
 */
void single_link_list_insert_head(SingleLinkListNode *head, int data);

/**
 尾部插入
 
 @param head 链表
 @param data 插入数据
 */
void single_link_list_insert_tail(SingleLinkListNode *head, int data);

/**
 删除头部节点
 
 @param head 链表
 @return 删除的节点
 */
SingleLinkListNode *single_link_list_delete_head(SingleLinkListNode *head);

/**
 删除尾部节点
 
 @param head 链表
 @return 删除的节点
 */
SingleLinkListNode *single_link_list_delete_tail(SingleLinkListNode *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
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
//带头结点，便于插入和删除统一操作

#pragma mark - 链表操作

/**
 创建头结点

 @return 链表
 */
SingleLinkListNode *single_link_list_create()
{
    SingleLinkListNode *head = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    if (head == NULL) {
        printf("头结点创建失败\n");
        return NULL;
    }
    head->next = NULL;
    
    return head;
}

/**
 链表是否空

 @param head 链表
 @return 链表是否空
 */
bool single_link_list_is_empty(SingleLinkListNode *head)
{
    return head->next == NULL;
}

/**
 链表遍历

 @param head 链表
 */
void single_link_list_dump_head(SingleLinkListNode *head)
{
    SingleLinkListNode *p = head->next;

    printf("带头结点链表:");
    while (p != NULL) {
        printf("%d", p->val);
        if (p->next != NULL) {
            printf("->");
        }
        else {
            printf("\n");
        }
        p = p->next;
    }
}

/**
 链表遍历 不带头结点
 
 @param head 链表
 */
void single_link_list_dump(SingleLinkListNode *head)
{
    SingleLinkListNode *p = head;
    
    printf("不带头结点链表:");
    while (p != NULL) {
        printf("%d", p->val);
        if (p->next != NULL) {
            printf("->");
        }
        else {
            printf("\n");
        }
        p = p->next;
    }
}

/**
 头部插入

 @param head 链表
 @param data 插入数据
 */
void single_link_list_insert_head(SingleLinkListNode *head, int data)
{
    SingleLinkListNode *p = head;

    SingleLinkListNode *temp = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    temp->val = data;
    temp->next = p->next;
    p->next = temp;
}

/**
 尾部插入

 @param head 链表
 @param data 插入数据
 */
void single_link_list_insert_tail(SingleLinkListNode *head, int data)
{
    SingleLinkListNode *p = head;
    
    while (p->next != NULL) {
        p = p->next;
    }
    
    SingleLinkListNode *temp = (SingleLinkListNode *)malloc(sizeof(SingleLinkListNode));
    temp->val = data;
    temp->next = NULL;
    
    p->next = temp;
}

/**
 删除头部节点

 @param head 链表
 @return 删除的节点
 */
SingleLinkListNode *single_link_list_delete_head(SingleLinkListNode *head)
{
    SingleLinkListNode *p = head;

    
    if (!p->next) {
        return NULL;
    }

    SingleLinkListNode *temp = p->next;
    p->next = temp->next;
    temp->next = NULL;
    return temp;
}

/**
 删除尾部节点

 @param head 链表
 @return 删除的节点
 */
SingleLinkListNode *single_link_list_delete_tail(SingleLinkListNode *head)
{
    SingleLinkListNode *p = head;

    if (!p->next) {
        return NULL;
    }
    
    while (p->next->next != NULL) {
        p = p->next;
    }
    
    
    SingleLinkListNode *temp = p->next;
    p->next = temp->next;
    temp->next = NULL;
    return temp;
}