数据结构源代码(清华大学+严蔚敏)

void Union(List &La, List Lb) { // 算法2.1

// 将所有在线性表Lb中但不在La中的数据元素插入到La中

int La_len,Lb_len,i;

ElemType e;

La_len = ListLength(La); // 求线性表的长度

Lb_len = ListLength(Lb);

for (i=1; i<=Lb_len; i++) {

GetElem(Lb, i, e); // 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal)) // La中不存在和e相同的数据元素

ListInsert(La, ++La_len, e); // 插入

}

} // union

void MergeList(List La, List Lb, List &Lc) { // 算法2.2

// 已知线性表La和Lb中的元素按值非递减排列。

// 归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。int La_len, Lb_len;

ElemType ai, bj;

int i=1, j=1, k=0;

InitList(Lc);

La_len = ListLength(La);

Lb_len = ListLength(Lb);

while ((i <= La_len) && (j <= Lb_len)) { // La和Lb均非空

GetElem(La, i, ai);

GetElem(Lb, j, bj);

if (ai <= bj) {

ListInsert(Lc, ++k, ai);

++i;

} else {

ListInsert(Lc, ++k, bj);

++j;

}

}

while (i <= La_len) {

GetElem(La, i++, ai); ListInsert(Lc, ++k, ai);

}

while (j <= Lb_len) {

GetElem(Lb, j++, bj); ListInsert(Lc, ++k, bj);

}

} // MergeList

Status InitList_Sq(SqList &L) { // 算法2.3

// 构造一个空的线性表L。

L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));

if (!L.elem) return OK; // 存储分配失败

L.length = 0; // 空表长度为0

L.listsize = LIST_INIT_SIZE; // 初始存储容量

return OK;

} // InitList_Sq

Status ListInsert_Sq(SqList &L, int i, ElemType e) { // 算法2.4

// 在顺序线性表L的第i个元素之前插入新的元素e，

// i的合法值为1≤i≤ListLength_Sq(L)+1

ElemType *p;

if (i < 1 || i > L.length+1) return ERROR; // i值不合法

if (L.length >= L.listsize) { // 当前存储空间已满，增加容量

ElemType *newbase = (ElemType *)realloc(L.elem,

(L.listsize+LISTINCREMENT)*sizeof (ElemType));

if (!newbase) return ERROR; // 存储分配失败

L.elem = newbase; // 新基址

L.listsize += LISTINCREMENT; // 增加存储容量

}

ElemType *q = &(L.elem[i-1]); // q为插入位置

for (p = &(L.elem[L.length-1]); p>=q; --p) *(p+1) = *p;

// 插入位置及之后的元素右移

*q = e; // 插入e

++L.length; // 表长增1

return OK;

} // ListInsert_Sq

Status ListDelete_Sq(SqList &L, int i, ElemType &e) { // 算法2.5

// 在顺序线性表L中删除第i个元素，并用e返回其值。

// i的合法值为1≤i≤ListLength_Sq(L)。

ElemType *p, *q;

if (i<1 || i>L.length) return ERROR; // i值不合法

p = &(L.elem[i-1]); // p为被删除元素的位置

e = *p; // 被删除元素的值赋给e q = L.elem+L.length-1; // 表尾元素的位置

for (++p; p<=q; ++p) *(p-1) = *p; // 被删除元素之后的元素左移--L.length; // 表长减1

return OK;

} // ListDelete_Sq

int LocateElem_Sq(SqList L, ElemType e,

Status (*compare)(ElemType, ElemType)) { // 算法2.6

// 在顺序线性表L中查找第1个值与e满足compare()的元素的位序。// 若找到，则返回其在L中的位序，否则返回0。

int i;

ElemType *p;

i = 1; // i的初值为第1个元素的位序

p = L.elem; // p的初值为第1个元素的存储位置

while (i <= L.length && !(*compare)(*p++, e))

++i;

if (i <= L.length) return i;

else return 0;

} // LocateElem_Sq

void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) { // 算法2.7

// 已知顺序线性表La和Lb的元素按值非递减排列。

// 归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。ElemType *pa,*pb,*pc,*pa_last,*pb_last;

pa = La.elem; pb = Lb.elem;

Lc.listsize = Lc.length = La.length+Lb.length;

pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));

if (!Lc.elem)

exit(OVERFLOW); // 存储分配失败

pa_last = La.elem+La.length-1;

pb_last = Lb.elem+Lb.length-1;

while (pa <= pa_last && pb <= pb_last) { // 归并

if (*pa <= *pb) *pc++ = *pa++;

else *pc++ = *pb++;

}

while (pa <= pa_last) *pc++ = *pa++; // 插入La的剩余元素while (pb <= pb_last) *pc++ = *pb++; // 插入Lb的剩余元素

} // MergeList

Status GetElem_L(LinkList &L,int i, ElemType &e) { // 算法2.8

// L为带头结点的单链表的头指针。

// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR LinkList p;

p = L->next;

int j = 1; // 初始化，p指向第一个结点，j为计数器while (p && j

//顺指针向后查找，直到p指向第i个元素或p为空p = p->next; ++j;

}

if ( !p || j>i ) return ERROR; // 第i个元素不存在

e = p->data; // 取第i个元素

return OK;

} // GetElem_L

Status ListInsert_L(LinkList &L, int i, ElemType e) { // 算法2.9

// 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s;

p = L;

int j = 0;

while (p && j < i-1) { // 寻找第i-1个结点

p = p->next;

++j;

}

if (!p || j > i-1) return ERROR; // i小于1或者大于表长

s = (LinkList)malloc(sizeof(LNode)); // 生成新结点

s->data = e; s->next = p->next; // 插入L中

p->next = s;

return OK;

} // LinstInsert_L

Status ListDelete_L(LinkList &L, int i, ElemType &e) { // 算法2.10

// 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值LinkList p,q;

p = L;

int j = 0;

while (p->next && j < i-1) { // 寻找第i个结点，并令p指向其前趋p = p->next;

++j;

}

if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理

q = p->next;

p->next = q->next; // 删除并释放结点

e = q->data;

free(q);

return OK; } // ListDelete_L

void CreateList_L(LinkList &L, int n) { // 算法2.11

// 逆位序输入（随机产生）n个元素的值，

// 建立带表头结点的单链线性表L

LinkList p;

int i;

L = (LinkList)malloc(sizeof(LNode));

L->next = NULL; // 先建立一个带头结点的单链表

for (i=n; i>0; --i) {

p = (LinkList)malloc(sizeof(LNode)); // 生成新结点

p->data = random(200); // 改为一个随机生成的数字(200以内)

p->next = L->next; L->next = p; // 插入到表头

}

} // CreateList_L

void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) {

// 算法2.12

// 已知单链线性表La和Lb的元素按值非递减排列。

// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。LinkList pa, pb, pc;

pa = La->next; pb = Lb->next;

Lc = pc = La; // 用La的头结点作为Lc的头结点

while (pa && pb) {

if (pa->data <= pb->data) {

pc->next = pa; pc = pa; pa = pa->next;

}

else { pc->next = pb; pc = pb; pb = pb->next; }

}

pc->next = pa ? pa : pb; // 插入剩余段

free(Lb); // 释放Lb的头结点

} // MergeList_L

int LocateElem_SL(SLinkList S, ElemType e) { // 算法2.13

// 在静态单链线性表L中查找第1个值为e的元素。

// 若找到，则返回它在L中的位序，否则返回0。

int i;

i = S[0].cur; // i指示表中第一个结点

while (i && S[i].data != e) i = S[i].cur; // 在表中顺链查找

return i;

} // LocateElem_SL

