判断单链表是否有序,并进行排序

原创
2018/11/28 20:31
阅读数 2.1K
#define EMPTY -1;
#define ORDER 0;
#define INORDER 1;

#define ERROR -2;


//判断单联表是否有序,并进行排序
int bubbleSort(LinkedList *&L){
    //count 用来记录节点的个数
    int count = 0;
    //flag表示单链表是否有序的标志
    int flag = 0;
    //冒泡排序的内部循环的i计数器
    int innercount = 0;
    
    LinkedNode *p = L->next->next;
    LinkedNode *q = L->next;        //q指向p的前一个节点
    LinkedNode *s = p; LinkedNode *t = q; //循环的时候使用
    //健壮性判断
    if(q == NULL)
        return EMPTY;
    if(q != NULL && p == NULL)
        return ORDER;//只有一个元素,是有序的
    
    //程序的第一步,判断有无序,然后j求出单链表的长度,用于进行冒牌排序趟数计算
    
    while(s->next != NULL){
        count++;
        if(t->data > s->data){  //若是前一个元素的z值大于后一个元素,那么无序。
            flag = INORDER;
        }
        t = s;
        s = s->next;
    }
    
    //程序的第二步,若是有序的,直接返回有序即可,若是无序,则进行排序,最后返回无序即可
    if(flag == 0){
        return flag;
        
    }else if(flag == 1){
        //冒泡排序法进行o排序
        for(int i=0; i <= count; i++){//冒泡排序的外层
            innercount = count - i;             //内层排序的趟数
            LinkedNode *s = p; LinkedNode *t = q;
            while(s != NULL){
                //交换元素之间的值
                if(t->data > s->data){
                    t->data = t->data + s->data;
                    s->data = t->data - s->data;
                    t->data = t->data - s->data;
                }
                //指针移动
                t = s;
                s = s->next;
                innercount--;
                if (innercount < 0) {
                    break;
                }
                
            }
        }
        return INORDER;
    }else{
        return ERROR;
    }
}

 

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部