排序算法、链表是否有环、反转、删除结点

折半查找

int search(int *a, int n, int key) {
     int min, max, mid;
     min = 0;
     max = n - 1;
     for (int i = min; i <= max; i ++) {
            mid = (min + max) / 2;
            if (key < a[mid]) {
                max = mid - 1;
            } else if (key > a[mid]) {
                min = mid + 1;
            } else {
               return mid;
            }
    }
    return -1;
}

冒泡排序

void sort0(int *a, int n) {
   for (int i = 0; i < n; i ++) {
         for (int j = 0; j < n - i - 1; j ++) {
              if (a[i] > a[j]) {
                  int temp = a[i];
                  a[i] = a[j];
                  a[j] = temp;
            }
       }
  }
}

选择排序

void sort1(int *a, int n) {
   for (int i = 0; i < n; i ++) {
         int tag = i;
         for (int j = 0; j < n - i; j ++) {
               if (a[tag] > a[j]) {
               tag = j;
               }
         }
         if (tag != i) {
             int temp = a[i];
             a[i] = a[tag];
             a[tag] = temp;
         }
     }
}

插入排序

void sort2(int *a, int n) {
    int i, j;
    for (i = 2; i < n; i ++) {
          if (a[i - 1] > a[i]) {
              a[0] = a[i];      // 其中a[0]为标志位
              for (j = i - 1; a[j] > a[0]; j--) {
                   a[j + 1]  = a[j];
              }
              a[j + 1] = a[0];
           }
       }
}

判断一个链表是否有环

#define Len 8
typedef int ElemType;       // 假定数据类型为int
typedef struct Node {
   ElemType data;
   struct Node *next;
} Node, *LinkList;            // 定义链表中节点类型，包含一个数据域与指针域
// 判断方式：使用两个指针p1,p2从链表头开始遍历，p1每次前进一步，p2每次前进两步。如果p2到达链表尾部，
   //说明无环，否则p1、p2必然会在某个时刻相遇(p1==p2)，从而检测到链表中有环。
int hasLoop(LinkList L) {
 LinkList p, q;
 p = L;
 q = L;
 while (p && q) {
        p = p->next;
        q = q->next;
        if (q) {
            q = q->next;
        }
        if (p && p == q) {
            return 1;
        }
 }
 return 0;
}

链表反转

//  需要三个指针，记录当前节点、前一个节点、后一个节点
LinkList reverseList(LinkList *L) {
   LinkList pre, cur, next;
   pre = *L;
   cur = pre->next;
   next = NULL;
   pre->next = NULL;
   while (cur) {
         next = cur->next;
         cur->next = pre;
         pre = cur;
         cur = next;
    }
    return pre;
}

链表删除结点方法：

• 只给定单链表中某个结点p(并非最后一个结点，即p->next!=NULL)指针，删除该结点。
  办法很简单，首先是放p中数据,然后将p->next的数据copy入p中，接下来删除p->next即可。

• 只给定单链表中某个结点p(非空结点)，在p前面插入一个结点。
  办法与前者类似，首先分配一个结点q，将q插入在p后，接下来将p中的数据copy入q中，然后再将要插入的数据记录在p中。