hmmmm 我没朋友，也开不起玩笑。 -- 延续插排的概念...作业五的构成 脑袋还没空掉的话，链结可以当成是一套随时变动长度的阵列 在基本盘来说，能用链结串列来做插排确实会比用阵列来得符合概念 只是实做上复杂性比较高一点，建立过程问题比较多，昨天抓个首项bug玩掉一小时(倒 好...再来先做个接下来用的表格说明 正确的长度会随着说明一个一个冒出来，这里先当做做出十个了 ┌—┬—┬—┬—┬—┬—┬—┬—┬—┬—┐ ｜０｜１｜２｜３｜４｜５｜６｜７｜８｜９｜ ←建立顺、ID，两者相同 ├—┼—┼—┼—┼—┼—┼—┼—┼—┼—┤ ｜０｜１｜２｜３｜４｜５｜６｜７｜８｜９｜ ←串列内顺序 ├—┼—┼—┼—┼—┼—┼—┼—┼—┼—┤ ｜１｜１｜２｜４｜６｜８｜９｜10｜80｜99｜ ←分数内容 └—┴—┴—┴—┴—┴—┴—┴—┴—┴—┘ : 类别部分采前文用的名字、内容 -- 先来说明实作法，有其他概念再谈hmm 这边随意排几组 ┌—┐ ┌—┐ ┌—┐ ┌—┐ ┌—┐ ｜０｜ ｜３｜ ｜１｜ ｜２｜ ｜４｜ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ｜０｜ ｜１｜ ｜２｜ ｜３｜ ｜４｜ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ｜１｜ ｜３｜ ｜６｜ ｜８｜ ｜９｜ └—┘ └—┘ └—┘ └—┘ └—┘ 现在假设有第５个、４要插入，就沿着串列顺序去找大於４的那一个 确认是顺序在２的１比较大，就把５的指标指向１(顺序２)、３指向５ (５取代成为第２项、後面的跟着自动会往後退一个顺序) 变成是 -- 插入 ↓ ┌—┐ ┌—┐ ┌—┐ ┌—┐ ┌—┐ ┌—┐ ｜０｜ ｜３｜ ｜５｜ ｜１｜ ｜２｜ ｜４｜ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ｜０｜ ｜１｜ ｜２｜ ｜３｜ ｜４｜ ｜５｜ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ├—┤ ｜１｜ ｜３｜ ｜４｜ ｜６｜ ｜８｜ ｜９｜ └—┘ └—┘ └—┘ └—┘ └—┘ └—┘ 我不想多挤一行写指向的下一项，所以就请稍微心领神会 每一个指向的下一项就看编号顺 -- 首先，在开始时是NULL，只建立几个aclass *p指标准备 或是你喜欢也能先new个位址给指标 我自己是试着整套用同个逻辑走，都放在回圈内生成 int main(){ aclass *p,*head,*tmp; } 这里三个指标，一个用来做运作(p)，一个用来指示起始点(head) tmp主要用来记录前一项的位址，因为p一定会像前面例子跑到２，抓不到前一个１在哪 : 有另外建立前项指标的写法另论 再来进每次输入、生成的部份...因为无聊，所以写成跟阵列的范例一样没有最大上限 这里用while制作 刚进回圈，一样先不要管类别部份 我们就先接受id、grade後再研究要干嘛 while(true){ int id,grade; cin>>id >>grade; } -- 针对第一项输入没有前後、内容，当作一个特例处理，在while之前设一个bool标记第一次 其他就照常输入就好 bool start=true; while(true){ int id,grade; cin>>id >>grade; if (start){ start = false; p = head = new aclass; p->setid(id); p->setgrade(grade); p->setptr(NULL); } else{ } } 然後是之後开始输入的每一项，都在else内处理 -- 从第二项开始，因为都不确定应该插在哪 因此从头开始沿着串列比大小，把p跟tmp一起归零回到第一项 开始沿着过程比大小，找出从哪个地方开始比输入来得大 寻找要从哪里插入 else{ p=tmp=head; while (true) { if (grade < p->getgrade()) break; else { tmp=p; if (p->getptr()==NULL) break; p=p->getptr(); } } -- 因为每次都是确定p->getgrade()小於输入後tmp才变为p 一旦发现有比输入值来得大的，或是一路没有比输入值来得小的数值就跳出 所以整个回圏结束时，tmp的位置一定会刚好是要插入的前一项 : 这部份不懂就多画几次图，搞不懂来问我也无妨...我会看是谁决定怎样说明 知道要插在哪项之後就很简单... new个物件给p、把东西装装进去就是了 然後替换一下指标指向位址就好 p = new aclass; p->setid(id); p->setgrade(grade); p->setptr(tmp->getptr()); tmp->setptr(p); -- 就这样...插入结束後就把内容印出来看有没有问题 p=head; while (true){ cout <<p->getid() <<'\t' <<p->getgrade() <<'\n'; if (p->getptr()==NULL) break; p=p->getptr(); } 嗯...上面这样算写完八成左右 残余会出现一个bug，在第一项变成新的输入值时会出错 会插入到第二项，而不是第一项 为了这点，我是再针对这个特例做处理 在前面侦测要插入在哪的地方多加一点变数判断 -- 加个bool记录一下是不是第一项需要换 else{ p=tmp=head; bool first=true; while (true) { if (grade < p->getgrade()) break; else { first=false; tmp=p; if (p->getptr()==NULL) break; p=p->getptr(); } } -- 再来随着这个判断 将配置物件内指标指向的地方做一点修改 避免因为first判断让程式误认为只要是first都要摆到第一项前 在判断式确定应该在前或在後 p = new students; p->setid(id); p->setgrade(grade); if (first && grade<tmp->getgrade()) { p->setptr(tmp); head = p; } else { p->setptr(tmp->getptr()); tmp->setptr(p); } 这样就算完成....大概吧 -- 完整内容大概就这样 #include<iostream> using namespace std; class students{ public: int getid(); int getgrade(); students* getptr(); void setid(int ID); void setgrade(int GRADE); void setptr(students *PTR); private: int id; int grade; students *ptr; }; void students::setid(int ID){id=ID;}; void students::setgrade(int GRADE){grade=GRADE;}; void students::setptr(students *PTR){ptr=PTR;}; int students::getid(){return id;}; int students::getgrade(){return grade;}; students* students::getptr(){return ptr;}; int main() { students *p,*head,*tmp; bool start=true; while(true){ int id,grade; cin>>id >>grade; if (start){ p = head = new students; p->setid(id); p->setgrade(grade); p->setptr(NULL); start=false; } else{ p=tmp=head; bool first=true; while (true) { if (grade < p->getgrade()) break; else { first=false; tmp=p; if (p->getptr()==NULL) break; p=p->getptr(); } } p = new students; p->setid(id); p->setgrade(grade); if (first && grade<tmp->getgrade()) { p->setptr(tmp); head = p; } else { p->setptr(tmp->getptr()); tmp->setptr(p); } } p=head; while (true){ cout <<p->getid() <<'\t' <<p->getgrade() <<'\n'; if (p->getptr()==NULL) break; p=p->getptr(); } } } -- 所恐惧的，不是没有知识的大众　 所憎恨的，不是深沉幽暗的人心 而是自以为是的思考之声 而是自恃甚高的执法者 所毁灭的，不是温馨和谐的世界 这是我最後的期许，没有愤怒、没有悔恨 而是自欺欺人的梦境 只剩下，浑沌的死亡呼吸 　　　　　　　　　　　　　　 节自　新月神话－弑王者 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 58.114.76.199 小修个BUG ※ 编辑: game0416 来自: 120.127.47.93 (03/22 10:15)