C语言基础---链表

版权声明：本文为小斑马伟原创文章，转载请注明出处！
一、数组的缺陷
数组的缺陷1:静态空间，一旦分配内存后，不可以动态扩展。如果分配少了，可能不够用，如果分配多了，可能造成浪费。
数组缺陷2：对头部删除和插入、效率很低。因为头部数据插入和删除，要移动数据。
二、链表的基本概念
链表的组成:链表是由节点组成的，节点由数据域和指针域组成。
链表的分类：方式1：静态链表 动态链表 方式2：单向链表 双向链表 单向循环链表和双向循环链表。

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

//1.静态链表

//节点的声明
struct LinkNode
{
    int num; //数据域
    struct LinkNode* next; //指针域
};

void test01() 
{
   //创建节点
   struct LinkNode node1 = { 10, NULL };
   struct LinkNode node2 = { 20, NULL };
   struct LinkNode node3 = { 30, NULL };
   struct LinkNode node4 = { 40, NULL };
   struct LinkNode node5 = { 50, NULL };

      //建立关系
   node1.next = &node2;
   node2.next = &node3;
   node3.next = &node4;
   node4.next = &node5;
   node5.next = NULL;

   //如何遍历这个链表

   //创建一个指针 指向第一个节点
   struct LinkNode* pCurrent = &node1;

   while (pCurrent != NULL) {
       printf("%d\n", pCurrent->num);

       pCurrent = pCurrent->next;
   }

}

//动态链表
void test2() {
    struct LinkNode* node1 = malloc(sizeof(struct LinkNode));
    struct LinkNode* node2 = malloc(sizeof(struct LinkNode));
    struct LinkNode* node3 = malloc(sizeof(struct LinkNode));
    struct LinkNode* node4 = malloc(sizeof(struct LinkNode));
    struct LinkNode* node5 = malloc(sizeof(struct LinkNode));

    node1->num = 10;
    node2->num = 30;
    node3->num = 50;
    node4->num = 70;
    node5->num = 90;

 //建立关系
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = NULL;

//遍历链表
   struct LinkNode* pCurrent = node1;
   while (pCurrent != NULL) {
       printf("%d\n", pCurrent->num);

       pCurrent = pCurrent->next;
    }

}

int main() {
    test01();
    printf("\n");
    test2();
    system("pause");
    return EXIT_SUCCESS;

}

静态链表 创建在栈上 动态链表 创建在堆上
三、带头和不带头的链表
带头节点链表：固定一个节点作为头结点（数据域不保存有效数据），起一个标志位的作用，以后不管链表节点如何改变，此头节点固定不变。


不带节点的链表：头节点不固定，根据实际需要交换头节点（如在原来头节点前插入新节点，然后，新节点重新作为链表的头节点）。


带头节点的链表的初始化和遍历

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

//节点声明
struct LinkNode
{
    int num;
    struct LinkNode *next;
};

//初始化链表
struct LinkNode* init_LinkList();

//遍历链表
void foreach_LinkList(struct LinkNode* pHeaher);

 //插入链表
void insert_LinkList(struct LinkNode* pHeaher, int oldValue, int newValue);

 //删除链表
void delete_LinkList(struct LinkNode* pHeader, int val);

//清空链表
void clear_LinkList(struct LinkNode* pHeader);

//销毁链表
void destory_LinkList(struct LinkNode* pHeader);

插入链表、删除链表、清空和销毁链表

#include"linkList.h"

struct LinkNode* init_LinkList()
{
struct LinkNode* pHeader = malloc(sizeof(struct LinkNode));

if (pHeader == NULL)
{
    return NULL;
}

//pHeader->num = -1; 头节点不维护数据域
pHeader->next = NULL;//头节点初始化指针域为NULL

//创建一个尾节点，利用后期添加新的数据
struct LinkNode* pTail = pHeader;

int val = -1;

while (1) {
    printf("请插入数据 -1代表输入结束:\n");

    scanf("%d", &val);

    if (val == -1)
    {
        break;
    }

    //创建新的节点
    struct LinkNode* newNode = malloc(sizeof(struct LinkNode));
    newNode->num = val;
    newNode->next = NULL;

    //建立关系
    pTail->next = newNode;
    //更新新的尾节点
    pTail = newNode;
}
return pHeader;
}

//遍历链表
void foreach_LinkList(struct LinkNode* pHeader)
{
if (pHeader == NULL)
{
    return;
}

//pCurrent 起始指向的是第一个有真实数据的节点
struct LinkNode* pCurrent = pHeader->next;

while (pCurrent != NULL)
{
    printf("%d\n", pCurrent->num);
    pCurrent = pCurrent->next;
}
}

//插入链表
void insert_LinkList(struct LinkNode* pHeader, int oldVal, int newVal)
{
if (pHeader == NULL)
{
    return;
}

//创建两个辅助指针变量
struct LinkNode* pPrev = pHeader;
struct LinkNode* pCurrent = pHeader->next;

while (pCurrent != NULL)
{
    if (pCurrent->next == oldVal)
    {
        break;
    }

    //如果没有找到位置，让辅助指针右移
    pPrev = pCurrent;
    pCurrent = pCurrent->next;
}

//创建新节点
struct LinkNode* newNode = malloc(sizeof(struct LinkNode));
newNode->num = newVal;
newNode->next = NULL;

//建立关系  更新指针的指向
newNode->next = pCurrent;
pPrev->next = newNode;

}

