c/c++ 线性表的光为循环链表

c/c++ 线性表底就为循环链表

线性表的才为循环链表

匪是存放在于连接的内存空间,链表中之每个节点的next都对下一个节点,最后一个节点的产一个节点不是NULL,而是头节点。因为头尾相连,所以受单循环链表。

实的首先个节点是头节点,头节点不存数量,单纯以编写程序方便。但是下注释里描写的【第一独节点】的含义是头节点的下一节点,也便是真心实意存放数据的第一单节点。

下的代码实现了以下功能

函数 功能描述
push_back 从链表的最后插入节点
push_front 从链表的起始插入节点
show_list 打印出链表里每个节点的值
pop_back 删除链表最后一个节点
pop_front 删除链表起始节点
insert_val 在合适的位置插入一个节点;
比如原来的链表:1->3->NULL,当要插入的节点的值为2的时候,就会在1和3之间插入这个节点,插入后的链表:1->2->3->NULL
find 查找指定的节点
length 返回链表中节点的个数
delete_val 删除指定的节点
sort 排序,重新排列节点
resver 按倒序,重新排列节点
clear 释放除了头节点之外的所有节点所占用的内存空间
destroy 释放所有节点的所占用的内存空间,包括头节点

whilenode.h

#ifndef __SEQNODE__
#define __SEQNODE__

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

#define ElemType int

typedef struct Node{
  ElemType data;
  struct Node* next;
}Node;

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

whilenode.c

#include "seqnode.h"

void init(NodeList* list){
  list->first = (Node*)malloc(sizeof(Node));
  list->last = list->first;
  list->last->next = NULL;
  list->size = 0;
}

Node* create_node(ElemType val){
  Node* node = (Node*)malloc(sizeof(Node));
  assert(NULL != node);
  node->data = val;
  node->next = NULL;
  return node;
}
void push_back(NodeList* list, ElemType val){
  Node* p = create_node(val);

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

void push_front(NodeList* list, ElemType val){
  Node* p = create_node(val);

  p->next = list->first->next;
  list->first->next = p;
  if(list->size == 0){
    list->last = p;
    list->last->next = list->first;
  }
  list->size++;
}

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

void pop_back(NodeList* list){
  if(list->size == 0)return;
  Node* p = list->first;
  while(p->next != list->last){
    p = p->next;
  }
  p->next = list->first;
  free(list->last);
  list->last = p;
  list->size--;
}
void pop_front(NodeList* list){
  if(list->size == 0)return;
  Node* p = list->first->next;
  list->first->next = p->next;
  if(list->size == 1){
    list->last = list->first;
  }
  list->size--;
  free(p);
}
void insert_val(NodeList* list, ElemType val){
  if(list->size == 0){
    push_back(list, val);
    return;
  }
  Node* p = create_node(val);

  Node* t = list->first;
  while(t->next != list->first && val > t->next->data){
    t = t->next;
  }
  if(t->next == list->first){
    list->last = p;
  }
  p->next = t->next;
  t->next = p;

  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;
    }
    p = p->next;
  }
  while(list->first != p);
  return NULL;
}
//寻找目标节点的前一个节点
Node* find1(NodeList* list, ElemType val){
  if(0 == list->size){
    return NULL;
  }
  Node* p = list->first;
  do{
    if(p->next->data == val){
      return p;
    }
    p = p->next;
  }while(list->first != p);
  return NULL;
}
void delete_val(NodeList* list, ElemType val){
  if(0 == list->size)return;

  Node* p = find1(list, val);
  if(NULL == p)return;
  if(p->next == list->last){
    list->last = p;
  }
  Node* tmp = p->next;
  p->next = p->next->next;
  free(tmp);
  list->size--;
}

void sort(NodeList* list){
  if(list->size == 0 || list->size == 1)return;

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

  Node* t = list->last = list->first;
  list->last->next = list->first;

  size_t s = list->size;

  while(s-- > 0){
    while(p->data > t->next->data && t->next != list->first){
      t = t->next;
    }
    if(t->next == list->first){
      list->last = p;
    }

    Node* tmp = p->next;
    p->next = t->next;
    t->next = p;

    p = tmp;
    t = list->first;
  }
  list->last->next = list->first;
}
void resver(NodeList* list){
  if(list->size == 0 || list->size == 1)return;

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

  list->last = list->first;
  list->last->next = list->first;

  while(head != list->first){
    Node* tmp = head->next;

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

    head = tmp;
  }
  list->last = end;
}

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

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

