雙重鏈接列表問題？

Question

我創建了，我認爲是一個雙向鏈表。這樣做是爲了扭轉每個輸入的詞輸出一個新行，所以：

Hello\nAll\n. 
.\nAll\nHello 

的想法是遍歷我的列表中，直到'\n'被發現，然後向相反的方向和打印其關閉，回去去我離開的地方繼續往前走，直到另一條新線，然後再往前走，打印等。

但是，我目前的執行情況似乎無法工作，而且我碰到了一堵磚牆，並提示或提示感謝！

typedef struct L { 
char val; 
struct L *next; 
struct L *prev; 
}List; 

List *insertList(char val, List *t1); 
List *createList(void); 

int main(void) { 
    List *z = createList(); 
    List *pos = z; 
    while (pos != NULL) { 
    while (z->val != '\n') { 
     if (z == NULL) 
      break; 
      z = z->next; 
      pos = z; 
} 
    while (z != NULL) { 
     printf("%c", z->val); 
     z = z->prev; 
    } 
} 
return 0; 
} 
List *createList(void) { 
    List *h = NULL; 
    char c; 
    do { 
    c =(char)getchar(); 
    h = insertList(c, h); 
    }while(c != '.'); 
    return h; 
} 
List *insertList(char val, List *t1) { 
    List *t = calloc(1, sizeof(List)); 
    t->prev = NULL; 
    t->val = val; 
    t->next = t1; 
    if (t1 != NULL) { 
    t1->prev = t; 
    } 
return t; 
} 

Answer 1

嘗試這些while循環，而不是[編輯以注意克里斯關於LL結束檢查註釋]：

while (pos != NULL) { 
    while (z != NULL) { 
     // if you've reached the line feed or the end of the linked list 
     if ((z->val == '\n') || (z->next == NULL)) { 
      pos = z->next; // store list position just after this char for next time through 
      break; 
     } 
     z = z->next; 
    } 
    while (z != NULL) { 
     printf("%c", z->val); 
     z = z->prev; 
     // don't print more than just this word!: 
     if ((z != NULL) && (z->val == '\n')) 
      break; 
    } 
    // reset z for top inner while loop 
    z = pos; 
} 

基本問題是，當外部while循環纏z不能復位;第二個問題是鏈表的末尾沒有突破第一個內部while循環;第三個問題是第二個內部while循環沒有檢查它正在打印的單詞的結尾。

你還需要在最後釋放鏈接列表，否則將會發生內存泄漏。您還應該檢查calloc()的返回值以確保它不返回null。

Answer 2

我認爲你的結構需要改變，沒有理由有雙鏈表來解決你的問題。

你的結構應該包含

struct node { 
char *word; 
struct node *next; 
}; 

然後主循環應該是這樣的：

1) Read character data until delimiter into expandable buffer. Add NULL string terminator. 
2) When delimiter is reached create node that points to buffer. 
3) Insert NODE at HEAD of list. 
4) When '.' is reached print each string starting from head of list. 

Answer 3

好吧，我有時間去看看爲什麼我的第一個答案是行不通的 - 一個如果通過調試器運行代碼，幾乎沒有什麼明顯的東西。所以這裏有一個完整的工作版本。這也許可以優化了不少，但是也遵循相同的結構，原來的代碼，所以希望你能理解：

typedef struct L { 
    char val; 
    struct L *next; 
    struct L *prev; 
} List; 

List* insertList(char val, List *t1) { 
    List *t = calloc(1, sizeof(List)); 
    t->prev = NULL; 
    t->val = val; 
    t->next = t1; 
    if (t1 != NULL) 
     t1->prev = t; 
    return t; 
} 

List* createList(void) { 
    List *h = NULL; 
    char c; 

    do { 
     c =(char)getchar(); 
     h = insertList(c, h); 
    } while (c != '.'); 

    return h; 
} 

void freeList(List *list) { 
    // free the linked list 
    if (list != NULL) { 
     freeList(list->next); 
     free(list); 
    } 
} 

int main(void) { 
    // create list 
    List *head = createList(); 
    List *pos = head, *currentChar = NULL, *wordStart = NULL; 

    while (pos != NULL) 
    { 
     // find next word 
     wordStart = NULL; 
     while (pos != NULL) 
     { 
      // gone past the beginning of a word yet? 
      if ((pos->val == '\n') || (pos->next == NULL)) 
      { 
       wordStart = (pos->next == NULL) ? pos : pos->prev; // note where this word starts 
       pos = pos->next; // jump over \n, or go to end of list (null), for next time into this loop 
       break; // jump out of this loop so we can output the word 
      } 
      else // not found end of word yet - on to next char 
       pos = pos->next; 
     } 

     // have we found a word? if so, output it! 
     if (wordStart != NULL) 
     { 
      currentChar = wordStart; // start at first char in the word 
      while (currentChar != NULL) 
      { 
       printf("%c", currentChar->val); // output this char 
       currentChar = currentChar->prev; // on to next char in the word 
       if ((currentChar != NULL) && (currentChar->val == '\n')) 
        break; // stop after last char of the word 
      } 
      // print the line-feed just before wordStart (if there is one) 
      if (wordStart->next != NULL) 
       printf("%c", wordStart->next->val); 
     } 
     else // we've reached the end - stop 
      break; // not really necessary - pos should be NULL at this point anyway 
    } 

    freeList(head); // free linked list memory 

    return 0; 
} 

