Article From:https://www.cnblogs.com/xiaoshiwang/p/9217296.html

c/c++ linear list”

one-way list of linear tables

It is not stored in continuous memory space. Every node in the linked list points to the next node, and the next node of the last node is NULL.

The first real node is the header node, and the header node does not store data, which is simple for programming. But the meaning of the first node in the note below is the next node of the header node, that is, the first node that actually stores the data.

The following code implements the following functions

functionFunctional description
push_backThe last insertion of a node from the list
push_frontStarting insertion node from the linked list
show_listPrint out the value of each node in the list
pop_backDelete the last node of the list
pop_frontDelete the start node of the list
insert_valInsert a node in the right position.
For example, the original chain list: 1-> 3-> NULL, when the value of the node to be inserted is 2, the node is inserted between 1 and 3, and the linked list is inserted: 1-> 2-> 3-> NULL
findLookup the specified node
lengthReturn the number of nodes in the list
delete_valDelete the specified node
sort by valSort, change the value in the node, and do not change the chain between nodes.
sort by nodeSort, rearrange the nodes
resver backRearrange the nodes in reverse order (the implementation is: tail insertion).
resver frontRearrange the nodes in reverse order.
clearRelease memory space occupied by all nodes except header nodes.
destroyRelease all memory space occupied by all nodes, including header nodes

seqnode.h

#ifndef __SEQNODE__
#define __SEQNODE__

#include <stdio.h>
#include <malloc.h>
#include <assert.h>
#include <memory.h>
#include <stdbool.h>

#define ElemType int

//NodeA representative node, data is the data saved in the node, and the next pointer holds the address of the next node.
typedef struct Node{
  ElemType data;
  struct Node* next;
}Node;

//NodeListRepresenting the linked list, first points to the header node, last points to the last node, and size is the number of nodes in the linked list.
typedef struct NodeList{
  Node*  first;
  Node*  last;
  size_t size;
}NodeList;

void init(NodeList*);
void push_back(NodeList*, ElemType);
void push_front(NodeList*, ElemType);
void pop_back(NodeList*);
void pop_front(NodeList*);
void show_list(NodeList*);
void insert_val(NodeList*, ElemType);
Node* find(NodeList*, ElemType);
void delete_val(NodeList*, ElemType);
void sort(NodeList*);
void sort1(NodeList*);
void resver(NodeList*);
void resver1(NodeList*);
void resver2(NodeList*);
void clear(NodeList*);
void destroy(NodeList*);

#endif

seqnode.c

#include "seqnode.h"

//The memory space of the assigned head node
void init(NodeList* list){
  list->first = (Node*)malloc(sizeof(Node));
  list->last = list->first;
  list->first->next = NULL;
  list->size = 0;
}

//The last insertion of a node from the list
void push_back(NodeList* list, ElemType val){
  Node* p = (Node*)malloc(sizeof(Node));
  assert(NULL != p);
  p->data = val;
  p->next = NULL;

  list->last->next = p;
  list->last = p;
  list->size++;
}

void push_front(NodeList* list, ElemType val){
  Node* p = (Node*)malloc(sizeof(Node));
  p->data = val;
  
  //The next node of the new insertion node points to the first node in the original linked list.
  p->next = list->first->next;
  //The next of the header node points to the newly inserted node
  list->first->next = p;
  //If there are no nodes in the linked list before inserting nodes, you must point last to the node inserted.
  if(list->size == 0){
    list->last = p;
  }
  list->size++;
}

void show_list(NodeList* list){
  Node* tmp = list->first->next;
  while(tmp != NULL){
    printf("%d->", tmp->data);
    tmp = tmp->next;
  }
  printf("NULL\n");
}

//Delete the last node
void pop_back(NodeList* list){
  if(list->size == 0)return;
  Node* p = list->first;
  //Find the last node of the last node, when p-> next = = list-> last, P is the last node of the previous node.
  while(p->next != list->last){
    p = p->next;
  }
  //Release the space occupied by the final node
  free(list->last);
  //pBecome the final node
  list->last = p;
  p->next = NULL;
  list->size--;
}

//Delete the first node
void pop_front(NodeList* list){
  if(list->size == 0)return;
  //pIt's the first node
  Node* p = list->first->next;
  //Turn second nodes into the first node
  list->first->next = p->next;
  //If there is only one node in the linked list, last must be moved.
  if(list->size == 1){
    list->last = list->first;
  }
  list->size--;
  //Release the space occupied by the first node
  free(p);
}

