循环单链表及常用操作（C语言描述）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了循环单链表及常用操作（C语言描述），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5932字，纯文字阅读大概需要9分钟。

内容图文

实现以下操作

init 初始化

traverse 遍历

head_add 头追加（），尾追加（尾插法）只需要注释掉函数最后一行的头指针赋值

len 长度

insert 指定位置插入

search 正、反向查找数据，返回第1次匹配的位置，找不到返回-1

get 获取指定位置的数据

代码

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct node {
    int data;
    struct node *pNext;
}NODE, *PNODE;

void init(PNODE *);
void traverse(PNODE);
void head_add(PNODE *, int);
int len(PNODE);
bool insert(PNODE *, int, int);
int search(PNODE, int, bool);
bool get(PNODE, int, int *);

bool get(PNODE head, int pos, int *pVal)
{
    PNODE p = head;
    int i = 1;
    if (! head || pos < 1 || pos > len(head)) {
        return false;
    }

    while (i < pos) {
        p = p->pNext;
        ++i;
    }
    *pVal = p->data;

    return true;    
}

int search(PNODE head, int val, bool forward)
{
    PNODE p = head;
    int i = 1, last = -1;
    if (!head)
        return -1;

    if (forward) {
        while (p->pNext != head && p->data != val) {
            p = p->pNext;
            ++i;
        }
        if (p->data == val)
            last = i;
    }
    else {
        while (p->pNext != head) {
            if (p->data == val) {
                last = i;
            }
            p = p->pNext;
            ++i;
        }
        if (p->data == val)
            last = i;
    }

    return last;
}

bool insert(PNODE *pHead, int pos, int val)
{
    PNODE tmp, p;
    int i = 1;
    printf("尝试插入位置 %d 数值 %d: ", pos, val);
    if (pos < 1 || pos > len(*pHead)+1) {
        printf(" 无效的插入位置\n");
        return false;
    }

    tmp = (PNODE)malloc(sizeof(NODE));
    tmp->data = val;

    if (! *pHead) {
        *pHead = tmp;
        tmp->pNext = *pHead;
        printf(", 空链表的第1个节点");
    }
    else if (pos == 1) {
        p = (*pHead)->pNext;
        while (p->pNext != (*pHead)) {
            p = p->pNext;
        }

        p->pNext = tmp;
        tmp->pNext = *pHead;
        // 更新头指针指向(不加下面这行则实现了尾插法)
        *pHead = tmp;
    }
    else {
        p = *pHead;
        while (i < pos-1) {
            p = p->pNext;
            i++;
        }
        tmp->pNext = p->pNext;
        p->pNext = tmp;
    }
    printf(", 成功\n");

    return true; 
}

int len(PNODE head)
{
    PNODE p = head;
    int i = 1;
    if (!head)
        return 0;

    while (p->pNext != head) {
        p = p->pNext;
        ++i;
    }
    return i;

}

void head_add(PNODE *pHead, int val)
{
    printf("head_add node value: %d\n", val);
    PNODE tmp, p;
    if (*pHead == NULL) {
        *pHead = (PNODE)malloc(sizeof(NODE));
        if (! *pHead) {
            printf("内存分配失败!\n");
            return;
        }
        (*pHead)->data = val;
        (*pHead)->pNext = *pHead;
    }
    else {
        tmp = (PNODE)malloc(sizeof(NODE));
        if (! tmp) {
            printf("内存分配失败!\n");
            return;
        }
        tmp->data = val;

        p = (*pHead)->pNext;
        while (p->pNext != (*pHead)) {
            p = p->pNext;
        }

        p->pNext = tmp;
        tmp->pNext = *pHead;
        // 更新头指针指向(不加下面这行则实现了尾插法)
        *pHead = tmp;
    }
}

void traverse(PNODE head)
{
    printf("遍历结果:\n");
    PNODE p = head;
    int i = 1;

    if (! head) {
        printf("链表为空!\n");
        return;
    }

    do {
        printf("第 %d 个节点, self %p, data %d, pNext %p\n", i, p, p->data, p->pNext);
        p = p->pNext;
        ++i;
    } while (p != head);
}

void init(PNODE *pHead)
{
    PNODE tmp, p;

    int val, i=1;
    while (1) {
        printf("请输入节点 %d 的值，结束初始化请输入负数: ", i);
        scanf("%d", &val);
        if (val < 0)
            break;

        if (*pHead == NULL) {
            *pHead = (PNODE)malloc(sizeof(NODE));
            if (! *pHead) {
                printf("内存分配失败!\n");
                return;
            }
            (*pHead)->data = val;
            (*pHead)->pNext = *pHead;
            printf("初始化头节点:self %p, data %d, pNext %p\n", *pHead, (*pHead)->data, (*pHead)->pNext);
        }
        else {
            tmp = (PNODE)malloc(sizeof(NODE));
            if (! tmp) {
                printf("内存分配失败!\n");
                return;
            }
            tmp->data = val;
            tmp->pNext = *pHead;

            p = (*pHead)->pNext;
            while (p->pNext != (*pHead)) {
                p = p->pNext;
            }
            p->pNext = tmp;
        }
        ++i;
    }

}

