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

第2章作业参考答案1. B2. A，D3. 1，n/2，(n-1)/2，n，0，04.templete <class ElemType>void SqList <ElemType> :: reverse(){ElemType e;for (int i = 0; i < len / 2; i++){e = elem[i];elem[i] = elem[len – i -1];elem[len – i – 1] = e;}}templete <class ElemType>void LinkList <ElemType> :: reverse(){if (!head->next) return;LinkNode <ElemType> *q = head -> next, *p = q -> next;q -> next = NULL;tail = q;while (p){q = p;p = p –> next;q –> next = head -> next;head -> next = q;}}8.void add(LinkList <Monomial> &pa, LinkList <Monomial> &pb) {int pa_len, pb_len, i, j;pa_len = pa.Length();pb_len = pb.Length();i = j = 1;Monomial pa_e, pb_e;pa.GetElem(pa_e, 1);pb.GetElem(pb_e, 1);while (i <= pa_len && j <= pb_len){if (pa_e.exp < pb_e.exp){i++;if (i <= pa_len) pa.GetElem(pa_e, i);}else if (pa_e.exp > pb_e.exp){pa.Insert(pb_e, i);i++;pa_len++;j++;if (j <= pb_len) pb.GetElem(pb_e, j);}else{if (pa_e.coef += pb_e.coef){pa.SetElem(pa_e, i);i++;}else{pa.Delete(pa_e, i);pa_len--;}j++;if (i <= pa_len) pa.GetElem(pa_e, i);if (j <= pb_len) pb.GetElem(pb_e, j);}}while (j <= pb_len){pb.GetElem(pb_e, j++);pa.Append(pb_e);}}第3章作业参考答案1.1,4,3,5,2)能，IOIIIOOIOO；(1,4,2,3,5)不能，因为4先于3和2出栈，4出栈时，2和3都在栈中，且2压在3之下，故只能3先出栈才能2出栈。

*若借助栈由输入序列1,2, … , n得到输出序列为p1, p2, …, p n，则在输出序列中不可能出现这样的情形：存在着i<j<k使p j<p k<p i。

2. 借助栈T，删除栈S中元素值为k的元素。

4.//定义双向栈类template <class ElemType>//声明一个类模板class DSqStack{public: //双向栈类的各成员函数DSqStack(int m = 100);~DSqStack();bool Empty(int i) const;ElemType & Top(int i) const;void Push(const ElemType &e,int i);void Pop(int i);private: //双向栈类的数据成员ElemType *base; //基地址指针int top[2]; //栈顶指针int size; //向量空间大小};//构造函数，分配m个结点的顺序空间，构造一个空的双向栈。

template <class ElemType>DSqStack <ElemType>::DSqStack(int m){top[0] = -1;top[1] = m;base = new ElemType[m];size = m;}//DSqStack//析构函数，将栈结构销毁。

template <class ElemType>DSqStack <ElemType>::~DSqStack(){if (base != NULL) delete[] base;}//~SqStack//判栈是否为空，若为空，则返回true，否则返回false。

template <class ElemType>bool DSqStack <ElemType>::Empty(int i) const{//i的取值为0或1if (i == 0)return top[0] == -1;elsereturn top[1] == size;}//Empty//取栈顶元素的值。

先决条件是栈不空。

template <class ElemType>ElemType & DSqStack <ElemType>::Top(int i) const{//i的取值为0或1return base[top[i]];}//Top//入栈，若栈满，则先扩展空间。

插入e到栈顶。

template <class ElemType>void DSqStack <ElemType>::Push(const ElemType &e, int i) {//i的取值为0或1if (top[0] == top[1] - 1){ //若栈满，则扩展空间。

ElemType *newbase;newbase = new ElemType[size + 10];for(int j = 0; j <= top[0]; j++)newbase[j] = base[j];for(int k = size - 1; k >= top[1]; k--)newbase[k + 10] = base[k];delete[] base;base = newbase;size += 10;top[1] += 10;}if (i == 0)base[++top[0]] = e;elsebase[--top[1]] = e;}//Push//出栈，弹出栈顶元素。

先决条件是栈非空。

template <class ElemType>void DSqStack <ElemType>::Pop(int i){//i的取值为0或1if (i == 0)top[0]--;elsetop[1]++;}//Pop5.(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++;elses--;if (s < 0) return false;}return true;}7. 借助队列q0和q1，将队列Q中的元素重新排列：奇数值元素在前，偶数值元素在后。

8.类型定义：typedef struct QNode {QElemType data;struct QNode *next;} QNode, * QLink;template <class ElemType>//声明一个类模板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 <class ElemType>CycLinkQueue <ElemType>:: CycLinkQueue(){m_rear = new QNode <ElemType>;m_rear->next = m_rear;}(2)//入队void CycLinkQueue <ElemType>::Append(const ElemType &e){QNode < ElemType > *p;p = new QNode <ElemType>;p->data = e;p->next = m_rear->next;m_rear->next = p;m_rear = p;}(3)//出队。

先决条件是队列不空。

template <class ElemType>void CycLinkQueue <ElemType>::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 ElemType>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个结点的顺序空间，构造一个空的循环队列。