C语言链表

链表

  • 链表用于解决合理利用存储空间的问题

  • malloc在没有连续内存空间的时候分配会失败

  • 解决方案:

    • 不要一次性开辟一块连续的存储空间, 每次少开辟一点
      最后利用指针将所有开辟的小的存储空间链接在一起, 组成一个整体

静态链表

typedef struct node{
    int data; // 专门用于存储数据的
    struct node *next; // 专门用于实现链接的
} Node;
int main()
{
 // 1.定义三个结构体
    Node a;
    Node b;
    Node c;
    // 2.让三个结构体保存数据
    a.data = 1;
    b.data = 3;
    c.data = 5;
    // 3.将三个结构体链接在一起
    a.next = &b;
    b.next = &c;
    // 如果指针没有值, 那么就可以赋值为NULL, 明确告诉系统该指针没有值
    // 如果一个指针没有值,也没有赋值为NULL, 那么这个指针就是一个野指针
    // 注意: 一定不要操作没有值的指针和野指针
    c.next = NULL;
    // 4.定义链表的头指针
    Node *head = &a;
    return 0;
}

空链表

  • 只有一个头指针和头结点,并且头结点没有下一个结点且没有数据
#include <studio.h>
Node * createNode();
typedef struct node{
int data;
struct node *next;
} Node;
int main()
{
    Node *head = createNode();
    return 0;
}
Node *createNode()
{
    //1.创建一个头结点
    Node *head= (Node *)malloc(sizeof(Node));
    //1.1可能分配失败
    if(head == NULL)
{
    exit(-1);
}
    //2.下一个节点赋值为空
    head -> next = NULL;
    return head;
}

  • 内存分配图解:


动态链表尾差法

  • 规则:
    1.把新结点的下一个结点指向头结点的下一个结点
    2.把头结点的下一个结点指向新结点

代码如下:

#include <stdio.h>
typedef struct node
{
    int data;
    struct node *next;
} Node;
void printList(Node * head);
Node *createList();
int main()
{
    //0.创建头结点和头指针
    Node *head = createList();
    //1.打印数据
    printList(head);
    return 0;
}

