// 折半查找
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 = i + 1; j < n; 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 = i + 1; j < n; 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]為標(biāo)志位
? ? ? ? ? ? ? ? ? for (j = i - 1; a[j] > a[0]; j--) {
? ? ? ? ? ? ? ? ? ? ? ?a[j + 1]? = a[j];
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? a[j + 1] = a[0];
? ? ? ? ? ? ? ?}
? ? ? ? ? ?}
}
// 判斷一個鏈表是否有環(huán)
#define Len 8
typedef int ElemType; ? ? ? // 假定數(shù)據(jù)類型為int
typedef struct Node {
? ? ? ?ElemType data;
? ? ? ?struct Node *next;
} Node, *LinkList; ? ? ? ? ? ?// 定義鏈表中節(jié)點類型，包含一個數(shù)據(jù)域與指針域
// 判斷方式：需要用到兩個指針，一開始都指向頭結(jié)點，之后一個指針每次走一步，另外一個指針每次走兩步，然后此時判斷兩個指針是否指向同一個節(jié)點，以此推出鏈表是否有環(huán)
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;
}
//? 鏈表反轉(zhuǎn)
//? 需要三個指針，記錄當(dāng)前節(jié)點、前一個節(jié)點、后一個節(jié)點
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;
}
