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、(head.link1 = NULL)/沒有結(jié)點(diǎn)return ERROR;head.link2 = head.link1;/設(shè)排列鏈表的第一個(gè)結(jié)點(diǎn)head.link2-link2 = NULL;p = head.link1-link1;/p為鏈表的第二個(gè)結(jié)點(diǎn)q = head;/q代表p插入位置的前一個(gè)結(jié)點(diǎn)if (!p)/只有一個(gè)結(jié)點(diǎn)return OK;while (p)while ( q-link2 & (q-link2-data data)/找查找入位置q = q-link2;if (!q-link2)/插在最后q-link2 = p;else /插在隊(duì)列中間p-link2 = q-link

3、2;q-link2 = p;p = p-link1;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 f

4、ules then the function return TRUE otherwise FALSE.算法:/s為待檢查的字符串int checkrules(char *s)len = strlen(s);/用string.h自帶函數(shù)取字符串s的長度if (len % 2 = 0)/字符串是偶數(shù)return FALSE;i = 0;/i指向字符串第一個(gè)字符n = len - 1;/n指向字符串最后一個(gè)字符while (i L.data)/無效的訪問return;p = &L;/定位，p指向已經(jīng)訪問的指針while(x-)p = p-next;p-freq+;/因?yàn)樾螀不在循環(huán)鏈表里，因此要用

5、L.pre-next表示循環(huán)鏈表的頭結(jié)點(diǎn)while (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隊(duì)的元素倒到to中void QueToQue(Queue *from, Queue *to, int ns)ta

6、g = 0;/用于標(biāo)注要排列的數(shù)是否進(jìn)棧while (!QueueEmpty(from)DeQueue(from, &nq);/nq用于存取出隊(duì)元素if (tag = 0 & nq ns) | tag = 1)/不能入隊(duì)EnQueue(to, nq);else/可以入隊(duì)了tag = 1;/設(shè)置標(biāo)志tag為1，表示已經(jīng)入隊(duì)了EnQueue(to, ns);EnQueue(to, nq);if (tag = 0)/當(dāng)ns比隊(duì)中任何數(shù)都大時(shí)EnQueue(to, ns);/將隊(duì)列from中的元素倒到to棧中void QueToStack(Queue *from, Stack *to)while (!

7、QueueEmpty(from)DeQueue(from, &nq);Push(to, nq);/排序的本體void sort(Stack *S)InitQueue(&Q1);InitQueue(&Q2);/初始化兩個(gè)隊(duì)列Q1,Q2Pop(S, &ns); EnQueue(&Q1, ns);/先將一個(gè)元素出隊(duì)進(jìn)棧while (!StackEmpty(S)Pop(S,&ns);if (!QueueEmpty(&Q1)/若Q1隊(duì)列不空(即Q2隊(duì)列為空)QueToQue(&Q1, &Q2, ns);else/若Q2隊(duì)列為空（即Q1隊(duì)列不為空）QueToQue(&Q2, &Q1, ns);if (!QueueEmpty(&Q1)/Q1不為空，也就是要把Q1隊(duì)載入棧QueToStack(&Q1, S);elseQueToStack(&Q2, S);5. 顏色排列的算法:/colors是顏色數(shù)組，number是數(shù)組大小void colorsort(int *colors, int number)i = 0, j = number 1;while (colorsi = 1)/找到第一個(gè)非1的單元i+;while (colorsj = 3)/找到最后一個(gè)非3的單元j-;k =