The C language data structure implements the reverse order and output of the linked list

  • 2020-05-17 06:04:08
  • OfStack

The C language data structure implements the reverse order and output of the linked list

Invert 1 list and output. I did this in two ways, the first with the help of a new empty list; The second is to directly implement the reverse order on the basis of the original linked list.

Example code:

The header file:


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

typedef int ElemType; 
typedef struct Node 
{// Node structure  
 ElemType value;    // domain  
 struct Node *next;// Pointer to the domain  
}Node,*ptr_Node; 

typedef struct LinkList 
{// Chain table structure  
 ptr_Node head; // Chain header node pointer  
 ptr_Node tail;// A pointer to the tail of a list  
 int length;  // Chain length of the table  
}LinkList,*ptr_LinkList; 

ptr_LinkList CreateList(void) 
{// create 1 An empty list  
 ptr_LinkList linklist; 
 linklist=(LinkList *)malloc(sizeof(LinkList)); 
 if(!linklist) 
 { 
  printf("allocation failed.\n"); 
 } 
 linklist->head=NULL; 
 linklist->tail=NULL; 
 linklist->length=0; 
 return linklist; 
} 

bool IsListEmpty(ptr_LinkList linklist) 
{// Determine if the list is empty  
 if(linklist->length==0) 
 { 
  return true; 
 } 
 return false; 
} 

void InsertListHead(ptr_LinkList linklist,ElemType element) 
{// The insert value at the header is element Is the new header  
 ptr_Node ptr_node; 
 ptr_node=(Node *)malloc(sizeof(Node)); // Generate insertion node  
 if(!ptr_node) 
 { 
  printf("allocation failed.\n"); 
 } 
 else 
 { 
  ptr_node->value=element; 
  if(linklist->length==0) 
  { 
   linklist->head=ptr_node; 
   linklist->tail=linklist->head; 
   linklist->tail->next=NULL; 
  } 
  else 
  { 
   ptr_node->next=linklist->head; 
   linklist->head=ptr_node; // head  
  } 
  linklist->length++; // List length plus 1 
 } 
} 

void InsertListTail(ptr_LinkList linklist,ElemType element) 
{ 
 ptr_Node ptr_node; 
 ptr_node=(Node *)malloc(sizeof(Node)); // Generate insertion node  
 if(!ptr_node) 
 { 
  printf("allocation failed.\n"); 
 } 
 else 
 { 
  ptr_node->value=element; 
  if(linklist->length==0) 
  { 
   linklist->head=ptr_node; 
   linklist->tail=linklist->head; 
   linklist->tail->next=NULL; 
  } 
  else 
  { 
   linklist->tail->next=ptr_node; 
   linklist->tail=ptr_node; // List the tail  
  } 
  linklist->length++; // List length plus 1 
 } 
} 

void InsertListPosition(ptr_LinkList linklist,int pos,ElemType element) 
{ 
 int i; 
 ptr_Node ptr_node; 
 ptr_Node temp_ptr_node; 
 if(pos<1 || pos>linklist->length) 
 { 
  printf("The insert position is invalidate.\n"); 
 } 
 else 
 { 
  ptr_node=(Node *)malloc(sizeof(Node)); // Generate insertion node  
  if(!ptr_node) 
  { 
   printf("allocation failed.\n"); 
  } 
  ptr_node->value=element; 
  if(pos==1) 
  { 
   InsertListHead(linklist,element); 
  } 
  else if(pos==linklist->length) 
  { 
   InsertListTail(linklist,element); 
  } 
  else 
  { 
   temp_ptr_node=linklist->head; 
   for(i=1;i<pos-1;i++) 
   {// Find the first pos-1 A node  
    temp_ptr_node=temp_ptr_node->next; 
   } 
   ptr_node->next=temp_ptr_node->next; 
   temp_ptr_node->next=ptr_node; 
   linklist->length++; 
  } 
 } 
} 

void Destroy(ptr_LinkList linklist) 
{// Destruction of the list  
 ptr_Node p=linklist->head; 
 ptr_Node q; 
 while(p) 
 {// Free up space for each node  
  q=p->next; 
  free(p); 
  p=NULL; 
  p=q; 
 } 
} 

void Traverse(ptr_LinkList linklist) 
{// Output the entire list  
 ptr_Node p; 
 p=linklist->head; 
 while(p) 
 { 
  printf("%4d",p->value); 
  p=p->next; 
 } 
}

The header file implements several basic operations of the linked list, some of which are required and some of which are not.

Implementation code:


#include "stdafx.h" 
#include "LinkList.h" 
#include <conio.h> 

ptr_LinkList InvertList(ptr_LinkList list) 
{// The method USES 1 Two new empty lists to reverse the list  
 ptr_LinkList inverted_linklist; 
 ptr_Node p; 
 p=list->head; 
 inverted_linklist=CreateList();// create 1 An empty list  
 while(p) 
 {// will list The node value in the linked list is entered into the newly created list in reverse order to realize the list inversion  
  InsertListHead(inverted_linklist,p->value); 
  p=p->next; 
 } 
 return inverted_linklist; 
} 

void InvertLinkList(ptr_LinkList linklist) 
{// This method can reverse the order of the original list without the help of other lists  
 ptr_Node p,q,r,m; 
 m=p=linklist->head; 
 q=p->next; 
 r=q->next; 
 while(r) 
 {// In turn, the nodes in the list are reversed  
  q->next=p; 
  p=q; 
  q=r; 
  r=r->next; 
 } 
 q->next=p; // The last 1 Nodal inversion  
 linklist->head=q; 
 linklist->tail=m; 
 linklist->tail->next=NULL; 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
 ptr_LinkList linklist; 
 ptr_LinkList list; 
 linklist=CreateList(); 
 if(linklist) 
 { 
  printf("We have created a new linklist.\n"); 
 } 
 InsertListHead(linklist,12); 
 InsertListHead(linklist,35); 
 InsertListHead(linklist,66); 
 InsertListHead(linklist,06); 
 InsertListHead(linklist,11); 
 InsertListHead(linklist,54); 
 InsertListHead(linklist,79); 
 Traverse(linklist); 
 printf("\n"); 
 printf("The first method:\n"); 
 list=InvertList(linklist); 
 Traverse(list); 
 printf("\n"); 
 printf("The second method:\n"); 
 InvertLinkList(linklist); 
 Traverse(linklist); 
 printf("\n"); 
 getch(); 
 return 0; 
} 


Thank you for reading, I hope to help you, thank you for your support of this site!


Related articles: