技术教程 c/c++ 线性表之单向链表 正文

c/c++ 线性表之单向链表

2022-11-09,

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);

}

c/c++ 线性表之单向链表的相关教程结束。

《c/c++ 线性表之单向链表.doc》

下载本文的Word格式文档，以方便收藏与打印。

Copyright 2023. 昆居客 - IT编程,互联网信息技术文档大全!