whilenodemain.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       ***\n");
    printf("*** [11]  sort        [12] resver     ***\n");
    printf("*** [13]              [14] clear      ***\n");
    printf("*** [0]   quit        [15*]destroy    ***\n");
    printf("*****************************************\n");
    printf("请选择:>");
    scanf("%d", &select);
    if(0 == select)
      break;
    switch(select){
    case 1:
      printf("请输入要插入的数据,以-1结束>\n");
      while(scanf("%d",&item) && item != -1){
    push_back(&list, item);
      }
      show_list(&list);
      break;
    case 2:
      printf("请输入要插入的数据,以-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("请输入要插入的数据>\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:
      sort(&list);
      show_list(&list);
      break;
    case 12:
      resver(&list);
      show_list(&list);
      break;
    case 13:
      resver(&list);
      show_list(&list);
      break;
    case 14:
      clear(&list);
      show_list(&list);
      break;
    case 15:
      destroy(&list);
      break;
    default:
      break;
    }
  }

  destroy(&list);
}

c/c++ 线性表底徒为链表

线性表的光为链表

匪是存放在于连接的内存空间,链表中之每个节点的next都针对下一个节点,最后一个节点的产一个节点是NULL。

诚实的第一单节点是头节点,头节点不存数量,单纯以编写程序方便。但是下注释里描写的【第一个节点】的含义是头节点的下一节点,也就是是真实存放数据的率先只节点。

脚的代码实现了以下职能

函数 功能描述
push_back 从链表的最后插入节点
push_front 从链表的起始插入节点
show_list 打印出链表里每个节点的值
pop_back 删除链表最后一个节点
pop_front 删除链表起始节点
insert_val 在合适的位置插入一个节点;
比如原来的链表:1->3->NULL,当要插入的节点的值为2的时候,就会在1和3之间插入这个节点,插入后的链表:1->2->3->NULL
find 查找指定的节点
length 返回链表中节点的个数
delete_val 删除指定的节点
sort by val 排序,改变节点里的值,不改变节点之间的链条
sort by node 排序,重新排列节点
resver back 按倒序,重新排列节点(实现方法是:尾插)
resver front 按倒序,重新排列节点(实现方法是:头插)
clear 释放除了头节点之外的所有节点所占用的内存空间
destroy 释放所有节点的所占用的内存空间,包括头节点

seqnode.h

#ifndef __SEQNODE__
#define __SEQNODE__

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

#define ElemType int

//Node代表节点,data是节点里保存的数据,next指针保存下一个节点的地址
typedef struct Node{
  ElemType data;
  struct Node* next;
}Node;

//NodeList代表链表,first指向头节点,last指向最后一个节点,size是链表里节点的个数
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"

//分配头节点的内存空间
void init(NodeList* list){
  list->first = (Node*)malloc(sizeof(Node));
  list->last = list->first;
  list->first->next = NULL;
  list->size = 0;
}

//从链表的最后插入节点
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;

  //新插入节点的下一个节点指向原来链表中的第一个节点
  p->next = list->first->next;
  //头节点的next指向新插入的节点
  list->first->next = p;
  //如果是插入节点前的链表里没有如何节点,则必须要把last指向插入的节点
  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");
}

//删除最后的节点
void pop_back(NodeList* list){
  if(list->size == 0)return;
  Node* p = list->first;
  //寻找最后节点的前一个节点,当p->next == list->last,p就是最后节点的前一个节点。
  while(p->next != list->last){
    p = p->next;
  }
  //释放最后节点所占用的空间
  free(list->last);
  //p变成最后节点
  list->last = p;
  p->next = NULL;
  list->size--;
}

