数据结构算法总结

算法总结

2.1

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

2.2

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

2.3

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

1

// 构造一个空的线性表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

2.4

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

2.5

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

2.6

int LocateElem_Sq(SqList L, ElemType e,

2

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

2.7

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

2.8

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<i) { // 顺指针向后查找,直到p指向第i个元素或p为空 p = p->next; ++j;

}

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

3

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

return OK;

} // GetElem_L

2.9

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

2.10

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

2.11

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

// 逆位序输入(随机产生)n个元素的值,建立带表头结点的单链线性表L LinkList p;

int i;

4

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

2.12

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

2.13

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

2.14

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

// 将一维数组space中各分量链成一个备用链表,space[0].cur为头指针, // "0"表示空指针

for (int i=0; i<MAXSIZE-1; ++i)

space[i].cur = i+1;

space[MAXSIZE-1].cur = 0; } // InitSpace_SL

2.15

5

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

2.16

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

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

space[k].cur = space[0].cur; space[0].cur = k; } // Free_SL

2.17

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) {

6

// 当前表中不存在该元素,插入在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

2.18

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<i) { //顺指针向后查找,直到p指向第i个元素或p为空 p = p->next;

++j;

}

if (p==va && j<i) return NULL; // 第i个元素不存在

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

7

2.19

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<i) { //顺指针向后查找,直到p指向第i个元素或p为空 p = p->next;

++j;

}

if (p==va || j<i) return NULL; // 第i个元素不存在

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

2.20

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

2.21

Status MergeList_L(NLinkList &La, NLinkList &Lb, NLinkList &Lc, int (*compare)(ElemType, ElemType)) { // 算法2.21 // 已知单链线性表La和Lb的元素按值非递减排列。

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

NLink ha, hb;

8

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

2.22

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)) { // 当前链表中不存在该指数项

9

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;

}

2.23

int Compare(PElemType a, PElemType b) {

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

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);

10

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

3.1

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);

11

printf ("%d", e);

}

printf("\n");

} // conversion

3.2

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);

}

3.3

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) {

12

// 算法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

13

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;

}

3.4

#define OPSETSIZE 7

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

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

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

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

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

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

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

};

14

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);

15

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)]; }

3.5

int Count=0;

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

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

// 将塔座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); //将编号为1的圆盘从x移到z

else {

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

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

hanoi(n-1, y, x, z); //将y上编号为1至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); }

3.7

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

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++)

17

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<CloseTime) // 银行尚未关门,插入事件表 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);

18

}

} // 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

4.1

#include "algo0403.cpp"

int Index(SString S, SString T, int pos) { // 算法4.1

// T为非空串。若主串S中第pos个字符之后存在与T相等的子串,

// 则返回第一个这样的子串在S中的位置,否则返回0

int n,m,i;

SString sub;

if (pos > 0) {

n = StrLength(S);

m = StrLength(T);

i = pos;

while (i <= n-m+1) {

SubString (sub, S, i, m);

if (StrCompare(sub,T) == 0) ++i;

else return i;

} // while

} // if

19

return 0;

}

4.2

Status Concat(SString &T, SString S1, SString S2) { // 算法4.2 // 用T返回由S1和S2联接而成的新串。若未截断,则返回TRUE,否则FALSE。 int i;

Status uncut;

if (S1[0]+S2[0] <= MAXSTRLEN) { // 未截断

for (i=1; i<=S1[0]; i++) T[i] = S1[i];

for (i=1; i<=S2[0]; i++) T[i+S1[0]] = S2[i];

T[0] = S1[0]+S2[0];

uncut = TRUE;

} else if (S1[0] < MAXSTRLEN) { // 截断

for (i=1; i<=S1[0]; i++) T[i] = S1[i];

for (i=S1[0]+1; i<=MAXSTRLEN; i++) T[i] = S2[i-S1[0]]; T[0] = MAXSTRLEN;

uncut = FALSE;

} else { // 截断(仅取S1)

for (i=0; i<=MAXSTRLEN; i++) T[i] = S1[i];

uncut = FALSE;

}

return uncut;

} // Concat

4.3

Status SubString(SString &Sub, SString S, int pos, int len) { // 算法4.3

// 用Sub返回串S的第pos个字符起长度为len的子串。

// 其中,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。 int i;

if (pos < 1 || pos > S[0] || len < 0 || len > S[0]-pos+1) return ERROR;

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

Sub[i] = S[pos+i-1];

Sub[0] = len;

return OK;

} // SubString

4.4

Status StrInsert(HString &S, int pos, HString T) { // 算法4.4 // 1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T。 int i;

if (pos < 1 || pos > S.length+1) // pos不合法

return ERROR;

if (T.length) { // T非空,则重新分配空间,插入T

if (!(S.ch = (char *)realloc(S.ch,(S.length+T.length+1)

20

*sizeof(char)))) return ERROR;

for (i=S.length-1; i>=pos-1; --i) // 为插入T而腾出位置 S.ch[i+T.length] = S.ch[i];

for (i=0; i<T.length; i++) // 插入T

S.ch[pos-1+i] = T.ch[i];

S.length += T.length;

}

return OK;

} // StrInsert

4.5

int Index(SString S, SString T, int pos) { // 算法4.5 // 返回子串T在主串S中第pos个字符之后的位置。

// 若不存在,则函数值为0。

// 其中,T非空,1≤pos≤StrLength(S)。

int i = pos;

int j = 1;

while (i <= S[0] && j <= T[0]) {

if (S[i] == T[j]) { // 继续比较后继字符

++i;

++j;

} else { // 指针后退重新开始匹配

i = i-j+2;

j = 1;

}

}

if (j > T[0]) return i-T[0];

else return 0;

} // Index

4.6

