顺序表与链表学习笔记

顺序表及其结构定义

（1）结构定义

• 顺序存储：
  • 顺序表的元素按顺序存储在一块连续的内存区域中，每个元素占用相同大小的存储空间。
  • 通过数组实现，每个元素可以通过下标快速访问。
• 存储密度高：
  • 因为顺序表使用连续的内存空间，所以其存储密度很高，没有额外的指针存储开销。
• 随机访问：
  • 顺序表支持O(1)时间复杂度的随机访问，可以通过下标直接访问任意位置的元素。
  • 访问时间复杂度：O(1)。
• 动态性：
  • 顺序表通常预留一定的存储空间来处理动态增长，但在容量不足时需要扩展数组。
  • 扩展数组时需要重新分配一块更大的连续内存，并将现有元素复制到新内存区域中。
• 插入和删除操作：
  • 在顺序表的末尾进行插入和删除操作的时间复杂度为O(1)。
  • 在顺序表的中间或开头进行插入和删除操作的时间复杂度为O(n)，因为需要移动大量元素以保持连续存储。
• 空间浪费问题：
  • 如果顺序表预留了过多的空间而未使用，会导致空间浪费。
  • 如果预留的空间不足，需要频繁扩展数组，会导致性能下降。

顺序表代码实现

#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;

• 顺序访问

  • 线性访问：链表不支持随机访问，只能从头节点开始顺序访问每个节点。访问第n个节点的时间复杂度为O(n)。
  • 指针操作：链表操作依赖于指针，需要进行频繁的指针操作（如指针的赋值和修改）。

• 插入和删除操作

  • 高效操作：插入和删除操作在链表任意位置的时间复杂度为O(1)，只需修改相关指针。不需要像数组那样移动大量数据，因此在处理动态数据时效率较高。

  5. 指针操作

  • 复杂性：链表的操作依赖于指针，需要进行频繁的指针操作（如指针的赋值和修改）。指针操作复杂度较高，容易出错。
  • 额外空间：链表每个节点需要额外的指针空间，与数组相比，链表有一定的空间开销。

不同类型的链表特性

• 单向链表

  • 单向链接：每个节点包含一个指向下一个节点的指针。

  • 末尾节点：链表末尾的节点指针为NULL，表示链表的结束。

    typedef struct Node {int data;struct Node *next;
    } Node;

• 双向链表

  • 双向链接：每个节点包含一个指向下一个节点的指针和一个指向前一个节点的指针。

  • 双向访问：可以从任意节点方便地访问其前驱节点和后继节点。

  • 额外开销：每个节点需要额外的空间存储前驱节点的指针。

    	typedef struct DNode {int data;struct DNode *prev;struct DNode *next;
    } DNode;

• 循环链表

  • 循环结构：循环链表的最后一个节点的指针指向头节点，形成一个环。

  • 循环单向链表：最后一个节点的next指向头节点。

  • 循环双向链表：最后一个节点的next指向头节点，头节点的prev指向最后一个节点。

    // 循环单向链表
    typedef struct CNode {int data;struct CNode *next;
    } CNode;// 循环双向链表
    typedef struct CDNode {int data;struct CDNode *prev;struct CDNode *next;
    } CDNode;

• 链表的应用场景

  • 插入和删除频繁：链表适用于插入和删除操作频繁的场景，如实现栈、队列、符号表等。
  • 内存管理：链表可以更好地管理内存，在需要频繁分配和释放内存的场景中表现优异。

• 链表的缺点

  • 随机访问效率低：链表不支持高效的随机访问，只能顺序访问，访问效率较低。
  • 指针开销：每个节点需要存储额外的指针信息，相对于数组，链表有一定的空间开销。
  • 复杂性：链表的指针操作较为复杂，容易出错，调试困难。

单链表代码实现

#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;
}``