标题:
[原创]单循环链表（请求改进）
[打印本页]
作者:
x86
时间:
2004-10-3 14:12
标题:
[原创]单循环链表（请求改进）
//首先是Link类的实现 #include
template
class Link { public: Elem element; Link *next; Link(const Elem& eleval,Link* nextval=NULL) { element=eleval; next=nextval; } Link(Link
*nextval=NULL){next=nextval;} }; //下面是Llist类的实现 #include"link_h.h" #include
template
class LList { public:// 这里声明为public型，因为private型发现无法访问 ？ Link
* head; Link
* tail; Link
* fence; int leftcnt; int rightcnt; void init() { fence=tail=head=new Link
; head->next=fence; leftcnt=rightcnt=0; } void removeall () { while(head->next!=head) remove2(1); } public: LList () {init();} ~LList() {removeall();} void clear() {removeall(); init();} bool insert(const Elem); bool append(const Elem&); bool remove( Elem&); bool remove2(const Elem&); bool find(const Elem&); void setstart() {if(head==tail) return; fence=head; rightcnt+=leftcnt; leftcnt=0;} void setend() {if(head==tail) return; fence=tail; leftcnt+=rightcnt; rightcnt=0;} void prev(); void next() {if (fence!=tail) {fence=fence->next; leftcnt++; rightcnt--;} else setstart(); } int leftLength() const {return leftcnt;} int rightLength() const {return rightcnt;} bool setPos(int pos); bool getvalue(Elem& it)const{ if (leftcnt==rightcnt==0) return false; it=fence->next->element; return true; } void print ()const; }; template
bool LList
::insert(const Elem item){ fence->next=new Link
(item,fence->next); if(fence==tail) tail=fence->next; fence=fence->next; leftcnt++; return true; } template
bool LList
::append(const Elem& item) { tail=tail->next=new Link
(item,head); rightcnt++; if(fence==head) {fence=head->next; leftcnt++; rightcnt--; } return true; } template
bool LList
::remove( Elem& item){ if(head==tail) return false; Link
* ltemp=fence->next; item=ltemp->element; fence->next=ltemp->next; if (ltemp==tail) {delete ltemp; tail=fence; rightcnt--; return true; } if (ltemp==head) {delete ltemp; head=fence->next; leftcnt--; return true; } delete ltemp; rightcnt--; return true; } template
bool LList
::remove2(const Elem& item) { Link
*temp1=head; if(item<=0||item>(leftcnt+rightcnt)) return false; int i; if(item==1) {fence=head; if(head->next->next==head) {delete head->next; tail=head->next=head; leftcnt--; return true; } if(head->next->next!=head) { Link
* temp5; temp5=head->next; head->next=temp5->next; delete temp5; setstart(); rightcnt--; fence=head->next; rightcnt--; leftcnt++; return true; } } setPos(item-1); remove(i); return true; } template
bool LList
::find(const Elem& item){ Link
* ltemp; ltemp=head; for(int i=1;i
next; if(ltemp->element==item) cout<<"the position is:"<
element<<'\n'; } return true; } template
void LList
::prev(){ Link
* ltemp; ltemp=head; while(ltemp->next!=fence) ltemp=ltemp->next; if(fence==head) setend(); else {fence=ltemp; leftcnt--; rightcnt++; } } template
bool LList
::setPos(int pos){ if ((pos<0)||(pos>(leftcnt+rightcnt))) return false; setstart(); for(int i=0;i
next; rightcnt--; leftcnt++; } return true; } template
void LList
::print() const { Link
* temp; temp=head->next; if(head==tail) {cout<<'|'; return; } while(temp!=fence) { cout<
element<<' '; temp=temp->next; } while(temp==fence) { cout<<' '<
element<<'|'; temp=temp->next;} while(temp!=tail->next) { cout<
element<<' '; temp=temp->next; } } void main(){ LList
intLList; //intLList.print(); cout<<"\n 1. 清除 "; cout<<"\n 2. 插入 "; cout<<"\n 3. 追加 "; cout<<"\n 4. 删除fence后面元素 "; cout<<"\n 5. 删除指定位置的节点 "; cout<<"\n 6. 查找链表元素的位置 "; cout<<"\n 7. 查看该链表当前状态 "; cout<<"\n 8. exit \n"; cout<<" (注:本程序中head指针始终指向一个空内存，清除时不会清除该节点 #_#)\n"; char choice; do{ cout<<"\nplease input your choice:\n"; cin>>choice; switch(choice) { case '1': cout<<"removeall?? Yes or No\n"; char flag; cin>>flag; if(flag=='y') intLList.removeall(); intLList.print(); break; case '2': cout<<"\nPlease input the data:"; int it1; cin>>it1; intLList.insert(it1); intLList.print(); break; case '3': cout<<"plesase input the data you want appand:\n"; int it3; cin>>it3; intLList.append(it3); intLList.print(); break; case '4': cout<<"即将删除fence后面的元素！！！\n"; int it2; intLList.remove(it2); intLList.print(); break; case '5': cout<<"请输入要删除的数据的位置:\n"; cout<<"该数字必须大于0，小于等于"<<(intLList.leftLength()+intLList.rightLength())<<'\n'; int it; cin>>it; intLList.remove2(it); intLList.print(); break; case '6': cout<<"please input the date you want to find:\n"; int it4; cin>>it4; intLList.find(it4); intLList.print(); break; case '7': cout<<"output the information:\n"; cout<<"leftcnt:"<
next->element; cout<<"\nthe tail element is:"<
element; cout<<"\n表头元素:"<
next->next->element; case '8': break; default: cout<<"you input a invalid choice."; } }while(choice!='8'); 觉得程序很是有多余的地方，可是自己已经无法修改了，请批评！！！
欢迎光临 黑色海岸线论坛 (http://bbs.thysea.com/)
Powered by Discuz! 7.2
