UC知道算法与数据结构问题（C语言）
来源：百度知道 编辑：UC知道 时间：2024/05/14 07:54:12
1.扩充抽象数据类型栈的定义，增加如下运算：
（1）StackSplit（S1,S2):将栈S1分为大小相同的2个栈S1和S2。栈S2中含原栈S1中上半部分元素，其余元素留在栈S1中。
（2）StackCombine（S1,S2)：将栈S2中元素合并于栈S1顶部，且保持原栈中元素次序。S2成为空栈。
用数组实现上述扩充后的栈。
2.用指针实现栈的方法重做第1题。
3.如果用一个布尔量来表示循环数组中的队列是否为空队列，那么应当如何定义这种队列结构的类型？写出在这种表示法下实现队列的基本运算。
（1）StackSplit（S1,S2):将栈S1分为大小相同的2个栈S1和S2。栈S2中含原栈S1中上半部分元素，其余元素留在栈S1中。
（2）StackCombine（S1,S2)：将栈S2中元素合并于栈S1顶部，且保持原栈中元素次序。S2成为空栈。
用数组实现上述扩充后的栈。
2.用指针实现栈的方法重做第1题。
3.如果用一个布尔量来表示循环数组中的队列是否为空队列，那么应当如何定义这种队列结构的类型？写出在这种表示法下实现队列的基本运算。
1.首先要说明栈的存贮表示：
typedef struct
{
int *base;
int *top;//站顶指针
int stacksize;//当前已分配存贮空间；
int n;//栈中已存贮元素个数；
}SqStack;
假设S1,S2是已经开辟了存贮空间的两个栈，S1中存贮有元素，则StackSplit（S1,S2)可这样实现：
void StackSplit（&S1,&S2)
{
int e;
S2.top=S2.base;//将S2置空
for(int i=0;i<=(S1.n)/2;i++)
{
e=*--S1.top;//取S1栈顶元素
*S2.top++=e;//插入S2
}
}
2.同样要先定义存贮结构：
typedef struct Snode
{
int data;
Stack next;
}SNode,*Stack;//单位存储结构
typedef struct
{
Stack base;
Stack top;//栈顶指针
int n;//栈中已存储元素个数；
}SqStack;
StackSplit（S1,S2)可这样实现：
void StackSplit（S1,S2)
{
Stack e;
S2.top=S2.base;//将S2置空
for(int i=0;i<=(S1.n)/2;i++)
{
e=S1.top;//保存S1栈顶元素
S1.top=S1.top->next;//退栈
e.next=S2.top;
S2