C语言 超详细介绍与实现线性表中的无头单向非循环链表

目录

• 一、本章重点
• 二、链表介绍
• 三、无头单向非循环链表常用接口实现
• 3.1动态申请一个节点
• 3.2单链表打印
• 3.3单链表尾插
• 3.4单链表的头插
• 3.5单链表的尾删
• 3.6单链表头删
• 3.7单链表查找
• 3.8单链表在pos位置之前插入x
• 3.9单链表删除pos位置的节点
• 四、在线oj训练
• 4.1移除链表元素（力扣）
• 4.2反转单链表（力扣）

一、本章重点

• 无头单向非循环链表介绍
• 无头单向非循环链表常用接口实现
• 在线oj训练

二、链表介绍

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表 中的指针链接次序实现的。

简单的说：链表就是一些结构体相互关联起来，而关联的手段就是指针，通过存储下一个结构体的地址，就能挨个访问存在结构体里的数据。

相比于顺序表来说。链表能够解决顺序表的一些缺点。

• 从内存角度来说：无论是静态顺序表还是动态顺序表都会有一定的内存浪费，链表则是用一个节点申请一个节点，无内存浪费。
• 从效率角度上来说：顺序表不管是头插还是中间插入与删除都要移动数据，时间复杂度是O（N）。而链表则只要改变指针指向即可达到插入和删除的效果。

实际中要实现的链表的结构非常多样，以下情况组合起来就有8种链表结构：

1. 单向、双向

2. 带头、不带头

3. 循环、非循环

带头：

存在一个哨兵位的节点，该节点不存储任何有效数据，属于无效节点，但通过这个无效节点当头节点让我们在某些方面使用会有一些优势。

比如，你头插新节点时，不需要传二级指针，因为我们的头节点始终指向这个无效节点。

带头单向非循环链表

双向：

指的是节点中不再只有一个指针，而是有两个指针，一个指向前一个节点，另一个指向后一个节点。

无头双向非循环链表

循环：

尾指针不再指向NULL，而是指向头节点。 

无头单向循环链表

三、无头单向非循环链表常用接口实现

3.1动态申请一个节点

SLTNode* BuySListNode(SLDataType x)
{
	SLTNode* newnode = malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

3.2单链表打印

void SListPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.3单链表尾插

void SListPushBack(SLTNode** pphead, SLDataType x)
{
	if (*pphead==NULL)
	{
		*pphead = BuySListNode(x);
		return;
	}
	else
	{
		SLTNode* tail;
		tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = BuySListNode(x);
		return;
	}
}

3.4单链表的头插

void SListPushFront(SLTNode** pphead, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

3.5单链表的尾删

void SListPopBack(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else if((*pphead)->next==NULL)
	{
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

3.6单链表头删

void SListPopFront(SLTNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SLTNode* temp = *pphead;
		(*pphead) = (*pphead)->next;
		free(temp);
	}
}

3.7单链表查找

SLTNode* SListSearch(SLTNode* phead, SLDataType x)
{
	while (phead)
	{
		if (phead->data == x)
		{
			return phead;
		}
		phead = phead->next;
	}
	return NULL;
}

3.8单链表在pos位置之前插入x

void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	SLTNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		return;
	}
	else if(*pphead==pos)
	{
		newnode->next = pos;
		*pphead = newnode;
	}
	else
	{
		SLTNode* cur = *pphead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		newnode->next = pos;
		cur->next = newnode;
	}
}

3.9单链表删除pos位置的节点

void SListErase(SLTNode** phead, SLTNode* pos)
{
	if (*phead == NULL)
	{
		return;
	}
	else if (*phead == pos)
	{
		*phead == NULL;
	}
	else
	{
		SLTNode* cur = *phead;
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next = pos->next;
		free(pos);
	}
}

四、在线oj训练

4.1移除链表元素（力扣）

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

输入：head = [1,2,6,3,4,5,6], val = 6

输出：[1,2,3,4,5]

输入：head = [7,7,7,7], val = 7

输出：[]

 思路：

前后指针（跟班指针），初始转态prev指向NULL，cur指向head，如果出现cur->val==val.

就进行删除，删除步骤为prev->next==cur->next;cur=cur->next。迭代过程为：prev=cur,cur==cur->next。

特殊情况，如果要删除的val为头节点，则删除步骤为head=cur->next;free(cur);cur=head。

代码参考：

typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
    ListNode* cur=head;
    ListNode* prev=NULL;
    while(cur)
    {
        if(cur->val==val)
        {
            if(cur==head)
            {
                head=cur->next;
                free(cur);
                cur=head;
            }
            else
            {
                 prev->next=cur->next;
                 cur=cur->next;
            }
        }
        else
        {
            prev=cur;
            cur=cur->next;
        }
    }
    return head;
}

4.2反转单链表（力扣）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

输入：head = [1,2,3,4,5]

输出：[5,4,3,2,1]

输入：head = []

输出：[]

这里提供一个头插思路：newhead=NULL,将head中的数据从左到右依次头插至newhead链表中。

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
    ListNode* newhead=NULL;
    ListNode* cur=head;
    if(cur==NULL)
    {
        return cur;
    }
    ListNode* next=cur->next;
    while(cur)
    {
        cur->next=newhead;
        newhead=cur;
        cur=next;
        if(next)
        next=next->next;
    }
    return newhead;
}

注意:结束条件是cur==NULL;此时如果next往后走，next=next->next;会出现NULL解引用的问题。

其次要考虑cur==NULL的问题，不然ListNode* next=cur->next也是对空指针解引用。

其实可以化简为：

struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* cur = head;
    struct ListNode* newhead = NULL;
    while(cur)
    {
       struct ListNode* next = cur->next;
        cur->next = newhead;
        newhead = cur;
        cur = next;
    }
    return newhead;
}

到此这篇关于C语言 超详细介绍与实现线性表中的无头单向非循环链表的文章就介绍到这了,更多相关C语言 无头单向非循环链表内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！