C中的鏈接列表

Question

雖然不是我的課程要求，但我試圖實現單鏈和雙鏈列表，以確保我理解這些概念。我想出了大部分我認爲的問題，除了我嘗試去調試的問題以外，還有一些問題我不知道。雖然我讀過不同的帖子，但我無法找出他們爲什麼不能以相似的方式工作。

當我的插入函數while(h != NULL)踢出時，我必須再次檢查最後一個項目，因爲它會跳過它。我想過一個do/while循環，但這不起作用。

我有完全相同的搜索功能循環，它使用while(h != NULL)找到列表中的最後一項，而不是在處理它之前踢我。

下面是從搜索功能工作循環，

while(h != NULL) //check list 
     if(h->val == s) 
      return true; 
     else 
      h = h->next; 

下面是從插入功能不循環，在退出之前這一個不結束鏈表使用的終值循環。如果您在閱讀完整代碼之前必須檢查if (t->next == NULL && t->val > n)是否讓它搜索最後一個項目。

 while(t->next != NULL) //assigns it in the middle 
     { 
      if(t->val < n) 
       t = t->next; 
      else 
      { 
       node* tt = t->prev; 
       tt->next = a; 
       a->next = t; 
       a->prev = t->prev; 
       t->prev = a; 

       return h; //returns original 
      } 
     } 

在此先感謝，希望我解釋它。很難，因爲我試圖學習我不知道的東西。

#include <stdio.h> 
#include <stdlib.h> //for rand(); 
#include <stdbool.h> //bool function 

typedef struct _node 
{ 
    int val; 
    struct _node* next; 
    struct _node* prev; 
} node; 

node* create(int n, node* h); 

node* insert(int n, node* h); 

bool search(int s, node* h); 

void print(node* h); 

void del(node* h); 

int main() 
{ 
    node* h = NULL; 

    for(int i = 0; i < 15; i++) 
    { 
     int n = rand() % 15; 
     h = create(n, h); 
    } 

    print(h); 

    int s = 10; //number to search for 

    if(search(s, h)) 
     printf("Found Item\n"); 
    else 
     printf("Item not found\n"); 

    del(h); 
} 

bool search(int s, node* h) 
{ 
    if(h == NULL) 
     printf("No nodes created to search.\n"); 

    while(h != NULL) //check list 
     if(h->val == s) 
      return true; 
     else 
      h = h->next; 

    return false; 
} 


void del(node* h) 
{ 
    node* t = h; 

    while (h->next != NULL) 
    { 
     t = h->next; 
     h->next = NULL; 
     free(h); 
     h = t; 
    } 
     free(h); 
} 

node* insert(int n, node* h) 
{ 
    node* a = malloc(sizeof(node)); 
    node* t = h; 

    if(a == NULL) 
    { 
     printf("Failed to create new node\n"); 
     return NULL; 
    } 

    a->val = n; //sets new node to have value of n 

    if(h->val >= n) //assigns the integer to the beginning 
    { 
     a->next = t; 
     t->prev = a; 
     a->prev = NULL; 
     h = a; //assigns a new head since it appended the item to the beginning 
     return h; 
    } 

    while(t->next != NULL) //assigns it in the middle 
    { 
     if(t->val < n) 
      t = t->next; 
     else 
     { 
      node* tt = t->prev; 
      tt->next = a; 
      a->next = t; 
      a->prev = t->prev; 
      t->prev = a; 

      return h; //returns original 
     } 
    } 

    if (t->next == NULL && t->val > n) //check to see if second to last 
    {  
     node* tt = t->prev; 
     tt->next = a; 
     a->next = t; 
     a->prev = t->prev; 
     t->prev = a; 
    } 
    else 
    { 
     a->next = NULL; 
     a->prev = t; 
     t->next = a; 
    } 

    return h; 
} 

node* create(int n, node* h) 
{ 
    if(h == NULL) //create first node in the list 
    { 
     h = malloc(sizeof(node)); 
     if(h == NULL) 
     { 
      printf("Failed to create first node\n"); 
      return NULL; 
     } 
     h->val = n; 
     h->next = NULL; 
     h->prev = NULL; 
    } 
    else //create additional nodes in the list 
     h = insert(n, h); 

    return h; 
} 

void print(node* h) 
{ 
    if(h == NULL) 
     printf("List is empty\n"); 
    else 
     while(h != NULL) 
     { 
      printf("%i\n", h->val); 
      h = h->next; 
     } 
} 

Answer 1

如果我正確理解你的問題，你問這些行：

while(t->next != NULL) //assigns it in the middle 
{ 
    if(t->val < n) 
     t = t->next; 
    else 
    { 
     node* tt = t->prev; 
     tt->next = a; 
     a->next = t; 
     a->prev = t->prev; 
     t->prev = a; 

     return h; //returns original 
    } 
} 

if (t->next == NULL && t->val > n) //check to see if second to last 
{  
    node* tt = t->prev; 
    tt->next = a; 
    a->next = t; 
    a->prev = t->prev; 
    t->prev = a; 
} 
else 
{ 
    a->next = NULL; 
    a->prev = t; 
    t->next = a; 
} 

，問題是：「如何才能避免從過了一會兒，而內部的重複代碼塊」

也許是這樣的：

while(1) 
{ 
    if(t->val < n) 
    { 
     if (t->next == NULL) break; 
     t = t->next; 
    } 
    else 
    { 
     //assigns it in the middle 
     node* tt = t->prev; 
     tt->next = a; 
     a->next = t; 
     a->prev = t->prev; 
     t->prev = a; 

     return h; //returns original 
    } 
} 

// Add new node at the end 
a->next = NULL; 
a->prev = t; 
t->next = a;