C 语言数据结构

2024年8月28日 | 阅读 12 分钟

C 数据结构 C 中的数据结构是指一种排列和存储数据的方式，以便能够快速访问和修改数据。

分为两种类型

线性数据结构
非线性数据结构

线性数据结构

C 语言中的线性数据结构是指数据元素按顺序或线性排列的数据结构。数组、链表、栈和队列是一些在 C 语言中使用的线性数据结构的例子。

1. 数组

在 C 语言中，数组用于存储固定数量的相同类型元素。

特性

存储固定数量的相同数据类型的元素
允许使用索引随机访问元素
可用于表示矩阵和其他数学结构

优点

简单易用
通过索引提供对元素的快速访问
可用于实现各种算法，包括排序和搜索算法

缺点

固定大小，如果数据集的大小未知或动态，则可能效率低下
如果数组很大，插入和删除元素可能会很昂贵

这是一个存储 5 个整数的数组示例

C 语言程序

#include <stdio.h>
#define SIZE 5
 
int main() {
  int arr[SIZE] = {2, 4, 6, 8, 10};
  int i;
 
  for (i = 0; i < SIZE; i++) {
    printf("%d ", arr[i]);
  }
 
  return 0;
}

输出

2 4 6 8 10

2. 链表

C 语言中的链表用于以动态方式存储元素集合。链表对于实现易于修改的动态数据结构很有用。

特性

根据需要增长或缩小的动态数据结构
提供快速的元素插入和删除
可以通过指针轻松遍历

优点

提供高效的内存管理
允许创建易于修改的动态数据结构
提供快速的元素插入和删除

缺点

对元素的随机访问效率低下
如果用于表示大型数据集，可能会占用大量内存

这是一个存储整数的链表示例。

C 语言程序

#include <stdio.h>
#include <stdlib.h>
 
struct Node {
  int data;
  struct Node *next;
};
 
void printList(struct Node *node) {
  while (node != NULL) {
    printf("%d ", node->data);
    node = node->next;
  }
}
 
int main() {
  struct Node* head = NULL;
  struct Node* second = NULL;
  struct Node* third = NULL;
 
  head = (struct Node*)malloc(sizeof(struct Node)); 
  second = (struct Node*)malloc(sizeof(struct Node));
  third = (struct Node*)malloc(sizeof(struct Node));
 
  head->data = 1; 
  head->next = second; 
 
  second->data = 2; 
  second->next = third; 
 
  third->data = 3; 
  third->next = NULL;
 
  printList(head);
 
  return 0;
}

输出

1 2 3

3. 队列

C 语言中的队列用于以“先进先出”（FIFO）的顺序存储元素集合。对于实现需要处理顺序的算法，队列很有用。

特性

以“先进先出”（FIFO）的顺序存储元素集合
可用于实现广泛的算法和数据结构
提供高效的内存管理

优点

提供一种简单高效的方式来实现需要 FIFO 顺序的算法
可以使用数组或链表轻松实现
提供对队列中第一个元素的快速访问

缺点

对元素的随机访问效率低下
如果用于实现需要随机访问元素的算法，则效率低下

这是一个存储整数的队列示例

C 语言程序

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// define the structure for the queue
struct queue {
    int items[MAX_SIZE];
    int front;
    int rear;
};

