作者yauhh (喲)
看板C_and_CPP
標題Re: [問題] 遞迴排列-- 避免重複字元的遞迴
時間Thu Mar 18 07:54:22 2010
※ 引述《liu2007 (薯)》之銘言：
: 我打算用遞迴寫字元的排列
: 可是這個字元陣列裡有時候可能會有重複的情況
: 譬如說
: a b c d e f # #
: 當這八個字元下去做排列的時候
: 理應只有 8!/2! 的答案
: 但是對於電腦來說還是有8!個答案
: 請問要怎麼樣避免這種狀況發生??
: 可否題點一下解決的方法@.@?
: 使用遞迴實在是好難......
遞迴概念超簡單,但用C寫實在是很難抓住細節,會寫到很想殺幾個人...
取字串排列會用到一個函數,是給一個字元a和一個字串str,求將a插入str任二個
字元之間,或是放在str頭或尾,的全部可能的結果.
在此稱這個函數是poss_insert.
一開始先寫個全部插入情況的基本型,這是當輸入字元和字串有重覆字母時,
會有重覆結果的情況.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct list {
char* str;
struct list* next;
};
struct list* poss_insert(char a, char* str, struct list** ls);
int main(int argc, char *argv[])
{
struct list* ls;
poss_insert('#', "a#", &ls);
int i;
struct list* p = ls;
while (p != NULL) {
printf("%s\n", p->str);
p = p->next;
}
system("PAUSE");
return 0;
}
struct list* poss_insert(char a, char* str, struct list** ls) {
int slen = strlen(str);
if (slen == 0) {
(*ls) = (struct list*)malloc(sizeof(struct list)*1);
(*ls)->str = (char*)malloc(sizeof(char)*(slen+1));
(*ls)->str[0] = a;
(*ls)->str[1] = '\0';
(*ls)->next = NULL;
} else {
/* Let a be after str */
(*ls) = (struct list*)malloc(sizeof(struct list)*1);
(*ls)->str = (char*)malloc(sizeof(char)*(slen+1));
strcpy((*ls)->str, str);
(*ls)->str[slen] = a;
(*ls)->str[slen+1] = '\0';
/* Let a insert into str */
char* tstr = (char*)malloc(sizeof(char)*(slen-1));
strncpy(tstr, str, slen-1);
tstr[slen-1] = '\0';
poss_insert(a, tstr, &(*ls)->next);
free(tstr);
struct list *p = (*ls)->next, *r;
char* q;
while(p != NULL) {
q = &(str[slen-1]);
p->str = strcat(p->str, q);
p = p->next;
}
}
return (*ls);
}
以上程式中,在先直接把a放到str後面的程式段落,可以發現如果a與str的最後一字
相同,這個動作可以跳過. 因為此時做這個動作,是製造出重覆結果的關鍵步驟.
所以,無重覆版本改成以下情況,改法是在發現a是str最後一字時,把struct list
結構的當前節點當做是空節點. 是藉著將 (*ls)->str 指定為 NULL 方式.
而這樣修改,其他用以讀取串列並產生輸出的程式都要記得檢查 ->str == NULL 情況.
int main(int argc, char *argv[])
{
struct list* ls;
poss_insert('+', "c&c+", &ls);
int i;
struct list* p = ls;
while (p != NULL) {
if (p->str != NULL) {
printf("%s\n", p->str);
}
p = p->next;
}
system("PAUSE");
return 0;
}
struct list* poss_insert(char a, char* str, struct list** ls) {
int slen = strlen(str);
if (slen == 0) {
(*ls) = (struct list*)malloc(sizeof(struct list)*1);
(*ls)->str = (char*)malloc(sizeof(char)*(slen+1));
(*ls)->str[0] = a;
(*ls)->str[1] = '\0';
(*ls)->next = NULL;
} else {
/* Let a be after str */
(*ls) = (struct list*)malloc(sizeof(struct list)*1);
if (str[slen-1] == a) {
(*ls)->str = NULL;
} else {
(*ls)->str = (char*)malloc(sizeof(char)*(slen+1));
strcpy((*ls)->str, str);
(*ls)->str[slen] = a;
(*ls)->str[slen+1] = '\0';
}
/* Let a insert into str */
char* tstr = (char*)malloc(sizeof(char)*(slen-1));
strncpy(tstr, str, slen-1);
tstr[slen-1] = '\0';
poss_insert(a, tstr, &(*ls)->next);
free(tstr);
struct list *p = (*ls)->next, *r;
char* q;
while(p != NULL) {
q = &(str[slen-1]);
if (p->str != NULL) {
p->str = strcat(p->str, q);
}
p = p->next;
}
}
return (*ls);
}
以上主程式情況,輸出:
c&c++
c&+c+
c+&c+
+c&c+
請按任意鍵繼續 . . .
--
媽,我寫出來了! (揮手)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.215.90
※ 編輯: yauhh 來自: 218.160.215.90 (03/18 07:57)