带头结点的单链表

  与顺序表相同，链表也是一种线性表。与顺序表不同的是，链表的物理存储结构是用一组地址任意的存储单元存储数据。它不像顺序表那样需要占据一段地址连续存储空间，而是将存储单元分散在内存的任意地址上。

  在链表结构中，每个数据元素都存放在链表中的一个结点（node）上，而每个结点之间通过指针将其连接起来，这样就形成了一条如“链”的结构。

  在C程序中，链表中的每个结点都可以用结构体来表示。在链表的每个结点中都必须有一个存放指针（地址）的域，也叫做指针域，指针域用来保存后继结点的地址，这样就将每个结点连接在一起，形成一条链。

  一个链表中通常有一个表头，表头的用来保存第一个结点的地址。一个链表的最后一个结点的指针域要置空（NULL），因为它没有后继结点。

单链表的特点：

• 除“第一个”数据元素外，其余数据元素有且仅有一个 前驱元素 prev，

• 除“最后一个”数据元素外，其余数据元素有且仅有一个 后继元素 next

• 单链表的每个结点只有一个指针域

结点：每一个结点都包含两个部分：数据域和指针域。数据域用于存放数据元素，指针域用于存放后继结点的地址。

头指针：无论链表是否为空，头指针均不为空，头指针是链表的必要元素，头指针指向表头结点
头结点：放在第一个元素结点之前，其数据域一般无意义（当然也可以用来存放链表的长度等）
首元结点：第一个元素的结点，它是表头结点之后的第一个结点。

  带头结点的单链表在后期的维护中更方便，头结点与其他结点一样拥有数据域和指针域，头结点的数据域可以不存储任何信息，但也可以存储如链表长度等附加信息。 头结点的指针域用于保存首元结点的地址。带头结点的单链表的相关代码如下。

---

带头结点的单链表操作

---

单链表元素结点

单链表的结点（LNode）通常使用结构体表示。

typedef struct node
{
    //结点数据域
    int data;
    //结点指针域
    struct node *next;
}LNode;

---

单链表头结点

单链表的头结点（HNode）也使用结构体表示，头结点的指针域保存首元结点的地址，所以其指针域的类型需要与元素结点类型相同。

typedef struct head
{
    //记录链表长度
    int len;
    LNode *next;
}HNode;

---

创建带头结点的单链表

创建一个带头结点的单链表，并返回一个指向单链表头结点的头指针。头指针用来标识单链表，保存单链表的入口地址。

/***************************************************************
函数功能: 创建带头结点的单链表
入口参数: 无
返回值: head（单链表头指针）
****************************************************************/
HNode *create_linked_list(void)
{
    //创建一个头指针
    HNode*head = NULL;
    //创建一个头结点，并将头指针指向头结点
    head = (HNode*)malloc(sizeof(HNode));
    head->len = 0;
    head->next = NULL;
    return head;
}

---

打印单链表

打印单链表的所有元素。

/***************************************************************
函数功能: 打印带头结点的单链表
入口参数: head（单链表头指针)）
返回值:  无
****************************************************************/
void print_linked_list(HNode*head)
{
    LNode *list = NULL;
    list = head->next;
    while(list)
    {
        printf("%d ", list->data);
        list = list->next;
    }
    printf("\n");
}

例如：

单链表：1 2 3 4 5 6 7 8 9

输出：1 2 3 4 5 6 7 8 9

---

尾插法

在单链表最后一个结点之后插入一个新结点，并将新插入的结点的指针域置NULL，单链表最后一个结点没有后继节点。

/***************************************************************
函数功能: 在单链表最后一个结点之后插入一个结点
入口参数: 
        参数1：head（单链表头指针)
        参数2：x(需要保存的元素数据)
返回值: head（单链表头指针）
****************************************************************/
HNode *add_linked_list_last(HNode *head,int x)
{
    LNode *last_node = NULL;
    last_node = head->next;
    //判断是否为最后一个结点
    while(last_node->next)
    {
        last_node=last_node->next;
    }
    //申请开辟一个结点空间
    LNode *new_node = (LNode*)malloc(sizeof(LNode));
    new_node->data = x;
    new_node->next=NULL;
    //将结点插入最后
    last_node->next = new_node;
    last_node = new_node;
    head->len++;//链表长度加1
    return head;
}

例如：

单链表：1 2 3 4 5 6 7 8 9

插入10后：1 2 3 4 5 6 7 8 9 10

---

头插法

在单链表首元结点之前插入一个新结点，并将头结点的指针指向新结点。

/***************************************************************
函数功能: 在单链表首元结点之前插入一个结点
入口参数: 
        参数1：head（单链表头指针)
        参数2：x(需要保存的元素数据)
返回值: head（单链表头指针）
****************************************************************/
HNode *add_linked_list_first(HNode *head,int x)
{
    LNode *new_node = NULL;
    //申请开辟一个结点空间
    new_node = (LNode*)malloc(sizeof(LNode));
    new_node->data = x;//保存需要插入的元素
    new_node->next = NULL;
    //将新结点插入到第一个结点之前
    new_node->next = head->next;
    head->next = new_node;
    head->len++;
    return head;
}

