C语言-数据结构-单向链表

链表

链表实现了，内存零碎数据的有效组织。比如，当我们用 malloc 来进行内存申请的时候，当内存足够，但是由于碎片太多，没有连续内存时，只能以申请失败而告终，而用链表这种数据结构来组织数据，就可以解决上类问题。

静态链表

#include 
// 1.定义链表节点
typedef struct node{
    int data;
    struct node *next;
}Node;
int main(int argc, char *argv[]) {
    // 2.创建链表节点
    Node a;
    Node b;
    Node c;

    // 3.初始化节点数据
    a.data = 1;
    b.data = 3;
    c.data = 5;

    // 4.链接节点
    a.next = &b;
    b.next = &c;
    c.next = NULL;

    // 5.创建链表头
    Node *head = &a;

    // 6.使用链表
    while(head != NULL){
        int currentData = head->data;
        printf("currentData = %i\n", currentData);
        head = head->next;//指向下一个节点
    }

    return 0;
}

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

动态链表

静态链表的意义不是很大，主要原因，数据存储在栈上，栈的存储空间有限，不能动态分配。所以链表要实现存储的自由，要动态的申请堆里的空间。

有头链表

无头链表

单向链表有有头节点和无头节点两种列表, 有头节点在列表的删除,反转,插入等操作会比无头节点简单,但是不好之处就是多占用些空间,而且在多个链表结合处理的时候有头链表每次都需要过滤头节点,而无头链表直接完美融合 ,而且很多高级语言都是无头链表的便于日后的扩展 ,下面都是依据无头节点进行演示

定义链表

typedef int boolean;//定义一个布尔类型
#define TRUE 1
#define FALSE 0

// 定义链表节点
typedef struct node {
    char *data;
    struct node *next;
} Node;
typedef  struct  CharLinked {
    Node *head;
    int len;
} CharLinked;
1
2
3
4
5
6
7
8
9
10
11
12
13

创建链表

/**
 * @return  创建链表
 */
CharLinked *createCharLinked() {
    CharLinked *charLinked = (CharLinked *) malloc(sizeof(CharLinked));
    charLinked->head = NULL;
    charLinked->len = 0;
    //返回头节点
    return charLinked;
}
1
2
3
4
5
6
7
8
9
10

创建一个空节点

/**
 * 创建一个空节点
 */
static Node *createNode() {
    Node *node = (Node *) malloc(sizeof(Node));
    node->data = NULL;
    node->next = NULL;

    return node;
}

1
2
3
4
5
6
7
8
9
10
11

尾插法

/**
 * @brief insertEndNode 尾插法插入节点
 * @param head 需要插入的头指针
 * @param data 需要插入的数据
 */
void insertCharLinkedEndNode(CharLinked *charLinked, char *data) {
    Node *head = charLinked->head;
    if(head==NULL){
        Node *newNode = createNode();
        newNode->data = data;
        charLinked->head = newNode;
        return;
    }
    //找到最后一个节点
    Node *pNode = head;
    while (head != NULL) {
        pNode = head;
        head = head->next;
    }
    //创建新节点,追加到最后一个节点
    Node *newNode = createNode();
    newNode->data = data;
    pNode->next = newNode;
    charLinked->len++;
}
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

头插法

/**
 * @brief insertHeadNode 头插法插入节点
 * @param head 需要插入的头指针
 * @param data 需要插入的数据
 */
