结构体类型数据单链表的操作

数据结构--结构体类型数据单链表的操作

杼蛘

3334人浏览 · 2022-06-30 10:51:04

杼蛘 · 2022-06-30 10:51:04 发布

第1关：头插法创建学生数据类型单链表

任务描述

本关任务：给定一个含有n个学生数据元素的数组a，用头插法来快速创建整个单链表。

测试说明

平台会对你编写的代码进行测试。

测试输入：
5
10010
Liyi
M
2000 5 23
45
10020
Lier
M
2001 2 3
62.5
10030
Lisan
F
2000 10 14
92.5
10040
Lisi
F
2002 7 23
87
10050
Liwu
M
1999 8 6
78

输入说明：
第一行输入为学生的个数N；
第二行开始输入N个学生的具体信息。

预期输出：
学号:10050 姓名:Liwu 性别:M 出生日期:1999-8-6 成绩:78.0
学号:10040 姓名:Lisi 性别:F 出生日期:2002-7-23 成绩:87.0
学号:10030 姓名:Lisan 性别:F 出生日期:2000-10-14 成绩:92.5
学号:10020 姓名:Lier 性别:M 出生日期:2001-2-3 成绩:62.5
学号:10010 姓名:Liyi 性别:M 出生日期:2000-5-23 成绩:45.0

输出说明：
输出为学生数据创建的单链表；每行输出一个学生的信息，输出数据的次序与输入次序正好相反。

代码如下

#include <stdio.h>
#include<stdlib.h>
#include<string.h>

/* 定义学生数据类型STUDENT */
typedef struct date
{  
	int year;
    int month;
    int day;
}DATE;
typedef struct student
{
     int num;
     char name[20];
     char sex;
     DATE birthday;
     float score;
}STUDENT;

/* 定义ElemType为STUDENT类型 */
typedef STUDENT ElemType;

void input(ElemType &s);
void output(ElemType s);

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;
void CreateHeadList(LinkList  &L, ElemType  a[ ], int n ) ; //根据数组用头插法创建单链表 
void ListTraverse(LinkList L,void(*vi)(ElemType));

int  main()
{
    LinkList  head;          //定义一个LinkList 型的变量head
    ElemType  a[100 ];
    int n,i;
    scanf("%d",&n);
    for(i=0; i<n; i++ )                //遍历a数组所有元素
    {
        input(a[i]);
    }
    CreateHeadList ( head,a,n);     //用头插法输入数据创建单链表
    ListTraverse (head,output);         //输出以head为头的链表各结点的值  
    return 0; 
}
void input(ElemType &s)
{
    //printf("请输入学生学号:");
    scanf("%d",&(s.num));
    //printf("请输入学生姓名:");
    scanf("%s", s.name);
    //printf("请输入学生性别:");
    scanf(" %c",&(s . sex));
    //printf("请输入学生出生日期:");
    scanf("%d%d%d",&s.birthday.year, &s.birthday.month, &s. birthday.day);
    //printf("请输入学生成绩:");
    scanf("%f",&(s.score));	
}

void output(ElemType s)
{
  printf("学号:%d\t姓名:%s\t性别:%c\t", s.num,s.name,s.sex);
  printf("出生日期:%d-%d-%d\t", s.birthday.year,s.birthday.month, s.birthday.day);
  printf("成绩:%.1f\n", s.score);
}


void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 
	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");
}
void CreateHeadList(LinkList  &L, ElemType  a[], int n )  
{
    //根据长度为n的数组a用头插法来创建单链表L
    /********** Begin **********/ 
    LinkList node;
    L = (LinkList)malloc(sizeof(LNnode));
    L->next = NULL;
    for(int i = 0; i < n; i++){
        node = (LinkList)malloc(sizeof(LNnode));
        node -> data = a[i];
        node->next = L -> next;
        L -> next = node;
    }
    /********** End **********/
}

第2关：尾插法创建学生数据类型单链表

任务描述

本关任务：给定一个含有n个学生数据元素的数组a，用尾插法来快速创建整个单链表。

