数据结构 ——无头单链表

数据结构 ——无头单链表

一、无头单链表的定义与特性
1、单链表简介
单链表是一种常见的基础数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。无头单链表是单链表的一种变体，其特点是没有明确的头节点，链表的第一个数据节点直接跟在头指针之后。
2、 无头单链表的特点
无头单链表省去了传统单链表头节点的存储空间，这使得在某些情况下可以更高效地使用内存。它直接通过头指针访问第一个数据节点，便于快速迭代整个链表，但同时也意味着在进行某些操作时，如获取链表长度，需要额外的遍历计数步骤。
二、简单操作实现
1、无头单链表示意图




尾插代码实现

2、具体代码实现

//nohead.h
#ifndef NOHEAD_H_
#define NOHEAD_H_
#define NAMESIZE 32
struct score_st
{
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
};
typedef struct noad_st
{
    struct score_st data;
    struct noad_st *next;
}node;
int list_insert(node **,struct score_st *data);
void list_show(node *);
int list_delete(node **);
// int list_find(node *,int);
struct score_st* list_find(node *,int);
void list_destroy(node *);
#endif

//nohead.c
#include<stdio.h>
#include<stdlib.h>
#include "nohead.h"
//首部插入，由于要改变头指针的指向，故需要传二级指针
int list_insert(node **list,struct score_st *data)
{
    node *new;
    new=malloc(sizeof(*new));
    if(new==NULL)   return -1;
    new->data=*data;
    new->next=*list;
    *list=new;
    return 0;
}
void list_show(node *list)
{
    node *cur;
    for(cur=list;cur!=NULL;cur=cur->next)
    {
        printf("%d %s %d %d\n",cur->data.id,cur->data.name,cur->data.math,cur->data.chinese);
    }

}
//考虑到只有一个结点的删除要改变指针的指向，故传二级指针
int list_delete(node **list)
{
    node *cur;
    if(*list==NULL) return -1;
    //cur指向第一个有效结点
    cur=*list;
    //改变头指针指向，使其指向第一个结点的next指针域
    *list=cur->next;
    free(cur);
    return 0;
}
//按值查找
struct score_st* list_find(node *list,int id)
{
    node *cur;
    #if 0
    for(cur=list;cur!=NULL;cur=cur->next)
    {
        if(cur->data.id==id)
        {
            printf("%d %s %d %d\n",cur->data.id,cur->data.name,cur->data.math,cur->data.chinese);
            return 0;
        }
    }
    printf("Can not find!\n");
    return -1;
    #endif
    /*实际工程开发中，只需要返回给用户一个成功找到的数据就行了，
    不需要替用户决定干什么，如打印输出，则返回类型要改为struct score_st *类型的数据*/
     #if 1
    for(cur=list;cur!=NULL;cur=cur->next)
    {
        if(cur->data.id==id)
        {
            return &cur->data;
        }
    }
    return NULL;
    #endif
}
/*销毁操作不用二级指针，因为不需要修改头结点地址，只是要销毁指针指向的内存而已
但最好传二级指针，把指向第一个数据的指针置为NULL比较合适*/
void list_destroy(node *list)
{
    node *cur;
    if(list==NULL) return ;
    for(cur=list;cur!=NULL;cur=list)
    {
        list=cur->next;
        free(cur);
    }
}

//main.c
#include<stdio.h>
#include<stdlib.h>
#include "nohead.h"
/*注意：！！！无头结点的单向链表不需创建，直接插入就行了，不需要像有头节点一样，
还要创建头结点，即直接创建一个指向空的指针即可 node *list=NULL*/
int main()
{
    node *list=NULL;
    struct score_st tmp,*ptr;
    int i=0,ret;
    #if 1
    for(i=0;i<7;i++)
    {
        tmp.id=i;
        snprintf(tmp.name,NAMESIZE,"stu%d",i);//数组名为指针常量，不能直接赋值；
        tmp.math=rand()%100;
        tmp.chinese=rand()%100;
       // list=list_insert(list,&tmp);
        ret=list_insert(&list,&tmp);//二级指针传参，插入失败时可区分错误类型（返回整形）
        if(ret!=0)
          return -1;
    }
    #endif
    list_show(list);
    #if 0
    if((ptr=list_find(list,6))==NULL)
    {
        printf("Can not find!\n");
    }
    else printf("%d %s %d %d\n",ptr->id,ptr->name,ptr->math,ptr->chinese);
    printf("\n");
    if(ret=(list_delete(&list))!=0)
       return -1;
    list_show(list);
    #endif
    list_destroy(list);
    return 0;
}