数据结构是计算机中对数据的一种存储和组织方式,同时也泛指相互之间存在一种或多种特定关系的数据的集合。
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。
业界许多专家都对其有相关定义,具体不多做赘述……
笔者理解的数据结构:一个数据结构是由数据元素依据某种逻辑联系组织起来的,对数据元素间逻辑关系的描述称为数据的逻辑结构。由于数据必须在计算机内存储,数据的存储结构是其在计算机内的表示,也就是数据结构的实现形式。
数据的逻辑结构(Logical Structure):也就是数据元素(Data Element)之间的逻辑关系。数据的逻辑结构是从逻辑关系上描述数据的,与数据在计算机中如何存储无关,也就是独立于计算机的抽象概念。
数据的存储结构(Storage Structure):也就是数据元素(Data Element)及其逻辑关系在计算机存储器中的表示形式。
数据的运算:也就是能够对数据施加操作。数据的运算基础在于数据的逻辑结构上,每种逻辑结构都可以归纳一个运算的集合。
具体案例:
每一行可以看作是一个数据元素(Data Element),也可以称为记录或者结点。这个数据元素由学号、姓名、数学成绩、物理成绩、英语成绩和语文成绩等数据项构成。
这个表中的逻辑关系:
对表中任意一个结点,直接前趋(Immediate Predecessor)结点最多只有一个。直接前趋结点也就是与它相邻且在它前面的结点。
表中只有第一个结点没有直接前趋,也就是开始结点。
例如,表中“张三”所在的结点就是开始结点,“马七”所在的结点就是终端结点。表中间的“陈九”所在结点的直接前趋结点是“李四”所在的结点,表中间的“陈九”所在结点的直接后继结点是“王一”所在的结点。这些结点关系就构成了某班级学生成绩表的逻辑结构。
再来看一下数据的存储结构:
我们知道数据的存储结构是数据元素及其逻辑关系在计算机存储器中的表示形式。
这方面的内容将在后面进行详细讲述。
再来看一下数据的运算:
拿到这个表之后,会进行哪些操作呢?一般来说,主要包括如下操作:
查找某个学生的成绩。
对于新入学的学生,在表中增加一个结点来存放。
其实,数据的逻辑结构、存储结构和运算是一个整体,单独地去理解这三者中的任何一个都是不全面的,这主要表现在如下两点:
- (1)同一个逻辑结构可以有不同的存储结构。
- (2)同一种逻辑结构也可以有不同的数据运算集合。
数据结构的存储方式:顺序存储方式、链式存储方式、索引存储方式、散列存储方式。
顺序存储方式:就是在一块连续的存储区域一个接着一个地存放数据。
一般采用数组或结构数组来描述。
链接存储方式:不要求逻辑上相邻的结点在物理位置上相邻,结点间的逻辑关系由附加的指针字段表示。一个结点的指针字段往往指向下一个结点的存放位置。
索引存储方式:采用附加的索引表的方式来存储结点信息。
索引存储方式中索引项的一般形式如下所示:
(
关
键
字
.
地
址
)
(关键字.地址)
(关键字.地址)
其中,关键字是能够唯一标识一个结点的数据项。
索引存储方式还可以细分为两类:稠密索引、稀疏索引。
散列存储方式:根据结点的关键字直接计算出该结点的存储地址的一种存储方式。
在实际应用中,需要根据具体数据结构来确定采用哪种数据结构。
数据类型:就是一个值的集合以及在这些值上定义的一系列操作的总称。
抽象数据类型(ADT): 数据的组织及其相关的操作,可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。
一个抽象数据类型可以定义为如下形式:
ADT 抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
} ADT 抽象数据类型名
抽象数据类型一般具有两个特征:数据抽象、数据封装。
从逻辑上来看,线性表就是由n(n≥0)个数据元素a1,a2,…,an组成的有限序列。
在计算机中线性表可以采用两种方式来保存,一种是顺序存储结构,另一种是链式存储结构。
顺序存储结构的线性表称为顺序表,链式存储的线性表称为链表。
由于顺序表是依次存放的,只要知道了该顺序表的首地址以及每个数据元素所占用的存储长度,很容易计算出任何一个数据元素(也就是数据结点)的位置。
假设顺序表中所有结点的类型相同,则每个结点所占用存储空间的大小亦相同,每个结点占用c个存储单元。其中第1个单元的存储地址则是该结点的存储地址,并设顺序表中开始结点a1的存储地址(简称为基地址)是LOC(a1),那么结点ai的存储地址LOC(ai)可通过下式计算得到。
L
O
C
(
a
i
)
=
L
O
C
(
a
1
)
+
(
i
?
1
)
?
c
(
1
≤
i
≤
n
)
LOC(a_i)=LOC(a_1)+(i-1)*c (1≤i≤n)
LOC(ai?)=LOC(a1?)+(i?1)?c (1≤i≤n)
#define MAXLEN 100 // 定义顺序表的最大长度
typedef struct
{
char kay[10]; // 结点的关键字
char name[20];
int age;
}DATA; // 定义结点类型
typedef struct // 定义顺序表结构
{
DATA ListData[MAXLEN + 1]; // 保存顺序表的结构数组
int ListLen; // 顺序表已存在的结点数量
}SLType;
// 在这里可以认为该顺序表是一个班级学生的记录。
// 其中,key为学号,name为学生的名称,age为年龄。
void SLInit(SLType *SL) // 初始化顺序表
{
SL->ListLen = 0; // 初始化为空表
}
int SLLength(SLType *SL)
{
return (SL->ListLen); // 返回顺序表的元素数量
}
插入结点
// 本算法将实现将元素data插入到顺序表SL中的第i个位置
int SLInsert(SLType *SL, int i, DATA data)
{
int j;
if (SL->ListLen >= MAXLEN) // 当前存储空间已满,不能插入
{
printf("顺序表已满,不能插入结点! \n");
return 0; // 返回0表示不能插入
}
if (i<1 || i > SL->ListLen - 1) // 判断i的范围是否有效
{
printf("插入元素序号错误,不能插入元素! \n");
return 0; // 返回0,表示插入失败
}
for (j = SL->ListLen; j >= i; j--) // 将顺序表中的数据向后移动
{
SL->ListData[i + 1] = SL->ListData[i];
}
SL->ListData[i] = data; // 插入结点
SL->ListLen++; // 顺序表长度加1
return i; // 插入成功,返回i
}
int SLAdd(SLType *SL, DATA data) // 增加元素到顺序表尾部
{
if (SL->ListLen >= MAXLEN) // 顺序表已满
{
printf("顺序表已满,不能再添加结点了! \n");
return 0;
}
SL->ListData[++SL->ListLen] = data;
return 1;
}
// 本算法将实现删除顺序表SL中的第i个位置的元素
int SLDelete(SLType *SL, int i)
{
int j;
if (i<1 || i > SL->ListLen) // 判断i的范围是否有效
{
printf("删除结点序号错误,不能删除结点! \n");
return 0; // 返回0,表示删除失败
}
for (j = i; j < SL->ListLen; j--) // 将顺序表中的数据向前移动
{
SL->ListData[i] = SL->ListData[i+1];
}
SL->ListLen--; // 顺序表长度减1
return 1; // 删除成功,返回1
}
DATA *SLFindByNum(SLType *SL, int i) // 根据序号返回数据元素
{
if (i<1 || i > SL->ListLen + 1) // 元素序号不正确
{
printf("结点序号错误,不能返回结点! \n");
return NULL; // 不成功,返回0
}
return &(SL->ListData[i]);
}
DATA *SLFindByCont(SLType *SL, char *key) // 根据关键字查询结点
{
int i;
for (i = 1; i <= SL->ListLen; i++)
{
if (strcmp(SL->ListData[i].key,key)==0) // 如果找到所需结点
{
return i; // 返回结点序号
}
}
return 0; // 搜索整个顺序表后未找到,返回0
}
int SLAll(SLType *SL) // 显示顺序表中所有的结点
{
int i;
for (i = 1; i <= SL->ListLen; i++)
{
printf("(%s, %s, %d) \n", SL->ListData[i].key, SL->ListData[i].name, SL->ListData[i].age);
}
return 0;
}
#include <stdio.h>
#include <string.h>
#define MAXLEN 100 // 定义顺序表的最大长度
typedef struct
{
char key[10]; // 结点的关键字
char name[20];
int age;
}DATA; // 定义结点类型
typedef struct // 定义顺序表结构
{
DATA ListData[MAXLEN + 1]; // 保存顺序表的结构数组
int ListLen; // 顺序表已存在的结点数量
}SLType;
void SLInit(SLType *SL) // 初始化顺序表
{
SL->ListLen = 0; // 初始化为空表
}
int SLLength(SLType *SL)
{
return (SL->ListLen); // 返回顺序表的元素数量
}
// 本算法将实现将元素data插入到顺序表SL中的第i个位置
int SLInsert(SLType *SL, int i, DATA data)
{
int j;
if (SL->ListLen >= MAXLEN) // 当前存储空间已满,不能插入
{
printf("顺序表已满,不能插入结点! \n");
return 0; // 返回0表示不能插入
}
if (i<1 || i > SL->ListLen - 1) // 判断i的范围是否有效
{
printf("插入元素序号错误,不能插入元素! \n");
return 0; // 返回0,表示插入失败
}
for (j = SL->ListLen; j >= i; j--) // 将顺序表中的数据向后移动
{
SL->ListData[i + 1] = SL->ListData[i];
}
SL->ListData[i] = data; // 插入结点
SL->ListLen++; // 顺序表长度加1
return i; // 插入成功,返回i
}
int SLAdd(SLType *SL, DATA data) // 增加元素到顺序表尾部
{
if (SL->ListLen >= MAXLEN) // 顺序表已满
{
printf("顺序表已满,不能再添加结点了! \n");
return 0;
}
SL->ListData[++SL->ListLen] = data;
return 1;
}
// 本算法将实现删除顺序表SL中的第i个位置的元素
int SLDelete(SLType *SL, int i)
{
int j;
if (i<1 || i > SL->ListLen) // 判断i的范围是否有效
{
printf("删除结点序号错误,不能删除结点! \n");
return 0; // 返回0,表示删除失败
}
for (j = i; j < SL->ListLen; j--) // 将顺序表中的数据向前移动
{
SL->ListData[i] = SL->ListData[i+1];
}
SL->ListLen--; // 顺序表长度减1
return 1; // 删除成功,返回1
}
DATA *SLFindByNum(SLType *SL, int i) // 根据序号返回数据元素
{
if (i<1 || i > SL->ListLen + 1) // 元素序号不正确
{
printf("结点序号错误,不能返回结点! \n");
return NULL; // 不成功,返回0
}
return &(SL->ListData[i]);
}
DATA *SLFindByCont(SLType *SL, char *key) // 根据关键字查询结点
{
int i;
for (i = 1; i <= SL->ListLen; i++)
{
if (strcmp(SL->ListData[i].key,key)==0) // 如果找到所需结点
{
return i; // 返回结点序号
}
}
return 0; // 搜索整个顺序表后未找到,返回0
}
int SLAll(SLType *SL) // 显示顺序表中所有的结点
{
int i;
for (i = 1; i <= SL->ListLen; i++)
{
printf("(%s, %s, %d) \n", SL->ListData[i].key, SL->ListData[i].name, SL->ListData[i].age);
}
return 0;
}
int main()
{
int i;
SLType SL; // 定义顺序表
DATA data; // 定义节点保存数据类型
DATA *pdata; // 定义结点保存指针
char key[10]; // 保存关键字
printf("顺序表操作演示: \n");
SLInit(&SL); // 初始化顺序表
printf("初始化顺序表完成! \n");
do { //循环添加数据结点
printf("输入要添加的结点(学号 姓名 年龄): \n");
fflush(stdin); // 清空输入缓冲区
scanf("%s %s %d", &data.key, &data.name, &data.age);
if (data.age) // 如果年龄不为0
{
if (!SLAdd(&SL, data)) // 若添加结点失败
{
break; // 退出死循环
}
}
else { // 若年龄为0
break; //退出死循环
}
} while (1);
printf("\n顺序表中的结点顺序为:\n");
SLAll(&SL); // 显示所有结点数据
fflush(stdin); // 清空输入缓冲区
printf("\n要取出的结点的序号:");
scanf("%d", &i); // 输入结点序号
pdata = SLFindByNum(&SL, i); // 按序号查找结点
if (pdata) // 若返回的结点指针不为空
{
printf("第%d个结点为:(%s ,%s ,%d) \n", i, pdata->key, pdata->name, pdata->age);
}
fflush(stdin); // 清空输入缓冲区
printf("\n要查找的结点的关键字:");
scanf("%s", key); // 输入关键字
i = SLFindByCont(&SL, key); // 按关键字查找结点,返回结点序号
pdata = SLFindByNum(&SL, i); // 按序号查找结点
if (pdata) // 若返回的结点指针不为空
{
printf("第%d个结点为:(%s ,%s ,%d) \n", i, pdata->key, pdata->name, pdata->age);
}
getchar();
return 0;
}
顺序表结构的存储方式非常容易理解,操作也十分方便。但是顺序表结构有如下一些缺点:
- 在插入或者删除结点时,往往需要移动大量的数据,影响运行效率。
- 如果表比较大,有时难以分配足够的连续存储空间,往往导致内存分配失败,而无法存储。
为了克服顺序表结构的以上缺点,可以采用链表结构。
注意:用户可以malloc函数动态分配结点的存储空间,当删除某个结点时,应该使用free函数释放其占用的内存空间。
链表结构的缺点:
单链表:向上面的链式结构一样,每个结点中只包含一个指针。
双向链表:若每个结点包含两个指针,一个指向下一个结点,另一个指向上一个结点,这就是双向链表。
单循环链表:在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点即可构成单循环链表。
多重链的循环链表:如果将表中结点链在多个环上,将构成多重链的循环链表。
typedef struct
{
char key[10]; // 关键字
char name[20];
int age;
}Data;
typedef struct Node // 定义链表结构
{
Data nodeData; // 数据域nodeData
struct Node *nextNode; // 指针域nextNode
}CLType;
尾插法
CLType *CLAddEnd(CLType * head, Data nodeData) // 尾插法
{
CLType *node, *htemp;
if (!(node = (CLType *)malloc(sizeof(CLType))))
{
printf("申请内存失败!\n");
return NULL; // 分配内存失败
}
else {
node->nodeData = nodeData; // 保存数据
node->nextNode = NULL; // 设置结点指针为空,即为表尾
if (head == NULL) // 头指针
{
head = node;
return head;
}
htemp = head;
while (htemp->nextNode != NULL) // 查找链表的末尾
{
htemp = htemp->nextNode;
}
htemp->nextNode = node;
return head;
}
}
头插法
CLType *CLAddFirst(CLType * head, Data nodeData) // 头插法
{
CLType *node;
if (!(node = (CLType *)malloc(sizeof(CLType))))
{
printf("申请内存失败!\n");
return NULL; // 分配内存失败
}
else {
node->nodeData = nodeData; // 保存数据
node->nextNode = head; // 指向头指针所指向的结点
head=node; // 头指针指向新增结点
return head;
}
}
查找结点
CLType *CLFindByNum(CLType *head, int i) // 根据序号返回数据元素
{
int j = 1; // 计数,初始为1
CLType *htemp=head->nextNode; // 头结点指针赋值给htemp
if (i == 0)
return head; // 若i为0,返回头结点
if (i < 1)
return NULL; // 若i无效,返回NULL
while (htemp && j > i) { // 从第一个结点开始查找,查找第i个结点
htemp = htemp->nextNode;
j++;
}
return htemp; // 返回第i个结点的指针
}
②按关键字查找结点。
CLType *CLFindNode(CLType *head, char *key) // 查找结点
{
CLType *htemp;
htemp = head; // 保存链表头指针
while (htemp) // 若结点有效,进行查找
{
if (strcmp(htemp->nodeData.key, key) == 0) // 判断结点关键字与传入关键字是否相同
{
return htemp; //返回该结点指针
}
htemp = htemp->nextNode; // 处理下一结点
}
return NULL; // 返回空指针
}
插入结点
在链表中间插入结点。
插入节点操作步骤:
CLType *CLInsertNode(CLType *head, char *findkey, Data nodeData) // 插入结点
{
CLType *node, *nodetemp;
if (!(node = (CLType *)malloc(sizeof(CLType)))) // 分配保存结点的内容
{
printf("申请内存失败! \n");
return 0; // 分配内存失败
}
node->nodeData = nodeData;
nodetemp = CLFindNode(head, findkey); // 保存结点中的数据
if (nodetemp) // 若找到要插入的结点
{
node->nextNode = nodetemp->nextNode; // 新插入结点指向关键字结点的下一结点
nodetemp->nextNode = node; // 设置关键结点指向新插入结点
}
else {
printf("未找到正确的插入位置! \n");
free(node); // 释放内存
}
return head; // 返回头指针
}
删除结点
int CLDeleteNode(CLType *head, char * key)
{
CLType *node, *htemp; // node保存删除结点的前一结点
htemp = head;
node = head;
while (htemp)
{
if (strcmp(htemp->nodeData.key, key) == 0) // 找到关键字,执行删除操作
{
node->nextNode = htemp->nextNode; // 使前一结点指向当前结点的下一结点
free(htemp); // 释放内存
return 1;
}
else {
node=htemp; // 指向当前结点
htemp = htemp->nextNode; // 指向下一结点
}
}
return 0; // 未删除
}
int CLLength(CLType *head) // 计算链表长度
{
CLType *htemp;
int Len = 0;
htemp = head;
while (htemp) // 遍历链表
{
Len++; // 累加结点数量
htemp = htemp->nextNode; // 处理下一结点
}
return Len; // 返回结点数量
}
void CLAllNode(CLType *head) // 遍历链表
{
CLType *htemp;
Data nodeData;
htemp = head;
printf("当前链表共有%d个结点。链表所有数据如下: \n", CLLength(head));
while (htemp) // 循环处理链表的每个节点
{
nodeData = htemp->nodeData; // 获取结点数据
printf("结点(%s, %s, %d) \n", nodeData.key, nodeData.name, nodeData.age);
htemp = htemp->nextNode; // 处理下一结点
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct
{
char key[10]; // 关键字
char name[20];
int age;
}Data;
typedef struct Node // 定义链表结构
{
Data nodeData; // 数据域nodeData
struct Node *nextNode; // 指针域nextNode
}CLType;
CLType *CLAddEnd(CLType * head, Data nodeData) // 尾插法
{
CLType *node, *htemp;
if (!(node = (CLType *)malloc(sizeof(CLType))))
{
printf("申请内存失败!\n");
return NULL; // 分配内存失败
}
else {
node->nodeData = nodeData; // 保存数据
node->nextNode = NULL; // 设置结点指针为空,即为表尾
if (head == NULL) // 头指针
{
head = node;
return head;
}
htemp = head;
while (htemp->nextNode != NULL) // 查找链表的末尾
{
htemp = htemp->nextNode;
}
htemp->nextNode = node;
return head;
}
}
CLType *CLAddFirst(CLType * head, Data nodeData) // 头插法
{
CLType *node;
if (!(node = (CLType *)malloc(sizeof(CLType))))
{
printf("申请内存失败!\n");
return NULL; // 分配内存失败
}
else {
node->nodeData = nodeData; // 保存数据
node->nextNode = head; // 指向头指针所指向的结点
head=node; // 头指针指向新增结点
return head;
}
}
CLType *CLFindNode(CLType *head, char *key) // 查找结点
{
CLType *htemp;
htemp = head; // 保存链表头指针
while (htemp) // 若结点有效,进行查找
{
if (strcmp(htemp->nodeData.key, key) == 0) // 判断结点关键字与传入关键字是否相同
{
return htemp; //返回该结点指针
}
htemp = htemp->nextNode; // 处理下一结点
}
return NULL; // 返回空指针
}
CLType *CLInsertNode(CLType *head, char *findkey, Data nodeData) // 插入结点
{
CLType *node, *nodetemp;
if (!(node = (CLType *)malloc(sizeof(CLType)))) // 分配保存结点的内容
{
printf("申请内存失败! \n");
return 0; // 分配内存失败
}
node->nodeData = nodeData;
nodetemp = CLFindNode(head, findkey); // 保存结点中的数据
if (nodetemp) // 若找到要插入的结点
{
node->nextNode = nodetemp->nextNode; // 新插入结点指向关键字结点的下一结点
nodetemp->nextNode = node; // 设置关键结点指向新插入结点
}
else {
printf("未找到正确的插入位置! \n");
free(node); // 释放内存
}
return head; // 返回头指针
}
int CLDeleteNode(CLType *head, char * key)
{
CLType *node, *htemp; // node保存删除结点的前一结点
htemp = head;
node = head;
while (htemp)
{
if (strcmp(htemp->nodeData.key, key) == 0) // 找到关键字,执行删除操作
{
node->nextNode = htemp->nextNode; // 使前一结点指向当前结点的下一结点
free(htemp); // 释放内存
return 1;
}
else {
node=htemp; // 指向当前结点
htemp = htemp->nextNode; // 指向下一结点
}
}
return 0; // 未删除
}
int CLLength(CLType *head) // 计算链表长度
{
CLType *htemp;
int Len = 0;
htemp = head;
while (htemp) // 遍历链表
{
Len++; // 累加结点数量
htemp = htemp->nextNode; // 处理下一结点
}
return Len; // 返回结点数量
}
void CLAllNode(CLType *head) // 遍历链表
{
CLType *htemp;
Data nodeData;
htemp = head;
printf("当前链表共有%d个结点。链表所有数据如下: \n", CLLength(head));
while (htemp) // 循环处理链表的每个节点
{
nodeData = htemp->nodeData; // 获取结点数据
printf("结点(%s, %s, %d) \n", nodeData.key, nodeData.name, nodeData.age);
htemp = htemp->nextNode; // 处理下一结点
}
}
int main()
{
int i;
CLType *node, *head=NULL;
Data nodeData;
char key[10], findkey[10];
printf("链表测试,先输入链表中的数据,格式为:关键字 姓名 年龄 \n");
do {
fflush(stdin); // 清空输入缓冲区
scanf("%s", nodeData.key);
if (strcmp(nodeData.key, "0") == 0)
{
break; // 若输入为0,则退出
}
else {
scanf("%s %d", nodeData.name, &nodeData.age);
head = CLAddEnd(head, nodeData); // 尾插法
}
} while (1);
CLAllNode(head); // 显示所有结点
printf("\n演示插入结点,输入插入位置的关键字:");
scanf("%s", findkey); // 输入插入位置的关键字
printf("输入插入结点的数据(关键字 姓名 年龄):");
scanf("%s %s %d", nodeData.key, nodeData.name, &nodeData.age); // 输入插入节点的数据
head = CLInsertNode(head, findkey, nodeData); // 调用插入函数
CLAllNode(head); // 显示所有结点
printf("\n演示删除结点,输入要删除的关键字:");
fflush(stdin); // 清空输入缓冲区
scanf("%s", key);
CLDeleteNode(head, key); // 调用删除结点函数
CLAllNode(head); // 显示所有结点
printf("\n输入要查找的结点的关键字:");
fflush(stdin); // 清空输入缓冲区
scanf("%s", key); // 输入关键字
node = CLFindNode(head, key); // 按关键字查找结点,返回结点指针
if (node) // 若返回的结点指针有效
{
nodeData = node->nodeData; // 获取结点数据
printf("关键字%s对应的结点为:(%s ,%s ,%d) \n", key, nodeData.key, nodeData.name,nodeData.age);
}
else { // 若结点指针无效
printf("在链表中未找到关键字为%s的结点! \n", key);
}
return 0;
}
2001 admin 12
2002 subei 14
2003 wewef 13
2004 ssddf 15
2005 whhkk 16
栈(Stack):只允许在一端进行插入和删除操作的线性表。
栈结构在日常生活中有很多例子。例如,当仓库中堆放货物时,先来的货物放在里面,后来的货物放在外面;而要取出货物时,总是先取外面的,最后才能取到里面放的货物。也就是说,后放入货物先取出。
#define MAXLEN 50
typedef struct
{
char name[10];
int age;
}DATA;
typedef struct stack
{
DATA data[SIZE + 1]; // 数据元素
int top; // 栈顶
}StackType;
StackType *STInit()
{
StackType *p;
if (p = (StackType *)malloc(sizeof(StackType))) // 申请栈内存
{
p->top = 0; // 设置栈顶为0
return p; // 返回指向栈的指针
}
return NULL;
}
int STIsEmpty(StackType *s) // 判断栈是否为空
{
int t;
t = (s->top == 0);
return t;
}
int STIsFull(StackType *s) // 判断栈是否为满
{
int t;
t = (s->top == MAXLEN);
return t;
}
void STClear(StackType *s) // 清空栈
{
s->top = 0;
}
void STFree(StackType *s) // 释放栈所占的空间
{
if (s)
{
free(s);
}
}
int PushST(StackType *s, DATA data) // 入栈操作
{
if ((s->top + 1) > MAXLEN)
{
printf("栈溢出! \n");
return 0;
}
s->data[++s->top] = data;
return 1;
}
DATA PopST(StackType *s) // 出栈操作
{
if (s->top == 0)
{
printf("栈为空! \n");
exit(0);
}
return (s->data[s->top--]);
}
DATA PeekST(StackType *s) // 读取栈顶数据
{
if (s->top == 0)
{
printf("栈为空! \n");
exit(0);
}
return (s->data[s->top]);
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEN 50 // 最大长度
#define SIZE 100
typedef struct
{
char name[10];
int age;
}DATA;
typedef struct stack
{
DATA data[SIZE + 1]; // 数据元素
int top; // 栈顶
}StackType;
StackType *STInit()
{
StackType *p;
if (p = (StackType *)malloc(sizeof(StackType))) // 申请栈内存
{
p->top = 0; // 设置栈顶为0
return p; // 返回指向栈的指针
}
return NULL;
}
int STIsEmpty(StackType *s) // 判断栈是否为空
{
int t;
t = (s->top == 0);
return t;
}
int STIsFull(StackType *s) // 判断栈是否为满
{
int t;
t = (s->top == MAXLEN);
return t;
}
void STClear(StackType *s) // 清空栈
{
s->top = 0;
}
void STFree(StackType *s) // 释放栈所占的空间
{
if (s)
{
free(s);
}
}
int PushST(StackType *s, DATA data) // 入栈操作
{
if ((s->top + 1) > MAXLEN)
{
printf("栈溢出! \n");
return 0;
}
s->data[++s->top] = data;
return 1;
}
DATA PopST(StackType *s) // 出栈操作
{
if (s->top == 0)
{
printf("栈为空! \n");
exit(0);
}
return (s->data[s->top--]);
}
DATA PeekST(StackType *s) // 读取栈顶数据
{
if (s->top == 0)
{
printf("栈为空! \n");
exit(0);
}
return (s->data[s->top]);
}
int main()
{
StackType *stack;
DATA data, data2;
stack = STInit(); // 初始化栈
printf("入栈操作: \n");
printf("输入姓名 年龄进行入栈: \n");
do {
scanf("%s %d", data.name, &data.age);
if (strcmp(data.name, "0") == 0)
{
break; // 若输入为0,则退出
}
else {
PushST(stack, data);
}
} while(1);
do {
printf("\n出栈操作:按任意键进行出栈操作:");
getchar();
data2 = PopST(stack);
printf("出栈的数据是(%s ,%d) \n", data2.name, data2.age);
} while (1);
STFree(stack); // 释放栈所占的空间
return 0;
}
adge 12
asdf 14
popd 15
numb 16
一种操作受限的线性表,只允许在表的一端进行插入,而在表的另一端进行删除。
队列结构在日常生活中有很多例子。例如银行的电子排号系统,先来的人取的号靠前,后来的人取的号靠后。这样,先来的人将最先得到服务,后来的人将后得到服务,一切按照“先来先服务”的原则。
不是任何对线性表的操作都可以作为队列的操作。比如:不可以随便读取队列中的某个数据。
#define QUEUELEN 15
typedef struct
{
char name[10];
int age;
}DATA;
typedef struct
{
DATA data[QUEUELEN]; //队列数组
int head; // 队头
int tail; // 队尾
}SQType;
SQType *SQTypeInit()
{
SQType *q;
if (q = (SQType *)malloc(sizeof(SQType))) // 申请内存
{
q->head = 0; // 设置队头
q->tail = 0; // 设置队尾
return q;
}
else {
return NULL; // 返回空
}
}
int SQTypeIsEmpty(SQType *q) // 判断空队列
{
int temp;
temp = q->head == q->tail;
return (temp);
}
int SQTypeIsFull(SQType *q) // 判断满队列
{
int temp;
temp = q->tail == QUEUELEN;
return (temp);
}
void SQTypeClear(SQType *q) // 清空队列
{
q->head = 0; // 设置队头
q->tail = 0; // 设置队尾
}
void SQTypeFree(SQType *q) // 释放队列
{
if (q != NULL)
{
free(q);
}
}
int InSQType(SQType *q, DATA data) // 入队列
{
if (q->tail == QUEUELEN)
{
printf("队列已满!操作失败! \n");
return 0;
}
else {
q->data[q->tail++] = data; // 将元素入队
return (1);
}
}
DATA *OutSQType(SQType *q) // 出队列
{
if (q->head == q->tail)
{
printf("\n队列为空!操作失败! \n");
exit(0);
}
else {
return &(q->data[q->head++]);
}
}
DATA *PeekSQType(SQType *q) // 读取结点数据
{
if (SQTypeIsEmpty(q))
{
printf("\n空队列! \n");
return NULL;
}
else {
return &(q->data[q->head]);
}
}
int SQTypeLen(SQType *q) // 计算队列长度
{
int temp;
temp = q->tail - q->head;
return (temp);
}
#include <stdio.h>
#define QUEUELEN 15
typedef struct
{
char name[10];
int age;
}DATA;
typedef struct
{
DATA data[QUEUELEN]; //队列数组
int head; // 队头
int tail; // 队尾
}SQType;
SQType *SQTypeInit()
{
SQType *q;
if (q = (SQType *)malloc(sizeof(SQType))) // 申请内存
{
q->head = 0; // 设置队头
q->tail = 0; // 设置队尾
return q;
}
else {
return NULL; // 返回空
}
}
int SQTypeIsEmpty(SQType *q) // 判断空队列
{
int temp;
temp = q->head == q->tail;
return (temp);
}
int SQTypeIsFull(SQType *q) // 判断满队列
{
int temp;
temp = q->tail == QUEUELEN;
return (temp);
}
void SQTypeClear(SQType *q) // 清空队列
{
q->head = 0; // 设置队头
q->tail = 0; // 设置队尾
}
void SQTypeFree(SQType *q) // 释放队列
{
if (q != NULL)
{
free(q);
}
}
int InSQType(SQType *q, DATA data) // 入队列
{
if (q->tail == QUEUELEN)
{
printf("队列已满!操作失败! \n");
return 0;
}
else {
q->data[q->tail++] = data; // 将元素入队
return (1);
}
}
DATA *OutSQType(SQType *q) // 出队列
{
if (q->head == q->tail)
{
printf("\n队列为空!操作失败! \n");
exit(0);
}
else {
return &(q->data[q->head++]);
}
}
DATA *PeekSQType(SQType *q) // 读取结点数据
{
if (SQTypeIsEmpty(q))
{
printf("\n空队列! \n");
return NULL;
}
else {
return &(q->data[q->head]);
}
}
int SQTypeLen(SQType *q) // 计算队列长度
{
int temp;
temp = q->tail - q->head;
return (temp);
}
int main()
{
SQType *stack;
DATA data, *data2;
stack = SQTypeInit(); // 初始化队列
printf("入队列操作: \n");
printf("输入姓名 年龄进行入队操作: \n");
do {
scanf("%s %d", data.name, &data.age);
if (strcmp(data.name, "0") == 0)
{
break; // 若输入为0,停止入队
}
else {
InSQType(stack, data);
}
} while (1);
do {
printf("出队操作:按任意键进行出队操作:\n");
getchar();
data2 = OutSQType(stack);
printf("出队列的数据为(%s ,%d) \n", data2->name, data2->age);
} while (1);
SQTypeFree(stack); // 释放队列所占的内存空间
return 0;
}
qeqwe 12
gfdsg 45
fddgf 63
dsgff 32
rgyhp 15
树(Tree)结构是一种描述非线性层次关系的数据结构。
树结构一般采用层次括号法。层次括号法的基本规则如下:
- 根结点放入一对圆括号中。
- 根结点的子树由左至右的顺序放入括号中。
- 对子树做上述相同的处理。
- 这样,同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来按照这种方法,下图所示的树结构可以表示成如下形式:
- (A(B(E)),(C(F(J)),(G(K,L))),(D(H),(I(M,N))))
二叉树是树结构的一种特殊形式,它是n个结点的集合,每个结点最多只能有两个子结点。
二叉树的子树仍然是二叉树。
二叉树一个结点上对应的两个子树分别称为左子树和右子树。
由于子树有左右之分,因此二叉树是有序树。
一个二叉树结构也可以是空的,此时空二叉树中没有数据结点,也就是一个空集合。
如果二叉树结构中仅包含一个结点,那么这也是一个二叉树,树根便是该结点自身。
依照子树的位置的个数,二叉树还有如下图所示的几种形式:
对于一般的二叉树来说,在树结构中可能包含上述的各种形式。按照上述二叉树的几种形式来看,为了研究的方便,二叉树还可以进一步细分为两种特殊的类型,满二叉树和完全二叉树。
从上面的满二叉树和完全二叉树的定义可以知道,满二叉树一定是完全二叉树,而完全二叉树不一定是满二叉树,因为没有达到完全满分支的结构。
树结构可以分为顺序存储结构和链式存储结构两种。
#define MAXLen 100 // 最大结点数
typedef char DATA; // 元素类型
typedef DATA SeqBinTree[MAXLen];
SeqBinTree SBT; // 定义保存二叉树数组
这种存储方式最大的缺点,就是浪费存储空间,这是因为其中填充了大量的无用数据。因此,顺序存储方式一般只适用于完全二叉树的情况。对于更为一般的情况,建议采用链式存储方式。
二叉树的链式存储
typedef struct ChainTree
{
DATA NodeData; // 元素数据
struct ChainTree *LSonNode; // 左子树结点
struct ChainTree *RSonNode; // 右子树结点
}ChinaTreeType;
ChinaTreeType *root = NULL; // 定义二叉树根结点指针
typedef struct ChainTree
{
DATA NodeData; // 元素数据
struct ChainTree *LSonNode; // 左子树结点
struct ChainTree *RSonNode; // 右子树结点
struct ChainTree *ParentNode; // 父结点指针
}ChinaTreeType;
ChinaTreeType *root = NULL; // 定义二叉树根结点指针
#define MAXLEN 100 // 最大长度
typedef char DATA; // 元素类型
typedef struct CBT
{
DATA data; // 元素数据
struct CBT* left; // 左子树结点指针
struct CBT* right; // 右子树结点指针
}CBTType;
CBTType* InitTree() // 初始化二叉树的根结点
{
CBTType* node;
if (node = (CBTType*)malloc(sizeof(CBTType))) // 申请内存
{
printf("请输入一个根结点的数据:\n");
scanf("%s", &node->data);
node->left = NULL;
node->right = NULL;
if (node != NULL) // 如果根结点不为空
{
return node;
}
else {
return NULL;
}
}
return NULL;
}
CBTType *TreeFindNode(CBTType *treeNode, DATA data) // 查找结点
{
CBTType *ptr;
if (treeNode == NULL)
{
return NULL;
}
else {
if (treeNode->data == data)
{
return treeNode;
}
else {
if (ptr = TreeFindNode(treeNode->left, data)) // 分别向左右子树递归查找
{
return ptr;
}
else if (ptr = TreeFindNode(treeNode->right, data))
{
return ptr;
}
else {
return NULL;
}
}
}
}
void AddTreeNode(CBTType* treeNode) // 添加结点
{
CBTType *pnode, *parent;
DATA data;
char menusel;
if (pnode = (CBTType *)malloc(sizeof(CBTType))) // 分配内存
{
printf("输入二叉树的结点数据:\n");
fflush(stdin); // 清空输入缓冲区
scanf("%s", &pnode->data);
pnode->left = NULL; // 设置左子树为空
pnode->right = NULL; // 设置右子树为空
printf("输入该结点的父结点数据:");
fflush(stdin); // 清空输入缓冲区
scanf("%s", &data);
parent = TreeFindNode(treeNode, data); // 查找指定数据的结点
if (!parent) // 如果未找到
{
printf("未找到该数据的父结点!\n");
free(pnode); // 释放创建的结点内存
return;
}
printf("1.添加该结点到左子树结点.\n2.添加该节点到右子树.\n");
do {
menusel = getch(); // 输入选择项
menusel -= '0';
if (menusel == 1 || menusel == 2)
{
if (parent == NULL)
{
printf("不存在父结点,请先设置父结点!\n");
}
else {
switch (menusel)
{
case 1: // 添加到左结点
if (parent->left) // 左子树不为空
{
printf("左子树结点不为空!\n");
}
else {
parent->left = pnode;
}
break;
case 2: // 添加到右结点
if (parent->right) // 右子树不为空
{
printf("右子树结点不为空!\n");
}
else {
parent->right = pnode;
}
break;
default:
printf("输入了无效参数!\n");
}
}
}
} while (menusel != 1 && menusel != 2);
}
}
CBTType *TreeLeftNode(CBTType *treeNode) // 获取左子树
{
if (treeNode)
{
return treeNode->left; // 返回值
}
else {
return NULL;
}
}
CBTType *TreeRightNode(CBTType *treeNode) // 获取右子树
{
if (treeNode)
{
return treeNode->right; // 返回值
}
else {
return NULL;
}
}
CBTType *TreeIsEmpty(CBTType *treeNode) // 判断空树
{
if (treeNode)
{
return 0; // 返回值
}
else {
return 1;
}
}
int TreeDepth(CBTType *treeNode) // 计算二叉树深度
{
int depleft, depright;
if (treeNode == NULL) {
return 0;
}
else {
depleft = TreeDepth(treeNode->left); // 左子树深度
depright = TreeDepth(treeNode->right); // 右子树深度
if (depleft > depright)
{
return depleft + 1;
}
else {
return depright + 1;
}
}
}
void ClearTree(CBTType *treeNode) // 清空二叉树
{
if (treeNode)
{
ClearTree(treeNode->left); // 清空左子树
ClearTree(treeNode->right); // 清空右子树
free(treeNode); // 释放当前结点所占内存
treeNode = NULL;
}
}
void TreeNodeData(CBTType *p) // 显示结点数据
{
printf("%c ", p->data); // 输出结点数据
}
void LevelTree(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) // 按层遍历
{
CBTType *p;
CBTType *q[MAXLEN]; //定义顺序栈
int head = 0, tail = 0;
if (treeNode) // 如果队首指针不为空
{
tail = (tail + 1) % MAXLEN; // 计算循环队列队尾序号
q[tail] = treeNode; // 将二叉树根指针进队
}
while (head != tail) // 队列不为空,进行循环
{
head = (head + 1) % MAXLEN; // 计算循环队列队首序号
p = q[head]; // 获取队首元素
TreeNodeData(p); // 处理队首元素
if (p->left != NULL) // 如果结点存在左子树
{
tail = (tail + 1) % MAXLEN; // 计算循环队列队尾序号
q[tail] = p->left; // 将左子树指针进队
}
if (p->right != NULL) // 如果结点存在右子树
{
tail = (tail + 1) % MAXLEN; // 计算循环队列队尾序号
q[tail] = p->right; // 将右子树指针进队
}
}
}
void DLRTree(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) // 先序遍历
{
if (treeNode)
{
TreeNodeData(treeNode); // 显示结点数据
DLRTree(treeNode->left, TreeNodeData); // 先序遍历左子树
DLRTree(treeNode->right, TreeNodeData); // 先序遍历右子树
}
}
void LDRTree(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) // 中序遍历
{
if (treeNode)
{
LDRTree(treeNode->left, TreeNodeData); // 中序遍历左子树
TreeNodeData(treeNode); // 显示结点数据
LDRTree(treeNode->right, TreeNodeData); // 中序遍历右子树
}
}
void LRDTree(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) // 后序遍历
{
if (treeNode)
{
LRDTree(treeNode->left, TreeNodeData); // 后序遍历左子树
LRDTree(treeNode->right, TreeNodeData); // 后序遍历右子树
TreeNodeData(treeNode); // 显示结点数据
}
}
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define MAXLEN 100 // 最大长度
typedef char DATA; // 元素类型
typedef struct CBT
{
DATA data; // 元素数据
struct CBT* left; // 左子树结点指针
struct CBT* right; // 右子树结点指针
}CBTType;
CBTType* InitTree() // 初始化二叉树的根结点
{
CBTType* node;
if (node = (CBTType*)malloc(sizeof(CBTType))) // 申请内存
{
printf("请输入一个根结点的数据:\n");
scanf("%s", &node->data);
node->left = NULL;
node->right = NULL;
if (node != NULL) // 如果根结点不为空
{
return node;
}
else {
return NULL;
}
}
return NULL;
}
CBTType *TreeFindNode(CBTType *treeNode, DATA data) // 查找结点
{
CBTType *ptr;
if (treeNode == NULL)
{
return NULL;
}
else {
if (treeNode->data == data)
{
return treeNode;
}
else {
if (ptr = TreeFindNode(treeNode->left, data)) // 分别向左右子树递归查找
{
return ptr;
}
else if (ptr = TreeFindNode(treeNode->right, data))
{
return ptr;
}
else {
return NULL;
}
}
}
}
void AddTreeNode(CBTType* treeNode) // 添加结点
{
CBTType *pnode, *parent;
DATA data;
char menusel;
if (pnode = (CBTType *)malloc(sizeof(CBTType))) // 分配内存
{
printf("输入二叉树的结点数据:\n");
fflush(stdin); // 清空输入缓冲区
scanf("%s", &pnode->data);
pnode->left = NULL; // 设置左子树为空
pnode->right = NULL; // 设置右子树为空
printf("输入该结点的父结点数据:");
fflush(stdin); // 清空输入缓冲区
scanf("%s", &data);
parent = TreeFindNode(treeNode, data); // 查找指定数据的结点
if (!parent) // 如果未找到
{
printf("未找到该数据的父结点!\n");
free(pnode); // 释放创建的结点内存
return;
}
printf("1.添加该结点到左子树结点.\n2.添加该节点到右子树.\n");
do {
menusel = getch(); // 输入选择项
menusel -= '0';
if (menusel == 1 || menusel == 2)
{
if (parent == NULL)
{
printf("不存在父结点,请先设置父结点!\n");
}
else {
switch (menusel)
{
case 1: // 添加到左结点
if (parent->left) // 左子树不为空
{
printf("左子树结点不为空!\n");
}
else {
parent->left = pnode;
}
break;
case 2: // 添加到右结点
if (parent->right) // 右子树不为空
{
printf("右子树结点不为空!\n");
}
else {
parent->right = pnode;
}
break;
default:
printf("输入了无效参数!\n");
}
}
}
} while (menusel != 1 && menusel != 2);
}
}
CBTType *TreeLeftNode(CBTType *treeNode) // 获取左子树
{
if (treeNode)
{
return treeNode->left; // 返回值
}
else {
return NULL;
}
}
CBTType *TreeRightNode(CBTType *treeNode) // 获取右子树
{
if (treeNode)
{
return treeNode->right; // 返回值
}
else {
return NULL;
}
}
CBTType *TreeIsEmpty(CBTType *treeNode) // 判断空树
{
if (treeNode)
{
return 0; // 返回值
}
else {
return 1;
}
}
int TreeDepth(CBTType *treeNode) // 计算二叉树深度
{
int depleft, depright;
if (treeNode == NULL) {
return 0;
}
else {
depleft = TreeDepth(treeNode->left); // 左子树深度
depright = TreeDepth(treeNode->right); // 右子树深度
if (depleft > depright)
{
return depleft + 1;
}
else {
return depright + 1;
}
}
}
void ClearTree(CBTType *treeNode) // 清空二叉树
{
if (treeNode)
{
ClearTree(treeNode->left); // 清空左子树
ClearTree(treeNode->right); // 清空右子树
free(treeNode); // 释放当前结点所占内存
treeNode = NULL;
}
}
void TreeNodeData(CBTType *p) // 显示结点数据
{
printf("%c ", p->data); // 输出结点数据
}
void LevelTree(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) // 按层遍历
{
CBTType *p;
CBTType *q[MAXLEN]; //定义顺序栈
int head = 0, tail = 0;
if (treeNode) // 如果队首指针不为空
{
tail = (tail + 1) % MAXLEN; // 计算循环队列队尾序号
q[tail] = treeNode; // 将二叉树根指针进队
}
while (head != tail) // 队列不为空,进行循环
{
head = (head + 1) % MAXLEN; // 计算循环队列队首序号
p = q[head]; // 获取队首元素
TreeNodeData(p); // 处理队首元素
if (p->left != NULL) // 如果结点存在左子树
{
tail = (tail + 1) % MAXLEN; // 计算循环队列队尾序号
q[tail] = p->left; // 将左子树指针进队
}
if (p->right != NULL) // 如果结点存在右子树
{
tail = (tail + 1) % MAXLEN; // 计算循环队列队尾序号
q[tail] = p->right; // 将右子树指针进队
}
}
}
void DLRTree(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) // 先序遍历
{
if (treeNode)
{
TreeNodeData(treeNode); // 显示结点数据
DLRTree(treeNode->left, TreeNodeData); // 先序遍历左子树
DLRTree(treeNode->right, TreeNodeData); // 先序遍历右子树
}
}
void LDRTree(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) // 中序遍历
{
if (treeNode)
{
LDRTree(treeNode->left, TreeNodeData); // 中序遍历左子树
TreeNodeData(treeNode); // 显示结点数据
LDRTree(treeNode->right, TreeNodeData); // 中序遍历右子树
}
}
void LRDTree(CBTType *treeNode, void(*TreeNodeData)(CBTType *p)) // 后序遍历
{
if (treeNode)
{
LRDTree(treeNode->left, TreeNodeData); // 后序遍历左子树
LRDTree(treeNode->right, TreeNodeData); // 后序遍历右子树
TreeNodeData(treeNode); // 显示结点数据
}
}
void main()
{
CBTType *root = NULL; // root为指向二叉树根结点的指针
char menusel;
void(*TreeNodeDatal)(); // 指向函数的指针
TreeNodeDatal = TreeNodeData; // 指向具体操作的函数
root = InitTree(); // 设置根元素
do { // 添加结点
printf("请选择菜单添加二叉树的结点!\n");
printf("0.退出\t");
printf("1.添加二叉树的结点!\n");
menusel = getch();
switch (menusel)
{
case '1':
AddTreeNode(root); // 添加结点
break;
case '0':
break;
default:
break;
}
} while (menusel != '0');
// 遍历二叉树
do {
printf("选择二叉树遍历序号,输入0表示退出:\n"); // 显示菜单
printf("1.先序遍历DLR\t");
printf("2.中序遍历LDR\t");
printf("3.后序遍历LRD\t");
printf("4.按层遍历\n");
menusel = getch();
switch (menusel)
{
case '0':
break;
case '1': // 先序遍历
printf("\n先序遍历结果:");
DLRTree(root, TreeNodeDatal);
printf("\n");
break;
case '2': // 中序遍历
printf("\n中序遍历结果:");
LDRTree(root, TreeNodeDatal);
printf("\n");
break;
case '3': // 后序遍历
printf("\n后序遍历结果:");
LRDTree(root, TreeNodeDatal);
printf("\n");
break;
case '4': // 按层遍历
printf("\n按层遍历结果:");
LevelTree(root, TreeNodeDatal);
printf("\n");
break;
default:
break;
}
} while (menusel != '0');
printf("\n二叉树深度为:%d\n", TreeDepth(root)); // 二叉树深度
ClearTree(root); // 清空二叉树
root = NULL;
}
图(Graph)结构也是一种非线性数据结构,图结构在实际生活中具有非常多的例子。例如,通信网络、交通网络、人际关系网络等都可以归结为图结构。
一个典型的图结构包括如下两个部分:
所有的顶点构成一个顶点集合,所有的边构成边集合,一个完整的图结构就是由顶点集合和边集合组成。图结构在数学上一般记为如下所示的形式:
G=(V,E)
或者
G=(V(G),E(G))
其中,V(G)表示图结构中所有顶点的集合,顶点可以用不同的数字或者字母来表示。E(G)是图结构中所有边的集合,每条边由所连接的两个顶点表示。
注意:图结构中顶点集合V(G)必须为非空,即必须包含一个顶点。而图结构中边集合E(G)可以为空,此时表示没有边。
例如,对于上文所示的图结构,对应的顶点集合和边集合如下:
V(G)={V1,V2,V3,V4,V5,V6}
E(G)={(V1,V2),(V1,V3),(V1,V5),(V2,V4),(V3,V5),(V4,V5),(V4,V6),(V5,V6)}
无向图:如果一个图结构中所有的边都没有方向性,这种图便被称为无向图。
由于无向图中的边没有方向性,在表示边时对两个顶点的顺序没有要求。例如顶点V1和顶点V5之间的边,可以表示为(V1,V5),也可以表示为(V5,V1)。
即下图对应的顶点集合和边集合如下:
V(G)={V1,V2,V3,V4,V5}
E(G)={(V1,V2),(V1,V5),(V2,V4),(V3,V5),(V4,V5),(V1,V3)}
有向图:如果一个图结构中边是有方向性的,这种图便被称为有向图。
由于有向图中的边有方向性,所以在表示边时对两个顶点的顺序有所要求。
为了与无向图区分,这里采用尖括号表示有向边。
例如,<V3,V4>表示从顶点V3到顶点V4的一条边,而<V4,V3>表示从顶点V4到顶点V3的一条边。<V3,V4>和<V4,V3>表示的是两条不同的边。
即下图对应的顶点集合和边集合如下:
V(G)={V1,V2,V3,V4,V5,V6}
E(G)={<V1,V2>,<V2,V1>,<V2,V3>,<V3,V4>,<V4,V3>,<V4,V5>,<V5,V6>,<V6,V4>,<V6,V2>}
无向完全图:在无向图中,每两个顶点之间都存在一条边。
有向完全图:在有向图中,每两个顶点之间都存在方向相反的两条边。
顶点的度、入度和出度
邻接顶点:图结构中一条边的两个顶点。
连通、连通图、连通分量:
如果图结构中两个顶点之间有路径,则称这两个路径是连通的。
如果无向图中任意两个顶点都是连通的,那么这个图便称为连通图。
如果无向图中包含两个顶点是不连通的,那么这个图便称为非连通图。
无向图的极大连通子图称为该图的连通分量。
对于一个连通图,其连通分量有且只有一个,就是该连通图自身。而对于一个非连通图,则有可能存在多个连通分量。
对于n个顶点的无向图G, 若G是连通图,则最少有 n-1 条边 若G是非连通图,则最多可能有
C
n
?
1
2
C_{n-1}^{2}
Cn?12?
条边。
例如,在下图中,图(a)为一个非连通图,因为顶点V2和顶点V3之间没有路径。这个非连通图中的连通分量包括两个,分别为图(b)和图(c)。
边的权、网:
带权图/网:边上带有权值的图称为带权图,也称网。
生成树、生成森林:
树、有向树
边数很少的图称为稀疏图,反之称为稠密图。
邻接矩阵
采用结构数组的形式来单独保存顶点信息,然后采用二维数组的形式保存顶点之间的关系。这种保存顶点之间关系的数组称为邻接矩阵(Adjacency Matrix)。
对于一个包含n个顶点的图,可以使用如下语句来声明1个数组保存顶点信息,再声明1个邻接矩阵保存边的权。
char Vertex[n]; //保存顶点信息(序号或字母)
int EdgeWeight[n][n]; //邻接矩阵,保存边的权
对于下图所示的无向图,可以采用一维数组来保存顶点,保存的形式如图2所示:
程序示例代码如下:
Vertex[1]=1;
Vertex[2]=2;
Vertex[3]=3;
Vertex[4]=4;
Vertex[5]=5;
对于邻接矩阵,可以按照下图所示的形式进行存储。
对于有向图,如下所示:
对于有向带权图:
注意:在实际程序中为了保存带权值的图,需要定义一个最大值MAX,其值大于所有边的权值之和,用MAX来替代特殊的符号Z保存在二维数组中。
#define MaxNum 20 // 图的最大顶点数
#define MaxValue 65535 // 最大值(可设为一个最大整数)
typedef struct
{
char Vertex[MaxNum]; // 保存顶点信息(序号或字母)
int GType; // 图的类型(0:无向图,1:有向图)
int VertexNum; // 顶点的数量
int EdgeNum; // 边的数量
int Edgeweight[MaxNum][MaxNum]; // 保存边的权
int isTrav[MaxNum]; // 遍历标志
}GraphMatrix; // 定义邻接矩阵图结构
void CreateGraph(GraphMatrix *GM) // 创建邻接矩阵图
{
int i, j, k;
int weight; // 权
char EstartV, EendV; // 边的起始顶点
printf("输入图中各顶点信息\n");
for (i = 0; i < GM->VertexNum; i++) // 输入顶点
{
getchar();
printf("第%d个顶点:", i + 1);
scanf("%c", &(GM->Vertex[i])); // 保存到各顶点数组元素中
}
printf("输入构成各边的顶点及权值:\n");
for (k = 0; k < GM->EdgeNum; k++) // 输入边的信息
{
getchar();
printf("第%d条边:", k + 1);
scanf("%c %c %d", &EstartV, &EendV, &weight);
for (i = 0; EstartV != GM->Vertex[i]; i++); // 在已有顶点中查找始点
for (j = 0; EendV != GM->Vertex[j]; j++); // 在已有顶点中查找终点
GM->Edgeweight[i][j] = weight; // 对应位置保存权值,表示有一条边
if (GM->GType == 0) // 若是无向图
{
GM->Edgeweight[j][i] = weight; // 在对角位置保存权值
}
}
}
void ClearGraph(GraphMatrix *GM)
{
int i, j;
for (i = 0; i < GM->VertexNum; i++) // 清空矩阵
{
for (j = 0; j < GM->VertexNum; j++)
{
GM->Edgeweight[i][j] = MaxValue; // 设置矩阵中各元素的值为Maxvalue
}
}
}
void OutGraph(GraphMatrix *GM) // 输出邻接矩阵
{
int i, j;
for (j = 0; j < GM->VertexNum; j++)
{
printf("\t%c", GM->Vertex[j]); // 在第1行输出顶点信息
}
printf("\n");
for (i = 0; i < GM->VertexNum; i++)
{
printf("%c", GM->Vertex[i]);
for (j = 0; j < GM->VertexNum; j++)
{
if (GM->Edgeweight[i][j] == MaxValue) // 若权值为最大值
{
printf("\tZ"); // 用表示无穷大
}
else {
printf("\t%d", GM->Edgeweight[i][j]); // 输出边的权值
}
}
printf("\n");
}
}
void DeepTraOne(GraphMatrix *GM, int n) // 从第n个结点开始,深度遍历图
{
int i;
GM->isTrav[n] = 1; // 标记该顶点已处理过
printf("->%c", GM->Vertex[n]); // 输出结点数据
//添加处理结点的操作
for (i = 0; i < GM->VertexNum; i++)
{
if (GM->Edgeweight[n][i] != MaxValue && !GM->isTrav[n])
{
DeepTraOne(GM, i); // 递归进行遍历
}
}
}
void DeepTraGraph(GraphMatrix *GM) // 深度优先遍历
{
int i;
for (i = 0; i < GM->VertexNum; i++) // 清除各顶点遍历标志
{
GM->isTrav[i] = 0;
}
printf("深度优先遍历结点:");
for (i = 0; i < GM->VertexNum; i++)
{
if (!GM->isTrav[i]) // 若该点未遍历
{
DeepTraOne(GM, i); // 调用函数遍历
}
}
printf("\n");
}
#include <stdio.h>
#define MaxNum 20 // 图的最大顶点数
#define MaxValue 65535 // 最大值(可设为一个最大整数)
typedef struct
{
char Vertex[MaxNum]; // 保存顶点信息(序号或字母)
int GType; // 图的类型(0:无向图,1:有向图)
int VertexNum; // 顶点的数量
int EdgeNum; // 边的数量
int Edgeweight[MaxNum][MaxNum]; // 保存边的权
int isTrav[MaxNum]; // 遍历标志
}GraphMatrix; // 定义邻接矩阵图结构
void CreateGraph(GraphMatrix *GM) // 创建邻接矩阵图
{
int i, j, k;
int weight; // 权
char EstartV, EendV; // 边的起始顶点
printf("输入图中各顶点信息\n");
for (i = 0; i < GM->VertexNum; i++) // 输入顶点
{
getchar();
printf("第%d个顶点:", i + 1);
scanf("%c", &(GM->Vertex[i])); // 保存到各顶点数组元素中
}
printf("输入构成各边的顶点及权值:\n");
for (k = 0; k < GM->EdgeNum; k++) // 输入边的信息
{
getchar();
printf("第%d条边:", k + 1);
scanf("%c %c %d", &EstartV, &EendV, &weight);
for (i = 0; EstartV != GM->Vertex[i]; i++); // 在已有顶点中查找始点
for (j = 0; EendV != GM->Vertex[j]; j++); // 在已有顶点中查找终点
GM->Edgeweight[i][j] = weight; // 对应位置保存权值,表示有一条边
if (GM->GType == 0) // 若是无向图
{
GM->Edgeweight[j][i] = weight; // 在对角位置保存权值
}
}
}
void ClearGraph(GraphMatrix *GM)
{
int i, j;
for (i = 0; i < GM->VertexNum; i++) // 清空矩阵
{
for (j = 0; j < GM->VertexNum; j++)
{
GM->Edgeweight[i][j] = MaxValue; // 设置矩阵中各元素的值为Maxvalue
}
}
}
void OutGraph(GraphMatrix *GM) // 输出邻接矩阵
{
int i, j;
for (j = 0; j < GM->VertexNum; j++)
{
printf("\t%c", GM->Vertex[j]); // 在第1行输出顶点信息
}
printf("\n");
for (i = 0; i < GM->VertexNum; i++)
{
printf("%c", GM->Vertex[i]);
for (j = 0; j < GM->VertexNum; j++)
{
if (GM->Edgeweight[i][j] == MaxValue) // 若权值为最大值
{
printf("\tZ"); // 用表示无穷大
}
else {
printf("\t%d", GM->Edgeweight[i][j]); // 输出边的权值
}
}
printf("\n");
}
}
void DeepTraOne(GraphMatrix *GM, int n) // 从第n个结点开始,深度遍历图
{
int i;
GM->isTrav[n] = 1; // 标记该顶点已处理过
printf("->%c", GM->Vertex[n]); // 输出结点数据
//添加处理结点的操作
for (i = 0; i < GM->VertexNum; i++)
{
if (GM->Edgeweight[n][i] != MaxValue && !GM->isTrav[n])
{
DeepTraOne(GM, i); // 递归进行遍历
}
}
}
void DeepTraGraph(GraphMatrix *GM) // 深度优先遍历
{
int i;
for (i = 0; i < GM->VertexNum; i++) // 清除各顶点遍历标志
{
GM->isTrav[i] = 0;
}
printf("深度优先遍历结点:");
for (i = 0; i < GM->VertexNum; i++)
{
if (!GM->isTrav[i]) // 若该点未遍历
{
DeepTraOne(GM, i); // 调用函数遍历
}
}
printf("\n");
}
void main()
{
GraphMatrix GM; // 定义保存邻接表结构的图
printf("输入生成图的类型:");
scanf("%d", &GM.GType); // 图的种类
printf("输入图的顶点数量:");
scanf("%d", &GM.VertexNum); // 输入图顶点数
printf("输入图的边数量:");
scanf("%d", &GM.EdgeNum); // 输入图边数
ClearGraph(&GM); // 清空图
CreateGraph(&GM); // 生成邻接表结构的图
printf("该图的邻接矩阵数据如下:\n");
OutGraph(&GM); // 输出邻接矩阵
DeepTraGraph(&GM); // 深度优先搜索遍历图
}
- [1]. 2020年王道考研数据结构考研复习指导.王道论坛
- [2]. C/C++常用算法手册(第三版).刘亚冬
- [3]. 数据结构(C语言版).严蔚敏(黑版)
- [4]. 算法笔记.胡凡
- [5]. 数据结构习题与解析(第3版).李春葆
- [6]. 数据结构与算法(C语言版).胡明
全文仅用于个人备考复习,不可商用
。
开发过程中,我们经常会遇到代码回滚的情况。正常人都知道,git 回滚有两大宝: ...
不少Windows 10用户之前都抱怨一个问题,那就是系统的屏幕出现了渲染问题,而微...
console.log ,作为一个前端开发者,可能每天都会用它来分析调试,但这个简单函...
本文转载自微信公众号「Linux开发那些事儿」,作者 LinuxThings 。转载本文请联...
继 Australis 和 Photon 之后,Mozilla 现又酝酿为 Firefox 带来名为Proton的全...
2月26日消息 众所周知,Windows 10 的安全更新和其他重要累计更新通常是在同一天...
前言 aop即是面向切面编程,众多Aop框架里Castle是最为人所知的,另外还有死去的...
简介 “ 大家好我是帅哥欢迎来到帅哥的程序人生我会把经历分享出来助你了解圈内...
一、Postman背景介绍 用户在开发或者调试网络程序或者是网页B/S模式的程序的时候...
互联网业务往往使用MySQL数据库作为后台存储,存储引擎使用InnoDB。我们针对互联...