void get_next(SString T, int *next) { // 算法4.7

int i=1;

next[1]=0;

int j=0;

while (i<T[0]) {

if(j==0 || T[i]== T[j]) {

++i; ++j; next[i] = j;

} else j= next[j];

}

}

int Index_KMP(SString S, SString T, int pos) { // 算法4.6 // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的 // KMP算法。其中,T非空,1≤pos≤StrLength(S)。

21

int next[255];

int i = pos;

int j = 1;

get_next(T, next);

while (i <= S[0] && j <= T[0]) {

if (j == 0 || S[i] == T[j]) { // 继续比较后继字符 ++i; ++j;

} else j = next[j]; // 模式串向右移动

}

if (j > T[0]) return i-T[0]; // 匹配成功

else return 0;

} // Index_KMP

4.7

void get_next(SString T, int *next) { // 算法4.7

int i=1;

next[1]=0;

int j=0;

while (i<T[0]) {

if(j==0 || T[i]== T[j]) {

++i; ++j; next[i] = j;

} else j= next[j];

}

}

int Index_KMP(SString S, SString T, int pos) { // 算法4.6 // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置的 // KMP算法。其中,T非空,1≤pos≤StrLength(S)。

int next[255];

int i = pos;

int j = 1;

get_next(T, next);

while (i <= S[0] && j <= T[0]) {

if (j == 0 || S[i] == T[j]) { // 继续比较后继字符 ++i; ++j;

} else j = next[j]; // 模式串向右移动

}

if (j > T[0]) return i-T[0]; // 匹配成功

else return 0;

} // Index_KMP

4.8

void get_nextval(SString T, int *next) { // 算法4.8 // 求模式串T的next函数修正值并存入数组nextval。

int i = 1;

22

int j = 0;

next[1] = 0;

while (i<T[0]) {

if (j==0 || T[i]==T[j]) {

++i; ++j;

if (T[i]!=T[j]) next[i] = j;

else next[i] = next[j];

}

else j = next[j];

}

} // get_nextval

int Index_KMP(SString S, SString T, int pos) { // 算法4.6 // 利用模式串T的next函数求T在主串S中第pos个字符之后的位置 // 的KMP算法。其中,T非空,1≤pos≤StrLength(S)。

int next[255];

int i = pos;

int j = 1;

get_nextval(T, next);

while (i<=S[0] && j<=T[0]) {

if (j==0 || S[i]==T[j]) { ++i; ++j; } // 继续比较后继字符 else j = next[j]; // 模式串向右移动 }

if (j>T[0]) return i-T[0]; // 匹配成功

else return 0;

} // Index_KMP

4.9

#define MaxBookNum 1000 // 假设只对1000本书建索引表 #define MaxKeyNum 2500 // 索引表的最大容量

#define MaxLineLen 500 // 书目串的最大长度

#define MaxWordNum 10 // 词表的最大容量

#define MaxWordLength 30 // 单词的最大长度

typedef int Boolean;

typedef struct {

char item[MaxWordNum][MaxWordLength]; // 字符串的数组 int last; // 词表的长度

} WordListType; // 词表类型(顺序表)

typedef struct {

HString key; // 关键词

NLinkList bnolist; // 存放书号索引的链表

23

} IdxTermType; // 索引项类型

typedef struct {

IdxTermType item[MaxKeyNum+1];

int last;

} IdxListType; // 索引表类型(有序表)

//------ 基本操作 ------

void InitIdxList(IdxListType &idxlist);

// 初始化操作,置索引表idxlist为空表,即idxlist.last=0,

// 且在idxlist.item[0]设一空串

void GetLine(FILE *f);

// 从文件f读入一个书目信息到书目串缓冲区buf

Status ExtractKeyWord(char *Buffer, WordListType &w, int &bno); // 从buf中提取书名关键词到词表wdlist,书号存入bno

Status InsertIdxList(IdxListType &idxlist, ElemType bno); // 将书号为bno的书名关键词按词典顺序插入索引表idxlist

Status PutText(FILE *g, IdxListType idxlist);

// 将生成的索引表idxlist输出到文件g

void PrintFile(FILE *FileName);

Status InsertIdxList(IdxListType &idxlist, int bno); // 算法4.10 // 索引表插入算法

void GetWord(int i, HString &wd); // 算法4.11 // 用wd返回词表wdlist中第i个关键词。

int Locate(IdxListType &idxlist, HString wd, Boolean &b); // 算法4.12

// 在索引表idxlist中查询是否存在与wd相等的关键词。

// 若存在,则返回其在索引表中的位置,

// 且b取值TRUE;否则返回插入位置,且b取值FALSE

void InsertNewKey(IdxListType &idxlist, int i, HString wd);//算法4.13

// 在索引表idxlist的第i项上插入新关键词wd,

// 并初始化书号索引的链表为空表

Status InsertBook(IdxListType &idxlist, int i, int bno); // 算法

4.14

// 在索引表idxlist的第i项中插入书号为bno的索引

//------ 主要变量 ------

char buf[MaxLineLen]; // 书目串缓冲区

WordListType wdlist; // 词表

IdxListType idxlist; // 索引表

//------ 主函数 ------

24

int main(int argc, char* argv[]) { // 算法4.9

FILE *f,*g;

int BookNo;

printf("**************************************************\n");

printf(" 《数据结构》(C语言版) 严蔚敏 吴伟民 编著 \n"); printf(" 算法4.9-4.14(参见图4.9) \n");

printf("**************************************************\n\n");

if ((f = fopen ("Algo0409BookInfo.txt", "r"))==NULL) { printf("ERROR in open BookInfo.txt!\n");

exit(1);

}

if ((g = fopen ("Algo0409BookIdx.txt", "w"))==NULL) { printf("ERROR in open BookIdx.txt!\n");

exit(1);

}

printf("书目文件:\n");

PrintFile(f);

InitIdxList(idxlist); // 初始化索引表idxlist为空表 while (!feof (f)) {

GetLine (f); // 从文件f读入一个书目信息到buf ExtractKeyWord(buf,wdlist,BookNo);

// 从buf提取关键词到词表,书号存入BookNo

InsertIdxList(idxlist, BookNo); // 书号为BookNo的关键词插入索引表

}

PutText(g, idxlist); // 将生成的索引表idxlist输出到文件g fclose(f);

fclose(g);

printf("对书目文件进行处理后的索引文件:\n");

if ((g = fopen ("Algo0409BookIdx.txt", "r"))==NULL) { printf("ERROR in open BookIdx.txt!\n");

exit(1);

}

PrintFile(g);

fclose(g);

printf("按任意键,结束 ......\n");

getch();

return 0;

} // main

