严蔚敏书中的线性表实现代码
时间: 2024-10-04 16:01:42 浏览: 4
《算法导论》作者Thomas H. Cormen(并非严蔚敏,但假设你在谈论同名书籍)书中关于线性表的实现通常会涉及到两种常见方法:数组实现(顺序表)和链表实现(链接表)。
**数组实现(顺序表)**:
```c
typedef struct {
int* elements; // 存放元素的数组
int length; // 当前元素的数量
int capacity; // 数组容量
} ArrayBasedList;
void array_based_list_init(ArrayBasedList* list) {
list->elements = malloc(sizeof(int) * list->capacity);
list->length = 0;
list->capacity = DEFAULT_CAPACITY;
}
// 插入、删除、查找等操作会涉及数组内的元素移动,时间复杂度较高
```
**链表实现(链接表)**:
```c
typedef struct ListNode {
int value;
struct ListNode* next;
} ListNode;
typedef struct LinkedList {
ListNode* head;
int length;
} LinkedList;
void linked_list_init(LinkedList* list) {
list->head = NULL;
list->length = 0;
}
// 链表操作通常是常数时间O(1),比如插入和删除只需更改相应节点的指针
void insert_at_head(LinkedList* list, int value) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
newNode->value = value;
newNode->next = list->head;
list->head = newNode;
list->length++;
}
```
注意:上述代码简化了示例,实际项目中需要考虑内存管理和其他细节。