对于无序的链表，还是沿着头结点顺序查找比较好。如果要用二分法查找，则先将该链表进行排序，以下是我用冒泡法对单链表进行的排序：/*单链表排序(mark=1，降序；mark=0，升序)*/void SortList(LNode *L,int mark){int i,j,change=TRUE;ElemType temp;LNode *p=L->next,*q;if(p && (p->next)) //如果单链表长度<2,则不用排序 { for(j=1;j<L->data && change;j++) { change=FALSE; p=L->next; q=p->next; for(i=0;i<L->data-j;i++) { if((q->data>p->data && mark) || (q->data<p->data && (!mark))) { temp=p->data; p->data=q->data; q->data=temp; change=TRUE; } p=q; q=q->next; } } }printf("排序成功\r\n");}/*从链表的第curI个点处开始查找第i个结点，前提:i>curI*/LNode *GetElem2(LNode *L,int curI,int i){LNode *p=L;while(p=p->next) if(i==(++curI)) { return p; }return NULL;}/*对排序后的链表进行二分法查找*/int DichotomyList(LNode *L,ElemType e){LNode *p=L;int cur=0;//cur用来保存当前的位置结点，避免每次定位结点都从头结点开始int left=1,right=L->data;//我定义的链表，其头结点的数据域保存着链表的长度int mid=(left+right)/2;//SortList(L,0);while(left<=right && (p=GetElem2(p,cur,mid))->data!=e){if(p->data>e) {cur=0;p=L;right=mid-1;mid=(left+right)/2;}else {cur=mid;left=mid+1;mid=(left+right)/2;}}if(p->data==e) {printf("find node in %d.\r\n",mid);return mid;}else {printf("find none.\r\n");return 0;}}
