课堂实验--找水王
熟悉的课堂实验没有一点点防备的就回归了！虽然这几周过的很轻松，但是没有编程的日子还是有那么一点点枯燥的，有时候忙碌也是一种享受生活的方式。
一、设计思想
这次实验一开始其实我是很茫然的，因为我不去贴吧，也不懂贴吧的一些规则，但是在老师慢慢的解说下我便明白了。简单的理解就是一组一维数组，其中的数随机，但是其中有一个数出现次数超过了一半以上。在老师的提示下我有了大致思路。我抓住了“超过一半”这个核心，若这个数在数组中超过一半，那么这其中剩下的数就可以和这个数相互抵消掉，最后剩下的就是这个“水王”。那么怎么让这些数抵消掉呢，老师在课堂上提到了相邻的两两比较，若相同则留下一个，若不相同则全部消掉。这样将那些不相同的部分抵消掉则就剩下水王了。
在这个过程中需要将中间不相同的数删除掉，慢慢迭代找到水王，考虑到数组长短的不确定，避免数组间传值的复杂，我尝试运用数据结构中链表的知识，由于它删除节点之后通过遍历又可以很快的组成新的一维数组，于是我选择了数据结构中的链表结构。在每一级链表中相邻的两个数进行上述操作，最后剩下的数便是水王。
二、代码实现
//Hao Ying 2016/5/18 //找出贴吧中的水王 #include<iostream> using namespace std; typedef struct node//定义链表中的成员 { int arr;//链表中的节点 struct node *pNext;//指向下一节点的指针 }Node,*pNode; pNode CreateList(int);//创建链表 int deledata(pNode,int);//删除链表 int Returnval(pNode,int);//返回ID值 int traver(pNode);//遍历重整 int main() { int i=0,num,num1; pNode pHead=NULL;//定义初始化头结点 cout<<"请输入帖子数（一维数组的长度）："; cin>>num; num1=num; pHead=CreateList(num); traver(pHead); do { if(num1=3)//若出现三个数中前两个数相同导致剩下两个数无法判断水王的情况，则跳出循环，令第一个节点成为水王 if(Returnval(pHead,0)==Returnval(pHead,1)) break; for(i=0;i<num1/2;i=i+2)//从第一个节点起相邻两个数进行比较 { if(Returnval(pHead,i)!=Returnval(pHead,i+1))//若两数不相同则将两个节点同时删除 { deledata(pHead,i); deledata(pHead,i+1); } else//若两数相同则保留前者 { deledata(pHead,i); } } num1=traver(pHead); }while(num1!=1);//循环直到链表中只剩下一个数为止 cout<<"该贴吧的水王为："<<Returnval(pHead,0)<<endl; return 0; } pNode CreateList(int num)//创建链表函数 { int i,val;//i用于循环，val存放链表相应位置的值 cout<<"请输入一组帖子ID（一维数组）："; pNode pHead=(pNode)malloc(sizeof(Node));//分配一个不存放有效数据的头结点 pNode pTail=pHead; pTail->pNext=NULL;//尾指针指向空 for(i=0;i<num;i++) { cin>>val; pNode pNew=(pNode)malloc(sizeof(Node));//为节点分配空间 pNew->arr=val;//将值赋予节点成员 pTail->pNext=pNew;//尾指针指向新节点 pNew->pNext=NULL;//新节点指针置为空 pTail=pNew;//新节点赋予最后一个节点 } return pHead; } int deledata(pNode pHead,int back)//删除节点函数 { int i=0,data; pNode _node=pHead; pNode pSwap; while(i<back-1) { _node=_node->pNext; ++i; } pSwap=_node->pNext; data=pSwap->arr; _node->pNext=_node->pNext->pNext; free(pSwap); return data; } int Returnval(pNode pHead,int num1)//返回节点值函数 { int i=0,data; pNode _node=pHead; pNode pval; while(i<num1) { _node=_node->pNext; ++i; } pval=_node->pNext; data=pval->arr; return data; } int traver(pNode pHead)//遍历函数 { int i=0; pNode p=pHead->pNext; while(NULL!=p) { p=p->pNext; ++i; } return i; }
在和同学
三、实现截图
当长度为5时：
当长度为3时：
当长度为10时：
四、个人总结
通过这次的实验我有很多的收获，之前编程一直都用c++，几乎都快忘了该如何运用数据结构的知识来编程了，通过这次对链表的运用，使我又熟悉了对链表的创建以及对链表删除的知识有了新的认识，其实之前一直不敢用数据结构的知识，尤其是涉及到指针就更加难上加难了，在这次实验时虽然遇到了很多问题，比如说访问链表发生冲突，以及如何正确返回链表中相应的正确值的时候出现了错位的情况，但是通过努力最终完成了这次实验，虽然不知道这个方法算不算是最快的方法，但是按照老师的思路我觉得要比记录数字出现次数的方法要快的多，虽然有很多不足之处，希望在以后的实验中多加努力，锻炼自己的能力，使得自己的编程能力得到更多的提升！。