C++数据结构单链表初始化、头插法、尾插法、按位置插入、按值查找、删除

知道并理解单链表连理，练习并掌握代码

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
#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;
typedef struct LNode {
    ElemType data; //数据域
    struct LNode *next; //指针域
} LNode, *LinkList;

// LNode* 是结构体指针，和LinkList完全等价 头插法
void linkHeadInsert(LinkList &L) {
    L = (LinkList) malloc(sizeof(LNode)); // 申请头节点空间，头指针指向头节点
    L->next = NULL;
    ElemType x;
    scanf("%d", &x);
    LNode *s;
    while (x != 9999) {
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;  // 头节点的next,指向新节点；
        scanf("%d", &x);
    }
}

// 尾插法
void linkTailInsert(LinkList &L) {
    L = (LinkList) malloc(sizeof(LNode)); // 申请头节点空间，头指针指向头节点
    L->next = NULL;
    ElemType x;
    scanf("%d", &x);
    LNode *s, *r = L;
    while (x != 9999) {
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s; // 尾部节点指向新的节点
        r = s;  // 头节点的next,指向新节点；
        scanf("%d", &x);
    }
    r->next = NULL;
}

// 按位置查找
LinkList getElemIndex(LinkList L, int pos) {
    if (pos < 0) {
        return NULL;
    }
    int i = 0;
    while (L && i < pos) {
        L = L->next;
        i++;
    }
    return L;
}

// 按值查找
LinkList getLocalElem(LinkList L, ElemType value) {
    L = L->next;
    while (L) {
        if (L->data == value) {
            return L;
        }
        L = L->next;
    }
    return NULL;
}


void printList(LinkList L) {
    L = L->next;
    while (L != NULL) {
        printf("%3d", L->data);
        L = L->next;
    }
    printf("\n");
}

// 新节点插入地i个位置
bool insertFrontList(LinkList &L, int pos, ElemType val) {
    LinkList p = getElemIndex(L, pos - 1);
    if (NULL == p) {
        return false;
    }
    LinkList s;
    s = (LinkList) malloc(sizeof(LNode));
    s->data = val;
    s->next = p->next;
    p->next = s;
    return true;
}

// 删除id对应的元素，删除L 不会变，不需要加引用
bool deleteList(LinkList L, int pos) {
    LinkList p = getElemIndex(L, pos - 1); // 拿到要删除节点的前一个节点
    if (NULL == p) {
        return false;
    }
    LinkList q = p->next; // 拿到要删除的节点指针
    p->next = q->next; // 断链
    free(q); // 释放被删除的节点
    return true;
}

// 头插法新建链表
int main() {
    LinkList L; // L是链表头指针，是数据机构的指针类型
    // 头插法
//    linkHeadInsert(L); // 输入数据可以为3 4 5 6 7 9999,都插法新建链表
//    printList(L);
    // 尾插法
    linkHeadInsert(L);
    printList(L);
    // 按位置查找
//    LinkList linkList = getElemIndex(L, 1);
//    if (linkList != NULL) {
//        printf("data=%d\n", linkList->data);
//    } else {
//        printf("no match");
//    }
    // 按位置查找
//    LinkList searchValue = getLocalElem(L, 5);
//    if (searchValue != NULL) {
//        printf("data=%d\n", searchValue->data);
//    } else {
//        printf("no match");
//    }
    // 新节点插入地i个位置
    insertFrontList(L, 3, 99);
    printList(L);
    // 删除元素
    bool ret = deleteList(L, 6);
    if (ret) {
        printf("success");
    } else {
        printf("failer");
    }
    printList(L);
    return 0;
}