顺序表

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct vector {
	int size, count;
	int *data;
} vector;

// 创建
vector *getNewVector(int n) {
	vector *p = (Vector *)malloc(sizeof(vector));
	p->size = n;
	p->count = 0;
	p->data = (int *)malloc(sizeof(int) * n);
	return p;
}

// 扩容
int expand(vector *v) {
	if (v == NULL) return 0;
	printf("expand v from %d to %d\\n", v->size, 2 * v->size);
	int *p = (int *)realloc(v->data, sizeof(int) * 2 * v->size);
	if (p == NULL) return 0;
	v->data = p;
	v->size *= 2;
	return 1;
}

// 插入
int insert(vector *v, int pos, int val) {
	if (pos < 0 || pos > v->count) return 0;
	if (v->size == v->count && !expand(v)) return 0;
	for (int i = v->count - 1; i >= pos; i--) {
		v->data[i + 1] = v->data[i];
	}
	v->data[pos] = val;
	v->count += 1;
	return 1;
}

// 删除
int erase(vector *v, int pos) {
	if (pos < 0 || pos >= v->count) return 0;
	for (int o = pos + 1; i < v->count; i++) {
		v->data[i - 1] = v->data[i];
	}
	v->count -= 1;
	return 1;
}

// 打印
void output_vecotr(vector *v) {
	int len = 0;
	for (int i = 0; i < v->size; i++) {
		len += printf("%3d", i);
	}
	printf("\\n");
	for (int i = 0; i < len; i++) printf("-");
	printf("\\n");
	for (int i = 0; i < v->count; i++) {
		printf("%3d", v->data[i]);
	}
	printf("\\n\\n\\n");
	return;
}

// 释放
void clear(vector *v) {
 if (v == NULL) return;
 free(v->data);
 free(v);
 return;
}

int main() {
	srand(time(0));
	#define MAX_OP 20
	vector *v = getNewVecotr(MAX_OP);
	for (int i = 0; i < MAX_OP; i++) {
		int op = rand() % 4, pos, val, ret;
		switch (op) {
			case 0:
			case 1:
			case 2:
				pos = rand() % (v->count + 2);
				val = rand() % 100;
				ret = insert(v, pos, val);
				printf("insert %d at %d to vector = %d\\n",
					val, pos, ret);
				break;
			case 3:
				pos = rand() % (v->count + 2);
				ret = erase(v, pos);
				printf("erase item at %d in vector = %d\\n",
					pos, ret);
				break;
		}
		output_vecotr();
	}
	return 0;
}

链表

结构定义：

• 若干个节点串联在一起
• 每个节点存储两部分信息，数据信息和指向下一个节点的指针信息

结构操作：

• 删除、插入
• 错误的插入会导致内存泄露

无头链表和有头链表：

• 无头链表：头部节点不存储数据信息；
• 有头链表：头部节点有存储数据信息的区域，但不使用。

有头链表的头部节点称为虚拟头节点。