数据结构带头结点的单向链表

经过学习我知道了线性表的顺序存储结构（顺序表），发现它有着明显的缺点：插入和删除元素时需要频繁的移动元素，运算效率低。必须申请堆空间。堆空间估计大了，造成浪费空间；估计小了，容易产生溢出，空间难以扩大。

采用链式存储结构的线性表（链表）可以克服以上的不足。

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以节点来表示的，每个节点的构成：元素(存放的数据元素)+指针(指示下一个元素存储位置，单、双链表的最后一个节点除外，它们存储的是一个空指针NULL)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

1.节点的结构如下图所示：

2.单链表由多个节点依次连接而成，结构如下图：

最开始的那个节点是头节点，头节点的数据域是不存放数据的，指针域指向链表的第一个节点。在单链表的定义中，带有头节点的称为带头节点单链表，不带头节点的称为不带头节点单链表。我们这次介绍的就是带头节点单链表。

一.节点的初始化

1.1 创建数据节点管理结构体

1.2 创建头结点管理结构体

1.3 初始化数据节点

1.4 初始化头结点

二.链表的初始化

2.1 头插法

2.2 尾插法

三判断链表是否空了

四修改节点

五删除节点

六插入节点

七摧毁链表

八显示链表

九全部代码

十运行结果

一.节点的初始化

1.1 创建数据节点管理结构体

// 定义输入数据类型
typedef int dataType;
// 定义数据节点
struct node
{
    dataType data;// 数据域
    struct node *next;// 指针域
};

1.2 创建头结点管理结构体

// 定义头节点
struct headNode
{
    struct node *first;// 头指针
    struct node *last;// 尾指针
    int nodeNumber;// 节点总个数
};

1.3 初始化数据节点

// 创建数据节点
struct node *create_Newnode(dataType data)
{
    struct node *pnew = malloc(sizeof(struct node));
    if(pnew == NULL)
        return NULL;
    pnew->data = data;
    pnew->next = NULL;
    return pnew;
}

1.4 初始化头结点

// 创建头节点
struct headNode *create_New_Nodehead(void)
{
    struct headNode *head = malloc(sizeof(struct headNode));
    if(head == NULL)
        return NULL;
    head->first = NULL;
    head->last = NULL;
    head->nodeNumber = 0;
    return head;
}

二.链表的初始化

链表的建立有两种方式，一种是头插法，一种是尾插法。由于单链表的头插和尾插性质，有时候常用来解决链表的逆置问题。

2.1 头插法

头插法：把后建立的结点插在头部。用这种方法建立起来的链表的实际顺序与输入顺序刚好向反,输出时为倒序。

操作步骤：创建指针pnew指向头节点，用malloc函数申请空间给节点pnew，接下来让节点pnew的指针域等于头节点的指针域，头节点的指针域指向节点pnew。把这段代码放到循环里面，进行多次头插操作。

// 创建链表
struct headNode *create_list(void)
{
    struct headNode *head = create_New_Nodehead();
    if(head == NULL)
        return NULL;
    printf("请输入数据:");
    while(1)
    {
        // 输入数据
        dataType data;
        scanf("%d",&data);
        if(data == 0)
            break;
        // 创建新节点
        struct node *pnew = create_Newnode(data);
        if(pnew == NULL)
            return NULL;
        // 从无到有
        if(head->first == NULL)
        {
            head->first = pnew;
            head->last = pnew;
        }
        else// 从少到多
        {
            // 头插法
            pnew->next = head->first;
            head->first = pnew;
           
        }
        // 更新节点
        head->nodeNumber++;
    }
    return head;
}

2.2 尾插法

尾插法就是在链表的尾部依次插入节点。

操作步骤：先找到链表的最后一个节点，然后在最后一个节点后面插入节点。接下来的操作和头插差不多了。

// 创建链表
struct headNode *create_list(void)
{
    struct headNode *head = create_New_Nodehead();
    if(head == NULL)
        return NULL;
    printf("请输入数据:");
    while(1)
    {
        // 输入数据
        dataType data;
        scanf("%d",&data);
        if(data == 0)
            break;
        // 创建新节点
        struct node *pnew = create_Newnode(data);
        if(pnew == NULL)
            return NULL;
        // 从无到有
        if(head->first == NULL)
        {
            head->first = pnew;
            head->last = pnew;
        }
        else// 从少到多
        {
            // 尾插法
            head->last->next = pnew;
            head->last = pnew;
          
        }
        // 更新节点
        head->nodeNumber++;
    }
    return head;
}

三判断链表是否空了

这里可以通过头结点管理结构体中定义的节点总个数nodeNumber来判断

// 判断链表是否为空
bool isNULL(struct headNode *head)
{
    if(head->nodeNumber == 0)
        return true;
    return false;
}

四修改节点

