折半查找
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中。
