[数据结构与算法]C语言数据结构 2：单链表

概念：

链表是以链式结构存储数据的，其中的元素在存储器上的位置是任意的，既逻辑上的相邻在物理位置上不一定相邻。

图示：

结点：

链表：

?头指针是指向头结点的指针。

代码演示：

定义链表结点：

/**
 * 定义链表结构体
 */
typedef struct LinkNode {
    char data;
    struct LinkNode *next;
} LNode, *LinkList, *NodePtr;

创建一个只含有一个节点且没有数据的链表:

/**
 * 创建一个只含有一个节点且没有数据的链表
 * @return 指向头节点的指针
 */
LinkList initLinkList() {
    NodePtr tempHeader = (NodePtr)calloc(1, sizeof(LNode));
    tempHeader->next = NULL;
    return tempHeader;

打印链表:

/**
 * 打印链表
 * @param paraHeader 链表的头节点
 */
void printList(NodePtr paraHeader) {
    NodePtr p = paraHeader->next;
    while (p != NULL) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\r\n");
}

尾插法添加链表元素:

/**
 * 尾插法添加链表元素
 * @param paraHeader 指向链表的头节点的指针
 * @param paraChar 待添加的元素
 */
void appendElement(NodePtr paraHeader, char paraChar) {
    NodePtr p, q;
?
    //1.创造一个新的节点并把paraChar赋给该节点
    q = (NodePtr)malloc(sizeof(LNode));
    q->data = paraChar;
    q->next = NULL;
?
    //2.使p指向该链表当前的尾结点
    p = paraHeader;
    while (p->next != NULL) {
        p = p->next;
    }
?
    //3.插入节点
    p->next = q;
}

原理图：

将元素插入到给定位置:

/**
 * 将元素插入到给定位置
 * @param paraHeader 链表的头节点
 * @param paraChar 待添加的元素
 * @param paraPOsition 插入的位置
 */
void insertElement(NodePtr paraHeader, char paraChar, int paraPosition) {
    NodePtr p, q;
?
    //1.使p指向待插入位置的上一个节点
    p = paraHeader;
    for (int i = 0; i < paraPosition; i++) {
        p = p->next;
        if (p == NULL) {
            printf("此位置：%d 在链表中不存在", paraPosition);
            return ;
        }
    }
?
    //2.创造一个新的节点
    q = (NodePtr)malloc(sizeof(LNode));
    q->data = paraChar;
?
    //3.插入
    printf("linking\r\n");
    q->next = p->next;
    p->next = q;
}

原理图：

从链表中删除数据(给定元素)：

/**
 * 从链表中删除数据
 * @param paraHeader 链表的头节点
 * @param paraChar 待删除的数据
 */
void deleteElement(NodePtr paraHeader, char paraChar) {
    NodePtr p, q;
?
    //寻找该元素
    p = paraHeader;
    while ((p->next != NULL) && (p->next->data != paraChar)) {
        p = p->next;
    }
?
    //判断该元素是否存在
    if (p->next == NULL) {
        printf("该元素不存在\r\n");
        return;
    }
?
    //删除操作
    q = p->next;
    p->next = p->next->next;
    free(q);
}

原理图：

完整代码：

#include <stdio.h>
#include <malloc.h>
?
/**
 * 定义链表结构体
 */
typedef struct LinkNode {
    char data;
    struct LinkNode *next;
} LNode, *LinkList, *NodePtr;
?
/**
 * 创建一个只含有一个节点且没有数据的链表
 * @return 指向头节点的指针
 */
LinkList initLinkList() {
    NodePtr tempHeader = (NodePtr)calloc(1, sizeof(LNode));
    tempHeader->next = NULL;
    return tempHeader;
}
?
/**
 * 打印链表
 * @param paraHeader 链表的头节点
 */
void printList(NodePtr paraHeader) {
    NodePtr p = paraHeader->next;
    while (p != NULL) {
        printf("%c", p->data);
        p = p->next;
    }
    printf("\r\n");
}
?
/**
 * 尾插法添加链表元素
 * @param paraHeader 指向链表的头节点的指针
 * @param paraChar 待添加的元素
 */
void appendElement(NodePtr paraHeader, char paraChar) {
    NodePtr p, q;
?
    //1.创造一个新的节点并把paraChar赋给该节点
    q = (NodePtr)malloc(sizeof(LNode));
    q->data = paraChar;
    q->next = NULL;
?
    //2.使p指向该链表当前的尾结点
    p = paraHeader;
    while (p->next != NULL) {
        p = p->next;
    }
?
    //3.插入节点
    p->next = q;
}
?
/**
 * 将元素插入到给定位置
 * @param paraHeader 链表的头节点
 * @param paraChar 待添加的元素
 * @param paraPOsition 插入的位置
 */
void insertElement(NodePtr paraHeader, char paraChar, int paraPosition) {
    NodePtr p, q;
?
    //1.使p指向待插入位置的上一个节点
    p = paraHeader;
    for (int i = 0; i < paraPosition; i++) {
        p = p->next;
        if (p == NULL) {
            printf("此位置：%d 在链表中不存在", paraPosition);
            return ;
        }
    }
?
    //2.创造一个新的节点
    q = (NodePtr)malloc(sizeof(LNode));
    q->data = paraChar;
?
    //3.插入
    printf("linking\r\n");
    q->next = p->next;
    p->next = q;
}
?
/**
 * 从链表中删除数据
 * @param paraHeader 链表的头节点
 * @param paraChar 待删除的数据
 */
void deleteElement(NodePtr paraHeader, char paraChar) {
    NodePtr p, q;
?
    //寻找该元素
    p = paraHeader;
    while ((p->next != NULL) && (p->next->data != paraChar)) {
        p = p->next;
    }
?
    //判断该元素是否存在
    if (p->next == NULL) {
        printf("该元素不存在\r\n");
        return;
    }
?
    //删除操作
    q = p->next;
    p->next = p->next->next;
    free(q);
}
?
/**
 *单元测试
 */
void appendInsertDeleteTest() {
    LinkList tempList = initLinkList();
    printList(tempList);
?
    appendElement(tempList, 'H');
    appendElement(tempList, 'e');
    appendElement(tempList, 'l');
    appendElement(tempList, 'l');
    appendElement(tempList, 'o');
    appendElement(tempList, '!');
    printList(tempList);
?
    deleteElement(tempList, 'e');
    deleteElement(tempList, 'a');
    deleteElement(tempList, 'H');
    printList(tempList);
?
    insertElement(tempList, 'o', 1);
    insertElement(tempList, 'a', 0);
    printList(tempList);
}
?
void basicAddressTest() {
    LNode tempNode1, tempNode2;
?
    tempNode1.data = 4;
    tempNode1.next = NULL;
?
    tempNode2.data = 6;
    tempNode2.next = NULL;
?
    printf("The first node: %p, %p, %p\r\n",
     ? ? ? &tempNode1, &tempNode1.data, &tempNode1.next);
    printf("The second node: %p, %p, %p\r\n",
     ? ? ? &tempNode2, &tempNode2.data, &tempNode2.next);
?
    tempNode1.next = &tempNode2;
}
?
int main() {
    appendInsertDeleteTest();
    basicAddressTest();
}

总结与反思：

在编写代码的过程中我发现了一个问题：在删除和在指定位置插入元素的操作中删除第一个元素或者插入到第一元素之前会发生什么呢，我之前一直觉得该链表的头指针会发生变化，包括我在上这门课之前自己写一些链表的时候遇到这些操作也的确如此，那么这两个函数的返回值老师却设置的是void，既不改变头指针，那么问题来了，这样编写程序在遇到上述两个问题时应该会出错，但是实际上运行测试代码的时候并没有发生任何错误，那么老师时怎么做到的呢，经过仔细观察我发现，老师在创建链表的时候给第一个链表结点赋成了’/0'，这样就导致了第一个结点实际上是没有意义的一个结点，只是用来让我们抓住这整个链表用的，后面加入的第一个结点如‘H’在物理意义上已经属于第二个结点了，于是该链表的头指针永远不会发生变化，这样大大减少了一些复杂的操作，例如上学期编写的项目学生管理系统中增删函数中某些的操作，所以思路的改变可以使代码更加的简单，这是一个写程序的人所必须铭记的。

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