4-13.c

数据结构经典算法一书源代码和习题解答实现代码。

#include "stdio.h"
#include "iostream.h"
#include "string.h"
#define StackSize 100 //假定预分配的栈空间最多为100个元素 
#define MaxLength  100// 最大的字符串长度 	
typedef int DataType;//假定栈元素的数据类型为整数 	
typedef struct{
      DataType data[StackSize];
      int top;
}SeqStack;   
// 置栈空
void Initial(SeqStack *S)
{//将顺序栈置空
      S->top=-1;
} 
//判栈空
int IsEmpty(SeqStack *S)
{
    return S->top==-1;
}
//判栈满
int IsFull(SeqStack *S)
{
	return S->top==StackSize-1;
}
//进栈
void Push(SeqStack *S,DataType x)
{
    if (IsFull(S))
	{
		printf("栈上溢"); //上溢,退出运行
		exit(1);
	}
    S->data[++S->top]=x;//栈顶指针加1后将x入栈
}
//出栈
DataType Pop(SeqStack *S)
{
	if(IsEmpty(S))
	{
		printf("栈为空"); //下溢,退出运行
		return -1;
	}
	return S->data[S->top--];//栈顶元素返回后将栈顶指针减1
}
// 取栈顶元素
DataType Top(SeqStack *S)
{
	if(IsEmpty(S))
	{
		printf("栈为空"); //下溢,退出运行
		exit(1);
	}
	return S->data[S->top];
}
int CheckBox(int net[ ], int n)
{// 确定开关盒是否可布线
	SeqStack *s = malloc(sizeof(SeqStack)*n);
	int x;
	//顺时针扫描各网组
	for (int i = 0; i < n; i++) {
	//检查n e t [ i ]
		if (!IsEmpty(s) ) {
			if (net[i]==net[s->Top()] ) {
	// net[i] 可布线，从堆栈中删除
				x=Pop(s);
			}
			else 
				Push(s,i); 
		}
		else Push(s,i);
	}
	// 是否有不可布线的网组?
	if (IsEmpty(s)) {
		free(s);
		printf("Switch box is routable\n");
		return 1;
	}
	free(s);
	printf("Switch box is not routable");
	return 0;
}

void main(void)
{
	int net[8];
	//net[8]赋值
	int succ=CheckBox(net,8);
}