如何删除C中链接列表中的最后一个元素？

Question

我不知道如何删除c中的链表中的第一个和最后一个元素。以下是我的程序，它使用链接列表。我不知道如何删除最后一个元素，但我能找到它。该元素由一个整数和下一个指针组成。如果有人可以请帮助我，它将不胜感激。

struct ListNode{ 
    int value; 
    struct ListNode *next; 
}; 
typedef struct ListNode Link; 

void deleteLast(Link *); 
void printList(Link *); 
void deleteFirst(Link *); 

int main(){ 
    Link *myList; 
Link *curr, *newlink; 
int i; 
    curr = myList; 
    for(i = 0; i < 10; i++){ 

      newlink = (Link*) malloc(1*sizeof(Link)); 
      newlink->value = i*i; 
      curr->next = newlink; 
      curr = newlink; 
    } 

    curr->next = NULL; 
    curr = myList->next; 
    deleteFirst(curr); 
    printList(curr); 
    printf("\n"); 
} 
void deleteLast(Link *head) 
{ 
    Link *curr; 
    curr = head->next; 
    while (curr->next!=NULL) 
    { 
     curr = curr->next; 
    } 
    free(curr->next); 

    curr->next = NULL; 

} 
void printList(Link *head){ 
    Link *curr; 
    curr = head->next; 

    printf("["); 
    if(curr!=NULL){ 
     printf("%d",curr->value); 
     curr = curr->next; 
    } 

    while(curr != NULL){ 
     printf(", %d", curr->value); 
     curr = curr->next; 
    } 
    printf("]\n"); 

} 
void deleteFirst(Link *head){ 
    Link *curr; 
    curr = head->next; 
    free(curr->value); 
    free(curr->next); 
    printf("%d\t",curr->value); 
} 

没有我尝试的作品，请你能帮助我吗。

Answer 1

你的代码有很多错误。

• 当您创建列表：
  • 你没有投你正在做curr->next = newlink;其中CURR = myList中与初始值的malloc
  • 的返回值。您可以将循环更改为

Link *myList = NULL; 
    Link *curr, *newlink; 
    int i; 

    curr = myList; 
    for(i = 0; i < 10; i++){ 

    newlink = malloc(1*sizeof(Link)); 
    newlink->value = i*i; 
    if (curr != NULL) 
     curr->next = newlink; 
    else 
     myList = newlink; 
    curr = newlink; 
    } 

• 当你删除你要远远的最后一个元素，这就是为什么它不工作

Link *curr; 

    curr = head->next; 
    while (curr->next != NULL) { 
    head = curr; 
    curr = curr->next; 
    } 

    free(head->next); 
    head->next = NULL; 

• 当你想删除列表的第一个元素
  • 您不必以释放字段的值，因为你即使你删除列表的第一个元素没有使用malloc
  • 分配它，你不改变你的主目录的开头的值。这就是为什么你必须采取一个PARAM一个Link**

void deleteFirst(Link **head){ 
    Link *curr; 

    curr = (*head)->next; 
    free(*head); 
    *head = curr; 
} 

，您可以通过给你的列表开头的地址调用，在主此功能：

deleteFirst(&myList); 
    deleteLast(myList); 
    printList(myList); 

当然，在所有的功能

你必须检查，如果你有在列表中，至少某些数值不是空指针NULL

Answer 2

#include <stdint.h> 
#include <stdlib.h> 
#include <stdio.h> 

typedef struct node Node; 
struct node{ 
    int element; 
    Node *next; 
}; 

Node* head = NULL; 

bool put(int data) 
{ 
    bool retVal = false; 

    Node* temp; 

    do 
    { 
     if (head == NULL) 
     { 
      head = malloc(sizeof(Node)); 

      if (head) 
      { 
       printf("New head created\n"); 
       head->element = data; 
       head->next = NULL; 
       printf("Element %d stored\n", data); 

       retVal = true; 
       break; 
      }   
      else 
      {   
       printf("Could not create new head\n"); 
       break; 
      } 
     } 

     temp = head; 
     while (temp->next != NULL) 
     { 
      temp = temp->next; 
     } 

     temp->next = malloc(sizeof(Node)); 
     temp->next->element = data; 
     temp->next->next = NULL; 

     printf("Element %d stored\n", data); 

     retVal = true; 
     break; 

    } while(1); 

    return retVal; 
} 



