常用数据结构与经典算法 简单讲解与示例代码
数据结构与算法
数据结构与算法是一个学习计算机绕不过去的话题，而我们大学之中多数课程之中都使用伪代码进行讲解，给对我们的学习理解也是一把双刃剑，虽然可以让我们自己通过算法、思路自己写出程序，但也可能“一叶障目”致使我们迟迟不知道具体到程序语言上问题出在哪里
所以我想自己使用不同的程序设计语言编写简单的数据结构和讲解一些经典的算法，在复习和记录的过程之中也和大家一起交流讨论数据结构与算法的一些巧妙的设计和个人见解与跳过的“坑”，各位共勉。
帖子会慢慢更新，当然速度可能不太能保证，也可能在后续的更新之中调整文章结构。
常用数据结构
线性表
线性表简介
定义
线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。
优点
线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
特征
1．集合中必存在唯一的一个“第一元素”。
2．集合中必存在唯一的一个 “最后元素” 。
3．除最后一个元素之外，均有唯一的后继。
4．除第一个元素之外，均有唯一的前驱。
线性表示例代码
代码（C语言）
链式线性表 Visual Studio 2019
/**
* 数据结构 C语言链式线性表
* @FileName SingleLinkList.c
* @author W.Lionel.Esaka
*/
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
#define Status int;
#define CORRECT 1;
#define ERROR 0;
#define OVERFLOW -1;
/*单链表的类型定义如下*/
typedef struct node{
DataType data;
struct node* next;
} LinkNode, * LinkList;
/*创建指定长度单链表 尾插法*/
void CreateListTail(LinkList* list, int Number)
{
LinkList node, r;
int i;
srand(time(0));
*list = (LinkList*)malloc(sizeof(LinkList));
r = *list;
for (i = 0; i < Number; i++)
{
node = (LinkNode*)malloc(sizeof(LinkNode));
node->data = rand() % 100 + 1;
r->next = node;
r = node;
}
r->next = NULL;
}
/* 插入元素 */
Status InsertLinkList(LinkList* list, int position, DataType value)
{
int i = 1;
LinkList p, s;
p = *list;
while (p && i < position)
{
p = p->next;
i++;
}
if ( !p || i > position)
{
return ERROR;
}
s = (LinkList)malloc(sizeof(LinkNode));
s->data = value;
s->next = p->next;
p->next = s;
return CORRECT;
}
/*删除元素 */
Status DeleteLinkList(LinkList* list, int position, DataType* value)
{
int i = 1;
LinkList p, q;
p = *list;
while (p->next && i < position)
{
p = p->next;
i++;
}
if (!(p->next) || i > position)
{
return ERROR;
}
q = p->next;
p->next = q->next;
*value = q->data;
free(q);
return CORRECT;
}
/*打印链表数据*/
void DisPlayList(LinkList* list)
{
LinkList p;
p = *list;
int i = 0;
printf("\n链表数据如下:\n");
while (p->next != NULL)
{
p = p->next;
printf("%d,\t", p->data);
i++;
if (i%10 == 0) printf("\n");
}
printf("\n链表长度为%d\n", i);
}
/*
将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B 和C。
其中 B 表中的结点为 A 表中值为奇数的结点，而 C 表中的结点为 A 表中值为偶数的结点。
*/
void func(LinkList* A, LinkList* B, LinkList* C)
{
LinkList p1;
p1 = *A;
while (p1->next != NULL)
{
p1 = p1->next;
if ( odd(p1->data) )
{
InsertLinkList(B, 1, p1->data);
}
else
{
InsertLinkList(C, 1, p1->data);
}
}
}
/*清空链表*/
Status ClearList(LinkList* list)
{
LinkList p, q;
p = (*list)->next;
while (p)
{
q = p->next;
free(p);
p = q;
}
(*list)->next = NULL;
return CORRECT;
}
/*odd(x) 为判奇数函数，x 为奇数，返回 1，否则返回 0。*/
int odd(int x)
{
if (x & 1)
{
return 1;
}
else
{
return 0;
}
}
/*入口 演示main*/
void main()
{
LinkList linklistA, linklistB, linklistC;
LinkList* listA = &linklistA;
LinkList* listB = &linklistB;
LinkList* listC = &linklistC;
int value = 0;
CreateListTail(listA, 20);
printf("单链表LinkListA");
DisPlayList(listA);
printf("\n将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B 和 C \n");
printf("其中 B 表中的结点为 A 表中值为奇数的结点，而 C 表中的结点为 A 表中值为偶数的结点\n");
CreateListTail(listB, 0);
CreateListTail(listC, 0);
func(listA,listB,listC);
printf("单链表LinkListB");
DisPlayList(listB);
printf("\n");
printf("单链表LinkListC");
DisPlayList(listC);
}
单链表实例 学生信息链表
代码（C语言）
学生信息链表 Dev-C++ 5.11
/**
* 数据结构 C语言链式线性表
* @FileName StuInfoSys.c
* @author W.Lionel.Esaka
*/
//头文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
//预处理 布尔变量 宏定义
#define Status int;
#define CORRECT 1;
#define ERROR 0;
#define OVERFLOW -1;
/*定义单链表节点*/
typedef struct Node {
char stunum[10] ;
char name[10] ;
float grade;
struct Node* Next;
} Node;
typedef struct Node* LinkList;
/*
创建指定长度单链表 头插法
根据指定学生个数，逐个输入学生信息
*/
void CreateListHead(LinkList *list,int Number) {
LinkList node;
int i;
*list = (LinkList*)malloc(sizeof(Node));
(*list)->Next = NULL;
printf("请输入%d学生信息\n",Number);
for (i = 0; i < Number; i++) {
node = (LinkList*)malloc(sizeof(Node));
scanf("%s %s %f",&node->stunum,&node->name,&node->grade);
node->Next = (*list)->Next;
(*list)->Next = node;
}
}
/*
创建指定长度单链表 尾插法
根据指定学生个数，逐个输入学生信息
*/
void CreateListTail(LinkList* list, int Number) {
LinkList node,r;
int i;
*list = (LinkList*)malloc(sizeof(LinkList));
r = *list;
for (i = 0; i < Number; i++)
{
node = (Node*)malloc(sizeof(Node));
scanf("%s %s %f",&node->stunum,&node->name,&node->grade);
r->Next = node;
r = node;
}
r->Next = NULL;
}
/*
插入元素
给定一个学生信息，插入到表中指定的位置
*/
Status InsertLinkList(LinkList *list,int position)
{
int i = 1;
LinkList p, s;
p = *list;
printf("请输入要插入到第%d个位置的学生信息\n",position);
while ( p && i < position)
{
p = p->Next;
i++;
}
if ( !p || i > position)
{
return ERROR;
}
s = (LinkList)malloc(sizeof(Node));
scanf("%s %s %f",&s->stunum,&s->name,&s->grade);
s->Next = p->Next;
p->Next = s;
return CORRECT;
}
/*
获取特定位置元素
根据指定的位置可返回相应的学生信息（学号，姓名，成绩）
*/
Status GetValue(LinkList *list, int position)
{
int i = 1;
LinkList p;
p = (*list)->Next;
printf("第%d个位置的学生信息:\n",position);
while ( p!= NULL && i < position ) {
p = p->Next;
i++;
}
if ( !p || i > position)
{
return ERROR;
}
printf("学号：%s\n姓名：%s\n成绩：%f\n",p->stunum,p->name,p->grade);
return CORRECT;
}
/*
删除元素
删除指定位置的学生记录
*/
Status DeleteLinkList(LinkList* list, int position)
{
int i = 1;
LinkList p,q;
p = *list;
while ( p->Next && i < position)
{
p = p->Next;
i++;
}
if ( !(p->Next) || i > position)
{
return ERROR;
}
q = p->Next;
p->Next = q->Next;
free(q);
printf("已删除第%d个位置的学生信息:\n",position);
return CORRECT;
}
/*
搜索元素
根据姓名进行查找，返回此学生的学号和成绩
*/
void SearchNameInList(LinkList *list)
{
LinkList p;
p = *list;
printf("请输入所要查找的学生姓名:\n");
char Searchname[10] ;
scanf("%s",&Searchname);
while (p->Next != NULL)
{
p = p->Next;
if(strcmp(p->name, Searchname) == 0)
printf("学号：%s\n成绩：%f\n",p->stunum,p->grade);
}
}
/*
输出链表数据
逐个显示学生表中所有学生的相关信息
统计表中学生个数
*/
void DisPlayList(LinkList *list)
{
LinkList p;
p = *list;
int i = 0;
while (p->Next != NULL)
{
p = p->Next;
printf("学号：%s\n姓名：%s\n成绩：%f\n",p->stunum,p->name,p->grade);
i++;
}
printf("\n学生总数为%d\n",i);
}
/*入口*/
void main()
{
//创建一个表
LinkList linklist;
LinkList* list = &linklist;
//头插法，创建一个可以包含五个信息的表
CreateListHead(list, 5);
//打印链表
DisPlayList(list);
//在第四个位置插入信息
InsertLinkList(list, 4);
//打印链表
DisPlayList(list);
//获取第三个学生的信息
GetValue(list, 3);
//删除第四个学生的信息
DeleteLinkList(list,4);
//打印链表
DisPlayList(list);
//根据输入的学生姓名 显示其其他信息
SearchNameInList(list);
}
循环链表
循环链表简介
定义
循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。
特征
循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。带尾指针的单循环链表。
循环链表示例代码
代码（C语言）
单循环链表 Visual Studio 2019
/**
* 数据结构 C语言单循环链表
* @FileName Circular_Linked_List.c
* @author W.Lionel.Esaka
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define Status int;
#define CORRECT 1;
#define ERROR 0;
#define OVERFLOW -1;
typedef int ElemType;
/*定义循环链表结点*/
typedef struct CLinkedList {
ElemType data;
struct CLinkedList* Next;
}Node;
/*初始化链表*/
void ListInit(Node** p)//如果链表为空，则创建一个链表，指针域指向自己，否则寻找尾节点，将
{ //将尾节点的指针域指向这个新节点，新节点的指针域指向头结点
int item;
Node* temp;
Node* target;
printf("输入节点的值，输入0结束\n");
while (1)
{
scanf("%d", &item);
if (item == 0) return;
if (*p == NULL) //如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head;
{
*p = (Node*)malloc(sizeof(Node));
if (!*p) exit(0);
(*p)->data = item;
(*p)->Next = *p;
}
else //输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
{
for (target = *p; target->Next != *p; target = target->Next);//寻找尾节点
temp = (Node*)malloc(sizeof(Node));
if (!temp)exit(0);
temp->data = item;
temp->Next = *p; //新节点指向头节点
target->Next = temp;//尾节点指向新节点
}
}
}
/*插入元素*/
void ListInsert(Node** list, int Position)
{
Node*p, *target, *temp;
int i;
ElemType item;
printf("请输入所要插入的数据：\n");
scanf("%d", &item);
fflush(stdin);
if (Position == 1)
{
temp = (Node*)malloc(sizeof(Node));
if (!(temp))
return ERROR;
temp->data = item;
for (target = (*list); target->Next != (*list); target = target->Next);
temp->Next = (*list);
target->Next = temp;
(*list) = temp;
}
else
{
target = (*list);
for (i = 1; i < (Position - 1); i++)
{
target = target->Next;
}
temp = (Node*)malloc(sizeof(Node));
if (!(temp))
return ERROR;
temp->data = item;
p = target->Next;
target->Next = temp;
temp->Next = p;
}
}
/*删除元素*/
void ListDelete(Node** list, int Position)
{
Node *temp, *target;
int i = 1;
if (Position == 1)
{
for (target = (*list); target->Next != (*list); target = target->Next);
temp = *list;
(*list) = (*list)->Next;
target->Next = (*list);
free(temp);
}
else
{ //删除其他节点
for (i = 1, target = *list; target->Next != *list && i != Position - 1; target = target->Next, i++); //首先找出尾节点
if (target->Next == *list) //判断要删除的位置是否大于链表长度，若大于链表长度，特殊处理直接删除尾节点
{
for (target = *list; target->Next->Next != *list; target = target->Next);//找出尾节的前一个节点
temp = target->Next; // 尾节点的前一个节点直接指向头节点 释放原来的尾节点
target->Next = *list;
printf("数字太大删除尾巴\n");
free(temp);
}
else
{
temp = target->Next;// 删除普通节点 找到要删除节点的前一个节点target，使target指向要删除节点的下一个节点 转存删除节点地址
target->Next = temp->Next; // 然后释放这个节点
free(temp);
}
}
}
/*查找元素*/
Status ListSearch(Node*list, int Elem)
{
Node *target;
int i = 1;
for (target = list; target->data != Elem && target->Next != list; i++)
{
target = target->Next;
}
if (target->Next == list && target->data != list->data)
{
return ERROR;
}
return i;
}
/*遍历链表*/
void ListDisplay(Node* list)
{
Node *target;
target = list;
do{
printf("%d\t", target->data);
target = target->Next;
} while (target != list);
printf("\n");
}
/*入口*/
int main(void)
{
Node* list = NULL;
ListInit(&list);
ListDisplay(list);
ListInsert(&list, 5);
ListInsert(&list, 1);
ListDisplay(list);
ListDelete(&list, 2);
ListDelete(&list, 5);
ListDisplay(list);
printf("大小为2的元素在第%d位置上\n",ListSearch(list,2));
printf("大小为3的元素在第%d位置上\n", ListSearch(list, 3));
}
静态链表
静态链表简介
定义
用数组描述的链表，即称为静态链表。
在C语言中，静态链表的表现形式即为结构体数组，结构体变量包括数据域data和游标CUR。
优点与缺点
优点:在插入和删除操作时,只需要修改游标,不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点
缺点:没有解决连续存储分配(数组)带来的表长难以确定的问题；失去了顺序存储结构随机存取的特征
总的来说，静态链表其实时为了给没有指针的编程语言设计的一种实现单链表功能的方法。
尽管我们可以用单链表就不用静态链表了，但这样的思考方式时非常巧妙地，应该理解其思想，以备不时之需。
静态链表示例代码
代码（C语言）
静态链式表 Visual Studio 2019
/**
* 数据结构 C语言 静态链式表
* @FileName SingleLinkList.c
* @author W.Lionel.Esaka
*/
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 1000
#define Status int
#define ERROR 0
#define CORRECT 1
#define OVERFLOW -1
typedef int ElemType;
/*静态链表成员结构体数组*/
typedef struct {
ElemType data;
int cursor;
}Componemt,StaticLinkedList[MAXSIZE];
/*静态链表初始化*/
Status InitList(StaticLinkedList space)
{
int i;
for (i = 0; i < MAXSIZE-1; i++)
space[i].cursor = i + 1;
space[MAXSIZE - 1].cursor = 0;
return CORRECT;
}
/*从备用链表分配新空间*/
int Malloc_SLL(StaticLinkedList space)
{
int i = space[0].cursor;
if (space[0].cursor)
space[0].cursor = space[i].cursor;
return i;
}
/*将之前的空间归为备用链表*/
void Free_SLL(StaticLinkedList space, int k)
{
space[k].cursor = space[0].cursor;
space[0].cursor = k;
}
/*返回当前静态链表长度值*/
int ListLength(StaticLinkedList space) {
int k = space[MAXSIZE - 1].cursor,i = 0;
while (k) {
k = space[k].cursor;
i++;
}
return i;
}
/*插入元素*/
Status InsertElem(StaticLinkedList list, int Position, ElemType value)
{
int j, k, l;
k = MAXSIZE - 1;
if (Position < 1 || Position > ListLength(list) + 1)
return ERROR;
j = Malloc_SLL(list);
if (j)
{
list[j].data = value;
for (l = 1;l <= Position - 1;l++)
{
k = list[k].cursor;
}
list[j].cursor = list[k].cursor;
list[k].cursor = j;
return CORRECT;
}
return CORRECT;
}
/*删除元素*/
Status DeleteElem(StaticLinkedList list, int Position)
{
int j, k;
if (Position < 1 || Position > ListLength(list))
return ERROR;
k = MAXSIZE - 1;
for ( j = 1; j <= Position - 1; j++)
{
k = list[k].cursor;
}
j = list[k].cursor;
list[k].cursor = list[j].cursor;
Free_SLL(list, j);
return CORRECT;
}
/*查找特定位置元素*/
Status GetElem(StaticLinkedList space, int Position, ElemType* value)
{
int j, k;
k = MAXSIZE - 1;
if (Position < 1 || Position > ListLength(space))
{
return ERROR;
}
for (j = 0; j < Position; j++) {
k = space[k].cursor;
}
*value = space[k].data;
return CORRECT;
}
/*打印静态链表*/
void printStaticLinkList(StaticLinkedList space) {
int k, i, m = 0;
k = MAXSIZE - 1;
i = space[k].cursor;
printf("\n当前静态链表数据如下：\n");
while (i != 0) {
printf("No.%d: %d\t", ++m, space[i].data);
i = space[i].cursor;
}
printf("\n");
}
/*入口*/
void main()
{
StaticLinkedList space;
StaticLinkedList* list = &space;
ElemType value;
InitList(list);
printf("此静态链表长度为%d\n", ListLength(list));
InsertElem(list, 1, 12);
InsertElem(list, 2, 13);
InsertElem(list, 3, 14);
printStaticLinkList(list);
GetElem(list,2,&value);
printf("第二个位置为%d\n", value);
DeleteElem(list, 2);
GetElem(list, 2, &value);
printf("第二个位置为%d\n", value);
}
双向链表
双向链表简介
定义
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
特征
循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
双向链表示例代码
代码（C语言）
双向链式线性表 Visual Studio 2019
/**
* 数据结构 C语言 双向链式线性表
* @FileName Dual_LinkedList.c
* @author W.Lionel.Esaka
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
enum status {
Error = 0,
Corrrect = 1,
Overflow = -1
};
enum status Status;
typedef char ElemType;
typedef struct DualList {
ElemType data;
struct DualList* Previous;
struct DualList* Next;
}DualNode, * DualLinkList;
/*创建指定长度链表 尾插法*/
//如果链表为空，则创建一个链表，指针域指向自己
void ListInit(DualNode** p,int Number)
{
DualNode* temp;
DualNode* target;
int i;
printf("输入节点的值，输入0结束\n");
for (i = 0; i < Number; i++)
{
if (*p == NULL) //如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head;
{
*p = (DualNode*)malloc(sizeof(DualNode));
if (!*p) exit(0);
(*p)->data = (char)(i + 65);
(*p)->Next = *p;
(*p)->Previous = *p;
}
else
{
for (target = *p; target->Next != *p; target = target->Next);//寻找尾节点
temp = (DualNode*)malloc(sizeof(DualNode));
if (!temp)exit(0);
temp->data = (char)(i + 65);
temp->Next = *p; //新节点指向头节点
(*p)->Previous = temp;
target->Next = temp; //尾节点指向新节点
temp->Previous = target;
}
}
}
/*插入元素*/
void ListInsert(DualNode** list, int Position)
{
DualNode* p, * target, * temp;
int i;
ElemType item;
printf("请输入所要插入的数据：\n");
scanf("%d", &item);
fflush(stdin);
if (Position == 1)
{
temp = (DualNode*)malloc(sizeof(DualNode));
if (!(temp))
return Error;
temp->data = item;
for (target = (*list); target->Next != (*list); target = target->Next);
temp->Next = (*list);
target->Next = temp;
(*list)->Previous = temp;
(*list) = temp;
}
else
{
target = (*list);
for (i = 1; i < (Position - 1); i++)
{
target = target->Next;
}
temp = (DualNode*)malloc(sizeof(DualNode));
if (!(temp))
return Error;
temp->data = item;
p = target->Next;
target->Next = temp;
temp->Next = p;
p->Previous = temp;
temp->Previous = target;
}
}
/*删除元素*/
void ListDelete(DualNode** list, int Position)
{
DualNode* temp, * target;
int i = 1;
if (Position == 1)
{
for (target = (*list); target->Next != (*list); target = target->Next);
temp = *list;
(*list) = (*list)->Next;
target->Next = (*list);
(*list)->Previous = target;
free(temp);
}
else
{ //删除其他节点
for (i = 1, target = *list; target->Next != *list && i != Position - 1; target = target->Next, i++);
if (target->Next == *list)
{
for (target = *list; target->Next->Next != *list; target = target->Next);
temp = target->Next;
target->Next = *list;
(*list)->Previous = target;
free(temp);
}
else
{
temp = target->Next;
target->Next = temp->Next;
temp->Next->Previous = target;
free(temp);
}
}
}
/*查找元素*/
int ListSearch(DualNode* list, int Elem)
{
DualNode* target;
int i = 1;
for (target = list; target->data != Elem && target->Next != list; i++)
{
target = target->Next;
}
if (target->Next == list && target->data != list->data)
{
return Error;
}
return i;
}
/*遍历链表 正序*/
void ListDisplayForward(DualNode* list)
{
DualNode* target;
target = list;
do {
printf("%c\t", target->data);
target = target->Next;
} while (target != list);
printf("\n\n");
}
/*遍历链表 逆序*/
void ListDisplayBackward(DualNode* list)
{
DualNode* target;
target = list->Previous;
do {
printf("%c\t", target->data);
target = target->Previous;
} while (target != list->Previous);
printf("\n\n");
}
/*字母表给定顺序输出*/
void ListDisplayAlphabet(DualNode* list, int Position)
{
DualNode* target;
target = list;
int i = 0;
if (Position > 0)
{
for(i = 1; i <= Position;i++)
target = target->Next;
}
if (Position < 0)
{
i = abs(Position);
for (i = 1; i <=abs(Position); i++)
{
target = target->Previous;
}
}
i = 1;
do {
printf("%c\t", target->data);
target = target->Next;
i++;
} while (i <= 26);
printf("\n\n");
}
/*入口*/
void main()
{
DualNode* list = NULL;
ListInit(&list, 26);
ListDisplayForward(list);
ListDisplayBackward(list);
/* ListInsert(&list, 5);
ListInsert(&list, 6);
ListDisplayForward(list);
ListDisplayBackward(list);
ListDelete(&list, 5);
ListDelete(&list, 6);
ListDisplayForward(list);
ListDisplayBackward(list);*/
ListDisplayAlphabet(list, 52);
ListDisplayAlphabet(list, 3);
ListDisplayAlphabet(list, -3);
}
栈（stack）又名堆栈
栈简介
定义
它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈示例代码
代码（C语言）
栈 Visual Studio 2019
/**
* 数据结构 C语言 栈
* @FileName FirstStack.c
* @author W.Lionel,Esaka
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>
/*相关宏变量*/
#define Stack_Init_Size 16
#define Stack_In_Create 8
/*定义栈结构*/
typedef char ElemType;
typedef struct {
ElemType* Base;
ElemType* Top;
int StackSize;
}SeqStack;
/*初始化*/
void InitStack(SeqStack* stack)
{
stack->Base = (ElemType*)malloc(Stack_Init_Size * sizeof(ElemType));
if (!stack->Base)
exit(0);
stack->Top = stack->Base;
stack->StackSize = Stack_Init_Size;
}
/*进栈*/
void Push(SeqStack* stack,ElemType value)
{
if ( (stack->Top - stack->Base) >= stack->StackSize)
{
stack->Base = (ElemType*)realloc(stack->Base, (stack->StackSize + Stack_In_Create) * sizeof(ElemType));
if (!stack->Base)
exit(0);
stack->Top = stack->Base + stack->StackSize;
stack->StackSize = stack->StackSize + Stack_In_Create;
}
*(stack->Top) = value;
stack->Top++;
}
/*出栈*/
void Pop(SeqStack* stack, ElemType *value)
{
if (stack->Top == stack->Base)
{
printf("栈空\n");
return 0;
}
*value = *--(stack->Top);
}
/*清空栈*/
void ClearStack(SeqStack* stack)
{
stack->Top = stack->Base;
}
/*销毁栈*/
void DestroyStack(SeqStack* stack)
{
int i, len;
len = stack->StackSize;
for (i = 0; i < len; i++)
{
free(stack->Base);
stack->Base++;
}
stack->Base = stack->Top = NULL;
stack->StackSize = 0;
}
/*返回长度*/
int LengthStack(SeqStack* stack)
{
return (stack->Top - stack->Base);
}
/*入口*/
void main()
{
SeqStack stack;
ElemType value;
int len, i, j, l, n, m;
int sum10 = 0;
int sum8[6] = { 0 };
int sum16[4] = { 0 };
InitStack(&stack);
printf("请输入二进制数：输入#结束\n");
scanf("%c", &value);
while (value != '#')
{
Push(&stack, value);
scanf("%c", &value);
}
getchar();
len = LengthStack(&stack);
for (i = 0, j = 0, l = 0, n = 0,m = 0; i < len; i++)
{
Pop(&stack, &value);
sum10 = sum10 + (value - 48) * pow(2, i);
sum8[n] = sum8[n] + (value - 48) * pow(2, j);
sum16[m] = sum16[m] + (value - 48) * pow(2, l);
j++;
l++;
if (j == 3)
{
n++;
j = 0;
}
if (l == 4)
{
m++;
l = 0;
}
}
printf("十进制：%d\n", sum10);
printf("二进制：");
for (i = n; i >= 0; i--)
{
printf("%d", sum8[i]);
}
printf("\n十六进制：");
for (i = m; i >= 0; i--)
{
printf("%d ", sum16[i]);
}
printf("\n");
}
链式栈 示例代码
代码（C语言）
链式栈 Visual Studio 2019
/**
* 数据结构 C语言 链式栈
* @FileName LinkedStack.c
* @author W.Lionel,Esaka
*/
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
typedef int status;
#define Correct 1
#define Error 0
typedef double ElemType;
typedef struct StackNode {
ElemType data;
struct StackNode* Next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack {
LinkStackPtr top;
int count;
}LinkStack;
status StackEmpty(LinkStack* s)
{
if (s->count == 0)
return Error;
else
return Correct;
}
status Push(LinkStack* stack, ElemType value)
{
LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
p->data = value;
p->Next = stack->top;
stack->top = p;
stack->count++;
return Correct;
}
status Pop(LinkStack* stack, ElemType* value)
{
LinkStackPtr p;
if (StackEmpty(stack))
return Error;
*value = stack->top->data;
p = stack->top;
stack->top = stack->top->Next;
free(p);
stack->count--;
return Correct;
}
经典算法——递归与回溯
汉诺塔
问题描述
汉诺塔（Tower of Hanoi），又称河内塔，是一个源于印度古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
解题思路
其实算法非常简单，当盘子的个数为n时，移动的次数应等于2^n – 1（有兴趣的可以自己证明试试看）。后来一位美国学者发现一种出人意料的简单方法，只要轮流进行两步操作就可以了。首先把三根柱子按顺序排成品字型，把所有的圆盘按从大到小的顺序放在柱子A上，根据圆盘的数量确定柱子的排放顺序：若n为偶数，按顺时针方向依次摆放 A B C；
若n为奇数，按顺时针方向依次摆放 A C B。
⑴按顺时针方向把圆盘1从现在的柱子移动到下一根柱子，即当n为偶数时，若圆盘1在柱子A，则把它移动到B；若圆盘1在柱子B，则把它移动到C；若圆盘1在柱子C，则把它移动到A。
⑵接着，把另外两根柱子上可以移动的圆盘移动到新的柱子上。即把非空柱子上的圆盘移动到空柱子上，当两根柱子都非空时，移动较小的圆盘。这一步没有明确规定移动哪个圆盘，你可能以为会有多种可能性，其实不然，可实施的行动是唯一的。
⑶反复进行⑴⑵操作，最后就能按规定完成汉诺塔的移动。
所以结果非常简单，就是按照移动规则向一个方向移动金片：
如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
示例代码（C语言）
汉诺塔 Visual Studio 6.0
#include <stdio.h>
#include <stdlib.h>
void move(int n, char x, char y, char z)
{
if (1 == n)
{
printf("%c-->%c\n", x, z);
}
else
{
move(n - 1, x, z, y);
printf("%c-->%c\n", x, z);
move(n - 1, y, x, z);
}
}
void main()
{
int n;
printf("请输入汉诺塔的层数：");
scanf("%d", &n);
printf("移动的步骤如下:\n");
move(n, 'X', 'Y', 'Z');
}
八皇后问题
问题描述
在8×8格的国际象棋上摆放8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。如果经过±90度、±180度旋转，和对角线对称变换的摆法看成一类，共有42类。计算机发明后，有多种计算机语言可以编程解决此问题。
解题思路
回溯算法优于穷举法。将列A的皇后放在第一行以后，列B的皇后放在第一行已经发生冲突。这时候不必继续放列C的皇后，而是调整列B的皇后到第二行，继续冲突放第三行，不冲突了才开始进入列C。如此可依次放下列A至E的皇后，如图2所示。将每个皇后往右边横向、斜向攻击的点位用叉标记，发现列F的皇后无处安身。这时回溯到列E的皇后，将其位置由第4行调整为第8行，进入列F，发现皇后依然无处安身，再次回溯列E。此时列E已经枚举完所有情况，回溯至列D，将其由第2行移至第7行，再进入列E继续。按此算法流程最终找到如图3所示的解，成功在棋盘里放下了8个“和平共处”的皇后。继续找完全部的解共92个。
回溯算法求解八皇后问题的原则是：有冲突解决冲突，没有冲突往前走，无路可走往回退，走到最后是答案。为了加快有无冲突的判断速度，可以给每行和两个方向的每条对角线是否有皇后占据建立标志数组。放下一个新皇后做标志，回溯时挪动一个旧皇后清除标志。
示例代码（C语言）
维吉尼亚密码表 Visual Studio 2019
#include <stdio.h>
int count = 0;
int notDanger(int row, int j, int(*chess)[8])
{
int i, k, flag1 = 0, flag2 = 0, flag3 = 0, flag4 = 0, flag5 = 0;
// 判断列方向
for (i = 0; i < 8; i++)
{
if (*(*(chess + i) + j) != 0)
{
flag1 = 1;
break;
}
}
// 判断左上方
for (i = row, k = j; i >= 0 && k >= 0; i--, k--)
{
if (*(*(chess + i) + k) != 0)
{
flag2 = 1;
break;
}
}
// 判断右下方
for (i = row, k = j; i < 8 && k < 8; i++, k++)
{
if (*(*(chess + i) + k) != 0)
{
flag3 = 1;
break;
}
}
// 判断右上方
for (i = row, k = j; i >= 0 && k < 8; i--, k++)
{
if (*(*(chess + i) + k) != 0)
{
flag4 = 1;
break;
}
}
// 判断左下方
for (i = row, k = j; i < 8 && k >= 0; i++, k--)
{
if (*(*(chess + i) + k) != 0)
{
flag5 = 1;
break;
}
}
if (flag1 || flag2 || flag3 || flag4 || flag5)
return 0;
else
return 1;
}
void EightQueen(int row, int n, int(*chess)[8])
{
int chess2[8][8], i, j;
for (i = 0; i < 8; i++)
for (j = 0; j < 8; j++)
chess2[i][j] = chess[i][j];
if (8 == row)
{
printf("第 %d 种\n", count + 1);
for (i = 0; i < 8; i++)
{
for (j = 0; j < 8; j++)
{
printf("%d ", *(*(chess2 + i) + j));
}
printf("\n");
}
printf("\n");
count++;
}
else
{
for (j = 0; j < n; j++)
{
if (notDanger(row, j, chess)) // 判断是否危险
{
for (i = 0; i < 8; i++)
{
*(*(chess2 + row) + i) = 0;
}
*(*(chess2 + row) + j) = 1;
EightQueen(row + 1, n, chess2);
}
}
}
}
int main()
{
int chess[8][8], i, j;
for (i = 0; i < 8; i++)
for (j = 0; j < 8; j++)
chess[i][j] = 0;
EightQueen(0, 8, chess);
printf("总共有 %d 种解决方法!\n\n", count);
return 0;
}
数据结构相关问题
维吉尼亚密码表
问题描述
吉尼亚密码是使用一系列凯撒密码组成密码字母表的加密算法，属于多表密码的一种简单形式。
该方法最早记录在吉奥万·巴蒂斯塔·贝拉索（ Giovan Battista Bellaso）于1553年所著的书《吉奥万·巴蒂斯塔·贝拉索先生的密码》中。然而，后来在19世纪时被误传为是法国外交官布莱斯·德·维吉尼亚（Blaise De Vigenère）所创造，因此现在被称为“维吉尼亚密码”。
维吉尼亚密码以其简单易用而著称，同时初学者通常难以破解，因而又被称为“不可破译的密码”。这也让很多人使用维吉尼亚密码来加密的目的就是为了将其破解。
加密与解密
在一个凯撒密码中，字母表中的每一字母都会作一定的偏移，例如偏移量为3时，A就转换为了D、B转换为了E……而维吉尼亚密码则是由一些偏移量不同的恺撒密码组成。
为了生成密码，需要使用表格法。用一个包括了26行字母表的表格，每一行都由前一行向左偏移一位得到。具体使用哪一行字母表进行编译是基于密钥进行的，在过程中会不断地变换。
例如，假设明文为：
ATTACKATDAWN
选择某一关键词并重复而得到密钥，如关键词为LEMON时，密钥为：
LEMONLEMONLE
对于明文的第一个字母A，对应密钥的第一个字母L，于是使用表格中L行字母表进行加密，得到密文第一个字母L。类似地，明文第二个字母为T，在表格中使用对应的E行进行加密，得到密文第二个字母X。以此类推，可以得到：
明文：ATTACKATDAWN密钥：LEMONLEMONLE密文：LXFOPVEFRNHR
解密的过程则与加密相反。例如：根据密钥第一个字母L所对应的L行字母表，发现密文第一个字母L位于A列，因而明文第一个字母为A。密钥第二个字母E对应E行字母表，而密文第二个字母X位于此行T列，因而明文第二个字母为T。以此类推便可得到明文。
示例代码（C语言）
维吉尼亚密码表 Visual Studio 2019
/**
* 数据结构 C语言 维吉尼亚密码表
* @FileName VigenèreCipher_Code.c
* @author W.Lionel.Esaka
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
typedef int Status;
#define CORRECT 1;
#define ERROR 0;
#define OVERFLOW -1;
typedef char ElemType;
typedef struct VC_Code {
ElemType Plaintext;
int Cipher;
struct VC_Code* Previous;
struct VC_Code* Next;
}VC_Code;
/*创建指定长度密码对应表*/
void ListInit(VC_Code** code, int Number)
{
VC_Code* temp;
VC_Code* target;
ElemType item;
int i;
srand(time(0));
for (i = 0; i < Number; i++)
{
//每输入一个字符需要换行
scanf("%c", &item);
fflush(stdin);
if (*code == NULL)
{
*code = (VC_Code*)malloc(sizeof(VC_Code));
if (!*code) exit(0);
(*code)->Cipher = rand () % 8 + 1;
(*code)->Plaintext = item;
(*code)->Next = *code;
(*code)->Previous = *code;
}
else
{
for (target = *code; target->Next != *code; target = target->Next);//寻找尾节点
temp = (VC_Code*)malloc(sizeof(VC_Code));
if (!temp)exit(0);
temp->Cipher = rand () % 8 + 1;
temp->Plaintext = item;
temp->Next = *code; //新节点指向头节点
(*code)->Previous = temp;
target->Next = temp; //尾节点指向新节点
temp->Previous = target;
}
}
}
void ListDisplay(VC_Code* code)
{
VC_Code* target;
ElemType Ciphertext;
printf("明文输出：\n");
target = code;
do {
printf("%c ", target->Plaintext);
target = target->Next;
} while (target != code);
printf("\n对应随机密码值：\n");
target = code;
do {
printf("%d ", target->Cipher);
target = target->Next;
} while (target != code);
printf("\n密文输出：\n");
target = code;
do {
if (target->Plaintext >= 'a' && target->Plaintext <= 'z')
{
Ciphertext = target->Plaintext + target->Cipher;
if ( Ciphertext > 122)
{
Ciphertext = (Ciphertext - 122) + 97;
}
}
if (target->Plaintext >= 'A' && target->Plaintext <= 'Z')
{
Ciphertext = target->Plaintext + target->Cipher;
if (Ciphertext > 90)
{
Ciphertext = (Ciphertext - 90) + 65;
}
}
if (target->Plaintext >= '0' && target->Plaintext <= '9')
{
Ciphertext = target->Plaintext + target->Cipher;
if (Ciphertext > 57)
{
Ciphertext = (Ciphertext - 57) + 48;
}
}
printf("%c ", Ciphertext);
target = target->Next;
} while (target != code);
}
/*入口*/
void main()
{
VC_Code* code = NULL;
printf("输入密码进行随机转换：\n");
ListInit(&code, 13);
ListDisplay(code);
}
魔术师发牌问题
问题描述
魔术师发牌问题的简介：一位魔术师掏出一叠扑克牌，魔术师取出其中13张黑桃，洗好后，把牌面朝下。
说：“我不看牌，只数一数就能知道每张牌是什么？”魔术师口中念一，将第一张牌翻过来看正好是A；
魔术师将黑桃A放到桌上，继续数手里的余牌，
第二次数1，2，将第一张牌放到这叠牌的下面，将第二张牌翻开，正好是黑桃2，也把它放在桌子上。
第三次数1，2，3，前面二张牌放到这叠牌的下面，取出第三张牌，正好是黑桃3，这样依次将13张牌翻出，全部都准确无误。
示例代码（C语言）
魔术师发牌 Visual Studio 2019
/**
* 数据结构 C语言 魔术师发牌
* @FileName MagicCard.c
* @author W.Lionel.Esaka
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define Status int;
#define CORRECT 1;
#define ERROR 0;
#define OVERFLOW -1;
#define CardNumber 13;
typedef int ElemType;
/*定义循环链表结点*/
typedef struct CLinkedList {
ElemType data;
struct CLinkedList* Next;
}Node;
/*初始化链表*/
void ListInit(Node** p, int number)
{
int item = 0;
Node* temp;
Node* target;
for (int i = 1; i <= number; i++)
{
if (*p == NULL)
{
*p = (Node*)malloc(sizeof(Node));
if (!*p)exit(0);
(*p)->data = item;
(*p)->Next = *p;
}
else
{
for (target = *p; target->Next != *p; target = target->Next);
temp = (Node*)malloc(sizeof(Node));
if (!temp)exit(0);
temp->data = item;
temp->Next = *p;
target->Next = temp;
}
}
}
/*设定牌堆顺序*/
void CardOrder(Node** card)
{
int PokerSize = 2;
Node* temp;
temp = (*card);
(*card)->data = 1;
while (1)
{
for (int j = 0; j < PokerSize; j++)
{
temp = temp->Next;
if (temp->data != 0)
{
temp->Next;
j--;
}
}
if (temp->data == 0)
{
temp->data = PokerSize;
PokerSize++;
if (PokerSize == 14)
break;
}
}
}
/*遍历链表*/
void CardDisplay(Node* list)
{
Node* target;
target = list;
do {
printf("黑桃%d ", target->data);
target = target->Next;
} while (target != list);
printf("\n");
}
/*销毁链表*/
void DestoryList(Node** list)
{
Node* ptr = (*list);
Node* buff[13];
int i = 0;
while (i < 13)
{
buff[i++] = ptr;
ptr = ptr->Next;
}
for (i = 0; i < 13; i++)
{
free(buff[i]);
}
*list = 0;
printf("表已销毁\n");
}
/*入口*/
int main(void)
{
Node* list = NULL;
ListInit(&list, 13);
CardOrder(&list);
CardDisplay(list);
DestoryList(&list);
}
约瑟夫问题
问题描述
据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
解题思路
约瑟夫问题是个有名的问题：N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。
(1) 每个人只有死和活着，因此可以用布尔标记每个人的状态，可用true表示死，false表示活。
(2) 开始时每个人都是活的，所以数组初值全部赋为false。
(3) 模拟杀人过程，直到所有人都被杀死为止。
示例代码（C语言）
约瑟夫环 Visual Studio 2019
/**
* 数据结构 C语言 顺序表_约瑟夫问题
* @FileName Seq_Josephus_Problem.c
* @author W.Lionel.Esaka
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
//预处理
#define MAXSIZE 200 //数据数组大小 MAXSIZE 方便更改
#define bool int //C语言中没有bool值，用int替换
#define true 1 //用true替换1，用false替换0
#define false 0 //也可以用Correct/Error
typedef int ElemType; //ElemType/Status 元素类型/状态
typedef int Status; //用来指代特定的数据类型
/*定义线性表结构体*/
typedef struct
{
ElemType Data[MAXSIZE]; //Data数组，用来存储线性表数据的“容器”
int Count; //数据个数计数器
} Sequential_linear_table; //Sequential_linear_table（顺序线性表）
//创建线性表(线性表指针，数据数组，数组长度)
void CreateList(Sequential_linear_table* list,int n)
{
int i;
for (i = 0; i < n; i++) //将所给数据数组数据赋值给线性表中的数组
list->Data[i] = i + 1;
list->Count = n; //线性表长度/计数器置为n
}
//判定是否为空表(线性表指针)
bool ListEmpty(Sequential_linear_table* list)
{
return (list->Count == 0); //返回此表达式的值，假为true，真为ture
}
//返回线性表长度值(线性表指针)
int ListLength(Sequential_linear_table* list)
{
return(list->Count); //返回线性表计数器中的值
}
//输出线性表(线性表指针)
void ListDisplay(Sequential_linear_table* list)
{
int i;
if (ListEmpty(list))
{
printf("空表\n");
return; //for循环输出线性表数据数组中的数据
}
for (i = 0; i < list->Count; i++)
{
printf("%4d\t", list->Data[i]);
}
printf("\n");
}
//求某个数据元素值(线性表指针，所查找的数据位置，将所的数据返回给此变量)
bool GetElem(Sequential_linear_table* list, int i, ElemType* e)
{
if (i<1 || i>list->Count) //判断所给位置是否在线性表范围内
return false;
*e = list->Data[i - 1]; //将查找位置的数据返回给所给变量
return true;
}
//按元素值查找元素位置(线性表指针，所查找的数据)
bool LocateElem(Sequential_linear_table* list, ElemType e)
{
int i = 0;
while (i < list->Count&& list->Data[i] != e)
i++; //将所给数据与线性表数组中的数据一一对比查找
if (i >= list->Count) //超出范围返回为false
return false;
else
return i + 1;
}
//插入数据元素(线性表指针，数据插入位置，将要插入的数据)
bool InsertList(Sequential_linear_table* list, int i, ElemType e)
{
int j;
if (i<1 || i>list->Count + 1)
return false; //不在范围内时返回false
i--; //将顺序表逻辑序号转化为数据数组序号
for (j = list->Count; j > i; j--) //将Data数组元素整体后移一位
list->Data[j] = list->Data[j - 1];
list->Data[i] = e; //插入元素e
list->Count++; //顺序表计数器加1
return true; //成功插入返回true
}
//删除数据元素(线性表指针，所要删除数据位置，被删除的数据值)
bool DeleteList(Sequential_linear_table* list, int i, ElemType e)
{
int j;
if (i<1 || i>list->Count) //不在范围内时返回false
return false;
i--; //将顺序表逻辑序号转化为物理序号
e = list->Data[i]; //将被删除数据值赋值给e
for (j = i; j < list->Count - 1; j++) //将Data数组元素整体前移一位
list->Data[j] = list->Data[j + 1];
list->Count--; //顺序表计数器减1
return true; //成功删除返回true
}
//入口函数
int main()
{
//游戏初始数值定义
printf("\n |约瑟夫问题测试| \n=-=-=-=-=-=-=-=-=-=-=\n");
ElemType value = 0;
int n,m,i = 1,Number_Off = 1;
printf("输入参与游戏的总人数n：");
scanf("%d", &n);
printf("输入报数上限m：");
scanf("%d", &m);
if (n > 200)
{
printf("超过游戏人数上限,程序退出\n");
exit(0);
}
//线性表初始化
Sequential_linear_table seqlist;
Sequential_linear_table* list = &seqlist;
//创建本局游戏
CreateList(list, n);
printf("\n本局游戏创建成功\n本局游戏人数为%d\n报名上限为%d\n", ListLength(list),m);
//游戏开始
while ( list->Count > 1 )
{
if (Number_Off == m)
{
DeleteList(list,i,value);
Number_Off = 1;
}
else
{
i++;
Number_Off++;
}
if ( i > list->Count )
{
i = 1;
}
}
printf("\n最后获胜的人的编号为");
ListDisplay(list);
return 0;
}
后缀表达式
问题描述
一个表达式E的后缀形式可以如下定义：
(1) 如果E是一个变量或常量，则E的后缀式是E本身。
(2) 如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’ op，这里E1’和E2’分别为E1和E2的后缀式。
(3) 如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。
如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+
(a+b)c-(a+b)/e的后缀表达式为：
(a+b)c-(a+b)/e
→((a+b)c)((a+b)/e)-
→((a+b)c)((a+b)e/)-
→(ab+c)(ab+e/)-
→ab+cab+e/-
作用
实现逆波兰式的算法，难度并不大，但为什么要将看似简单的中缀表达式转换为复杂的逆波兰式？原因就在于这个简单是相对人类的思维结构来说的，对计算机而言中序表达式是非常复杂的结构。相对的，逆波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。
示例代码（C语言）
栈__后缀表达式 Visual Studio 2019
/**
* 数据结构 C语言 栈__后缀表达式
* @FileName Against_Poland.c
* @author W.Lionel,Esaka
* 样例输入
* (4+4)*2-(4+4)/2#
* 样例输出
* 4 4 + 2 * 4 4 + 2 /-
* 最终的计算结果为12
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <math.h>
/*相关宏变量*/
#define MaxBuffer 10
#define Stack_Init_Size 20
#define Stack_In_Create 10
/*定义栈结构*/
typedef char ElemType;
typedef struct {
ElemType* Base;
ElemType* Top;
int StackSize;
}SeqStack;
/*初始化*/
void InitStack(SeqStack* stack)
{
stack->Base = (ElemType*)malloc(Stack_Init_Size * sizeof(ElemType));
if (!stack->Base)
exit(0);
stack->Top = stack->Base;
stack->StackSize = Stack_Init_Size;
}
/*进栈*/
void Push(SeqStack* stack, ElemType value)
{
if ((stack->Top - stack->Base) >= stack->StackSize)
{
stack->Base = (ElemType*)realloc(stack->Base, (stack->StackSize + Stack_In_Create) * sizeof(ElemType));
if (!stack->Base)
exit(0);
stack->Top = stack->Base + stack->StackSize;
stack->StackSize = stack->StackSize + Stack_In_Create;
}
*(stack->Top) = value;
stack->Top++;
}
/*出栈*/
void Pop(SeqStack* stack, ElemType* value)
{
if (stack->Top == stack->Base)
{
printf("栈空\n");
return 0;
}
*value = *--(stack->Top);
}
/*清空栈*/
void ClearStack(SeqStack* stack)
{
stack->Top = stack->Base;
}
/*销毁栈*/
void DestroyStack(SeqStack* stack)
{
int i, len;
len = stack->StackSize;
for (i = 0; i < len; i++)
{
free(stack->Base);
stack->Base++;
}
stack->Base = stack->Top = NULL;
stack->StackSize = 0;
}
/*返回长度*/
int LengthStack(SeqStack stack)
{
return(stack.Top - stack.Base);
}
/*入口*/
void main()
{
SeqStack Stack;
SeqStack* stack = &Stack;
ElemType d,e,value;
ElemType array[20] = { 0 };
int i = 0,n;
char c;
InitStack(stack);
scanf("%c", &c);
while (c != '#')
{
if (c >= '0' && c <= '9')
{
printf("%c ", c);
array[i] = c;
i++;
}
else if (c == ')')
{
Pop(stack, &value);
while ('(' != value)
{
printf("%c ", value);
array[i] = value;
i++;
Pop(stack, &value);
}
}
else if (c == '+' || c == '-')
{
if ( stack->Top == stack->Base )
{
Push(stack, c);
}
else
{
do
{
Pop(stack, &value);
if ( '(' == value)
{
Push(stack, value);
}
else
{
printf("%c ", value);
array[i] = value;
i++;
}
} while ( LengthStack(Stack) && '(' != value);
Push(stack, c);
}
}
else if ('*' == c || '/' == c || '(' == c)
{
Push(stack, c);
}
else
{
printf("出错\n");
}
scanf("%c", &c);
}
while ( LengthStack(Stack) )
{
Pop(stack, &value);
printf("%c", value);
array[i] = value;
i++;
}
printf("\n");
n = i;
i = 0;
while( i < n)
{
if (array[i] >= '1' && array[i] <= '9')
{
value = (int)array[i] - 48;
Push(stack, value);
}
if (array[i] == '+' || array[i] == '-' || array[i] == '/' || array[i] == '*')
{
switch (array[i])
{
case '+':
Pop(stack, &e);
Pop(stack, &d);
Push(stack, d + e);
break;
case '-':
Pop(stack, &e);
Pop(stack, &d);
Push(stack, d - e);
break;
case '*':
Pop(stack, &e);
Pop(stack, &d);
Push(stack, d * e);
break;
case '/':
Pop(stack, &e);
Pop(stack, &d);
Push(stack, d/e);
break;
}
}
i++;
}
Pop(stack, &value);
printf("最终的计算结果为%d\n", value);
}