//Insert a node in the right position.
//For example, the original chain list: 1-> 3-> NULL, when the value of the node to be inserted is 2, the node is inserted between 1 and 3, and the linked list is inserted: 1-> 2-> 3-> NULL
void insert_val(NodeList* list, ElemType val){
  //If the list is empty and directly call the tail
  if(list->size == 0){
    push_back(list, val);
    return;
  }
  Node* p = (Node*)malloc(sizeof(Node));
  p->data = val;
  Node* t = list->first;
  do{
    //t->nextIt's not the last node, and it's in the right place
    if(val >= t->data && t->next != NULL && val <= t->next->data){
      p->next = t->next;
      t->next = p;
      break;
    }
    //t->nextIt's the last node
    if(t->next == NULL){
      list->last->next = p;
      list->last = p;
      list->last->next = NULL;
      break;
    }
    t = t->next;
  }
  while(1);
  list->size++;
}
Node* find(NodeList* list, ElemType val){
  if(0 == list->size){
    return NULL;
  }
  Node* p = list->first->next;
  do{
    if(val == p->data){
      return p;
      break;
    }
    p = p->next;
  }
  while(NULL != p);
}
void delete_val(NodeList* list, ElemType val){
  if(0 == list->size)return;
  Node* p = list->first;
  do{
    if(p->next->data == val){
      //p->nextIt is the last node, so we must move the direction of last.
      if(NULL == p->next->next){
        list->last = p;
      }
      free(p->next);
      //p->nextIs the node to be deleted, so p-> next points to the next node of the node to be deleted.
      p->next = p->next->next;
      list->size--;
      break;
    }
    p = p->next;
  }while(NULL != p->next);
}

//Delete using the find function
void delete_val1(NodeList* list, ElemType val){
  if(0 == list->size)return;
  Node* p = find(list, val);
  if(NULL == p)return;
  //If the node to be deleted is the last node, it will be called tail deletion directly.
  if(p == list->last){
    pop_back(list);
  }
  //findFind the node to be deleted, but do not know the address of the node in front of it, so you can not make the next of the front node pointing to the node behind it.
  //The solution is to assign the data in its posterior node to it, and then delete the nodes behind it. If the node behind it is the last node, the direction of last must be modified.
  else{
    p->data = p->next->data;
    free(p->next);
    p->next = p->next->next;
    if(NULL == p->next){
      list->last = p;
    }
    list->size--;
  }
}
//Instead of rearranging nodes, they modify the values in the nodes and sort them by bubble method.
void sort(NodeList* list){
  if(list->size == 0 || list->size == 1)return;
  Node* p = list->first->next;
  for(int i = 0; i < list->size-1; ++i){
    for(int j = 0; j < list->size-i-1; ++j){
      if(p->data > p->next->data){
        p->data = p->data + p->next->data;
        p->next->data = p->data - p->next->data;
        p->data = p->data - p->next->data;
      }
      p = p->next;
    }
    p = list->first->next;
  }
}

void insert_pnt(NodeList* list, Node* node){
  Node* t = list->first;
  do{
    if(t->next != NULL && node->data <= t->next->data){
      node->next = t->next;
      t->next = node;
      break;
    }
    if(t->next == NULL){
      list->last->next = node;
      list->last = node;
      list->last->next = NULL;
      break;
    }
    t = t->next;
  }
  while(1);
  list->size++;
}

//Rearrange the nodes. Train of thought: divide the linked list into 2 linked lists, leave a node in the first list, and use insert_val to insert the remaining nodes back to the first node.
void sort1(NodeList* list){
  if(list->size == 0 || list->size == 1)return;

  list->size = 1;
  list->last = list->first->next;
  list->last->next = NULL;
    
  //nPointing to second nodes
  Node* n = list->first->next->next;
  Node* t;
  while(NULL != n){
    //Because n>, next will be changed in the insert_pnt below, so save n->, next to t in advance.
    t = n->next;
    insert_pnt(list, n);
    n = t;
  }
}
void push_back_pnt(NodeList* list, Node* node){
  list->last->next = node;
  list->last = node;
  list->last->next = NULL;
  list->size++;
}
//Thinking: divide the list into 2 linked lists, the first list is only the first few points, the remaining nodes are placed on the second chain tables, and the tail nodes in the second chain tables are searched, and the tail nodes are inserted into the first linked list.
void resver(NodeList* list){
  if(list->size == 0 || list->size == 1)return;

  Node* e = list->last;
  Node* b = list->first->next;
  Node* tmp = list->first;
  size_t sz = list->size;

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

  while(sz-- > 0){
    //Search for the last node, find and modify e, and let e move a node forward.
    while(tmp->next != e && b != e){
      tmp = tmp->next;
    }
    if(b == e){
      push_back_pnt(list, b);
    }else{
      push_back_pnt(list, tmp->next);
    }
    //Let e move a node forward
    e   = tmp;
    //Let TMP point to the first node again, the purpose is to start from the first node, to find the last node.
    tmp = b;
  }
}

