线性表
1. 对链表设置头结点的作用是什么？
【解答】其好处有:
const的作用(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。
(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
2. 建立单链表的常用方法
【解答】建立单链表的常用方法有两种。下面以顺序存储为例来叙述。
(1) 头插法建表
该方法从一个空表开始，读取数组a中的字符，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止。算法如下：
void CreateListF(Snode *&L, ElemType a[], int n)
{ Snode *s; int i;
L = (Snode *) malloc(sizeof(Snode));
L->next = NULL;
for (i=0; i<n;i++)
{ s = (Snode *)malloc(sizeof(Snode));
s->data = a[i];
s->next = L->next;
L->next = s;
}
}
(2) 尾插法建表
头插法建立链表虽然算法简单，但生成的链表中结点的次序和原数组元素的顺序相反，若希望两者次序一致，可采用尾插法。该方法是将新结点插到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾结点。算法如下：
void CreateListR(Snode *&L, ElemType a[], int n)
{ Snode *s, *r; int i;
L = (Snode *) malloc(sizeof(Snode));
L->next = NULL;
r = L;
for (i=0; i<n;i++)
{ s = (Snode *)malloc(sizeof(Snode));
s->data = a[i];
r->next = s;
r = s;
}
r-> next = NULL;
}
栈
1.试证明：若借助栈可由输入序列1, 2, 3, …, n得到一个输出序列p1, p2, p3, …, pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i < j < k，使得pj < pk < pi.
【解答】因为借助栈由输入序列1, 2, 3, …, n，可得到输出序列p1, p2, p3, …, pn ，如果存在下标i, j, k，满足i < j < k，那么在输出序列中，可能出现如下5种情况:
i进栈,i出栈,j进栈,j出栈,k进栈,k出栈.此时具有最小值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最大值的排在pk位置，有pi < pj < pk, 不可能出现pj < pk < pi的情形;
i进栈,i出栈,j进栈,k进栈,k出栈,j出栈.此时具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中间值的排在最后pk位置，有pi < pk < pi , 不可能出现pj, pk < pi的情形;
i进栈,j进栈,j出栈,i出栈,k进栈,k出栈.此时具有中间值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj < pi < pk, 不可能出现pj < pk < pi的情形;
i进栈,j进栈,j出栈,k进栈,k出栈,i出栈.此时具有中间值的排在最前面pi 位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk < pi < pj, 也不可能出现pj < pk < pi的情形;
i进栈,j进栈,k进栈,k出栈,j出栈,i出栈.此时具有最大值的排在最前面pi 位置，具有中间值的排在其后pj位置，具有最小值的排在pk位置，有pk < pj < pi, 也不可能出现pj < pk F)
2 设计一个算法，利用栈的基本运算返回指定栈中栈底元素。
【解答】假定采用顺序栈结构。先退栈st中所有元素，利用一个临时栈tmpst存放st栈退出的元素，最后的一个元素即为所求，然后将临时栈中的元素逐一出栈并进栈到st中，这样恢复st 栈中原来的元素。算法如下：
ElemType bottom(Stack st)
{ ElemType x,y;
Stack tmpst;
InitStack(tmpst);
while (!StackEmpty(st))
{ pop(st,x);
push(tmpst,x);
}
while (!StackEmpty(tmpst))
{ pop(tmpst,y);
push(st,y);
}
return x;
}
队列
1. 何为队列上溢现象？何为假溢现象？有哪些解决方法？并分别简述其工作原理。
【解答】在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队的容量为MaxSize。当有元素要加入队列时，若rear=MaxSize（初始时rear=0），则发生队列的上溢现象，该元素不能加入队列。
队列的假溢出现象是指队列中还有空余的空间，但元素不能进队列。造成这种现象的原因是由于队列的操作方式所致。
解决队列假溢出的方法如下：
（1）建立一个足够大的存储空间，但这样做会造成空间浪费。
（2）采用环形队列方式。
（3）采用平移元素的方法，当删除一个对头元素时，依次移动队中的元素，始终使front指向队列中的第一个位置。
2. 若使用循环链表来表示队列,p是链表中的一个指针.试基于此结构给出队列的插入(enqueue)和删除(dequeue)算法，并给出p为何值时队列空.
【解答】
链式队列的类定义
template class Queue; //链式队列类的前视定义
template class QueueNode { //链式队列结点类定义
friend class Queue;
private:
Type data; //数据域
QueueNode *link; //链域
QueueNode ( Type d = 0, QueueNode *l = NULL ) : data (d), link (l) { } //构造函数};
template class Queue { //链式队列类定义
public:
Queue ( ) : p ( NULL ) { } //构造函数
~Queue ( ); //析构函数
void EnQueue ( const Type & item ); //将item加入到队列中
Type DeQueue ( ); //删除并返回队头元素
Type GetFront ( ); //查看队头元素的值
void MakeEmpty ( ); //置空队列，实现与~Queue ( ) 相同
int IsEmpty ( ) const { return p == NULL; } //判队列空否
private:
QueueNode *p; //队尾指针(在循环链表中)
};
template Queue::~Queue ( ) { //队列的析构函数
QueueNode *s;
while ( p != NULL ) { s = p; p = p→link; delete s; } //逐个删除队列中的结点
}
//队列的插入函数
template void Queue::EnQueue ( const Type & item ) {
if ( p == NULL ) { //队列空, 新结点成为第一个结点
p = new QueueNode ( item, NULL ); p→link = p;
}
else { //队列不空, 新结点链入p之后
QueueNode *s = new QueueNode ( item, NULL );
s→link = p→link; p = p→link = s; //结点p指向新的队尾
}
}
//队列的删除函数
template Type Queue::DeQueue ( ) {
if ( p == NULL ) { cout << "队列空, 不能删除!" << endl; return 0; } QueueNode *s = p; //队头结点为p后一个结点
p→link = s→link; //重新链接, 将结点s从链中摘下
Type retvalue = s→data; delete s; //保存原队头结点中的值, 释放原队头结点return retvalue; //返回数据存放地址
}
//队空条件 p == NULL.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。