本文共 4440 字，大约阅读时间需要 14 分钟。

单链表技术指南

结点类型定义

在单链表中，结点由数据域和指针域组成。数据域存储实际数据，指针域指向下一个结点。定义如下：

typedef struct LNode {    int data;    struct LNode *next;} LNode *, *LinkList;

初始化单链表

首先需要初始化链表。以下是初始化链表的步骤：

#include 
   
    using namespace std;typedef struct LNode {    int data;    struct LNode *next;} LNode *, *LinkList;void initLinkList(LinkList &L) {    L = (LinkList)malloc(sizeof(LNode));    if (L == NULL) {        cout << "内存不足，空间分配失败！";        return;    }    L->next = NULL;}int main() {    LinkList L;    initLinkList(L);    return 0;}
   

创建单链表

头插法创建单链表

头插法是创建单链表的一种常用方法。以下是实现代码：

#include 
   
    using namespace std;typedef struct LNode {    int data;    struct LNode *next;} LNode *, *LinkList;void initLinkList(LinkList &L) {    L = (LinkList)malloc(sizeof(LNode));    if (L == NULL) {        cout << "内存不足，空间分配失败！";        return;    }    L->next = NULL;}void createLinkList_Head(LinkList &L, int a[], int n) {    for (int i = 0; i < n; i++) {        LNode *p = (LNode *)malloc(sizeof(LNode));        p->data = a[i];        p->next = L->next;        L->next = p;    }}int main() {    int data[] = {1, 2, 3, 4, 5};    LinkList L;    initLinkList(L);    createLinkList_Head(L, data, 5);    LNode *q = L->next;    while (q != NULL) {        cout << q->data << " ";        q = q->next;    }    return 0;}
   

尾插法创建单链表

尾插法是另一种创建单链表的方法。以下是实现代码：

#include 
   
    using namespace std;typedef struct LNode {    int data;    struct LNode *next;} LNode *, *LinkList;void initLinkList(LinkList &L) {    L = (LinkList)malloc(sizeof(LNode));    if (L == NULL) {        cout << "内存不足，空间分配失败！";        return;    }    L->next = NULL;}void createLinkList(LinkList &L, int a[], int n) {    LNode *r = L;    for (int i = 0; i < n; i++) {        LNode *p = (LNode *)malloc(sizeof(LNode));        p->data = a[i];        p->next = NULL;        r->next = p;        r = p;    }}int main() {    int data[] = {1, 2, 3, 4, 5};    LinkList L;    initLinkList(L);    createLinkList(L, data, 5);    LNode *q = L->next;    while (q != NULL) {        cout << q->data << " ";        q = q->next;    }    return 0;}
   

查找单链表中的元素

按序号查找

以下是按序号查找单链表中指定位置的结点的实现：

#include 
   
    using namespace std;typedef struct LNode {    int data;    struct LNode *next;} LNode *, *LinkList;LNode *getLocalElem(LinkList L, int i) {    LNode *p = L;    int num = 0;    while (p != NULL && num < i) {        p = p->next;        num++;    }    return p;}int main() {    int data[] = {1, 2, 3, 4, 5};    LinkList L;    initLinkList(L);    createLinkList_Tail(L, data, 5);    LNode *q = getLocalElem(L, 2);    if (q == NULL) {        cout << "未找到该元素，请检查输入是否正确！";    } else {        cout << q->data;    }    return 0;}
   

按值查找

以下是根据结点数据值查找单链表中的结点的实现：

#include 
   
    using namespace std;typedef struct LNode {    int data;    struct LNode *next;} LNode *, *LinkList;LNode *getValueElem(LinkList L, int val) {    LNode *p = L->next;    while (p != NULL) {        if (p->data != val) {            p = p->next;        } else {            return p;        }    }    return NULL;}int main() {    int data[] = {1, 2, 3, 4, 5};    LinkList L;    initLinkList(L);    createLinkList_Tail(L, data, 5);    LNode *q = getValueElem(L, 2);    if (q == NULL) {        cout << "未找到该元素，请检查输入是否正确！";    } else {        cout << q->data;    }    return 0;}
   

插入结点

在指定位置插入结点

以下是插入结点的实现：

#include 
   
    using namespace std;typedef struct LNode {    int data;    struct LNode *next;} LNode *, *LinkList;void InLinkList(LinkList &L, int i, int val) {    LNode *p = getLocalElem(L, i - 1);    LNode *q = (LNode *)malloc(sizeof(LNode));    q->data = val;    q->next = p->next;    p->next = q;}int main() {    int data[] = {1, 2, 3, 4, 5};    LinkList L;    initLinkList(L);    createLinkList_Tail(L, data, 5);    InLinkList(L, 2, 0);    LNode *q = L->next;    while (q != NULL) {        cout << q->data << " ";        q = q->next;    }    return 0;}
   

删除结点

删除指定位置的结点

以下是删除结点的实现：

#include 
   
    using namespace std;typedef struct LNode {    int data;    struct LNode *next;} LNode *, *LinkList;void DeLinkList(LinkList &L, int i) {    LNode *p = getLocalElem(L, i - 1);    LNode *q = p->next;    p->next = q->next;    free(q);}int main() {    int data[] = {1, 2, 3, 4, 5};    LinkList L;    initLinkList(L);    createLinkList_Tail(L, data, 5);    DeLinkList(L, 2);    LNode *q = L->next;    while (q != NULL) {        cout << q->data << " ";        q = q->next;    }    return 0;}
   

通过以上方法，我们可以完成单链表的创建、查找、插入和删除操作。每个操作都需要仔细处理指针指向，确保链表的完整性和正确性。

转载地址：http://aumq.baihongyu.com/