专栏首页racaljk[数据结构]C语言链表实现

[数据结构]C语言链表实现

我学数据结构的时候也是感觉很困难,当我学完后我发现了之所以困难时因为我没有系统的进行学习,而且很多教授都只是注重数据结构思想,而忽略了代码方面,为此我写了这些博文给那些试图自学数据结构的朋友,希望你们少走弯路

我尝试用最简单的语言与代码来描述链表,事实上它本身也很简单

静态单链表实现

下面一部分的讨论都将围绕上面这幅图片展开,既然是逐步实现,我不考虑在开头就让这个单链表完美实现,它将只有两个部分:链表的创建&遍历链表输出

首先我们要知道一些简单的概念,一个链表是由节点构成,而每个节点又是又一个数据域和一个指向下一个节点的指针构成,因此我们可以很容易写出下面的结构

struct node//节点
{
    int data;//数据域,这里我们选择存储int型
    struct node *next;//指针域,指向下一个节点,因此被定义为struct *NODE
};

然后再认真观察一下上面的图会发现似乎还有一个头指针没有用(head pointer),头指针的作用就是在浩瀚的内存中指向这个链表的第一个节点,然后我们由第一个节点(通常称之为头结点)的next指针指向下面一个,因此很容易就能想到,只要有了头指针我们就能很容易的对链表进行各项操作。

于是我们可以继续写代码了:

int main(){
    //创建上图的链表
    node *head;//一个头指针。用来指向这个链表的第一个节点
    node *f=new node;//对应上图第一个节点first node,这种奇葩命名法不是我要让你们学会的,另我使用了new而不是malloc主要是因为惰性
    node *s=new node;//对应上图第二个节点second node
    node *t=new node;//对应上图第三个节点third node
    f->data=8;//第一个node的值
    f->next=s;//第一个节点next指针指向第二个节点
    s->data=7;//第二个node的值
    s->next=t;//第二个节点next指针指向第三个节点
    t->data=9;//第三个节点值
    t->next=NULL;//从上图得知第三个节点后没有节点了,所以指向NULL,通常称这个节点为尾节点
    head=f;//头指针指向第一个节点,至于为什么前面已经说了//打印这个链表里面储存的元素
    std::cout<<"链表数据:"<<"\n";
   node *print_ptr=head;//为什么这里要new一个print_ptr?因为我们可能还要利用head进行其他操作,如果直接用head进行下面的操作,就意味着head指向的位置已经改变了
   while(print_ptr!=NULL){
           std::cout<<print_ptr->data<<"\n";//通过头结点迭代打印每个节点的值
           print_ptr=print_ptr->next;//更新,让当前指针指向下一个节点
   }
   //输出节点的个数,虽然我们已经知道了是3个
   node *length_ptr=head;//同上面的
   print_ptrint k=0;
   while(length_ptr!=NULL){
           k++;length_ptr=length_ptr->next;
   }
   std::cout<<"链表节点个数:"<<"\n"<<k<<"\n";//插入一个节点,这里我选择在第一个节点与第二个节点之间插入一个新节点ins_node
   node *ins_node=new node;//为即将插入的节点从堆上分配点内存
   ins_node->data=14;//赋值
   ins_node->next=s;//让新节点的next指向第二个节点
   f->next=ins_node;//然后让第一个节点的next指向新节点,这就完成了插入//删除之前插入的节点
   ins_node=f->next;//让第一个节点next指向新插入的节点,这里你可能会感到疑惑,我建议你画图或者再看看上面的图就能理解,当然你也可以看下面
  f->next=ins_node->next;//第一个节点的next指向新节点的next,因为新节点的next相当于指向了第二个节点,所以这里也等价于第一个节点指向第二个节点f->next=f-next->next
   system("pause");
}

上面就完成了使用尾插法创建的一个链表及其简单操作包括创建/输出/插入/删除,不过如你所见它也存在许多不足,比如命名的拙计,new后没有delete,以及全部在main中执行没有考虑使用函数等等缺陷,不过这没关系,因为我们会一步步修改最终让他成为一个不错的链表

可能你关于上面插入与删除你没有搞清楚,这里我再特意讲一下

上图我们需要把储存14这个数据的node插入到一和二之间,于是我们就需要更改next指针,所以之前f->next=s;就不能用了, 你可能会想到让第一个指向新节点,然后再让新节点指向第三个,如:

f->next=ins_node;
ins_node->next=f->next;

事实通常证明第一感觉是错误的,仔细看看上面代码你就会发现加入f->next=ins_node,那么第二条就相当于ins_node->next=ins_node;它指向了自己!所以我们需要反过来思考,先让新节点指向第二个,然后再让第一个指向新节点,就如上面的代码了,至于删除我没有弄出图片,我只是简单讲一下,删除是直接让第一个节点的next指向需要删除的节点,然后再让第一个节点的next指向需要删除的节点的next,你可能会思考为什么不直接让第一个节点next指向第二个呢?这个疑问你可以自己解答比较好

动态单链表实现

到这里一个简单的链表就已经实现了,但是我们还需要继续改进,因为我们有时候不知道每个节点储存的数据,所以我们就需要一个动态链表了,下面这个将实现把用户输入的数据以链式结构储存,也就是动态链表

#include <iostream>

struct node
{
    int data;
    struct node *next;
};


node *create_linklist();
void print_linklist(node *head);