25

Status InsertIdxList(IdxListType &idxlist, int bno) { // 算法

4.10

int i,j;

HString wd;

Boolean b;

for (i=0; i<wdlist.last; i++) {

GetWord(i, wd);

j = Locate(idxlist, wd, b);

if (!b)

InsertNewKey(idxlist, j, wd); // 插入新的索引项

InsertBook(idxlist, j, bno); // 插入书号索引

}

return OK;

} // InsertIdxList

void GetWord(int i, HString &wd) { // 算法4.11

char *p;

p = *(wdlist.item +i); // 取词表中第i个字符串

StrAssign(wd, p); // 生成关键字字符串

} // GetWord

int Locate(IdxListType &idxlist, HString wd, Boolean &b) { // 算法4.12

int i,m;

for (i = idxlist.last-1;

((m = StrCompare(idxlist.item[i].key, wd)) > 0); --i); if (m==0) { // 找到

b = TRUE;

return i;

} else { // 没找到

b = FALSE;

return i+1;

}

} // Locate

void InsertNewKey(IdxListType &idxlist, int i, HString wd) {//算法4.13

int j;

for (j=idxlist.last-1; j>=i; --j) // 后移索引项

idxlist.item[j+1] = idxlist.item[j];

// 插入新的索引项

StrCopy(idxlist.item[i].key, wd); // 串赋值

InitList(idxlist.item[i].bnolist); // 初始化书号索引表为空表 ++idxlist.last;

26

} // InsertNewKey

Status InsertBook(IdxListType &idxlist, int i, int bno) { //算法4.14

NLink p;

if (!MakeNode (p, bno))

return OVERFLOW; // 分配失败

Append(idxlist.item[i].bnolist, p); // 插入新的书号索引 return OK;

} // InsertBook

//------ 基本操作 -------

void InitIdxList(IdxListType &idxlist) {

int i;

idxlist.last= 0;

for(i=0; i<MaxKeyNum+1; i++)

InitList(idxlist.item[i].bnolist);

}

Status ExtractKeyWord(char* Buffer,WordListType &w,int &Num) { int i=0, j=0, k=0;

bool Ignore;

char TempChar[30];

char IgnoreChar[7][10] =

{ "to","of","the","and","not","or","if" };

w.last=0;

while(*(Buffer+i)!= ' ') { TempChar[i]=*(Buffer+i); i++; } i++;

TempChar[i]= '\0';

Num=atoi(TempChar);

while(*(Buffer+i)!='\n' && *(Buffer+i)!='\0') {

// 每个字符串末尾都有作为结束符'\n'

if(*(Buffer+i)!=' ') { // 若非空字符,则把当前字符加入新的字符串中 if(*(Buffer+i)>='A' && *(Buffer+i)<='Z') // 大写字母转换为小写

*(Buffer+i)-='A'-'a';

w.item[j][k]=*(Buffer+i);

k++; i++;

} else { // 如果是空字符,这是则开始另一个字符串 Ignore=false;

w.item[j][k++]='\0';

for (int m=0; m<7; m++)

if(strcmp(w.item[j],IgnoreChar[m])==0)

{ Ignore=true; break; }

27

if (!Ignore) { j++; k=0; i++; w.last++; } else { k=0; i++; }

}

}

w.item[j][k++]='\0'; // 把最后一个字符串收尾

Ignore=false;

for (int m=0; m<7; m++)

if (strcmp(w.item[j],IgnoreChar[m])==0)

{ Ignore=true; break; }

if (!Ignore) w.last++; // 并把最大数加1

return OK;

}

void GetLine(FILE *f) {

fgets(buf, MaxLineLen, f); // buf是全局数组变量

}

Status PutText(FILE *IdxFile, IdxListType MyIdx) { int i,j,k;

NLink p;

for(i=0; i<MyIdx.last; i++) {

for(j=0; j<MyIdx.item[i].key.length; j++)

putc(*(MyIdx.item[i].key.ch+j ),IdxFile);

putc('\t',IdxFile);

if (MyIdx.item[i].key.length < 8) putc('\t',IdxFile); p = MyIdx.item[i].bnolist.head;

for (k=0; k<MyIdx.item[i].bnolist.len; k++) { p = p->next;

fprintf(IdxFile,"%03d",p->data);

putc(' ', IdxFile);

}

putc('\n',IdxFile);

}

return OK;

}

void PrintFile(FILE *FileName) { // 辅助函数

char ch;

rewind(FileName);

ch=getc(FileName);

while (ch!=EOF) {

putchar(ch);

ch=getc(FileName);

}

28

printf("\n");

rewind(FileName);

}

5.1

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

5.2

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

29

5.3

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<M.mu) tp=M.rpos[arow+1];

else tp=M.tu+1;

for (p=M.rpos[arow]; p<tp;++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

5.4

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;

30

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->j<j); q=q->right);

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 <i; q = q->down ); p->down = q->down; q->down = p;

} // 完成列插入

} // for

