线性表
约 461 个字 187 行代码 预计阅读时间 5 分钟
Sequential Linear List 顺序存储线性表(数组)
| typedef struct{
int *data; //指示动态分配数组的指针
int MaxSize; //顺序表最大容量
int length; //顺序表当前容量
} SeqList;
|
- 随机存取，即在 \(O(1)\) 时间内找到第 i 个元素
- 存储密度(存储利用率)高，每个节点只存储数据元素
- 拓展容量不方便
- 插入和删除不方便，需要移动大量元素
- 元素的逻辑顺序与物理顺序相同
Linked List 链表的创建与添加节点
单向链表通常有个 dummy head，因此头指针存放的不是头结点的内容
| typedef struct Node *PtrToNode;
struct Node {
int element
PtrToNode next;
};
PtrToNode a = {0,NULL};
PtrToNode newnode = (PtrToNode)malloc(sizeof(struct Node));
newnode->element = 1;
newnode->next = NULL;
a->next = newnode;
|
Stack 栈
| struct stackrecord{
int maxsize;
int top;
int *array;
};
struct stackrecord stack={Max,0};
stack.array = (int *)calloc(stack.maxsize+1,sizeof(int));
|
以链表的方式实现栈
| struct Node {
int data;
struct Node* next;
};
struct Stack {
int size;
struct Node* top;
};
struct Stack* createStack() {
struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
stack->size = 0;
stack->top = NULL;
return stack;
}
void push(struct Stack* stack, int data) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = stack->top;
stack->top = newNode;
stack->size++;
}
int pop(struct Stack* stack) {
if (stack->size == 0) {
return -1;
}
struct Node* temp = stack->top;
int data = temp->data;
stack->top = temp->next;
free(temp); // temp 的作用就是释放空间
stack->size--;
return data;
}
struct Stack* stack = createStack();
|
顺序栈
指在物理内存上是有序的，元素值的大小不一定有序
Queue 队列
| struct Node {
int data;
struct Node* next;
};
struct Queue {
struct Node *front, *rear;
};
struct Node* newNode(int data) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = data;
temp->next = NULL;
return temp;
}
struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
void enQueue(struct Queue* q, int data) {
struct Node* temp = newNode(data);
if (q->rear == NULL) {
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
int deQueue(struct Queue* q) {
if (q->front == NULL)
return -1;
struct Node* temp = q->front;
int data = temp->data;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
free(temp);
return data;
}
|
Priority Queue 堆
| typedef struct HeapStruct *PriorityQueue; //设为指针形式方便直接在函数中修改值
struct HeapStruct {
int *Elements;
int Capacity;
int Size;
};
// 其实更多以数组的方式实现 左子树：2*index 右子树 2*index+1 父节点 index/2
// 注意，有个dummy head，根节点从index = 1开始
PriorityQueue Initialize(int MaxElements){
PriorityQueue H=(PriorityQueue)malloc(sizeof(struct HeapStruct));
if(H==NULL)
exit(1);
H->Elements=(int*)malloc((MaxElements+1)*sizeof(int));
//留一个空位给dummyhead
if(H->Elements==NULL)
exit(1);
H->Capacity=MaxElements;
H->Size=0;
return H;
}
|
Delete操作
| //进行delete操作，思路是删除最小元素，将队尾元素移至root处，再下滤至符合要求
int DeleteMin(Priority H){
int i,child;
int MinElement,LastElement;
if(isEmpty(H))
return;
MinElement = H->Elements[1];
LastElement = H->Elements[H->Size--];
for(i=1;i*2<=H->Size;i=child){
child = i * 2;
if(child != H->Size && H->Elements[child+1] < H->Elements[child])
child++;
if(LastElement > H->Elements[child])
H->Elements[i] = H->Elements[child];
else
break;
}
H->Elements[i] = LastElement;
return MinElement;
}
|
如果你已经定义过了 PercolateDown 的函数，你也可以直接使用来完成上述 DeleteMin 操作。
| void PercolateDown(int p,PriorityQueue H){
//下滤操作的时间复杂度为树的高度O(h)，minheap情况下大的往下
int min;
int value = H->Elements[p];
while(2*p <= H->Size){
min = 2*p;
if(min+1 <= H->Size && H->Elements[min] > H->Elements[min+1])
//跟子树中较小的比
++min;
if(H->Elements[min] < value){
H->Elements[p] = H->Elements[min];
p = min;
}else
break;
}H->Elements[p] = value;
}
void PercolateUp(int p,PriorityQueue H){
int tmp;
while(p/2 >= 1 && H->Elements[p/2] > H->Elements[p]){
tmp = H->Elements[p/2];
H->Elements[p/2] = H->Elements[p];
H->Elements[p] = tmp;
p = p/2;
}
}
|
由 PercolateDown 可以简化删除步骤如下：
| H->Elements[1] = H->Elements[H->Size--];
PercolateDown(1,H);
|
插入操作
将待插入元素放到最后，然后 PercolateUp 即可
| void Insert(int X,Priority H){
int i;
if(isFull(H)){
return;
}
for(i=++H->Size;H->Elements[i/2]>X;i/=2){ //minHeap的情况
H->Elements[i]=H->Elements[i/2];
}H->Elements[i]=X;
}
|
建堆操作 (调整建堆法)
对于未成堆的Heap，我们一般从\(\lfloor \frac{n}{2} \rfloor\)开始下滤，完成排序，并且时间复杂度为O(n)。
\[T=\sum_1^{h+1} 2^{h+1} -1 -2^h= 2^{h+1} -1-(h+1)=O(n)\]
| for(int i=H->Size/2;i>=1;--i)
PercolateDown(i,H);
|
d-heap
注意，d-heap 指一个节点有 d 个孩子（仍然是完全树）
| child(i,j) = d*(i-1)+2+j;
// i是父亲结点的下标，j是第几个儿子，范围是0~d-1
parent(i) = (i-2+d)/d;
last_have_leaf = (size()+1)/d;
// 这是d-heap最后一个有叶子的结点。在heap里是size()/2)
|
堆排序
利用最大堆最大的元素在根节点的性质，可以对数组进行排序。
具体实现原理为:
- 先将初始的 R[1,...,n] 建立成最大堆，此时是无序堆，而堆顶是最大元素。
- 再将堆顶 R[1] 和最后一个元素 R[n] 交换，由此得到新的无序区 R[1,...,n-1] 与有序区 R[n]。
- 将无序区再次建堆(只用对 R[1] 进行下滤操作即可)，重复上述操作。
- 直到无序区只剩下最后一个元素，可以得到递增序列。