英文版数据结构算法题.doc

《英文版数据结构算法题.doc》由会员分享，可在线阅读，更多相关《英文版数据结构算法题.doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1. Suppose we have a linked list.Eack node has three parts: one data field and two linked fields.The list has been linked by the first linked field link1,but the list is disorder.Try your best to sort the list with the second linked field into an increasing list.算法:int creasort(struct node &head)if

2、(head1 = NULL)/没有结点return ERROR;head2 = head1;/设排列链表的第一个结点head2-link2 = NULL;p = head1-link1;/p为链表的第二个结点q = head;/q代表p插入位置的前一个结点if (!p)/只有一个结点return OK;while (p)while ( q-link2 & (q-link2-data data)/找查找入位置q = q-link2;if (!q-link2)/插在最后q-link2 = p;else /插在队列中间p-link2 = q-link2;q-link2 = p;p = p-link1

3、;q = head;return OK;2. Suppose we have a sequence with the terminal character .The format of the sequence can be S1&S2,S1 and S2 do not contain &, S2 is the reverse sequence of S1.Try to write an algorithm to check the sequence if the format of the sequence obeys the above fules then the function re

4、turn TRUE otherwise FALSE.算法:/s为待检查的字符串int checkrules(char *s)len = strlen(s);/用string.h自带函数取字符串s的长度if (len % 2 = 0)/字符串是偶数return FALSE;i = 0;/i指向字符串第一个字符n = len - 1;/n指向字符串最后一个字符while (i L.data)/无效的访问return;p = &L;/定位，p指向已经访问的指针while(x-)p = p-next;p-freq+;/因为形参L不在循环链表里，因此要用L.pre-next表示循环链表的头结点while

5、 (p-pre -freq freq & p-pre != L.pre-next)p-data p-pre-data;p-freq p-pre-freq;4. Suppose we have a disordered list of integers.The list has been stored in a stack. You are supposed to sort the list with queue.算法:/表示将from队的元素倒到to中void QueToQue(Queue *from, Queue *to, int ns)tag = 0;/用于标注要排列的数是否进栈while

6、 (!QueueEmpty(from)DeQueue(from, &nq);/nq用于存取出队元素if (tag = 0 & nq ns) | tag = 1)/不能入队EnQueue(to, nq);else/可以入队了tag = 1;/设置标志tag为1，表示已经入队了EnQueue(to, ns);EnQueue(to, nq);if (tag = 0)/当ns比队中任何数都大时EnQueue(to, ns);/将队列from中的元素倒到to栈中void QueToStack(Queue *from, Stack *to)while (!QueueEmpty(from)DeQueue(f

7、rom, &nq);Push(to, nq);/排序的本体void sort(Stack *S)InitQueue(&Q1);InitQueue(&Q2);/初始化两个队列Q1,Q2Pop(S, &ns); EnQueue(&Q1, ns);/先将一个元素出队进栈while (!StackEmpty(S)Pop(S,&ns);if (!QueueEmpty(&Q1)/若Q1队列不空(即Q2队列为空)QueToQue(&Q1, &Q2, ns);else/若Q2队列为空（即Q1队列不为空）QueToQue(&Q2, &Q1, ns);if (!QueueEmpty(&Q1)/Q1不为空，也就是要

8、把Q1队载入栈QueToStack(&Q1, S);elseQueToStack(&Q2, S);5. 颜色排列的算法:/colors是颜色数组，number是数组大小void colorsort(int *colors, int number)i = 0, j = number 1;while (colorsi = 1)/找到第一个非1的单元i+;while (colorsj = 3)/找到最后一个非3的单元j-;k = i;/遍历指针设为iwhile(k = j)switch (colorsk)case 1: colorskcolorsi;i+; k+;break;case 2: k+;break;case 3: colorskcolorsj;j-;break;第 7 页