return OK;

} // CreateSMatrix_OL

5.5

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

31

5.6

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

5.7

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;

32

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

}//if

} while (!StrEmpty(sub));

q->ptr.tp = NULL;

} // else

} // else

return OK;

} // CreateGList

6.1

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

6.2

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;

33

} // InOrderTraverse

6.3

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

6.4

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

6.5

Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType)) {

// 算法6.5

// T指向头结点,头结点的左链lchild指向根结点,头结点的右链lchild指向 // 中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T,

// 对每个数据元素调用函数Visit。

BiThrTree p;

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

34

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

6.6

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

6.7

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

6.8

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

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

35

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

6.9

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

6.10

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

6.11

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;

}

36

return 1;

} // fix_mfset

6.12

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);

37

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

6.13

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;

}

38

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;

39

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

6.15

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

7.1

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

7.2

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);

40

for (i=0; i<G.vexnum; i++ ) {

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

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

getchar();

} // 构造顶点向量

for (i=0; i<G.vexnum; ++i ) // 初始化邻接矩阵

for (j=0; j<G.vexnum; ++j ) {

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

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

}

for (k=0; k<G.arcnum; ++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; // 弧<v1,v2>的权值

// if (IncInfo) scanf(G.arcs[i][j].info); // 输入弧含有相关信息 G.arcs[j][i].adj = G.arcs[i][j].adj; // 置<v1,v2>的对称弧<v2,v1>

}

return OK;

} // CreateUDN

7.3

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<G.vexnum; ++i) { // 构造表头向量

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

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

}

for (k=0; k<G.arcnum; ++k) { // 输入各弧并构造十字链表

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

i=LocateVex(G, v1); j=LocateVex(G, v2); // 确定v1和v2在G中位置

p=(ArcBox *) malloc (sizeof (ArcBox)); // 假定有足够空间

41

// *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

7.4

void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 算法7.4 // 对图G作深度优先遍历。

int v;

VisitFunc = Visit; // 使用全局变量VisitFunc,使DFS不必设函数指针参数 for (v=0; v<G.vexnum; ++v) visited[v] = false; // 访问标志数组初始化

for (v=0; v<G.vexnum; ++v)

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

7.5

//--- 算法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);

}

7.6

void BFSTraverse(Graph G, Status (*Visit)(int v )) {// 算法7.6 // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 QElemType v,w;

queue Q;

QElemType u;

for (v=0; v<G.vexnum; ++v) visited[v] = FALSE;

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

for (v=0; v<G.vexnum; ++v)

42

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

7.7

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

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

int v; int j=0;

CSTree p,q;

T = NULL;

for (v=0; v<G.vexnum; ++v) visited[v] = FALSE;

for (v=0; v<G.vexnum; ++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

7.8

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;

43

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

7.9

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<G.vexnum; ++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<G.vexnum; ++i) { // 选择其余G.vexnum-1个顶点 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<G.vexnum; ++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

7.10

44

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

// 连通图G以邻接表作存储结构,查找并输出G上全部关节点。

// 全局量count对访问计数。

int v;

struct ArcNode *p;

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

for (int i=1; i<G.vexnum; ++i) visited[i] = 0; // 其余顶点尚未访问

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

7.11

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

7.12

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

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

45

// 若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<G.vexnum; ++i) // 建零入度顶点栈S

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<G.vexnum) return ERROR; // 该有向图有回路 else return OK;

} // TopologicalSort

7.13

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<G.vexnum; ++j) // 建零入度顶点栈S

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

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

count = 0;

for(int i=0; i<G.vexnum; i++) ve[i] = 0; // 初始化

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;

46

}//for *(p->info)=dut(<j,k>)

}//while

if (count<G.vexnum) return ERROR; // 该有向网有回路

else return OK;

} // TopologicalOrder

7.14

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<G.vexnum; 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<j,k>

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

}

for (j=0; j<G.vexnum; ++j) // 求ee,el和关键活动 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

7.15

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<G.vexnum; ++v) {

final[v] = FALSE;

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

for (w=0; w<G.vexnum; ++w) P[v][w] = FALSE; // 设空路径 if (D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }

47

}

D[v0] = 0; final[v0] = TRUE; // 初始化,v0顶点属于S集 //--- 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 --- for (i=1; i<G.vexnum; ++i) { // 其余G.vexnum-1个顶点 min = INFINITY; // 当前所知离v0顶点的最近距离 for (w=0; w<G.vexnum; ++w)

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

if (D[w]<min) { v = w; min = D[w]; } // w顶点离v0顶点更近 final[v] = TRUE; // 离v0顶点最近的v加入S集 for (w=0; w<G.vexnum; ++w) // 更新当前最短路径及距离 if (!final[w] && (min+G.arcs[v][w].adj<D[w])) {

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

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

for(j=0;j<G.vexnum;j++) P[w][j] = P[v][j]; //第v行赋值于第w行

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

}//if

}//for

} // ShortestPath_DIJ

7.16

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<G.vexnum; ++v) // 各对结点之间初始已知路径及距离 for (w=0; w<G.vexnum; ++w) {

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

for (u=0; u<G.vexnum; ++u) P[v][w][u] = FALSE;

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

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

}//if

}//for

for (u=0; u<G.vexnum; ++u)

for (v=0; v<G.vexnum; ++v)

for (w=0; w<G.vexnum; ++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<G.vexnum; ++i)

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

}//if

} // ShortestPath_FLOYD

48

8.1

const int e = 16; // 不保留<=e的剩余量