例如：

单链表：2 4 7 8 9 1

插入11后：11 2 4 7 8 9 1

---

删除单链表中第N个结点

删除单链表中的第N个结点，需要将第N-1个结点的后继指针指向第N+1个结点，然后将第N个结点的后继指针置NULL，然后再释放第N个结点的空间。

/***************************************************************
函数功能: 删除单链表中的第N个结点
入口参数: 
        参数1：head（单链表头指针)
        参数2：n（第N个结点）
返回值: head（单链表头指针）
****************************************************************/
HNode *delete_theN_node(HNode *head,int n)
{
    //判断n是否大于链表长度
    if (n > head->len || n < 1)
    {
        printf("该结点不存在！\n");
        return 0;
    }
    LNode *now_node = NULL;
    LNode *prev_node = NULL;
    now_node = head->next;
    //删除第一个结点
    if (1 == n)
    {
        head->next = now_node->next;
        now_node->next = NULL;
        free(now_node);
        now_node = NULL;
        head->len--;
    }
    //删除最后一个结点
    else if(head->len == n)
    {
        while(--n)
        {
            prev_node = now_node;
            now_node = now_node->next;
        }
        prev_node->next = NULL;
        free(now_node);
        now_node = NULL;
        head->len--;
    }
    //删除中间某个结点
    else
    {
        while(--n)
        {
            prev_node = now_node;
            now_node = now_node->next;
        }
        prev_node->next = now_node->next;
        now_node->next = NULL;
        free(now_node);
        now_node = NULL;
        head->len--;
    }
    return head;
}

例如：

单链表：2 4 7 8 9 1

删除第2个结点后： 2 7 8 9 1

---

删除单链表中元素为X的结点

前提：单链表中不包含重复元素。

/***************************************************************
函数功能: 删除单链表中元素为X的结点（单链表中不包含重复元素）
入口参数: 
        参数1：head（单链表头指针)
        参数2：x(删除的元素数据)
返回值: head（单链表头指针）
****************************************************************/
HNode *delete_num(HNode *head,int x)
{
    LNode *now_node = NULL;
    LNode *prev_node = NULL;
    now_node = head->next;

    //判断X是不是第一个结点的元素
    if(x == now_node->data){
        head->next = now_node->next;
        now_node->next = NULL;
        free(now_node);
        now_node = NULL;
        head->len--;
        return head;
    }
    //判断中间
    while(now_node->next)
    {
        if(x == now_node->data){
            prev_node->next = now_node->next;
            now_node->next = NULL;
            free(now_node);
            now_node = NULL;
            head->len--;
            return head;
        }
        else{
            prev_node = now_node;
            now_node = now_node->next;
        }
    }
    //判断最后一个结点的元素是否为X
    if(x == now_node->data){
        prev_node->next = NULL;
        free(now_node);
        now_node = NULL;
        head->len--;
    }
    else{
        printf("链表中无%d这个元素\n",x);
        return 0;
    }
    return head;
}

例如：

单链表：2 4 7 8 9 1

删除元素9后：2 4 7 8 1

---

删除单链表中连续重复的元素只保留一个

/***************************************************************
函数功能: 删除单链表中的重复元素
入口参数: head（单链表头指针)
返回值: head（单链表头指针）
****************************************************************/
HNode *delete_repetitive_num(HNode*head)
{
    LNode *now_node = NULL;
    LNode *prev_node = NULL;
    now_node = head->next;

    while(now_node->next){
        prev_node = now_node;
        now_node = now_node->next;
        //判断相邻两个元素是否相等
    if(prev_node->data == now_node->data){
            prev_node->next = now_node->next;
            now_node->next = NULL;
            free(now_node);
            now_node = prev_node;
        }
    }
    return head;
}

例如：

单链表：1 1 2 2 3 3 3 5 5

删除后：1 2 3 5

---

销毁单链表

销毁除头结点之外的结点。

/***************************************************************
函数功能: 销毁除头结点之外的结点
入口参数: head（单链表头指针)）
返回值: head（单链表头指针）
****************************************************************/
HNode *destroy_linked_list(HNode *head)
{
    LNode *now_node = NULL;
    //从第一个元素结点开始销毁
    while(head->next){
        now_node = head->next;
        if(now_node->next == NULL){
            head->next = NULL;
            free(now_node);
            now_node = NULL;
            head->len--;
            break;
        }
        head->next = now_node->next;
        now_node->next = NULL;
        free(now_node);
        now_node = NULL;
        head->len--;
    }
    return head;
}

---

单链表逆置

说明：此逆置不改变结点原来的位置，只交换两个结点存储的数据。