void InitSpace_SL(SLinkList space) { // 算法2.14

// 将一维数组space中各分量链成一个备用链表，

// space[0].cur为头指针，

// "0"表示空指针

for (int i=0; i

space[i].cur = i+1;

space[MAXSIZE-1].cur = 0;

} // InitSpace_SL

int Malloc_SL(SLinkList &space) { // 算法2.15

// 若备用空间链表非空，则返回分配的结点下标，否则返回0

int i = space[0].cur;

if (space[0].cur) space[0].cur = space[space[0].cur].cur;

return i;

} // Malloc_SL

void Free_SL(SLinkList &space, int k) { // 算法2.16

// 将下标为k的空闲结点回收到备用链表

space[k].cur = space[0].cur; space[0].cur = k;

} // Free_SL

void difference(SLinkList &space, int &S) { // 算法2.17

// 依次输入集合A和B的元素，

//在一维数组space中建立表示集合(A-B)∪(B-A)

// 的静态链表, S为头指针。

// 假设备用空间足够大，space[0].cur为头指针。

int i, j, k, m, n, p, r;

ElemType b;

InitSpace_SL(space); // 初始化备用空间

S = Malloc_SL(space); // 生成S的头结点

r = S; // r指向S的当前最后结点

m = random(2,8); // 输入A的元素个数

n = random(2,8); // 输入B的元素个数

printf(" A = ( ");

initrandom_c1();

for (j=1; j<=m; ++j) { // 建立集合A的链表

i = Malloc_SL(space); // 分配结点

//printf("i=%d ",i);

space[i].data = random_next_c1(); // 输入A的元素值

printf("%c ", space[i].data); // 输出A的元素

space[r].cur = i; r = i; // 插入到表尾

}

printf(")\n");

space[r].cur = 0; // 尾结点的指针为空

initrandom_c1();

printf(" B = ( ");

for (j=1; j<=n; ++j) {

// 依次输入B的元素,若不在当前表中,则插入,否则删除

b = random_next_c1(); // 输入B的元素值

printf("%c ", b); // 输出B的元素

p = S; k = space[S].cur; // k指向集合A中第一个结点

while (k!=space[r].cur && space[k].data!=b) {// 在当前表中查找

p = k; k = space[k].cur;

}

if (k == space[r].cur) {

// 当前表中不存在该元素,插入在r所指结点之后，且r的位置不变

i = Malloc_SL(space);

space[i].data = b;

space[i].cur = space[r].cur;

space[r].cur = i;

} else { // 该元素已在表中,删除之

space[p].cur = space[k].cur;

Free_SL(space, k);

if (r == k) r = p; // 若删除的是尾元素，则需修改尾指针}

}

printf(")\n");

} // difference

DuLinkList GetElemP_DuL(DuLinkList va, int i) {

// L为带头结点的单链表的头指针。

// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR DuLinkList p;

p = va->next;

int j = 1; // 初始化，p指向第一个结点，j为计数器

while (p!=va && j

//顺指针向后查找，直到p指向第i个元素或p为空p = p->next;

++j;

}

if (p==va && j

else return p;

} // GetElem_L

Status ListInsert_DuL(DuLinkList &L, int i, ElemType e) { //算法2.18

// 在带头结点的双链循环线性表L的第i个元素之前插入元素e，// i的合法值为1≤i≤表长+1。

DuLinkList p,s;

if (!(p = GetElemP_DuL(L, i))) // 在L中确定第i个元素的位置指针p return ERROR; // p=NULL, 即第i个元素不存在

if (!(s = (DuLinkList)malloc(sizeof(DuLNode))))

return ERROR;

s->data = e;

s->prior = p->prior;

p->prior->next = s;

s->next = p;

p->prior = s;

return OK;

} // ListInsert_DuL

DuLinkList GetElemP_DuL(DuLinkList va, int i) {

// L为带头结点的单链表的头指针。

// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR DuLinkList p;

p = va->next;

int j = 1; // 初始化，p指向第一个结点，j为计数器

while (p!=va && j

//顺指针向后查找，直到p指向第i个元素或p为空

p = p->next;

++j;

}

if (p==va || j

else return p;

} // GetElem_L

Status ListDelete_DuL(DuLinkList &L, int i, ElemType &e) {//算法2.19

// 删除带头结点的双链循环线性表L的第i个元素，

// i的合法值为1≤i≤表长

DuLinkList p;

if (!(p = GetElemP_DuL(L, i))) // 在L中确定第i个元素的位置指针p return ERROR; // p=NULL, 即第i个元素不存在e = p->data;

p->prior->next = p->next;

p->next->prior = p->prior;

free(p);

return OK;

} // ListDelete_DuL

Status ListInsert_L(NLinkList L, int i, ElemType e) { // 算法2.20

// 在带头结点的单链线性表L的第i个元素之前插入元素e

NLink h,s;

if (!LocatePos(L, i-1, h))

return ERROR; // i值不合法

if (!MakeNode(s, e))

return ERROR; // 结点存储分配失败

InsFirst(h, s);

// 对于从第i结点开始的链表，第i-1结点是它的头结点

return OK;

} // ListInsert_L

Status MergeList_L(NLinkList &La, NLinkList &Lb, NLinkList &Lc,

int (*compare)(ElemType, ElemType)) { // 算法2.21

// 已知单链线性表La和Lb的元素按值非递减排列。

// 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。NLink ha, hb;

Position pa, pb, q;

ElemType a, b;

if (!InitList(Lc)) return ERROR; // 存储空间分配失败

ha = GetHead(La); // ha和hb分别指向La和Lb的头结点

hb = GetHead(Lb);

pa = NextPos(La, ha); // pa和pb分别指向La和Lb中当前结点

pb = NextPos(Lb, hb);

while (pa && pb) { // La和Lb均非空

a = GetCurElem(pa); // a和b为两表中当前比较元素

b = GetCurElem(pb);

if ((*compare)(a, b)<=0) { // a≤b

DelFirst(ha, q); Append(Lc, q); pa = NextPos(La, pa);

} else { // a＞b

DelFirst(hb, q); Append(Lc, q); pb = NextPos(Lb, pb);

}

} // while

if (pa) Append(Lc, pa); // 链接La中剩余结点

else Append(Lc, pb); // 链接Lb中剩余结点

FreeNode(ha); FreeNode(hb); // 释放La和Lb的头结点

return OK;

} // MergeList_L

Status cmp(PElemType a, PElemType b) {

if (a.expn>=b.expn) return 1;

else return 0;

} void CreatPolyn(PLinkList &P, int m) { // 算法2.22

// 输入m项的系数和指数，建立表示一元多项式的有序链表P PLink h, q, s;

PElemType e;

int i;

InitList(P); h = GetHead(P);

e.coef = 0.0; e.expn = -1;

SetCurElem(h, e); // 设置头结点

for (i=1; i<=m; ++i) { // 依次输入m个非零项

// scanf ("%f,%d\n",&e.coef, &e.expn);

e.coef = (float)(random(1, 90) + random(10)/10.0);

if (random(2)) e.coef = -e.coef;

e.expn=e.expn+random(1,10);

//产生随机的数据，但是expn值是递增的

if (!LocateElem(P, e, q, cmp)) { // 当前链表中不存在该指数项

if (MakeNode(s,e)) InsFirst(q, s); // 生成结点并插入链表

if(q==P.tail) P.tail=s;

} else i--; // 如果没有产生插入，则将i值减1

}

} // CreatPolyn

Status PrintfPoly(PLinkList P) {

int i=0;

PLink q=P.head->next;

while (q) {

if (fabs(q->data.coef) > 0.005) {

if (i>0) {

if (q->data.coef>0.005) printf(" + ");

else printf(" - ");

printf("%.2f", fabs(q->data.coef));

} else printf("%.2f", q->data.coef);

if (q->data.expn>=1) printf("x");

if (q->data.expn>1) printf("^%d", q->data.expn);

}

q=q->next;

if (++i % 6 == 0) printf("\n ");

}

printf("\n");

return OK;

}

int Compare(PElemType a, PElemType b) {

if (a.expn

if (a.expn>b.expn) return 1;

return 0;

}

void AddPolyn(PLinkList &Pa, PLinkList &Pb) { // 算法2.23

// 多项式加法：Pa = Pa＋Pb，利用两个多项式的结点构成"和多项式"。PLink ha,hb,qa,qb;

PElemType a, b, temp;

float sum;

ha = GetHead(Pa); // ha和hb分别指向Pa和Pb的头结点

hb = GetHead(Pb);

qa = NextPos(Pa,ha); // qa和qb分别指向La和Lb中当前结点qb = NextPos(Pb,hb);

while (qa && qb) { // Pa和Pb均非空

a = GetCurElem (qa); // a和b为两表中当前比较元素

b = GetCurElem (qb);

switch (Compare(a,b)) {

case -1: // 多项式PA中当前结点的指数值小

ha = qa;

qa = NextPos (Pa, qa);

break;

case 0: // 两者的指数值相等

sum = a.coef + b.coef ;

if (sum != 0.0) { // 修改多项式PA中当前结点的系数值

temp.coef=sum;

temp.expn=a.expn;

SetCurElem(qa, temp) ;

ha = qa;

} else { // 删除多项式PA中当前结点

DelFirst(ha, qa);

FreeNode(qa);

}

DelFirst(hb, qb);

FreeNode(qb);

qb = NextPos(Pb, hb);

qa = NextPos(Pa, ha);

break;

case 1: // 多项式PB中当前结点的指数值小

DelFirst(hb, qb);

InsFirst(ha, qb);

qb = NextPos(Pb, hb);

ha = NextPos(Pa, ha);

break;

} // switch

} // while

if (!Empty(Pb)) Append(Pa, qb); // 链接Pb中剩余结点FreeNode(hb); // 释放Pb的头结点

} // AddPolyn

void conversion (int Num) { // 算法3.1

// 对于输入的任意一个非负十进制整数，

// 打印输出与其等值的八进制数

ElemType e;

SqStack S;

InitStack(S); // 构造空栈

while (Num) {

Push(S, Num % 8);

Num = Num/8;

}

while (!StackEmpty(S)) {

Pop(S,e);

printf ("%d", e);

}

printf("\n");

} // conversion

void LineEdit() { // 算法3.2

//利用字符栈S，从终端接收一行并传送至调用过程的数据区。char ch,*temp;

SqStack S;

InitStack(S); //构造空栈S

printf("请输入一行(#:退格；@:清行):\n");

ch = getchar(); //从终端接收第一个字符

while (ch != EOF) { //EOF为全文结束符

while (ch != EOF && ch != '\n') {

switch (ch) {

case '#': Pop(S, ch); break; // 仅当栈非空时退栈

case '@': ClearStack(S); break; // 重置S为空栈

default : Push(S, ch); break; // 有效字符进栈,未考虑栈满情形

}

ch = getchar(); // 从终端接收下一个字符

}

temp=S.base;

while(temp!=S.top) {

printf("%c",*temp);

++temp;

}

// 将从栈底到栈顶的栈内字符传送至调用过程的数据区；

ClearStack(S); // 重置S为空栈

printf("\n");

if (ch != EOF) {

printf("请输入一行(#:退格；@:清行):\n");

ch = getchar();

}

}

DestroyStack(S);

}

Status Pass(MazeType MyMaze, PosType CurPos);

void FootPrint(MazeType &MyMaze, PosType CurPos);

void MarkPrint(MazeType &MyMaze, PosType CurPos);

PosType NextPos(PosType CurPos, int Dir);

Status MazePath(MazeType &maze, PosType start, PosType end) {

// 算法3.3

// 若迷宫maze中从入口start到出口end的通道，

// 则求得一条存放在栈中

// （从栈底到栈顶），并返回TRUE；否则返回FALSE

Stack S;

PosType curpos;

int curstep;

SElemType e;

InitStack(S);

curpos = start; // 设定"当前位置"为"入口位置"

curstep = 1; // 探索第一步

do {

if (Pass(maze,curpos)) {

// 当前位置可通过，即是未曾走到过的通道块

FootPrint(maze,curpos); // 留下足迹

e.di =1;

e.ord = curstep;

e.seat= curpos;

Push(S,e); // 加入路径

if (curpos.r == end.r && curpos.c==end.c)

return (TRUE); // 到达终点（出口）

curpos = NextPos(curpos, 1); // 下一位置是当前位置的东邻

curstep++; // 探索下一步

} else { // 当前位置不能通过

if (!StackEmpty(S)) {

Pop(S,e);

while (e.di==4 && !StackEmpty(S)) {

MarkPrint(maze,e.seat);

Pop(S,e); // 留下不能通过的标记，并退回一步

} // while

if (e.di<4) {

e.di++;

Push(S, e); // 换下一个方向探索

curpos = NextPos(e.seat, e.di);

// 当前位置设为新方向的相邻块

} // if

} // if

} // else

} while (!StackEmpty(S) );

return FALSE;

} // MazePath

Status Pass( MazeType MyMaze,PosType CurPos) {

if (MyMaze.arr[CurPos.r][CurPos.c]==' ')

return 1; // 如果当前位置是可以通过，返回1

else return 0; // 其它情况返回0

}

void FootPrint(MazeType &MyMaze,PosType CurPos) {

MyMaze.arr[CurPos.r][CurPos.c]='*';

}

void MarkPrint(MazeType &MyMaze,PosType CurPos) {

MyMaze.arr[CurPos.r][CurPos.c]='!';

}

PosType NextPos(PosType CurPos, int Dir) {

PosType ReturnPos;

switch (Dir) {

case 1:

ReturnPos.r=CurPos.r;

ReturnPos.c=CurPos.c+1;

break;

case 2:

ReturnPos.r=CurPos.r+1;

ReturnPos.c=CurPos.c;

break;

case 3:

ReturnPos.r=CurPos.r;

ReturnPos.c=CurPos.c-1;

break;

case 4:

ReturnPos.r=CurPos.r-1;

ReturnPos.c=CurPos.c;

break;

}

return ReturnPos;

}

#define OPSETSIZE 7

unsigned char Prior[7][7] = { // 表3.1 算符间的优先关系'>','>','<','<','<','>','>',

'>','>','<','<','<','>','>',

'>','>','>','>','<','>','>',

'>','>','>','>','<','>','>',

'<','<','<','<','<','=',' ',

'>','>','>','>',' ','>','>',

'<','<','<','<','<',' ','='

};

float Operate(float a, unsigned char theta, float b);

char OPSET[OPSETSIZE]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'};

Status In(char Test,char* TestOp);

char precede(char Aop, char Bop);

float EvaluateExpression(char* MyExpression) { // 算法3.4 // 算术表达式求值的算符优先算法。

// 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。

StackChar OPTR; // 运算符栈，字符元素

StackFloat OPND; // 运算数栈，实数元素

char TempData[20];

float Data,a,b;

char theta,*c,x,Dr[2];

InitStack (OPTR);

Push (OPTR, '#');

InitStack (OPND);

c = MyExpression;

strcpy(TempData,"\0");

while (*c!= '#' || GetTop(OPTR)!= '#') {

if (!In(*c, OPSET)) {

Dr[0]=*c;

Dr[1]='\0';

strcat(TempData,Dr);

c++;

if(In(*c,OPSET)) {

Data=(float)atof(TempData);

Push(OPND, Data);

strcpy(TempData,"\0");

}

} else { // 不是运算符则进栈

switch (precede(GetTop(OPTR), *c)) {

case '<': // 栈顶元素优先权低

Push(OPTR, *c);

c++;

break;

case '=': // 脱括号并接收下一字符

Pop(OPTR, x);

c++;

break;

case '>': // 退栈并将运算结果入栈

Pop(OPTR, theta);

Pop(OPND, b);

Pop(OPND, a);

Push(OPND, Operate(a, theta, b));

break;

} // switch

}

} // while

return GetTop(OPND);

} // EvaluateExpression

float Operate(float a,unsigned char theta, float b) { switch(theta) {

case '+': return a+b;

case '-': return a-b;

case '*': return a*b;

case '/': return a/b;

default : return 0;

}

}

Status In(char Test,char* TestOp) {

bool Find=false;

for (int i=0; i< OPSETSIZE; i++) {

if (Test == TestOp[i]) Find= true;

}

return Find;

}

int ReturnOpOrd(char op,char* TestOp) {

int i;

for(i=0; i< OPSETSIZE; i++) {

if (op == TestOp[i]) return i;

}

return 0;

} char precede(char Aop, char Bop) {

return Prior[ReturnOpOrd(Aop,OPSET)][ReturnOpOrd(Bop,OPSET)]; }

int Count=0;

void move(char x, int n, char z);

void hanoi (int n, char x, char y, char z) { // 算法3.5

/*将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到*/

// 塔座z上，y可用作辅助塔座。

// 搬动操作move (x, n, z) 可定义为：

// (c是初值为0的全局变量，对搬动计数)

// printf("%i. Move disk %i from %c to %c\n", ++c, n, x, z);

if (n==1)

move(x, 1, z); //将编号为１的圆盘从x移到z

else {

hanoi(n-1,x,z,y);

move(x, n, z); //将编号为n的圆盘从x移到z

hanoi(n-1, y, x, z);

//将y上编号为１至n-1的圆盘移到z,x作辅助塔

}

}

void move(char x, int n, char z) {

printf(" %2i. Move disk %i from %c to %c\n",++Count,n,x,z);

}

// 程序中用到的主要变量

EventList ev; // 事件表

Event en; // 事件

LinkQueue q[5]; // 4个客户队列,q[0]未用QElemType customer; // 客户记录

int TotalTime, CustomerNum; // 累计客户逗留时间, 客户数

int CloseTime;

//---------------- 算法3.7 ------------------

int cmp(Event a, Event b) {

/*依事件a的发生时刻<或= 或>事件b的发生时刻分别返回-1或0或1 */

if (a.OccurTime < b.OccurTime) return -1;

if (a.OccurTime > b.OccurTime) return +1;

return 0;

}

void Random(int &durtime, int &intertime) { // 生成随机数durtime = random(2, 10);

intertime = random(10);

}

int Minimum(LinkQueue q[]) { // 求长度最短队列

int minlen = QueueLength(q[1]);

int i = 1;

for (int j=2; j<=4; j++)

if (QueueLength(q[j]) < minlen) {

minlen = QueueLength(q[j]);

i = j;

}

return i;

}

void OpenForDay() {

// 初始化操作

TotalTime = 0; CustomerNum = 0;

// 初始化累计时间和客户数为0

InitList(ev); // 初始化事件链表为空表

en.OccurTime = 0; en.NType = 0; // 设定第一个客户到达事件OrderInsert(ev, en, cmp); // 按事件发生时刻的次序插入事件表for (int i=1; i<=4; ++i) InitQueue(q[i]); // 置空队列

} // OpenForDay

void CustomerArrived() {

// 处理客户到达事件，en.NType=0

int durtime, intertime, i, t;

++CustomerNum;

printf("Customer %d arrived at %d and ", CustomerNum, en.OccurTime);

Random(durtime, intertime); // 生成随机数

t = en.OccurTime + intertime; // 下一客户到达时刻

if (t

OrderInsert(ev, MakeElem(t, 0), cmp);

i = Minimum(q); // 求长度最短队列printf("enter the Queue %d\n", i);

EnQueue(q[i], MakeQElem(en.OccurTime, durtime));

if (QueueLength(q[i]) == 1)

//设定第i队列的一个离开事件并插入事件表

OrderInsert(ev, MakeElem(en.OccurTime+durtime, i), cmp);

} // CustomerArrived

void CustomerDeparture() {

// 处理客户离开事件，en.NType>0

printf("Customer departure at %d\n", en.OccurTime);

int i = en.NType; DeQueue(q[i], customer);

//删除第i队列的排头客户

TotalTime += en.OccurTime-customer.ArrivalTime; // 累计客户逗留时间

if (!QueueEmpty(q[i])) {

// 设定第i队列的一个离开事件并插入事件表

GetHead (q[i], customer);

OrderInsert(ev, MakeElem(en.OccurTime+customer.Duration, i), cmp);

}

} // CustomerDeparture void Bank_Simulation(int closetime) {

int i = 0;

BLink p;

CloseTime = closetime;

printf("Bank_Simulation( %d ) ----- 银行业务模拟\n", closetime); OpenForDay(); // 初始化

while (!ListEmpty(ev)) {

printList(ev);

if (DelFirst(GetHead(ev), p)) {

en = GetCurElem(p);

if (en.NType == 0)

CustomerArrived(); // 处理客户到达事件

else CustomerDeparture(); // 处理客户离开事件

}

if (++i % 9 == 0) {

printf("\n----- 按任意键，继续-----");

getch();

printf("\n\n");

}

}

// 计算并输出平均逗留时间

printf("\nThe Average Time is %f\n", (float)TotalTime/CustomerNum); } // Bank_Simulation

Status TransposeSMatrix(TSMatrix M, TSMatrix &T) { // 算法5.1

// 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T

int p, q, col;

T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;

if (T.tu) {

q = 1;

for (col=1; col<=M.nu; ++col)

for (p=1; p<=M.tu; ++p)

if (M.data[p].j == col) {

T.data[q].i=M.data[p].j;T.data[q].j =M.data[p].i;

T.data[q].e =M.data[p].e; ++q;

}

}

return OK;

} // TransposeSMatrix

Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T) { // 算法5.2 // 采用三元组顺序表存储表示，求稀疏矩阵M的转置矩阵T

int col, t, p, q;

int num[20], cpot[20];

T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;

if (T.tu) {

for (col=1; col<=M.nu; ++col) num[col] = 0;

for (t=1; t<=M.tu; ++t) // 求M 中每一列所含非零元的个数++num[M.data[t].j];

cpot[1] = 1;

// 求M 中每一列的第一个非零元在b.data 中的序号

for (col=2; col<=M.nu; ++col) cpot[col] = cpot[col-1]+num[col-1];

for (p=1; p<=M.tu; ++p) {

col = M.data[p].j; q = cpot[col];

T.data[q].i =M.data[p].j; T.data[q].j =M.data[p].i;

T.data[q].e =M.data[p].e; ++cpot[col];

} // for

} // if

return OK;

} // FastTransposeSMatrix

Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {

// 算法5.3

// 求矩阵乘积Q=M?N，采用行逻辑链接存储表示。

int arow,brow,p,q,t,ctemp[30],l,ccol,tp;

if (M.nu != N.mu) return ERROR;

Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0; // Q初始化

if (M.tu*N.tu != 0) { // Q是非零矩阵

for (arow=1; arow<=M.mu; ++arow) { // 处理M的每一行

for (l=1; l<=M.nu; ++l) ctemp[l] = 0; // 当前行各元素累加器清零

Q.rpos[arow] = Q.tu+1;

if (arow

else tp=M.tu+1;

for (p=M.rpos[arow]; p

brow=M.data[p].j; // 找到对应元在N中的行号

if (brow < N.mu ) t = N.rpos[brow+1];

else t = N.tu+1;

for (q=N.rpos[brow]; q< t; ++q) {

ccol = N.data[q].j; // 乘积元素在Q中列号

ctemp[ccol] += M.data[p].e * N.data[q].e;

} // for q

} // 求得Q中第crow( =arow)行的非零元

for (ccol=1; ccol<=Q.nu; ++ccol) // 压缩存储该行非零元

if (ctemp[ccol]) {

if (++Q.tu > MAXSIZE) return ERROR;

Q.data[Q.tu].i=arow;

Q.data[Q.tu].j=ccol;

Q.data[Q.tu].e=ctemp[ccol];

} // if

} // for arow

} // if

return OK;

} // MultSMatrix

Status CreateSMatrix_OL (CrossList &M) { // 算法5.4

// 创建稀疏矩阵M。采用十字链表存储表示。

// if (M) free(M);

// scanf(&m, &n, &t ); // 输入M的行数、列数和非零元个数OLNode *p,*q;

int i,j,e;

int m=random(4,6), n=random(4,6), t=random(4,5);

M.mu=m; M.nu=n; M.tu=t;

if (!(M.rhead = (OLink *)malloc((m+1)*sizeof(OLink)))) return ERROR; if (!(M.chead = (OLink *)malloc((n+1)*sizeof(OLink)))) return ERROR; for(int a=1;a<=m;a++)

// 初始化行列头指针向量；各行列链表为空链表

M.rhead[a]=NULL;

for(int b=1;b<=n;b++) M.chead[b]=NULL;

for ( int c=1; c<=t; c++) { // 按任意次序输入非零元

scanf(&i,&j,&e);

if (!(p = (OLNode *)malloc(sizeof(OLNode)))) return ERROR;

p->i=i; p->j=j; p->e=e; p->down=NULL; p->right=NULL;

// 新结点

if (M.rhead[i] == NULL || M.rhead[i]->j > j) {

p->right = M.rhead[i]; M.rhead[i]= p;

} else { // 寻查在行表中的插入位置

for (q=M.rhead[i]; (q->right) && (q->right->jright);

p->right = q->right; q ->right = p;

} // 完成行插入

if (M.chead[j] == NULL || M.chead[j]->i > i) {

p->down = M.chead[j]; M.chead[j]= p;

} else { // 寻查在列表中的插入位置

for ( q=M.chead[j]; (q->down) && q->down->i down );

p->down = q->down; q->down = p;

} // 完成列插入

} // for

return OK;

} // CreateSMatrix_OL

int GListDepth(GList L) { // 算法5.5

// 采用头尾链表存储结构,求广义表L的深度。

int max, dep;

GList pp;

if (!L) return 1; // 空表深度为1

if (L->tag == ATOM) return 0; // 原子深度为0

for (max=0, pp=L; pp; pp=pp->ptr.tp) {

dep = GListDepth(pp->ptr.hp);

// 求以pp->ptr.hp为头指针的子表深度if (dep > max) max = dep;

}

return max + 1; // 非空表的深度是各子表的深度的最大值加1 } // GListDepth

Status CopyGList(GList &T, GList L) { // 算法5.6

// 采用头尾链表存储结构,由广义表L复制得到广义表T。

if (!L) T = NULL; // 复制空表

else {

if (!(T = (GList)malloc(sizeof(GLNode)))) // 建表结点

return ERROR;

T->tag = L->tag;

if (L->tag == ATOM) T->atom = L->atom; // 复制单原子

else {

CopyGList(T->ptr.hp, L->ptr.hp);

// 复制广义表T->ptr.hp的副本L->ptr.hp

CopyGList(T->ptr.tp, L->ptr.tp);

// 复制广义表T->ptr.tp的副本L->ptr.tp

} // else

} // else

return OK;

} // CopyGList

Status CreateGList(GList &L, SString S) { // 算法5.7

// 采用头尾链表存储结构，由广义表的书写形式串S创建广义表L。// 设emp="()"。

char s[3]="()";

SString emp;

crt_SString(emp,s);

SString sub,hsub;

GList p,q;

if (StrCompare(S, emp)) L = NULL; // 创建空表

else {

if (!(L=(GList)malloc(sizeof(GLNode)))) return ERROR; // 建表结点if (StrLength(S)==1) { // 创建单原子广义表

L->tag = ATOM; L->atom =S[1]; }

} else {

L->tag = LIST; p = L;

SubString(sub, S, 2, StrLength(S)-2); // 脱外层括号

do { // 重复建n个子表

sever(sub, hsub); // 从sub中分离出表头串hsub

CreateGList(p->ptr.hp, hsub); q = p;

if (!StrEmpty(sub)) { // 表尾不空

if (!(p = (GLNode *) malloc (sizeof(GLNode)))) return ERROR;

p->tag = LIST; q->ptr.tp = p;

}//if

} while (!StrEmpty(sub));

q->ptr.tp = NULL;

} // else

} // else

return OK;

} // CreateGList

Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) { // 算法6.1

// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数，// 先序遍历二叉树T的递归算法，对每个数据元素调用函数Visit。

// 最简单的Visit函数是：

// Status PrintElement( ElemType e ) { // 输出元素e的值

// printf( e ); // 实用时，加上格式串

// return OK;

// }

// 调用实例：PreOrderTraverse(T, PrintElement);

if (T) {

if (Visit(T->data))

if (PreOrderTraverse(T->lchild, Visit))

if (PreOrderTraverse(T->rchild, Visit)) return OK;

return ERROR;

} else return OK;

} // PreOrderTraverse

Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType)) {

// 算法6.2

// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。stack S;

BiTree p;

InitStack(S); Push(S, T); // 根指针进栈

while (!StackEmpty(S)) {

while (GetTop(S, p) && p) Push(S, p->lchild); // 向左走到尽头

Pop(S, p); // 空指针退栈

if (!StackEmpty(S)) { // 访问结点，向右一步

Pop(S, p);

if (!Visit(p->data)) return ERROR;

Push(S, p->rchild);

}

}

return OK;

} // InOrderTraverse

Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType)) {

// 算法6.3

// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数。// 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。stack S;

BiTree p;

InitStack(S); p = T;

while (p || !StackEmpty(S)) {

if (p) { Push(S, p); p = p->lchild; } // 非空指针进栈，继续左进

else { // 上层指针退栈，访问其所指结点，再向右进

Pop(S, p);

if (!Visit(p->data)) return ERROR;

p = p->rchild;

}

}

return OK;

} // InOrderTraverse