Space AllocBoundTag (Space &pav, int n) { // 算法8.1

// 若有不小于n的空闲块,则分配相应的存储块,并返回其首地址;

// 否则返回NULL。

// 若分配后可利用空间表不空,则pav指向表中刚分配过的结点的后继结点 Space p;

for (p=pav;

p && p->size<n && p->rlink!=pav;

p=p->rlink); // 查找不小于n的空闲块

if (!p || p->size<n) return NULL; // 找不到,返回空指针 else { // p指向找到的空闲块

Space f = FootLoc(p); // 指向底部

pav = p->rlink; // pav指向*p结点的后继结点。 if (p->size-n <= e) { // 整块分配,不保留<=e的剩余量 if (pav==p) pav = NULL; // 可利用空间表变为空表 else { // 在表中删除分配的结点

pav->llink = p->llink; p->llink->rlink = pav;

}

p->tag = f->tag = 1; // 修改分配结点的头部和底部标志 } else { // 分配该块的后n个字

f->tag = 1; // 修改分配块的底部标志

p->size -= n; // 置剩余块大小

f = FootLoc(p); // 指向剩余块底部

f->tag = 0; f->uplink = p; // 设置剩余块底部

p = f+1; // 指向分配块头部

p->tag = 1; p->size = n; // 设置分配块头部

}

return p; // 返回分配块首地址

}

} // AllocBoundTag

8.2

WORD_b* AllocBuddy (FreeList &avail, int n) { // 算法8.2

// avail[0..m]为可利用空间表,n为申请分配量,若有不小于n的空闲块, // 则分配相应的存储块,并返回其首地址;否则返回NULL

WORD_b *pa, *pre, *suc, *pi;

for (int k=0;

k<=m && (!avail[k].first || avail[k].nodesize<n+1); ++k); // 查找满足分配要求的子表 if (k>m) return NULL; // 分配失败,返回NULL else { // 进行分配

pa = avail[k].first; // 指向可分配子表的第一个结点 pre = pa->llink; suc = pa->rlink; // 分别指向前驱和后继

49

if (pa==suc) avail[k].first = NULL; // 分配后该子表变成空表 else { // 从子表删去*pa结点

pre->rlink = suc; suc->llink = pre; avail[k].first = suc; }

for (int i=1; avail[k-i].nodesize>=n+1; ++i) {

pi = pa+(int)pow(2, (k-i)); pi->rlink = pi; pi->llink = pi; pi->tag = 0; pi->kval = k-i; avail[k-i].first = pi; } // 将剩余块插入相应子表

pa->tag = 1; pa->kval = k-(--i);

}

return pa;

} // AllocBuddy

8.3

void MarkList(GList GL) { // 算法8.3

// 遍历非空广义表GL(GL!=NULL且GL->mark==0),

// 对表中所有未加标志的结点加标志

GList q = NULL, p = GL, t = NULL; // t指示p的母表

int finished = FALSE;

while (!finished) {

while (p->mark==0) {

p->mark = 1;

// MarkHead(p)的细化:

q = p->ptr.hp; // q指向*p的表头

if (q && q->mark==0) {

if (q->tag==ATOM) q->mark = 1; // ATOM,表头为原子结点 else // 继续遍历子表

{ p->ptr.hp = t; p->tag = ATOM; t = p; p = q; } }

} // 完成对表头的标志

q = p->ptr.tp; // q指向*p的表尾

if (q && q->mark==0) { // 继续遍历表尾

p->ptr.tp = t; t = p; p = q;

} else { // BackTrack(finished)的细化:

while (t && t->tag==LIST) { // LIST,表结点,从表尾回溯 q = t; t = q->ptr.tp; q->ptr.tp = p; p = q;

}

if (!t) finished = TRUE; // 结束

else { // 从表头回溯

q = t; t = q->ptr.hp; q->ptr.hp = p;

p = q; p->tag = LIST;

} // 继续遍历表尾

}

}

50

} // MarkList

9.1

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

9.2

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

9.3

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) // 选择最小的腜i值 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; // 右子树空

51

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

} // SecondOptimal

9.4

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

9.5a

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

9.5b

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

9.6

Status InsertBST(BiTree &T, ElemType e) { // 算法9.6

// 当二叉排序树T中不存在关键字等于e.key的数据元素时,

52

// 插入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

9.7

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

9.8

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

9.9

53

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

9.10

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

9.11

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

54

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

9.12

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

9.13

void ShowBTNode(BTree p) { //display the BTnode

printf("(");

for(int i=1; i<=p->keynum; i++)

printf("%3d", p->key[i]);

printf(" )");

55

}

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]<=K<p->key[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

9.14

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;

56

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]和

57

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

9.15

RECORD *SearchDLTree(DLTree T, KeysType K) { // 算法9.15 // 在非空双链树T中查找关键字等于K的记录。

DLTree p;

int i;

p = T->first; i=0; // 初始化

while (p && i<K.num) {

while (p && p->symbol != K.ch[i]) // 查找关键字的第i位 p = p->next;

if (p && i<K.num-1) p = p->first; // 准备查找下一位 ++i;

} // 查找结束

if (!p) return NULL; // 查找不成功

else return p->infoptr; // 查找成功

} //Search DLTree

9.16

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<K.num; // *p为分支结点

p=p->bh.ptr[ord(K.ch[i])], i++); // ord求字符在字母表中序号 if (p && p->kind==LEAF && strcmp(p->lf.K.ch, K.ch)==0)

58

return p->lf.infoptr; // 查找成功

else return NULL; // 查找不成功

} // SearchTrie

9.17

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

9.18

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

10.1

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]; // 记录后移

59

L.r[j+1] = L.r[0]; // 插入到正确位置

}

} // InsertSort

10.2

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