int main(void)
{
    PNODE head;
    int val;

    traverse(head);
    printf("len:%d\n", len(head));
    init(&head);
    traverse(head);
    head_add(&head, 10);
    head_add(&head, 9);
    traverse(head);
    printf("len:%d\n", len(head));
    insert(&head, 1, 8);
    insert(&head, 1, 6);
    insert(&head, 2, 7);
    traverse(head);
    printf("len:%d\n", len(head));

    insert(&head, 2, 11);
    traverse(head);
    printf("正向查找 5 所在节点:%d\n", search(head, 5, true));
    printf("正向查找 11 所在节点:%d\n", search(head, 11, true));
    printf("反向查找 11 所在节点:%d\n", search(head, 11, false));
    printf("正向查找 13 所在节点:%d\n", search(head, 13, true));

    if (get(head, 1, &val)) {
        printf("get成功，第 %d 节点值为: %d\n", 1, val);
    }

    if (get(head, 5, &val)) {
        printf("get成功，第 %d 节点值为: %d\n", 5, val);
    }

    return 0;
}

output

[root@8be225462e66 c]# gcc circular_linklist.c && ./a.out
遍历结果:
链表为空!
len:0
请输入节点 1 的值，结束初始化请输入负数: 11
初始化头节点:self 0x139cac0, data 11, pNext 0x139cac0
请输入节点 2 的值，结束初始化请输入负数: 12
请输入节点 3 的值，结束初始化请输入负数: 13
请输入节点 4 的值，结束初始化请输入负数: -1
遍历结果:
第 1 个节点, self 0x139cac0, data 11, pNext 0x139cae0
第 2 个节点, self 0x139cae0, data 12, pNext 0x139cb00
第 3 个节点, self 0x139cb00, data 13, pNext 0x139cac0
head_add node value: 10
head_add node value: 9
遍历结果:
第 1 个节点, self 0x139cb40, data 9, pNext 0x139cb20
第 2 个节点, self 0x139cb20, data 10, pNext 0x139cac0
第 3 个节点, self 0x139cac0, data 11, pNext 0x139cae0
第 4 个节点, self 0x139cae0, data 12, pNext 0x139cb00
第 5 个节点, self 0x139cb00, data 13, pNext 0x139cb40
len:5
尝试插入位置 1 数值 8: , 成功
尝试插入位置 1 数值 6: , 成功
尝试插入位置 2 数值 7: , 成功
遍历结果:
第 1 个节点, self 0x139cb80, data 6, pNext 0x139cba0
第 2 个节点, self 0x139cba0, data 7, pNext 0x139cb60
第 3 个节点, self 0x139cb60, data 8, pNext 0x139cb40
第 4 个节点, self 0x139cb40, data 9, pNext 0x139cb20
第 5 个节点, self 0x139cb20, data 10, pNext 0x139cac0
第 6 个节点, self 0x139cac0, data 11, pNext 0x139cae0
第 7 个节点, self 0x139cae0, data 12, pNext 0x139cb00
第 8 个节点, self 0x139cb00, data 13, pNext 0x139cb80
len:8
尝试插入位置 2 数值 11: , 成功
遍历结果:
第 1 个节点, self 0x139cb80, data 6, pNext 0x139cbc0
第 2 个节点, self 0x139cbc0, data 11, pNext 0x139cba0
第 3 个节点, self 0x139cba0, data 7, pNext 0x139cb60
第 4 个节点, self 0x139cb60, data 8, pNext 0x139cb40
第 5 个节点, self 0x139cb40, data 9, pNext 0x139cb20
第 6 个节点, self 0x139cb20, data 10, pNext 0x139cac0
第 7 个节点, self 0x139cac0, data 11, pNext 0x139cae0
第 8 个节点, self 0x139cae0, data 12, pNext 0x139cb00
第 9 个节点, self 0x139cb00, data 13, pNext 0x139cb80
正向查找 5 所在节点:-1
正向查找 11 所在节点:2
反向查找 11 所在节点:7
正向查找 13 所在节点:9
get成功，第 1 节点值为: 6
get成功，第 5 节点值为: 9
[root@8be225462e66 c]#

内容总结

以上是互联网集市为您收集整理的循环单链表及常用操作（C语言描述）全部内容，希望文章能够帮你解决循环单链表及常用操作（C语言描述）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端