发布时间 : 2024/5/5 2:37:47 星期日 文章数据结构实用教程课后习题答案万健C++更新完毕开始阅读5f0c822965ec102de2bd960590c69ec3d5bbdb3c

第2章作业参考答案

1. B

2. A，D

3. 1，n/2，(n-1)/2，n，0，0 4.

templete

void SqList :: 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

void LinkList :: reverse() {

if (!head->next) return;

LinkNode *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 &pa, LinkList &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, …, pn，则在输出序列中不可能出现这样的情形：存在着i

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

//定义双向栈类

template //声明一个类模板 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

DSqStack ::DSqStack(int m) { top[0] = -1; top[1] = m; base = new ElemType[m]; size = m; }//DSqStack

//析构函数，将栈结构销毁。 template

DSqStack ::~DSqStack() { if (base != NULL) delete[] base;

}//~SqStack

//判栈是否为空，若为空，则返回true，否则返回false。 template

bool DSqStack ::Empty(int i) const {//i的取值为0或1 if (i == 0) return top[0] == -1; else return top[1] == size; }//Empty

//取栈顶元素的值。先决条件是栈不空。 template

ElemType & DSqStack ::Top(int i) const {//i的取值为0或1 return base[top[i]]; }//Top

//入栈，若栈满，则先扩展空间。插入e到栈顶。 template

void DSqStack ::Push(const ElemType &e, int i) {//i的取值为0或1

if (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; else base[--top[1]] = e; }//Push

//出栈，弹出栈顶元素。先决条件是栈非空。 template