搜索到
4
篇
分类为 数据结构 的文章
-
数据结构之队列 队列 (Queue)1. 概述队列（Queue）是一种特殊的线性表，只允许在表的一端进行插入操作，而在表的另一端进行删除操作。插入操作称为入队（enqueue），删除操作称为出队（dequeue）。队列遵循先进先出（First In First Out, FIFO）的原则。2. 队列的定义队列是一种线性表，只允许在一端进行插入操作，在另一端进行删除操作。插入的一端称为队尾（Rear），删除的一端称为队头（Front）。3. 队列的基本操作队列的基本操作包括初始化队列、判断队列空、判断队列满、入队、出队和取队头元素。3.1 顺序队列顺序队列是用一组地址连续的存储单元依次存放从队头到队尾的队列元素。定义顺序队列结构#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; int rear; } SeqQueue;初始化队列void InitQueue(SeqQueue *Q) { Q->front = 0; Q->rear = 0; }判断队列空bool QueueEmpty(SeqQueue Q) { return Q.front == Q.rear; }判断队列满bool QueueFull(SeqQueue Q) { return (Q.rear + 1) % MAXSIZE == Q.front; }入队bool Enqueue(SeqQueue *Q, int e) { if (QueueFull(*Q)) return false; Q->data[Q->rear] = e; Q->rear = (Q->rear + 1) % MAXSIZE; return true; }出队bool Dequeue(SeqQueue *Q, int *e) { if (QueueEmpty(*Q)) return false; *e = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXSIZE; return true; }取队头元素bool GetFront(SeqQueue Q, int *e) { if (QueueEmpty(Q)) return false; *e = Q.data[Q.front]; return true; }3.2 链队列链队列是用链表来存储队列中的元素。定义链队列节点结构typedef struct QNode { int data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue;初始化队列void InitQueue(LinkQueue *Q) { Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q->front) exit(1); Q->front->next = NULL; }判断队列空bool QueueEmpty(LinkQueue Q) { return Q.front == Q.rear; }入队bool Enqueue(LinkQueue *Q, int e) { QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if (!p) return false; p->data = e; p->next = NULL; Q->rear->next = p; Q->rear = p; return true; }出队bool Dequeue(LinkQueue *Q, int *e) { if (QueueEmpty(*Q)) return false; QueuePtr p = Q->front->next; *e = p->data; Q->front->next = p->next; if (Q->rear == p) Q->rear = Q->front; free(p); return true; }取队头元素bool GetFront(LinkQueue Q, int *e) { if (QueueEmpty(Q)) return false; *e = Q.front->next->data; return true; }4. 队列的应用队列在计算机科学中有广泛的应用，例如：操作系统中的任务调度：使用队列实现任务的先进先出调度。网络数据缓冲：在网络通信中，使用队列保存接收到的数据包。树和图的广度优先搜索：在树和图的遍历中使用队列实现广度优先搜索。打印队列：管理打印任务的顺序。5. 示例代码下面是使用队列实现广度优先搜索（BFS）的示例代码：#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define MAXVEX 100 typedef struct { int data[MAXVEX]; int front; int rear; } SeqQueue; void InitQueue(SeqQueue *Q) { Q->front = 0; Q->rear = 0; } bool QueueEmpty(SeqQueue Q) { return Q.front == Q.rear; } bool Enqueue(SeqQueue *Q, int e) { if ((Q->rear + 1) % MAXVEX == Q->front) return false; Q->data[Q->rear] = e; Q->rear = (Q->rear + 1) % MAXVEX; return true; } bool Dequeue(SeqQueue *Q, int *e) { if (QueueEmpty(*Q)) return false; *e = Q->data[Q->front]; Q->front = (Q->front + 1) % MAXVEX; return true; } void BFS(int graph[MAXVEX][MAXVEX], int n, int start) { bool visited[MAXVEX] = {false}; SeqQueue Q; InitQueue(&Q); printf("%d ", start); visited[start] = true; Enqueue(&Q, start); while (!QueueEmpty(Q)) { int v; Dequeue(&Q, &v); for (int i = 0; i < n; i++) { if (graph[v][i] == 1 && !visited[i]) { printf("%d ", i); visited[i] = true; Enqueue(&Q, i); } } } } int main() { int graph[MAXVEX][MAXVEX] = { {0, 1, 1, 0, 0, 0}, {1, 0, 0, 1, 1, 0}, {1, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 0, 1}, {0, 1, 1, 0, 0, 1}, {0, 0, 0, 1, 1, 0} }; int n = 6; BFS(graph, n, 0); return 0; }上述代码实现了使用顺序队列进行广度优先搜索（BFS）的功能。通过队列保存待访问的节点，依次访问每个节点，并将其未访问的邻接节点加入队列，从而实现广度优先搜索。 -
数据结构之栈 栈 (Stack)1. 概述栈（Stack）是一种线性表，但限定在表的一端进行插入和删除操作的特殊线性表。按后进先出（Last In First Out, LIFO）的原则进行操作。栈的插入操作称为进栈（push），删除操作称为出栈（pop）。2. 栈的定义栈是一种只允许在一端进行插入和删除操作的线性表。这个端被称为栈顶（Top），相对的另一端为栈底（Bottom）。3. 栈的基本操作栈的基本操作包括初始化栈、判断栈空、判断栈满、进栈、出栈和取栈顶元素。3.1 顺序栈顺序栈是用一组地址连续的存储单元依次存放自栈底到栈顶的栈中元素。定义顺序栈结构#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; } SeqStack;初始化栈void InitStack(SeqStack *S) { S->top = -1; }判断栈空bool StackEmpty(SeqStack S) { return S.top == -1; }判断栈满bool StackFull(SeqStack S) { return S.top == MAXSIZE - 1; }进栈bool Push(SeqStack *S, int e) { if (S->top == MAXSIZE - 1) return false; S->data[++S->top] = e; return true; }出栈bool Pop(SeqStack *S, int *e) { if (S->top == -1) return false; *e = S->data[S->top--]; return true; }取栈顶元素bool GetTop(SeqStack S, int *e) { if (S.top == -1) return false; *e = S.data[S.top]; return true; }3.2 链栈链栈是用链表来存储栈中的元素。定义链栈节点结构typedef struct StackNode { int data; struct StackNode *next; } StackNode, *LinkStack;初始化栈void InitStack(LinkStack *S) { *S = NULL; }判断栈空bool StackEmpty(LinkStack S) { return S == NULL; }进栈bool Push(LinkStack *S, int e) { StackNode *p = (StackNode *)malloc(sizeof(StackNode)); if (!p) return false; p->data = e; p->next = *S; *S = p; return true; }出栈bool Pop(LinkStack *S, int *e) { if (*S == NULL) return false; StackNode *p = *S; *e = p->data; *S = p->next; free(p); return true; }取栈顶元素bool GetTop(LinkStack S, int *e) { if (S == NULL) return false; *e = S->data; return true; }4. 栈的应用栈在计算机科学中有广泛的应用，例如：表达式求值：使用栈可以实现中缀表达式转换为后缀表达式，并求值。括号匹配：使用栈可以检测表达式中的括号是否匹配。函数调用：函数调用过程中使用栈保存返回地址和局部变量，实现递归调用。深度优先搜索：在图的遍历中使用栈实现深度优先搜索。5. 示例代码下面是使用栈实现括号匹配的示例代码：#include <stdio.h> #include <stdbool.h> #include <stdlib.h> typedef struct StackNode { char data; struct StackNode *next; } StackNode, *LinkStack; void InitStack(LinkStack *S) { *S = NULL; } bool StackEmpty(LinkStack S) { return S == NULL; } bool Push(LinkStack *S, char e) { StackNode *p = (StackNode *)malloc(sizeof(StackNode)); if (!p) return false; p->data = e; p->next = *S; *S = p; return true; } bool Pop(LinkStack *S, char *e) { if (*S == NULL) return false; StackNode *p = *S; *e = p->data; *S = p->next; free(p); return true; } bool GetTop(LinkStack S, char *e) { if (S == NULL) return false; *e = S->data; return true; } bool BracketMatch(char *exp) { LinkStack S; InitStack(&S); for (int i = 0; exp[i] != '\0'; i++) { if (exp[i] == '(' || exp[i] == '[' || exp[i] == '{') { Push(&S, exp[i]); } else if (exp[i] == ')' || exp[i] == ']' || exp[i] == '}') { if (StackEmpty(S)) return false; char topElem; Pop(&S, &topElem); if ((exp[i] == ')' && topElem != '(') || (exp[i] == ']' && topElem != '[') || (exp[i] == '}' && topElem != '{')) { return false; } } } return StackEmpty(S); } int main() { char *exp = "{[(2+3)*(4+5)]}"; if (BracketMatch(exp)) { printf("The brackets match.\n"); } else { printf("The brackets do not match.\n"); } return 0; }上述代码实现了使用链栈进行括号匹配的功能。通过遍历表达式，将左括号入栈，遇到右括号时出栈，并检查是否匹配，最后检查栈是否为空来判断括号是否匹配。
-
数据结构之线性表 线性表 (Linear List)1. 概述线性表（Linear List）是一种最基本、最常用的数据结构。它是由同类型数据元素构成的有限序列。根据存储方式的不同，线性表可以分为顺序表（顺序存储）和链表（链式存储）。2. 线性表的定义线性表是由 n 个元素构成的有序序列。通常表示为：[ L = {a_1, a_2, a_3, \ldots, a_n} ]其中：( L ) 是线性表的名字。( a_i ) 表示线性表中的第 ( i ) 个元素。( n ) 表示线性表中的元素个数。3. 线性表的类型线性表按存储结构分为两种类型：顺序表（Sequential List）：使用一段连续的存储单元依次存放线性表的各个元素。链表（Linked List）：使用一组任意的存储单元存放线性表的各个元素，这些存储单元可以是连续的，也可以是不连续的。4. 顺序表4.1 顺序表的定义顺序表是一种线性表，其数据元素按顺序存储在一块连续的内存空间中。4.2 顺序表的基本操作初始化顺序表#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList; void InitList(SeqList *L) { L->length = 0; }插入元素bool ListInsert(SeqList *L, int i, int e) { if (i < 1 || i > L->length + 1) return false; if (L->length == MAXSIZE) return false; for (int j = L->length; j >= i; j--) { L->data[j] = L->data[j-1]; } L->data[i-1] = e; L->length++; return true; }删除元素bool ListDelete(SeqList *L, int i, int *e) { if (i < 1 || i > L->length) return false; *e = L->data[i-1]; for (int j = i; j < L->length; j++) { L->data[j-1] = L->data[j]; } L->length--; return true; }查找元素int LocateElem(SeqList L, int e) { for (int i = 0; i < L.length; i++) { if (L.data[i] == e) { return i + 1; } } return 0; }5. 链表5.1 链表的定义链表是一种线性表，其数据元素的存储单元可以是非连续的，通过指针链接各个元素。5.2 链表的基本操作定义单链表节点结构typedef struct Node { int data; struct Node *next; } Node, *LinkList;初始化链表void InitList(LinkList *L) { *L = (LinkList)malloc(sizeof(Node)); if (*L == NULL) exit(1); (*L)->next = NULL; }插入元素bool ListInsert(LinkList L, int i, int e) { LinkList p = L; int j = 0; while (p && j < i - 1) { p = p->next; j++; } if (!p || j > i - 1) return false; LinkList s = (LinkList)malloc(sizeof(Node)); s->data = e; s->next = p->next; p->next = s; return true; }删除元素bool ListDelete(LinkList L, int i, int *e) { LinkList p = L; int j = 0; while (p->next && j < i - 1) { p = p->next; j++; } if (!(p->next) || j > i - 1) return false; LinkList q = p->next; p->next = q->next; *e = q->data; free(q); return true; }查找元素LinkList GetElem(LinkList L, int i) { LinkList p = L->next; int j = 1; while (p && j < i) { p = p->next; j++; } if (!p || j > i) return NULL; return p; }6. 线性表的应用线性表在许多领域有广泛应用，例如：存储有序数据实现栈和队列实现字符串处理实现其他复杂数据结构的基础线性表作为数据结构的基础，其理解和应用对编程和算法设计非常重要。以上内容涵盖了线性表的基本概念、类型及其常见操作，希望对你有所帮助。
-