测试说明

平台会对你编写的代码进行测试。

测试输入：
5
10010
Liyi
M
2000 5 23
45
10020
Lier
M
2001 2 3
62.5
10030
Lisan
F
2000 10 14
92.5
10040
Lisi
F
2002 7 23
87
10050
Liwu
M
1999 8 6
78

输入说明：
第一行输入为学生的个数N；
第二行开始输入N个学生的具体信息。

输出说明：
输出为学生数据创建的单链表；每行输出一个学生的信息，输出数据的次序与输入次序相同。

代码如下

#include <stdio.h>
#include<stdlib.h>
#include<string.h>

/* 定义学生数据类型STUDENT */
typedef struct date
{  
	int year;
    int month;
    int day;
}DATE;
typedef struct student
{
     int num;
     char name[20];
     char sex;
     DATE birthday;
     float score;
}STUDENT;

/* 定义ElemType为STUDENT类型 */
typedef STUDENT ElemType;

void input(ElemType &s);
void output(ElemType s);

/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;
void CreateTailList (LinkList  &L, ElemType  a[ ], int n ) ; //根据数组用头插法创建单链表 
void ListTraverse(LinkList L,void(*vi)(ElemType));

int  main()
{
    LinkList  head;          //定义一个LinkList 型的变量head
    ElemType  a[100];
    int n,i;
    scanf("%d",&n);
    for(i=0; i<n; i++ )                //遍历a数组所有元素
    {
        input(a[i]);
    }
    CreateTailList ( head,a,n);     //用尾插法输入数据创建单链表
    ListTraverse (head,output);         //输出以head为头的链表各结点的值  
    return 0; 
}
void input(ElemType &s)
{
    //printf("请输入学生学号:");
    scanf("%d",&(s.num));
    //printf("请输入学生姓名:");
    scanf("%s", s.name);
    //printf("请输入学生性别:");
    scanf(" %c",&(s . sex));
    //printf("请输入学生出生日期:");
    scanf("%d%d%d",&s.birthday.year, &s.birthday.month, &s. birthday.day);
    //printf("请输入学生成绩:");
    scanf("%f",&(s.score));	
}

void output(ElemType s)
{
  printf("学号:%d\t姓名:%s\t性别:%c\t", s.num,s.name,s.sex);
  printf("出生日期:%d-%d-%d\t", s.birthday.year,s.birthday.month, s.birthday.day);
  printf("成绩:%.1f\n", s.score);
}


void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 
	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	/********** Begin **********/ 
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");
	/********** End **********/
}
void CreateTailList(LinkList  &L, ElemType  a[], int n)  
{
	//根据长度为n的数组a用尾插法来创建单链表L	 
	/********** Begin **********/ 
    LinkList node,p;
    p = L = (LinkList)malloc(sizeof(LNnode));
    L->next = NULL;
    for(int i = 0; i < n; i++){
        node = (LinkList)malloc(sizeof(LNnode));
        node -> data = a[i];
        node -> next = NULL;
        p->next = node;
        p = node;
    }
	/********** End **********/
}

第3关：将学生数据类型单链表按姓名排序

任务描述

本关任务：将一个含有n个学生数据元素的单链表按姓名排成一个从小到大的有序的单链表。

测试说明

平台会对你编写的代码进行测试。

测试输入：
5
10010
Liyi
M
2000 5 23
45
10020
Lier
M
2001 2 3
62.5
10030
Lisan
F
2000 10 14
92.5
10040
Lisi
F
2002 7 23
87
10050
Liwu
M
1999 8 6
78

输入说明：
第一行输入为学生的个数N；
第二行开始输入N个学生的具体信息。

