双向链表问题？

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

我认为你的结构需要改变，没有理由用双链表来解决你的问题。

你的结构应该包含

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 2

尝试这些 while 循环[编辑以注意 Chris 关于检查 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 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;
}

主要的变化是我输出换行符的方式。我意识到这不是您需要的每个单词后面的换行符，而是它之前的换行符（根本不合逻辑 - 我想知道这是否是问题最初的意图？）。但它现在输出的正是您所需要的。我还为您添加了一个函数来在最后释放链表内存。 :)

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;    

}