精华内容
下载资源
问答
  • 单链表的创建

    2020-03-30 12:13:27
    单链表的创建 单链表的创建一般用到结构体 struct node { int data; node* next; } node* create() { int i=0; //链表节点计数器 node* head,* p,*q;//head头节点,p为循环中的临时节点,q末节点 int x=0; head=...

    单链表的创建

    单链表的创建一般用到结构体

    struct node
    {
        int data;
        node* next;
    }
    node* create()
    {
        int i=0; //链表节点计数器
        node* head,* p,*q;//head头节点,p为循环中的临时节点,q末节点
        int x=0;
        head=(node*) malloc(sizeof(node));
        q=(node*)malloc(sizeof(node));//因为可能用到所以提前开辟好内存
        while(1)
        {
            printf("请输入x的值\n");
            scanf("%d",x);
            if(x==0)
            {
                break;
            }
            p=(node*)malloc(sizeof(node));
            p.data=x;
            if(++i==1)
            {
                head->next=p;//个节点要绑定在头结点上
            }
            else
            {
                q->next=p; //之后节点要绑定在末节点上
            }
           q=p;//p临时节点重新变成末节点, 被q指向
        }
        q->next=NULL;   //末节点next置空
         return head;
    }
    
    展开全文
  • 单链表的创建--从零开始

    万次阅读 多人点赞 2018-09-10 13:01:28
    上学期临近期末时候用Word写了一篇链表详解,今天突然想到自己一直在搞算法题,很长时间没有用链表了。试着在纸上写了几步,发现回想起来竟然有些吃力,这里把上学期写链表详解贴上来mark一下,顺便以此作为数据...

    2021.2.14更新
    结合很多小伙伴的困惑,博主录制了一个视频讲解,如果大家感兴趣,欢迎跳转到我的b站视频《单链表的创建—从零开始》(P.S.这是我录制的第一个视频,因为是在晚上,怕打扰到别人,所以说话声音较小;又没什么剪辑经验,故而视频质量可能不高。希望大家不要介意hh)


    上学期临近期末的时候用Word写了一篇链表详解,今天突然想到自己一直在搞算法题,很长时间没有用链表了。试着在纸上写了几步,发现回想起来竟然有些吃力,这里把上学期写的链表详解贴上来mark一下,顺便以此作为数据结构笔记的第一篇。


    学习链表需要了解的基本知识点

    首先,想要熟练使用链表,就要知道两大类基本知识点:
    1. 指针 2.结构体
    (如果对这两个知识点有疑惑请百度一下,没有什么问题是百度一下解决不了的,如果有,就百度两下)

    结构体定义部分:
    struct node{int num;struct node *next };
    带头节点的链表示意图:
    在这里插入图片描述
      上图就是链接后每个节点的状态,单链表每个节点保存下一个节点的地址(struct node *next),环环相扣,因此称之为链表。知道这两个知识点后,我们就可以开始写链表了。首先是定义结构体,struct node{…}; 千万不要忘了结构体定义后的分号!


    关于typedef的问题

    typedef是用来为复杂的声明定义简单的别名,比如typedef struct node}{…}Lnode;
    这句话的意思即使用Lnode来代替struct node这句声明。
    typedef的好处是什么呢?
    我认为有如下:
      首先, 在复杂的程序里,很容易打错一些字,比如把struct打成stuct,把struct node 打成struct ndoe blablabla~,用typedef可以避免这种错误发生。
      其次, 简单省事,struct node *head; 和 Lnode *head;都是定义头节点的作用,但显然后者更加便捷。(当然不怕麻烦并且足够自信的话用第一个也完全没问题)


    关于创建单链表(createlink)

      如果想得到创建后的链表,我们显然需要知道他的头在哪。因此在Createlink()函数中,需要返回head(也就是这条链子的头部),这样顺着头我们就可以一直找到链表的每一个元素,直到尾部(p若为最后一个链结的话,那么p->next==NULL)。
    在这里插入图片描述
      因为需要返回head这个指针,因此需要这样写(可能有小伙伴会有疑问:都说通过传递指针给函数就可以改变实参的值,还有必要返回指针吗?有兴趣的读者可以跳转到我的这篇博客:关于传递指针与传递引用作参数的测试

    struct node *createlink()
    {
    	//.....这些是创建的过程
    	return head;
    }
    

    返回值类型搞定之后,我们便可以进入创建链表的环节。

    单链表分为两种:
    (1)不带头节点的链表:此种链表的head即保存第一个数据,访问时从head开始。不利于删除或者添加指定位置数据的操作。
    (2)带头节点的链表:此种链表保存数据是从head->next开始的,head中并未保存有数据,访问时自然head->next开始,优点就是方便操作。


    这里先以不带头节点的链表的创建为例
    (我采用创建链表的方法叫做尾插法——每新建立一个节点,都把它放到现有链表的尾部)
      首先,我们需要有一个结构体指针来保存头节点,方便于之后的使用,所以:struct node *head;
      注意:这里的head是不能变的,,不变的意思不是他的值不变,而是他永远固定在链表的首位,作为链表的头部,方便之后的索引。
      因此,当我们每新加入一个元素时,不是直接更新head的值,而是在链表的尾部插入一个新的结点。不妨用一个结构体指针pnew来记录新加入的值,通过旧节点pend与新节点的相连来构造一个链表,示意图如下:
    这里写图片描述
      显然,pend所指向的单位,实际就是上一次的pnew(可以理解为,pnew作为新元素被成功加入到链表之后,它便变成了旧节点,两个字概括为:更替
      欸?是不是还有一个变量忘了声明?没错,那就是整型n,用来表示新加入的值。这样我们便可以通过输入n并且给节点赋值,只要输入不为-1,那么继续进行输入,否则终止循环。

    不带头节点单链表代码的实现:
      首先,我们定义head,最初的时候链表还没有添加元素,因此head=NULL;
      然后,输入一个元素代表将要添加的值。判断元素是否符合条件(这里以元素>=0为条件),如果满足,就进入添加环节。

    scanf("%d",&num);
    while(num>=0)
    {
    //操作
    	scanf("%d",&num);
    }
    

    在循环中,因为要添加值,所以要先为pnew分配内存,这样才能对pnew进行赋值操作。

    pnew=(struct node*)malloc(sizeof(struct node));
    pnew->num=num;
    pnew->next=NULL; //新创建的指针的下一个位置还没有定
    

      因为我们想要创建不带头节点的单链表,因此如果是第一次添加值(第一次添加的判断是,如果head指向NULL,证明还未加入元素),那么head就应该指向pnew的位置,然后pnew(也就是head)的位置变为旧位置pend。

    if(head==NULL)
    {
    	head=pnew;
    	pend=head;
    }
    

      如果不是第一次添加了,那么此时存放旧地址的就应该是pend,观察上图,只需要如下操作进行连接就可以了:

    else{
    	pend->next=pnew;
    	pend=pnew;//一定注意,操作的位置是内存
    	//因此进行上面一步之后,pend->next这块内存已经有了指向
    }
    

    这样,便成功创建了不带头节点的单链表。

    完整代码

    scanf("%d",&num);
    while(num>=0)
    {
    	pnew=(struct node*)malloc(sizeof(struct node));
    	pnew->num=num;
    	pnew->next=NULL; //新创建的指针的下一个位置还没有定
    	if(head==NULL)
    	{
    		head=pnew;
    		pend=head;
    	}
    	else
    	{
    		pend->next=pnew;
    		pend=pnew;
    	}
    	scanf("%d",&num);
    }
    

    带头节点单链表代码的实现:
      带有头节点的单链表创立,只需稍微改变代码即可。
      既然是带有头节点,那么头节点里肯定是不需要赋值的,因此在创建时,我们直接最开始就让头节点作为旧节点,这样头节点就可以不用被赋值了。

    head=(struct node*)malloc(sizeof(struct node));
    head->next=NULL;
    pend=head;
    scanf("%d",&n);
    While(n!=-1)
    {
    	pnew=(struct node *)malloc(sizeof(struct node));	//这里一定要为pnew开辟内存!
    	//想象一下,你无法int *a;后直接赋值a=3;必须先分配内存,同理。
    	pnew->num=n;
    	pnew->next=NULL;//新节点指向空,因为后面还没有元素加入
    	pend->next=pnew;	//旧节点的指针指向新节点
    	pend=pnew;		//新节点变为旧节点
    	scanf(%d”,&n);
    }
    

    展开全文
  • 单链表的创建算法

    万次阅读 多人点赞 2016-03-26 23:34:51
    单链表的创建算法  当一个序列中只含有指向它的后继结点的链接时,就称该链表为单链表。  单链表的示意图如下:    Head指针为单链表的头指针,单链表L:L既是单链表的名字,也是其头指针。链表中的最后一个...

                                                                            单链表的创建算法

           本文根据:清华大学出版社《数据结构与算法(C语言版)(第3版)》整理,详细请见书本。

           当一个序列中只含有指向它的后继结点的链接时,就称该链表为单链表。

           单链表的示意图如下:

                                               
          Head指针为单链表的头指针,单链表L:L既是单链表的名字,也是其头指针。链表中的最后一个结点的指针域定义为空指针(NULL)。
          单链表的定义:

     struct Node
     {
       ElemType data;
       struct Node *next;
     };
     typedef struct Node LNode;
     typedef struct Node *LinkedList;
              单链表有带头结点和不带头结点之分。

           上图为没有头结点的单链表,下图为带有头结点的单链表:

                                             

       1.单链表的初始化,即建立一个空链表。

      //不带头结点的单链表的初始化
      void LinkedListInit1(LinkedList L)
      {
        L=NULL;
      }
      //带头结点的单链表的初始化
      void LinkedListInit2(LinkedList L)
      {
        L=(LNode *)malloc(sizeof(LNode));
        if(L==NULL)
        {
          printf("申请空间失败!");
          exit(0);
        }
        L->next=NULL;
      }

        2.单链表的求表长操作

          单链表的求表长操作需要设定当前指针p和一个计数器j,初始时p指向链表中的第一个结点,p每向下移动一个结点时,j就加1,直到到达p链表的尾部。带头结点的链表,链表长度不包括头结点。
      //带头结点的单链表求表长
      int LinkedListLength(LinkedList L)
      {
        LNode *p;            //p需要声明为LNode类型
        p=L->next;
        int j=0;
        while(p!=NULL)
        {
          j++;
          p=p->next;         //将p向下移动一个结点
        }
        return j;
      }

        3.单链表获取第i个结点元素的操作

         设定p为当前结点,初始时p指向链表的第一个结点,然后向下移动i,此时p所指向的元素就是需要查找的第i个结点元素。

      //带头结点的单链表取元素操作
      LinkedList LinkedListGetINode(LinkedList L, int i)
      {
        LNode *p;
        p=L->next;
        int j=1;
        while((p!=NULL)&&(j<i))
        {
          p=p->next;
          j++;
        }
        return p;
      }

        4.单链表的定位操作

        查找元素e第一次出现的位置。从链表的第一个结点开始,判断当前结点的值是否等于e,等于则返回该结点的指针,否则继续向后查找,直至到达链表的最后。
      //带头结点的单链表定位操作
      LNode LinkedListLocateE(LinkedList L, ElemType e)
      {
        LNode *p;
        p=L->next;
        while((p!=NULL)&&(p->data!=e))
        {
          p=p->next;
        }
        return p;
      }

        5.单链表的插入操作

        在结点p之前插入一个新的结点q:对于不带头结点的单链表,结点p的位置有所不同,插入操作有以下两种情况:
        1)在链表的表头插入:
           (1)创建一个新的结点q。
           (2)将此结点的数据域赋值为e,并将它的next指针指向第一个结点,即L。
           (3)将L修改为指向新的结点q。
           操作示意图如下:

                                        
        2)在链表的中间插入
           (1)创建一个新的结点q。
           (2)将此结点的数据域赋值为e,并将它的next指针指向p。
           (3)查找到p的前驱结点pre。
           (4)将pre的next指针指向新创建的结点q。
          操作示意图如下:
                                                 

        //不带头结点的单链表的插入操作
        void LinkedListInertQE1(LinkedList L, LinkedList p, ElemType e)
        {
          q=(LNode *)malloc(sizeof(LNode));        //创建一个新的结点q
          if(q==NULL)
          {
            printf("申请空间失败!");
            exit(0);
          }
          q->data=e;
    
          if(p==L)   //在表头插入
          {
            q->next=L;
            L=q;
          }
          else      //在表的中间进行插入
          {
            pre=L;
            while((pre!=NULL)&&(pre->next!=p))           //寻找p的前驱
               pre=pre->next;
    
            q->next=pre->next;
            pre->next=q;
          }
        }
    
        //带头结点的单链表的插入操作
        void LinkedListInertQE2(LinkedList L, LinkedList p, ElemType e)
        {
          q=(LNode *)malloc(sizeof(LNode));        //创建一个新的结点q
          if(q==NULL)
          {
            printf("申请空间失败!");
            exit(0);
          }
          q->data=e;
    
          //插入新的结点
          pre=L;
          while((pre!=NULL)&&(pre->next!=p))           //寻找p的前驱
            pre=pre->next;
    
          q->next=pre->next;
          pre->next=q;
        }

          6.单链表的删除操作

           删除链表中的某个元素e,如果e在链表中出现不止一次,将删除第一次出现的e,否则什么也不做。
           用p找到元素e所在的结点:
            1)p是链表中的第一个结点
                (1)将L指向p->next。
                (2)释放p。
             示意图如下:

                                           

             2)p是链表中的其他结点
                (1)找到p的前驱结点pre。
                (2)将pre->next指向p->next。
                (3)释放p。
             示意图如下:

                                                                     

         //不带头结点的单链表的删除操作
         void LinkedListDeleteQE1(LinkedList L, LinkedList p, ElemType e)
         {
            pre=L;
            while((pre!=NULL)&&(pre->next->data!=e))      //查找元素e的前驱
                pre=pre->next;
            p=pre->next;
    
            if(p!=NULL)                //找到需要删除的结点
            {
              if(p==L)                 //删除的是第一个结点
                L=p->next;
              else                     //删除的是其他结点
                pre->next=p->next;
              free(p);
            }
         }
         //带头结点的单链表的删除操作
         void LinkedListDeleteQE2(LinkedList L, LinkedList p, ElemType e)
         {
            pre=L;
            while((pre!=NULL)&&(pre->next->data!=e))      //查找元素e的前驱
                pre=pre->next;
            p=pre->next;
    
            if(p!=NULL)                //找到需要删除的结点
            {
              pre->next=p->next;
              free(p);
            }
         }

            7.单链表的创建操作

            单链表的创建方法有两种:头插法和尾插法。
            头插法是将新增结点插入第一个结点之前,示意图如下:

                                              
            尾插法是将新增结点插入最后一个结点之后,示意图如下:

                                                           

        //用头插法创建带头结点的单链表
        void LinkedListCreateHeadL(LinkedList L, ElemType a[n])
        {
          L=(LNode *)malloc(sizeof(LNode));
          if(L==NULL)
          {
            printf("申请空间失败!");
            exit(0);
          }
          L->next=NULL;
    
          for(i=0; i<n; i++)
          {
            p=(LNode *)malloc(sizeof(LNode));
            if(p==NULL)
            {
              printf("申请空间失败!");
              exit(0);
            }
    
            p->data=a[i];
            p->next=L->next;
            L->next=p;
          }
        }
        //用尾插法创建带头结点的单链表
        void LinkedListCreateTailL(LinkedList L, ElemType a[n])
        {
          L=(LNode *)malloc(sizeof(LNode));
          if(L==NULL)
          {
            printf("申请空间失败!");
            exit(0);
          }
          L->next=NULL;
          tail=L;         //设置尾指针,方便插入
    
          for(j=0; j<n; j++)
          {
            p=(LNode *)malloc(sizeof(LNode));
            if(p==NULL)
            {
              printf("申请空间失败!");
              exit(0);
            }
    
            p->data=a[j];
            p->next=NULL;
            tail->next=p;
            tail=p;
          }
        }

          8.单链表的合并操作

          首先设置3个指针pa、pb、pc, pa和pb分别指向链表La与Lb的当前待比较插入结点,pc指向链表Lc的最后一个结点。当pa->data≤pb->data时,将pa所指的结点插入到pc后面,否则就将pb所指的结点插入到pc后面。最后,当有一个表合并完,将另一个表剩余的结点全插入到pc。

        //带头结点的单链表合并操作
        void LinkedListMergeLaLb(LinkedList La, LinkedList Lb, LinkedList Lc)
        {
          pa=La->next;
          pb=Lb->next;
          Lc=La;          //借用表La的头结点作为表Lc的头结点
          pc=Lc;
    
          while((pa!=NULL)&&(pb!=NULL))
          {
            if(pa->data<=pb->data)
            {
              pc->next=pa;
              pc=pa;
              pa=pa->next;
            }
            else
            {
              pc->next=pb;
              pc=pb;
              pb=pb->next;
            }
          }
          if(pa!=NULL)
            pc=pa->next;
          else
            pc=pb->next;
    
          free(pb);    //将Lb的表头结点释放
        }

     附录:

           程序实例:尾插法创建单链表

           首先在VS2010中新建Win32 控制台应用程序的项目LinkedList,结果如下:

                                                   

           LinkedList.cpp : 定义控制台应用程序的入口点。

    // LinkedList.cpp : 定义控制台应用程序的入口点。
    
        #include "stdafx.h"
    
        #include<stdio.h>
        #include<stdlib.h>
        typedef struct node
        {
          int data;
          struct node *next;
        }*LinkedList;
    
        LinkedList LinkedListCreateTailL(int a[8])
        {
          LinkedList p, L, tail;
          int i=0;
          L=(struct node*)malloc(sizeof(struct node));
          tail=L;
    
          for(i=0; i<8; i++)
          {
            p=(struct node*)malloc(sizeof(struct node));
            p->data=a[i];
            tail->next=p;
            tail=p;
          }
          tail->next=NULL;
          return L;
        }
    
        void LinkedListPrint(LinkedList L)
        {
          LinkedList p;
          p=L->next;
          while(p!=NULL)
          {
            printf("%d ",p->data);
            p=p->next;
          }
        }
    
        void main()
        {
          int a[8], i;
          LinkedList L;
          printf("请输入8个列表元素,以回车结束:\n");
    	  for(i=0; i<8; i++)
          {
            scanf("%d", &a[i]);
          }
    
          L=LinkedListCreateTailL(a);
          LinkedListPrint(L);
        }
    
           Ctrl+F5执行以上cpp文件,程序运行截图:

                                               

    展开全文
  • 单链表的创建以及操作 1.单链表的概念 : 单链表的存储结构为线性非连续型,相比于数组极大的减少了空间的利用率,通过指针指向下一个结点让链表最大的利用了空间 以下是链表的实现原理: 链表的每个结点都包含一个...

    单链表的创建以及操作

    1.单链表的概念 :
    单链表的存储结构为线性非连续型,相比于数组极大的减少了空间的利用率,通过指针指向下一个结点让链表最大的利用了空间

    以下是链表的实现原理:

    在这里插入图片描述
    链表的每个结点都包含一个数据域和一个指针域
    创建链表的步骤:
    1.先创建出结构体变量

    struct Node
    {
      int data;   //数据域
      struct Node* next; //指针域
    }

    2.创建表头

    struct Node* creatList()
    { 
       //定义一个指针变量通过动态内存申请将指针变量变为结点 
      struct Node* headNode=(struct Node*)malloc(sizeof(struct Node));
      headNode=NULL;   //建立一个空表
      return headNode; 
    }
    

    3.创建结点

    struct Node* creatNode(int data)
    {  
      //为新结点动态内存申请空间
      struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
      newNode->data=data;   //将形参传递的数据传入新结点内
      newNode->next=NULL;   //将新结点的指针域为空
      return newNode;
    }
    

    4.打印链表
    打印以headNode为头结点的链表

    void printList(struct Node* headNode)
    { 
      //因为第一个结点内不存放数据,所以从第二个结点开始打印
      //定义一个新的指针变量指向第二个结点
      struct Node* pMove=headNode->next;
      while(pMove!=NULL)
      {
        printf("data=%d\n",pMove->data);
        pMove=pMove->next;
      }   
      printf("\n");
    }
    

    链表功能的实现

    链表的创建操作已经完成了,现在我们来完善链表的功能
    链表的功能包括了增,删, 查 ,改

    1.插入结点(表头法)
    在这里插入图片描述

    void InsertNode(struct Node* headNode)
    { 
       //调用创建结点函数来创建新结点
      struct Node* newNode=creatNode(data);
      newNode->next=headNode->next;
      headNode->next=newNode;
    }
    

    通过图片不难看出头插法是如何实现的

    2.插入结点(尾插法)
    在这里插入图片描述

    void InsertNode(struct Node* headNode)
    { 
      struct Node* newNode=creatNode(data);
      //定义一个临时变量指向表头
      struct Node* temp=headNode;
      if(headNode==NULL)   //如果头结点为空
      {  
        //如果headNode为空则将newNode设为第一个新结点
       headNode=newNode;
       newNode->=NULL;
      }
      else
      {  
         //最终让temp指向尾结点
        while(temp->next != NULL)
        {  
          temp=temp->next;
        }
        //将尾结点temp的next设为newNode,即将newNdoe设为尾结点
        temp->next=newNode;
      }
    }
    

    3.查找结点

    void SeekNode(struct Node* headNode,int data)
    { 
      //创建一个指针变量指向第二个结点
      struct Node* pMove=headNode->next;
      if(pMove==NULL)
      {
        printf("数据为空,无法查找!\n");
      }
      while(pMove != NULL)
      {
         if(pMove->data == data)
         {
           printf("数据存在!\n");
           printf("data=%d\n",pMove->data);
         }
         pMove=pMove->data;
      }
         printf("\n");
    }
    

    4.指定位置删除结点

    void DeletedNode(struct Node* headNode,int posData)
    {
    	struct Node* posNode = headNode->next;
    	struct Node* posFrotNode = headNode;
    	if (posNode == NULL)
    	{
    		printf("数据为空,无法删除!\n");
    	}
    	while (posNode->data != posData)
    	{
    		posFrotNode = posNode;   //将指定位置的前面到达指定位置
    		posNode = posFrotNode->next;
    		if (posNode == NULL)
    		{
    			printf("未找到指定位置,无法删除!\n");
    		}
    	}
    	posFrotNode->next = posNode->next;
    	free(posNode);
    }
    
    展开全文
  • C++单链表的创建和二叉树的创建 链表的创建 struct ListNode { int val; ListNode* next; ListNode(int x) :val(x), next(NULL) {} }; ListNode* creat() { ListNode* head, * p; int val[] = { 1,2,3,4,5,6 };...
  • 学习目标:轻松学会单链表的创建 学习时间:2020.10.20 星期二 12点-8点 学习内容:本次构造单向、不带头、非循环的单链表 顺序表:物理上是连续的,逻辑上也是连续的。 单链表:物理上不一定是连续的,单逻辑上是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,751
精华内容 1,900
关键字:

单链表的创建