数据结构实用教程课后习题答案万健C++

void DSqStack ::Pop(int i) {//i的取值为0或1 if (i == 0) top[0]--; else top[1]++; }//Pop 5.

(1). A, C, D

(2). 从左到右读序列，任何时候累计I的个数都应大于等于O的个数。 (3).

bool islegal(char *a) {

int s = 0, n = strlen(s); for (int i = 0; i < n; i++) {

if (a[i] == “I”) s++; else s--;

if (s < 0) return false; }

return true; }

7. 借助队列q0和q1，将队列Q中的元素重新排列：奇数值元素在前，偶数值元素在后。 8.

类型定义：

typedef struct QNode {

QElemType data; struct QNode *next; } QNode, * QLink;

template //声明一个类模板 class CycLinkQueue {

public: //循环链表队列的各成员函数 CycLinkQueue (); //~CycLinkQueue (); //void Clear(); //bool Empty() const; //int Length() const;

//ElemType & GetHead() const; //ElemType & GetLast() const; void Append(const ElemType &e); void Remove(); private:

QNode < ElemType > *m_rear; //队尾指针 }; (1)

//构造函数，构造一个空的循环链队列。 template

CycLinkQueue :: CycLinkQueue() { m_rear = new QNode ; m_rear->next = m_rear; } (2)

//入队

void CycLinkQueue ::Append(const ElemType &e) { QNode < ElemType > *p; p = new QNode ; p->data = e;

p->next = m_rear->next; m_rear->next = p; m_rear = p; } (3)

//出队。先决条件是队列不空。 template

void CycLinkQueue ::Remove() { QNode < ElemType > *p = m_rear->next->next; m_rear->next->next = p->next; if (p == m_rear)

m_rear = m_rear->next; //若出队后队列为空，需修改m_rear。 delete p; } 9.

template class SqQueue {

public: //循环队列的各成员函数

SqQueue(int m = 100); //~SqQueue(); //void Clear(); //bool Empty() const; //int Length() const;

//ElemType & GetHead() const; //ElemType & GetLast() const; void Append(const ElemType &e); void Remove();

private: //循环队列类的数据成员 ElemType *m_base; //基地址指针 int m_front; //队头指针 int m_length; //队列长度 int m_size; //向量空间大小 };

//构造函数，分配m个结点的顺序空间，构造一个空的循环队列。 template

SqQueue ::SqQueue(int m) { m_front = m_length = 0; m_base = new ElemType[m]; m_size = m; }//SqQueue

//入队，插入e到队尾。 template

void SqQueue ::Append(const ElemType &e) { int j, k;

if (m_length == m_size) { //队满，则扩展空间。 ElemType *newbase;

newbase = new ElemType[m_size + 10];

for(j = m_front, k = 0; k < m_length; j = (j + 1) % m_size, k++) newbase[k] = m_base[j]; delete[] m_base; m_base = newbase; m_front = 0; m_size += 10; }

m_base[(m_front + m_length) % m_size] = e; m_length++; }//Append

//出队。先决条件是队列不空。 template

void SqQueue ::Remove() { m_front = (m_front + 1) % m_size; m_length--; }//Remove 10.

Length(s)的结果为14 sub1的值为”I am a “ Index(s,”a”,4)的结果为6 s的值为”I am a worker” sub3的值为”goodworker” sub3的值为”good worker” 11. (1) 288 (2) 1282 (3) 1180 (4) 1234 12.

(1) k=2i+j-3

(2) i=?(k+1)/3?+1，j=i+(k+1)%3-1 15.

(1) (a, b) (2) ( ) (3) (b) (4) b (5) (d) 16. （略）

(i用前式代入即可)