预期输出：
排序前:
学号:10050 姓名:Liwu 性别:M 出生日期:1999-8-6 成绩:78.0
学号:10040 姓名:Lisi 性别:F 出生日期:2002-7-23 成绩:87.0
学号:10030 姓名:Lisan 性别:F 出生日期:2000-10-14 成绩:92.5
学号:10020 姓名:Lier 性别:M 出生日期:2001-2-3 成绩:62.5
学号:10010 姓名:Liyi 性别:M 出生日期:2000-5-23 成绩:45.0
排序后:
学号:10020 姓名:Lier 性别:M 出生日期:2001-2-3 成绩:62.5
学号:10030 姓名:Lisan 性别:F 出生日期:2000-10-14 成绩:92.5
学号:10040 姓名:Lisi 性别:F 出生日期:2002-7-23 成绩:87.0
学号:10050 姓名:Liwu 性别:M 出生日期:1999-8-6 成绩:78.0
学号:10010 姓名:Liyi 性别:M 出生日期:2000-5-23 成绩:45.0

输出说明：
第一部分输出根据输入数据创建的单链表，每行输出一个学生的信息。
第二部分输出按姓名排成一个从小到大的有序的单链表，每行输出一个学生的信息。

代码如下

 #include <stdio.h>
#include<stdlib.h>
#include<string.h>

/* 定义学生数据类型STUDENT */
typedef struct date
{  
	int year;
	int month;
	int day;
}DATE;
typedef struct student
{
	int num;
	char name[20];
	char sex;
	DATE birthday;
	float score;
}STUDENT;

/* 定义ElemType为STUDENT类型 */
typedef STUDENT ElemType;

void input(ElemType &s);
void output(ElemType s);
int compare(ElemType a,ElemType b);
void swap(ElemType &a, ElemType &b);


/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;

void CreateHeadList(LinkList  &L, ElemType  a[ ], int n ) ; //根据数组用头插法创建单链表 
void ListTraverse(LinkList L,void(*vi)(ElemType));
void BubbleSort(LinkList  &head,int (*compare)(ElemType,ElemType));

int  main()
{
	LinkList  head;          //定义一个LinkList 型的变量head
	ElemType  a[100 ];
	int n,i;
	scanf("%d",&n);
	for(i=0; i<n; i++ )                //输入数组所有元素
	{
		input(a[i]);
	}
	CreateHeadList ( head,a,n);        //用头插法输入数据创建单链表
	printf("排序前:\n");
	ListTraverse (head,output);         //输出以head为头的链表各结点的值
	BubbleSort(head,compare);
	printf("排序后:\n");
	ListTraverse (head,output); 
	return 0; 
}
void input(ElemType &s)
{
	//printf("请输入学生学号:");
	scanf("%d",&(s.num));
	//printf("请输入学生姓名:");
	scanf("%s", s.name);
	//printf("请输入学生性别:");
	scanf(" %c",&(s . sex));
	//printf("请输入学生出生日期:");
	scanf("%d%d%d",&s.birthday.year, &s.birthday.month, &s. birthday.day);
	//printf("请输入学生成绩:");
	scanf("%f",&(s.score));	
}

void output(ElemType s)
{
	printf("学号:%d\t姓名:%s\t性别:%c\t", s.num,s.name,s.sex);
	printf("出生日期:%d-%d-%d \t", s.birthday.year,s.birthday.month, s.birthday.day);
	printf("成绩:%.1f\n", s.score);
}
int compare(ElemType a,ElemType b) 
{   // 如果要按照学生的姓名比较大小，则需根据a,b的name成员比较大小的结果，返回1、0、-1
	if (  strcmp( a.name, b.name ) > 0 )
		return 1;
	else  if ( strcmp( a.name, b.name ) == 0 )
		return 0;
	else 
		return -1;   
}

void swap(ElemType &a, ElemType &b)
{
	ElemType t;
	t=a;a=b;b=t;
}


void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 
	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");
}
void CreateHeadList(LinkList  &L, ElemType  a[], int n )  
{
	//根据长度为n的数组a用头插法来创建单链表L
	LNnode *p;          
	int i;  	         
	L =(LNnode *) malloc( sizeof(LNnode) ) ;  //创建头结点
	L ->next=NULL;      //头结点的next域置空，表示一个空单链表
	for(i=0; i<n; i++ )                //遍历a数组所有元素
	{
		p=(LNnode *)malloc(sizeof(LNnode));
		p->data=a[i];                   //创建存放a[i]元素的新结点p
		p->next=L->next;               //将p插在头结点之后
		L->next=p;        
	}  
} 