10.3

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.length; ++i) {

// SL.r[1..i-1]中记录已按关键字有序排列,

// 第i个记录在SL中的当前位置应不小于i

while (p<i) // 找到第i个记录,并用p指示其在SL中当前位置

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

10.4

60

void ShellInsert(SqList &L, int dk) { // 算法10.4

// 对顺序表L作一趟希尔插入排序。本算法对算法10.1作了以下修改: // 1. 前后记录位置的增量是dk,而不是1;

// 2. r[0]只是暂存单元,不是哨兵。当j<=0时,插入位置已找到。 int i,j;

for (i=dk+1; i<=L.length; ++i)

if (LT(L.r[i].key, L.r[i-dk].key)) { // 需将L.r[i]插入有序增量子表

L.r[0] = L.r[i]; // 暂存在L.r[0]

for (j=i-dk; j>0 && LT(L.r[0].key, L.r[j].key); j-=dk) L.r[j+dk] = L.r[j]; // 记录后移,查找插入位置 L.r[j+dk] = L.r[0]; // 插入

}

} // ShellInsert

10.5

void ShellSort(SqList &L, int dlta[], int t) { // 算法10.5 // 按增量序列dlta[0..t-1]对顺序表L作希尔排序。

for (int k=0; k<t; ++k)

ShellInsert(L, dlta[k]); // 一趟增量为dlta[k]的插入排序 } // ShellSort

10.6a

int Partition(SqList &L, int low, int high) { // 算法10.6(a) // 交换顺序表L中子序列L.r[low..high]的记录,使枢轴记录到位, // 并返回其所在位置,此时,在它之前(后)的记录均不大(小)于它 KeyType pivotkey;

RedType temp;

pivotkey = L.r[low].key; // 用子表的第一个记录作枢轴记录 while (low<high) { // 从表的两端交替地向中间扫描 while (low<high && L.r[high].key>=pivotkey) --high; temp=L.r[low];

L.r[low]=L.r[high];

L.r[high]=temp; // 将比枢轴记录小的记录交换到低端 while (low<high && L.r[low].key<=pivotkey) ++low; temp=L.r[low];

L.r[low]=L.r[high];

L.r[high]=temp; // 将比枢轴记录大的记录交换到高端 }

return low; // 返回枢轴所在位置

} // Partition

10.6b

int Partition(SqList &L, int low, int high) { // 算法10.6(b) // 交换顺序表L中子序列L.r[low..high]的记录,使枢轴记录到位, // 并返回其所在位置,此时,在它之前(后)的记录均不大(小)于它 KeyType pivotkey;

61

L.r[0] = L.r[low]; // 用子表的第一个记录作枢轴记录 pivotkey = L.r[low].key; // 枢轴记录关键字

while (low<high) { // 从表的两端交替地向中间扫描 while (low<high && L.r[high].key>=pivotkey) --high; L.r[low] = L.r[high]; // 将比枢轴记录小的记录移到低端 while (low<high && L.r[low].key<=pivotkey) ++low; L.r[high] = L.r[low]; // 将比枢轴记录大的记录移到高端 }

L.r[low] = L.r[0]; // 枢轴记录到位

return low; // 返回枢轴位置

} // Partition

10.7

void QSort(SqList &L, int low, int high) { //算法10.7

// 对顺序表L中的子序列L.r[low..high]进行快速排序

int pivotloc;

if (low < high) { // 长度大于1

pivotloc = Partition(L, low, high); // 将L.r[low..high]一分为二

QSort(L, low, pivotloc-1); // 对低子表递归排序,pivotloc是枢轴位置

QSort(L, pivotloc+1, high); // 对高子表递归排序 }

} // QSort

10.8

void QuickSort(SqList &L) { // 算法10.8

// 对顺序表L进行快速排序

QSort(L, 1, L.length);

} // QuickSort

10.9

void SelectSort(SqList &L) { // 算法10.9

// 对顺序表L作简单选择排序。

int i,j;

for (i=1; i<L.length; ++i) { // 选择第i小的记录,并交换到位

j = SelectMinKey(L, i); // 在L.r[i..L.length]中选择key最小的记录

if (i!=j) { // L.r[i]←→L.r[j]; 与第i个记录交换 RedType temp;

temp=L.r[i];

L.r[i]=L.r[j];

L.r[j]=temp;

}

}

} // SelectSort

10.10

62

void HeapAdjust(HeapType &H, int s, int m) { // 算法10.10 // 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义, // 本函数调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆

// (对其中记录的关键字而言)

int j;

RedType rc;

rc = H.r[s];

for (j=2*s; j<=m; j*=2) { // 沿key较大的孩子结点向下筛选

if (j<m && H.r[j].key<H.r[j+1].key) ++j; // j为key较大的记录的下标

if (rc.key >= H.r[j].key) break; // rc应插入在位置s上 H.r[s] = H.r[j]; s = j;

}

H.r[s] = rc; // 插入

} // HeapAdjust

10.11

void HeapSort(HeapType &H) { // 算法10.11

// 对顺序表H进行堆排序。

int i;

RedType temp;

for (i=H.length/2; i>0; --i) // 把H.r[1..H.length]建成大顶堆 HeapAdjust ( H, i, H.length );

for (i=H.length; i>1; --i) {

temp=H.r[i];

H.r[i]=H.r[1];

H.r[1]=temp; // 将堆顶记录和当前未经排序子序列Hr[1..i]中 // 最后一个记录相互交换

HeapAdjust(H, 1, i-1); // 将H.r[1..i-1] 重新调整为大顶堆 }

} // HeapSort

10.12

void Merge (RedType SR[], RedType TR[], int i, int m, int n) { // 算法10.12

// 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]

int j,k;

for (j=m+1, k=i; i<=m && j<=n; ++k) {

// 将SR中记录由小到大地并入TR

if LQ(SR[i].key,SR[j].key) TR[k] = SR[i++];

else TR[k] = SR[j++];

}

if (i<=m) // TR[k..n] = SR[i..m]; 将剩余的SR[i..m]复制到TR while (k<=n && i<=m) TR[k++]=SR[i++];

if (j<=n) // 将剩余的SR[j..n]复制到TR

while (k<=n &&j <=n) TR[k++]=SR[j++];

63

} // Merge

10.13

void MSort(RedType SR[], RedType TR1[], int s, int t) { // 算法10.13

// 将SR[s..t]归并排序为TR1[s..t]。

int m;

RedType TR2[20];

if (s==t) TR1[t] = SR[s];

else {

m=(s+t)/2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t] MSort(SR,TR2,s,m); // 递归地将SR[s..m]归并为有序的TR2[s..m] MSort(SR,TR2,m+1,t); // 将SR[m+1..t]归并为有序的TR2[m+1..t] Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]

}

} // MSort

10.14

void MergeSort(SqList &L) { // 算法10.14

// 对顺序表L作归并排序。

MSort(L.r, L.r, 1, L.length);

} // MergeSort

10.15

void Distribute(SLList &L, int i, ArrType &f, ArrType &e) { // 算法10.15

// 静态链表L的r域中记录已按(keys[0],...,keys[i-1])有序,

// 本算法按第i个关键字keys[i]建立RADIX个子表,

// 使同一子表中记录的keys[i]相同。f[0..RADIX-1]和e[0..RADIX-1] // 分别指向各子表中第一个和最后一个记录。

int j, p;

for (j=0; j<RADIX; ++j) f[j] = 0; // 各子表初始化为空表 for (p=L.r[0].next; p; p=L.r[p].next) {

j = L.r[p].keys[i]-'0'; // 将记录中第i个关键字映射到[0..RADIX-1], if (!f[j]) f[j] = p;

else L.r[e[j]].next = p;

e[j] = p; // 将p所指的结点插入第j个子表中

}

} // Distribute

10.16

void Collect(SLList &L, int i, ArrType f, ArrType e) { // 算法10.16 // 本算法按keys[i]自小至大地将f[0..RADIX-1]所指各子表依次链接成 // 一个链表,e[0..RADIX-1]为各子表的尾指针

int j,t;

for (j=0; !f[j]; j++); // 找第一个非空子表,succ为求后继函数: ++ L.r[0].next = f[j]; // L.r[0].next指向第一个非空子表中第一个结点

64

t = e[j];

while (j<RADIX) {

for (j=j+1; j<RADIX && !f[j]; j++); // 找下一个非空子表 if (j<RADIX) // 链接两个非空子表

{ L.r[t].next = f[j]; t = e[j]; }

}

L.r[t].next = 0; // t指向最后一个非空子表中的最后一个结点 } // Collect

10.17

void RadixSort(SLList &L) { // 算法10.17

// L是采用静态链表表示的顺序表。

// 对L作基数排序,使得L成为按关键字自小到大的有序静态链表,

// L.r[0]为头结点。

int i;

ArrType f, e;

for (i=1; i<L.recnum; ++i) L.r[i-1].next = i;

L.r[L.recnum].next = 0; // 将L改造为静态链表

for (i=0; i<L.keynum; ++i) {

// 按最低位优先依次对各关键字进行分配和收集

Distribute(L, i, f, e); // 第i趟分配

Collect(L, i, f, e); // 第i趟收集

print_SLList2(L, i);

}

} // RadixSort

10.18

void Rearrange(SqList &L, int adr[]) {// 算法 10.18

// adr给出顺序表L的有序次序,即L.r[adr[i]]是第i小的记录。

// 本算法按adr重排L.r,使其有序。

int i,j,k;

for (i=1; i<L.length; ++i)

if (adr[i]!=i) { // 第i小的记录未按序到位

j = i; L.r[0] = L.r[i]; // 暂存记录L.r[i]

while (adr[j]!=i) { // 调整L.r[adr[j]]的记录到位直到adr[j]=i为止

k = adr[j]; L.r[j] = L.r[k];

adr[j] = j; j = k;

}

L.r[j] = L.r[0]; adr[j] = j; // 记录按序到位

}

} // Rearrange

11.1

void K_Merge (LoserTree &ls, External &b) { // 算法11.1

// 利用败者树ls将编号从0到k-1的k个输入归并段中的记录归并到输出归并段。

65

// b[0]至b[k-1]为败者树上的k个叶子结点,分别存放k个输入归并段中当前记 // 录的关键字

int i, q;

for (i=0; i<k; ++i) input(b[i].key, i); //分别从k个输入归并段读入该段

// 当前第一个记录的关键字到外结点 CreateLoserTree(ls); // 建败者树ls,选得最小关键字为b[ls[0]].key while (b[ls[0]].key != MAXKEY) {

q = ls[0]; // q指示当前最小关键字所在输入归并段

output(q); // 将编号为q的输入归并段中当前(关键字为b[q].key)的 // 记录写至输出归并段

input(b[q].key, q); // 从编号为q的输入归并段读入下一个记录的关键字 Adjust(ls, q); // 调整败者树,选择新的最小关键字

}

output(ls[0]); // 将含最大关键字MAXKEY的记录写至输出归并段 } // K_Merge

11.2

void Adjust(LoserTree &ls, int s) { // 算法11.2

// 沿从叶子结点b[s]到根结点ls[0]的路径调整败者树。

int t, temp;

t = (s+k)/2; // ls[t]是b[s]的双亲结点

while (t>0) {

if (b[s].key > b[ls[t]].key) {

temp = s; s = ls[t]; ls[t] = temp; // s指示新的胜者 }

t /= 2;

}

ls[0] = s;

} // Adjust

11.3

void CreateLoserTree(LoserTree &ls) { // 算法11.3

// 已知b[0]到b[k-1]为完全二叉树ls的叶子结点存有k个关键字,

// 沿从叶子到根的k条路径将ls调整成为败者树

int i;

b[k].key = MINKEY; // 设MINKEY为关键字可能的最小值 for (i=0; i<k; ++i) ls[i] = k; // 设置ls中"败者"的初值 for (i=k-1; i>=0; --i) Adjust(ls, i);

// 依次从b[k-1],b[k-2],...,b[0]出发调整败者

} // CreateLoserTree

11.4

void Replace_Selection(LoserTree &ls, WorkArea &wa,

FILE *fi, FILE *fo) { // 算法11.4

// 在败者树ls和内存工作区wa上用置换-选择排序求初始归并段,fi为输入文 // 件(只读文件)指针,fo为输出文件(只写文件)指针,两文件均已打开

66

RcdType RUNEND_SYMBOL; // 段结束标志

RUNEND_SYMBOL.key=MAXKEY;

Construct_Loser (ls, wa); // 初建败者树

rc = rmax = 1; // rc指示当前生成的初始归并段的段号,

// rmax指示wa中关键字所属初始归并段的最大段号 while (rc <= rmax) { // "rc=rmax+1"标志输入文件的置换-选择排序已完成

get_run(ls, wa); // 求得一个初始归并段

fwrite(&RUNEND_SYMBOL, sizeof(RcdType), 1, fo);

// 将段结束标志写入输出文件

rc = wa[ls[0]].rnum; // 设置下一段的段号

}

} // Replace_Selection

11.5

void get_run(LoserTree &ls, WorkArea &wa) { // 算法11.5 // 求得一个初始归并段,fi为输入文件指针,fo为输出文件指针

while (wa[ls[0]].rnum == rc) { // 选得的MINIMAX记录属当前段时 int q = ls[0]; // q指示MINIMAX记录在wa中的位置 minimax = wa[q].key;

fwrite(&(wa[q].rec), sizeof(RcdType), 1, fo);

// 将刚选的MINIMAX记录写入输出文件

if (fread(&wa[q].rec, sizeof(RcdType), 1, fi)==1) { // 从输入文件读下一记录

wa[q].key = wa[q].rec.key; // 提取关键字

if (wa[q].key < minimax) { // 新读入的记录属下一段 rmax = rc + 1; wa[q].rnum = rmax;

} else wa[q].rnum = rc; // 新读入的记录属当前段

} else // 当文件读取不成功或输入文件结束时,虚设记录(属"rmax+1"段) { wa[q].rnum = rmax+1; wa[q].key = MAXKEY; }

Select_MiniMax (ls, wa, q); // 选择新的MINIMAX记录 }

} // get_run

11.6

void Select_MiniMax (LoserTree &ls, WorkArea wa, int q) { // 算法11.6

//从wa[q]起到败者树的根比较选择MINIMAX记录,并由q指示它所在的归并段 int t, p, temp;

for (t=(w+q)/2, p=ls[t]; t>0; t/=2, p=ls[t])

if (wa[p].rnum<wa[q].rnum ||

(wa[p].rnum==wa[q].rnum && wa[p].key<wa[q].key)) { temp=q; q=ls[t]; ls[t]=temp; // q指示新的胜利者

}

ls[0] = q;

} // Select_MiniMax

67

11.7

void Construct_Loser(LoserTree &ls, WorkArea &wa) { // 算法11.7 // 输入w个记录到内存工作区wa,建得败者树ls,

// 选出关键字最小的记录并由s指示其在wa中的位置

int i;

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

wa[i].rnum = wa[i].key = ls[i] = 0; // 工作区初始化

}

for (i=w-1; i>=0; --i) {

fread(&wa[i].rec, sizeof(RcdType), 1, fi); // 输入一个记录 wa[i].key = wa[i].rec.key; // 提取关键字

wa[i].rnum = 1; // 其段号为"1"

Select_MiniMax (ls, wa, i); // 算法11.6,调整败者

}

} // Construct_Loser

12.1

Status MergeFile (FILE *f, FILE *g, FILE *h) { // 算法12.1 // 由按关键字递增有序的非空顺序文件f和g归并得到新文件h,三个文件均 // 已打开,其中,f和g为只读文件,文件中各附加一个最大关键字记录, // 且g文件中对该记录的操作为插入。h为只写文件

RcdType fr, gr;

fread(&fr, sizeof(RcdType), 1, f);

fread(&gr, sizeof(RcdType), 1, g);

while (!feof(f) || !feof(g)) {

if (fr.key < gr.key) { // 复制"旧"主文件中记录 fwrite(&fr, sizeof(RcdType), 1, h);

/*if (!feof(f))*/ fread(&fr, sizeof(RcdType), 1, f); } else if (gr.code=='D' && fr.key==gr.key) {

// 删除"旧"主文件中记录,即不复制

/*if (!feof(f))*/ fread(&fr, sizeof(RcdType), 1, f); /*if (!feof(g))*/ fread(&gr, sizeof(RcdType), 1, g); } else if (gr.code=='I' && fr.key>gr.key) {

// 插入,函数P把gr加工为h的结构

fwrite(P(gr), sizeof(RcdType), 1, h);

/*if (!feof(g))*/ fread(&gr, sizeof(RcdType), 1, g); } else if (gr.code=='U' && fr.key==gr.key) {

// 更改"旧"主文件中记录

fwrite(Q(fr, gr), sizeof(RcdType), 1, h);

// 函数Q将fr和gr归并成一个h结构的记录

/*if (!feof(f))*/ fread(&fr, sizeof(RcdType), 1, f); /*if (!feof(g))*/ fread(&gr, sizeof(RcdType), 1, g); } else return ERROR; // 其它均为出错情况

} // while

return OK;

68

} // MergeFile

69

相关推荐