void push_front_pnt(NodeList* list, Node* node){
  node->next = list->first->next;
  list->first->next = node;
  list->size++;
}
//Thinking: divide the list into 2 linked lists, the first list has only the first node, the rest of the nodes on the second chain tables, the use of the head insert, the second linked list of nodes back into the first chain.
void resver1(NodeList* list){
  if(list->size == 0 || list->size == 1)return;

  Node* head = list->first->next->next;

  list->last = list->first->next;
  list->last->next = NULL;
  list->size = 1;

  Node* tmp;
  while(head != NULL){
    tmp = head->next;
    push_front_pnt(list, head);
    head = tmp;
  }
}
//Like resver1, but not push_front_pnt.
void resver2(NodeList* list){
  if(list->size == 0 || list->size == 1)return;

  Node* p = list->first->next->next;
  list->last = list->first->next;
  list->last->next = NULL;

  Node* q;
  while(p != NULL){
    q = p->next;
    p->next = list->first->next;
    list->first->next = p;
    p = q;
  }
}

void clear(NodeList* list){
  if(list->size == 0) return;
  Node* b = list->first->next;
  Node* q;
  while(b != NULL){
    q = b->next;
    free(b);
    b = q;
  }
  list->last = list->first;
  list->last->next = NULL;
  list->size = 0;
}

void destroy(NodeList* list){
  Node* b = list->first;
  Node* q;
  while(b != NULL){
    q = b->next;
    free(b);
    b = q;
  }
}

seqnodemain.c

#include "seqnode.h"

int main(){
  NodeList list;
  init(&list);
  int select = 1;
  ElemType item;
  Node* node = NULL;
  while(select){
    printf("*****************************************\n");
    printf("*** [1]   push_back   [2]  push_front ***\n");
    printf("*** [3]   show_list   [4]  pop_back   ***\n");
    printf("*** [5]   pop_front   [6]  insert_val ***\n");
    printf("*** [7]   find        [8]  length     ***\n");
    printf("*** [9]   delete_val  [10] sort by val***\n");
    printf("*** [11]  sort by node[12] resver back***\n");
    printf("*** [13]  resver front[14] clear      ***\n");
    printf("*** [0]   quit        [15*]destroy    ***\n");
    printf("*****************************************\n");
    printf("Please choose: > ");
    scanf("%d", &select);
    if(0 == select)
      break;
    switch(select){
    case 1:
      printf("Please enter the data to be inserted and end the > with -1;\n");
      while(scanf("%d",&item) && item != -1){
    push_back(&list, item);
      }
      show_list(&list);
      break;
    case 2:
      printf("Please enter the data to be inserted and end the > with -1;\n");
      while(scanf("%d", &item) && item != -1){
    push_front(&list, item);
      }
      show_list(&list);
      break;
    case 3:
      show_list(&list);
      break;
    case 4:
      pop_back(&list);
      show_list(&list);
      break;
    case 5:
      pop_front(&list);
      show_list(&list);
      break;
    case 6:
      printf("Please enter the data > to be inserted.\n");
      scanf("%d",&item);
      insert_val(&list, item);
      show_list(&list);
      break;
    case 7:
      printf("please enter what you shoule find out>\n");
      scanf("%d",&item);
      node = find(&list, item);
      if(node == NULL){
    printf("can not find %d\n", item);
      }
      break;
    case 8:
      printf("length is %ld\n", list.size);
      break;
    case 9:
      printf("please enter what you want to delete>\n");
      scanf("%d",&item);      
      delete_val(&list, item);
      show_list(&list);
      break;
    case 10:
      sort(&list);
      show_list(&list);
      break;
    case 11:
      sort1(&list);
      show_list(&list);
      break;
    case 12:
      resver(&list);
      show_list(&list);
      break;
    case 13:
      resver2(&list);
      show_list(&list);
      break;
    case 14:
      clear(&list);
      show_list(&list);
      break;
      //case 15:
      //destroy(&list);
      break;
    default:
      break;
    }
  }

  destroy(&list);
}

Leave a Reply

Your email address will not be published. Required fields are marked *