第一次用链表。一道简单的题 hdu 2019 数列有序

数列有序!

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 22117Accepted Submission(s): 9464

Problem Description

有n(n<=100)个整数，已经按照从小到大顺序排列好，现在另外给一个整数x，请将该数插入到序列中，并使新的序列仍然有序。

Input

输入数据包含多个测试实例，每组数据由两行组成，第一行是n和m，第二行是已经有序的n个数的数列。n和m同时为0标示输入数据的结束，本行不做处理。

Output

对于每个测试实例，输出插入新的元素后的数列。

Sample Input

3 3
1 2 4
0 0

Sample Output

1 2 3 4

先说说 链表。 早就知道点皮毛，但一直没真正用过链表。 今天终于算是用了一下。虽然是特别简单的一个链表问题。链表只是在思维上连续，但物理上是不连续的。链表最基本的是需要三个指针，一个头指针，一个指针用于开辟新内存，还有一个就是用于连接。头指针就是指向整个链表开端，就像是一根铁链，只要手握着一头，就可以顺利的找到每个环节。

最基本的形式就是用到结构体

struct node

｛

int a；

......

//数据部分。

struct node *next；

｝；

这里的next指针就是指向下一个结构体的指针。

这是一张单向链表的思路图。

链表给我最大的经验就是，不要看看书就以为自己懂了，纸面上理解不难，难的是实践。所以不要停留在书面上，通过一道题自己一步步写出代码来，可能比看很久的书收获还大。下面是关于这题的代码

#include<stdio.h>
#include<stdlib.h>
struct node
{
	int num;
	node *next;
};
int main()
{
	int n,m,i;
	while(scanf("%d%d",&n,&m)!=EOF&&(m!=0||n!=0))

	{
			node * root=(node *)malloc(sizeof(node));    //定义一个头指针 root
			root->next=NULL;
			node *p=root;                  //定义用于连接的指针p
			for(i=1;i<=n;i++)         //依次开辟新空间，存入数据，并且一节一节的连接
			{
				scanf("%d",&p->num);
				node *temp=(node *)malloc(sizeof(node));
				temp->next=NULL;
				p->next=temp;
				p=temp;
			}
			p=root;
			while(p->next!=NULL)        //这里开始插入数字。
			{
				  if(p->next->num>=m)
				  {
					  node *temp=(node *)malloc(sizeof(node));   //为新数字开辟内存。并连接。
					  temp->num=m;
					  temp->next=p->next;                                                    					  p->next=temp;
					  break;
				  }
			      p=p->next;
			}
			
			p=root;
			while(p->next!=NULL)       //输出链表的数据。最后一节的next指针为空。用来结束。
			{
				if(p==root)
				printf("%d",p->num);
				else
					printf(" %d",p->num);
				p=p->next;
			}
			printf("\n");

	}
	return 0;
}

本来这题我在hdu用 c 叫的时候 CE 了，原因是代码中 定义一个新的结构体变量 必须 用 struct node *temp；不能写成

node * temp； 但第二种写法c++ 中是可以的。所以我就用c++交上去AC了。 没改代码了。还有一个就是插入的数字可能比原有序列的所有元素都大 或都小， 这是我代码没考虑的。

今天整个收获还是不错的。 分冶算法开始懂一点了，（领略到了一点分冶的魅力 ^_^ ）快速排序搞定了。唉， 不过队里 布置的寒假任务 计算几何 还没开始看。今晚要早点睡觉。 明天继续。