BiTree CreateBiTree(BiTree &T) { // 算法6.4

// 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，

// 构造二叉链表表示的二叉树T。

char ch;

scanf("%c",&ch);

if (ch=='#') T = NULL;

else {

if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR;

T->data = ch; // 生成根结点

CreateBiTree(T->lchild); // 构造左子树

CreateBiTree(T->rchild); // 构造右子树

}

return T;

} // CreateBiTree

Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType)) { // 算法6.5

// T指向头结点，头结点的左链lchild指向根结点，

// 头结点的右链lchild指向

// 中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T，// 对每个数据元素调用函数Visit。

BiThrTree p;

p = T->lchild; // p指向根结点

while (p != T) { // 空树或遍历结束时，p==T

while (p->LTag==Link) p = p->lchild;

if (!Visit(p->data)) return ERROR; // 访问其左子树为空的结点

while (p->RTag==Thread && p->rchild!=T) {

p = p->rchild; Visit(p->data); // 访问后继结点}

p = p->rchild; // p进至其右子树根

}

return OK;

} // InOrderTraverse_Thr

Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) { // 算法6.6 // 中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。

if (!(Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) exit(OVERFLOW);

Thrt->LTag = Link; Thrt->RTag =Thread; // 建头结点

Thrt->rchild = Thrt; // 右指针回指

if (!T) Thrt->lchild = Thrt; // 若二叉树空，则左指针回指

else {

Thrt->lchild = T; pre = Thrt;

InThreading(T); // 算法6.7：中序遍历进行中序线索化

pre->rchild = Thrt; pre->RTag = Thread; // 最后一个结点线索化

Thrt->rchild = pre;

}

return OK;

} // InOrderThreading

void InThreading(BiThrTree p) { // 算法6.7

if (p) {

InThreading(p->lchild); // 左子树线索化

if (!p->lchild) // 建前驱线索

{ p->LTag = Thread; p->lchild = pre; }

if (!pre->rchild) // 建后继线索

{ pre->RTag = Thread; pre->rchild = p; }

pre = p; // 保持pre指向p的前驱

InThreading(p->rchild); // 右子树线索化

}

} // InThreading

int find_mfset(MFSet S, int i) { // 算法6.8

// 找集合S中i所在子集的根

int j;

if (i<0 || i>S.n) return -1; // i不是S中任一子集的成员

if (i==0)

printf("\t%d(%d%3d)\n",i,S.nodes[0].data,S.nodes[0].parent);

for (j=i; S.nodes[j].parent>=0; j=S.nodes[j].parent)

printf("\t%d(%d%3d)\n",j,S.nodes[j].data,S.nodes[j].parent);

return 1; }// find_mfset

Status merge_mfset(MFSet &S, int i, int j) { // 算法6.9

/* S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj 的根结点。*/

// 求并集Si∪Sj。

if (i<0 || i>S.n || j<0 || j>S.n) return ERROR;

S.nodes[i].parent = j;

return OK;

} // merge_mfset

Status mix_mfset(MFSet &S, int i, int j) { // 算法6.10

/* S.nodes[i]和S.nodes[j]分别为S中两个互不相交的子集Si和Sj 的根结点*/

// 求并集Si∪Sj。

if (i<0 || i>S.n || j<0 || j>S.n) return ERROR;

if (S.nodes[i].parent>S.nodes[j].parent) { // Si所含成员数比Sj少S.nodes[j].parent+=S.nodes[i].parent;

S.nodes[i].parent=j;

} else { // Sj的元素比Si少

S.nodes[i].parent+=S.nodes[j].parent;

S.nodes[j].parent=i;

}

return OK;

} // mix_mfset

int fix_mfset(MFSet &S, int i) { // 算法6.11

/*确定i所在子集，并将从i至根路径上所有结点都变成根的孩子结点。*/

int j,k,t;

if (i<1 || i>S.n) return -1; // i 不是S中任一子集的成员

for (j=i; S.nodes[j].parent>=0; j=S.nodes[j].parent)

printf("\t%d(%d%3d)\n", j, S.nodes[j].data, S.nodes[j].parent);

for (k=i; k!=j; k=t) {

t=S.nodes[k].parent; S.nodes[k].parent=j;

}

return 1;

} // fix_mfset

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {

// 算法6.12

// w存放n个字符的权值(均>0)，构造哈夫曼树HT，

// 并求出n个字符的哈夫曼编码HC

int i, j, m, s1, s2, start;

char *cd;

unsigned int c, f;

if (n<=1) return;

m = 2 * n - 1;

HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用for (i=1; i<=n; i++) { //初始化

HT[i].weight=w[i-1];

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

}

for (i=n+1; i<=m; i++) { //初始化

HT[i].weight=0;

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

}

printf("\n哈夫曼树的构造过程如下所示：\n");

printf("HT初态:\n 结点weight parent lchild rchild");

for (i=1; i<=m; i++)

printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,

HT[i].parent,HT[i].lchild, HT[i].rchild);

printf(" 按任意键，继续...");

getch();

for (i=n+1; i<=m; i++) { // 建哈夫曼树

// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，

// 其序号分别为s1和s2。

Select(HT, i-1, s1, s2);

HT[s1].parent = i; HT[s2].parent = i;

HT[i].lchild = s1; HT[i].rchild = s2;

HT[i].weight = HT[s1].weight + HT[s2].weight;

printf("\nselect: s1=%d s2=%d\n", s1, s2);

printf(" 结点weight parent lchild rchild");

for (j=1; j<=i; j++)

printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,

HT[j].parent,HT[j].lchild, HT[j].rchild);

printf(" 按任意键，继续...");

getch();

}

