首页 > 操作系统 >

带头结点与不带头结点的单链表初始化

电脑杂谈　发布时间：2019-08-01 20:08:55　来源：网络整理

不带头结点的单链表_结点链表_时间结点与节点

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);

不带头结点的单链表对于第一个节点的操作与其他节点不一样，需要特殊处理，这增加了程序的复杂性和出现bug的机会，因此，通常在单链表的开始结点之前附设一个头结点。

不带头结点的单链表_时间结点与节点_结点链表

带头结点的单链表，初始时一定返回的是指向头结点的地址，所以一定要用二维指针，否则将导致内存访问失败或异常。

在单向链表（c++实现）中，链表的最后一个节点的nex指针指向null，而所谓的循环单向链表即是指链表的最后一个节点的next指针指向首节点(注意不是头节点，头节点是方便链表操作而存在的结构体变量)。举例说明，例如i,m,n是三个相邻的结点，假设经过若干步操作，已经把结点i之前的指针调整完毕，这些结点的next指针都指向前面一...。initlist 初始化循环链表,开辟一个空间作为头结点,并让l l- next先让它指向自己,令链表循环起来. listinsert 向循环链表里面插入数据包括编号和密码 , displist 以定义的头结点为第一个数,输出循环链表.josephus 主要用于解决约瑟夫环问题,首先调用initlist 建立循环链表,再调用listinsert 插入数据,再调用displist 把储存的数据输出来.定义两个指针s和q,再定义count作为计数器,此时需要任意输入一个正整数x作为初始报数上限值,当计数器count x时就把该指针所指向的数据输出并把该数据赋给x,作为新的报数上限值.然后删除该结点,s和q的主要作用是在把输出数据之后的结点删除.如此循环,直到还剩最后一个结点,同时定义a[i],b[i]用来储存编号和密码。

因为不带头结点声明Node *head 时，C编译器将其自动初始化为NULL，于是根本不需要调用InitList(head); 也即不带头结点的初始化是个伪操作。而带头结点的初始化在堆开辟了一段内存，需要修改head指针变量指向的地址(即head的值)，所以要修改head的值，必须传保存head变量的地址(即二维指针)。而直接调用CreatList(head);相当于传head变量的值，函数修改的是head的副本，无法真正改变head的值。

注：这里可以将head指针看成一个变量(不管它保存的是地址)，就比较好理解了。

数组指针是指向数组首元素的地址的指针，其本质为指针（这个指针存放的是数组首地址的地址，相当于2级指针，这个指针不可移动）。传址调用：是双向的，把实参的地址传给形参，形参就指针了实参变量不带头结点的单链表，因此形参的改变会影响实参。但receiver仍然是self本身，这点需要注意，因为当我们想通过[super class]获取超类时，编译器只是将指向self的id指针和class的sel传递给了objc_msgsendsuper函数，因为只有在nsobject类找到class方法不带头结点的单链表，然后class方法调用object_getclass()，传入参数是指向self的id指针，所以我们得到的永远都是self的类型。

另外，对于函数的形参是指针时，只要该参数不在左边（即都是右值操作），二维指针(形参)就可以简化为一维指针。如上面带头结点的尾插简化版本。

结点链表_时间结点与节点_不带头结点的单链表