C语言数据结构与算法 | 第一部分

2025年3月17日 | 阅读 12 分钟

数据结构-数组、动态数组和链表

DSA 是任何编程语言中非常重要的概念。假设我们有很多书，我们需要一个书架来整理所有书。我们会先检查有多少本书，然后我们会假设未来可能还会买多少本书。然后，我们会考虑一个合理的预算来购买书架。我们会检查哪些书架坚固且寿命长。最后，我们会买最好的一个。

在编程中，**书本指的是我们在编写代码时需要处理的海量数据，我们正在编写的程序就是房间**，而在我们的程序中，**我们需要找到一个好的存储位置来高效地整理所有数据**。杂乱的房间永远不是好事。

在这个系列教程中，我们将涵盖 C 语言中的所有数据结构，然后是另一个主题-算法。

数据类型和数据结构

这两个词可能都有“数据”这个词，但它们并不相同。简单来说，我们可以说**数据类型是变量的特征**。它表示特定变量可以存储哪种类型的数据/值。C 语言是一种静态语言。因此，我们需要在使用程序中的每个变量之前声明它的数据类型。

**另一方面，数据结构是由不同数据类型的数据组成的集合和组织方式，我们可以从中处理和检索数据**。它涉及数据在计算机内存中的排列。

int、float 等是数据类型，栈、队列等是数据结构的例子。

C 语言中有不同类型的数据结构。我们需要学习它们，以便知道何时需要使用哪种数据结构。

下图是根据变量的组织方式在 C 语言中进行分类的流程图

Data Structures and Algorithms in C | Set 1

术语

**线性 DS：** 线性：线条。如果数据结构中的元素是顺序存储的，那么它就是线性数据结构。
**静态 DS：** 如果数据结构中的内存或空间是固定的，不能根据需要在运行时更改，那么它就是静态数据结构。
**动态 DS：** 数据结构中的空间或内存可以根据需要在运行时更改。

事实

线性数据结构易于遍历。
访问静态数据结构的元素很容易
动态数据结构的内存占用更少，使其更高效。

数组

数组是位于连续内存位置的同构元素集合。可以使用索引（0 到 size-1）访问数组的元素。它可以是多维的。它可以存储基本数据类型和派生数据类型的元素，但所有元素都必须属于同一数据类型。创建数组的目的是用一个名称表示多个相同数据类型的元素。

基本语法

注意事项

**C 语言中没有 IndexOutOfBoundException；** 如果我们尝试访问数组中不存在的索引处的元素，编译器不会报错，但会给出垃圾值。
**数据类型 * 名称：** 数据类型指针的数组。如果声明 int * a，则 a 是一个可以包含整数指针的数组的名称。
**指针：** 数组的名称表示第一个元素的地址，当传递给函数时，数组始终作为指针传递，即使我们使用方括号。
**array[index] = *(array + index) = index[array]**（可交换性）
**矩阵：** 我们可以使用多维数组来表示矩阵-array[行][列]。

这是一个包含数组所有基本操作的程序

