单链表带头结点不带头结点

2024-04-24 15:38
文章标签 单链 结点 带头

本文主要是介绍单链表带头结点不带头结点,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Node *head;  //声明头结点

带头结点初始化

void InitList(Node **head){

     *head=(Node *)malloc( sizeof(Node));
     (*head)->next=NULL;
}

带头结点尾插入,统一操作
方式一:
void CreatList(Node **head){
     Node *r=*head,*s;
     int a;
     while(scanf("%d",&a)){
          if(a!=0){
               s=(Node *)malloc(sizeof(Node));
               s->value=a;
               r->next=s;
               r=s;    
          }
          else{    
               r->next=NULL;
               break;    
          }
     }
}
调用CreatList(&head);

方式二:
void CreatList(Node *head){
     Node *r=head,*s;
     ... //下面的都一样
}
调用CreatList(head);

------------------------------------------------------------------------------------------------------

不带头结点初始化
方式一:
void InitList(Node **head){
     *head=NULL;
}
调用InitList(&head);
方式二:
void InitList(Node *head){
     head=NULL;
}
调用InitList(head);
不带头结点尾插入,第一个节点与其他节点分开操作
void CreatList(Node  **head){
     Node *p,*t;         /*p工作指针,t临时指针*/
     int a,i=1;
     while(scanf("%d",&a)){
          if(a!=0){
               t=(Node *)malloc(sizeof(Node));
               t->value=a;
               if(i==1){
                    *head=t;    
               }
               else{
                    p->next=t;
               }
               p=t;
          }
          else{    
               p->next=NULL;
               break;    
          }
          i++;
     }
}
调用CreatList(&head);

一、两者区别:
     1、不带头结点的单链表对于第一个节点的操作与其他节点不一样,需要特殊处理,这增加了程序的复杂性和出现bug的机会,因此,通常
          在单链表的开始结点之前附设一个头结点。
     2、带头结点的单链表,初始时一定返回的是指向头结点的地址,所以一定要用二维指针,否则将导致内存访问失败或异常。
     3、带头结点与不带头结点初始化、插入、删除、输出操作都不样,在遍历输出链表数据时,带头结点的判断条件是while(head->next!=NULL),
          而不带头结点是while(head!=NULL),虽然头指针可以在初始时设定,但是如1所述,对于特殊情况如只有一个节点会出现问题。
二、为什么不带头结点初始化有2种方式,而带头结点只有1种方式呢?
     因为不带头结点声明Node *head 时;C编译器将其自动初始化为NULL,于是根本不需要调用InitList(head);也即不带头结点的初始化
是个伪操作。而带头结点的初始化在堆开辟了一段内存,需要修改head指针变量指向的地址(即head的值),所以要修改head的值,必须传保
存head变量的地址(即二维指针)。而直接调用CreatList(head);相当于传head变量的值,函数修改的是head的副本,无法真正改变head的值。 
     :这里可以将head指针看成一个变量(不管它保存的是地址),就比较好理解了。
三(key)、其实本质上还是传值,传址的问题,只不过指针本身保存的地址,让这个过程变得有点纠结。在函数调用需要修改指针变量的指向(value)时,
 应该传递指针变量的地址(address)。
      另外,对于函数的形参是指针时,只要该参数不在左边(即都是右值操作),二维指针(形参)就可以简化为一维指针。如上面带头结点的尾插
简化版本。

这篇关于单链表带头结点不带头结点的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/932137

相关文章

Go语言构建单链表

package mainimport "fmt"type ListNode struct {Val intNext *ListNode}func main() {list := []int{2,4,3}head := &ListNode{Val:list[0]}tail := head //需要头尾两个指针for i:=1;i<len(list);i++ {//方法一 数组直接构建链表tai

[数据结构]线性表之单链表的类模板实现

类的具体实现如下: /#include"LinearList.h"#include <iostream>#include <cstdlib>using namespace std;template<class T>struct LinkNode //链表节点类{T data;LinkNode<T>* link;LinkNode(LinkNode<T>* ptr=NULL):

带头结点的线性链表的基本操作

持续了好久,终于有了这篇博客,链表的操作需要借助图像模型进行反复学习,这里尽可能的整理并记录下自己的思考,以备后面复习,和大家分享。需要说明的是,我们从实际应用角度出发重新定义了线性表。 一. 定义 从上一篇文章可以看到,由于链表在空间的合理利用上和插入、删除时不需要移动等优点,因此在很多场合下,它是线性表的首选存储结构。然而,它也存在某些实现的缺点,如求线性表的长度时不如顺序存储结构的

逆序和顺序创建单链表

单链表是一种顺序的存储方式,数据结构学的不好,考研又是必考内容,只好从头开始学习,相信不断地积累会有更好的爆发! 首先单链表的创建,单链表是建立在结构体的基础上,要创建单链表首先要建立起一个储存数据的结构体: struct node{int elem;node *next;};elem是数据域,用来存放你要输入的数据,next是指向下个存放数据节点的指针同为node 类型; 下面是

【hdu】I Hate It(线段树,结点修改求区间最大值)

线段树的模板题,还是二分递归。 #include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <vector>#include <queue>#include <set>#include <map>#incl

【hdu】敌兵布阵(线段树,更加结点,区间求和)

最近开始刷线段树,主要围绕notonlysuccess的线段树总结刷。 结点修改还是比较简单的,不需要什么懒惰标记,直接二分递归就可以了。 #include <iostream>#include <cstdlib>#include <cstdio>#include <string>#include <cstring>#include <cmath>#include <vecto

【数据结构初阶】链表分类与双向带头循环链表接口实现

文章目录 1. 链表的分类2. 双向带头循环链表接口实现2. 1 结点声明2. 2 创建链表节点2. 3 初始化链表2. 4 打印链表2. 5 尾插2. 6 判空2. 7 尾删2. 8 头插2. 9 头删2. 10 查找2. 11 在指定位置删除与插入2. 12 销毁 3. 链表接口测试4. 单链表与双链表5. 顺序表与链表 1. 链表的分类 链表的结构非常多样,以下情况组合

单链表核心操作代码

头插法建立单链表 代码: void createListByHead(LinkList &L,int n){LNode *s;//移动指针s int x;//要插入的元素 L = (LinkList)malloc(sizeof(LNode));//创建头结点 L->next=NULL;//初始化头结点 for(int i=0;i<n;i++){scanf("&d",&x);//输入要插入的值

浅谈单链表与双链表的区别

数组的优点 随机访问性强(通过下标进行快速定位) 查找速度快 数组的缺点 插入和删除效率低(插入和删除需要移动数据) 可能浪费内存(因为是连续的,所以每次申请数组之前必须规定数组的大小,如果大小不合理,则可能会浪费内存) 内存空间要求高,必须有足够的连续内存空间。 数组大小固定,不能动态拓展 链表的优点 插入删除速度快(因为有next指针指向其下一个节点,通过改变指针的指向可以方便的增加删除元素)

数据结构——单链表查询、逆序、排序

1、思维导图 2、查、改、删算法 //快慢排序法找中间值int mid_link(Link_t *plink){Link_Node_t *pfast = plink->phead;Link_Node_t *pslow = pfast;int m = 0;while(pfast != NULL){pfast = pfast->pnext;++m;if(m % 2 == 0){pslow