【算法数据结构总结 5400字】范文118

算法数据结构总结

来源:m.fanwen118.com时间:2023.3.11

**大学

算法与数据结构课程设计

课程：

专业：

班级：

学号：

姓名： **

2010 年 11 月 18日

本次算法与数据结构实践课中我们小组主要选择了两个课题，一个是迷宫的创建及求解问题，另一个是停车场管理系统问题，还选做了一个敢死队的问题。

在迷宫创建及求解这个问题中，我主要负责的是求解迷宫这个模块。迷宫求解采用的是课本中的回溯法，其求解过程就是沿着一个方向进行探索，若能走通，则继续向前走；否则原路返回，换一个方向在进行探索，直到找到了出口，或者所有可能的探索都失败而告终。

在探索过程中，可以用一个栈来保存探索的序列。其算法框架如下：

创建一个（保存探索过程的）空栈：

把入口位置压入栈中：

While 栈不空时{

取栈顶位置并设置为当前位置；

While 当前位置存在试探可能{

取下一个试探位置；

If（下一个位置是出口）

打印栈中保存的探索过程然后返回

If （下一个位置是通道）

把下一个位置进栈并且设置为当前位置；

}

这个模块在程序中对应的代码段是：

Status InitStack(Stack *s) /*创建栈s并初始化为空栈*/ {

s->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); /*分配内存空间*/

if(!s->base) Error("Overflow");

s->top=s->base;

s->stacksize=STACK_INIT_SIZE;

return OK;

}

Status DestroyStack(Stack *s) /*销毁栈*/

{

s->top=NULL;

s->stacksize=0;

free(s->base);

s->base=NULL;

return OK;

}

Boolean StackEmpty(Stack *s) /*核对栈是否为空栈*/

{

if(s->top==s->base) return TRUE;

else return FALSE;

}

int StackLength(Stack *s) /*得到栈的长度*/ {

if(s->top>s->base) return (int)(s->top-s->base);

else return 0;

}

Status Push(Stack *s,SElemType e) /*入栈*/

