学步园

     某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
　　由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。　　已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

#include "stdafx.h"<br /> #include <iostream><br /> using namespace std;</p> <p>class NodeList<br /> {<br /> public:<br /> struct Node<br /> {<br /> int m_start;<br /> int m_end;<br /> Node * pNext;<br /> int Get() { return (m_end - m_start +1);}<br /> };<br /> NodeList();<br /> ~NodeList();<br /> void AddNode(Node* p);<br /> int GetNum();<br /> public:<br /> Node* pFirst;<br /> };<br /> NodeList::NodeList()<br /> {<br /> pFirst = NULL;<br /> }<br /> NodeList::~NodeList()<br /> {<br /> Node * pTemp;<br /> while(pFirst != NULL)<br /> {<br /> pTemp = pFirst;<br /> pFirst = pFirst->pNext;<br /> delete pTemp;<br /> }<br /> }<br /> void NodeList::AddNode(NodeList::Node *p)<br /> {<br /> Node* pTemp = NULL;<br /> Node* pTempHeader = NULL;<br /> if(p!= NULL)<br /> {<br /> if(pFirst !=NULL)<br /> {<br /> pTemp = pFirst;<br /> pTempHeader = pFirst;<br /> while(pTemp != NULL)<br /> {<br /> if(p->m_start <= pTemp->m_start)<br /> {<br /> p->pNext = pTemp;<br /> pTempHeader->pNext = p;<br /> break;<br /> }<br /> else<br /> {<br /> if(pTemp->pNext !=NULL)<br /> {<br /> pTempHeader = pTemp;<br /> pTemp = pTemp->pNext;<br /> continue;<br /> }<br /> else<br /> {<br /> pTemp->pNext = p;<br /> break;<br /> }<br /> }<br /> }<br /> }<br /> else<br /> {<br /> pFirst = p;<br /> }<br /> }<br /> }<br /> int NodeList::GetNum()<br /> {<br /> int num = 0;<br /> Node *pTemp = pFirst;<br /> while(pTemp != NULL)<br /> {<br /> if(pTemp->pNext != NULL)<br /> {<br /> if(pTemp->m_end < pTemp->pNext->m_start)<br /> {<br /> num += pTemp->Get();<br /> pTemp = pTemp->pNext;<br /> continue;<br /> }<br /> else<br /> {<br /> if(pTemp->m_end < pTemp->pNext->m_end)<br /> {<br /> pTemp->pNext->m_start = pTemp->m_start;<br /> pTemp = pTemp->pNext;<br /> continue;<br /> }<br /> else<br /> {<br /> pTemp->pNext->m_start = pTemp->m_start;<br /> pTemp->pNext->m_end = pTemp->m_end;<br /> pTemp = pTemp->pNext;<br /> continue;<br /> }<br /> }</p> <p> }<br /> else<br /> {<br /> num += pTemp->Get();<br /> break;<br /> }<br /> }<br /> return num;<br /> }</p> <p>int start()<br /> {<br /> NodeList::Node* p = NULL;<br /> NodeList nl;<br /> int L ,m ,start,end;<br /> cout<<"please input int L :/n";<br /> cin>> L;// 总长度<br /> while((L < 1 &&L >10000))<br /> {<br /> cout<<"L is invalid,please retry !";<br /> cin >>L;<br /> }</p> <p> cout<<"please input int m :/n";<br /> cin>> m;// 区域的组数<br /> while((m < 1 &&m >100))<br /> {<br /> cout<<"m is invalid,please retry !";<br /> cin >>m;<br /> }<br /> for(int i =0;i<m;i++)<br /> {<br /> p = new NodeList::Node();<br /> cout<<"please input (start and end ) numofarray :* "<<i+1<<" *"<<endl;<br /> cin >>start;<br /> cin >>end;<br /> if(start >=end &&end > L)<br /> {<br /> cout<< " start or end is invalid ,please retry";<br /> i--;<br /> }<br /> else<br /> {<br /> p->m_start = start;<br /> p->m_end = end;<br /> nl.AddNode(p);<br /> }<br /> }</p> <p> return (L -nl.GetNum());<br /> }<br /> void main()<br /> {<br /> int num = start();<br /> system("cls");<br /> cout<<"剩下树的棵数为 ："<< num <<endl;<br /> }