陈大剩博客

C语言-单链表相关操作

  • 陈大剩
  • 2021-02-04 00:03:31
  • 1525

复习C语言单链表其实并不顺利,网上查找教程标题是《C语言操作单链表》,内容却是C++;
当时看到*&link这种甚至搜索了一个多星期
后面才搞明白二维指针其实* &==* *,只是C语言中并没有*&这样引用,只有C++才具有;

注意:严蔚敏的《数据结构 C语言版中》大部分代码是C++,C语言运行可能会报错(血的教训);

单链表操作平均时间负杂度为O(n)

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

typedef struct {
    int data;
    struct Link *next;
} link;

void initList(link **list);

void createNode(link **list);

void getInput(link *list);

void insertHeadNode(link *list);

void insertTailNode(link *list);

void freeList(link **list);

void insertRandNode(link *list, int add);

void selectNode(link *list, int add);

void amendNode(link *list, int add);

//初始化链表
void initList(link **list) {
    //申请头节点
    link *temp, *p = (link *) malloc(sizeof(link));
    if (p == NULL) {
        printf("%s函数执行,申请内存失败\n", __FUNCTION__);
    }
    p->data = NULL;
    createNode(&temp);
    p->next = temp;
    *list = p;
}

//获取输入值
void getInput(link *list) {
    link *temp = list;
    printf("请输入值\n");
    temp->next = NULL;
    scanf("%d", &temp->data);
}

//创建节点
void createNode(link **list) {
    link *temp = (link *) malloc(sizeof(link));
    if (temp == NULL) {
        printf("%s函数执行,申请内存失败\n", __FUNCTION__);
    }
    getInput(temp);
    *list = temp;
}

//头插法
void insertHeadNode(link *list) {
    link *temp = NULL, *p = list;
    createNode(&temp);
    if (p->next == NULL) {
        printf("%s函数执行,头结点为空\n", __FUNCTION__);
    }
    temp->next = p->next;
    p->next = temp;
}

//尾插法
void insertTailNode(link *list) {
    link *temp = NULL, *p = list;
    createNode(&temp);
    if (p == NULL) {
        printf("%s函数执行,链表为空\n", __FUNCTION__);
    } else {
        while (p->next) {
            p = p->next;
        }
        p->next = temp;
    }
}

//插入指定位置
void insertRandNode(link *list, int add) {
    link *p = list, *temp;
    int i;
    for (i = 1; i < add; i++) {
        if (p == NULL) {
            printf("%s函数执行,插入位置无效\n", __FUNCTION__);
        }
        p = p->next;
    }
    createNode(&temp);
    temp->next = p->next;
    p->next = temp;
}

//查找节点
void selectNode(link *list, int add) {
    link *temp = list;
    int i;
    for (i = 1; i <= add; i++) {
        if (temp == NULL) {
            printf("%s函数执行,查询位置无效\n", __FUNCTION__);
        }
        temp = temp->next;
    }
    printf("查找的值为:%d \n", temp->data);
}

//修改节点
void amendNode(link *list, int add) {
    link *temp = list;
    int i;
    for (i = 1; i <= add; i++) {
        if (temp == NULL) {
            printf("%s函数执行,查询位置无效\n", __FUNCTION__);
        }
        temp = temp->next;
    }
    printf("请输入修改的值\n");
    scanf("%d", &temp->data);
}

//清空链表
void freeList(link **list) {
    link *temp = *list;
    link *del = NULL;
    if (temp == NULL) {
        printf("%s函数执行,链表为空\n", __FUNCTION__);
    } else {
        while (temp->next) {
            del = temp;
            temp = temp->next;
            free(del);
        }
    }
    del = temp;
    free(del);
    *list = NULL;
}

//打印链表
void printList(link *list) {
    link *temp = list;
    if (temp == NULL) {
        printf("%s函数执行,链表为空\n", __FUNCTION__);
    } else {
        while (temp->next) {
            temp = temp->next;
            printf("输出的值为:%d \n", temp->data);
        }
    }
    putchar('\n');
}

int main() {
    link *list;
    initList(&list);
    insertHeadNode(list);
    insertHeadNode(list);
    insertTailNode(list);
    amendNode(list, 3);
    insertTailNode(list);
    insertRandNode(list, 3);
    selectNode(list, 4);
    printList(list);
    freeList(&list);
    printList(list);
    return 0;
}

输入与输出

//输入
1
2
3
4
5
6
7
//输出
查找的值为:5 
输出的值为:3 
输出的值为:2 
输出的值为:7 
输出的值为:5 
输出的值为:4 
输出的值为:6 

printList函数执行,链表为空

文章如有错误之处,欢迎大神指导。

分享到:
0

说点儿什么吧

头像

表情

本站由陈大剩博客程序搭建 | 湘ICP备17009938号| Copyright © 2017 - 陈大剩博客 | 本站采用创作共用版权:CC BY-NC 4.0

站长统计| 文章总数[31]| 评论总数[12]| 登录用户[21]| 时间点[33]

登入

社交账号登录