通过编程训练题来讲讲链表操作

通过编程训练题来讲讲链表操作

先来看看第一道题：

单链表中确定值最大的结点

输入若干个不超过100的整数，建立单链表，然后通过一趟遍历在单链表中确定值最大的结点。输出该结点的值及其序号。

输入格式:

首先输入一个整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据在一行上输入数据个数n及n个不超过100的整数。

输出格式:

对于每组测试，输出单链表中值最大的结点的值和该结点的序号。输出格式如下： “max=dmax num=dnum” 其中，dmax表示最大的结点的值，dnum表示最大的结点的值所在结点的序号。若有多个相同的最大值，则以首次出现的为准。

输入样例:

1
30 85 97 43 70 69 29 77 22 64 25 55 39 95 69 99 61 97 69 59 12 88 55 75 66 13 75 36 85 67 69

输出样例:

max=99 num=15

解题思路：

题目未完全说清楚，第二行的第一个数其实是这组数据的个数。

这道题是叫我们建立多条链表，然后分别在每一条链表中寻找最大值以及它的值。

不知道有没有人和我一样把这个题目理解成多条链表中寻找最大值，然后输出最大值和这个值在这条链表中的位置。

先来看看我这种想法的思路吧：

#include<stdio.h>
#include<stdlib.h>
​
typedef struct list{
    int data;
    struct list *next;
}node_s,* node_p;
​
node_p create_head(){
    node_p head = malloc(sizeof(node_s));
    if(head != NULL){
        head->next = NULL;
    }
    return head;
}
​
node_p creat_new_node(int n){
    node_p new_node = malloc(sizeof(node_s));
    if(new_node != NULL){
        new_node->data = n;
        new_node->next = NULL;
        
    }
    return new_node;
}
​
void add_node_tail(node_p head,node_p new_node){
    
    while(head->next != NULL){
        head = head -> next;
    }
    head->next = new_node;
}
​
int main(){
    node_p head = create_head();
    int T;
    scanf("%d",&T);
    int num;
    int first_num = 0;
    int max=0;
    for(int i=0;i<T;i++){
        node_p new_node = NULL;
        int t;
        scanf("%d",&t);
        for(int i=0;i<t;i++){
            scanf("%d",&num);
            new_node = creat_new_node(num);
            add_node_tail(head,new_node);
        }
        
        
        int num1=0;
        while(head->next != NULL){
            if(head->data > max){
                max = head->data;
                first_num=num1;
            }
            head = head->next;
            num1++;
        }
        
    }
    
    printf("max=%d num=%d",max,first_num);
    
    return 0;
}

有兴趣的朋友可以看一下，本次文章就不介绍这个题目的解法了。

下面介绍来讲解这道题目的正确解法。

先看看链表的常规结构：

typedef struct list{
    int data;
    struct list *next;
}node_s,* node_p;

数据域data与指针域next.

接着是创建头节点的函数。

node_p create_head(){
    node_p head = malloc(sizeof(node_s));
    if(head != NULL){
        head->next = NULL;
    }
    return head;
}

我们这把头节点设置为没有数据，有的人习惯头节点也放置数据。我认为在需要考虑处理头节点时使用不放数据的头节点比较方便。

接下来是创建新节点的函数。

node_p creat_new_node(int n){
    node_p new_node = malloc(sizeof(node_s));
    if(new_node != NULL){
        new_node->data = n;
        new_node->next = NULL;
        
    }
    return new_node;
}

过程很简单，给新节点分配一块内存，然后将数据域填上，因为不知道是链表尾部添加节点还是链表头部添加节点，我们在此将指针域赋值为空。

然后在此我们这里在链表尾部添加节点。

void add_node_tail(node_p head,node_p new_node){
    
    while(head->next != NULL){
        head = head -> next;
    }
    head->next = new_node;
}

很简单的实现了，将头指针指到尾部，然后将节点连接即可。

然后是查找函数了。

void find(node_p head){
    int max=0;
    int num=0;
    int last_num=0;
    while(head != NULL){
        if(head->data > max){
            max = head->data;
            last_num=num;
        }
        head = head->next;
        num++;
    }
    
    printf("max=%d num=%d\n",max,last_num);
}

遍历链表，找出最大值及其坐标然后输出。

最后看一看主函数吧~

int main(){
	
	int T;
	scanf("%d",&T);
	int num;
	for(int i=0;i<T;i++){
		node_p head = create_head();
		node_p new_node = NULL;
		int t;
		scanf("%d",&t);
		for(int i=0;i<t;i++){
			scanf("%d",&num);
			new_node = creat_new_node(num);
			add_node_tail(head,new_node);
		}
		find(head);
	}
	
	return 0;
}

分组查找大值及其坐标然后输出......