我真的在這個關于鏈表和節點洗掉的練習中苦苦掙扎。
基本上,當一個序列中的每個堿基在另一個序列中的相同位置具有相應的互補時,就稱 DNA 序列是互補的。堿基 A 與 T 鍵合,堿基 C 與 G 鍵合。例如,序列 ACGT 和 TGCA 是互補的。
我必須實作一個需要兩個鏈表的函式:第一個是原始 DNA,第二個是編輯序列。該函式必須應用前面描述的編輯方法并回傳新串列。
例如,我們將“ACGTAGACGTTCT A”作為原始 DNA 序列,將“GC A”作為鍵合序列。G 與 C 匹配,C 與 G 匹配,A 與 T 匹配(反之亦然)。因此,“CG T”是“GC A”的反射。然后我們必須按照這個確切的順序從原始 DNA 序列中洗掉“C”、“G”和 T”,結果證明這是下面所述的預期結果。
另外,有兩件事: 1. 我必須忽略由于任何節點洗掉而生成的任何后續匹配項。2. 除了 stdlib.h 和 malloc() 或 calloc() 等函式,我不能使用任何頭檔案。我只被允許使用free()。
輸入:
A C G T A G A C G T T C T A
G C A
預期結果:
A A G A T C T A
實際結果:
A A G A C G T T C T A
任何想法將不勝感激。
謝謝!
uj5u.com熱心網友回復:
我應該根據您當前的代碼撰寫代碼以便更好地溝通,但我認為不使用遞回會更簡單。請你試試:
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkedNode {
char data;
struct LinkedNode *next;
} LinkedNode;
/*
* append the node with data at the end of the list
*/
void append(LinkedNode *head, char data)
{
LinkedNode *newNode = malloc(sizeof(LinkedNode));
newNode->data = data;
newNode->next = NULL;
LinkedNode *temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
/*
* dump the data of the list
*/
void dump(LinkedNode *head)
{
for (head = head->next; head != NULL; head = head->next) {
printf("%c ", head->data);
}
printf("\n");
}
/*
* generate another list of complimentary sequence
*/
void gencomp(LinkedNode *dest, LinkedNode *src)
{
char s_data, d_data;
for (src = src->next; src != NULL; src = src->next) {
s_data = src->data;
switch(s_data) {
case 'A':
d_data = 'T';
break;
case 'T':
d_data = 'A';
break;
case 'C':
d_data = 'G';
break;
case 'G':
d_data = 'C';
break;
default:
fprintf(stderr, "unknown base: %c\n", s_data);
exit(1);
}
append(dest, d_data);
}
}
/*
* return the pointer to the last element if the subsequences match
*/
LinkedNode *match(LinkedNode *head, LinkedNode *comp)
{
for (; head != NULL; head = head->next, comp = comp->next) {
if (head->data != comp->data) {
return NULL;
} else if (comp->next == NULL) {
return head;
}
}
return NULL;
}
/*
* search "head" for "comp". If matched, the matched portion is skipped
* (not freed)
*/
void edit(LinkedNode *head, LinkedNode *comp)
{
LinkedNode *matched;
for (; head != NULL; head = head->next) {
if ((matched = match(head->next, comp->next))) {
head->next = matched->next; // skip matched sequence
}
}
}
int main()
{
char dna_orig[] = "ACGTAGACGTTCTA";
char dna_bond[] = "GCA";
int i;
// generate list of original sequence
LinkedNode *head = malloc(sizeof(LinkedNode));
head->next = NULL;
for (i = 0; dna_orig[i] != 0; i ) {
append(head, dna_orig[i]);
}
// generate list of bonding sequence
LinkedNode *bond = malloc(sizeof(LinkedNode));
bond->next = NULL;
for (i = 0; dna_bond[i] != 0; i ) {
append(bond, dna_bond[i]);
}
// generate list of complementary sequence of bond
LinkedNode *comp = malloc(sizeof(LinkedNode));
comp->next = NULL;
gencomp(comp, bond);
// edit the original sequence and see the result
edit(head, comp);
dump(head);
return 0;
}
輸出:
A A G A T C T A
- 我創建了一個鍵合序列的互補序列串列,以使搜索變得容易。
- 到目前為止,該代碼效率低下,因為它在串列中使用重復的線性搜索。
- 為了列印目的,我必須包含 <stdio.h> 。
[編輯]
釋放跳過的節點時,我們不能按從頭到尾的正向順序釋放它們,因為一旦第一個節點被釋放,到下一個節點的鏈接就會丟失。然后我們可以利用遞回以相反的順序釋放它們。這是釋放跳過的節點的函式:
void freenodes(LinkedNode *head, LinkedNode *tail)
{
if (head->next == tail) { // the last node to remove
free(head);
return;
}
freenodes(head->next, tail); // free nodes recursively
free(head);
}
函式的第一個引數一個接一個地前進,直到它到達匹配序列的最后一個節點。然后函式回傳到呼叫者,回傳到匹配序列的第一個節點,同時釋放節點。這是更新的完整代碼,包括修改edit函式以回傳已編輯串列的頭部。
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkedNode {
char data;
struct LinkedNode *next;
} LinkedNode;
/*
* append the node with data at the end of the list
*/
void append(LinkedNode *head, char data)
{
LinkedNode *newNode = malloc(sizeof(LinkedNode));
newNode->data = data;
newNode->next = NULL;
LinkedNode *temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
/*
* dump the data of the list
*/
void dump(LinkedNode *head)
{
for (head = head->next; head != NULL; head = head->next) {
printf("%c ", head->data);
}
printf("\n");
}
/*
* compare characters complementarily
* return 1 for matching pairs as A<=>T or C<=>G
*/
int compcomp(char a, char b)
{
if ((a == 'A' && b == 'T') || (a == 'T' && b == 'A')
|| (a == 'C' && b == 'G') || (a == 'G' && b == 'C'))
return 1;
else
return 0;
}
/*
* return the pointer to the last node if the subsequences match complementarily
*/
LinkedNode *match(LinkedNode *head, LinkedNode *bond)
{
for (; head != NULL; head = head->next, bond = bond->next) {
if (! compcomp(head->data, bond->data)) {
return NULL;
} else if (bond->next == NULL) {
return head;
}
}
return NULL;
}
/*
* free skipped nodes
*/
void freenodes(LinkedNode *head, LinkedNode *tail)
{
if (head->next == tail) { // the last node to remove
// printf("> %c\n", head->data); // for debugging
free(head);
return;
}
freenodes(head->next, tail); // free nodes recursively
// printf("> %c\n", head->data); // for debugging
free(head);
}
/*
* search "head" for the sequence of complementary of "bond". If matched,
* the matched portion is skipped and skipped nodes are freed
*/
LinkedNode *edit(LinkedNode *head, LinkedNode *bond)
{
LinkedNode *matched; // last node of matched sequence
LinkedNode *matchednext;
LinkedNode *tmp; // copy of head to traverse the list
for (tmp = head; tmp != NULL; tmp = tmp->next) {
if ((matched = match(tmp->next, bond->next))) {
matchednext = matched->next; // backup matched->next
freenodes(tmp->next, matched->next);
tmp->next = matchednext; // skip matched sequence
}
}
return head;
}
int main()
{
char dna_orig[] = "ACGTAGACGTTCTA";
char dna_bond[] = "GCA";
int i;
// generate list of original sequence
LinkedNode *head = malloc(sizeof(LinkedNode));
head->next = NULL;
for (i = 0; dna_orig[i] != 0; i ) {
append(head, dna_orig[i]);
}
// generate list of bonding sequence
LinkedNode *bond = malloc(sizeof(LinkedNode));
bond->next = NULL;
for (i = 0; dna_bond[i] != 0; i ) {
append(bond, dna_bond[i]);
}
// edit the original sequence and see the result
dump(edit(head, bond));
return 0;
}
順便說一句,您可以#include <stdio.h>通過洗掉printf()和fprintf()僅用于報告目的的函式來省略。
[EDIT2]
The main difference between your code and mine is the data structure of
the linked list. The head of my list has empty data and is the entrance
to the first node, while your dna_original directly starts with the node
which contains the data. Same with bond and sequencia.
Both have its own advantages but we cannot mix them.
Then please modify your editar_dna as:
LinkedNode *editar_dna(LinkedNode *dna_original, LinkedNode *seq_edicao){
LinkedNode *matched, *matchednext, *tmp;
for (tmp = dna_original; tmp != NULL; tmp = tmp->next) {
if ((matched = match(tmp->next, seq_edicao))) {
matchednext = matched->next;
liberar_nos(tmp->next, matched->next);
tmp->next = matchednext;
}
}
return dna_original;
}
changing seq_edicao->next to seq_edicao in match() function. Then It will output A A A.
The potential problem of your data structure is we cannot remove
the starting subsequence such as: "CGTACGTA". It is technically
possible to fix but may require additional huge modifications.
Now you have three options:
- Neglect the edge case starting with matched subsequence.
- Modify the linked list structure (easy but I'm not sure if it is acceptable.)
- Find a countermeasure keeping current data structure.
It's up to you. :)
[EDIT3]
Here is the version applying option 3 (w/o the modification of main) to your code (FYI):
#include <stdio.h>
#include <stdlib.h>
typedef struct LinkedNode LinkedNode;
struct LinkedNode {
char data;
LinkedNode *next;
};
void imprimir1(LinkedNode *inicio){
if(inicio == NULL){
return;
}
printf("%c", inicio->data);
if (inicio->next!=NULL) printf(" ");
else printf("\n");
imprimir1(inicio->next);
return;
}
void liberar_lista(LinkedNode *inicio){
if(inicio == NULL) return;
liberar_lista(inicio->next);
free(inicio);
}
LinkedNode *inserir_final_r(LinkedNode *inicio, char valor) {
if (inicio == NULL) {
LinkedNode *novo = malloc(sizeof(LinkedNode));
if (novo == NULL) return inicio;
novo->data = valor;
novo->next = NULL;
return novo;
}
inicio->next = inserir_final_r(inicio->next, valor);
return inicio;
}
void liberar_nos(LinkedNode *head, LinkedNode *tail) {
if (head == tail) {
return;
}
liberar_nos(head->next, tail);
free(head);
}
int compare(char a, char b) {
if ((a == 'A' && b == 'T') || (a == 'T' && b == 'A')
|| (a == 'C' && b == 'G') || (a == 'G' && b == 'C'))
return 1;
else
return 0;
}
LinkedNode *match(LinkedNode *head, LinkedNode *bond) {
for (; head != NULL; head = head->next, bond = bond->next) {
if (! compare(head->data, bond->data)) {
return NULL;
} else if (bond->next == NULL) {
return head;
}
}
return NULL;
}
LinkedNode *editar_dna(LinkedNode *dna_original, LinkedNode *seq_edicao){
LinkedNode *matched, *matchednext, *tmp;
// remove leading matched subsequence(s) as a preproces
while ((matched = match(dna_original, seq_edicao))) {
matchednext = matched->next;
liberar_nos(dna_original->next, matched->next); // note we cannot free the 1st node
dna_original->data = matchednext->data;
dna_original->next = matchednext->next;
liberar_nos(matchednext, matchednext->next); // free the copied node which is no longer used
}
/*
for (tmp = dna_original; tmp != NULL; tmp = tmp->next) {
if ((matched = match(tmp->next, seq_edicao))) {
matchednext = matched->next;
liberar_nos(tmp->next, matched->next);
tmp->next = matchednext;
}
}
*/
for (tmp = dna_original; tmp != NULL; ) {
if ((matched = match(tmp->next, seq_edicao))) {
matchednext = matched->next;
liberar_nos(tmp->next, matched->next);
tmp->next = matchednext; // skip matched sequence
} else {
tmp = tmp->next; // proceed to next node
}
}
return dna_original;
}
int main(){
//Creating empty nodes
LinkedNode *dna_original = NULL;
LinkedNode *sequencia = NULL;
//Populating test data into the original sequence
// dna_original = inserir_final_r(dna_original, 'A'); // dropped just for the test
dna_original = inserir_final_r(dna_original, 'C');
dna_original = inserir_final_r(dna_original, 'G');
dna_original = inserir_final_r(dna_original, 'T');
dna_original = inserir_final_r(dna_original, 'C');
dna_original = inserir_final_r(dna_original, 'G');
dna_original = inserir_final_r(dna_original, 'T');
dna_original = inserir_final_r(dna_original, 'A');
dna_original = inserir_final_r(dna_original, 'C');
dna_original = inserir_final_r(dna_original, 'G');
dna_original = inserir_final_r(dna_original, 'T');
dna_original = inserir_final_r(dna_original, 'A');
//Populating test data into the second sequence
sequencia = inserir_final_r(sequencia, 'G');
sequencia = inserir_final_r(sequencia, 'C');
sequencia = inserir_final_r(sequencia, 'A');
//Printing the original sequence before change
imprimir1(dna_original);
//Changing the sequence
editar_dna(dna_original, sequencia);
//Printing the original sequence after change
imprimir1(dna_original);
//Freeing allocated memory
liberar_lista(dna_original);
liberar_lista(sequencia);
return 0;
}
Please note the initialization of the list in main() is modified for the debugging and demonstration purpose.
uj5u.com熱心網友回復:
從標題和討論中,我假設應用編輯應該通過洗掉匹配的子序列來改變輸入串列。如果串列的第一個節點被洗掉,您需要回傳一個指向稍后某個節點的指標。否則回傳第一個節點。
處理這兩種情況的天真方法是進行特定檢查。但是,有一種眾所周知的模式可以同時處理這兩種情況。它暫時掛起一個“虛擬”頭節點,永遠不會被洗掉。我將附加代碼,而不是嘗試進一步解釋。見apply_edit。
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
typedef struct node_s {
struct node_s *next;
char base;
} Node;
void print(Node *seq) {
for (Node *p = seq; p; p = p->next) printf("%c", p->base);
printf("\n");
}
bool base_match(char x, char y) {
switch (x) {
case 'A': return y == 'T';
case 'C': return y == 'G';
case 'G': return y == 'C';
case 'T': return y == 'A';
}
exit(42); // input error
}
// If the prefix of seq is as given, return the following seq node, else seq.
Node *remove_prefix(Node *prefix, Node *seq) {
Node *p, *s;
for (p = prefix, s = seq; p && s; p = p->next, s = s->next)
if (!base_match(p->base, s->base))
return seq;
return p ? seq : s;
}
Node *apply_edit(Node *edit, Node *seq) {
Node head[1] = {{ seq }};
for (Node *p = head; p && p->next; ) {
Node *next = remove_prefix(edit, p->next);
if (next == p->next) p = next; // No match; advance one.
else p->next = next; // Remove the match; don't advance.
}
return head->next;
}
Node *build_seq(char *gene) {
Node *seq = NULL;
for (int i = strlen(gene) - 1; i >= 0; --i) {
Node *node = malloc(sizeof *node);
node->base = gene[i];
node->next = seq;
seq = node;
}
return seq;
}
int main(void) {
// Provided test case. Expect AAGATCTA.
print(apply_edit(build_seq("GCA"), build_seq("ACGTAGACGTTCTA")));
// Remove from head. Expect A.
print(apply_edit(build_seq("GCA"), build_seq("CGTA")));
// Remove from tail. Expect A.
print(apply_edit(build_seq("GCA"), build_seq("ACGT")));
// Incomplete match at tail. Expect ACG
print(apply_edit(build_seq("GCA"), build_seq("ACG")));
// Remove all. Expect empty string.
print(apply_edit(build_seq("GCA"), build_seq("CGTCGT")));
// Remove creates new match, which is ignored. Expect CGT.
print(apply_edit(build_seq("GCA"), build_seq("CCGTGT")));
return 0;
}
盡管它使代碼更難閱讀,但您可以在呼叫它的地方行內輔助函式apply_edit并獲得非常簡潔的內容:
Node *apply_edit(Node *edit, Node *seq) {
Node *e, *s, head[1] = {{ seq }};
for (Node *p = head; p && p->next; ) {
for (e = edit, s = p->next; e && s; e = e->next, s = s->next)
if (!base_match(e->base, s->base)) break;
if (e) p = s; // No match; advance one.
else p->next = s; // Remove the match; don't advance.
}
return head->next;
}
I'll also point out that traversing lists with recursion is something you wouldn't do in production code. While a good compiler with optimizations turned up will convert tail recursion (like yours) into iteration, it can be a finicky optimization ... as in the compiler will skip it under non-obvious circumstances. If that happens, your program needs stack space proportional to the length of lists you're traversing, while an iterative code will run fine in one stack frame. That's a big deal if your program needs to be reliable.
轉載請註明出處,本文鏈接:https://www.uj5u.com/qukuanlian/448942.html
上一篇:我想在java中交換字串的字符但它回傳垃圾值你能告訴我我的代碼有什么問題嗎
下一篇:計算遞回呼叫的次數
