链表删除练习

admin2024-04-03  0

1.链表删除练习(题目链接)

题目描述

试图编写一个链表,实现插入后,试着编写一下删除操作。(这种使用数组的方式可能会浪费内存,但是请暂时忽略这点)

作为练习的判断,请输出删除链表内所有元素x后的序列。数组保证删除后仍不为空。

输入格式

第一行包括一个数字n(n<100000),表示链表内元素的个数。

接下来一行,共n个整数,表示链表内的数据

接下来一个数字x,表示要删除的元素。

输出格式

一行,表示删除后的序列。

样例输入

8
2 3 4 4 4 5 3 8
4

样例输出

2 3 5 3 8

解题思路:

这道题运用到了链表的创建,删除,对创建如果还不熟,可以看看这个专栏中前一篇文,这道题对删除的操作进阶了一下,会出现连续多个一样的数,不过应该也做过删除数组元素时出现连续多个一样的数情况,所以也不算突兀,
按题目的意思,创建链表时,元素是以正序存入,也就是要用尾插法

参考代码:

这里我写的创建和删除没有做的那么规整,都糅合在了main函数里,

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int data;
    struct node *next;
}list;
int main()
{
	int n,x;
	scanf("%d",&n);//n是节点个数
	list *L,*q,*p;
	L=(list*)malloc(sizeof(list));//头节点
	q=L;//q指向头节点
	for(int i=0;i<n;i++)//创建链表,n个节点,
	{
	    p=(list*)malloc(sizeof(list));
	    scanf("%d",&p->data);
	    q->next=p;//使用尾插法,把p节点接至q节点后
	    q=q->next;//指针q后移
	}
	q->next=NULL;//链表结束
	q=L;//q和p一前一后两节点用于删除的操作
	p=L->next;
	scanf("%d",&x);//要删除的节点元素
	while(p)//遍历链表寻找要删除的节点
	{
	    if(p->data==x)//删除节点,删节点的时候q和p不移动,防止连续多个一样的元素的情况
	    {
	        q->next=p->next;//跳过要被删除的p节点
	        free(p);//释放指针p指向的节点,也就是删除
	        p=q->next;//再让指针p指向下一个节点
	    }
	    else
	    {
	        q=q->next;
	        p=p->next;
	    }
	}
	q=L->next;//让q指向第一个节点,用于后面输出链表
	while(q)//输出链表
	{
	    printf("%d ",q->data);
	    q=q->next;
	}
	return 0;
}

我还是对这道题总结一个删除链表元素的函数,无返回值的:

void deletelist(list *L,int x)
{
    list *p=L,*q=L->next;
    while(q)
    {
        if(q->data==x)
        {
            p->next=q->next;
            free(q);
            q=p->next;
        }
        else
        {
            p=p->next;
            q=q->next;
        }
    }
}

2.[编程入门]链表之节点删除(题目链接)

题目描述

有两个链表a和b,设节点中包含学号、成绩。从a链表中删去b链表中有相同学号的那些节点。

输入格式

第一行有两个用空格隔开的整数n和m,分别表示a和b两个链表中的节点个数。保证n和m均不超过100。
之后的n行每行有两个用空格隔开的整数,分别表示一个学生的学号和成绩。
最后的m行每行有两个用空格隔开的整数,分别表示一个学生的学号和成绩。
a和b两个链表中的节点并不一定按照学号顺序排列。保证a链表中学号各不相同,b链表中学号各不相同。

输出格式

首先输出a链表最终剩下的节点个数k。
在接下来的k行,每行输出两个用空格隔开的整数,分别表示一个学生的学号和成绩。
请注意行尾输出换行。

样例输入

3 3
106 90
104 80
101 85
104 95
106 88
105 87

样例输出

1
101 85

解题思路:

题目虽然说是从a链表中删去b链表中有相同学号的那些节点,但实际上只用建一个链表就够了,这题是顺着存入,仍然是尾插法

参考代码:

这回写的规整些

#include<stdio.h>
#include<stdlib.h>
typedef struct node
{
    int sno;
    int score;
    struct node *next;
}list;
void createlist(list *L,int n)//创建链表
{
    list *p=L,*q;
    for(int i=0;i<n;i++)
    {
        q=(list*)malloc(sizeof(list));
        scanf("%d%d",&q->sno,&q->score);
        p->next=q;//尾插法,q接至p后
        p=p->next;//p后移
    }
}
void deletelist(list *L,int x,int *k)//删除链表元素,题目要求输出的时候输出最后的链表节点数,k代表最终的链表节点数
{
    list *p=L,*q=L->next;
    while(q)
    {
        if(q->sno==x)
        {
            p->next=q->next;
            free(q);
            q=p->next;
            (*k)--;//删除了节点,节点数自减
        }
        else
        {
            p=p->next;
            q=q->next;
        }
    }
}
void dislist(list *L)//输出链表
{
    list *p=L->next;
    while(p)
    {
        printf("%d %d\n",p->sno,p->score);
        p=p->next;
    }
}
int main()
{
	int n,m,k;
	scanf("%d%d",&n,&m);
	k=n;
	list *L;
	L=(list*)malloc(sizeof(list));
	createlist(L,n);
	for(int i=0;i<m;i++)//没有创建另一个链表,直接用两个变量获取学号和分数
	{
	    int a,b;//a为学号,b为分数
	    scanf("%d%d",&a,&b);
	    deletelist(L,a,&k);//题目是删除相同学号,用学号做对比
	}
	printf("%d\n",k);
	dislist(L);
	return 0;
}
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!