題目概述:

長(zhǎng)度為n的環(huán)狀串有n種表示法， 字典序最小的稱為最小表示。輸入一個(gè)長(zhǎng)度為n(n<100)的環(huán)狀字符串的一種表示方法，輸出最小表示 。
如：CTCC 為環(huán)狀字符串的一種表示方法，它的所有表示方法分別為：CTCC、TCCC、CCCT、CCTC。其中最小表示為CCCT。

儲(chǔ)備知識(shí)：

字典序：

字典序：按字典順序從兩個(gè)字符串的第一位開始比較，字典順序靠前的串較小。若兩串前n個(gè)字母都相同，但串A長(zhǎng)于串B，則串B小。
如：ABCD小于BCDA

思路：

將序列放入無(wú)頭指針循環(huán)鏈表(一定是無(wú)頭指針的鏈表，否則判每次遍歷都需跳過頭指針，非常麻煩)。
利用循環(huán)鏈表的循環(huán)特性求出每種情況， 分別比較。 代碼其實(shí)并不長(zhǎng)，只是寫鏈表占了很多行。

收獲：

掌握了無(wú)頭指針循環(huán)鏈表的定義方法，學(xué)到了字典序的概念。

代碼：

#include <iostream> #include <cstdio> #include <list> #include <cstdlib> #include <cstring>using namespace std ;typedef struct LNode *lbook ; struct LNode{char x ;struct LNode *list ; }; //創(chuàng)建 lbook Creat(char a[] , int len1) {lbook P , P1 , P2 ;P = (lbook)malloc(sizeof(LNode)) ; //無(wú)頭指針 P->x = a[0] ; //無(wú)頭指針的鏈表定義方式 P1 = P;int j = 1 ;while(j != len1) {char s = a[j++] ;lbook P3 ;P3 = (lbook)malloc(sizeof(LNode)) ;P3->x = s ;P3->list = P1->list ;P1->list = P3 ;P1 = P3 ;}P1->list = P ; //循環(huán)鏈表 return P ; }//查找 lbook Find(lbook P , int len , int i) { int k = 0 ; while(k++ != len) {if(k == i) return P ;P = P->list ;} } int main() {//悔棋很麻煩。 lbook L ;char a[105] ;cin >> a ; //輸入 int len = strlen(a) ; //輸入字符串a(chǎn)的長(zhǎng)度L = Creat(a , len) ; if(len == 1) { //特殊情況：長(zhǎng)度為1則直接輸出。 Show(L,len) ;return 0 ;}//每條鏈比較字典序，n條鏈需比較n-1次。int k = 0 ; int s = 2 ;char c[105] ; //存放結(jié)果strcpy(c,a) ; //c先行存放a數(shù)組的值。 while(k++ != (len-1)) {lbook LL = Find(L, len, s) ;s++ ;//定義d數(shù)組，分別存放環(huán)狀序列所有結(jié)果 char d[105] ; int r = 0 ;while(r != len) {d[r] = LL->x ;r++ ;LL = LL->list ;}//若c>d,則將d賦給c，重復(fù)操作。 if((strcmp(c,d)) == 1) strcpy(c,d) ;} cout << c ; return 0 ;} 超強(qiáng)干貨來(lái)襲 云風(fēng)專訪：近40年碼齡，通宵達(dá)旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的算法竞赛入门经典(第二版) | 程序3-10 生成元 (UVa1584,Circular Sequence)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。