// function to create an empty queue
struct queue* createQueue() {
    struct queue* q = malloc(sizeof(struct queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

// function to check if the queue is empty
int isEmpty(struct queue* q) {
    if (q->rear == -1)
        return 1;
    else
        return 0;
}

// function to add an element to the queue
void enqueue(struct queue* q, int value) {
    if (q->rear == MAX_SIZE - 1)
        printf("Queue is full!");
    else {
        if (q->front == -1)
            q->front = 0;
        q->rear++;
        q->items[q->rear] = value;
    }
}

// function to remove an element from the queue
int dequeue(struct queue* q) {
    int item;
    if (isEmpty(q)) {
        printf("Queue is empty");
        item = -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
    }
    return item;
}

int main() {
    struct queue* q = createQueue();

    enqueue(q, 1);
    enqueue(q, 2);
    enqueue(q, 3);

    printf("Dequeued item: %d\n", dequeue(q));
    printf("Dequeued item: %d\n", dequeue(q));
    printf("Dequeued item: %d\n", dequeue(q));

    return 0;
}

输出

Dequeued item: 1
Dequeued item: 2
Dequeued item: 3

4. 栈

C 编程语言中的栈以“后进先出”（LIFO）的顺序存储一组元素。对于实现需要分层排序的算法，栈很有用。

特性

以“后进先出”（LIFO）的顺序存储元素集合
可用于实现广泛的算法和数据结构
提供高效的内存管理

优点

提供了一种简单高效的方式来实现需要 LIFO 顺序的算法
可以使用数组或链表轻松实现
提供对栈顶元素的快速访问

缺点

对元素的随机访问效率低下
如果用于实现需要随机访问元素的算法，则效率低下

这是一个存储整数的栈示例

C 语言程序

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

// define the structure for the stack
struct stack {
    int items[MAX_SIZE];
    int top;
};

// function to create an empty stack
struct stack* createStack() {
    struct stack* s = malloc(sizeof(struct stack));
    s->top = -1;
    return s;
}

// function to check if the stack is empty
int isEmpty(struct stack* s) {
    if (s->top == -1)
        return 1;
    else
        return 0;
}

// function to check if the stack is full
int isFull(struct stack* s) {
    if (s->top == MAX_SIZE - 1)
        return 1;
    else
        return 0;
}

// function to add an element to the stack
void push(struct stack* s, int value) {
    if (isFull(s))
        printf("Stack is full!");
    else {
        s->top++;
        s->items[s->top] = value;
    }
}

// function to remove an element from the stack
int pop(struct stack* s) {
    int item;
    if (isEmpty(s)) {
        printf("Stack is empty");
        item = -1;
    } else {
        item = s->items[s->top];
        s->top--;
    }
    return item;
}

int main() {
    struct stack* s = createStack();

    push(s, 1);
    push(s, 2);
    push(s, 3);

    printf("Popped item: %d\n", pop(s));
    printf("Popped item: %d\n", pop(s));
    printf("Popped item: %d\n", pop(s));

    return 0;
}

输出

Popped item: 3
Popped item: 2
Popped item: 1

非线性数据结构

非线性数据结构是指元素不像数组和链表那样按线性或顺序排列的数据结构。相反，元素可以按层次结构、树状结构或图状结构排列。

非线性数据结构包括，例如

1. 树

树是一种分层数据结构，其中每个节点至少有一个子节点和一个父节点。底部的节点称为叶节点，最上面的节点称为根节点。不常见的树数据结构包括二叉树。

特点：树是分层数据结构，由节点组成，每个节点都有一个父节点和零个或多个子节点。在树中，叶节点和根节点都没有父节点，也没有子节点。二叉树（每个节点最多有两个子节点）和 n 叉树（每个节点最多有 n 个子节点）是根据每个节点可以拥有的子节点的最大数量来分类的两种树。
优点：树在表示数据之间的分层关系（如文件系统、组织结构图和家谱）方面很有用。此外，它们还用于搜索算法，在搜索、插入和删除元素方面具有对数时间复杂度，例如二叉搜索树。
缺点：如果树变得不平衡，即树的一个分支比其他分支长得多，则树的性能可能很差。这可能导致搜索、插入和删除操作具有线性时间复杂度。

这是一个树的示例

C 语言程序

// Tree traversal in C

#include <stdio.h>
#include <stdlib.h>

struct node {
  int item;
  struct node* left;
  struct node* right;
};

// Inorder traversal
void inorderTraversal(struct node* root) {
  if (root == NULL) return;
  inorderTraversal(root->left);
  printf("%d ->", root->item);
  inorderTraversal(root->right);
}

// Preorder traversal
void preorderTraversal(struct node* root) {
  if (root == NULL) return;
  printf("%d ->", root->item);
  preorderTraversal(root->left);
  preorderTraversal(root->right);
}

// Postorder traversal
void postorderTraversal(struct node* root) {
  if (root == NULL) return;
  postorderTraversal(root->left);
  postorderTraversal(root->right);
  printf("%d ->", root->item);
}

// Create a new Node
struct node* createNode(value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->item = value;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

// Insert on the left of the node
struct node* insertLeft(struct node* root, int value) {
  root->left = createNode(value);
  return root->left;
}

// Insert on the right of the node
struct node* insertRight(struct node* root, int value) {
  root->right = createNode(value);
  return root->right;
}

int main() {
  struct node* root = createNode(1);
  insertLeft(root, 2);
  insertRight(root, 3);
  insertLeft(root->left, 4);

  printf("Inorder traversal \n");
  inorderTraversal(root);

  printf("\nPreorder traversal \n");
  preorderTraversal(root);

  printf("\nPostorder traversal \n");
  postorderTraversal(root);
}

输出

Inorder traversal 
4 ->2 ->1 ->3 ->
Preorder traversal 
1 ->2 ->4 ->3 ->
Postorder traversal 
4 ->2 ->3 ->1 ->

2. 图

图由节点（或顶点）和连接它们的边组成。我们知道图可以是环形或非环形的，有向或无向的，也可以是加权的或不加权的。

特点：图本质上是由边连接的节点（也称为顶点）的集合。边可以包含权重以表示顶点之间的成本或距离，并且可以是定向的或无向的。可以根据是否存在循环对图进行分类，例如无环图（无循环）和有环图（一个或多个循环）。
优点：图在表示数据之间的复杂关系（如社交网络、交通网络和计算机网络）方面很有用。它们还用于最短路径、最小生成树和网络流问题的算法。
缺点：由于其复杂性，图可能难以操作和分析。图问题的算法可能具有高的时间和空间复杂度，尤其是在大型图的情况下。

这是一个图的示例

C 语言程序

#include <stdio.h>
#include <stdlib.h>
 
// We are defining the maximum number of vertices in the graph
#define N 6
 
// It is a data structure to store a graph object
struct Graph
{
    // An adjacency list can be represented by an array of pointers to Nodes
    struct Node* head[N];
};
 
// An adjacency list for the graph's nodes is kept in a data structure.
struct Node
{
    int dest;
    struct Node* next;
};
 
// An edge-storing data structure for graphs
struct Edge {
    int src, dest;
};
 
// Function to create an adjacency list from specified edges
struct Graph* createGraph(struct Edge edges[], int n)
{
    // allocate storage for the graph data structure
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
 
    // initialize head pointer for all vertices
    for (int i = 0; i < N; i++) {
        graph->head[i] = NULL;
    }
 
    // add edges to the directed graph one by one
    for (int i = 0; i < n; i++)
    {
        // get the source and destination vertex
        int src = edges[i].src;
        int dest = edges[i].dest;
 
        // allocate a new node of adjacency list from src to dest
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->dest = dest;
 
        // point new node to the current head
        newNode->next = graph->head[src];
 
        // point head pointer to the new node
        graph->head[src] = newNode;
    }
 
    return graph;
}
 
// Function to print adjacency list representation of a graph
void printGraph(struct Graph* graph)
{
    for (int i = 0; i < N; i++)
    {
        // print current vertex and all its neighbors
        struct Node* ptr = graph->head[i];
        while (ptr != NULL)
        {
            printf("(%d ?> %d)\t", i, ptr->dest);
            ptr = ptr->next;
        }
 
        printf("\n");
    }
}
 
// Directed graph implementation in C
int main(void)
{
    // input array containing edges of the graph (as per the above diagram)
    // (x, y) pair in the array represents an edge from x to y
    struct Edge edges[] =
    {
        {0, 1}, {1, 2}, {2, 0}, {2, 1}, {3, 2}, {4, 5}, {5, 4}
    };
 
    // calculate the total number of edges
    int n = sizeof(edges)/sizeof(edges[0]);
 
    // construct a graph from the given edges
    struct Graph *graph = createGraph(edges, n);
 
    // Function to print adjacency list representation of a graph
    printGraph(graph);
 
    return 0;
}

输出

(0 ?> 1)	
(1 ?> 2)	
(2 ?> 1)	(2 ?> 0)	
(3 ?> 2)	
(4 ?> 5)	
(5 ?> 4)

3. 堆

堆是一种特殊的基于树的数据结构，它满足堆属性。在最小堆中，父节点始终小于其子节点，而在最大堆中，父节点始终大于其子节点。

特点：堆是基于树的数据结构，它满足堆属性，即每个父节点的值大于或等于其子节点的值（对于最大堆）或小于或等于其子节点的值（对于最小堆）。堆通常实现为二叉树，其中每个节点代表堆中的一个元素。
优点：堆在实现优先队列方面很有用，在优先队列中，元素按优先级（即最大或最小）从队列中移除。它们还用于排序算法，例如堆排序，其时间复杂度为 O(n log n)。
缺点：堆在插入元素时可能性能很差，尤其是在堆变得不平衡时。此外，由于堆通常实现为二叉树，如果堆中的元素数量不是 2 的幂，则可能会浪费空间。

这是一个堆的示例

C 语言程序

// Max-Heap data structure in C

#include <stdio.h>
int size = 0;
void swap(int *a, int *b)
{
  int temp = *b;
  *b = *a;
  *a = temp;
}
void heapify(int array[], int size, int i)
{
  if (size == 1)
  {
    printf("Single element in the heap");
  }
  else
  {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < size && array[l] > array[largest])
      largest = l;
    if (r < size && array[r] > array[largest])
      largest = r;
    if (largest != i)
    {
      swap(&array[i], &array[largest]);
      heapify(array, size, largest);
    }
  }
}
void insert(int array[], int newNum)
{
  if (size == 0)
  {
    array[0] = newNum;
    size += 1;
  }
  else
  {
    array[size] = newNum;
    size += 1;
    for (int i = size / 2 - 1; i >= 0; i--)
    {
      heapify(array, size, i);
    }
  }
}
void deleteRoot(int array[], int num)
{
  int i;
  for (i = 0; i < size; i++)
  {
    if (num == array[i])
      break;
  }

  swap(&array[i], &array[size - 1]);
  size -= 1;
  for (int i = size / 2 - 1; i >= 0; i--)
  {
    heapify(array, size, i);
  }
}
void printArray(int array[], int size)
{
  for (int i = 0; i < size; ++i)
    printf("%d ", array[i]);
  printf("\n");
}
int main()
{
  int array[10];

  insert(array, 3);
  insert(array, 4);
  insert(array, 9);
  insert(array, 5);
  insert(array, 2);

  printf("Max-Heap array: ");
  printArray(array, size);

  deleteRoot(array, 4);

  printf("After deleting an element: ");

  printArray(array, size);
}

输出

Max-Heap array: 9 5 4 3 2 
After deleting an element: 9 5 2 3

这些只是非线性数据结构的一些例子，还有许多其他数据结构用于各种应用。

结论

总之，线性数据结构和非线性数据结构在计算机科学中都很重要，并且可以使用 C 编程语言实现。

线性数据结构，如数组、链表和栈，具有简单的线性组织，并用于按顺序存储数据。它们的优点是可以快速访问结构中间的元素，但对于在结构中间插入或删除元素，性能可能较慢。

非线性数据结构，如树、图和堆，具有更复杂的组织，并用于存储具有分层或互联关系的数据。它们的优点是搜索、插入和删除操作效率高，但访问结构中间元素的性能可能较差。

数据结构的选则取决于所解决问题的具体要求。对于需要按顺序访问数据或数据大小已知的数据集的问题，线性数据结构更为合适。对于数据具有复杂关系或需要高效搜索、插入和删除操作的问题，非线性数据结构更为合适。

在 C 编程中，可以使用数组、指针和结构来实现线性和非线性数据结构。还有许多可用的库和框架提供了常见数据结构的实现，例如 C++ 中的标准模板库（STL）。理解不同数据结构的特性、优点和缺点是计算机科学家和软件开发人员的一项重要技能。

下一主题C语言中switch语句和if-else-if梯形语句的区别

C 语言数据结构

线性数据结构

1. 数组

2. 链表

3. 队列

4. 栈

非线性数据结构

1. 树

2. 图

3. 堆

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

C 语言数据结构

线性数据结构

1. 数组

2. 链表

3. 队列

4. 栈

非线性数据结构

1. 树

2. 图

3. 堆

结论

相关帖子

C/C++ 中的模运算符

C 语言中的强数

C 语言 getchar() 函数

使用 C 语言指针相加两个数字

C 语言运算符优先级

C 语言 Strtoul() 函数

C 语言中的实际参数和形式参数

C 语言杨辉三角

C 语言 clrscr

C 语言学校账单系统

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器