二分（折半）查找，冒泡、选择、插入排序，判断链表是否有环、链表反
// 折半查找
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]为标志位
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; // 定义链表中节点类型，包含一个数据域与指针域
// 判断方式：需要用到两个指针，一开始都指向头结点，之后一个指针每次走一步，另外一个指针每次走两步，然后此时判断两个指针是否指向同一个节点，以此推出链表是否有环
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;
}
