目录
第三章:栈和队列(刷题记录)P[48-49]
第一题:2022年4月15日 星期五 晚上19:20 - 19:35
第三章:栈和队列(刷题记录)
P[48-49]
第一题:2022年4月15日 星期五 晚上19:20 - 19:35
【算法思想】
两栈共享向量空间,将两栈栈底设在向量两端,初始时,左栈顶指针为-1,右栈顶为m。两栈顶指针相邻时为栈满。两栈顶相向增长,栈顶指针指向栈顶元素。左栈是通常意义下的栈,在进栈操作时,其栈顶指针右移(加1),出栈时,栈顶指针左移(减1)。而右栈进栈操作时,其栈顶指针左移(减1),出栈时,栈顶指针右移(加1)。
【算法描述】
typedef struct{
int top[2], bot[2]; //栈顶和栈底指针
ElemType* V; //栈数组
int m; //栈最大可容纳元素个数
}DblStack; //两栈类型
//1
Status InitDblStack(DblStack& S, int m)
{//初始化一个大小为m的双向栈s
S.V = new ElemType[m]; //动态分配一个最大容量为m的数组空间
S.bot[0] = -1; //左栈栈底指针
S.bot[1] = m; //右栈栈底指针
S.top[0] = -1; //左栈栈顶指针
S.top[1] = m; //右栈栈顶指针
return 0;
}
Status DblPush(DblStack S, int i,int x)
{//向指定的i号栈中插入元素x
if (S.top[i] - S.top[0] == 1)
{
return ERROR;
}
if (i == 0)
{
S.V[++S.top[0]] = x; //左栈;栈顶指针先加1,然后按照此地址进栈
}
else
{
S.V[--S.top[1]] = x; //左栈;栈顶指针先加1,然后按照此地址进栈
}
}
Status DblPop(DblStack& S, int i, ElemType& x)
{//删除指定的i号栈的栈顶元素,用x返回其值
if (S.top[i]==S.top[i]) //栈空
{
return ERROR;
}
if (i == 0)
{
x = S.V[S.top[0]--]; //左栈;栈顶指针减1
}
else
{
x = S.V[S.top[0]++]; //左栈;栈顶指针加1
}
return OK;
}
int IsEmpty(DblStack S, int i)
{//判断指定的i号栈是否为空,空返回1,否则返回0
return (S.top[i] == S.bot[i]);
}
int IsFull(DblStack S)
{//判断栈是否满,满则返回1,否则返回0
if (S.top[0] + 1 == S.top[1])
{
return 1;
}
else
{
return 0;
}
}
//测试
int main()
{
int m; //双向栈的元素个数
int i; //栈号
ElemType x; //元素
cout << "可以运行啊!nice啊!";
cout << endl;
DblStack S;
cout << "请输入双向栈的元素个数:";
cin >> m;
if (InitDblStack(S, m))
{
cout << "初始化成功!" << endl;
}
cout << "初始化栈" << endl;
cout << "向第几号栈添加元素:";
cin >> i;
for (int j = 0; j < m/2; j++)
{
cout << "将第" << j << "个元素入栈"<<i<<"中: ";
cin >> x;
DblPush(S, i, x);
}
cout << "删除第几号栈顶元素:";
cin >> i;
if (DblPop(S, i, x))
{
cout << "删除成功!";
}
else
{
cout << "删除失败!";
}
cout << "判断第几号栈是否为空:";
cin >> i;
if (IsEmpty(S,i))
{
cout << "栈为空!"<<endl;
}
else
{
cout << "栈不为空!"<<endl;
}
cout << "判断当前栈是否为满:";
if (IsFull(S))
{
cout << "栈已满!";
}
else
{
cout << "栈未满!";
}
cout << endl;
cout << "20213002624李季鸿代码";
system("pause");
return 1;
}
第二题:2022年5月10日 星期二 晚上20:10 - 20:30
【算法思想】
将字符串前一半入栈,然后,栈中元素和字符串后一半进行比较。即将第一个出栈元素和后一半串中第一个字符比较,若相等,则再出栈一个元素与后一个字符比较,以此类推,直至栈空,在这种情况下可判定该字符序列是回文。如果出栈元素与串中的字符进行比较时出现不等的情况,则可判定该字符序列不是回文。
【算法描述】
int IsPalindrome(char* t)
{//判断t字符向量是否为回文,若是,返回1,否则返回0
int i;
char temp,e;
SqStack S;
InitStack(S);
int len = strlen(t); //求向量的长度
for ( i = 0; i < len / 2; i++)
{//将一半字符入栈
Push(S, t[i]);
}
if (len % 2 != 0)
{
i++; //长度为奇数,跳过中间字段
}
while (!StackEmpty(S))
{//每弹出一个字符与相应字符比较
temp = Pop(S,e);
if (temp != t[i])
{
return 0; //不等则返回0
}
else
{
i++;
}
}
return 1; //比较完毕均相等则返回1
}
由于第三题实在没有含金量,就不写了。
第三题:2022年5月10日 星期二 晚上20:25 - 20:40
【算法思想】
根据ai的值判断进行入栈或者出栈操作,入栈前首先判断是否栈满,出栈前先判断是否栈空,
随后再进行相关操作。
【算法描述】
(持续更新中。。。。。。)