首页 > 其他 > 详细

第一章---线性表之单链表的创建方法1

时间:2021-02-05 10:43:20      阅读:29      评论:0      收藏:0      [点我收藏+]
单链表的创建方法:头插法和尾插法    单链表创建建议带头节点,因为能减少麻烦
按照是否带头节点又分为:带头结点的头插法,尾插法和不带头结点的头插法,尾插法
  1.单链表的结构定义
    typedef int DataType; //给int数据类型起一个别名,叫DataType
    typedef struct Lnode{
      DataType data;
      struct Lnode *next;
    }Lnode,*LinkList;
  2.易混淆的地方
  head头指针只有两个取值,要摸head=NULL表示头结点不存在(空表),要摸head->next=NULL表示头结点存在(链表只有一个头结点
  学完了汇编语言我们知道了指针就是游标,一个可以存储存储器的地址序号的变量就是指针,单独拿出来这个变量他表示的就是一个地址,
  eg:int *a,b;b=3;a=&b;cout<<a<<endl;//会显示b的地址,说明直接使用指针名表示的就是地址
    1.head=NULL,head->next=NULL的区分
      head=NULL表示链表没有任何节点,因为头结点都是NULL了 空表
      head->next=NULL表示链表只有头结点
    2.head=NULL,head->next=NULL应用,可以用来创建不带头结点和带头结点的单链表
  3.头插法和尾插法创建链表的原理 自己多写代码体悟 理解了本质写代码就不用再拘泥于定格了
    本质上都是:用一个游标指针一直指向链表最后一个元素,实现链表的创建
  头插法:输入的链表数据和输出的链表数据方向相反 应用:可以用来对一串数据进行反向输出
    eg:输入:123 头插法输出:321

  

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int DataType; //使int重命名为DataType
DataType flag = 0; //flag是用来判断神魔时候输入数据结束
typedef struct Lnode{
  DataType data; //定义DataType为int ,存储结构为顺序存储
  struct Lnode *next;
}Lnode,*LinkList;


//不带头结点的头插法创建单链表
LinkList create_LinkList(){
  LinkList head,s;
  //head是一个移动的指针,一直指向单链表的头部(是实际输入的尾部)
  //s是一个动态创建的节点指针

  head=NULL; //声明空表,没有头结点
  DataType x;
  cout<<"请输入x的值:";
  cin>>x;
  while(x!=flag){//flag是用来判断神魔时候输入结束的标志
    s=(LinkList)malloc(sizeof(Lnode));
    s->data=x;
    s->next=NULL;
//这步的操作的本质是为了设置第一个s为尾结点 s->next=NULL,只不过先把head赋值NULL,再赋值给s了,和直接s=NULL一样
    head=s; //head指针一直指向尾巴
    cin>>x;
  }
  return head;
//返回指向链表输入尾巴节点的指针
} 

//带头节点的头插法创建链表
LinkList create_LinkList1(){
  LinkList head,p,s;
  p->next=NULL; //设p是头结点
  head=p; //head指针指向头结点
  DataType x;
  cout<<"请输入x的值:";
  cin>>x;
  while(x!=flag){
    s=(LinkList)malloc(sizeof(Lnode));
    s->data=x;
    s->next=head; //第一次的含义:让新增加的第一个节点指向头结点 创建带头结点的单链表
    head=s; //游标指针head指向尾巴
    cin>>x;
  }
  return head; //返回指向链表输入尾巴节点的指针
}

//输出不带头节点的头插法创建的单链表的方法
void out_LinkList(LinkList head){ //采用指针传递参数,共用内存
  LinkList p=head; //让p指向head,保存head,防止修改head了,以后别的方法用head时找不到了
  cout<<"头插法输入和输出数据顺序相反"<<endl;
  while(p->next!=NULL){
     cout<<p->data<<" ";
     p=p->next;
  }
  //因为没有头节点,所以最后一个节点的data也得输出
  cout<<p->data<<end;
}

//输出带头节点的头插法创建的单链表的方法
void out_LinkList(LinkList head){
  LinkList p=head; //保护head指针
   cout<<"头插法输入和输出数据顺序相反"<<endl;
  while(p->next!=NULL)
  {
    cout<<p->data<<" ";
    p=p->next;
  }
  //因为带头节点所以最后一个结点的数据域的数据不用输出(因为头结点的数据域未赋值)
}
 

int main(int argc, char** argv) {

//带头节点

  LinkList head1 = create_LinkList1();

  out_LinkList1(head1);

  cout<<endl;

//不带头结点

    LinkList head = create_LinkList();

  out_LinkList(head);

  return 0;

}














  

第一章---线性表之单链表的创建方法1

原文:https://www.cnblogs.com/nanfengnan/p/14376196.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!