不改变节点个数，在已经存在的节点上修改指定节点的数值。

// 修改节点
struct headNode* reviseLink(struct headNode *head,int data1,dataType data2)
{
	struct node *p = head->first;
	while(p != NULL)
	{
		if(p->data == data1)// 原始数据
		{
			p->data = data2;// 修改后的数据
		}
		p = p->next;
	}
	return head;
}

五删除节点

操作步骤：先找到要删除节点前面的那个节点，然后修改指针域，用free释放要删除节点的空间，删除操作完成。

// 删除节点
struct headNode *deleteNode(struct headNode *head,dataType data)
{
    struct node *p=head->first;
    struct node *pre=NULL;
    // 找节点
    while (p)
    {
        // 找到了出来
        if(p->data==data)
        {
            break;
        }
        // 没找到继续找
        else
        {
            pre=p;
            p=p->next;
        }
    }
    // 如果删除节点为头节点
    if(p->data==head->first->data)
    {
        head->first=p->next;
        p->next=NULL;
        free(p);      
    }
    // 如果删除节点为尾节点
    else if(p->next==NULL)
    {
        pre->next=NULL;
        free(p);
    }
    // 如果删除节点为中间节点
    else
    {
        pre->next=p->next;
        p->next=NULL;
        free(p);
    }
    // 更新节点个数
    head->nodeNumber--;
    return head;
}

六插入节点

在指定位置插入元素，我们只需要找到要插入元素位置的前一个节点就可以了，然后修改节点指针域即可。

// 插入节点
struct headNode *interNode(struct headNode *head,int data,dataType newdata)
{
    struct node *p = head->first;
    struct node *per = NULL;
    struct node *pnew = create_Newnode(newdata);
    // 找节点
    while(p)
    {
        // 找到了
        if(p->data == data)
        {
            break;
        }
        // 没找到
        else
        {
            per = p;
            p = p->next;
        }
    }
    // 如果需要插入的节点没找到，直接尾插到最后面
    if(p==NULL)
    {
        head->last->next = pnew;
        head->last = pnew;
    }
    // 如果需要插入的节点为头结点，直接头插到最前面
    else if(head->first->data==p->data)
    {
        pnew->next = head->first;
        head->first = pnew;
    }
    // 如果为中间节点，随便插
    else
    {
        pnew->next = p;
        per->next = pnew;
    }
    // 更新节点个数
    
    head->nodeNumber++;
    return head;
}

七摧毁链表

因为单链表的一个个节点是用malloc申请的空间，这一部分的空间在内存的堆区，系统不会自动回收堆区的空间，所以要用free函数去把一个个的节点释放空间。

// 摧毁链表
struct headNode *distoryNode(struct headNode *head)
{
    if(isNULL(head))
    {
        printf("no found data\n");
        return NULL;
    }
    
    // 逐一删除节点
    struct node *p = NULL;
    for(struct node *tmp = head->first;tmp != NULL; tmp = p)
    {
        p = tmp->next;
        tmp->next = NULL;
        free(tmp);
        head->nodeNumber--;
    }
    return head;
}

八显示链表

没什么好说的，就是将链表打印出来。

// 显示链表
void printList(struct headNode *head)
{
    if(isNULL(head))
    {
        printf("no found data\n");
        return;
    }
    for(struct node *p = head->first;p != NULL;p = p->next)
    {
        printf("%d\t",p->data);
    }
    printf("\n");
    printf("链表节点个数为；%d\n",head->nodeNumber);
}

九全部代码