/***************************************************************
函数功能: 逆置单链表（交换元素数据）
入口参数: head（单链表头指针)
返回值: head（单链表头指针）
****************************************************************/
HNode *reverse_linked_list(HNode *head)
{
    int n = head->len;
    int temp;
    int i,j;
    printf("链表长度：%d\n",n);
    LNode *first_node = NULL;
    LNode *temp1_node = NULL;
    LNode *temp2_node = NULL;

    first_node = head->next;
    temp1_node = first_node;
    //如果链表元素个数为奇数则(n-1)%2,反之n%2
    if(n%2 == 0||(n-1)%2==0)
    {        
        //不管是奇数个元素还是偶数个元素，都只需要交换n/2次
        //奇数个元素其最中间那一个元素不需要交换
        for(i=0;i<n/2;i++)
        {
            temp2_node = first_node;
            for(j=0;j<n-i-1;j++)
            {
                temp2_node = temp2_node->next;
            }
            temp = temp1_node->data;
            temp1_node->data = temp2_node->data;
            temp2_node->data = temp;
            //指向第一个结点的指针往后移动一个
            temp1_node = temp1_node->next;
        }
    }
    return head;
}

例如：

单链表：3 2 4 5 10 8 1

逆置后：1 8 10 5 4 2 3

---

将两个链表归并为一个有序链表

/***************************************************************
函数功能: 将两个链表归并为一个有序链表
入口参数: 
        参数1：head1（单链表头指针)
        参数2：head2（单链表头指针）
返回值: head3（单链表头指针）
****************************************************************/
HNode *combine_linked_list(HNode*head1,HNode*head2)
{
    HNode *head3 = NULL;
    LNode *now_node = NULL;
    LNode *next_node = NULL;
    int flag = 0;
    int temp;
    int n;
    now_node = head1->next;
    //找head1的最后一个结点
    while(now_node->next){
        now_node = now_node->next;
    }
    //连接head1和head2
    now_node->next = head2->next;
    //合并
    head3 = head1;
    head3->len = (head1->len) + (head2->len);
    n = head3->len;

    //冒泡排序
    for(int i=0;i<n-1;i++)
    {
        now_node = head3->next;
        next_node = now_node;
        for(int j=0;j<n-1-i;j++)
        {
            next_node = next_node->next;
            if(now_node->data > next_node->data)
            {
                temp = now_node->data;
                now_node->data = next_node->data;
                next_node->data = temp;
                flag = 1;
            }
            now_node = now_node->next;
        }
        if(flag == 0){
            break;
        }
    }
    return head3;
}

例如：

单链表1：5 4 3 2 1

单链表2：9 6 8 7

归并后：1 2 3 4 5 6 7 8 9

---

更新第N个结点的数据

/***************************************************************
函数功能: 修改第N个结点的数据
入口参数: 
        参数1：head（单链表头指针)
        参数2：n（第N个结点）
        参数3：更新的数据
返回值: head3（单链表头指针）
****************************************************************/
HNode *change_theN_node(HNode *head,int n,int x)
{
	//判断n是否大于链表长度
	if (n > head->len || n < 1)
	{
		printf("该结点不存在！\n");
		return 0;
	}
	LNode *now_node = NULL;
	now_node = head->next;
	while(--n)
	{
		now_node = now_node->next;
	}
	now_node->data = x;
	return head;
}

例如：

单链表：5 4 3 2 1

更新第2个结点数据为12：5 12 3 2 1

---

查找值为X的元素

/***************************************************************
函数功能: 查找值为X的元素
入口参数: 
        参数1：head（单链表头指针)
        参数2：x（查找的值）
返回值: 0 表示不存在，1表示存在
****************************************************************/
int find_data_linked_list(HNode *head,int x)
{
	LNode *now_node = NULL;
	now_node = head->next;
	while(now_node){
		if(now_node->data == x){
			return 1;
		}
		now_node = now_node->next;
	}
	return 0;
}

---

主函数参考

int main(int argc, char const *argv[])
{
	int num;
	int n;
	//创建一个头指针用于标识链表
	HNode *phead = NULL;
	//创建一个带头结点的单链表
	phead = create_linked_list();

	LNode*new_node = NULL;
	LNode*last_node = NULL;

	printf("请向单链表输入数据：");
	do{
		scanf("%d",&num);
		new_node = (LNode*)malloc(sizeof(LNode));
		new_node->data = num;
		new_node->next = NULL;
		if (phead->next == NULL)
		{
			phead->next = new_node;
			last_node = new_node;
			phead->len++;
		}
		else
		{
			last_node->next = new_node;
			last_node = new_node;
			phead->len++;
		}

	}while(getchar() != '\n');
	//打印链表所有元素
	printf("链表长度：%d\n",phead->len);
	printf("链表所有元素：");
	print_linked_list(phead);
    
    //尾插法
    
    //头插法
	
	//删除第N个结点
	
	//查找数据
	
	return 0;
}

注意：该文章仅供学习交流不得转载商用。