主要的變化是如何I輸出換行。我意識到這不是你需要的每一個單詞後面的換行符，而只是在它之前的一個單詞（根本不合邏輯 - 我想知道這個問題最初的目的是什麼？）。但它現在完全按照您的要求輸出。我已經添加了一個函數來釋放鏈表的內存，最後也是爲了你。 :)

Answer 4

#include<stdio.h> 
#include<conio.h> 
#include<malloc.c> 
struct dnode{ 
int data; 
struct dnode *prev,*next; 
}; 
typedef struct dnode DNODE; 
DNODE *first; 
DNODE *last; 

DNODE* createDnode(int ele){ 
DNODE *nnode; 
nnode=(DNODE *)malloc(sizeof(DNODE)); 
nnode->data=ele; 
nnode->next=NULL; 
nnode->prev=NULL; 
return nnode;  

}

//Insert First 

DNODE *insertFirst(int ele){ 
DNODE *nnode; 
nnode=createDnode(ele); 
if(first==NULL){ //if node is creating first time 
    first=last=nnode; 
    return;  
} 
nnode->prev=NULL; 
nnode->next=first; 
first=nnode; 
return first; 
} 

//Insert Last 

DNODE *insertLast(int ele){ 
DNODE *nnode; 
nnode=createDnode(ele); 
if(first==NULL){ //if node is creating first time 
    first=last=nnode; 
    return;  
} 
last->next=nnode; 
nnode->prev=last; 
last=nnode; 
return last;  
} 

//Insert Before an Element 

DNODE *insertBefore(int ele,int key){ 
DNODE *nnode,*curr,*pre; 
nnode=createDnode(ele); 
if(first==NULL){ //if node is creating first time 
    first=last=nnode; 
    return;  
} 
if(first->data==key){ // if key is found at first node 
    nnode->next=first; 
    first=nnode; 
    return first; 
} 
curr=first; 
while(curr && curr->data!=key){ 
    pre=curr; 
    curr=curr->next; 
} 
if(!curr){ //if search not found then curr will be NULL, it's means the node is added at last 
    last->next=nnode; 
    nnode->prev=last; 
    last=nnode; 
    return last; 
} 
    curr->prev->next=nnode; 
    nnode->prev=curr->prev; 
    nnode->next=curr; 
    curr->prev=nnode; 
    return; 
    } 

// Insert After an Element 

    DNODE *insertAfter(int ele,int key){ 
    DNODE *nnode,*curr,*pre; 
    nnode=createDnode(ele); 
    if(first==NULL){ //if node is creating first time 
    first=last=nnode; 
    return;  
} 
curr=first; 
while(curr && curr->data!=key){ 
    //pre=curr; 
    curr=curr->next; 
} 
if(!curr){ //if search not found then curr will be NULL, it's means the node  is added at last 
    last->next=nnode; 
    nnode->prev=last; 
    last=nnode; 
    return last; 
} 
nnode->next=curr->next; 
curr->next->prev=nnode; 
nnode->prev=curr; 
curr->next=nnode; 
return;  

}

//去除功能

int removeNode(int key){ 
DNODE *curr; 
if(first==NULL){ //if node is creating first time 
    printf("\n\nList is Empty"); 
    return -1;  
} 
curr=first; 
if(first->data==key){ //if first node has key 
    first=first->next; 
    first->prev=NULL; 
    curr->next = NULL; 
    free(curr); 
    return; 
} 

while(curr && curr->data!=key){ 
    curr=curr->next; 
} 
if(!curr){ //if search not found then curr will be NULL, 
    return -1; 
} 

curr->prev->next=curr->next; 
curr->next->prev=curr->prev; 
curr->next = curr->prev = NULL; 
printf("\n\n%d is Successfully Deleted: ",curr->data); 
free(curr); 
return; 
} 

void display(){ 
DNODE *curr; 
if(first==NULL) 
    printf("\n\nNothing to Display\n\n"); 
curr=first; 
printf("\n\n\tElement in List\n\n\t"); 
while(curr){ 
    printf("%d ",curr->data); 
    curr=curr->next;  
    } 
} 
main(){ 
int ele,ch,key; 
do{ 
    printf("\nEnter Your Choice: \n"); 
    printf("1-Insert First\t2-Insert Last\n3-Insert Before\t4-Insert After\n5-Remove \t6-Display\n"); 
    scanf("%d",&ch); 
    switch(ch){ 
     case 1: 
      printf("Enter Element To Insert: "); 
      scanf("%d",&ele); 
      insertFirst(ele); 
      break; 
     case 2: 
      printf("Enter Element To Insert: "); 
      scanf("%d",&ele); 
      insertLast(ele); 
      break; 
     case 3: 
      printf("Enter Element To Insert: "); 
      scanf("%d",&ele); 
      printf("\nEnter Key: "); 
      scanf("%d",&key); 
      insertBefore(ele,key); 
      break; 
     case 4: 
      printf("Enter Element To Insert: "); 
      scanf("%d",&ele); 
      printf("\nEnter Key: "); 
      scanf("%d",&key); 
      insertAfter(ele,key); 
      break; 
     case 5: 
      printf("Enter Key to Delete: "); 
      fflush(stdin); 
      scanf("%d",&key); 
      removeNode(key); 
      break; 
     case 6: 
      display(); 
      break; 
    } 
}while(ch!=7); 
getch(); 
return 0;  

}