双循环链表的各种操作

//#include \# include # include using namespace std; class node {

public: node (){};//初始化 node (string na,int nu,node * p,node * q):name(na),number(nu),next(p),prior(q){};//初始化 void creat_list(node * const);//链表的建立，只需要输入头节点地址 void transverse_list(node * const)//链表的遍历，即输出各个元素的值 bool isempty_list(node * const);//判断链表是否为空 bool insert_list(node * const,const int);//在第 i（从1开始）位置插入一个节点 int length_list(node * const);//链表的长度，（从1开始计算） void delete_list(node * const,int);//删除第i个基点（从1开始计算） node * ptail(node * const);//输入尾节点地址 void quicksort_list(node * const,node *,int,node *,int);//安找number对链表快速排序 node * first(node * const);//首节点地址 int halfsearch_list(node * const,node * left,int begin,node * right,int end,int val); //二分查找节点中学号为val的节点位置，从1开始计算 private: string name;//姓名 int number;//学号 node * next; node * prior; };

int node::halfsearch_list(node * const head,node * left,int begin,node * right,int end,int val) { int i=begin,j=end; int mid=(i+j)/2;//取中点 node * p=left,*q=right; node * half=head;

for(int k=0;knext; } if(i==j)//i==j时说明已经找完链表，只有两种情况，找到或者没找到 {

if(val==half->number)//找到 return i; else return -1; } if(i

{ if(half->number>val)//如果中点的number比val大，说明val在mid的左边 { j=mid-1;

q=half->prior;//最右边的地址应该挪到中间节点的左边 } else if(half->numbernext; } else//如果中点的number和val相等，说明该节点就是查找的节点 { i=mid; j=mid; p=half; q=half; } halfsearch_list(head,p,i,q,j,val);//递归 } }

node * node::first(node * const head)//返回首节点的地址 { return head->next;//头节点的下个节点即是首节点 }

void node::quicksort_list(node * const head,node * left,int begin,node * right,int end) {

int i=begin,j=end; node * p=left,*q=right; int number=p->number;//将左边节点的姓名和学号进行复制 string name=p->name; if(i

while(inumber>number)//如果右边的学号比复制的学号大，一直左移，知道比他小 { j--; q=q->prior; } if(i

p->name=q->name; p->number=q->number; i++; p=p->next; } while(inumbernext; } if(iname=p->name; q->number=p->number; j--; q=q->prior; } } q->name=name;//将复制的东西放在中间 q->number=number; quicksort_list(head,left,begin,p,i);//左边递归 quicksort_list(head,p->next,i+1,right,end);//右边递归 } }

node * node::ptail (node * const head)//返回尾节点 { node * p=head->next; while(p->next!=head->next) p=p->next; return p; }

void node::delete_list(node * const head,int pos)//删除序号为pos的节点（从1开始） { if(isempty_list(head))//判断链表是否为空 { cout<<\链表为空，程序结束！\ exit(1); } node * p=head; node * tail=head->next; while(tail->next!=head->next) tail=tail->next;