//--- 从叶子到根逆向求每个字符的哈夫曼编码---

cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间

cd[n-1] = '\0'; // 编码结束符。

for (i=1; i<=n; ++i) { // 逐个字符求哈夫曼编码

start = n-1; // 编码结束符位置

for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)

// 从叶子到根逆向求编码

if (HT[f].lchild==c) cd[--start] = '0';

else cd[--start] = '1';

HC[i] = (char *)malloc((n-start)*sizeof(char));

// 为第i个字符编码分配空间

strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC

}

free(cd); // 释放工作空间

} // HuffmanCoding

void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) {

// 算法6.13

// w存放n个字符的权值(均>0)，构造哈夫曼树HT，

// 并求出n个字符的哈夫曼编码HC

int i, j, m, s1,s2;

char *cd;

int p;

int cdlen;

if (n<=1) return;

m = 2 * n - 1;

HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用

for (i=1; i<=n; i++) { //初始化

HT[i].weight=w[i-1];

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

}

for (i=n+1; i<=m; i++) { //初始化

HT[i].weight=0;

HT[i].parent=0;

HT[i].lchild=0;

HT[i].rchild=0;

}

printf("\n哈夫曼树的构造过程如下所示：\n");

printf("HT初态:\n 结点weight parent lchild rchild");

for (i=1; i<=m; i++)

printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,

HT[i].parent,HT[i].lchild, HT[i].rchild);

printf(" 按任意键，继续...");

getch();

for (i=n+1; i<=m; i++) { // 建哈夫曼树

// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，

// 其序号分别为s1和s2。

Select(HT, i-1, s1, s2);

HT[s1].parent = i; HT[s2].parent = i;

HT[i].lchild = s1; HT[i].rchild = s2;

HT[i].weight = HT[s1].weight + HT[s2].weight;

printf("\nselect: s1=%d s2=%d\n", s1, s2);

printf(" 结点weight parent lchild rchild");

for (j=1; j<=i; j++)

printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,

HT[j].parent,HT[j].lchild, HT[j].rchild);

printf(" 按任意键，继续...");

getch();

}

//------无栈非递归遍历哈夫曼树，求哈夫曼编码

cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间

p = m; cdlen = 0;

for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志HT[i].weight = 0;

while (p) {

if (HT[p].weight==0) { // 向左

HT[p].weight = 1;

if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }

else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码

HC[p] = (char *)malloc((cdlen+1) * sizeof(char));

cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)

}

} else if (HT[p].weight==1) { // 向右

HT[p].weight = 2;

if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }

} else { // HT[p].weight==2，退回退到父结点，编码长度减1

HT[p].weight = 0; p = HT[p].parent; --cdlen;

}

}

} // HuffmanCoding

void GetPowerSet(int i, List A, List &B) { // 算法6.15

// 线性表A表示集合A，线性表B表示幂集ρ(A)的一个元素。

// 局部量k为进入函数时表B的当前长度。

// 第一次调用本函数时，B为空表，i＝1。

ElemType x;

int k;

if (i > ListLength(A)) Output(B);

// 输出当前B值，即ρ(A)的一个元素

else {

GetElem(A, i, x); k = ListLength(B);

ListInsert(B, k+1, x); GetPowerSet(i+1, A, B);

ListDelete(B, k+1, x); GetPowerSet(i+1, A, B);

}

} // GetPowerSet

Status CreateGraph( MGraph &G ) { // 算法7.1

// 采用数组(邻接矩阵)表示法，构造图G。

scanf(&G.kind); // 自定义输入函数，读入一个随机值

switch (G.kind) {

case DG: return CreateDG(G); // 构造有向图G

case DN: return CreateDN(G); // 构造有向网G

case UDG: return CreateUDG(G); // 构造无向图G

case UDN: return CreateUDN(G); // 构造无向网G，算法7.2

default : return ERROR;

}

} // CreateGraph