#include<stdio.h>
int sum(int arr[]);
int *sort(int arr[]);
void main()
{
	//declaration
	int i, result;
	int a[5];
	int b[5] = {1, 2, 3, 4, 5};
	int c[5] = {};
	int *d;//array pointer(8 bytes)-stores integer pointers
	//Assigning elements to a[5]
	int j = 10;
	printf("a[5] = ");
	for(i = 0; i < 5; i++)
	{
		a[i] = j;
		j += 10;
		printf("%d ", a[i]);//Accessing elements
	}
	printf("\nOut of index a[5]: %d", a[5]);//garbage value
	//contiguous memory locations
	printf("\nArray elements are stored in contiguous locations:");
	for(i = 0; i < 5; i++)
	{
		printf("\n%p ", &a[i]);
	}
	//pointer indication
	printf("\nPointer indication:");
	printf("\n a[0] = %d", a[0]);
	printf("\n *a = %d", *a);
	printf("\nTraversing using pointer:");
	for(i = 0; i < 5; i++)
	{
		printf("\n%d ", *(a + i));
	}
	printf("\nBy commutative property a[i] = i[a] =");
	printf("\n a[2] = %d", a[2]);
	printf("\n 2[a] = %d", 2[a]);
	//Multi-dimensional arrays
	printf("\nMulti-dimensional array(4 X 4): \n");
	int multarr[4][4], k = 0;
	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 4; j++)
		{
			multarr[i][j] = k;
			k++;
			printf("%d ", multarr[i][j]);
		}
		printf("\n");
	}
	//passing array to a function
	result = sum(b);
	printf("Sum of elements of b[5] =  %d", result);
	int x[5] = {4, 1, 7, 2, 9};
	printf("\nSorting the array x: ");
	int n = sort(x);
	for(i = 0; i < 5; i++)
	{
		printf("%d ", x[i]);
	}	
} 
int sum(int arr[])
{
	int i, add = 0;
	for(i = 0; i < 5; i++)
	{
		add += arr[i];
	}
	return add;
}
int* sort(int *arr)
{
	int temp, i, j;
	for(i = 0; i < 4; i++)
	{
		for(j = 0; j < 4 - i - 1; j++)
		{
			if(arr[j] > arr[j + 1])
			{
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
	return arr;
}

输出

a[5] = 10 20 30 40 50
Out of index a[5]: 0
Array elements are stored in contiguous locations:
000000000062FDF0
000000000062FDF4
000000000062FDF8
000000000062FDFC
000000000062FE00
Pointer indication:
 a[0] = 10
 *a = 10
Traversing using pointer:
10
20
30
40
50
By commutative property a[i] = i[a] =
 a[2] = 30
 2[a] = 30
Multi-dimensional array(4 X 4):
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Sum of elements of b[5] =  15
Sorting the array x: 1 2 4 7 9
--------------------------------
Process exited after 0.8778 seconds with return value 2
Press any key to continue . . .

链表

链表是一种线性数据结构，与数组类似，但元素不是存储在连续的内存位置。链表中的每个节点/元素有两个部分-一个包含数据，另一个包含指向下一个节点位置的指针。这些指针将节点连接起来，形成一个线性链表。第一个节点的地址存储在 head 中。

注意事项

链表还用于实现其他用户定义的数据结构，如**栈和队列**。
链表中的第一个节点是 head，我们必须从它开始对链表的所有操作。
链表的最后一个节点指向 Null，表示链表已完成。

在 C 语言中，链表是使用结构创建的，它也与数组一样是同构的，这意味着它的节点只能存储相同数据类型的数据。

一个简单的链表如下所示

如上图所示，head 是第一个节点，最后一个节点的 next（引用）部分持有 None。

双向链表如下所示

在双向链表中，每个节点将有三个部分。Head 持有第一个节点的引用，第一个节点的“previous”部分持有 None，最后一个节点的 next 字段指向 None。每个节点将持有两个引用以及数据，一个指向其前一个节点，一个指向后继节点。

循环链表

循环链表可以是单向的或双向的

单向循环链表

这是一个单向链表，但列表中的最后一个节点像一个圆一样持有第一个节点的引用。

双向循环链表

这是一个双向链表，但列表中的最后一个节点持有第一个节点的引用，并且第一个节点的“previous”部分持有最后一个节点的引用，就像一个圆一样。

这里有一个程序，展示了我们可以对单向链表执行的一些基本操作

#include<stdio.h>
#include<stdlib.h>
//declaration of a linked list
struct Node{
	int data;
	struct Node* next;
};
//Definition of all functions
void displayLL(struct Node *ptr);
void InsertNodeAtBeg(struct Node* head, int value);
void InsertAfterNode(struct Node* head, int node_val, int value);
void InsertAtlast(struct Node* head, int value);
void DeleteBeg(struct Node* head);
void DeleteEnd(struct Node* head);
void DeleteMid(struct Node* head, int pos);
int main()
{
	//Nodes
	struct Node *head;
	struct Node *first;
	struct Node *second;
	struct Node *third;
	//Allocating dynamic memory
	first = (struct Node*)malloc(sizeof(struct Node));
	second = (struct Node*)malloc(sizeof(struct Node));
	third = (struct Node*)malloc(sizeof(struct Node));
	//Given data to the nodes and linking the nodes
	first->data = 1;
	first->next = second;
	second->data = 2;
	second->next = third;
	third->data = 3;
	third->next = NULL;
	head = first;
	//Calling the functions
	printf("The created Linked List: ");
	displayLL(head);
	printf("\n\nInsertions: ");
	InsertNodeAtBeg(head, 5);
	InsertAfterNode(head, 2, 10);
	InsertAtlast(head, 17);
	printf("\n\nDeletions:");
	DeleteBeg(head);
	DeleteEnd(head);
	DeleteMid(head, 3);
}
//displaying the linked list
void displayLL(struct Node *ptr)
{
	printf("HEAD -> ");
	while(ptr != NULL)
	{
		printf("%d -> ", ptr->data);
		ptr = ptr->next;
	}
	printf("NULL");
}
//Inserting a node at the beginning
void InsertNodeAtBeg(struct Node* head, int value)
{
	printf("\n\nAfter inserting %d at the beginning: ", value);
	struct Node* newnode;
	newnode = (struct Node*)malloc(sizeof(struct Node));
	displayLL(head);
	newnode->data = value;
	newnode->next = head;
	head = newnode;
	printf(" -----> ");
	displayLL(head);
}
//Inserting a node after the node with the given value
void InsertAfterNode(struct Node* head, int node_val, int value)
{
	printf("\n\nAfter inserting %d after %d node: ", value, node_val);
	displayLL(head);
	printf(" ----> ");
	struct Node* newnode;
	newnode = (struct Node*)malloc(sizeof(struct Node));
	newnode->data = value;
	struct Node* ptr = head;
	while(ptr != NULL)
	{
		if(ptr->data == node_val)
		{
			newnode->next = ptr->next;
			ptr->next = newnode;
			break;
		}
		ptr = ptr->next;
	}
	displayLL(head);
}
//Inserting a node at the end of the linked list
void InsertAtlast(struct Node* head, int value)
{
	printf("\n\nAfter inserting %d at the end: ", value);
	displayLL(head);
	printf(" ----> ");
	struct Node* newnode;
	struct Node* ptr = head;
	newnode = (struct Node*)malloc(sizeof(struct Node));
	newnode->data = value;
	newnode->next = NULL;
	while(ptr->next != NULL)
	{
		ptr = ptr->next;
	}
	ptr->next = newnode;
	displayLL(head);
}
//deleting the first node
void DeleteBeg(struct Node* head)
{
	printf("\n\nAfter deleting the 1st node: ");
	displayLL(head);
	printf(" ----> ");
	struct Node* temp = head->next;
	head = head->next;
	displayLL(head);
}
//Deleting the last node
void DeleteEnd(struct Node* head)
{
	printf("\n\nAfter deleting the last node: ");
	displayLL(head);
	printf(" ----> ");
	struct Node* ptr = head;
	while(ptr->next->next != NULL)
	{
		ptr = ptr->next;
	}
	ptr->next = NULL;
	displayLL(head);
}
//deleting from the middle
void DeleteMid(struct Node* head, int pos)
{
	printf("\n\nAfter deleting node from %d position: ", pos);
	displayLL(head);
	printf(" ----> ");
	int i;
	struct Node* temp = head;
	for(i=2; i< pos; i++)
	{
  		if(temp->next!=NULL)
		{
   			 temp = temp->next;
  		}
	}
temp->next = temp->next->next;
displayLL(head);
}

输出

The created Linked List: HEAD -> 1 -> 2 -> 3 -> NULL

Insertions:

After inserting 5 at the beginning: HEAD -> 1 -> 2 -> 3 -> NULL -----> HEAD -> 5 -> 1 -> 2 -> 3 -> NULL

After inserting 10 after 2 node: HEAD -> 1 -> 2 -> 3 -> NULL ----> HEAD -> 1 -> 2 -> 10 -> 3 -> NULL

After inserting 17 at the end: HEAD -> 1 -> 2 -> 10 -> 3 -> NULL ----> HEAD -> 1 -> 2 -> 10 -> 3 -> 17 -> NULL

Deletions:

After deleting the 1st node: HEAD -> 1 -> 2 -> 10 -> 3 -> 17 -> NULL ----> HEAD -> 2 -> 10 -> 3 -> 17 -> NULL

After deleting the last node: HEAD -> 1 -> 2 -> 10 -> 3 -> 17 -> NULL ----> HEAD -> 1 -> 2 -> 10 -> 3 -> NULL

After deleting node from 3 position: HEAD -> 1 -> 2 -> 10 -> 3 -> NULL ----> HEAD -> 1 -> 2 -> 3 -> NULL

动态数组

一旦声明了一个数组，它的size就会固定。这是一个缺点，因为我们可能在运行时需要更多的内存。因此，引入了动态数组。

与普通数组不同，**动态数组是可扩展和可收缩的，并提供对元素的随机访问。**
**动态数组与可变长度数组不同**。可变长度数组是其大小在运行时确定的数组，通常通过从用户处获取大小作为输入来确定。
即使是可变长度数组，一旦用户给出大小，我们就无法修改它。
常规数组和可变长度数组是在栈上分配的，而动态数组是在堆上分配的。
C 语言**不支持内置动态数组**，但我们可以使用**动态内存分配 (DMA)**。

有 4 个内置的动态内存分配函数可用

1. malloc()

malloc 代表 memory allocation（内存分配）。
**语法：** (type*) malloc(size)
如果我们调用 malloc 函数并传入 n 字节，它会**保留一个 n 字节的大内存块**。它返回一个指向第一个字节的 void 指针，我们可以将其强制转换为任何我们想要的数据类型- **(type*)**。
如果可用空间不足，则分配失败并返回 NULL 指针。
每个块都用**垃圾值**初始化。

2. calloc()

calloc 代表 contiguous allocation（连续分配）。
它与 malloc() 类似。
**语法：** (type*)calloc(count, size)
**count** 是元素的数量，**size** 是每个元素的大小。
如果我们调用 calloc 函数并传入 m 个 count 和 n 个字节，它会分配**m 个大小为 n 的块**。
每个块都用**0**初始化。

在 malloc() 和 calloc() 中，内存都是在一个地方连续分配的。因此，可以创建动态数组。

这是一个示例程序，展示了 malloc() 和 calloc() 分配之间的区别

#include<stdio.h>
#include<stdlib.h>
void main()
{
	int *ptr1, *ptr2, n1, n2, i;
	printf("Enter the number of elements in the first D-array: ");
	scanf("%d", &n1);
	printf("Enter the number of elements in the second D-array: ");
	scanf("%d", &n2);
	//initialization
	ptr1 = (int*)malloc(sizeof(int)*n1);
	ptr2 = (int*)calloc(n2, sizeof(int));
	//Initial values
	printf("\nInitial values: ");
	printf("\nBy malloc(): ");
	for(i=0;i<n1;i++)
	{
		printf("%d ", *(ptr1 + i));
	}
	printf("\nBy calloc(): ");
	for(i=0;i<n1;i++)
	{
		printf("%d ", *(ptr2 + i));
	}
	//Allocated addresses
	printf("\n\nMemory allocations: ");
	printf("\nBy malloc(): ");
	for(i=0;i<n1;i++)
	{
		printf("%d ", ptr1 + i);
	}
	printf("\nBy calloc(): ");
	for(i=0;i<n1;i++)
	{
		printf("%d ", ptr2 + i);
	}
}

输出

Enter the number of elements in the first D-array: 5
Enter the number of elements in the second D-array: 5

Initial values:
By malloc(): 11901584 0 11862352 0 1936028257
By calloc(): 0 0 0 0 0

Memory allocations:
By malloc(): 11867904 11867908 11867912 11867916 11867920
By calloc(): 11867936 11867940 11867944 11867948 11867952

3. free()

它用于**显式释放动态内存分配的内存**。对于常规变量，内存会在运行时自动释放。在这种情况下，我们需要使用 free() 来释放 DMA 的所有保留内存。
**语法：** free(ptr)
**ptr** 指的是之前使用 malloc 或 calloc 分配的指针。

4. realloc()

realloc 代表 reallocation（重新分配）。
它用于动态地重新分配已分配的动态内存。
假设我们使用了 malloc 或 calloc 并保留了一些内存，但内存不足；我们可以使用 realloc 来保留更多内存。
**语法：** realloc(ptr, newsize)
**ptr** 指的是之前使用 malloc 或 calloc 分配的指针。

假设我们创建了一个大小为 n 的常规数组，并且我们决定在运行时不需要第一个元素。我们将所有元素向左移动，移除第一个元素。这不会改变数组的大小，空位永远不会消失。

对于动态数组，我们可以使用 realloc() 来收缩数组。这里有一个演示此现象的示例

#include<stdio.h>
#include<stdlib.h>
void main()
{
	int *ptr, n, arr[n], i;
	printf("Enter the size: ");
	scanf("%d", &n);
	//Creating a dynamic array
	ptr = (int*)malloc(sizeof(int)*n);
	printf("\nThe memory allocations in a regular array: ");
	for(i = 0; i < n; i++)
	{
		printf("%d ", &arr[i]);
	}
	printf("\nThe memory allocations in the dynamic array: ");
	for(i = 0; i < n; i++)
	{
		printf("%d ", &ptr[i]);
	}
	//Removing the first element
	for(i = 1; i < n; i++)
	{
		arr[i - 1] = arr[i];
		ptr[i - 1] = ptr[i];
	}
	printf("\n\nAfter removing the first element:");
	printf("\nRegular array: ");
	for(i = 0; i < n; i++)
	{
		printf("%d ", &arr[i]);
	}

	printf("\nDynamic array: ");
	//Shrinking the memory of the dynamic array
	int t = n - 1;
	ptr = realloc(ptr, (t)*sizeof(int));
	for(i = 0; i < t; i++)
	{
		printf("%d ", &ptr[i]);
	}
	free(ptr);
}

输出

Enter the size: 6

The memory allocations in a regular array: 6487264 6487268 6487272 6487276 6487280 6487284
The memory allocations in the dynamic array: 12130048 12130052 12130056 12130060 12130064 12130068

After removing the first element:
Regular array: 6487264 6487268 6487272 6487276 6487280 6487284
Dynamic array: 12130048 12130052 12130056 12130060 12130064
--------------------------------
Process exited after 2.795 seconds with return value 1
Press any key to continue . . .

我们无法对动态数组使用 sizeof()。它只返回第一个指针的大小。
我们需要使用 free() 函数显式地释放内存。

结论

这是关于 C 语言数据结构与算法的第一个教程。

在本教程中，我们涵盖了

数据类型和数据结构之间的区别
数组
链表
动态数组-C 语言中的 DMA

实现了带有所有基本操作和解释的程序，以便更好地理解。在下一个教程中，我们将继续学习栈和队列。

下一主题C语言数据结构与算法|第二部分

C语言数据结构与算法 | 第一部分

数据结构-数组、动态数组和链表

数据类型和数据结构

术语

事实

数组

注意事项

链表

循环链表

动态数组

结论

联系信息

关注我们

教程

面试题

在线编译器

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语言数据结构与算法 | 第一部分

数据结构-数组、动态数组和链表

数据类型和数据结构

术语

事实

数组

注意事项

链表

循环链表

动态数组

结论

相关帖子

C 语言 abort() 函数

C 语言 Strtok() 函数

C 语言算法

C 语言字符串数组

C 语言 Strftime()

C 语言部门管理系统

C 语言 fgets() 函数

C 语言栈

C 语言中的哈希是什么

C 语言入口控制循环

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器