node *create_linklist(){
    node *head=new node;
    node *new_node,*current;//一个新节点作为当前节点
    current=head;//头结点复制给当前节点
    int k;
    printf("输入节点个数:");
    scanf("%d",&k);
    for (int i = 0; i < k; ++i)
    {
        new_node=new node;
        if(i==0)//这里也就是创建第一个节点的情况
        {
            head=new_node;//把头指针指向第一个节点
        }
        printf("输入节点数据:");
        scanf("%d",&new_node->data);
        current->next=new_node;//注意这里由于创建了一个新节点,而当前节点还是开始的head的那个位置,所以就需要更新一下,让当前节点next等于new_node的位置
        new_node->next=NULL;//当前节点的next=NULL表示当前节点就是最后一个节点了
        current=new_node;//然后把new_node节点复制给当前节点,以便继续后面的节点添加
    }
    return head;
}

void print_linklist(node *head)//参数传入一个头指针用来指向第一个节点
{
    node *phead=head;
    while(phead!=NULL)
    {
        printf("%d", phead->data);
        phead=phead->next;
    }
}

int main(){
    node *h=create_linklist();
    print_linklist(h);
    system("pause");
}

双向链表实现

再想想上面图片,下面要介绍的就是双向链表,双向链表与单项链表的区别就在于它有一个指向前一个节点的指针,于是我们就应该定义这样的结构体

typedef struct NODE
{
	int data;
	struct NODE *next;
	struct NODE *pre;
}node;

由于双向链表不可避免有些操作需要从后向前遍历,于是我们就应该添加一个概念,尾指针,也就是指向尾节点的指针,如下就实现了一个双向链表,它有三个节点abc,并有两种输出方式

#include <iostream>

typedef struct NODE
{
	int data;
	struct NODE *next;
	struct NODE *pre;
}node;

int main(){
	node *a=new node,*b=new node,*c=new node;
	node *head=a;
	node *tail=c;
	a->data=9;
	a->next=b;
	a->pre=NULL;

	b->data=17;
	b->next=c;
	b->pre=a;

	c->data=6;
	c->next=NULL;
	c->pre=b;
	//输出
	/*node *print_head=head;
	while(print_head!=NULL){
		std::cout<<print_head->data<<"\n";
		print_head=print_head->next;
	}*/
	/*node *print_head=tail;
	while(print_head!=NULL){
		std::cout<<print_head->data<<"\n";
		print_head=print_head->pre;
	}*/
	system("pause");
}

双向链表的难点不是创建输出而是插入与删除,我没有制作图片,所以这需要读者认真去思考一下,建议画图,也很容易理解,下面代码是在上面创建了abc的基础上实现的在ab间插入一个k,然后再删除它

	//插入
	node *k=new node;
	k->data=698;
	k->pre=a;
	k->next=a->next;
	k->next->pre=a;
	a->next=k;
	//删除
	k->pre->next=k->next;
	k->next->pre=k->pre;

循环单链表

循环链表我不考虑讲,因为它就是把尾巴节点指向了头节点从而形成一个环,所以说循环链表不叫loop linked list而叫circular linked list

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [数据结构]C语言栈的实现

    有始有终,所以我准备把各种数据结构都讲一次,栈也分顺序存储和链式储存,这里我们选择链式存储来讲,顺序存储没有难度(链式其实也是)

    racaljk
  • Julia体验 语言基础

    以前听说过Julia,不过那时候官网还处于时不时宕机状态,最近Julia发布了1.0 released版本到处都是它的资讯,官网良心自带简体中文,趁着热度我也来...

    racaljk
  • Leetcode 283. Move Zeroes 移动数组中的零 (数组,模拟)

    已知数组nums,写一个函数将nums中的0移动到数组后面,同时保持非零元素的相对位置不变。比如已知nums=[0,1,0,3,12],调用你写的函数后nums...

    racaljk
  • 剑指offer - 反转链表 - JavaScript

    借助栈的后入先出的顺序,可以将顺序列表逆序。不过这不是原地反转,当然题目也没有要求。

    心谭博客
  • 用js来实现那些数据结构13(树01-二叉搜索树的实现)

      前一篇文章我们学会了第一个非顺序数据结构hashMap,那么这一篇我们来学学树,包括树的概念和一些相关的术语以及二叉搜索树的实现。唉?为什么不是树的实现,不...

    zaking
  • 最短路问题与标号算法(label correcting algorithm)研究(3)

    本章将围绕Label Correcting Algorithms展开。首先,3.1小节介绍了最短路径最优性条件,这些条件允许我们评估一组距离标签是否达到最优,以...

    用户1621951
  • 最短路问题与标号算法(label correcting algorithm)研究(5)

    这是全文第三章label correcting algorithm的第三节。本章围绕Label Correcting Algorithms展开。前两节我们介绍了...

    用户1621951
  • 一篇文章搞懂红黑树的原理及实现2-3-4 Tree(2-3-4树)红黑树左倾红黑树的删除操作删除红黑树最小节点删除任意节点总结

    二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找...

    desperate633
  • winform如何保持TreeView节点展开和折叠的状态

    转载:http://blog.sina.com.cn/s/blog_6abcacf5010138q5.html

    跟着阿笨一起玩NET
  • 一步一步教你从零开始写C语言链表——构建一个链表

    今天小编给大家带来c语言难点--链表的讲解,一步一步教你从零开始写C语言链表---构建一个链表。

    诸葛青云

扫码关注云+社区

领取腾讯云代金券