通过编程训练题来讲讲链表操作
先来看看第一道题：
单链表中确定值最大的结点
输入若干个不超过 100 的整数，建立单链表，然后通过一趟遍历在单链表中确定值最大的结点。输出该结点的值及其序号。
输入格式:
首先输入一个整数 T，表示测试数据的组数，然后是 T 组测试数据。每组测试数据在一行上输入数据个数 n 及 n 个不超过 100 的整数。
输出格式:
对于每组测试，输出单链表中值最大的结点的值和该结点的序号。输出格式如下： “max=dmax num=dnum” 其中，dmax 表示最大的结点的值，dnum 表示最大的结点的值所在结点的序号。若有多个相同的最大值，则以首次出现的为准。
输入样例:
130 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
复制代码
输出样例:
解题思路：
题目未完全说清楚，第二行的第一个数其实是这组数据的个数。
这道题是叫我们建立多条链表，然后分别在每一条链表中寻找最大值以及它的值。
不知道有没有人和我一样把这个题目理解成多条链表中寻找最大值，然后输出最大值和这个值在这条链表中的位置。
先来看看我这种想法的思路吧：
#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;}
复制代码
分组查找大值及其坐标然后输出......
评论