{

if(s->top-s->base>=s->stacksize)

{

s->base=(SElemType *)realloc(s->base,

(s->stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!s->base) Error("Overflow");

s->top=s->base+s->stacksize;

s->stacksize+=STACKINCREMENT;

}

*s->top++=e;

return OK;

}

SElemType Pop(Stack *s,SElemType e) /*出栈*/

{

if(s->top==s->base) Error("Pop");

e=*--s->top;

return e;

}

Status GetTop(Stack *s,SElemType *e) /*e置到栈顶*/ {

if(s->top==s->base) Error("GetTop");

*e=*(s->top-1);

return OK;

}

Boolean Pass(PosType curpos) /*检测目前位置是否可通*/ {

if(maze[curpos.x][curpos.y].td==1&&

maze[curpos.x][curpos.y].foot==0&&maze[curpos.x][curpos.y].mark==0) return TRUE;

else return FALSE;

}

void MarkPrint(PosType seat) /*标记位置*/

{

maze[seat.x][seat.y].mark=-1;

}

void FootPrint(PosType curpos)

{

maze[curpos.x][curpos.y].foot=1;

}

PosType NextPos(PosType seat,int di)

{

switch(di)

{

case 1: seat.y++; return seat; /* 下方向 */

case 2: seat.x++; return seat; /* 右方向 */

case 3: seat.y--; return seat; /* 上方向 */

case 4: seat.x--; return seat; /* 左方向 */

default: seat.x=0; seat.y=0; return seat;

}

在停车场管理系统这个问题中我主要负责的模块是停车场及便道里面车辆信息显示这个模块。这个模块分为一个大模块，两个子模块。其中大模块是显示列表的选择选项的模块，会调用两个子模块。两个子模块的功能分别是显示停车场里面的车辆的信息以及显示便道里德车辆的信息。

这个模块的的大致的流程图如下：

算法数据结构总结

这个模块的在程序中对应的代码段是：

//////////////////////////////////////////////////*列表的显示信息*/

void List1(SeqStackCar *s)

{

int i;

if(s->top>0)

{

printf("\n停车场");

printf("\n位置到达时间车牌号\n");

for(i=1;i<=s->top;i++)

{

printf("%d%7d:%d ", i, s->stack[i]->reach.hour, s->stack[i]->reach.min); puts(s->stack[i]->num);

}

else

printf("\n停车场里没车");

}

/////////////////////////////////////*便道里的信息*/

void List2(LinkQueueCar *w)

{

QueueNode *p;

p=w->front->next;

if(w->front!=w->rear)

{

printf("\n便道里等待的车辆的号码为：");

while(p!=NULL)

{

puts(p->data->num);

p=p->next;

}

else

printf("\n便道里没有车。");

}

//////////////////////////////////////////////////////

void List(SeqStackCar s,LinkQueueCar w)

{

int flag,m;

flag=1;

while(flag)

{

printf("\n请选择 1 2 3");

printf("\n1.停车场 2.便道 3.返回\n");

while(1)

{

scanf("%d",&m);

if(m>=1&&m<=3)

{

break;

}

else

printf("输入错误！请重新选择！");

}

switch(m)

{

case 1: List1(&s);

break;

case 2: List2(&w);

break;

case 3: flag=0;

break;

default:

break;

}

在停车场这个程序中，显示列表这个模块中界面显示中给出的是3个选项，在最开始的时候没有注意的一个问题:如果输入的不是三个选项中的任何一个，程序不会报错，也不会继续往下进行。后来在程序中加入了一个判断语句，如果输入的不是选项中的任何一个程序会报错，从而解决了这个问题。

敢死队问题其实就是一个约瑟夫问题，这个问题可以采用遍历或者逆推的方式。遍历就是把所有的队员都当做1号求解一遍，然后吧符合要求的打印出来。逆推就是从一号开始进行一次约瑟夫求解，然后逆推出从几号开始队长最后一个出列，最后打印出来。遍历的方法简单易懂，但是时间复杂度比较高；而逆推的方法时间复杂度稍微低了一点，但是有一点难懂。

算法与数据结构课程设计个人心得

我认为，在算法与数据结构实践课中，在收获知识的同时，还收获了阅历，收获了成熟，在此过程中，我们通过查找大量资料，请教老师，以及不懈的努力，不仅培养了独立思考、动手操作的能力，在各种其它能力上也都有了提高。更重要的是，在实验课上，我们学会了很多学习的方法。而这是日后最实用的，真的是受益匪浅。要面对社会的挑战，只有不断的学习、实践，再学习、再实践。

在选题发面，我们小组选择了迷宫求解问题和停车场管理问题，在经历了多次失败、种种尝试后，最终调试通过了满足题目要求的程序。这些都是一种锻炼，一种知识的积累，能力的提高。完全可以把这个当作基础东西，只有掌握了这些最基础的，才可以更进一步，取得更好的成绩。很少有人会一步登天吧。永不言弃才是最重要的。

而且，这对于我们的将来也有很大的帮助。以后，不管有多苦，我想我们都能变苦为乐，找寻有趣的事情，发现其中珍贵的事情。就像中国提倡的艰苦奋斗一样，我们都可以在实验

结束之后变的更加成熟，会面对需要面对的事情。

程序虽然都调试通过了，但是其中还是有一些瑕疵，比如说迷宫程序并没有满足题目要求的方式来显示迷宫路径，虽然并没有做到最好，但是，最起码我们没有放弃，它是我们的骄傲！相信以后我们会以更加积极地态度对待我们的学习、对待我们的生活。我们的激情永远不会结束，相反，我们会更加努力，努力的去弥补自己的缺点，发展自己的优点，去充实自己，只有在了解了自己的长短之后，我们会更加珍惜拥有的，更加努力的去完善它，增进它。只有不断的测试自己，挑战自己，才能拥有更多的成功和快乐！快乐至上，享受过程，而不是结果！认真对待每一个实验，珍惜每一分一秒，学到最多的知识和方法，锻炼自己的能力，这个是我们在算法与数据结构实践课上学到的最重要的东西，也是以后都将受益匪浅的！

与队友的合作更是一件快乐的事情，只有彼此都付出，彼此都努力维护才能将作品做的更加完美。而团队合作也是当今社会最提倡的。以后工作以后所有的问题都不可能靠一个人来完成，在实践课中通过团队来完成任务也是对我们团队合作能力的一种锻炼。通过这次实践我在学习专业知识发面的收获如下

1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。

2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。

3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。

根据我在实习中遇到得问题，我将在以后的学习过程中注意以下几点：

1、认真上好专业实验课，多在实践中锻炼自己。

2、写程序的过程中要考虑周到，严密。

3、在做设计的时候要有信心，有耐心，切勿浮躁。

4、认真的学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。

5、在课余时间里多写程序，熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。

另外，在这个实践课中我还担任了评委，在认真听取了所有同学的报告后，我发现所有的问题都会有不同的切入点，有不同的实现方法。这也让我明白了发散思维的重要性，以后再遇到问题时，可以从不同的角度入手，说不定会取到预想不到的效果。

总之，这次实践课我们受益颇多，在以后的学习实践以及生活中我们要多使用这次实践课中得到的经验，多避免这次实践课中出现的失误，我们相信我们一定能做的更好！

08级计算机2班

08060102**

第二篇：数据结构算法总结 88200字

算法总结

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

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

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个元素不存在

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;

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

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

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

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;

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

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

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

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

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

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

}

3.4

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

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); //将编号为１的圆盘从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); }

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

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

}

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

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)

*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)。

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

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; // 存放书号索引的链表

} 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; // 索引表

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

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

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;

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

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

}

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

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;

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

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

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;

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

}//if

} while (!StrEmpty(sub));

q->ptr.tp = NULL;

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

} // 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指向根结点

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所在子集的根

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;

}

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

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;

}

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

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

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)); // 假定有足够空间

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

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;

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

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采用邻接表存储结构。

// 若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;

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

}

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

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; // 分别指向前驱和后继

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;

} // 继续遍历表尾

}

} // 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; // 右子树空

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的数据元素时，

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

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

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

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

}

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;

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

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)

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

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

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;

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

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++];

} // 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指向第一个非空子表中第一个结点

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个输入归并段中的记录归并到输出归并段。

// 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为输出文件（只写文件）指针，两文件均已打开

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

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;

} // MergeFile

＋更多类似范文
┣ 数据结构与算法总结 4100字
┣ 数据结构与算法总结 3000字
┣ 数据结构与算法总结 3000字
┣ 数据结构与算法总结1 2500字
┣ 更多数据结构算法总结
┗ 搜索类似范文

相关推荐

电脑看范文

算法数据结构总结

专栏推荐