Status CreateUDN(MGraph &G) {// 算法7.2

// 采用数组（邻接矩阵）表示法，构造无向网G。

int i,j,k,w;

VertexType v1,v2;

printf("G.vexnum :" ); scanf("%d",&G.vexnum);

printf("G.arcnum :"); scanf("%d",&G.arcnum);

getchar(); /*** 加上此句getchar()!!! ***/

// scanf("%d,%d,%d",&G.vexnum, &G.arcnum, &IncInfo);

for (i=0; i

printf("G.vexs[%d] : ",i);

scanf("%c",&G.vexs[i]);

getchar();

} // 构造顶点向量

for (i=0; i

for (j=0; j

G.arcs[i][j].adj = INFINITY; //{adj,info}

G.arcs[i][j].info= NULL;

}

for (k=0; k

printf("v1 (char) : "); scanf("%c", &v1);getchar();

printf("v2 (char) : "); scanf("%c", &v2);getchar();

printf("w (int) : " ); scanf("%d", &w); getchar();

// 输入一条边依附的顶点及权值

i = LocateVex(G, v1); j = LocateVex(G, v2);

// 确定v1和v2在G中位置

G.arcs[i][j].adj = w; // 弧的权值

// if (IncInfo) scanf(G.arcs[i][j].info); // 输入弧含有相关信息

G.arcs[j][i].adj = G.arcs[i][j].adj; // 置的对称弧 }

return OK;

} // CreateUDN

Status CreateDG(OLGraph &G) { // 算法7.3

// 采用十字链表存储表示，构造有向图G（G.kind=DG）。

//scanf(&G.vexnum, &G.arcnum, &IncInfo);

int i,j,k;

char v1,v2;

int IncInfo=0;

struct ArcBox *p;

scanfInit(); // 输入初始化

scanf(&G.vexnum, &G.arcnum, &IncInfo); // 自定义输入函数

for (i=0; i

scanf(&G.xlist[i].data); // 输入顶点值

G.xlist[i].firstin = G.xlist[i].firstout = NULL; // 初始化指针

}

for (k=0; k

scanf(&v1, &v2); // 输入一条弧的始点和终点

i=LocateVex(G, v1); j=LocateVex(G, v2);

// 确定v1和v2在G中位置

p=(ArcBox *) malloc (sizeof (ArcBox)); // 假定有足够空间// *p = {i, j, G.xlist[j].firstin, G.xlist[i].firstout, NULL}

// {tailvex, headvex, hlink, tlink, info}

p->tailvex=i;

p->headvex=j;

p->hlink=G.xlist[j].firstin;

p->tlink=G.xlist[j].firstout;

G.xlist[j].firstin = G.xlist[i].firstout = p;

// 完成在入弧和出弧链头的插入

//if (IncInfo) Input(*p->info); // 输入弧含有相关信息，此略!!! }

return OK;

} // CreateDG

void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 算法7.4

// 对图G作深度优先遍历。

int v;

VisitFunc = Visit;

// 使用全局变量VisitFunc，使DFS不必设函数指针参数

for (v=0; v

if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS

}

//--- 算法7.4和7.5使用的全局变量---

bool visited[MAX_VERTEX_NUM]; // 访问标志数组

Status (* VisitFunc)(int v); // 函数变量

void DFS(Graph G, int v) { // 算法7.5

// 从第v个顶点出发递归地深度优先遍历图G。

int w;

visited[v] = true; VisitFunc(v); // 访问第v个顶点

for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w))

if (!visited[w]) // 对v的尚未访问的邻接顶点w递归调用DFS DFS(G, w);

}

void BFSTraverse(Graph G, Status (*Visit)(int v )) {// 算法7.6

// 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。

QElemType v,w;

queue Q;

QElemType u;

for (v=0; v

InitQueue(Q); // 置空的辅助队列Q

for (v=0; v

if (!visited[v]) { // v尚未访问

visited[v] = TRUE; Visit(v); // 访问v

EnQueue(Q, v); // v入队列

while (!QueueEmpty(Q)) {

DeQueue(Q, u); // 队头元素出队并置为u

for (w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G, u, w))

if (!visited[w]) { // u的尚未访问的邻接顶点w入队列Q

visited[w] = TRUE; Visit(w);

EnQueue(Q, w);

}//if

}//while

}//if

} // BFSTraverse

void DFSForest(Graph G, CSTree &T) { // 算法7.7

// 建立无向图G的深度优先生成森林的(最左)孩子(右)兄弟链表T int v; int j=0;

CSTree p,q;

T = NULL;

for (v=0; v

for (v=0; v

if (!visited[v]) { // 第v顶点为新的生成树的根结点

p= (CSTree)malloc(sizeof(CSNode)); // 分配根结点

p->data=GetVex(G,v); // 给该结点赋值

p->firstchild=NULL;

p->nextsibling=NULL;

if (!T) T = p; // 是第一棵生成树的根(T的根)

else q->nextsibling = p;

// 其它生成树的根(前一棵的根的“兄弟”)

q = p; // q指示当前生成树的根

DFSTree(G, v,p); // 建立以p为根的生成树

}//if

} // DFSForest

void DFSTree(Graph G, int v, CSTree &T) { // 算法7.8

// 从第v个顶点出发深度优先遍历图G，建立以T为根的生成树int w;

CSTree p,q;

bool first =TRUE;

visited[v] = TRUE;

for (w=FirstAdjVex(G, v); w!=-1; w=NextAdjVex(G, v, w))

if (!visited[w]) {

p = (CSTree) malloc (sizeof (CSNode)); // 分配孩子结点

p->data = GetVex(G,w);

p->firstchild=NULL;

p->nextsibling=NULL;

if (first) { // w是v的第一个未被访问的邻接顶点

T->firstchild = p; first = FALSE; // 是根的左孩子结点

} else { // w是v的其它未被访问的邻接顶点

q->nextsibling = p; // 是上一邻接顶点的右兄弟结点

}

q = p;

DFSTree(G,w,q) ;

}//if

} // DFSTree

void MiniSpanTree_PRIM(MGraph G, VertexType u) { // 算法7.9

// 用普里姆算法从第u个顶点出发构造网G的最小生成树T，

// 输出T的各条边。

// 记录从顶点集U到V－U的代价最小的边的辅助数组定义：

// struct {

// VertexType adjvex;

// VRType lowcost;

// } closedge[MAX_VERTEX_NUM];

int i,j,k;

k = LocateVex ( G, u );

for ( j=0; j

if (j!=k)

{ closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j].adj; }

}

closedge[k].lowcost = 0; // 初始，U＝{u}

for (i=1; i

k = minimum(closedge); // 求出T的下一个结点：第k顶点

// 此时closedge[k].lowcost =

// MIN{ closedge[vi].lowcost | closedge[vi].lowcost>0, vi∈V-U } printf(closedge[k].adjvex, G.vexs[k]); // 输出生成树的边

closedge[k].lowcost = 0; // 第k顶点并入U集

for (j=0; j

if (G.arcs[k][j].adj < closedge[j].lowcost) {

// 新顶点并入U后重新选择最小边

// closedge[j] = { G.vexs[k], G.arcs[k][j].adj };

closedge[j].adjvex=G.vexs[k];

closedge[j].lowcost=G.arcs[k][j].adj;

}

}

} // MiniSpanTree

void FindArticul(ALGraph G) { // 算法7.10

// 连通图G以邻接表作存储结构，查找并输出G上全部关节点。// 全局量count对访问计数。

int v;

struct ArcNode *p;

visited[0] = 1; // 设定邻接表上0号顶点为生成树的根

for (int i=1; i

p = G.vertices[0].firstarc;

if(p) {

v = p->adjvex;

DFSArticul(G, v); // 从第v顶点出发深度优先查找关节点。

if (count < G.vexnum) { // 生成树的根有至少两棵子树

printf (0, G.vertices[0].data); // 根是关节点，输出

while (p->nextarc) {

p = p->nextarc; v = p->adjvex;

if (visited[v]==0) DFSArticul(G, v);

}//while

}//if

}//if(p)

} // FindArticul

void DFSArticul(ALGraph G, int v0 ) { // 算法7.11

// 从第v0个顶点出发深度优先遍历图G，查找并输出关节点

int min,w;

struct ArcNode *p;

visited[v0] = min = ++count; // v0是第count个访问的顶点

for (p=G.vertices[v0].firstarc; p!=NULL; p=p->nextarc) {

// 检查v0的每个邻接顶点

w = p->adjvex; // w为v0的邻接顶点

if (visited[w] == 0) { // w未曾被访问，是v0的孩子

DFSArticul(G, w); // 返回前求得low[w]

if (low[w] < min) min = low[w];

if (low[w] >= visited[v0])

printf(v0, G.vertices[v0].data); // 输出关节点

}

else if (visited[w] < min) min = visited[w];

// w已被访问，w是v0在生成树上的祖先

}//for

low[v0] = min;

} // DFSArticul

Status TopologicalSort(ALGraph G) { // 算法7.12

// 有向图G采用邻接表存储结构。

// 若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR。

SqStack S;

int count,k,i;

ArcNode *p;

char indegree[MAX_VERTEX_NUM];

FindInDegree(G, indegree); // 对各顶点求入度

indegree[0..vernum-1]

InitStack(S);

for (i=0; i

if (!indegree[i]) Push(S, i); // 入度为0者进栈

count = 0; // 对输出顶点计数

while (!StackEmpty(S)) {

Pop(S, i);

printf(i, G.vertices[i].data); ++count; // 输出i号顶点并计数

for (p=G.vertices[i].firstarc; p; p=p->nextarc) {

k = p->adjvex; // 对i号顶点的每个邻接点的入度减1 if (!(--indegree[k])) Push(S, k); // 若入度减为0，则入栈

}

}

if (count

else return OK;

} // TopologicalSort

Status TopologicalOrder(ALGraph G, Stack &T) { // 算法7.13

// 有向网G采用邻接表存储结构，

// 求各顶点事件的最早发生时间ve(全局变量)。

// T为拓扑序列定点栈，S为零入度顶点栈。

// 若G无回路，则用栈T返回G的一个拓扑序列，

// 且函数值为OK，否则为ERROR。

Stack S;int count=0,k;

char indegree[40];

ArcNode *p;

InitStack(S);

FindInDegree(G, indegree); // 对各顶点求入度

indegree[0..vernum-1]

for (int j=0; j

if (indegree[j]==0) Push(S, j); // 入度为0者进栈

InitStack(T);//建拓扑序列顶点栈T

count = 0;

for(int i=0; i

while (!StackEmpty(S)) {

Pop(S, j); Push(T, j); ++count; // j号顶点入T栈并计数

for (p=G.vertices[j].firstarc; p; p=p->nextarc) {

k = p->adjvex; // 对j号顶点的每个邻接点的入度减1

if (--indegree[k] == 0) Push(S, k); // 若入度减为0，则入栈

if (ve[j]+p->info > ve[k]) ve[k] = ve[j]+p->info;

}//for *(p->info)=dut()

}//while

if (count

else return OK;

} // TopologicalOrder

Status CriticalPath(ALGraph G) { // 算法7.14

// G为有向网，输出G的各项关键活动。

Stack T;

int a,j,k,el,ee,dut;

char tag;

ArcNode *p;

if (!TopologicalOrder(G, T)) return ERROR;

for(a=0; a

vl[a] = ve[G.vexnum-1]; // 初始化顶点事件的最迟发生时间while (!StackEmpty(T)) // 按拓扑逆序求各顶点的vl值

for (Pop(T, j), p=G.vertices[j].firstarc; p; p=p->nextarc) {

k=p->adjvex; dut=p->info; //dut

if (vl[k]-dut < vl[j]) vl[j] = vl[k]-dut;

}

for (j=0; j

for (p=G.vertices[j].firstarc; p; p=p->nextarc) {

k=p->adjvex;dut=p->info;

ee = ve[j]; el = vl[k]-dut;

tag = (ee==el) ? '*' : ' ';

printf(j, k, dut, ee, el, tag); // 输出关键活动

}

return OK;

} // CriticalPath

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)

{ // 算法7.15

// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v] // 及其带权长度D[v]。

// 若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。// final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。int i=0,j, v,w,min;

bool final[MAX_VERTEX_NUM];

for (v=0; v

final[v] = FALSE;

D[v] = G.arcs[v0][v].adj;

for (w=0; w

if (D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }

}

D[v0] = 0; final[v0] = TRUE; // 初始化，v0顶点属于S集

//--- 开始主循环，每次求得v0到某个v顶点的最短路径，

// 并加v到S集---

for (i=1; i

min = INFINITY; // 当前所知离v0顶点的最近距离

for (w=0; w

if (!final[w]) // w顶点在V-S中

if (D[w]

for (w=0; w

if (!final[w] && (min+G.arcs[v][w].adj

// 修改D[w]和P[w], w∈V-S

D[w] = min + G.arcs[v][w].adj;

for(j=0;j

P[w][w] = TRUE; // P[w] = P[v]+[w]

}//if

}//for

} // ShortestPath_DIJ

void ShortestPath_FLOYD(MGraph G, PathMatrix P[], DistancMatrix &D) { // 算法7.16

/*用Floyd算法求有向网G中各对顶点v和w之间的最短路径P[v][w]及其*/

// 带权长度D[v][w]。若P[v][w][u]为TRUE，

// 则u是从v到w当前求得最

// 短路径上的顶点。

int v,w,u,i;

for (v=0; v

D[v][w] = G.arcs[v][w].adj;

for (u=0; u

if (D[v][w] < INFINITY) { // 从v到w有直接路径

P[v][w][v] = P[v][w][w] = TRUE;

}//if

}//for

for (u=0; u

for (v=0; v

for (w=0; w

if (D[v][u]+D[u][w] < D[v][w]) {

// 从v经u到w的一条路径更短

D[v][w] = D[v][u]+D[u][w];

for (i=0; i

P[v][w][i] =(P[v][u][i] || P[u][w][i]);

}//if

} // ShortestPath_FLOYD

int Search_Seq(SSTable ST, KeyType key) { // 算法9.1

// 在顺序表ST中顺序查找其关键字等于key的数据元素。

// 若找到，则函数值为该元素在表中的位置，否则为0。

int i=0;

ST.elem[0].key=key; // "哨兵"

for (i=ST.length; ST.elem[i].key!=key; --i); // 从后往前找

return i; // 找不到时，i为0

} // Search_Seq

int Search_Bin ( SSTable ST, KeyType key ) { // 算法9.2

// 在有序表ST中折半查找其关键字等于key的数据元素。

// 若找到，则函数值为该元素在表中的位置，否则为0。

int low, high, mid;

low = 1; high = ST.length; // 置区间初值

while (low <= high) {

mid = (low + high) / 2;

if (EQ(key , ST.elem[mid].key)) return mid; // 找到待查元素

else if (LT(key, ST.elem[mid].key)) high = mid - 1;

// 继续在前半区间进行查找else low = mid + 1; // 继续在后半区间进行查找}

return 0; // 顺序表中不存在待查元素

} // Search_Bin

Status SecondOptimal(BiTree &T, ElemType R[], float sw[],

int low, int high) { // 算法9.3

// 由有序表R[low..high]及其累计权值表sw

// (其中sw[0]==0)递归构造次优查找树T。

int i,j;

float min,dw;

i = low; min = (float)fabs(sw[high]-sw[low]);

dw = sw[high]+sw[low-1];

for (j=low+1; j<=high; ++j) // 选择最小的ΔPi值if (fabs(dw-sw[j]-sw[j-1]) < min) {

i = j; min = (float)fabs(dw-sw[j]-sw[j-1]);

}

if (!(T = (BiTree)malloc(sizeof(BiTNode)))) return ERROR;

T->data = R[i]; // 生成结点if (i==low) T->lchild = NULL; // 左子树空

else SecondOptimal(T->lchild, R, sw, low, i-1); // 构造左子树

if (i==high) T->rchild = NULL; // 右子树空

else SecondOptimal(T->rchild, R, sw, i+1, high); // 构造右子树

return OK;

} // SecondOptimal

typedef BiTree SOSTree; // 次优查找树采用二叉链表的存储结构

Status CreateSOSTree(SOSTree &T, SSTable ST) { // 算法9.4

// 由有序表ST构造一棵次优查找树T。ST的数据元素含有权域weight

float sw[20];

if (ST.length == 0) T = NULL;

else {

FindSW(sw, ST);

// 按照有序表ST中各元素的weight域求累计权值表sw

SecondOptimal(T, ST.elem, sw, 1, ST.length);

}

return OK;

} // CreateSOSTree

BiTree SearchBST (BiTree T, KeyType key) { // 算法9.5(a)

/*在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，*/

/*若查找成功，则返回指向该数据元素结点的指针，否则返回空指针*/

if (!T || EQ(key, T->data.key)) return T; // 查找结束

else if (LT(key, T->data.key))

return SearchBST(T->lchild, key); // 在左子树中继续查找else

return SearchBST(T->rchild, key); // 在右子树中继续查找

} // SearchBST

Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {

// 算法9.5(b)

/*在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，*/

// 若查找成功，则指针p指向该数据元素结点，并返回TRUE，

// 否则指针p指向查找路径上访问的最后一个结点并返回FALSE，// 指针f指向T的双亲，其初始调用值为NULL

if (!T) { p = f; return FALSE; } // 查找不成功else if (EQ(key, T->data.key)) { p = T; return TRUE; } // 查找成功

else if (LT(key, T->data.key))

return SearchBST(T->lchild, key, T, p); // 在左子树中继续查找else

return SearchBST(T->rchild, key, T, p); // 在右子树中继续查找

} // SearchBST

Status InsertBST(BiTree &T, ElemType e) { // 算法9.6

// 当二叉排序树T中不存在关键字等于e.key的数据元素时，

// 插入e并返回TRUE，否则返回FALSE

BiTree p,s;

if (!SearchBST(T, e.key, NULL, p)) { // 查找不成功

s = (BiTree)malloc(sizeof(BiTNode));

s->data = e; s->lchild = s->rchild = NULL;

if (!p) T = s; // 插入s 为新的根结点

else if (LT(e.key, p->data.key)) p->lchild=s; // 插入s为左孩子

else p->rchild = s; // 插入s 为右孩子

return TRUE;

} else return FALSE; // 树中已有关键字相同的结点，不再插入

} // Insert BST

Status DeleteBST(BiTree &T, KeyType key) { // 算法9.7

// 若二叉排序树T中存在关键字等于key的数据元素时，

// 则删除该数据元素结点p，并返回TRUE；否则返回FALSE

if (!T) return FALSE; // 不存在关键字等于key的数据元素else {

if (EQ(key, T->data.key)) // 找到关键字等于key的数据元素

return Delete(T);

else if (LT(key, T->data.key)) return DeleteBST(T->lchild, key);

else return DeleteBST(T->rchild, key);

}

} // DeleteBST

Status Delete(BiTree &p) { // 算法9.8

// 从二叉排序树中删除结点p，并重接它的左或右子树

BiTree q, s;

if (!p->rchild) { // 右子树空则只需重接它的左子树

q = p; p = p->lchild; free(q);

} else if (!p->lchild) { // 只需重接它的右子树

q = p; p = p->rchild; free(q);

} else { // 左右子树均不空

q = p; s = p->lchild;

while (s->rchild) // 转左，然后向右到尽头

{ q = s; s = s->rchild; }

p->data = s->data; // s指向被删结点的“后继”

if (q != p) q->rchild = s->lchild; // 重接*q的右子树

else q->lchild = s->lchild; // 重接*q的左子树

free(s);

}

return TRUE;

} // Delete

void R_Rotate(BSTree &p) { // 算法9.9

// 对以*p为根的二叉排序树作右旋处理，处理之后p指向新的树

根结点，

// 即旋转处理之前的左子树的根结点

BSTree lc;

lc = p->lchild; // lc指向*p的左子树根结点

p->lchild = lc->rchild; // lc的右子树挂接为*p的左子树

lc->rchild = p; p = lc; // p指向新的根结点

} // R_Rotate

void L_Rotate(BSTree &p) { // 算法9.10

// 对以p↑为根的二叉排序树作左旋处理，

// 处理之后p指向新的树根结点，

// 即旋转处理之前的右子树的根结点

BSTree rc;

rc = p->rchild; // rc指向*p的右子树根结点

p->rchild = rc->lchild; // rc的左子树挂接为*p的右子树

rc->lchild = p; p = rc; // p指向新的根结点

} // L_Rotate

Status InsertAVL(BSTree &T, ElemType e, Boolean &taller) { // 算法9.11 // 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，// 则插入一个数据元素为e的新结点，并返回1，否则返回0。// 若因插入而使二叉排序树失去平衡，则作平衡旋转处理，

// 布尔变量taller反映T长高与否

if (!T) { // 插入新结点，树"长高"，置taller为TRUE

T = (BSTree) malloc (sizeof(BSTNode)); T->data = e;

T->lchild = T->rchild = NULL; T->bf = EH; taller = TRUE;

}

else {

if (EQ(e.key, T->data.key)) // 树中已存在和e有相同关键字的结点

{ taller = FALSE; return 0; } // 则不再插入

if (LT(e.key, T->data.key)) { // 应继续在*T的左子树中进行搜索

if (InsertAVL(T->lchild, e, taller)==0) return 0; // 未插入

if (taller) // 已插入到*T的左子树中且左子树"长高"

switch (T->bf) { // 检查*T的平衡度

case LH: // 原本左子树比右子树高，需要作左平衡处理LeftBalance(T); taller = FALSE; break;

case EH:

// 原本左、右子树等高，现因左子树增高而使树增高

T->bf = LH; taller = TRUE; break;

case RH: // 原本右子树比左子树高，现左、右子树等高T->bf = EH; taller = FALSE; break;

} // switch (T->bf)

} // if

else { // 应继续在T↑的右子树中进行搜索

if (InsertAVL(T->rchild, e, taller)==0) return 0;

if (taller) // 已插入到*T的右子树且右子树长高

switch (T->bf) { // 检查*T的平衡度

case LH: // 原本左子树比右子树高，现左、右子树等高T->bf = EH; taller = FALSE; break;

case EH:

// 原本左、右子树等高，现因右子树增高而使树增高

T->bf = RH; taller = TRUE; break;

case RH: // 原本右子树比左子树高，需要作右平衡处理RightBalance(T); taller = FALSE; break;

} // switch (T->bf)

} // else

} // else

return 1;

} //InsertAVL

void LeftBalance(BSTree &T) { // 算法9.12

// 对以指针T所指结点为根的二叉树作左平衡旋转处理。

// 本算法结束时，指针T指向新的根结点

BSTree lc,rd;

lc = T->lchild; // lc指向*T的左子树根结点

switch (lc->bf) { // 检查*T的左子树的平衡度，并作相应平衡处理case LH:

// 新结点插入在*T的左孩子的左子树上，要作单右旋处理T->bf = lc->bf = EH;

R_Rotate(T);

break;

case RH: // 新结点插入在*T的左孩子的右子树上，要作双旋处理rd = lc->rchild; // rd指向*T的左孩子的右子树根

switch (rd->bf) { // 修改*T及其左孩子的平衡因子

case LH: T->bf = RH; lc->bf = EH; break;

case EH: T->bf = lc->bf = EH; break;

case RH: T->bf = EH; lc->bf = LH; break;

} // switch (rd->bf)

rd->bf = EH;

L_Rotate(T->lchild); // 对*T的左子树作左旋平衡处理

R_Rotate(T); // 对*T作右旋平衡处理

} // switch (lc->bf)

} // LeftBalance

void ShowBTNode(BTree p) { //display the BTnode

printf("(");

for(int i=1; i<=p->keynum; i++)

printf("%3d", p->key[i]);

printf(" )");

}

int Search(BTree p, KeyType K) {

for(int i=0; i < p->keynum && p->key[i+1] <= K; i++);

return i;

}

Result SearchBTree(BTree T, KeyType K, int f) { // 算法9.13 // 在m阶B树T上查找关键字K，返回结果(pt,i,tag)

BTree p, q;

int found, i, j=0;

Result R;

p = T; q = NULL; found = FALSE; i = 0;

// 初始化，p指向待查结点，q指向p的双亲while (p && !found) {

if (f) {

if (j) printf(" --> ");

ShowBTNode(p);

}

i = Search(p, K); // 在p->key[1..keynum]中查找i，

// 使得：p->key[i]<=Kkey[i+1] if (i>0 && p->key[i]==K) found = TRUE; // 找到待查关键字

else { q = p; p = p->ptr[i]; }

j++;

}

if (found) { // 查找成功

R.pt = p; R.i = i; R.tag = 1;

} else { // 查找不成功

R.pt = q; R.i = i; R.tag = 0;

}

return R; // 返回结果信息: K的位置(或插入位置) } // SearchBTree

void Insert(BTree &q, int i, KeyType x, BTree ap) {

// insert the key X between the key[i] and key[i+1]

// at the pointer node q

int n = q->keynum;

for (int j=n; j>i; j--) {

q->key[j+1] = q->key[j];

q->ptr[j+1] = q->ptr[j];

}

q->key[i+1] = x;

q->ptr[i+1] = ap;

if (ap) ap->parent = q;

q->keynum++;

}

void split(BTree &q, int s, BTree &ap) {

//move key[s+1...m],p->ptr[s...m] int the new pointer *ap

int i,j,n=q->keynum;

ap = (BTree)malloc(sizeof(BTNode));

ap->ptr[0] = q->ptr[s];

for (i=s+1,j=1; i<=n; i++,j++) {

ap->key[j] = q->key[i];

ap->ptr[j] = q->ptr[i];

}

ap->keynum = n-s;

ap->parent = q->parent;

for (i=0; i<=n-s; i++)

//refresh the parent_pointer of the subpointer in new pointer *ap if (ap->ptr[i]) ap->ptr[i]->parent = ap;

q->keynum = s-1;

}

void NewRoot(BTree &T, BTree p, KeyType x, BTree ap) {

T = (BTree)malloc(sizeof(BTNode));

T->keynum = 1; T->ptr[0] = p; T->ptr[1] = ap; T->key[1] = x;

//if (f) ShowBTNode(T);

if (p) p->parent= T;

// refresh the parent_pointer of sub_pointers in *p and *q

if (ap) ap->parent = T;

T->parent = NULL;

}

Status InsertBTree(BTree &T, KeyType K, BTree q, int i) { // 算法9.14

// 在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K。// 若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B树。

BTree ap;

int finished, needNewRoot, s;

KeyType x;

if (!q) // T是空树(参数q初值为NULL)

NewRoot(T, NULL, K, NULL); // 生成仅含关键字K的根结点*T else {

x = K; ap = NULL; finished = needNewRoot = FALSE;

while (!needNewRoot && !finished) {

Insert(q, i, x, ap); // 将x和ap分别插入到q->key[i+1]和q->ptr[i+1]

if (q->keynum < m) finished = TRUE; // 插入完成

else { // 分裂结点*q

// 将q->key[s+1..m], q->ptr[s..m]和

// q->recptr[s+1..m]移入新结点*ap

s = (m+1)/2; split(q, s, ap); x = q->key[s];

if (q->parent) { // 在双亲结点*q中查找x的插入位置

q = q->parent; i = Search(q, x);

} else needNewRoot = TRUE;

} // else

} // while

if (needNewRoot) // 根结点已分裂为结点*q和*ap

NewRoot(T, q, x, ap); // 生成新根结点*T,q和ap为子树指针

}

return OK;

} // InsertBTree

RECORD *SearchDLTree(DLTree T, KeysType K) { // 算法9.15 // 在非空双链树T中查找关键字等于K的记录。

DLTree p;

int i;

p = T->first; i=0; // 初始化

while (p && i

while (p && p->symbol != K.ch[i]) // 查找关键字的第i位

p = p->next;

if (p && ifirst; // 准备查找下一位

++i;

} // 查找结束

if (!p) return NULL; // 查找不成功

else return p->infoptr; // 查找成功

} //Search DLTree

int ord(char c) {

return c-'@';

}

RECORD *SearchTrie(TrieTree T, KeysType K) { // 算法9.16 // 在键树T中查找关键字等于K的记录。

TrieTree p;

int i;

for (p=T, i=0; // 对K的每个字符逐个查找

p && p->kind==BRANCH && i

p=p->bh.ptr[ord(K.ch[i])], i++); // ord求字符在字母表中序号if (p && p->kind==LEAF && strcmp(p->lf.K.ch, K.ch)==0)

return p->https://www.wendangku.net/doc/0b14810135.html,ptr; // 查找成功

else return NULL; // 查找不成功

} // SearchTrie

Status SearchHash(HashTable H, HKeyType K, int &p, int &c) { // 算法9.17

// 在开放定址哈希表H中查找关键码为K的元素，

// 若查找成功，以p指示待查数据元素在表中位置，并返回SUCCESS；

// 否则，以p指示插入位置，并返回UNSUCCESS,

// c用以计冲突次数，其初值置零，供建表插入时参考

p = Hash(K); // 求得哈希地址

while ((H.elem[p].key != NULLKEY) && // 该位置中填有记录

!equal(K, (H.elem[p].key))) // 并且关键字不相等collision(p, ++c); // 求得下一探查地址p if (equal(K, (H.elem[p].key)))

return SUCCESS; // 查找成功，p返回待查数据元素位置

else return UNSUCCESS; // 查找不成功(H.elem[p].key == NULLKEY)，

// p返回的是插入位置

} // SearchHash

Status InsertHash(HashTable &H, HElemType e) { // 算法9.18 // 查找不成功时插入数据元素e到开放定址哈希表H中，并返回OK；

// 若冲突次数过大，则重建哈希表

int c = 0;

int p = 0;

if (SearchHash(H, e.key, p, c) == SUCCESS )

return DUPLICATE; // 表中已有与e有相同关键字的元素else if (c < H.cursize) { // 冲突次数c未达到上限，（阀值c可调）

H.elem[p] = e; ++H.count; return SUCCESS; // 插入e

} else {

RecreateHashTable(H); // 重建哈希表

return UNSUCCESS;

}

} // InsertHash

void InsertSort(SqList &L) { // 算法10.1

// 对顺序表L作直接插入排序。

int i,j;

for (i=2; i<=L.length; ++i)

if (LT(L.r[i].key, L.r[i-1].key)) {

// "<"时，需将L.r[i]插入有序子表

L.r[0] = L.r[i]; // 复制为哨兵

for (j=i-1; LT(L.r[0].key, L.r[j].key); --j)

L.r[j+1] = L.r[j]; // 记录后移

L.r[j+1] = L.r[0]; // 插入到正确位置

}

} // InsertSort

void BInsertSort(SqList &L) { // 算法10.2

// 对顺序表L作折半插入排序。

int i,j,high,low,m;

for (i=2; i<=L.length; ++i) {

L.r[0] = L.r[i]; // 将L.r[i]暂存到L.r[0]

low = 1; high = i-1;

while (low<=high) { // 在r[low..high]中折半查找有序插入的位置

m = (low+high)/2; // 折半

if (LT(L.r[0].key, L.r[m].key)) high = m-1; // 插入点在低半区

else low = m+1; // 插入点在高半区

}

for (j=i-1; j>=high+1; --j) L.r[j+1] = L.r[j]; // 记录后移

L.r[high+1] = L.r[0]; // 插入

}

} // BInsertSort

void Arrange(SLinkList &SL) { // 算法10.3

// 根据静态链表SL中各结点的指针值调整记录位置，

// 使得SL中记录按关键字非递减有序顺序排列

SLNode temp;

int i;

int p,q;

p = SL.r[0].next; // p指示第一个记录的当前位置

for (i=1; i

// SL.r[1..i-1]中记录已按关键字有序排列，

// 第i个记录在SL中的当前位置应不小于i

while (p

p = SL.r[p].next;

q = SL.r[p].next; // q指示尚未调整的表尾

if (p!= i) {

temp=SL.r[p];

SL.r[p]=SL.r[i];

SL.r[i]=temp;

SL.r[i].next=p;

// 指向被移走的记录，使得以后可由while循环找回

}

p=q; // p指示尚未调整的表尾，为找第i+1个记录作准备}

} // Arrange

void ShellInsert(SqList &L, int dk) { // 算法10.4

// 对顺序表L作一趟希尔插入排序。本算法对算法10.1作了以下修改：// 1. 前后记录位置的增量是dk，而不是1；

// 2. r[0]只是暂存单元，不是哨兵。当j<=0时，插入位置已找到。

数据结构 清华大学出版社 严蔚敏吴伟民编著

第一章绪论 1、数据结构是计算机中存储、组织数据的方式。精心选择的数据 结构可以带来最优效率的算法。 2、程序设计= 算法+数据结构 3、解决问题方法的效率： ●跟数据的组织方式有关 ●跟空间的利用效率有关 ●跟算法的巧妙程度有关 4、数据：所有能输入到计算机中,且被计算机处理的符号的集合， 是计算机操作对象的总称； 是计算机处理的信息的某种特定的符号表示形式。 5、数据元素：数据中的一个“个体”,数据结构中讨论的基本单 位。相当于“记录”,在计算机程序中通常作为一个整体考 虑和处理。 6、数据项: 相当于记录的“域”, 是数据的不可分割的最小单位, 如学号。数据元素是数据项的集合。 7、数据对象：性质相同的数据元素的集合. 例如: 所有运动员的记录集合 8、数据结构：是相互间存在某种关系的数据元素集合。 9、数据结构是带结构的数据元素的集合。 10、不同的关系构成不同的结构。 11、次序关系：

{|i=1,2,3,4,5,6} 12、对每种数据结构，主要讨论如下两方面的问题： 1）数据的逻辑结构，数据结构的基本操作； 2）数据的存储结构，数据结构基本操作的实现； 13、数据的逻辑结构： 数据之间的结构关系，是具体关系的抽象。 数据结构的基本操作： 指对数据结构的加工处理。 14、数据的存储结构(物理结构)： 数据结构在计算机内存中的表示。 数据结构基本操作的实现： 基本操作在计算机上的实现（方法)。 15、数据结构的有关概念 16、数据元素的4类的基本结构： ○1集合； ○2线性结构：结构中数据元素之间存在一对一的关系； ○3树形结构：结构中数据元素之间存在一对多的关系； ○4图状结构或网状结构：结构中数据元素之间存在多对多的关系。 17、C语言的优点：C语言可以直接操作内存。 18、每个节点都由两部分组成：数据域和指针域。 19、链接存储结构特点：

数据结构课后习题答案清华大学出版社殷人昆

1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息？广义地讲，信息就是消息。宇宙三要素（物质、能量、信息）之一。它是现实世界各种事物在人们头脑中的反映。此外，人们通过科学仪器能够认识到的也是信息。信息的特征为：可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据？因为信息的表现形式十分广泛，许多信息在计算机中不方便存储和处理，例如，一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等，必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此，数据(data)是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中，信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为：数据结构= { D, R }。其中，D是某一数据对象，R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容： ①数据成员以及它们相互之间的逻辑关系，也称为数据的逻辑结构，简称为数据结构； ②数据成员极其关系在计算机存储器内的存储表示，也称为数据的物理结构，简称为存储结构； ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储不是一码事，是与计算机存储无关的。因此，数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型，是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现（亦称为映像），它是依赖于计算机的，是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算，每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么？ 【解答】 线性结构的特点是：在结构中所有数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如，一维数组、线性表等就是典型的线性结构 非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如，树、图或网络等都是典型的非线性结构。 1-4．什么是抽象数据类型？试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数：缺省的构造函数没有参数；第二个构造函数将双精度浮点数赋给复数的实部，虚部置为0；第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部，以及+、-、*、/等运算的成员函数。

清华大学数据结构试题及答案

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系 时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是 ___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插 入元素的时间复杂度为____________。 5. 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j从0到3 ， 则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6. 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的 总和是_____________。 8.8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表 达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。

2015年清华大学826运筹学与统计学

2015年清华大学826运筹学与统计学（数学规划、应用随机模型、统计学各占1/3）考研复习参考书 科目：826 运筹学与统计学（数学规划、应用随机模型、统计学各占1/3）参考书：《运筹学（数学规划）（第3版）清华大学出版社，2004年1月 W.L.Winston 《运筹学》（应用随机模型）清华大学出版社，2004年2月 V.G. Kulkarni 《概率论与数理统计》（第1～9章）高等教育出版社，2001年盛聚等 考研复习方法，这里不详细展开。简单归纳为： 新祥旭考研提醒：首先，清楚考试明细，掌握真题，真题为本。通过真题，了解和熟知：考什么、怎么考、考了什么、没考什么；通过练习真题，了解：目前我的能力、复习过程中我的进步、我的考试目标。提醒一句：千万不要浪费大量时间做不相关的模拟题；千万不要把考研复习等同于做题目，搞题海战术。 其次，把握参考书，参考书为锚。弄懂、弄熟。考研复习如何才能成功？借用《卖油翁》里的一句话，那就是：手熟而已。明确考试之后，考研就基本上是一个熟悉吃透的过程。无论何时，参考书第一，不能轻视。所以，千万不要本末倒置，把做题凌驾于看书之上。如何才叫熟悉？我认为，要打破“讲速度，不讲效率”的做法，看了多少遍并不是检验熟悉与否的指标，合上书本，随时自我检测，能否心中有数、一问便知，这才是关键。 再次，制定计划，合理分配时间。不是每一本参考书都很重要，都一样重要，所以，在了解真题的基础上，要了解每一本书占多少分，如何命题考试，在此基础上，每一本参考书的主次轻重、复习方略也就清楚了，复习才不会像开摊卖药，平均用力。一个月制定一份计划书，每天写一句话鼓励自己，一个月调整一次复习重点，这都是必要的。 最后，快乐复习。考研复习是以什么样状态进行的，根源在于能否克服不良情绪。第一，报考对外汉语，你是因为喜欢这个专业吗？如果是，那么，就继续给自己这种暗示，那么你一定会发现，复习再紧张，也是愉悦的，因为你是为了兴趣而考研的；第二，规律的作息，不大时间战，消耗战，养精蓄锐。运动加休息，如果能每天都很规律，那么成功也就有了保障，负面情绪少了，效率也就高了。 总结为几个关键词，就是：知己知彼、本末分明。

李春葆数据结构习题与解析(修订版)知识分享

李春葆编著：数据结构（C语言篇）――习题与解析（修订版） 清华大学出版社 一、绪论 选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。 1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面是2。 1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.正确性和简单性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。 A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。 A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。 A.正确 B.不正确 填空题 1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。 2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3.在树形结构中，树根结点没有结点，其余每个结点有且只有个前驱结点；叶子结点没有结点，其余每个结点的后续可以。

数据结构(C语言版)第三版__清华大学出版社_习题参考答案

附录习题参考答案 习题1参考答案 1.1.选择题 (1). A. (2). A. (3). A. (4). B.,C. (5). A. (6). A. (7). C. (8). A. (9). B. (10.) A. 1.2.填空题 (1). 数据关系 (2). 逻辑结构物理结构 (3). 线性数据结构树型结构图结构 (4). 顺序存储链式存储索引存储散列表（Hash）存储 (5). 变量的取值范围操作的类别 (6). 数据元素间的逻辑关系数据元素存储方式或者数据元素的物理关系 (7). 关系网状结构树结构 (8). 空间复杂度和时间复杂度 (9). 空间时间 (10). Ο(n) 1.3 名词解释如下： 数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，一个数据元素可由若干个数据项组成。 数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。 数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。 数据类型：是指变量的取值范围和所能够进行的操作的总和。 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。 1.4 语句的时间复杂度为： (1) Ο(n2) (2) Ο(n2) (3) Ο(n2) (4) Ο(n-1) (5) Ο(n3) 1.5 参考程序： main() { int X,Y,Z； scanf(“%d, %d, %d”,&X,&Y,Z)； if (X>=Y) if(X>=Z) if (Y>=Z) { printf(“%d, %d, %d”,X,Y,Z);} else { printf(“%d, %d, %d”,X,Z,Y);}

第四版运筹学部分课后习题解答

运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题 a） 12 12 12 12 min z=23 466 ..424 ,0 x x x x s t x x x x + +≥ ? ? +≥ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为 最优解，即该问题有无穷多最优解，这时的最优值为 min 3 z=2303 2 ?+?= P47 1.3 用图解法和单纯形法求解线性规划问题 a） 12 12 12 12 max z=10x5x 349 ..528 ,0 x x s t x x x x + +≤ ? ? +≤ ? ?≥ ? 解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点， 即 1 12 122 1 349 3 528 2 x x x x x x = ? += ?? ? ?? +== ?? ? ，即最优解为* 3 1, 2 T x ?? = ? ?? 这时的最优值为 max 335 z=1015 22 ?+?=

单纯形法： 原问题化成标准型为 121231241234 max z=10x 5x 349 ..528,,,0x x x s t x x x x x x x +++=?? ++=??≥? j c → 10 5 B C B X b 1x 2x 3x 4x 0 3x 9 3 4 1 0 0 4x 8 [5] 2 0 1 j j C Z - 10 5 0 0 0 3x 21/5 0 [14/5] 1 -3/5 10 1x 8/5 1 2/5 0 1/5 j j C Z - 1 0 - 2 5 2x 3/2 0 1 5/14 -3/14 10 1x 1 1 0 -1/7 2/7 j j C Z - -5/14 -25/14

数据结构(C语言版)9-12章练习 答案 清华大学出版社

9-12章数据结构作业答案 第九章查找 选择题 1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。 这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 判断题 1．Hash表的平均查找长度与处理冲突的方法无关。 (错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。（错） 3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（错） 填空题 1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20， 需做的关键码比较次数为 4 . 算法应用题 1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长 为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。要求：对该关 键字序列构造哈希表，并计算查找成功的平均查找长度。 2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲 突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在 等概率情况下查找成功时的平均查找长度。 ３、对长度为20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均 查找长度。 ４、设散列表的长度为15，散列函数H（K）=K%13，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散 列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。

运筹学模拟卷2运筹学胡运权清华大学出版社

运筹学模拟2 3分，共5题，总计15分） 1.线性规划问题中可行域的顶点与线性规划问题的（）对应。 A 可行解 B 基本解 C 基本可行解 D 不能确定 2．在对偶理论中下列说法正确的是：（） A 原问题任一可行解的目标函数值是其对偶问题目标函数值的上界。 B 对偶问题任一可行解的目标函数值是其原问题目标函数的下界。 C 如原问题有可行解且目标函数值无界，则其对偶问题无可行解 D 若原问题有可行解而其对偶问题无可行解，则原问题目标函数值有界。 3．资源的影子价格实际上是一种机会成本。在纯市场经济条件下，当市场价格低于影子价格时，这种资源应该：（） A买进 B卖出 C不买进也不卖出 D不能确定 4．关于整数线性规划问题与它的松弛问题之间的关系说法不正确的是：（）A整数线性规划问题的可行域是它的松弛问题可行域的子集。 B若松弛问题无可行解，则整数线性规划问题也无可行解 C松弛问题的最优解是整数线性规划问题的最优解的一个下界。 D若松弛问题的最优解的各个分量都是整数，则它也是整数线性规划的最优解 5．一个人的效用曲线反映了他对风险的态度。对实际收入的增加的反应比较迟钝的是（） A 保守型 B 中间型 C 冒险型 D 无法确定 2分，共5题，总计10分） 1．如果一个线性规划问题有可行解，那么它一定有最优解。（） 2．若线性规划的原问题和对偶问题都有最优解，则它们最优解一定相等。（） y>0,说明在最优生产计划中， 3．已知在线性规划的对偶问题的最优解中，对偶变量 i 第i种资源已经完全用尽。（） 4．因为运输问题是一种特殊的线性规划模型，因而求其解也可能出现下列4种情况：有唯一最优解，有无穷最优解，无界解，无可行解。（）

数据结构习题集答案解析_清华大学版

第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果：改变复数C 的第k 元的值为e IsAscending(C) 操作结果：如果复数C 的两个元素按升序排列，则返回1，否则返回0 IsDescending(C)

《数据结构》期终考试试卷(A)-清华大学

2010年《数据结构》期终考试试卷（A） 班级学号姓名 一、简答题（每小题6分，共30分） (1) 假设一个线性链表的类名为linkedList，链表结点的类名为ListNode，它包含两个数据成员data和link。data存储该结点的数据，link是链接指针。下面给定一段递归打印一个链表中所有结点中数据的算法： void PrintList (ListNode *L) { if ( L != NULL ) { cout << L->data << endl; PrintList ( L->link ); } } 试问此程序在什么情况下不实用？给出具体修改后的可实用的程序？ (1) 此程序在内存容量不足时不适用。因为需要一个递归工作栈。当链表越长，递归工作栈的深度越深，需要的存储越多。可采用非递归算法节省存储。 void PrintList (ListNode *L) { while ( L != NULL ) { cout << L->data << endl; L = L->link; } } (2) 如果每个结点占用2个磁盘块因而需要2次磁盘访问才能实现读写，那么在一棵有n个关键码的2m阶B树中，每次搜索需要的最大磁盘访问次数是多少？ (2) 在2m阶B树中关键码个数n与B树高度h之间的关系为h≤log m ((n+1)/2)+1，那么每次搜索最大磁盘访问次数为2h max = 2log m ((n+1)/2)+2。

(3) 给定一棵保存有n 个关键码的m 阶B 树。从某一非叶结点中删除一个关键码需要的最大磁盘访问次数是多少？ (3) 在m 阶B 树中关键码个数n 与B 树最大高度h 的关系为h = log ?m/2?((n+1)/2)+1。若设寻找被删关键码所在非叶结点读盘次数为h ’，被删关键码是结点中的k i ，则从该结点的p i 出发沿最左链到叶结点的读盘次数为h -h ’。当把问题转化为删除叶结点的k 0时，可能会引起结点的调整或合并。极端情况是从叶结点到根结点的路径上所有结点都要调整，除根结点外每一层读入1个兄弟结点，写出2个结点，根结点写出1个结点，假设内存有足够空间，搜索时读入的盘块仍然保存在内存，则结点调整时共读写盘3(h -1)+1。总共的磁盘访问次数为 h ’+(h -h ’)+3(h -1)+1 = 4h -2 = 4(log ?m/2?((n+1)/2)+1)-2 = = 4log ?m/2?((n+1)/2)+2 (4) 给定一个有n 个数据元素的序列，各元素的值随机分布。若要将该序列的数据调整成为一个堆，那么需要执行的数据比较次数最多是多少？ (4) 设堆的高度为h = ?log 2(n+1)?，当每次调用siftDown 算法时都要从子树的根结点调整到叶结点，假设某子树的根在第i 层（1≤i ≤h -1），第h 层的叶结点不参加比较。从子树根结点到叶结点需要比较h -i 层，每层需要2次比较：横向在两个子女里选一个，再纵向做父子结点的比较。因此，在堆中总的比较次数为 )i h j ( 2j 2 2j 22 2j 2 2)i h (221 h 1 j j 1 -h 1 h 1 j j -1 h 1 h 1 j 1 -j -h 1h 1 i 1-i -=??=??=?=-∑ ∑∑∑-=-=--=-=代换 因为 2h-1 ≤n ≤2h -1，且∑-=∞ →=1 h 1j j h 22j lim ，则n 42n 22 j 221 h 1j j 1 h =??≤??∑-=-

清华严蔚敏《数据结构》的全部代码实现C语言

创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王* /* c1.h (程序名) */ #include #include #include /* malloc()等*/ #include /* INT_MAX等*/ #include /* EOF(=^Z或F6),NULL */ #include /* atoi() */ #include /* eof() */ #include /* floor(),ceil(),abs() */ #include /* exit() */ /* 函数结果状态代码*/ #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 /* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行*/ typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等*/ typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */

/* algo2-1.c 实现算法2.1的程序*/ #include"c1.h" typedef int ElemType; #include"c2-1.h" /*c2-1.h 线性表的动态分配顺序存储结构*/ #define LIST_INIT_SIZE 10 /* 线性表存储空间的初始分配量*/ #define LISTINCREMENT 2/* 线性表存储空间的分配增量*/ typedef struct { ElemType*elem; /* 存储空间基址*/ int length; /* 当前长度*/ int listsize; /* 当前分配的存储容量(以sizeof(ElemType)为单位) */ }SqList; #include"bo2-1.c" /* bo2-1.c 顺序表示的线性表(存储结构由c2-1.h定义)的基本操作(12个) */ Status InitList(SqList*L) /* 算法2.3 */ { /* 操作结果：构造一个空的顺序线性表*/ (*L).elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if(!(*L).elem) exit(OVERFLOW); /* 存储分配失败*/ (*L).length=0; /* 空表长度为0 */ (*L).listsize=LIST_INIT_SIZE; /* 初始存储容量*/ return OK; } Status DestroyList(SqList*L) { /* 初始条件：顺序线性表L已存在。操作结果：销毁顺序线性表L */ free((*L).elem); (*L).elem=NULL; (*L).length=0; (*L).listsize=0; return OK; } 创作编号： GB8878185555334563BT9125XW 创作者：凤呜大王*

数据结构习题集答案(c版)(清华大学 严蔚敏)

1.16 void print_descending(int x,int y,int z)//按从大到小顺序输出三个数 { scanf("%d,%d,%d",&x,&y,&z); if(xy; //<->为表示交换的双目运算符,以下同 if(yz; if(xy; //冒泡排序 printf("%d %d %d",x,y,z); }//print_descending 1.17 Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f { int tempd; if(k<2||m<0) return ERROR; if(m

运筹学教程第五版课后答案

《运筹学》试题（答案） 一、单项选择题。下列每题给出的四个答案中只有一个是正确的，将表示正确答案的字母填入题后的括号中。（20分） 1．对一个极大化的线性规划问题用单纯形法求解，若对所有的检验数0 ≤j σ，但对某个 非基变量j x ，有0 =j σ，则该线性规划问题（ B ） A ．有唯一的最优解； B ．有无穷多个最优解； C ．为无界解； D ．无可行解。 2．使用人工变量法求解极大化线性规划问题时，当所有的检验数0 ≤j σ，在基变量中仍含有非零的人工变量，表明该线性规划问题（ D ） A ．有唯一的最优解； B ．有无穷多个最优解； C ．为无界解； D ．无可行解。 3．在对偶问题中，若原问题与对偶问题均具有可行解，则（ A ） A ．两者均具有最优解，且它们最优解的目标函数值相等； B ．两者均具有最优解，原问题最优解的目标函数值小于对偶问题最优解的目标函数值； C ．若原问题有无界解，则对偶问题无最优解； D ．若原问题有无穷多个最优解，则对偶问题只有唯一最优解； 4．在用对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中（ D ） A ．b 列元素不小于零； B ．检验数都大于零； C ．检验数都不小于零； D ．检验数都不大于零。 5．在产销平衡运输问题中，设产地为m 个，销地为n 个，那么解中非零变量的个数（ A ）。 A ．不能大于(m +n -1)；B ．不能小于(m +n -1)；C ．等于(m +n -1)；D ．不确定。 6．在运输问题中，每次迭代时，如果有某非基变量的检验数等于零，则该运输问题（ B ）。 A ．无最优解；B ．有无穷多个最优解；C ．有唯一最优解；D ．出现退化解。 7．在目标规划中，求解的基本原则是首先满足高级别的目标，但当高级别目标不能满足时（ D ）。 A ．其后的所有低级别目标一定不能被满足； B ．其后的所有低级别目标一定能被满足； C ．其后的某些低级别目标一定不能被满足； D ．其后的某些低级别目标有可能被满足。 8．若一个指派问题的系数矩阵的某行各元素都加上常数k 得到一个新的矩阵，这一新矩阵对应着一个新的指派问题，则（ A ）。 A ．新问题与原问题有相同的最优解； B ．新问题最优目标值大于原问题最优目标函数值； C ．新问题最优解等于原问题最优解加上k ； D ．新问题最优解小于原问题最优解。 9．如果要使目标规划实际实现值不超过目标值，则相应的偏离变量应满足（ B ）。 A ．0>+d ； B ．0=+d ； C ．0=-d ； D ． .0,0>>+-d d 10．动态规划问题中最优策略具有性质：（ C ） A ．每个阶段的决策都是最优的； B ．当前阶段以前的各阶段决策是最优的； C ．无论初始状态与初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应

数据结构习题集答案解析清华大学版

第1章 绪论 1、1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型与抽象数据类型。 解：数据就是对客观事物得符号表示。在计算机科学中就是指所有能输入到计算机中并被计算机程序处理得符号得总称。 数据元素就是数据得基本单位，在计算机程序中通常作为一个整体进行考虑与处理。 数据对象就是性质相同得数据元素得集合，就是数据得一个子集。 数据结构就是相互之间存在一种或多种特定关系得数据元素得集合。 存储结构就是数据结构在计算机中得表示。 数据类型就是一个值得集合与定义在这个值集上得一组操作得总称。 抽象数据类型就是指一个数学模型以及定义在该模型上得一组操作。就是对一般数据类型得扩展。 1、2 试描述数据结构与抽象数据类型得概念与程序设计语言中数据类型概念得区别。 解：抽象数据类型包含一般数据类型得概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用得数据与在这些数据上所进行得操作。在定义抽象数据类型中得数据部分与操作部分时，要求只定义到数据得逻辑结构与操作说明，不考虑数据得存储结构与操作得具体实现，这样抽象层次更高，更能为其她用户提供良好得使用接口。1、3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图得画法惯例画出其逻辑结构图。 解： 1、4 试仿照三元组得抽象数据类型分别写出抽象数据类型复数与有理数得定义（有理数就是其分子、分母均为自然数且分母不为零得分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部与虚部分别为re 与im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 得第k 元得值 Put(&C,k,e) 操作结果：改变复数C 得第k 元得值为e IsAscending(C) 操作结果：如果复数C 得两个元素按升序排列，则返回1，否则返回0

运筹学教学大纲

《运筹学》教学大纲一、课程基本信息

二、课程性质和任务 课程的性质：本课程是我校工程管理专业学生开设的专业课，是一门理论性和综合性很强的学科，同时也是学习其它相关课程的基础。 课程的任务：本课程主要介绍线性规划以及求线性规划问题的基本方法-单纯形法，线性规划的对偶理论及对偶单纯形法，运输问题和目标规划理论，图论和网络计划，存储论等运筹学中的重要的理论与方法。它不仅能丰富学生的数学理论和管理知识，更重要的是能让学生在以后的工作和学习或科研中能够应用运筹学思想和方法，提高工作和科研的效能和效益。 三、学时分配表 四、教学内容及基本要求 绪论 2学时 【教学目的】

1.了解运筹学的释义与发展； 2.了解运筹学的分支与应用； 3.了解运筹学的研究方法。 【教学重点和难点】 重点：运筹学的分支和方法 难点：运筹学的释义 【主要教学内容】 运筹学的释义 运筹学的发展 运筹学的分支 运筹学的研究方法 运筹学的应用与前景 第1章线性规划基础 8学时 【教学目的】 1.了解线性规划问题及其数学模型； 2.掌握线性规划问题解的概念以及图解法； 3.掌握线性规划的标准型； 4.能够将线性规划非标准型转化为标准型； 5.了解线性规划的基本理论。 【教学重点和难点】 重点：线性规划问题的解的概念、图解法、线性规划的标准型难点：线性规划问题的几何意义、将线性规划的非标准型标准化【主要教学内容】 1.1 线性规划问题及其数学模型 1.2 线性规划的图解 1.3 线性规划标准型与解的概念 1.4 线性规划的基本理论 第2章线性规划原理与解法 14学时 【教学目的】 1..掌握单纯形原理； 2.掌握单纯形表的计算步骤和计算方法；

《数据结构》练习题及答案清华出版社

《数据结构》模拟题 2010年 7月 一、单选题（每空 2 分，共 10 分） 1、队列的删除操作是在（）进行。 A ．队首B．队尾C．队前 D ．对后 2、当利用大小为N 的数组顺序存储一个栈时，假定用top = = N 表示栈空，则退栈时，用（）语句修改top 指针。 A ． top++;B． top=0;C． top--;D． top=N; 3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A．51B． 23C．53D． 74 4、在一棵二叉树中，第 4 层上的结点数最多为（）。 A．31B．8 C.15D．16 5、向堆中插入一个元素的时间复杂度为（）。 A ． O(log 2n)B． O(n)C．O(1) D ． O(nlog 2n) 二、填空题（每空 1 分，共 20 分） 1、数据的逻辑结构被分为____________、___________、____________ 和 ____________四种。 2、若对一棵二叉树的结点编号从 1 开始顺序编码，按顺序存储，把编号为 1 的结点存储到 a[1]中，其余类推，则a[i] 元素的左孩子元素为______，右孩子元素为 _____，双亲元素 (i>0) 为 ________。 3、从一个栈删除元素时，首先取出，然后再前移一位。 4、后缀表达式“ 2 10 + 5 * 6–9 / ”的值为。 5、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K) ，则度为3、 2、 1、 0 的结点数分 别为 ______、 ______、 ______和 ______个。 6、在一个具有 n 个顶点的无向完全图中，包含有________条边，在一个具有n 个顶点的有 向完全图中，包含有________条边。 7、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为________索引，若对 应主表中的若干条记录，则称此索引为________索引。 8、对于二分查找所对应的判定树，它既是一棵_____，又是一棵 _____ __ ___ 。 三、运算题（每小题 5 分，共 10 分） 1、 1、空堆开始依次向堆中插入线性表（64,52, 12,48,45,26）中的每个元素，请以线性 表的形式给出每插入一个元素后堆的状态。（为小根堆） 2、在一份电文中共使用五种字符：A，G，F，U，Y，Z，它们的出现频率依次为 12,9,18,7,14， 11，求出每个字符的哈夫曼编码。

数据结构(C语言版)第6章练习 清华大学出版社

第六章数据结构作业 第六章树 选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2．算术表达式a+b*（c+d/e）转为后缀表达式后为（） A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ 3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（） A．5 B．6 C．7 D．8 4. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（） A．9 B．11 C．15 D．不确定 6．具有10个叶结点的二叉树中有（）个度为2的结点， A．8 B．9 C．10 D．ll 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数为（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 有n个叶子的哈夫曼树的结点总数为（）。 A．不确定 B．2n C．2n+1 D．2n-1 9. 一棵具有 n个结点的完全二叉树的树高度（深度）是（） A．?logn?+1 B．logn+1 C．?logn? D．logn-1 10．深度为h的满m叉树的第k层有（）个结点。(1=