怎么做网站视频,教育品牌加盟网站建设,东莞网站优化案例,广州南沙建设和交通局网站顺序表及其结构定义
#xff08;1#xff09;结构定义
顺序存储#xff1a; 顺序表的元素按顺序存储在一块连续的内存区域中#xff0c;每个元素占用相同大小的存储空间。通过数组实现#xff0c;每个元素可以通过下标快速访问。 存储密度高#xff1a; 因为顺序表使用…顺序表及其结构定义
1结构定义
顺序存储 顺序表的元素按顺序存储在一块连续的内存区域中每个元素占用相同大小的存储空间。通过数组实现每个元素可以通过下标快速访问。 存储密度高 因为顺序表使用连续的内存空间所以其存储密度很高没有额外的指针存储开销。 随机访问 顺序表支持O(1)时间复杂度的随机访问可以通过下标直接访问任意位置的元素。访问时间复杂度O(1)。 动态性 顺序表通常预留一定的存储空间来处理动态增长但在容量不足时需要扩展数组。扩展数组时需要重新分配一块更大的连续内存并将现有元素复制到新内存区域中。 插入和删除操作 在顺序表的末尾进行插入和删除操作的时间复杂度为O(1)。在顺序表的中间或开头进行插入和删除操作的时间复杂度为O(n)因为需要移动大量元素以保持连续存储。 空间浪费问题 如果顺序表预留了过多的空间而未使用会导致空间浪费。如果预留的空间不足需要频繁扩展数组会导致性能下降。
顺序表代码实现
#includestdio.h
#include stdlib.h
#include time.htypedef 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; 链表的应用场景 插入和删除频繁链表适用于插入和删除操作频繁的场景如实现栈、队列、符号表等。内存管理链表可以更好地管理内存在需要频繁分配和释放内存的场景中表现优异。 链表的缺点 随机访问效率低链表不支持高效的随机访问只能顺序访问访问效率较低。指针开销每个节点需要存储额外的指针信息相对于数组链表有一定的空间开销。复杂性链表的指针操作较为复杂容易出错调试困难。
单链表代码实现
#includestdio.h
#includestdlib.h
#includetime.htypedef 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;
}
