当前位置 : 主页 > 编程语言 > 其它开发 >

带头结点的单链表

来源:互联网 收集:自由互联 发布时间:2022-07-01
带头结点的单链表   与顺序表相同,链表也是一种线性表。与顺序表不同的是,链表的物理存储结构是用一组地址任意的存储单元存储数据。它不像顺序表那样需要占据一段地址连续
带头结点的单链表

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

  在链表结构中,每个数据元素都存放在链表中的一个结点(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;
}

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

上一篇:Redis docker 主从模式与哨兵sentinel
下一篇:没有了
网友评论