bool get(int *pData) 
{ 
    bool retVal = false; 
    Node* temp; 

    if (head != NULL) 
    { 
     retVal = true; 
     Node *prevNode = head; 

     temp = prevNode; 
     while (temp->next) 
     { 
      prevNode = temp; 
      temp = temp->next; 
     } 

     *pData = temp->element; 
     printf("Element %d retrieved\n", *pData); 

     free(temp); 
     printf("Node freed\n"); 

     if (temp == head) 
     { 
      head = NULL; 
     } 
     else 
     { 
      prevNode->next = NULL; 
     } 
    } 

    return retVal; 
} 


int main(void) 
{ 
    int retrievedNum; 
    int num; 

    for (num = 0; num < 5; num++) 
    { 
     put(num); 
    } 

    printf("\n"); 

    for (num = 0; num < 6; num++) 
    { 
     get(&retrievedNum); 
    } 

    put(num); 

    get(&retrievedNum); 

    printf("Element retrieved: %d\n", retrievedNum); 

    return 1; 
} 

Answer 3

此代码将在链表中删除最后一个元素的工作：

void dellast() 

{ 

r=head; 

struct node* z; 
do 
{ 
    z=r; 
    r=r->next; 
    if(r->next==NULL) 
    { 
     z->next=NULL; 
     free(r->next); 
    } 
}while(z->next!=NULL); 
} 

的代码是这样的：

保持当前节点和其先前的轨道节点。

如果current-> next == NULL表示它是最后一个节点。

所以不要previous->未来= NULL和免费当前节点

Answer 4

我做了用C我自己（单独）LinkedList的例子，它证明工作：

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

/********** GLOBALS *******************************/ 
#define OK 0 
#define ERROR -1 

/********** STRUCT AND TYPES DEFINTIONS ***********/ 
/* a node with key, data and reference to next node*/ 
typedef struct Node { 
    int key; 
    char string[1024]; 
    struct Node *next; // pointer to next node 
} Node; 

/* the actual linked list: ref to first and last Node, size attribute */ 
typedef struct LinkedList { 
    struct Node *first; 
    struct Node *last; 
    int size; 
} LinkedList; 

/********** FUNCTION HEADERS **********************/ 
LinkedList* init_list(); 
void insert_end(LinkedList *list, int key, char string[]); 
void insert_beginning(LinkedList *list, int key, char string[]); 
int remove_end(LinkedList *list); 
int remove_beginning(LinkedList *list); 
int print_list(LinkedList *list); 
void free_list(LinkedList *list); 
char * get_string(LinkedList *list, int key); 

/*********** FUNCTION DEFINITIONS ***************/ 

/** 
* init_list Returns an appropriately (for an empty list) initialized struct List 
* 
* @return LinkedList *   ..ptr to the newly initialized list 
*/ 
LinkedList * init_list() { 
    printf("initializing list...\n"); 

    LinkedList *list = (LinkedList*) malloc(sizeof(LinkedList)); 

    list->first = NULL; 
    list->last = NULL; 
    list->size = 0; 

    return list; 
} 

/** 
* Given a List, a key and a string adds a Node containing this 
* information at the end of the list 
* 
* @param list  LinkedList * ..ptr to LinkedList 
* @param key  int    .. key of the Node to be inserted 
* @param string char[]   .. the string of the Node to be inserted 
*/ 
void insert_end(LinkedList *list, int key, char string[]) { 
    printf("----------------------\n"); 

    list->size++;     // increment size of list 

    // intialize the new Node 
    Node* newN = (Node*) malloc(sizeof(Node)); 
    newN->key = key; 
    strcpy(newN->string, string); 
    newN->next = NULL; 

    Node* oldLast = list->last;  // get the old last 
    oldLast->next = newN;   // make new Node the next Node for oldlast 
    list->last = newN;    // set the new last in the list 

    printf("new Node(%p) at end: %d '%s' %p \n", newN, newN->key, newN->string,newN->next); 
} 

/** 
* Given a List, a key and a string adds a Node, containing 
* this information at the beginning of the list 
* 
* @param list  LinkedList * ..ptr to LinkedList 
* @param key  int    .. key of the Node to be inserted 
* @param string char[]   .. the string of the Node to be inserted 
*/ 
void insert_beginning(LinkedList *list, int key, char string[]) { 
    printf("----------------------\n"); 

    list->size++;     // increment size of list 
    Node* oldFirst = list->first; //get the old first node 

    /* intialize the new Node */ 
    Node* newN = (Node*) malloc(sizeof(Node)); 
    newN->key = key; 
    strcpy(newN->string, string); 
    newN->next = oldFirst; 

    list->first = newN;    // set the new first 

    /* special case: if list size == 1, then this new one is also the last one */ 
    if (list->size == 1) 
     list->last = newN; 

    printf("new Node(%p) at beginning: %d '%s' %p \n", newN, newN->key,newN->string, newN->next); 
} 