//删除链表
void delete_LinkList(struct LinkNode* pHeader, int val)
{
if (pHeader == NULL)
{
    return;
}

//创建两个辅助的指针变量
struct LinkNode* pPrev = pHeader;
struct LinkNode* pCurrent = pHeader->next;

while (pCurrent != NULL)
{
    if (pCurrent->num == val)
    {
        break;
    }

    pPrev = pCurrent;
    pCurrent = pCurrent->next;
}

//无效数据 就直接return
if (pCurrent == NULL)
{
    return;
}

//更改指针的指向
pPrev->next = pCurrent->next;

//删除节点
free(pCurrent);
pCurrent = NULL;
}

//清空链表
void clear_LinkList(struct LinkNode* pHeader)
{
  if (pHeader == NULL)
  {
    return;
  }

//创建临时指针
struct LinkNode* pCurrent = pHeader->next;

while (pCurrent != NULL)
{
    //先保存住待删除节点的后面的节点
    struct LinkNode* nextNode = pCurrent->next;

    free(pCurrent);
    pCurrent = nextNode;
}

//头节点的next置空
pHeader->next = NULL;
}

//销毁链表
void destory_LinkList(struct LinkNode* pHeader)
{
if (pHeader == NULL)
{
    return;
}

//先清空链表
clear_LinkList(pHeader);
//再释放头节点
free(pHeader);
pHeader = NULL;

}

void test01()
{
 //初始化链表
struct LinkNode* pHeader = init_LinkList();

//遍历链接
printf("遍历链表的结果为\n");
foreach_LinkList(pHeader);

//插入数据
//10 20 30 
insert_LinkList(pHeader, 10, 100);
insert_LinkList(pHeader, 20, 200);
insert_LinkList(pHeader, -1, 300);

//插入后数据的遍历
printf("遍历链表的结果为\n");
foreach_LinkList(pHeader);

//测试删除
delete_LinkList(pHeader, 30);
delete_LinkList(pHeader, 100);
delete_LinkList(pHeader, 1000);

//删除后的数据
printf("遍历链表的结果为\n");
foreach_LinkList(pHeader);

//清空链表
clear_LinkList(pHeader);
//清空后的数据
printf("遍历链表的结果为\n");
foreach_LinkList(pHeader);

//尾插
insert_LinkList(pHeader, 111, 111);
insert_LinkList(pHeader, 222, 222);
insert_LinkList(pHeader, 333, 333);

//清空后再次使用链表，遍历链表
foreach_LinkList(pHeader);

//销毁链表
destory_LinkList(pHeader);
pHeader = NULL;
}

int main() {
test01();

system("pause");
return EXIT_SUCCESS;
}


链表的反转和计算其个数

//反转链表
void reverse_LinkList(struct LinkNode* pHeader)
{
if (pHeader == NULL)
{
    return;
}

struct LinkNode * pPrev = NULL;
struct LinkNode * pCurrent = pHeader->next;
struct LinkNode * pNext = NULL;

while (pCurrent != NULL)
{
    pNext = pCurrent->next;
    pCurrent->next = pPrev; //改变链表指向

    pPrev = pCurrent;
    pCurrent = pNext;
}

pHeader->next = pPrev;
}

 //返回链表长度
int size_LinkList(struct LinkNode* pHeader)
{
if (pHeader == NULL)
{
    return -1;
}

struct LinkNode* pCurrent = pHeader->next;

int num = 0; 
while (pCurrent != NULL)
{
    num++;
    pCurrent = pCurrent->next;
}

return num;
}

void test02()
{
struct LinkNode* pHeader = init_LinkList();

// 10 20 30

//翻转后 结果应该是 30 20 10 
reverse_LinkList(pHeader);

printf("翻转链表后结果为\n"); 
foreach_LinkList(pHeader);

printf("链表的长度为: %d\n", size_LinkList(pHeader));

}

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 211,290评论 6赞 491
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,107评论 2赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 156,872评论 0赞 347
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,415评论 1赞 283
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,453评论 6赞 385
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,784评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,927评论 3赞 406
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,691评论 0赞 266
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,137评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,472评论 2赞 326
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,622评论 1赞 340
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,289评论 4赞 329
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,887评论 3赞 312
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,741评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,977评论 1赞 265
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,316评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,490评论 2赞 348

推荐阅读更多精彩内容

  • 数据结构基础概念篇
    一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这...
    Winterfell_Z阅读 5,695评论 0赞 13
  • 2018之线性表的基本概念
    转自：http://blog.csdn.net/oreo_go/article/details/52116214 ...
    YYT1992阅读 965评论 0赞 4
  • 捕梦网1
    "哇，好帅啊。"苏月趴在沙发上全神贯注的看着电视。 "大家好，我们是TFBOYS。" "我是TFBOYS王俊凯。"...
    夏月心阅读 135评论 0赞 2
  • 武大心咨义工读书会（陆·深剖）
    武大心咨义工读书会第六次活动，地点：胡姐家。 本次特邀嘉宾，胡姐的朋友，调频107.8“私家夜话”栏目主播，陈老师...
    Walking林杨阅读 386评论 1赞 1