希望本篇文章对大家有所帮助!!@!!
设计任务:
设计一个基于DOS菜单的应用程序。要求利用多级菜单实现各种功能。内容如下：
- 单链表的基本操作及应用
- 创建
- 插入
- 删除
- 查找
- 显示
- 通讯录设计（应用）
- 栈的基本操作及应用
- 进栈
- 出栈
- 取栈顶元素
- 表达式的求解（应用）
- 数组的基本操作及应用
- 创建
- 显示
- 矩阵乘法（应用）
- 二叉树的基本操作及应用
- 创建二叉树
- 遍历二叉树（先序、中序、后序）
- 计算叶子结点个数及树的深度
- 查找指定结点的双亲
- 查找指定结点的兄弟
- Huffman编码（应用）
- 图的基本操作及应用
- 创建无向图
- 创建有向图
- 创建无向网
- 创建有向网
- 遍历
- 拓扑排序
- 最小生成树（应用）
- 最短路径（应用）
- 关键路径（应用）
1.图的操作:
#pragma once
#include"功能实现.h"
#include<cstdio>
#include<stdlib.h>
#include<malloc.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1 //infeasible
#define OVERFLOW -2 //overflow
typedef int Status;
typedef int ElemType;
//定点数量最大个数
#define MAX_VERTEX_NUM 20
typedef int InfoType ;
typedef char VertexType;
typedef int ElemType;
bool visited[MAX_VERTEX_NUM]; //访问标志数组
//队列的结构
//队列的基本操作
typedef struct QueueNode {
ElemType data;
struct QueueNode* next;
}Squeue, * queue;
typedef struct {
queue front, rear;
}Queue, * LinkQueue;
//-----------------------------------------------------
//图的结构
typedef struct ArcNode { //相当于边关系区块
ElemType adjvex; //相当于 V1-V2 中储存V2
struct ArcNode* nextarc; //指向下一条弧的指针
InfoType info; //权值
}ArcNode;
typedef struct VNode {
VertexType data; // 结点值
ArcNode* firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;//图的当前顶点数和弧数
int kind; //类型
}ALGraph;
//-----------------------------------------------------
//队列的操作
void initQueue(LinkQueue Q);
bool QueueisEmpty(LinkQueue Q);
void EnQueue(LinkQueue Q, ElemType x);
bool DeQueue(LinkQueue Q, ElemType &x);
//图的操作
Status Test5(void);
Status ShowMeun5(void);
Status CreateGraph(ALGraph& G,int Kind);
Status CreatDG(ALGraph& G);
Status CreatDN(ALGraph& G);
Status CreatUDG(ALGraph& G);
Status CreatUDN(ALGraph& G);
Status ShowGraph(ALGraph& G);
Status ShowDG(ALGraph& G); //有向图的邻接表输出
Status ShowDN(ALGraph& G); //有向网的邻接表输出
Status ShowUDG(ALGraph& G); //无向图的邻接表输出
Status ShowUDN(ALGraph& G); //无向网的邻接表输出
Status Depth_First_Search(ALGraph& G); //深度优先搜索
Status Broadth_First_Search(ALGraph& G); //广度优先搜索
Status DFS(ALGraph& G, int i);
Status TopologicalSort(ALGraph G);
Status FindInDegree(ALGraph G, int indegree[MAX_VERTEX_NUM]);
int LocateVex(ALGraph G, char v); //返回结点下标
int FirstAdjVex(ALGraph& G, int i);
int NextAdjVex(ALGraph& T, int v, int w);
//-----------------------------------------------------
Status CreateGraph(ALGraph& G,int Kind) {
G.kind = Kind;
switch (Kind) {
case 0:return CreatUDG(G); //构造无向图
case 1:return CreatUDN(G); //构造无向网
case 2:return CreatDG(G); //构造有向图
case 3:return CreatDN(G); //构造有向网
default:return ERROR;
}
return OK;
}
Status CreatUDG(ALGraph& G) { //无向图(边无权值)
printf("请输入顶点数 -->");
scanf("%d", &G.vexnum);
printf("请输入图边数 -->");
scanf("%d", &G.arcnum);
printf("请按顺序插入顶点信息(格式)a b c d\n");
for (int i = 0; i < G.vexnum; ++i) { //初始化顶点
getchar();
scanf("%c", &G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
printf("请输入边的信息(格式)ab\n");
for (int k = 0; k < G.arcnum; k++) { //边个数
char v1, v2;
getchar();
scanf("%c%c", &v1, &v2);
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
//对i行进行区块插入
ArcNode* Temp1 = (ArcNode*)malloc(sizeof(ArcNode));
Temp1->info = 0;
Temp1->adjvex = j;
Temp1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = Temp1;
//对j行区块插入
ArcNode* Temp2 = (ArcNode*)malloc(sizeof(ArcNode));
Temp2->info = 0;
Temp2->adjvex = i;
Temp2->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = Temp2;
}
return OK;
}
Status CreatUDN(ALGraph& G) { //无向网
printf("请输入顶点数 -->");
scanf("%d", &G.vexnum);
printf("请输入图边数 -->");
scanf("%d", &G.arcnum);
printf("请按顺序插入顶点信息(格式)a b c d\n");
for (int i = 0; i < G.vexnum; ++i) { //初始化顶点
getchar();
scanf("%c", &G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
printf("请输入边的信息(格式)ab-3\n");
for (int k = 0; k < G.arcnum; k++) { //边个数
char v1, v2;
int Info;
getchar();
scanf("%c%c-%d", &v1, &v2,&Info);
int i = LocateVex(G, v1);
int j = LocateVex(G, v2);
//对i行进行区块插入
ArcNode* Temp1 = (ArcNode*)malloc(sizeof(ArcNode));
Temp1->info = Info;
Temp1->adjvex = j;
Temp1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = Temp1;
//对j行区块插入
ArcNode* Temp2 = (ArcNode*)malloc(sizeof(ArcNode));
Temp2->info = Info;
Temp2->adjvex = i;
Temp2->nextarc = G.vertices[j].firstarc;
G.vertices[j].firstarc = Temp2;
}
return OK;
}
Status CreatDG(ALGraph& G) { //有向图
printf("请输入顶点数 -->");
scanf("%d", &G.vexnum);
printf("请输入图边数 -->");
scanf("%d", &G.arcnum);
printf("请按顺序插入顶点信息(格式)a b c d\n");
for (int i = 0; i < G.vexnum; ++i) { //初始化顶点
getchar();
scanf("%c", &G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
printf("请输入边的信息\n");
for (int k = 0; k < G.arcnum; k++) { //边个数
char v1, v2;
getchar();
scanf("%c%c", &v1, &v2);
int i = LocateVex(G, v1);
//对i行进行区块插入
ArcNode* Temp1 = (ArcNode*)malloc(sizeof(ArcNode));
Temp1->info = 0;
Temp1->adjvex = LocateVex(G, v2);
Temp1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = Temp1;
}
return OK;
}
Status CreatDN(ALGraph& G) { //有向网
printf("请输入顶点数 -->");
scanf("%d", &G.vexnum);
printf("请输入图边数 -->");
scanf("%d", &G.arcnum);
printf("请按顺序插入顶点信息(格式)a b c d\n");
for (int i = 0; i < G.vexnum; ++i) { //初始化顶点
getchar();
scanf("%c", &G.vertices[i].data);
G.vertices[i].firstarc = NULL;
}
printf("请输入边的信息(格式)ab_3\n");
for (int k = 0; k < G.arcnum; k++) { //边个数
char v1, v2;
int Info;
getchar();
scanf("%c%c_%d", &v1, &v2, &Info);
int i = LocateVex(G, v1);
//对i行进行区块插入
ArcNode* Temp1 = (ArcNode*)malloc(sizeof(ArcNode));
Temp1->info = Info;
Temp1->adjvex = LocateVex(G, v2);
Temp1->nextarc = G.vertices[i].firstarc;
G.vertices[i].firstarc = Temp1;
}
return OK;
}
Status ShowGraph(ALGraph& G) {
switch (G.kind) {
case 0:return ShowUDG(G); //输出无向图
case 1:return ShowUDN(G); //输出无向网
case 2:return ShowDG(G); //输出有向图
case 3:return ShowDN(G); //输出有向网
default:return ERROR;
}
}
Status ShowUDG(ALGraph& G) { //无向图的邻接表输出
printf("该无向图邻接表输出结果如下\n");
ArcNode* Temp;
for (int i = 0; i < G.vexnum; i++) { //每行顶点分开输出
printf("%c: ", G.vertices[i].data);
for (Temp = G.vertices[i].firstarc; Temp; Temp = Temp->nextarc)
printf(" ->%c", G.vertices[Temp->adjvex].data);
printf("\n");
}
return OK;
}
Status ShowUDN(ALGraph& G) {
printf("该无向网邻接表输出结果如下\n");
ArcNode* Temp;
for (int i = 0; i < G.vexnum; i++) { //每行顶点分开输出
printf("%c: ", G.vertices[i].data);
for (Temp = G.vertices[i].firstarc; Temp; Temp = Temp->nextarc)
printf(" ->%c|%d", G.vertices[Temp->adjvex].data, Temp->info);
printf("\n");
}
return OK;
}
Status ShowDG(ALGraph& G) { //有向图的邻接表输出
printf("该有向图邻接表输出结果如下\n");
ArcNode* Temp;
for (int i = 0; i < G.vexnum; i++) { //每行顶点分开输出
printf("%c: ", G.vertices[i].data);
for (Temp = G.vertices[i].firstarc; Temp; Temp = Temp->nextarc)
printf(" ->%c", G.vertices[Temp->adjvex].data);
printf("\n");
}
return OK;
}
Status ShowDN(ALGraph& G) { //有向网
printf("该有向图邻接表输出结果如下\n");
ArcNode* Temp;
for (int i = 0; i < G.vexnum; i++) { //每行顶点分开输出
printf("%c: ", G.vertices[i].data);
for (Temp = G.vertices[i].firstarc; Temp; Temp = Temp->nextarc)
printf(" ->%c|%d", G.vertices[Temp->adjvex].data, Temp->info);
printf("\n");
}
return OK;
}
Status Depth_First_Search(ALGraph& G) {
if (G.kind == 0) printf("无向图深度优先遍历结果如下:\n");
else if(G.kind==1) printf("无向网深度优先遍历结果如下:\n");
else if (G.kind == 2) { printf("有向图无法进行深度优先遍历\n"); return ERROR; }
else if (G.kind == 3) { printf("有向网无法进行深度优先遍历:\n"); return ERROR; }
printf("深度优先搜索结果如下\n");
for (int i = 0; i < G.vexnum; i++) visited[i] = FALSE; //标志位清空
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) DFS(G, i);
}
printf("\n");
return TRUE;
}
Status Broadth_First_Search(ALGraph& G) {
if (G.kind == 0) printf("无向图广度优先遍历结果如下:\n");
else if (G.kind == 1) printf("无向网广度优先遍历结果如下:\n");
else if (G.kind == 2) { printf("有向图无法进行广度优先遍历\n"); return ERROR; }
else if (G.kind == 3) { printf("有向网无法进行广度优先遍历:\n"); return ERROR; }
printf("广度优先搜索结果如下\n");
for (int i = 0; i < G.vexnum; ++i) visited[i] = FALSE;
LinkQueue Q = (LinkQueue)malloc(sizeof(queue));
initQueue(Q);
for(int i = 0;i<G.vexnum;++i)
if (!visited[i]) {
visited[i] = TRUE;
printf("%c ", G.vertices[i].data);
EnQueue(Q, i);
while (!QueueisEmpty(Q)) {
int u ;
DeQueue(Q, u);
for (int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) {
if (!visited[w]) {
visited[w] = TRUE;
printf("%c ", G.vertices[w].data);
EnQueue(Q, w);
}
}
}
}
printf("\n");
return TRUE;
}
Status DFS(ALGraph& G,int i) {
visited[i] = TRUE;
printf("%c ", G.vertices[i].data);
for (int w = FirstAdjVex(G, i); w >= 0; w = NextAdjVex(G, i, w)) { //FirstAdjvex检查所有的邻节点
if (!visited[w]) DFS(G, w);
}
return TRUE;
}
Status TopologicalSort(ALGraph G) {
if (G.kind == 0) {printf("无向图无拓扑序列\n"); return ERROR;}
else if (G.kind == 1) { printf("无向网无拓扑序列\n"); return ERROR; }
else if (G.kind == 2) printf("有向图拓扑序列如下:\n");
else if (G.kind == 3) printf("有向网拓扑序列如下:\n");
int indegree[MAX_VERTEX_NUM];
FindInDegree(G, indegree);
SqStack S;
InitStack(S);
for (int i = 0; i < G.vexnum; ++i) {
if (!indegree[i]) Push(S, i);
}
int count = 0;
int i;
while (!StackEmpty(S)) {
Pop(S, i);printf("%c ", G.vertices[i].data);count++;
for (ArcNode* p = G.vertices[i].firstarc; p; p = p->nextarc) {
int k = p->adjvex;
if (!(--indegree[k]))Push(S, k);
}
}
if (count < G.vexnum)return ERROR;
else return OK;
}
Status FindInDegree(ALGraph G, int indegree[MAX_VERTEX_NUM]) {
//初始化数组，默认初始值全部为0
for (int i = 0; i < G.vexnum; i++) {
indegree[i] = 0;
}
//遍历邻接表，根据各链表中结点的数据域存储的各顶点位置下标，在indegree数组相应位置+1
for (int i = 0; i < G.vexnum; i++) {
ArcNode* p = G.vertices[i].firstarc;
while (p) {
indegree[p->adjvex]++;
p = p->nextarc;
}
}
return OK;
}
int LocateVex(ALGraph G, char v) {
for (int i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == v)
return i;
}
return -1;
}
int FirstAdjVex(ALGraph& G, int i) {
return G.vertices[i].firstarc->adjvex;
}
int NextAdjVex(ALGraph& T, int v, int w){
ArcNode* p;
p = T.vertices[v].firstarc;
while (p->adjvex != w) { p = p->nextarc; }
//找到对应行区块的后一个元素
p = p->nextarc;
if (p != NULL) return p->adjvex;
else return -1;
}
void initQueue(LinkQueue Q) {
Q->front = Q->rear = (queue)malloc(sizeof(Squeue));
Q->front->next = NULL;
}
bool QueueisEmpty(LinkQueue Q) {
if (Q->front == Q->rear) return true;
else return false;
}
void EnQueue(LinkQueue Q, ElemType x) {
queue s = (queue)malloc(sizeof(Squeue));
s->data = x;
s->next = NULL;
Q->rear->next = s;
Q->rear = s;
}
bool DeQueue(LinkQueue Q,ElemType &x) {
if (Q->front == Q->rear) return false;
queue p = Q->front->next;
x = p->data;
Q->front->next = p->next;
if (Q->rear == p) Q->rear = Q->front;
free(p);
return true;
}2.二叉树:
#define _CRT_SECURE_NO_WARNINGS
#define OK 1
#include<string>
#define ERROR 0
#include<stdio.h>
#include<stdlib.h>
using namespace std;
#include<iostream>
#define MAX_TREE_SIZE 100
typedef struct BiTNode {
char data;
struct BiTNode* lchild, * rchild;
}BiTNode, * BiTree;
void CreateBiTree(BiTree &T)
{
char ch;
scanf("%c", &ch);
if (ch == '-') T = NULL;
else {
T = (BiTNode*)malloc(sizeof(BiTNode));
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
int Visit(char e)
{
printf("%c", e);
return 1;
}
bool PreOrderTravelse(BiTree T, int Visit(char e))
{
if (T) {
if (Visit(T->data))
if (PreOrderTravelse(T->lchild, Visit)) {
if (PreOrderTravelse(T->rchild, Visit))
return OK;
}
return ERROR;
}
else return OK;
}//前序遍历
bool InOrderTravelse(BiTree T, int Visit(char e))
{
if (T) {
if (InOrderTravelse(T->lchild, Visit))
{
if (Visit(T->data))
if (InOrderTravelse(T->rchild, Visit))
return OK;
}
return ERROR;
}
else return OK;
}//中序遍历
bool PostOrderTravelse(BiTree T, int Visit(char e))
{
if (T) {
if (PostOrderTravelse(T->lchild, Visit))
{
if (PostOrderTravelse(T->rchild, Visit))
if (Visit(T->data))
return OK;
}
return ERROR;
}
else return OK;
}//后序遍历
int Coutleaf(BiTNode* T, int& num)
{
if (T)
{
if (!T->lchild && !T->rchild) num++;
Coutleaf(T->lchild, num);
Coutleaf(T->rchild, num);
}
return num;
}//计算叶子节点
int Depth(BiTree T) {
int depth, Left, Right;
if (!T)
depth = 0;
else if ((!T->lchild) && (!T->rchild)) depth = 1;
else {
Left = Depth(T->lchild);
Right = Depth(T->rchild);
depth = 1 + (Left > Right ? Left : Right);
}
return depth;
}//计算二叉树深度
//查找兄弟
void Brother(BiTree T,char e)
{
if (T) {
if ((T->lchild && T->lchild->data == e) || (T->rchild && T->rchild->data == e))
{
if (T->lchild->data == e)
cout << "兄弟为" << T->rchild->data << endl;
else if (T->rchild->data == e)
cout << "兄弟为" << T->lchild->data << endl;
}
Brother(T->lchild, e);
Brother(T->rchild, e);
}
}
void ParentX(BiTree T, char x)
{
if (T) {
if ((T->lchild && T->lchild->data == x) || (T->rchild && T->rchild->data == x))
{
cout << x << "的双亲为" << T->data << endl;
return;
}
ParentX(T->lchild, x);
ParentX(T->rchild, x);
}
}
//赫夫曼编码
typedef struct
{
int weight;
int parent, lchild, rchild;
}HTNode,*HuffmanTree;
typedef char* *HuffmanCode;
void Select(HuffmanTree& HT, int n, int &s1, int &s2)
{
s1 = 0; s2 = 0;
int w1 = 0; int w2 = 0;
for (int i = 1; i <= n; i++)
{
if (HT[i].parent == 0)
{
if (s1 == 0)
{
s1 = i;
w1 = HT[i].weight;
continue;
}
if (s2 == 0)
{
s2 = i;
w2 = HT[i].weight;
continue;
}
if (w1 > w2 && w1 > HT[i].weight)
{
w1 = HT[i].weight;
s1 = i;
continue;
}
if (w2 > w1 && w2 > HT[i].weight)
{
w2 = HT[i].weight;
s2 = i;
continue;
}
}
}
}
void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC, int* w, int n)
{
int m, i,s1,s2, start,c,f;
char *Cd;
HuffmanTree p;
if (n < 1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
for (p = HT + 1,i = 1; i <= n; i++, p++, w++)
*p = { *w,0,0,0 };
for (; i <= m; i++, p++)*p = { 0,0,0,0 };
for (i = n + 1; i <= m; i++) {
Select(HT, i - 1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
Cd = (char*)malloc(n * sizeof(char));
Cd[n - 1] = '\0';
for (i = 1; i <= n; i++) {
start = n - 1;
for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
if (HT[f].lchild == c)Cd[--start] = '0';
else Cd[--start] = '1';
HC[i] = (char*)malloc((n - start) * sizeof(char));
strcpy(HC[i], &Cd[start]);
}
free(Cd);
}3.功能实现:
#pragma once
/*
1．单链表的基本操作及应用
①创建
②插入
③删除
④查找
⑤显示
⑥通讯录设计（应用）*/
#define _CRT_SECURE_NO_WARNINGS
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define INFEASIBLE -1
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>
using namespace std;
typedef struct Lode {
char name[20];
int data;
struct Lode* next;
}LNode, * LinkList;
void CreateList(LinkList& L, int n)
{
//顺序输入n个元素的值，建立带表头指针结点的单链线性表L
LNode* p;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;//先建立一个带表头结点的单链表
for (int i = 0; i < n; i++)
{
p = (LinkList)malloc(sizeof(LNode));//生成新结点
printf("请输入联系人名字\n");
cin >> p->name;//输入名字
printf("请输入联系人号码\n");
scanf("%d", &p->data);//输入元素值
p->next = L->next;
L->next = p;
}
}//创建
void LookList_L(LinkList& L) {
LNode* p = L->next;
while (p != NULL)
{
cout << p->name << endl;//查看名字
printf(" %d\n", p->data);
p = p->next;
}
}//查看
int GetElem_L(LinkList L, string c, int &e)
{
//L为带头结点的单链表的头指针
//当第i个元素存在时，其赋值给e并返回OK，否则返回ERROR
LNode* p;
p = L->next;
while (p && (p->name != c))
{
p = p->next;
}
if (!p) return ERROR;
cout << "名字为" << c << endl;
e = p->data;
printf("电话号码为%d\n", e);
return OK;
}//查找
int ListInsert_L(LinkList& L, int i, int e, char* Name)
{
//在带头结点的单链线性表L中第i个位置之前插入元素e
Lode* p = L; int j = 0;
while (p && j < i - 1)
{
p = p->next; ++j;
}//寻找第i-1结点
if (!p || j > i - 1) return ERROR;//i小于1或者大于表长加1
LNode* s = (LinkList)malloc(sizeof(LNode));
s->data = e;
strcpy(s->name, Name);
s->next = p->next;
p->next = s;
return OK;
}//插入
int ListDelete_L(LinkList& L, int i, string Name, int& e)
{
//在头节点的单链线性表L中，删除第i个元素，并由e返回其值
Lode* p = L; int j = 0;
while (p->next && j < i - 1) {
//寻找第i个结点，并令p指向其前趋
p = p->next;
++j;
}
if (!(p->next) || j > i - 1) return ERROR;//删除位置不合理
Lode* q = p->next; p->next = q->next;
Name = q->name;
e = q->data;
cout << Name << endl;//输入名字
printf(" %d", e);
free(q);
return OK;
}//删除
/*
2．栈的基本操作及应用
①进栈
②出栈
③取栈顶元素
④表达式的求解（应用）*/
typedef struct {
int* top;//栈顶指针
int* base;
int stacksize;//当前已分配的内存空间，以元素为单位
}SqStack;
//构造一个空栈
int InitStack(SqStack& S)
{
S.base = (int*)malloc(STACK_INIT_SIZE * sizeof(int));
if (!S.base)exit(OVERFLOW);// 内存分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
bool StackEmpty(SqStack S) {
//判断栈顶与栈底是否相等
if (S.top == S.base)
return OK;
else
return ERROR;
}//判断栈空
//返回栈顶元素函数
int GetTop(SqStack S, int& e) {
//若栈不空，则用e返回s的栈顶元素，并返回OK，否则返回ERROR
if (S.top == S.base)return(OVERFLOW);
e = *(S.top - 1);//输出下一个数
printf("%d", e);
return OK;
}//查找
int Push(SqStack& S, int e) {
//插入元素e
//当栈满
if (S.top - S.base >= S.stacksize) {
//追加栈容量
S.base = (int*)realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(int));
if (!S.base)exit(OVERFLOW);//存储分配失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
//当栈没满
*S.top++ = e;
return OK;
}//插入
//出栈顶元素
int Pop(SqStack& S, int& e)
{
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回Ok，否则返回ERROR
if (S.top == S.base)exit(OVERFLOW);
e = *--S.top;
printf("%d", e);
return OK;
}
//表达式求值
4.压缩矩阵:
#include<stdio.h>
#include<iostream>
using namespace std;
#define MAXSIZE 12500
typedef int Elemtype;
typedef int Status;
typedef struct {
int i, j;
Elemtype e;
}Triple;
typedef struct {
Triple data[MAXSIZE + 1];
int mu, nu, tu;
}Tsmaxtrix;
Status TransposeSMatrix(Tsmaxtrix M, Tsmaxtrix& T) {
T.mu = M.mu;
T.nu = M.nu;
T.tu = M.tu;
int q = 1;
if (T.tu) {
for (int col = 1; col <= M.nu; col++)
for (int p = 1; p <= M.tu; p++) {
if (M.data[p].j == col) {
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
q++;
}
}
}
q = 1;
printf("转置后的矩阵T用三元组表表示为：\n");
for (q; q <= T.tu; q++)
cout << "(" << T.data[q].i << "," << T.data[q].j << "," << T.data[q].e << ")" << endl;
return 0;
}
/*
int main()
{
int mu, nu, tu = 0, i, j, n = 1;
int p = 1, q;
int a[20][30];
Tsmaxtrix M, T;
M.data[1000];
printf("请输入行数及列数mu，nu:\n");
scanf_s("%d,%d", &mu, &nu);
M.mu = mu;
M.nu = nu;
printf("请输入稀疏矩阵：\n");
for (i = 1; i <= mu; i++)
for (j = 1; j <= nu; j++) {
scanf_s("%d", &a[i][j]);
if (a[i][j] != 0) {
tu++;
}
}
M.tu = tu;
printf("该稀疏矩阵为：\n");
for (i = 1; i <= mu; i++)
for (j = 1; j <= nu; j++) {
printf("%2d", a[i][j]);
if (n % nu == 0) {
printf("\n");
}
n++;
}
for (i = 1; i <= mu; i++)
for (j = 1; j <= nu; j++) {
if (a[i][j] != 0) {
M.data[p].e = a[i][j];
M.data[p].i = i;
M.data[p].j = j;
p++;
}
continue;
}
printf("该稀疏矩阵用三元组表表示为：\n");
p = 1;
for (p; p <= tu; p++) {
cout << "(" << M.data[p].i << "," << M.data[p].j << "," << M.data[p].e << ")" << endl;
}
TransposeSMatrix(M, T);
}
*/
5.操作目录:
#pragma once
#include"二叉树.h"
#include"功能实现.h"
#include"压缩矩阵.h"
#include"图的操作.h"
void ShowMainMenu() {
printf("\n");
printf("*******************算法与数据结构******************\n");
printf("* 1 单链表的基本操作及应用 *\n");
printf("* 2 栈的基本操作及应用 *\n");
printf("* 3 数组的基本操作及应用 *\n");
printf("* 4 树的基本操作及应用 *\n");
printf("* 5 图的基本操作及应用 *\n");
printf("* 6 退出 *\n");
printf("***************************************************\n");
}
void LinkListmanu() {
int n;
LinkList L;
L = NULL;
do {
printf("\n");
printf("**************单链表的基本操作及应用***************\n");
printf("* 1 创建联系人 *\n");
printf("* 2 插入联系人 *\n");
printf("* 3 删除联系人 *\n");
printf("* 4 查找 *\n");
printf("* 5 显示 *\n");
printf("* 7 退出 *\n");
printf("*************************************************** \n");
printf("请选择：");
scanf("%d", &n);
int i, e = 0;
char Name[20];
switch (n) {
case 1:
printf("--------创建联系人---------");
printf("输入要创建的长度\n");
scanf("%d", &i);
CreateList(L, i);
break;
case 2:
printf("--------插入信息-------");
printf("输入插入的位序\n");
scanf("%d", &i);
printf("输入插入的名字\n");
cin >> Name;
printf("输入插入的号码\n");
cin >> e;
ListInsert_L(L, i, e, Name);
break;
case 3:
printf("--------删除信息-------");
printf("输入要删除的位序\n");
scanf("%d", &i);
ListDelete_L(L, i, Name, e);
break;
case 4:
printf("--------查找信息-------");
printf("输入要查找的名字\n");
cin >> Name;
GetElem_L(L, Name, e);
break;
case 5:
printf("--------显示通讯录-------");
LookList_L(L);
break;
case 6:
printf("--------通讯录---------"); break;
case 7: break;
default:
printf("ERROR!"); break;
}
} while (n != 7);
}
void Stack() {
int n;
SqStack S; InitStack(S);
do {
printf("\n");
printf("****************栈的基本操作及应用*****************\n");
printf("* 1 进栈 *\n");
printf("* 2 出栈 *\n");
printf("* 3 取栈顶元素 *\n");
printf("* 4 表达式求解（应用） *\n");
printf("* 5 退出 *\n");
printf("***************************************************\n");
printf("请选择：");
scanf("%d", &n);
int e,i,number=10;
switch (n) {
case 1:
printf("--------进栈-------\n");
printf("请输入入栈的数量\n");
scanf("%d", &number);
for (int i = 0; i < number; i++)
{
printf("输入数字\n");
scanf("%d", &e);
Push(S, e);
}
break;
case 2:
printf("--------出栈-------\n");
while (!StackEmpty(S)) {
Pop(S, e);
}
break;
case 3:
printf("--------取栈顶元素-------\n");
GetTop(S, e);
break;
case 4:
printf("--------表达式求值-------");
break;
case 5:break;
default:
printf("ERROR!"); break;
}
} while (n != 5);
}
void Array() {
int n;
int mu, nu, tu = 0, i, j, number = 1;
int p = 1, q;
int a[20][30];
Tsmaxtrix M, T;
M.data[1000];
do {
printf("\n");
printf("*************稀疏矩阵的压缩存储及应用**************\n");
printf("* 1 创建 *\n");
printf("* 2 显示 *\n");
printf("* 3 矩阵乘法（应用） *\n");
printf("* 4 退出 *\n");
printf("***************************************************\n");
printf("请选择：");
scanf("%d", &n);
switch (n) {
case 1:
printf("---------创建-------");
printf("请输入行数及列数mu，nu:\n");
scanf_s("%d,%d", &mu, &nu);
M.mu = mu;
M.nu = nu;
printf("请输入稀疏矩阵：\n");
for (i = 1; i <= mu; i++)
for (j = 1; j <= nu; j++) {
scanf_s("%d", &a[i][j]);
if (a[i][j] != 0) {
tu++;
}
}
M.tu = tu;
break;
case 2:
printf("---------显示-------");
printf("该稀疏矩阵为：\n");
for (i = 1; i <= mu; i++)
for (j = 1; j <= nu; j++) {
printf("%2d", a[i][j]);
if (number % nu == 0) {
printf("\n");
}
n++;
}
for (i = 1; i <= mu; i++)
for (j = 1; j <= nu; j++) {
if (a[i][j] != 0) {
M.data[p].e = a[i][j];
M.data[p].i = i;
M.data[p].j = j;
p++;
}
continue;
}
printf("该稀疏矩阵用三元组表表示为：\n");
p = 1;
for (p; p <= tu; p++) {
cout << "(" << M.data[p].i << "," << M.data[p].j << "," << M.data[p].e << ")" << endl;
}
TransposeSMatrix(M, T);
break;
case 3:
printf("---------矩阵乘法-------"); break;
case 4:break;
default:
printf("ERROR!"); break;
}
} while (n != 4);
}
void BiTreefunction() {
int n;
BiTree T=NULL;
char e,x;int num=0;
HuffmanTree HT; HuffmanCode HC; int number=4; int* w;
int weight[20] = { 1,2,3,4 };
w = weight;
char a[] = { 'a','b','c','d' };
do {
printf("\n");
printf("**************二叉树的基本操作及应用***************\n");
printf("* 1 创建二叉树 *\n");
printf("* 2 遍历二叉树（先/中/后） *\n");
printf("* 3 计算树的深度 *\n");
printf("* 4 计算叶子结点个数 *\n");
printf("* 5 查找双亲 *\n");
printf("* 6 查找兄弟 *\n");
printf("* 7 Huffman编码（应用） *\n");
printf("* 8 退出\n");
printf("***************************************************\n");
printf("请选择：");
scanf("%d", &n);
switch (n) {
case 1:
printf("---------创建二叉树--------\n");
getchar();
CreateBiTree(T);
break;
case 2:
printf("---------*遍历二叉树-------");
PreOrderTravelse(T, Visit);
break;
case 3:
printf("---------计算树的深度------");
cout << "二叉树深度为"<<Depth(T)<<endl;
break;
case 4:
printf("---------计算叶子结点个数-------");
cout << "叶子节点个数为" << Coutleaf(T, num) << endl;
break;
case 5:
printf("---------查找双亲-------");
printf("输入双亲\n");
getchar();
scanf("%c", &x);
ParentX(T, x);
break;
case 6:
printf("---------查找兄弟-------");
printf("输入要查找的孩子\n");
getchar();
scanf("%c", &e);
Brother(T, e);
break;
case 7:
printf("---------Huffman编码-------\n");
HuffmanCoding(HT,HC,w, number);
for (int i = 1; i <= 4; i++) {
cout << a[i - 1] << " " << HC[i] << endl;
}
break;
case 8:break;
default:
printf("ERROR!"); break;
}
} while (n != 8);
}
void Graphfuction() {
int select;
ALGraph G;
do {
printf("\n");
printf("****************图的基本操作及应用*****************\n");
printf("* 1 创建无向图 *\n");
printf("* 2 创建无向网 *\n");
printf("* 3 创建有向图 *\n");
printf("* 4 创建有向网 *\n");
printf("* 5 遍历 *\n");
printf("* 6 拓扑排序 *\n");
printf("* 7 最小生成树（应用） *\n");
printf("* 8 最短路径（应用） *\n");
printf("* 9 关键路径（应用） *\n");
printf("* 10 退出 *\n");
printf("***************************************************\n");
printf("请选择：");
scanf("%d", &select);
switch (select) {
case 1:
printf("---------创建无向图-------\n");
if (CreateGraph(G, select - 1)) printf("构造成功!\n");
else printf("构造失败!\n");
system("pause");
break;
case 2:
printf("---------创建无向网-------\n");
if (CreateGraph(G, select - 1)) printf("构造成功!\n");
else printf("构造失败!\n");
system("pause");
break;
case 3:
printf("---------创建有向图-------\n");
if (CreateGraph(G, select - 1)) printf("构造成功!\n");
else printf("构造失败!\n");
system("pause");
break;
case 4:
printf("---------创建有向网-------\n");
if (CreateGraph(G, select - 1)) printf("构造成功!\n");
else printf("构造失败!\n");
system("pause");
break;
case 5:
printf("---------遍历-------\n");
printf("邻接表显示如下:\n");
ShowGraph(G);
Depth_First_Search(G);
Broadth_First_Search(G);
system("pause");
break;
case 6:
printf("---------拓扑排序-------");
TopologicalSort(G);
system("pause");
break;
case 7:
printf("---------最小生成树-------"); break;
case 8:
printf("---------最短路径-------"); break;
case 9:
printf("---------关键路径-------"); break;
case 10:break;
default:
printf("ERROR!"); break;
}
} while (select != 10);
}
void main() {
int n;
do {
ShowMainMenu();
printf("请选择：");
scanf("%d", &n);
switch (n) {
case 1:LinkListmanu(); break;
case 2:Stack(); break;
case 3:Array(); break;
case 4:BiTreefunction(); break;
case 5:Graphfuction(); break;
case 6:break;
default:printf("ERROR!"); break;
}
} while (n != 6);
}