/** 
* Removes the first Node from the list 
* 
* @param list  LinkedList *  .. ptr to the List 
* 
* @return OK | ERROR 
*/ 
int remove_beginning(LinkedList *list) { 
    printf("----------------------\n"); 

    if (list->size <= 0) 
     return ERROR; 

    list->size--; 

    Node * oldFirst = list->first; 

    printf("delete Node(%p) at beginning: '%d' '%s' '%p' \n", oldFirst,oldFirst->key, oldFirst->string, oldFirst->next); 

    free(list->first);   //free it 
    list->first = oldFirst->next; 
    oldFirst = NULL; 

    return OK; 
} 

/** 
* Removes the last Node from the list. 
* 
* @param list  LinkedList *  .. ptr to the List 
* 
* @return OK | ERROR 
*/ 
int remove_end(LinkedList *list) { 
    printf("----------------------\n"); 

    /* special case #1 */ 
    if (list->size <= 0) 
     return ERROR; 

    /* special case #2 */ 
    if (list->size == 1) { 
     free(list->first); 
     list->first = NULL; 
     list->last = NULL; 
     return OK; 
    } 

    printf("delete Node(%p) at end: '%d' '%s' '%p' \n", list->last,list->last->key, list->last->string, list->last->next); 

    list->size--;   // decrement list size 
    Node * startNode = list->first; 

    /* find the new last node (the one before the old last one); list->size >= 2 at this point!*/ 
    Node * newLast = startNode; 
    while (newLast->next->next != NULL) { 
     newLast = newLast->next; 
    } 

    free(newLast->next); //free it 
    newLast->next = NULL; //set to NULL to denote new end of list 
    list->last = newLast; // set the new list->last 

    return OK; 
} 

/** 
* Given a List prints all key/string pairs contained in the list to 
* the screen 
* 
* @param list  LinkedList *  .. ptr to the List 
* 
* @return OK | ERROR 
*/ 
int print_list(LinkedList *list) { 

    printf("----------------------\n"); 

    if (list->size <= 0) 
     return ERROR; 

    printf("List.size = %d \n", list->size); 

    Node *startN = list->first; //get first 

    /* iterate through list and print contents */ 
    do { 
     printf("Node#%d.string = '%s', .next = '%p' \n", startN->key,startN->string, startN->next); 
     startN = startN->next; 
    } while (startN != NULL); 

    return OK; 
} 

/** 
* Given a List, frees all memory associated with this list. 
* 
* @param list  LinkedList *  ..ptr to the list 
*/ 
void free_list(LinkedList *list) { 
    printf("----------------------\n"); 
    printf("freeing list...\n"); 

    if (list != NULL && list->size > 0) { 
     Node * startN = list->first; 
     Node * temp = list->first; 

     do { 
      free(temp); 
      startN = startN->next; 
      temp = startN; 
     } while (startN != NULL); 

     free(list); 
    } 
} 

/** 
* Given a List and a key, iterates through the whole List and returns 
* the string of the first node which contains the key 
* 
* @param list  LinkedList *  ..ptr to the list 
* @param key  int     .. the key of the Node to get the String from 
* 
* @return OK | ERROR 
*/ 
char * get_string(LinkedList *list, int key) { 
    printf("----------------------\n"); 

    Node *startN = list->first; //get first 

    /* iterate through list and find Node where node->key == key */ 
    while (startN->next != NULL) { 
     if (startN->key == key) 
      return startN->string; 
     else 
      startN = startN->next; 
    } 

    return NULL; 
} 

/*************** MAIN **************/ 
int main(void) { 

    LinkedList *list = init_list(); 

    insert_beginning(list, 1, "im the first"); 
    insert_end(list, 2, "im the second"); 
    insert_end(list, 3, "im the third"); 
    insert_end(list, 4, "forth here"); 

    print_list(list); 
    remove_end(list); 
    print_list(list); 
    remove_beginning(list); 
    print_list(list); 
    remove_end(list); 
    print_list(list); 
    printf("string at node with key %d = '%s' \n",2,get_string(list, 2)); 
    free_list(list); 

    return OK; 
} 

希望此实现示例有所帮助。