void printList(Node * head){
    //1.接收头指针,头指针指向头结点
    //2.头结点是没有数据的,我们可以将头指针直接指向头结点的下一个结点
    //输出数据
    Node *cur = head;
    while(cur->next != NULL){
        cur = cur -> next;
        printf("%d\n",cur -> data);
    }
/**
 * @brief createList 尾差法创建动态链表
 * @return 返回头指针
 */
Node *createList(){
    //1.创建头指针和头结点
    Node *head = (Node *)malloc(sizeof(Node));
    if(head == NULL){
        exit(-1);
    }
    head -> next = NULL;

    //1.用一个变量表示循环条件
    //2.提示用户输入要保存的数据
    int num = 0;
    printf("请输入想要保存的数据,输入-1结束\n");
    scanf("%d",&num);
    while(-1 != num)
    {
        Node *node = (Node*)malloc(sizeof(Node));
        //保存数据
        node -> data = num;
        //1.把新结点的下一个结点指向头结点的下一个结点
        node -> next = head -> next;
        //2.把头结点的下一个结点指向新结点
        head -> next = node;

        printf("请输入想要保存的数据,输入-1结束\n");
        scanf("%d",&num);
    }
    return head;
}

  • 图解


动态链表头插法

  • 规则:
    1.定义变量记录最后一个结点
    2.让新结点成为上一个结点的下一个结点
    3.把新结点作为下一个结点的上一个结点
#include <stdio.h>
typedef struct node
{
    int data;
    struct node *next;
} Node;
Node *createList();
void printList(Node *head);
int main()
{
    //动态链表头插法
    Node *head = createList();
    printList(head);
    return 0;
}

void printList(Node *head){
    Node *cur = head;
    while(cur->next != NULL)//首先判断不是空链表
    {
        cur = cur -> next;
        printf("%d\n",cur -> data);
    }
}
Node *createList(){
    //1.创建头结点和头指针
    Node *head = (Node*)malloc(sizeof(Node));
    //分配失败
    if(head == NULL){
        exit(-1);
    }
    head->next = NULL;

    //定义变量控制循环
    int num = -1;
    printf("请输入你想要保存的数据:\n");
    scanf("%d",&num);
    //1.定义变量记录最后一个结点
    Node *cur = head;//一定要放在最外面,否则会引起值覆盖
    while(-1 != num)
    {
        Node *node = (Node*)malloc(sizeof(Node));
        node->data = num;
        node->next = NULL;
        //2.让新结点的上一个结点的下一个结点指向新结点
        cur->next = node;
        //3.把新结点作为下一个结点的上一个结点
        cur = node;
        printf("请输入你想要保存的数据:\n");
        scanf("%d",&num);
    }
    return head;
}

  • 图解


封装

  • 我们可以封装一个创建空链表的函数
/**
 * @brief createEmpty 创建空链表
 * @return 链表的头指针
 */
Node *createEmpty(){
    // 1.定义头指针
    Node *head = NULL;
    // 2.创建一个空节点, 并且赋值给头指针
    head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    // 3.返回头指针
    return head;
}
  • 我们可以将插入数据封装成一个函数
void  insertNode(Node *head, int num){
    // 1.创建一个新的节点
    Node *node = (Node *)malloc(sizeof(Node));
    // 2.将数据保存到新节点中
    node->data = num;

    // 3.进行插入
    // 3.1让新节点的下一个节点 等于 头节点的下一个节点
    node->next = head->next;
    // 3.2让头结点的下一个节点 等于 新节点
    head->next = node;
}
  • 我们可以封装一个销毁链表的函数
// 封装一个专门用于销毁链表的函数
/**
 * @brief destroyList 销毁链表
 * @param head 链表的头指针
 */
void destroyList(Node *head){
    Node *cur = NULL;
    while(head != NULL){
        cur = head->next;
        free(head);
        head = cur;
    }
}
  • 我们可以封装一个计算链表长度的函数
// 封装一个专门用于计算链表长度的函数
int listLength(Node *head){
    // 1.定义变量记录节点的个数
    int count = 0;
    // 注意点: 头结点不要
    Node *cur = head->next;
    // 2.遍历统计节点个数
    while(cur != NULL){
        count++;
        cur = cur->next;
    }
    return count;
}
  • 我们可以封装一个查找指定结点的函数
// 封装一个专门用于查找指定节点的函数
/**
 * @brief findNode 查找指定节点
 * @param head 链表的头指针
 * @param key 需要查找的key
 * @return 符合要求的节点, 如果找不到返回NULL
 */
Node *findNode(Node* head, int key){
    // 注意点: 头结点不需要查找
    head = head->next;
    while(head != NULL){
        // 判断当前节点保存的值是否是要查找的值
        if(head->data == key){
            return head;
        }else{
            head = head->next;
        }
    }
    return NULL;
}
  • 我们可以封装一个删除指定结点的函数
//封装一个专门用于删除指定节点的函数
/**
 * @brief deleteNode 删除指定节点
 * @param head 链表的头指针
 * @param node 需要删除的节点
 */
void deleteNode(Node *head, Node *node){
    // 1.找到需要删除节点的上一个节点
    while(head->next != node){
        head = head->next;
    }
    // 2.将删除节点上一个节点的next改为 , 删除节点的下一个节点
    head->next = node->next;
    // 3.删除对应节点
    free(node);
}
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,922评论 6赞 497
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,591评论 3赞 389
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 160,546评论 0赞 350
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,467评论 1赞 288
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,553评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,580评论 1赞 293
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,588评论 3赞 414
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,334评论 0赞 270
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,780评论 1赞 307
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,092评论 2赞 330
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,270评论 1赞 344
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,925评论 5赞 338
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,573评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,194评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,437评论 1赞 268
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,154评论 2赞 366
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,127评论 2赞 352