(09)王道数据结构-单链表的查找

按位查找

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
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
LNode* GetElem(LinkList L, int i);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！\n");
    }

    int e = 0;
    ListDelete(L, 8, e);

    //判断是否删除成功
    LNode* node = NULL;
    node = GetElem(L, 8);
    if (node == NULL) {
        printf("删除成功！\n");
    }
    node = GetElem(L, 6);
    printf("获取元素:%d\n", node->data);
    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //分配头结点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->next = NULL;     //头结点之后暂时没有节点
    return true;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
        printf("插入失败!\n");
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p != NULL && j < i-1) {      //循环找到第i-1个节点
        p = p->next;
        j++;
    }
    if (p == NULL) {    //i值不合法
        return false;
        printf("插入失败!\n");
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;        //将节点s连接到p之后
    return true;        //插入成功
}

//按位序删除：带头结点
bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    LNode *p;       //指针p指向当前扫描到的节点
    int j = 0;      //当前p指向的是第几个节点
    p = L;          //L指向头结点，头结点是第0个节点（不存数据）
    while(p != NULL && j < i-1) {   //循环找到第i-1个节点
        p = p->next;
        j++;
    }

    if (p==NULL) {  //i值不合法
        return false;
    }
    if (p->next == NULL) {  //第i-1个节点之后已无其他节点
        return false;
    }
    LNode *q = p->next;     //令p指向被删除节点
    e = q->data;            //用e返回元素的值
    p->next = q->next;      //将*q节点从链中“断开”
    free(q);
    return true;
}

//按位查找，返回第i个元素（带头结点）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p!=NULL && j<i) {    //循环找到第i个节点
        p = p->next;
        j++;
    }
    return p;
}

封装之后

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
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
bool InsertNextNode(LNode *p, int e);
LNode* GetElem(LinkList L, int i);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！\n");
    }

    int e = 0;
    ListDelete(L, 8, e);

    //判断是否删除成功
    LNode* node = NULL;
    node = GetElem(L, 8);
    if (node == NULL) {
        printf("删除成功！\n");
    }
    node = GetElem(L, 6);
    printf("获取元素:%d\n", node->data);
    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //分配头结点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->next = NULL;     //头结点之后暂时没有节点
    return true;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    return InsertNextNode(p, e);    //p后插入新元素e
}

//按位序删除：带头结点
bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    if (p==NULL) {  //i值不合法
        return false;
    }
    if (p->next == NULL) {  //第i-1个节点之后已无其他节点
        return false;
    }
    LNode *q = p->next;     //令p指向被删除节点
    e = q->data;            //用e返回元素的值
    p->next = q->next;      //将*q节点从链中“断开”
    free(q);
    return true;
}

//按位查找，返回第i个元素（带头结点）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p!=NULL && j<i) {    //循环找到第i个节点
        p = p->next;
        j++;
    }
    return p;
}

//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {    //内存分配失败
        return false;
    }
    s->data = e;    //用节点s保存数据元素e
    s->next = p->next;
    p->next = s;
    return true;
}

按值查找

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
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
bool InsertNextNode(LNode *p, int e);
LNode* LocalElem(LinkList L, int e);
LNode* GetElem(LinkList L, int i);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    if (!Empty(L)) {
        printf("插入成功！\n");
    }

    int e = 0;
    ListDelete(L, 8, e);

    //判断是否删除成功
    LNode* node = NULL;
    node = LocalElem(L, 88);
    if (node == NULL) {
        printf("删除成功！\n");
    }
    node = LocalElem(L, 66);
    printf("获取元素位序:%d\n", node->data);
    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //分配头结点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->next = NULL;     //头结点之后暂时没有节点
    return true;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    return InsertNextNode(p, e);    //p后插入新元素e
}

//按位序删除：带头结点
bool ListDelete(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    if (p==NULL) {  //i值不合法
        return false;
    }
    if (p->next == NULL) {  //第i-1个节点之后已无其他节点
        return false;
    }
    LNode *q = p->next;     //令p指向被删除节点
    e = q->data;            //用e返回元素的值
    p->next = q->next;      //将*q节点从链中“断开”
    free(q);
    return true;
}

//按值查找，找到数据域==e的节点
LNode* LocalElem(LinkList L, int e) {
    LNode *p = L->next;
    //从第一个节点开始查找数据域为e的节点
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

//按位查找，返回第i个元素（带头结点）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p!=NULL && j<i) {    //循环找到第i个节点
        p = p->next;
        j++;
    }
    return p;
}

//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {    //内存分配失败
        return false;
    }
    s->data = e;    //用节点s保存数据元素e
    s->next = p->next;
    p->next = s;
    return true;
}

求表长度

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
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode {      //定义单链表结构
    int data;               //每个节点存放一个数据
    struct LNode *next;     //指针指向下一个节点
}LNode, *LinkList;
bool InitList(LinkList &L);
bool Empty(LinkList L);
bool ListInsert(LinkList &L, int i, int e);
bool InsertNextNode(LNode *p, int e);
LNode* GetElem(LinkList L, int i);
int length(LinkList L);
int main(void) {
    LinkList L;
    InitList(L);
    if (Empty(L)) {
        printf("链表为空!\n");
    }

    ListInsert(L, 1, 11);
    ListInsert(L, 2, 22);
    ListInsert(L, 3, 33);
    ListInsert(L, 4, 44);
    ListInsert(L, 5, 55);
    ListInsert(L, 6, 66);
    ListInsert(L, 7, 77); 
    ListInsert(L, 8, 88);

    printf("链表长度为:%d\n",length(L));
    return 0;
}

//初始化空的单链表
bool InitList(LinkList &L) {
    L = (LNode *)malloc(sizeof(LNode));   //分配头结点
    if (L == NULL) {    //内存不足，分配失败
        return false;
    }
    L->next = NULL;     //头结点之后暂时没有节点
    return true;
}

//判断单链表是否为空（带头结点）
bool Empty(LinkList L) {
    if (L->next == NULL) {
        return true;
    } else {
        return false;
    }
}

//在第i个位置插入元素e（带头结点）
bool ListInsert(LinkList &L, int i, int e) {
    if (i < 1) {
        return false;
    }
    LNode *p = GetElem(L, i-1);     //找到第i-1个节点
    return InsertNextNode(p, e);    //p后插入新元素e
}

//按位查找，返回第i个元素（带头结点）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) {
        return NULL;
    }
    LNode *p;   //指针p指向当前扫描到的节点
    int j = 0;  //当前p指向的是第几个节点
    p = L;      //L指向头结点，头结点是第0个节点（不存数据）
    while (p!=NULL && j<i) {    //循环找到第i个节点
        p = p->next;
        j++;
    }
    return p;
}

//后插操作：在p节点之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (p == NULL) {
        return false;
    }
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) {    //内存分配失败
        return false;
    }
    s->data = e;    //用节点s保存数据元素e
    s->next = p->next;
    p->next = s;
    return true;
}

//求表长度 
int length(LinkList L) {
    int len = 0;    //统计表长
    LNode *p = L;
    while (p->next != NULL) {
        p = p->next;
        len++;
    }
    return len;
}
信工核心
#数据结构 #单链表 #查找
(09)王道数据结构-单链表的查找
https://www.eldpepar.com/iecore/28391/
作者
EldPepar
发布于
2022年7月22日
许可协议