void BubbleSort(LinkList  &head,int (*compare)(ElemType,ElemType))
{
	//用冒泡法将带头结点的单链表排成一个有序的单链表
	/********** Begin **********/ 
	LinkList p1,p2;
    p1 = head->next;
    while(p1){
        p2 = p1 -> next;
        while(p2){
            if(compare(p1->data,p2->data)>0){
                swap(p1->data,p2->data);
            }
            p2 = p2 -> next;
        }
        p1 = p1 -> next;
    }
	/********** End **********/
}

4. 在学生数据类型单链表中查找成绩第一名和第二名的学生信息

任务描述

本关任务：在一个含有n个学生数据元素的单链表中查找成绩第一名和第二名的学生信息。

测试说明

平台会对你编写的代码进行测试：

测试输入：
5
10010
Liyi
M
2000 5 23
45
10020
Lier
M
2001 2 3
62.5
10030
Lisan
F
2000 10 14
92.5
10040
Lisi
F
2002 7 23
87
10050
Liwu
M
1999 8 6
78

输入说明：
第一行输入为学生的个数N；
第二行开始输入N个学生的具体信息。

预期输出：
所有学生信息:
学号:10050 姓名:Liwu 性别:M 出生日期:1999-8-6 成绩:78.0
学号:10040 姓名:Lisi 性别:F 出生日期:2002-7-23 成绩:87.0
学号:10030 姓名:Lisan 性别:F 出生日期:2000-10-14 成绩:92.5
学号:10020 姓名:Lier 性别:M 出生日期:2001-2-3 成绩:62.5
学号:10010 姓名:Liyi 性别:M 出生日期:2000-5-23 成绩:45.0

第3个学生成绩是第一名：
学号:10030 姓名:Lisan 性别:F 出生日期:2000-10-14 成绩:92.5

第2个学生成绩是第二名：
学号:10040 姓名:Lisi 性别:F 出生日期:2002-7-23 成绩:87.0

输出说明：
第一部分根据输入数据创建的单链表，输出所有学生信息，每行输出一个学生的信息。
第二部分输出查找结果，输出成绩第一和第二的学生信息。

代码如下

 #include <stdio.h>
#include<stdlib.h>
#include<string.h>

/* 定义学生数据类型STUDENT */
typedef struct date
{  
	int year;
	int month;
	int day;
}DATE;
typedef struct student
{
	int num;
	char name[20];
	char sex;
	DATE birthday;
	float score;
}STUDENT;

/* 定义ElemType为STUDENT类型 */
typedef STUDENT ElemType;

void input(ElemType &s);
void output(ElemType s);
int compare(ElemType a,ElemType b);
void swap(ElemType &a, ElemType &b);


/* 单链表类型定义 */
typedef struct LNnode
{	
	ElemType data;
	struct LNnode *next;
}LNnode,*LinkList;

void CreateHeadList(LinkList  &L, ElemType  a[ ], int n ) ; //根据数组用头插法创建单链表 
void ListTraverse(LinkList L,void(*vi)(ElemType));
void FstAndSndValue(LinkList  L, void(*vi)(ElemType), int (*compare)(ElemType,ElemType) ) ;

int  main()
{
	LinkList  head;          //定义一个LinkList 型的变量head
	ElemType  a[100 ];
	int n,i;
	scanf("%d",&n);
	for(i=0; i<n; i++ )                //输入数组所有元素
	{
		input(a[i]);
	}
	CreateHeadList ( head,a,n);        //用头插法输入数据创建单链表
	printf("所有学生信息:\n");
	ListTraverse (head,output);         //输出以head为头的链表各结点的值
	FstAndSndValue(head,output,compare);
	return 0; 
}
void input(ElemType &s)
{
	//printf("请输入学生学号:");
	scanf("%d",&(s.num));
	//printf("请输入学生姓名:");
	scanf("%s", s.name);
	//printf("请输入学生性别:");
	scanf(" %c",&(s . sex));
	//printf("请输入学生出生日期:");
	scanf("%d%d%d",&s.birthday.year, &s.birthday.month, &s. birthday.day);
	//printf("请输入学生成绩:");
	scanf("%f",&(s.score));	
}

