- DSA 使用 C 教程
- 使用 C 的 DSA - 主页
- 使用 C 语言的 DSA - 概述
- 使用 C 语言的 DSA - 环境
- 使用 C 算法的 DSA
- 使用 C 的 DSA - 概念
- 使用 C 数组的 DSA
- 使用 C 链表的 DSA
- 使用 C 的 DSA - 双向链表
- 使用 C 的 DSA - 循环链表
- 使用 C 的 DSA - 堆栈内存溢出
- 使用 C 的 DSA - 解析表达式
- 使用 C 队列的 DSA
- 使用 C 的 DSA - 优先级队列
- 使用 C 树的 DSA
- 使用 C 哈希表的 DSA
- 使用 C 堆的 DSA
- 使用 C - Graph 的 DSA
- 使用 C 搜索技术的 DSA
- 使用 C 排序技术的 DSA
- 使用 C 的 DSA - 递归
- 使用 C 语言的 DSA 有用资源
- 使用 C 的 DSA - 快速指南
- 使用 C 的 DSA - 有用资源
- 使用 C 的 DSA - 讨论
使用 C 的 DSA - 快速指南
使用 C 语言的 DSA - 概述
什么是数据结构？
数据结构是一种组织数据以使其能够有效使用的方法。以下术语是数据结构的基础术语。
接口- 每个数据结构都有一个接口。接口代表数据结构支持的操作集。接口仅提供支持的操作列表、它们可以接受的参数类型以及这些操作的返回类型。
实现- 实现提供数据结构的内部表示。实现还提供了数据结构操作中使用的算法的定义。
数据结构的特征
正确性- 数据结构实现应该正确实现其接口。
时间复杂度- 数据结构操作的运行时间或执行时间必须尽可能小。
空间复杂度- 数据结构操作的内存使用量应尽可能少。
对数据结构的需求
随着应用程序变得越来越复杂且数据越来越丰富，应用程序现在面临三个常见问题。
数据搜索- 考虑商店的100 万（10 6 ）件商品的库存。如果应用程序是搜索一个项目。每次它必须搜索 100 万（10 6 ）个项目，这会减慢搜索速度。随着数据的增长，搜索会变得更慢。
处理器速度- 虽然处理器速度非常高，但如果数据增长到十亿条记录，处理器速度就会受到限制。
多个请求- 由于数千个用户可以在 Web 服务器上同时搜索数据，因此即使非常快的服务器在搜索数据时也会失败。
为了解决上述问题，数据结构就派上用场了。数据可以以这样的方式组织在数据结构中：不需要搜索所有项目并且几乎可以立即搜索所需的数据。
执行时间案例
通常使用三种情况以相对方式比较各种数据结构的执行时间。
最坏情况- 这是特定数据结构操作花费最大时间的情况。如果操作的最坏情况时间为 f(n)，则该操作所花费的时间不会超过 f(n) 时间，其中 f(n) 表示 n 的函数。
平均情况- 这是描述数据结构操作的平均执行时间的场景。如果执行一个操作需要 f(n) 时间，则 m 个操作将花费 mf(n) 时间。
最佳情况- 这是描述数据结构操作的最短可能执行时间的场景。如果一个操作在执行中需要 f(n) 时间，那么实际操作可能会花费随机数的时间，该时间最大为 f(n)。
使用 C 的 DSA - 环境设置
本地环境设置
如果您仍然愿意设置 C 编程语言环境，则您的计算机上需要有以下两个软件：(a) 文本编辑器和 (b) C 编译器。
文本编辑器
这将用于输入您的程序。少数编辑器的示例包括 Windows 记事本、操作系统编辑命令、Brief、Epsilon、EMACS 和 vim 或 vi。
文本编辑器的名称和版本可能因不同操作系统而异。例如，记事本将在 Windows 上使用，vim 或 vi 可以在 Windows 上使用，也可以在 Linux 或 UNIX 上使用。
您使用编辑器创建的文件称为源文件，包含程序源代码。C 程序的源文件通常以扩展名“ .c ”命名。
在开始编程之前，请确保您有一个文本编辑器，并且您有足够的经验来编写计算机程序、将其保存在文件中、编译并最终执行它。
C 编译器
源文件中编写的源代码是程序的人类可读源。它需要被“编译”，变成机器语言，这样你的CPU才能真正按照给定的指令执行程序。
该 C 编程语言编译器将用于将您的源代码编译为最终的可执行程序。我假设您具有有关编程语言编译器的基本知识。
最常用且免费的编译器是 GNU C/C++ 编译器，否则，如果您有各自的操作系统，则可以使用 HP 或 Solaris 的编译器。
以下部分将指导您如何在各种操作系统上安装 GNU C/C++ 编译器。我将 C/C++ 一起提及是因为 GNU gcc 编译器适用于 C 和 C++ 编程语言。
在 UNIX/Linux 上安装
如果您使用的是Linux 或 UNIX，请通过从命令行输入以下命令来检查您的系统上是否安装了 GCC -
$ gcc -v
如果你的机器上安装了 GNU 编译器，那么它应该打印一条消息，如下所示 -
Using built-in specs. Target: i386-redhat-linux Configured with: ../configure --prefix=/usr ....... Thread model: posix gcc version 4.1.2 20080704 (Red Hat 4.1.2-46)
如果未安装 GCC，则您必须使用https://gcc.gnu.org/install/上提供的详细说明自行安装它
本教程是基于 Linux 编写的，所有给出的示例都是在 Linux 系统的 Cent OS 版本上编译的。
Mac 操作系统上的安装
如果您使用 Mac OS X，获取 GCC 的最简单方法是从 Apple 网站下载 Xcode 开发环境并按照简单的安装说明进行操作。设置 Xcode 后，您将能够使用 C/C++ 的 GNU 编译器。
Xcode 目前可在developer.apple.com/technologies/tools/上获取。
在 Windows 上安装
要在 Windows 上安装 GCC，您需要安装 MinGW。要安装 MinGW，请访问 MinGW 主页www.mingw.org，然后点击链接进入 MinGW 下载页面。下载最新版本的 MinGW 安装程序，该程序应命名为 MinGW-<version>.exe。
安装 MinWG 时，您至少必须安装 gcc-core、gcc-g++、binutils 和 MinGW 运行时，但您可能希望安装更多。
将 MinGW 安装的 bin 子目录添加到PATH环境变量中，以便您可以在命令行上通过简单名称指定这些工具。
安装完成后，您将能够从 Windows 命令行运行 gcc、g++、ar、ranlib、dlltool 和其他几个 GNU 工具。
使用 C 算法的 DSA
算法
算法是一个逐步的过程，它定义了一组按一定顺序执行以获得所需输出的指令。在数据结构方面，算法的类别如下。
搜索- 搜索数据结构中的项目的算法。
排序- 按特定顺序对项目进行排序的算法
插入- 在数据结构中插入项目的算法
更新- 更新数据结构中现有项目的算法
删除- 从数据结构中删除现有项目的算法
算法分析
算法分析涉及数据结构的各种操作的执行时间或运行时间。操作的运行时间可以定义为否。每个操作执行的计算机指令的数量。由于任何操作的确切运行时间因一台计算机而异，因此我们通常将任何操作的运行时间分析为 n 的某个函数，其中 n 为编号。数据结构中该操作中处理的项目数。
渐近分析
渐近分析是指以数学计算单位计算任何操作的运行时间。例如，一个操作的运行时间计算为f (n)，另一操作的运行时间计算为g (n 2 )。这意味着第一个操作的运行时间将随着n的增加而线性增加，而第二个操作的运行时间将随着n的增加而呈指数增加。类似地，如果 n 非常小，则两个操作的运行时间将几乎相同。
渐近符号
以下是计算算法运行时间复杂度时常用的渐近符号。
Ο 表示法
Ω 表示法
θ 表示法
大哦符号，Ο
Ο(n) 是表达算法运行时间上限的正式方式。它衡量最坏情况的时间复杂度或算法完成可能需要的最长时间。
例如，对于函数f (n)
Big Oh 表示法用于简化函数。例如，我们可以将特定的函数方程 7nlogn + n - 1 替换为 Ο( f (nlogn))。考虑如下场景 -
它表明，使用常数 c = 8 和 n 0 = 2， f (n) = 7nlogn +n - 1 在O (nlogn)的范围内。
欧米茄表示法，Ω
Ω(n) 是表达算法运行时间下限的正式方式。它衡量最佳情况的时间复杂度或算法完成可能需要的最佳时间。
例如，对于函数f (n)
Theta 表示法，θ
θ(n) 是表达算法运行时间下限和上限的正式方式。其表示如下。
使用 C 的 DSA - 概念
数据结构是一种组织数据以使其能够有效使用的方法。以下术语是数据结构的基本术语。
数据定义
数据定义定义了具有以下特征的特定数据。
Atomics- 定义应该定义一个概念
可追踪- 定义应该能够映射到某些数据元素。
准确- 定义应该明确。
清晰简洁- 定义应该是可以理解的。
数据对象
数据对象表示具有数据的对象。
数据类型
数据类型是对整数、字符串等各种类型的数据进行分类的方式，它决定了相应类型的数据可以使用的值、可以对相应类型的数据执行的操作类型。两种类型的数据类型 -
内置数据类型
派生数据类型
内置数据类型
语言内置支持的那些数据类型称为内置数据类型。例如，大多数语言都提供以下内置数据类型。
整数
布尔值（真、假）
浮点数（十进制数）
字符和字符串
派生数据类型
那些与实现无关的数据类型，因为它们可以以一种或其他方式实现，被称为派生数据类型。这些数据类型通常是通过主数据类型或内置数据类型及其关联操作的组合来构建的。例如 -
列表
大批
堆
队列
使用 C 数组的 DSA
概述
数组是一个可以容纳固定数量的项目的容器，并且这些项目应该具有相同的类型。大多数数据结构都使用数组来实现其算法。以下是理解数组概念的重要术语。
元素- 存储在数组中的每个项目称为元素。
索引- 数组中元素的每个位置都有一个数字索引，用于标识该元素。
数组表示
根据上图所示，以下是需要考虑的要点。
索引从0开始。
数组长度为8，这意味着它可以存储8个元素。
每个元素都可以通过其索引来访问。例如，我们可以将索引 6 处的元素获取为 9。
基本操作
以下是数组支持的基本操作。
插入- 在给定索引处添加一个元素。
删除- 删除给定索引处的元素。
搜索- 使用给定索引或按值搜索元素。
更新- 更新给定索引处的元素。
在 C 中，当使用大小初始化数组时，它会按以下顺序为其元素分配默认值。
| 先生编号 | 数据类型 | 默认值 |
|---|---|---|
| 1 | 布尔值 | 错误的 |
| 2 | 字符 | 0 |
| 3 | 整数 | 0 |
| 4 | 漂浮 | 0.0 |
| 5 | 双倍的 | 0.0f |
| 6 | 空白 | |
| 7 | wchar_t | 0 |
例子
#include <stdio.h>
#include <string.h>
static void display(int intArray[], int length){
int i=0;
printf("Array : [");
for(i = 0; i < length; i++) {
/* display value of element at index i. */
printf(" %d ", intArray[i]);
}
printf(" ]\n ");
}
int main() {
int i = 0;
/* Declare an array */
int intArray[8];
// initialize elements of array n to 0
for ( i = 0; i < 8; i++ ) {
intArray[ i ] = 0; // set elements to default value of 0;
}
printf("Array with default data.");
/* Display elements of an array.*/
display(intArray,8);
/* Operation : Insertion
Add elements in the array */
for(i = 0; i < 8; i++) {
/* place value of i at index i. */
printf("Adding %d at index %d\n",i,i);
intArray[i] = i;
}
printf("\n");
printf("Array after adding data. ");
display(intArray,8);
/* Operation : Insertion
Element at any location can be updated directly */
int index = 5;
intArray[index] = 10;
printf("Array after updating element at index %d.\n",index);
display(intArray,8);
/* Operation : Search using index
Search an element using index.*/
printf("Data at index %d:%d\n" ,index,intArray[index]);
/* Operation : Search using value
Search an element using value.*/
int value = 4;
for(i = 0; i < 8; i++) {
if(intArray[i] == value ){
printf("value %d Found at index %d \n", intArray[i],i);
break;
}
}
return 0;
}
输出
如果我们编译并运行上面的程序，那么它将产生以下输出 -
Array with default data.Array : [ 0 0 0 0 0 0 0 0 ] Adding 0 at index 0 Adding 1 at index 1 Adding 2 at index 2 Adding 3 at index 3 Adding 4 at index 4 Adding 5 at index 5 Adding 6 at index 6 Adding 7 at index 7 Array after adding data. Array : [ 0 1 2 3 4 5 6 7 ] Array after updating element at index 5. Array : [ 0 1 2 3 4 10 6 7 ] Data at index 5: 10 4 Found at index 4
使用 C 链表的 DSA
概述
链接列表是包含项目的链接序列。每个链接都包含到另一个链接的连接。链表是继数组之后第二常用的数据结构。以下是理解链表概念的重要术语。
链接- 链表的每个链接都可以存储称为元素的数据。
Next - 链接列表的每个链接都包含一个指向下一个链接的链接，称为“Next”。
LinkedList - LinkedList 包含指向名为 First 的第一个链接的连接链接。
链表表示
根据上图所示，以下是需要考虑的要点。
LinkedList 包含一个名为first 的链接元素。
每个链接携带一个数据字段和一个接下来调用的链接字段。
每个链接都使用其下一个链接与其下一个链接进行链接。
Last Link 带有一个为 null 的 Link 来标记列表的结尾。
链表的类型
以下是链表的各种风格。
简单链接列表- 项目导航仅向前。
双向链表- 项目可以向前和向后导航。
循环链表- 最后一项包含第一个元素作为下一个元素的链接，第一个元素包含到最后一个元素作为上一个元素的链接。
基本操作
以下是列表支持的基本操作。
插入- 在列表的开头添加一个元素。
删除- 删除列表开头的元素。
显示- 显示完整列表。
搜索- 使用给定键搜索元素。
删除- 使用给定键删除元素。
插入操作
插入是一个三步过程 -
使用提供的数据创建新链接。
将新链接指向旧的第一个链接。
将第一个链接指向此新链接。
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
删除操作
删除是一个两步过程 -
获取第一个链接指向的链接作为临时链接。
将第一个链接指向临时链接的下一个链接。
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//mark next to first link as first
head = head->next;
//return the deleted link
return tempLink;
}
导航操作
导航是一个递归步骤过程，是搜索、删除等许多操作的基础。 -
获取第一个链接指向的链接作为当前链接。
检查当前链接是否不为空并显示它。
将当前链接指向当前链接的下一个链接并移至上述步骤。
注意 -
//display the list
void printList(){
struct node *ptr = head;
printf("\n[ ");
//start from the beginning
while(ptr != NULL){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
高级操作
以下是为列表指定的高级操作。
排序- 根据特定顺序对列表进行排序。
反转- 反转链表。
排序操作
我们使用冒泡排序来对列表进行排序。
void sort(){
int i, j, k, tempKey, tempData ;
struct node *current;
struct node *next;
int size = length();
k = size ;
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head ;
next = head->next ;
for ( j = 1 ; j < k ; j++ ) {
if ( current->data > next->data ) {
tempData = current->data ;
current->data = next->data;
next->data = tempData ;
tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}
current = current->next;
next = next->next;
}
}
}
反向操作
以下代码演示了反转单个链表。
void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
例子
LinkedListDemo.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
//display the list
void printList(){
struct node *ptr = head;
printf("\n[ ");
//start from the beginning
while(ptr != NULL){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//mark next to first link as first
head = head->next;
//return the deleted link
return tempLink;
}
//is list empty
bool isEmpty(){
return head == NULL;
}
int length(){
int length = 0;
struct node *current;
for(current = head; current!=NULL;
current = current->next){
length++;
}
return length;
}
//find a link with given key
struct node* find(int key){
//start from the first link
struct node* current = head;
//if list is empty
if(head == NULL){
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next == NULL){
return NULL;
} else {
//go to next link
current = current->next;
}
}
//if data found, return the current Link
return current;
}
//delete a link with given key
struct node* delete(int key){
//start from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is empty
if(head == NULL){
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next == NULL){
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}
//found a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
previous->next = current->next;
}
return current;
}
void sort(){
int i, j, k, tempKey, tempData ;
struct node *current;
struct node *next;
int size = length();
k = size ;
for ( i = 0 ; i < size - 1 ; i++, k-- ) {
current = head ;
next = head->next ;
for ( j = 1 ; j < k ; j++ ) {
if ( current->data > next->data ) {
tempData = current->data ;
current->data = next->data;
next->data = tempData ;
tempKey = current->key;
current->key = next->key;
next->key = tempKey;
}
current = current->next;
next = next->next;
}
}
}
void reverse(struct node** head_ref) {
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Original List: ");
//print list
printList();
while(!isEmpty()){
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}
printf("\nList after deleting all items: ");
printList();
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nRestored List: ");
printList();
printf("\n");
struct node *foundLink = find(4);
if(foundLink != NULL){
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}
delete(4);
printf("List after deleting an item: ");
printList();
printf("\n");
foundLink = find(4);
if(foundLink != NULL){
printf("Element found: ");
printf("(%d,%d) ",foundLink->key,foundLink->data);
printf("\n");
} else {
printf("Element not found.");
}
printf("\n");
sort();
printf("List after sorting the data: ");
printList();
reverse(&head);
printf("\nList after reversing the data: ");
printList();
}
输出
如果我们编译并运行上面的程序，那么它将产生以下输出 -
Original List: [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ] Deleted value:(6,56) Deleted value:(5,40) Deleted value:(4,1) Deleted value:(3,30) Deleted value:(2,20) Deleted value:(1,10) List after deleting all items: [ ] Restored List: [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ] Element found: (4,1) List after deleting an item: [ (6,56) (5,40) (3,30) (2,20) (1,10) ] Element not found. List after sorting the data: [ (1,10) (2,20) (3,30) (5,40) (6,56) ] List after reversing the data: [ (6,56) (5,40) (3,30) (2,20) (1,10) ]
使用 C 的 DSA - 双向链表
概述
双链表是链表的一种变体，与单链表相比，双链表可以轻松地向前和向后两种方式进行导航。以下是理解双向链表概念的重要术语。
链接- 链表的每个链接都可以存储称为元素的数据。
Next - 链接列表的每个链接都包含一个指向下一个链接的链接，称为“Next”。
Prev - 链接列表的每个链接都包含一个指向称为 Prev 的上一个链接的链接。
LinkedList - LinkedList 包含指向名为 First 的第一个链接和名为 Last 的最后一个链接的连接链接。
双向链表表示
根据上图所示，以下是需要考虑的要点。
双向链表包含一个名为first 和last 的链接元素。
每个链接携带一个数据字段和一个接下来调用的链接字段。
每个链接都使用其下一个链接与其下一个链接进行链接。
每个链接都使用其上一个链接与其前一个链接进行链接。
Last Link 带有一个为 null 的 Link 来标记列表的结尾。
基本操作
以下是列表支持的基本操作。
插入- 在列表的开头添加一个元素。
删除- 删除列表开头的元素。
Insert Last - 在列表末尾添加一个元素。
删除最后一个- 从列表末尾删除一个元素。
Insert After - 在列表的项目之后添加一个元素。
删除- 使用 key 从列表中删除一个元素。
向前显示- 以向前方式显示完整列表。
向后显示- 以向后方式显示完整列表。
插入操作
以下代码演示了双向链表开头的插入操作。
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()){
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
删除操作
以下代码演示了双向链表开头的删除操作。
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL){
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
操作结束时插入
以下代码演示了双向链表中最后位置的插入操作。
//insert link at the last location
void insertLast(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()){
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
例子
双链表Demo.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
struct node *prev;
};
//this link always point to first Link
struct node *head = NULL;
//this link always point to last Link
struct node *last = NULL;
struct node *current = NULL;
//is list empty
bool isEmpty(){
return head == NULL;
}
int length(){
int length = 0;
struct node *current;
for(current = head; current!=NULL;
current = current->next){
length++;
}
return length;
}
//display the list in from first to last
void displayForward(){
//start from the beginning
struct node *ptr = head;
//navigate till the end of the list
printf("\n[ ");
while(ptr != NULL){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
printf(" ]");
}
//display the list from last to first
void displayBackward(){
//start from the last
struct node *ptr = last;
//navigate till the start of the list
printf("\n[ ");
while(ptr != NULL){
//print data
printf("(%d,%d) ",ptr->key,ptr->data);
//move to next item
ptr = ptr ->prev;
printf(" ");
}
printf(" ]");
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()){
//make it the last link
last = link;
} else {
//update first prev link
head->prev = link;
}
//point it to old first link
link->next = head;
//point first to new first link
head = link;
}
//insert link at the last location
void insertLast(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key = key;
link->data = data;
if(isEmpty()){
//make it the last link
last = link;
} else {
//make link a new last link
last->next = link;
//mark old last node as prev of new link
link->prev = last;
}
//point last to new last node
last = link;
}
//delete first item
struct node* deleteFirst(){
//save reference to first link
struct node *tempLink = head;
//if only one link
if(head->next == NULL){
last = NULL;
} else {
head->next->prev = NULL;
}
head = head->next;
//return the deleted link
return tempLink;
}
//delete link at the last location
struct node* deleteLast(){
//save reference to last link
struct node *tempLink = last;
//if only one link
if(head->next == NULL){
head = NULL;
} else {
last->prev->next = NULL;
}
last = last->prev;
//return the deleted link
return tempLink;
}
//delete a link with given key
struct node* delete(int key){
//start from the first link
struct node* current = head;
struct node* previous = NULL;
//if list is empty
if(head == NULL){
return NULL;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next == NULL){
return NULL;
} else {
//store reference to current link
previous = current;
//move to next link
current = current->next;
}
}
//found a match, update the link
if(current == head) {
//change first to point to next link
head = head->next;
} else {
//bypass the current link
current->prev->next = current->next;
}
if(current == last){
//change last to point to prev link
last = current->prev;
} else {
current->next->prev = current->prev;
}
return current;
}
bool insertAfter(int key, int newKey, int data){
//start from the first link
struct node *current = head;
//if list is empty
if(head == NULL){
return false;
}
//navigate through list
while(current->key != key){
//if it is last node
if(current->next == NULL){
return false;
} else {
//move to next link
current = current->next;
}
}
//create a link
struct node *newLink = (struct node*) malloc(sizeof(struct node));
newLink->key = key;
newLink->data = data;
if(current==last) {
newLink->next = NULL;
last = newLink;
} else {
newLink->next = current->next;
current->next->prev = newLink;
}
newLink->prev = current;
current->next = newLink;
return true;
}
main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("\nList (First to Last): ");
displayForward();
printf("\n");
printf("\nList (Last to first): ");
displayBackward();
printf("\nList , after deleting first record: ");
deleteFirst();
displayForward();
printf("\nList , after deleting last record: ");
deleteLast();
displayForward();
printf("\nList , insert after key(4) : ");
insertAfter(4,7, 13);
displayForward();
printf("\nList , after delete key(4) : ");
delete(4);
displayForward();
}
输出
如果我们编译并运行上面的程序，那么它将产生以下输出 -
List (First to Last): [ (6,56) (5,40) (4,1) (3,30) (2,20) (1,10) ] List (Last to first): [ (1,10) (2,20) (3,30) (4,1) (5,40) (6,56) ] List , after deleting first record: [ (5,40) (4,1) (3,30) (2,20) (1,10) ] List , after deleting last record: [ (5,40) (4,1) (3,30) (2,20) ] List , insert after key(4) : [ (5,40) (4,1) (4,13) (3,30) (2,20) ] List , after delete key(4) : [ (5,40) (4,13) (3,30) (2,20) ]
使用 C 的 DSA - 循环链表
概述
循环链表是链表的一种变体，其中第一个元素指向最后一个元素，最后一个元素指向第一个元素。单链表和双向链表都可以做成循环链表。
作为循环的单向链表
循环双向链表
根据上图所示，以下是需要考虑的要点。
在单链表和双链表两种情况下，Last Link'next 都指向列表的第一个链接。
在双向链表的情况下，第一个链接的 prev 指向列表的最后一个。
基本操作
以下是循环列表支持的重要操作。
insert - 在列表的开头插入一个元素。
删除- 从列表的开头插入一个元素。
显示- 显示列表。
长度操作
以下代码演示了基于单链表的循环链表中的插入操作。
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key =key;
link->data=data;
if (isEmpty()) {
head = link;
head->next = head;
} else {
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
}
删除操作
下面的代码演示了基于单链表的循环链表中的删除操作。
//delete first item
struct node * deleteFirst(){
//save reference to first link
struct node *tempLink = head;
if(head->next == head){
head = NULL;
return tempLink;
}
//mark next to first link as first
head = head->next;
//return the deleted link
return tempLink;
}
显示列表操作
以下代码演示了循环链表中的显示列表操作。
//display the list
void printList(){
struct node *ptr = head;
printf("\n[ ");
//start from the beginning
if(head != NULL){
while(ptr->next != ptr){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
printf(" ]");
}
例子
双链表Demo.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
struct node {
int data;
int key;
struct node *next;
};
struct node *head = NULL;
struct node *current = NULL;
bool isEmpty(){
return head == NULL;
}
int length(){
int length = 0;
//if list is empty
if(head == NULL){
return 0;
}
current = head->next;
while(current != head){
length++;
current = current->next;
}
return length;
}
//insert link at the first location
void insertFirst(int key, int data){
//create a link
struct node *link = (struct node*) malloc(sizeof(struct node));
link->key =key;
link->data=data;
if (isEmpty()) {
head = link;
head->next = head;
} else {
//point it to old first node
link->next = head;
//point first to new first node
head = link;
}
}
//delete first item
struct node * deleteFirst(){
//save reference to first link
struct node *tempLink = head;
if(head->next == head){
head = NULL;
return tempLink;
}
//mark next to first link as first
head = head->next;
//return the deleted link
return tempLink;
}
//display the list
void printList(){
struct node *ptr = head;
printf("\n[ ");
//start from the beginning
if(head != NULL){
while(ptr->next != ptr){
printf("(%d,%d) ",ptr->key,ptr->data);
ptr = ptr->next;
}
}
printf(" ]");
}
main() {
insertFirst(1,10);
insertFirst(2,20);
insertFirst(3,30);
insertFirst(4,1);
insertFirst(5,40);
insertFirst(6,56);
printf("Original List: ");
//print list
printList();
while(!isEmpty()){
struct node *temp = deleteFirst();
printf("\nDeleted value:");
printf("(%d,%d) ",temp->key,temp->data);
}
printf("\nList after deleting all items: ");
printList();
}
输出
如果我们编译并运行上面的程序，那么它将产生以下输出 -
Original List: [ (6,56) (5,40) (4,1) (3,30) (2,20) ] Deleted value:(6,56) Deleted value:(5,40) Deleted value:(4,1) Deleted value:(3,30) Deleted value:(2,20) Deleted value:(1,10) List after deleting all items: [ ]
使用 C 的 DSA - 堆栈内存溢出
概述
堆栈是一种只允许在一端对数据进行操作的数据结构。它只允许访问最后插入的数据。堆栈也称为 LIFO（后进先出）数据结构，Push 和 Pop 操作以这样的方式相关：只有最后压入（添加到堆栈）的项目才能弹出（从堆栈中删除）。
堆栈表示
在本文中，我们将使用数组来实现 Stack。
基本操作
以下是堆栈的两个主要操作。
Push - 将一个元素压入栈顶。
Pop - 从堆栈顶部弹出一个元素。
以下是堆栈支持的更多操作。
Peek - 获取堆栈顶部的元素。
isFull - 检查堆栈是否已满。
isEmpty - 检查堆栈是否为空。
推送操作
每当一个元素被推入堆栈时，堆栈就会将该元素存储在存储的顶部，并递增顶部索引以供以后使用。如果存储已满，通常会显示错误消息。
// Operation : Push
// push item on the top of the stack
void push(int data) {
if(!isFull()){
// increment top by 1 and insert data
intArray[++top] = data;
} else {
printf("Cannot add data. Stack is full.\n");
}
}
流行操作
每当要从堆栈中弹出一个元素时，堆栈都会从存储顶部检索该元素，并减少顶部索引以供以后使用。
// Operation : Pop
// pop item from the top of the stack
int pop() {
//retrieve data and decrement the top by 1
return intArray[top--];
}
例子
StackDemo.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
// size of the stack
int size = 8;
// stack storage
int intArray[8];
// top of the stack
int top = -1;
// Operation : Pop
// pop item from the top of the stack
int pop() {
//retrieve data and decrement the top by 1
return intArray[top--];
}
// Operation : Peek
// view the data at top of the stack
int peek() {
//retrieve data from the top
return intArray[top];
}
//Operation : isFull
//return true if stack is full
bool isFull(){
return (top == size-1);
}
// Operation : isEmpty
// return true if stack is empty
bool isEmpty(){
return (top == -1);
}
// Operation : Push
// push item on the top of the stack
void push(int data) {
if(!isFull()){
// increment top by 1 and insert data
intArray[++top] = data;
} else {
printf("Cannot add data. Stack is full.\n");
}
}
main() {
// push items on to the stack
push(3);
push(5);
push(9);
push(1);
push(12);
push(15);
printf("Element at top of the stack: %d\n" ,peek());
printf("Elements: \n");
// print stack data
while(!isEmpty()){
int data = pop();
printf("%d\n",data);
}
printf("Stack full: %s\n" , isFull()?"true":"false");
printf("Stack empty: %s\n" , isEmpty()?"true":"false");
}
输出
如果我们编译并运行上面的程序，那么它将产生以下输出 -
Element at top of the stack: 15 Elements: 15 12 1 9 5 3 Stack full: false Stack empty: true
使用 C 的 DSA - 解析表达式
像 2*(3*4) 这样的普通算术表达式对于人类来说更容易解析，但对于算法来说解析这样的表达式会非常困难。为了缓解这一困难，可以使用两步方法通过算法来解析算术表达式。
将提供的算术表达式转换为后缀表示法。
评估后缀表示法。
中缀表示法
正常算术表达式遵循中缀表示法，其中运算符位于操作数之间。例如 A+B，这里 A 是第一个操作数，B 是第二个操作数，+ 是作用于两个操作数的运算符。
后缀表示法
后缀表示法与普通算术表达式或中缀表示法的不同之处在于运算符位于操作数之后。例如，请考虑以下示例。
| 先生。没有。 | 中缀表示法 | 后缀表示法 |
|---|---|---|
| 1 | A+B | AB+ |
| 2 | (A+B)*C | AB+C* |
| 3 | A*(B+C) | ABC+* |
| 4 | A/B+C/D | AB/CD/+ |
| 5 | (A+B)*(C+D) | AB+CD+* |
| 6 | ((A+B)*C)-D | AB+C*D- |
中缀到后缀转换
在研究如何将中缀转换为后缀表示法之前，我们需要考虑以下中缀表达式求值的基础知识。
中缀表达式的计算从左到右开始。
请记住优先级，例如 * 的优先级高于 +。例如
2+3*4 = 2+12。
2+3*4 = 14。
-
使用括号覆盖优先级，例如
(2+3)*4 = 5*4。
(2+3)*4=20。
现在让我们手动将一个简单的中缀表达式 A+B*C 转换为后缀表达式。
| 先生编号 | 字符读取 | 到目前为止已解析的中缀表达 | 后缀表达式发展至今 | 评论 |
|---|---|---|---|---|
| 1 | A | A | A | |
| 2 | + | A+ | A | |
| 3 | 乙 | A+B | AB | |
| 4 | * | A+B* | AB | + 无法复制，因为 * 具有更高的优先级。 |
| 5 | C | A+B*C | ABC | |
| 6 | A+B*C | ABC* | 复制 * 作为两个操作数 B 和 C | |
| 7 | A+B*C | ABC*+ | 复制 + 作为两个操作数 BC 和 A |
现在让我们使用堆栈将上面的中缀表达式 A+B*C 转换为后缀表达式。
| 先生编号 | 字符读取 | 到目前为止已解析的中缀表达 | 后缀表达式发展至今 | 堆栈内容 | 评论 |
|---|---|---|---|---|---|
| 1 | A | A | A | ||
| 2 | + | A+ | A | + | 将 + 运算符压入堆栈。 |
| 3 | 乙 | A+B | AB | + | |
| 4 | * | A+B* | AB | +* | 运算符 * 的优先级高于 +。将 * 运算符推入堆栈。否则会弹出+。 |
| 5 | C | A+B*C | ABC | +* | |
| 6 | A+B*C | ABC* | + | 没有更多的操作数，弹出 * 运算符。 | |
| 7 | A+B*C | ABC*+ | 弹出 + 运算符。 |
现在让我们看另一个例子，通过使用堆栈将中缀表达式 A*(B+C) 转换为后缀表达式。
| 先生编号 | 字符读取 | 到目前为止已解析的中缀表达 | 后缀表达式发展至今 | 堆栈内容 | 评论 |
|---|---|---|---|---|---|
| 1 | A | A | A | ||
| 2 | * | A* | A | * | 将 * 运算符推入堆栈。 |
| 3 | （ | A*（ | A | *( | 将 ( 推入堆栈。 |
| 4 | 乙 | A*(B | AB | *( | |
| 5 | + | A*(B+ | AB | *(+ | 将 + 压入堆栈。 |
| 6 | C | A*(B+C | ABC | *(+ | |
| 7 | ） | A*(B+C) | ABC+ | *( | 弹出 + 运算符。 |
| 8 | A*(B+C) | ABC+ | * | 弹出 ( 运算符。 | |
| 9 | A*(B+C) | ABC+* | 弹出其余的运算符。 |
例子
现在我们将演示如何使用堆栈将中缀表达式转换为后缀表达式，然后计算后缀表达式。
#include<stdio.h>
#include<string.h>
//char stack
char stack[25];
int top=-1;
void push(char item) {
stack[++top]=item;
}
char pop() {
return stack[top--];
}
//returns precedence of operators
int precedence(char symbol) {
switch(symbol) {
case '+':
case '-':
return 2;
break;
case '*':
case '/':
return 3;
break;
case '^':
return 4;
break;
case '(':
case ')':
case '#':
return 1;
break;
}
}
//check whether the symbol is operator?
int isOperator(char symbol) {
switch(symbol){
case '+':
case '-':
case '*':
case '/':
case '^':
case '(':
case ')':
return 1;
break;
default:
return 0;
}
}
//converts infix expression to postfix
void convert(char infix[],char postfix[]){
int i,symbol,j=0;
stack[++top]='#';
for(i=0;i<strlen(infix);i++){
symbol=infix[i];
if(isOperator(symbol)==0){
postfix[j]=symbol;
j++;
} else {
if(symbol=='('){
push(symbol);
} else {
if(symbol==')'){
while(stack[top]!='('){
postfix[j]=pop();
j++;
}
pop();//pop out (.
} else {
if(precedence(symbol)>precedence(stack[top])) {
push(symbol);
} else {
while(precedence(symbol)<=precedence(stack[top])) {
postfix[j]=pop();
j++;
}
push(symbol);
}
}
}
}
}
while(stack[top]!='#') {
postfix[j]=pop();
j++;
}
postfix[j]='\0';//null terminate string.
}
//int stack
int stack_int[25];
int top_int=-1;
void push_int(int item) {
stack_int[++top_int]=item;
}
char pop_int() {
return stack_int[top_int--];
}
//evaluates postfix expression
int evaluate(char *postfix){
char ch;
int i=0,operand1,operand2;
while( (ch=postfix[i++]) != '\0') {
if(isdigit(ch)){
push_int(ch-'0'); // Push the operand
} else {
//Operator,pop two operands
operand2=pop_int();
operand1=pop_int();
switch(ch) {
case '+':
push_int(operand1+operand2);
break;
case '-':
push_int(operand1-operand2);
break;
case '*':
push_int(operand1*operand2);
break;
case '/':
push_int(operand1/operand2);
break;
}
}
}
return stack_int[top_int];
}
void main() {
char infix[25] = "1*(2+3)",postfix[25];
convert(infix,postfix);
printf("Infix expression is: %s\n" , infix);
printf("Postfix expression is: %s\n" , postfix);
printf("Evaluated expression is: %d\n" , evaluate(postfix));
}
输出
如果我们编译并运行上面的程序，那么它将产生以下输出 -
Infix expression is: 1*(2+3) Postfix expression is: 123+* Result is: 5
使用 C 队列的 DSA
概述
队列是一种类似于堆栈的数据结构，主要区别在于插入的第一个项目是要删除的第一个项目（FIFO - 先进先出），其中堆栈基于 LIFO（后进先出）原理。
队列表示
基本操作
insert / enqueue - 将一个项目添加到队列的末尾。
删除/出队- 从队列前面删除一个项目。
在本文中，我们将使用数组来实现队列。下面还有一些队列支持的操作。
Peek - 获取队列前面的元素。
isFull - 检查队列是否已满。
isEmpty - 检查队列是否为空。
插入/入队操作
每当一个元素插入到队列中时，队列都会增加后索引以供以后使用，并将该元素存储在存储的后端。如果后端到达最后一个索引并且它被包裹到底部位置。这种排列称为环绕，这种队列是循环队列。该方法也称为入队操作。
void insert(int data){
if(!isFull()){
if(rear == MAX-1){
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
删除/出队操作
每当要从队列中删除元素时，队列都会使用前索引获取该元素并递增前索引。作为环绕安排，如果前面的索引大于数组的最大索引，则将其设置为 0。
int removeData(){
int data = intArray[front++];
if(front == MAX){
front = 0;
}
itemCount--;
return data;
}
例子
队列演示.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 6
int intArray[MAX];
int front = 0;
int rear = -1;
int itemCount = 0;
int peek(){
return intArray[front];
}
bool isEmpty(){
return itemCount == 0;
}
bool isFull(){
return itemCount == MAX;
}
int size(){
return itemCount;
}
void insert(int data){
if(!isFull()){
if(rear == MAX-1){
rear = -1;
}
intArray[++rear] = data;
itemCount++;
}
}
int removeData(){
int data = intArray[front++];
if(front == MAX){
front = 0;
}
itemCount--;
return data;
}
int main() {
/* insert 5 items */
insert(3);
insert(5);
insert(9);
insert(1);
insert(12);
// front : 0
// rear : 4
// ------------------
// index : 0 1 2 3 4
// ------------------
// queue : 3 5 9 1 12
insert(15);
// front : 0
// rear : 5
// ---------------------
// index : 0 1 2 3 4 5
// ---------------------
// queue : 3 5 9 1 12 15
if(isFull()){
printf("Queue is full!\n");
}
// remove one item
int num = removeData();
printf("Element removed: %d\n",num);
// front : 1
// rear : 5
// -------------------
// index : 1 2 3 4 5
// -------------------
// queue : 5 9 1 12 15
// insert more items
insert(16);
// front : 1
// rear : -1
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 5 9 1 12 15
// As queue is full, elements will not be inserted.
insert(17);
insert(18);
// ----------------------
// index : 0 1 2 3 4 5
// ----------------------
// queue : 16 5 9 1 12 15
printf("Element at front: %d\n",peek());
printf("----------------------\n");
printf("index : 5 4 3 2 1 0\n");
printf("----------------------\n");
printf("Queue: ");
while(!isEmpty()){
int n = removeData();
printf("%d ",n);
}
}
输出
如果我们编译并运行上面的程序，那么它将产生以下输出 -
Queue is full! Element removed: 3 Element at front: 5 ---------------------- index : 5 4 3 2 1 0 ---------------------- Queue: 5 9 1 12 15 16
使用 C 的 DSA - 优先级队列
概述
优先级队列是比队列更专业的数据结构。与普通队列一样，优先级队列的方法相同，但有重大区别。在优先级队列中，项目按键值排序，因此键值最低的项目位于前面，键值最高的项目位于后面，反之亦然。因此，我们根据项目的键值为其分配优先级。洛