#include 
#include 
#include 
// 定义输入数据类型
typedef int dataType;
// 定义数据节点
struct node
{
    dataType data;
    struct node *next;
};
// 定义头节点
struct headNode
{
    struct node *first;
    struct node *last;
    int nodeNumber;
};
// 创建头节点
struct headNode *create_New_Nodehead(void)
{
    struct headNode *head = malloc(sizeof(struct headNode));
    if(head == NULL)
        return NULL;
    head->first = NULL;
    head->last = NULL;
    head->nodeNumber = 0;
    return head;
}
// 创建数据节点
struct node *create_Newnode(dataType data)
{
    struct node *pnew = malloc(sizeof(struct node));
    if(pnew == NULL)
        return NULL;
    pnew->data = data;
    pnew->next = NULL;
    return pnew;
}
// 创建链表
struct headNode *create_list(void)
{
    struct headNode *head = create_New_Nodehead();
    if(head == NULL)
        return NULL;
    printf("请输入数据:");
    while(1)
    {
        // 输入数据
        dataType data;
        scanf("%d",&data);
        if(data == 0)
            break;
        // 创建新节点
        struct node *pnew = create_Newnode(data);
        if(pnew == NULL)
            return NULL;
        // 从无到有
        if(head->first == NULL)
        {
            head->first = pnew;
            head->last = pnew;
        }
        else// 从少到多
        {
            #if 1
            // 尾插法
            head->last->next = pnew;
            head->last = pnew;
            #else
            // 头插法
            pnew->next = head->first;
            head->first = pnew;
            #endif
        }
        // 更新节点
        head->nodeNumber++;
    }
    return head;
}
// 修改节点
struct headNode* reviseLink(struct headNode *head,int data1,dataType data2)
{
	struct node *p = head->first;
	while(p != NULL)
	{
		if(p->data == data1)
		{
			p->data = data2;
		}
		p = p->next;
	}
	return head;
}
// 删除节点
struct headNode *deleteNode(struct headNode *head,dataType data)
{
    struct node *p=head->first;
    struct node *pre=NULL;
    while (p)
    {
        if(p->data==data)
        {
            break;
        }
        else
        {
            pre=p;
            p=p->next;
        }
    }
    if(p->data==head->first->data)
    {
        head->first=p->next;
        p->next=NULL;
        free(p);      
    }
    else if(p->next==NULL)
    {
        pre->next=NULL;
        free(p);
    }
    else
    {
        pre->next=p->next;
        p->next=NULL;
        free(p);
    }
    head->nodeNumber--;
    return head;
}
// 插入节点
struct headNode *interNode(struct headNode *head,int data,dataType newdata)
{
    struct node *p = head->first;
    struct node *per = NULL;
    struct node *pnew = create_Newnode(newdata);
    while(p)
    {
        if(p->data == data)
        {
            break;
        }
        else
        {
            per = p;
            p = p->next;
        }
    }
    if(p==NULL)
    {
        head->last->next = pnew;
        head->last = pnew;
    }
    else if(head->first->data==p->data)
    {
        pnew->next = head->first;
        head->first = pnew;
    }
    else
    {
        pnew->next = p;
        per->next = pnew;
    }
    
    head->nodeNumber++;
    return head;
}
// 判断链表是否为空
bool isNULL(struct headNode *head)
{
    if(head->nodeNumber == 0)
        return true;
    return false;
}
// 显示链表
void printList(struct headNode *head)
{
    if(isNULL(head))
    {
        printf("no found data\n");
        return;
    }
    for(struct node *p = head->first;p != NULL;p = p->next)
    {
        printf("%d\t",p->data);
    }
    printf("\n");
    printf("链表节点个数为；%d\n",head->nodeNumber);
}
// 摧毁链表
struct headNode *distoryNode(struct headNode *head)
{
    if(isNULL(head))
    {
        printf("no found data\n");
        return NULL;
    }
    
    // 逐一删除节点
    struct node *p = NULL;
    for(struct node *tmp = head->first;tmp != NULL; tmp = p)
    {
        p = tmp->next;
        tmp->next = NULL;
        free(tmp);
        head->nodeNumber--;
    }
    return head;
}
int main(int argc, char const *argv[])
{
    struct headNode *head = create_list();
    if(head == NULL)
        return -1;
    printf("\n");
    // 修改节点
    printf("修改节点后:");
    head = reviseLink(head,1,11);
    head = reviseLink(head,5,55);
    printList(head);
    printf("\n");
    // 删除节点
    printf("删除节点后:");
    head = deleteNode(head,11);
    printList(head);
    printf("\n");
    
    // 插入节点
    head = interNode(head,1,88);
    head = interNode(head,2,88);
    head = interNode(head,3,88);
    head = interNode(head,4,88);
    printf("插入节点后:");
    printList(head);
    printf("\n");
    
    // 摧毁链表
    distoryNode(head);
    printf("销毁节点后:");
    printList(head);
    printf("\n");
    return 0;
}

十运行结果

假定输入数据为1,2,3,4,5，结果如下：

数据结构带头结点的单向链表

一.节点的初始化

1.1 创建数据节点管理结构体

1.2 创建头结点管理结构体

1.3 初始化数据节点

1.4 初始化头结点

二.链表的初始化

2.1 头插法

2.2 尾插法

三判断链表是否空了

四修改节点

五删除节点

六插入节点

七摧毁链表

八显示链表

九全部代码

十运行结果

相关文章

最近发表

热门文章

数据结构带头结点的单向链表

一.节点的初始化

1.1 创建数据节点管理结构体

1.2 创建头结点管理结构体

1.3 初始化数据节点

1.4 初始化头结点

二.链表的初始化

2.1 头插法

2.2 尾插法

三 判断链表是否空了

四 修改节点

五 删除节点

六 插入节点

七 摧毁链表

八 显示链表

九 全部代码

十 运行结果

相关文章

最近发表

热门文章

三判断链表是否空了

四修改节点

五删除节点

六插入节点

七摧毁链表

八显示链表

九全部代码

十运行结果