数组和链表¶
数组¶
链表¶
- 定义： 链表(linked list): 链表由一系列不必在内存中相连的结构组成。每个结构均含有表元素和指向包含该元素后继元的结构指针，称之为next 指针。最后一个单元的next指针指向NULL ;该值由C定义并且不能与其他指针混淆。ANSIC中规定NULL为零。
-
组成结构 链表的组成单位是「节点 node」对象。每个节点都包含两项数据：节点的“值”和指向下一节点的“引用”。
-
链表的首个节点被称为“头节点”（header），最后一个节点被称为“尾节点”。
- 尾节点指向的是“空”，
- 在 C、C++、Go 和 Rust 等支持指针的语言中，上述的“引用”应被替换为“指针”。
常用操作¶
由于链表的不连续性，防止链表丢失“头”节点。
链表类型¶
List Reverse( List L)
{
List head, p, s;
if (L->Next == NULL)
{
return L;
}
head = L;
s = L->Next;
L = s->Next;
while(L!= NULL)
{
p = L->Next;
L->Next = s;
s = L;
L = p;
}
head->Next->Next = NULL;
head->Next = s;
return head;
}
栈与对列¶
栈¶
常见操作¶
| 方法 | 描述 | 时间复杂度 |
|---|---|---|
push() |
元素入栈（添加至栈底） | \(O(1)\) |
pop() |
栈顶元素出栈 | \(O(1)\) |
peek() |
访问栈顶元素 | \(O(1)\) |
栈的实现¶
基于链表¶
/* 基于链表实现的栈 */
typedef struct
{
ListNode *top; // 将头节点作为栈顶
int size; // 栈的长度
} LinkedListStack;
/* 构造函数 */
LinkedListStack *newLinkedListStack()
{
LinkedListStack *s = malloc(sizeof(LinkedListStack)); //用malloc()分配内存空间
s->top = NULL;
s->size = 0;
return s;
}
/* 析构函数 */
void delLinkedListStack(LinkedListStack *s)
{
while (s->top)
{
ListNode *n = s->top->next;
free(s->top);
s->top = n;
}
free(s);
}
/* 获取栈的长度 */
int size(LinkedListStack *s)
{
assert(s);
return s->size;
}
/* 判断栈是否为空 */
bool isEmpty(LinkedListStack *s)
{
assert(s);
return size(s) == 0;
}
/* 访问栈顶元素 */
int peek(LinkedListStack *s)
{
assert(s);
assert(size(s) != 0);
return s->top->val;
}
/* 入栈 */
void push(LinkedListStack *s, int num)
{
assert(s);
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->next = s->top; // 更新新加节点指针域
node->val = num; // 更新新加节点数据域
s->top = node; // 更新栈顶
s->size++; // 更新栈大小
}
/* 出栈 */
int pop(LinkedListStack *s)
{
if (s->size == 0)
{
printf("stack is empty.\n");
return INT_MAX;
}
assert(s);
int val = peek(s);
ListNode *tmp = s->top;
s->top = s->top->next;
// 释放内存
free(tmp);
s->size--;
return val;
}
基于数组¶
/* 基于数组实现的栈 */
typedef struct {
int *data;
int size;
} ArrayStack;
/* 构造函数 */
ArrayStack *newArrayStack() {
ArrayStack *s = malloc(sizeof(ArrayStack));
// 初始化一个大容量，避免扩容
s->data = malloc(sizeof(int) * MAX_SIZE);
s->size = 0;
return s;
}
/* 获取栈的长度 */
int size(ArrayStack *s) {
return s->size;
}
/* 判断栈是否为空 */
bool isEmpty(ArrayStack *s) {
return s->size == 0;
}
/* 入栈 */
void push(ArrayStack *s, int num) {
if (s->size == MAX_SIZE) {
printf("stack is full.\n");
return;
}
s->data[s->size] = num;
s->size++;
}
/* 访问栈顶元素 */
int peek(ArrayStack *s) {
if (s->size == 0) {
printf("stack is empty.\n");
return INT_MAX;
}
return s->data[s->size - 1];
}
/* 出栈 */
int pop(ArrayStack *s) {
if (s->size == 0) {
printf("stack is empty.\n");
return INT_MAX;
}
int val = peek(s);
s->size--;
return val;
}
队列¶
常见操作¶
| 方法 | 描述 | 时间复杂度 |
|---|---|---|
push() |
元素入队（添加至队尾） | \(O(1)\) |
pop() |
队首元素出队 | \(O(1)\) |
peek() |
访问队首元素 | \(O(1)\) |
队列的实现¶
1.基于链表的实现¶
2. 基于数组的实现¶
哈希表¶
哈希表¶
「哈希表 hash table」，又称「散列表」，其通过建立键 key 与值 value 之间的映射，实现高效的元素查询。具体而言，我们向哈希表输入一个键 key ，则可以在 \(O(1)\) 时间内获取对应的值 value 。
常见操作¶
初始化、查询操作、添加键值对和删除键值对。
数组实现¶
哈希函数：
1. 通过某种哈希算法 hash() 计算得到哈希值。
2. 将哈希值对桶数量（数组长度）capacity 取模，从而获取该 key 对应的数组索引 index 。
index = hash(key) % capacity
Supplement from Textbook¶
抽象数据类型（ADT）：并（union），交（intersction）,求大小（size）,取余数（complement）
表ADT(List)¶
Definition¶
链表(linked list): 链表由一系列不必在内存中相连的结构组成。每个结构均含有表元素和指向包含该元素后继元的结构指针，称之为next 指针。最后一个单元的next指针指向NULL ;该值由C定义并且不能与其他指针混淆。ANSIC中规定NULL为零。
栈ADT(Stack)¶
Definition¶
- Stack: A stack is a list with the restriction that inserts and deletes can be performed in only one position.
- Top: the end of the list called the top.
- Push: The fundamental operations on a stack are push, which is equivalent to an insert,
-
pop: pop deletes the most recently inserted element.
-
The most recently inserted element can be examined prior to performing a pop by use of the top routine.
-
Error: A pop or top on an empty stack is generally considered an error in the stack ADT. On the other hand, running out of space when performing a push is an implementation error but not an ADT error.