对n个桶中不同颜色的砾石进行排序(页 1) - 数据结构与算法

jfo 发表于 2007-7-13 21:25

对n个桶中不同颜色的砾石进行排序

算法思路，对顺序表进行排序操作。 设计内容及分析过程： 在此设立三个指针分别为s,p和q，其中s指向线性表的L.elem[0]，即第一个元素，p=s+1，即p指向线性表的第二个元素L.elem[1]，q指向线性表的最后一个元素。 查找时，当指针p不等于q时，首先判断s所指向的元素是否为’a’，如果是，则s指针向后滑一个位置，同时p指针也向后滑一个位置。然后判断q所指向的元素是否为’c’，如果是，则q指针向前滑一个位置。 如果指针s所指向的元素为’c’时,则与指针q所指向的元素交换，指针s的位置不变，q指针向前滑一个位置，如果指针q所指向的元素为’a’时,则与指针s所指向的元素交换，指针q的位置不变，s指针向后滑一个位置，同时，p指针也向后滑一个位置。如此循环下去，直到指针p等于q时，退出循环。 该程序实现了对n个桶中不同颜色的砾石进行排序，而且在查找过程中对每粒砾石的颜色只观察了一次. 提示：以上“a”、“c”表示不同的颜色。 帮忙给个源程序我研究

HJin 发表于 2007-7-14 16:09

回复：（jfo）对n个桶中不同颜色的砾石进行排序

/*--------------------------------------------------------------------------- File name: stones.cpp Author: HJin (email: fish_sea_bird [at] yahoo [dot] com ) Created on: 7/14/2007 00:35:35 Environment: Windows XP Professional SP2 English + Visual Studio 2005 v8.0.50727.762
 Modification history: ===========================================================================
 Problem statement: --------------------------------------------------------------------------- 对n个桶中不同颜色的砾石进行排序算法思路，对顺序表进行排序操作。 设计内容及分析过程：
在此设立三个指针分别为s,p和q，其中s指向线性表的L.elem[0]，即第一个元素，p=s+1， 即p指向线性表的第二个元素L.elem[1]，q指向线性表的最后一个元素。
查找时，当指针p不等于q时，首先判断s所指向的元素是否为’a’，如果是，则s指针向后 滑一个位置，同时p指针也向后滑一个位置。然后判断q所指向的元素是否为’c’，如果是， 则q指针向前滑一个位置。
如果指针s所指向的元素为’c’时,则与指针q所指向的元素交换，指针s的位置不变，q指针 向前滑一个位置，如果指针q所指向的元素为’a’时,则与指针s所指向的元素交换，指针q 的位置不变，s指针向后滑一个位置，同时，p指针也向后滑一个位置。如此循环下去，直到 指针p等于q时，退出循环。
该程序实现了对n个桶中不同颜色的砾石进行排序，而且在查找过程中对每粒砾石的颜色只 观察了一次. 
提示：以上“a”、“c”表示不同的颜色。
帮忙给个源程序我研究
 Analysis: --------------------------------------------------------------------------- Here is a modified verion of my code which handle 3 colors --- I wrote that code a few years ago. In your case, only two colors are required, so it is easier.
I am not using a list, instead I am using an array. You should be able to rewrite it for your own task.
I did not test boundary cases, such as the case all the colors are a.
Sample output: ---------------------------------------------------------------------------
Please input a number n (n>0): 23 The oringinal matrix is: c c a a a a c c a c a a c c c a c c a c a a a ---------------------------------------------------------------------- The arranged matrix is: a a a a a a a a a a a a c c c c c c c c c c c Press any key to continue . . .
 Reference: ---------------------------------------------------------------------------
1. 对n个桶中不同颜色的砾石进行排序 <a href="http://bbs.bc-cn.net/viewthread.php?tid=155209" target="_blank" >http://bbs.bc-cn.net/viewthread.php?tid=155209</A>
 */
#include <iostream> #include <algorithm> #include <iterator> #include <ctime> using namespace std;
/** arrange the two colors so that color a sits on the left, color c sits on the right.
Time complexity is O(n), space complexity is O(1). Thus it is the best algorithm one could have. */ void arrangeAC(char*a, int n);
void swap(char& i, char& j);
// randome generator for an array consisting of colors a and c. void randomGenerator(char* arr, int size);
 int main(int argc, char** argv) { // prepare the array int kSize; cout<<"Please input a number n (n>0): "; cin>>kSize;
 char *a = new char[kSize]; randomGenerator(a, kSize);
 cout<<"The oringinal matrix is:\n"; copy(a, a+kSize, std::ostream_iterator<char>(cout, " ")); cout<<endl; cout<<"----------------------------------------------------------------------\n";
 arrangeAC(a, kSize);
 cout<<"The arranged matrix is:\n"; copy(a, a+kSize, std::ostream_iterator<char>(cout, " ")); cout<<endl;
 delete [] a;
 return 0; }
void arrangeAC(char *a, int n) { /** These 3 variables are the 3 pointers of your case. */ int aMarker = 0; int cMarker = n-1; int i = 1;
 // on the left of a marker, all colors are a while ( a[aMarker] == 'a' ) { ++aMarker; }
 // on the right of c marker, all colors are c while ( a[cMarker] == 'c') { --cMarker; }
 i = aMarker+1; while (i <= cMarker) { if(a[i] == 'a') { if( i > aMarker ) { swap(a[i], a[aMarker]); ++aMarker; } else ++i; } else { swap(a[i], a[cMarker]); --cMarker; } } }
void swap(char& i, char& j) { char temp = i; i = j; j = temp; }
void randomGenerator(char* arr, int size) { srand(time(NULL));
 for(int i=0; i<size; ++i) { arr[i] = ( (rand() | (rand()<<16) ) % 2 == 0 ? 'a' : 'c'); } }

jfo 发表于 2007-7-14 20:33

回复：（HJin）回复：（jfo）对n个桶中不同颜色的砾石...

thanks to you 要是我哪天有这么厉害就好啦~~ 再次感谢楼上朋友给出的解

xujianwen 发表于 2008-7-7 13:33

上面要求是用顺序表形式编辑程序，并不是用数组形式呀，哪位大虾能用顺序表形式表现出来不？

页: [1]