贪心的小明看电视（后续）——链表

• 题目
• • 题目描述
  • 输入
  • 输出
  • 样例输入
  • 样例输出
• 过程剖析
• • 1.创建链表——输入节目信息
  • 2.链表排序——以节目结束时间排序
  • 3.遍历链表——查询所看节目个数
• 完整main函数

为了方便阅读，这里再把题目重复一遍

暑假到了，小明终于可以开心的看电视了，但是小明喜欢的节目太多了，他希望尽量多的看到完整的节目，现在他把他喜欢的电视节目的转播时间表给你，你能帮他合理安排吗？

每组输入的第一行是一个整数n（n<=100），表示小明喜欢的节目的总数。
接下来n行，每行输入两个整数si和ei（1<=i<=n），表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。

输出能完整看到的电视节目的个数。

12
1 3
3 4
0 7
3 8
15 19
15 20
10 15
8 18
6 12
5 10
4 14
2 9

5

首先定义合适的结构体类型 Time来储存单个节目信息和 List来储存链表信息，具体如下

typedef struct time{
	int start;
	int end;
	struct time *next;
}Time;//存放电视节目时间
typedef struct list{
	Time *head;
	Time *tail;
}List; //储存链表信息

用一个结构体单独存放链表信息的目的，在于更好的归纳各个链表，在这个例子中具体体现的作用，是在建立链表时能更方便地使用尾接法。

接着定义了一个add函数，将每一次输入的信息即时地生成结点并尾接链表，函数如下：

void add(List *list,int a,int b){
	Time *p=NULL;//工具指针 暂时存放结点
	//生成新结点
	p=(Time *)malloc(sizeof(Time));
	p->start = a;
	p->end = b; 
	p->next = NULL;
	//将新结点插尾
	if(list->tail ){
		//如果链表不空，接尾
		list->tail ->next=p;
		list->tail =p;
	}else{
	//如果为空链表，令头指针指向头结点，尾指针也要指向头结点，不然，尾和头断连 
		list->head =p;
		list->tail =p;
	}

同样定义了一个函数来进行排序，这个函数的排序思路与选择排序类似，在排序时只交换结点的数据域而不改变指针域，函数如下：

void sort(List *list,int n){//传入链表及电视节目个数 
	int i=0,start,end;//start和end 是交换工具，i控制循环次数
	Time *p1=list->head ;
	Time *p2=p1->next ;
	for(i=0;inext ;p2!=NULL;p2=p2->next){
			if(p1->end >p2->end ){
				//swap start
				start=p1->start ;
				p1->start =p2->start ;
				p2->start =start;
				
				//swap end
				end=p1->end ;
				p1->end =p2->end ;
				p2->end =end;
			}
		}
		p1=p1->next ;//p1后移 
	}
}

在不清楚结点个数（如n）时，也可通过判断p1是否为空结束循环

又是一个函数，传入要查询的链表信息，传出所看节目数，具体如下：

int find(List *list){
	int count=1,really_end;
	Time *p=list->head ; 
	really_end=p->end ;
	while(p!=NULL){
		if(really_end<=p->start ){
			count++;
			really_end=p->end ;
		}
		p=p->next ;
	}
	return count;
} 

int main(void){
	int n=0,i=0,count=0;
	int start=0,end=0;//临时储存开始结束时间
	int really_end=0;
	Time *p=NULL,*q=NULL;//用于遍历链表看电视 
	
	//创建空链表
	List list;
	list.head=list.tail =NULL;
	 
	scanf("%d",&n);
	
	//输入节目信息 
	for(i=0;i 
至此，小明成功看到了电视。