//删除第一个的节点
void pop_front(NodeList* list){
  if(list->size == 0)return;
  //p就是第一个节点
  Node* p = list->first->next;
  //把第二个节点变成第一个节点
  list->first->next = p->next;
  //如果链表里只有一个节点,则必须移动last
  if(list->size == 1){
    list->last = list->first;
  }
  list->size--;
  //释放第一个节点所占用的空间
  free(p);
}

//在合适的位置插入一个节点.
//比如原来的链表:1->3->NULL,当要插入的节点的值为2的时候,就会在1和3之间插入这个节点,插入后的链表:1->2->3->NULL
void insert_val(NodeList* list, ElemType val){
  //如果链表为空直接调用尾插
  if(list->size == 0){
    push_back(list, val);
    return;
  }
  Node* p = (Node*)malloc(sizeof(Node));
  p->data = val;
  Node* t = list->first;
  do{
    //t->next不是最后一个节点,并且在合适位置
    if(val >= t->data && t->next != NULL && val <= t->next->data){
      p->next = t->next;
      t->next = p;
      break;
    }
    //t->next是最后一个节点
    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->next是最后一个节点,所以必须移动last的指向
      if(NULL == p->next->next){
        list->last = p;
      }
      free(p->next);
      //p->next是要被删除的节点,所以p->next指向要被删除节点的下一个节点
      p->next = p->next->next;
      list->size--;
      break;
    }
    p = p->next;
  }while(NULL != p->next);
}

//利用find函数进行删除
void delete_val1(NodeList* list, ElemType val){
  if(0 == list->size)return;
  Node* p = find(list, val);
  if(NULL == p)return;
  //如果要被删除的节点是最后一个节点,就直接调用尾删。
  if(p == list->last){
    pop_back(list);
  }
  //find找到是要被删除的节点,但是不知道它前面的节点的地址,所以就不无法让它前面的节点的next指向它后面的节点
  //解决办法,把它后节点里的数据,赋给它,然后删除它后面的节点。如果它后面的节点是最后节点,必须修改last的指向。
  else{
    p->data = p->next->data;
    free(p->next);
    p->next = p->next->next;
    if(NULL == p->next){
      list->last = p;
    }
    list->size--;
  }
}
//不重新排列节点,只是修改节点里的值,用冒泡法排序。
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++;
}

//重新排列节点。思路:把链表分成2个链表,第一个链表留一个节点,利用insert_val,把剩下的节点再插回第一个节点
void sort1(NodeList* list){
  if(list->size == 0 || list->size == 1)return;

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

  //n指向第二个节点
  Node* n = list->first->next->next;
  Node* t;
  while(NULL != n){
    //因为n>next在下面的insert_pnt里会被改变,所以提前把n->next方到t里保存
    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++;
}
//思路:把链表分成2个链表,第一个链表只有头几点,剩下的节点放在第二个链表,循环找第二个链表里的尾节点,利用尾插,把找到的尾节点插入回第一个链表。
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){
    //寻找最后一个节点,找到后修改e,让e为往前移动一个节点
    while(tmp->next != e && b != e){
      tmp = tmp->next;
    }
    if(b == e){
      push_back_pnt(list, b);
    }else{
      push_back_pnt(list, tmp->next);
    }
    //让e为往前移动一个节点
    e   = tmp;
    //让tmp再次指向第一个节点,目的是再从第一个节点开始,去寻找最后一个节点
    tmp = b;
  }
}

void push_front_pnt(NodeList* list, Node* node){
  node->next = list->first->next;
  list->first->next = node;
  list->size++;
}
//思路:把链表分成2个链表,第一个链表只有第一个节点,剩下的节点放在第二个链表,利用头插,把第二个链表里的节点再插入回第一个链表。
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;
  }
}
//和resver1的思路一样,但不调用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("请选择:>");
    scanf("%d", &select);
    if(0 == select)
      break;
    switch(select){
    case 1:
      printf("请输入要插入的数据,以-1结束>\n");
      while(scanf("%d",&item) && item != -1){
    push_back(&list, item);
      }
      show_list(&list);
      break;
    case 2:
      printf("请输入要插入的数据,以-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("请输入要插入的数据>\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);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图