顺序表及其结构定义
(1)结构定义
- 顺序存储:
- 顺序表的元素按顺序存储在一块连续的内存区域中,每个元素占用相同大小的存储空间。
- 通过数组实现,每个元素可以通过下标快速访问。
- 存储密度高:
- 因为顺序表使用连续的内存空间,所以其存储密度很高,没有额外的指针存储开销。
- 随机访问:
- 顺序表支持O(1)时间复杂度的随机访问,可以通过下标直接访问任意位置的元素。
- 访问时间复杂度:O(1)。
- 动态性:
- 顺序表通常预留一定的存储空间来处理动态增长,但在容量不足时需要扩展数组。
- 扩展数组时需要重新分配一块更大的连续内存,并将现有元素复制到新内存区域中。
- 插入和删除操作:
- 空间浪费问题:
- 如果顺序表预留了过多的空间而未使用,会导致空间浪费。
- 如果预留的空间不足,需要频繁扩展数组,会导致性能下降。
顺序表代码实现
#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, v->size * 2);int *p = (int *)realloc(v->data , sizeof(int) * v->size * 2);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 i = pos + 1; i < v->count; i++) {v->data[i - 1] = v->data[i];}v->count -= 1;return 1;
}void clear(vector *v) {if (v == NULL) return ;free(v->data);free(v);return ;
}void output_vector(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 ;
}int main() {srand(time(0));#define MAX_OP 20 vector *v = getNewVector(2);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_vector(v);}clear(v);return 0;
}
链表及其结构定义
链表是一种灵活的线性数据结构,与数组(顺序表)相比具有许多不同的性质。以下是链表的主要结构性质:
-
动态内存分配
-
节点结构
-
节点组成:链表由一系列节点组成,每个节点包含数据部分和指针部分。数据部分存储实际的数据,指针部分用于指向下一个节点(或前后节点)。
typedef struct Node {int data;struct Node *next; } Node;
-
-
顺序访问
-
插入和删除操作
- 高效操作:插入和删除操作在链表任意位置的时间复杂度为O(1),只需修改相关指针。不需要像数组那样移动大量数据,因此在处理动态数据时效率较高。
5. 指针操作
不同类型的链表特性
-
单向链表
-
双向链表
-
双向链接:每个节点包含一个指向下一个节点的指针和一个指向前一个节点的指针。
-
双向访问:可以从任意节点方便地访问其前驱节点和后继节点。
-
额外开销:每个节点需要额外的空间存储前驱节点的指针。
typedef struct DNode {int data;struct DNode *prev;struct DNode *next; } DNode;
-
-
循环链表
-
链表的应用场景
-
链表的缺点
单链表代码实现
#include<stdio.h>
#include<stdlib.h>
#include<time.h>typedef struct Node {int data;struct Node *next;
}Node;Node *getNewNode(int val) {Node *p = (Node *)malloc(sizeof(Node));p->data = val;p->next = NULL; return p;
}Node *insert(Node *head, int pos, int val) {Node new_head, *p = &new_head, *node = getNewNode(val);new_head.next = head;for (int i = 0; i < pos; i++) p = p->next;node->next = p->next;p->next = node;return new_head.next;
}void clear(Node *head) {if (head == NULL) return ;for (Node *p = head, *q; p; p = q) {q = p->next;free(p);}return ;
}void output_linlist(Node *head, int flag) {int n = 0; for (Node *p = head; p; p = p->next) n += 1;for (int i = 0; i < n; i++) {printf("%3d", i);printf(" ");}printf("\n");for (Node *p = head; p; p = p->next) {printf("%3d", p->data);printf("->");}printf("\n");if (flag == 0) printf("\n\n");return ;
}int find(Node *head, int val) {Node *p = head;int n = 0;while (p) {if (p->data == val) {output_linlist(head, 1);int len = 5 * n + 2;for (int i = 0; i < len; i++) printf(" ");printf("^\n");for (int i = 0; i < len; i++) printf(" ");printf("|\n");return 1;}n++;p = p->next;}return 0;
}int main() {srand(time(0));#define MAX_OP 10Node *head = NULL;for (int i = 0; i < MAX_OP; i++) {int pos = rand() % (i + 1), val = rand() % 100, ret;printf("insert %d at %d to linklist\n", val, pos);head = insert(head, pos, val);output_linlist(head, 0);}int val;while (~scanf("%d", &val)) {if (find(head, val) == 0) {printf("not found\n");}}clear(head);return 0;
}``