void output(ElemType s)
{
	printf("学号:%d\t姓名:%s\t性别:%c\t", s.num,s.name,s.sex);
	printf("出生日期:%d-%d-%d \t", s.birthday.year,s.birthday.month, s.birthday.day);
	printf("成绩:%.1f\n", s.score);
}
int compare(ElemType a,ElemType b) 
{   // 如果要按照学生的成绩比较大小，则需根据a,b的score成员比较大小的结果，返回1、0、-1
	if ( a.score == b. score )
     	return 0;
   	else
    if( a. score < b. score )
     	return -1;
	else 
     	return 1;
}

void swap(ElemType &a, ElemType &b)
{
	ElemType t;
	t=a;a=b;b=t;
}


void ListTraverse(LinkList L,void(*vi)(ElemType))
{ 
	// 初始条件：单链表L已存在。
	//操作结果：依次对L的每个数据元素调用函数vi()
	LinkList p=L->next;
	while(p)
	{
		vi(p->data);
		p=p->next;
	}
	printf("\n");
}

void CreateHeadList(LinkList  &L, ElemType  a[], int n )  
{
	//根据长度为n的数组a用头插法来创建单链表L
	LNnode *p;          
	int i;  	         
	L =(LNnode *) malloc( sizeof(LNnode) ) ;  //创建头结点
	L ->next=NULL;      //头结点的next域置空，表示一个空单链表
	for(i=0; i<n; i++ )                //遍历a数组所有元素
	{
		p=(LNnode *)malloc(sizeof(LNnode));
		p->data=a[i];                   //创建存放a[i]元素的新结点p
		p->next=L->next;               //将p插在头结点之后
		L->next=p;        
	}  
} 

void  FstAndSndValue(LinkList  L, void(*vi)(ElemType), int (*compare)(ElemType,ElemType) ) 
{
	//在带头结点的单链表成查找成绩第一名和第二名学生的信息
	/********** Begin **********/ 
	STUDENT one ,two;
    int i = 1,a = 1,b;
    one = L -> next -> data;
    L = L->next->next;
    while(L){
        i++;
        if(compare(L->data,one)>0){
            two = one;
            b = a;
            one = L -> data;
            a = i;
        }else if(compare(L->data,two)>0){
            two = L -> data;
            b = i;
        }
        L = L -> next ;
    }
    

    printf("第%d个学生成绩是第一名：\n",a);
    vi(one);
    printf("\n");
    printf("第%d个学生成绩是第二名：\n",b);
    vi(two);
	/********** End **********/
}

2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

解密Linux TCP网络协议栈的工作原理

根据四次挥手流程，可以思考一些问题：（1）传输数据过程中，网线断了之后立刻连接，TCP如何知道？可以使用异步，将网络层和业务层分离，单独处理。四次挥手FIN_WAIT_1、FIN_WAIT_2、TIME_WAIT、CLOSING直接的转换，CLOSE_WAIT和LAST_ACK的处理等。为了保证数据能正确分发，TCP使用一种TCB（传输控制块）的数据结构，把发送给不同设备的数据封装起来。需要注意

2048 AI社区

未来展厅图景：以创新为笔，绘就交互新生态

2048 AI社区

深入解析Rocket框架的FromRequest与责任链模式

Rocket 框架通过特性及其返回的Outcome枚举，巧妙地应用了责任链模式来构建请求处理流程。请求守卫作为链中的处理器（Handler），按顺序执行，并通过Outcome的SuccessFailureForward三种结果来决定请求是向下传递、中断处理还是被转发。这种设计提供了高度的灵活性、可组合性和安全性，是 Rocket 路由和守卫机制的核心。