void insertCharLinkedHeadNode(CharLinked *charLinked, char *data) {
    Node *pNode = createNode();
    //插入数据
    pNode->data =data;
    pNode->next = charLinked->head;
    charLinked->head = pNode;
    charLinked->len++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

指定位置插入一个结点

简单来说就是先找到需要插入的位置,然后将当前位置节点和他前一个节点连接到需要插入的节点就行了

/**
 * @brief insertNOde 将数据节点插入到指定数据位置节点,指定数据节点向后移动,  如果没有找到插入的位置,那么就插入到最后
 * @param insertionPoint 指定的数据节点
 * @param data 需要插入的数据
 */
void insertCharLinkedNode(CharLinked *charLinked, char *insertionPoint, char *data) {

    Node *pNode = charLinked->head;
    Node *pre = pNode;//父节点
    while (pNode != NULL) {
        if (strcmp(pNode->data, insertionPoint) == 0) { //找到插入的位置
            break;
        }
        pre = pNode; //保留当前节点
        pNode = pNode->next;
    }
    //如果没有找到那么就插入到最后
    if (pNode == NULL) {
        insertCharLinkedEndNode(charLinked, data);
        return;
    }
    Node *dataNode = createNode();
    dataNode->data = data;
    pre->next = dataNode;
    dataNode->next = pNode;
    charLinked->len++;
}
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

打印链表

/**
 * @brief printNodeListDouble 遍历链表
 * @param charLinked 链表
 */
void printCharLinked(CharLinked *charLinked) {
    Node *head = charLinked->head;
    while (head != NULL ) {
        char *currentData = head->data;
        printf("currentData = %s\n", currentData);
        head = head->next;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13

链表搜索

/**
 * @brief searchList 查找指定节点
 * @param head 链表头指针
 * @param key 需要查找的值
 * @return
 */
Node *searchCharLinked(CharLinked *charLinked, void *key) {
   Node *head = charLinked->head;
    while (head!=NULL) {
        if (strcmp(head->data, key) == 0) {
            break;
        } else {
            head = head->next;
        }
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

链表数据排序

/**
 * @brief bubbleSort 对链表值进行排序  小到大  按照ASCII
 * @param head 链表头指针
 */
void charCharLinkedSort(CharLinked *charLinked) {
    // 2.定义变量记录前后节点
    Node *cur = charLinked->head;
    while (cur != NULL) {
        Node *cur1 = cur->next;
        while (cur1 != NULL) {
            //比较大小 ,然后交换数据
            if (strcmp(cur->data, cur1->data) >0) {
                char *temp = cur->data;
                cur->data = cur1->data;
                cur1->data = temp;
            }
            cur1 = cur1->next;
        }
        cur = cur->next;
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

反转链表

断开链表头，然后以头插法的方式将原链表的数据添加链表。

/**
 * @brief reverseList 反转链表
 * @param head 链表头指针
 */
void reverseCharLinked(CharLinked *charLinked) {

    Node *head = charLinked->head;
    Node *pre = head, *cur = head->next;
    pre->next = NULL;
    while (cur != NULL) {
        Node *node = cur->next;
        cur->next = pre;
        pre = cur;
        cur = node;
    }
    charLinked->head = pre;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

删除节点数据

先找到需要删除的节点,之后将后一个结点赋值给前一个结点的next,然后将删除位置的结点释放即可

/**
 * @brief delNode 删除指定节点
 */
void delCharLinkedNode(CharLinked *charLinked, void *key) {

    Node *head = charLinked->head;
    //根节点单独处理
    if (strcmp(head->data, key) == 0 && head->next != NULL) {
        charLinked->head = head->next;
        free(head);
        charLinked->len--;
        return;
    }
    Node *head1 = head->next;
    Node *pre = head;//根节点
    while (head1 != NULL) {
        if (strcmp(head1->data, key)==0) {
            pre->next = head1->next;
            free(head1);
            break;
        }
        pre = head1;//当前节点
        head1 = head1->next; //下一个节点
    }
    charLinked->len--;
}

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

加工器

//加工器
void handleCharLinked(CharLinked *charLinked, char *(*func)(char *)) {
    Node *head = charLinked->head;
    while (head != NULL ) {
        head->data=func(head->data);
        head = head->next;
    }
}
1
2
3
4
5
6
7
8

迭代器

// 迭代器结构
typedef struct nodeIterator {
    Node *node;    // 迭代器所指向的集合
} NodeIterator;

NodeIterator *createNodeIterator(CharLinked *charLinked) {
    NodeIterator *iterator = malloc(sizeof(NodeIterator));
    iterator->node = charLinked->head;
    return iterator;
}
boolean hasNextNodeIterator(NodeIterator *iterator) {
    boolean b = iterator->node !=NULL ? TRUE : FALSE;
    if(!b){//迭代完毕释放内存
        free(iterator);
    }
    return b;
}
//迭代下一个元素
char *nextNodeIterator(NodeIterator *iterator) {
    if(!hasNextNodeIterator(iterator)){
        return NULL;
    }
    char *p = iterator->node->data;
    iterator->node = iterator->node->next;//切换到下一个节点
    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

销毁链表

/**
 * @brief destroyList 销毁链表
 * @param head 链表头指针
 */
void destroyCharLinked(CharLinked *charLinked) {
    Node *head = charLinked->head;
    Node *cur = head;
    while (head != NULL) {
        cur = head->next;
        free(head);//清除当前节点内存
        head = cur;
    }
    free(charLinked);//清除链表
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

点赞 -收藏-关注-便于以后复习和收到最新内容 有其他问题在评论区讨论-或者私信我-收到会在第一时间回复 在本博客学习的技术不得以任何方式直接或者间接的从事违反中华人民共和国法律,内容仅供学习、交流与参考 免责声明：本文部分素材来源于网络，版权归原创者所有，如存在文章/图片/音视频等使用不当的情况，请随时私信联系我、以迅速采取适当措施，避免给双方造成不必要的经济损失。 感谢,配合,希望我的努力对你有帮助^_^