登录
当前位置： 首页 > 编程笔记 >

C语言单链表实现方法详解

袁何平
2023-03-14
本文向大家介绍C语言单链表实现方法详解，包括了C语言单链表实现方法详解的使用技巧和注意事项，需要的朋友参考一下

本文实例讲述了C语言单链表实现方法。分享给大家供大家参考，具体如下：

slist.h

#ifndef __SLIST_H__
#define __SLIST_H__
#include<cstdio>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;
typedef struct Node { //定义单链表中的结点信息
  ElemType data; //结点的数据域
  struct Node *next; //结点的指针域
}Node,*PNode;
typedef struct List { //定义单链表的链表信息
  PNode first; //first指向单链表中的第一个结点
  PNode last; //last指向单链表中的最后一个结点
  size_t size; //记录单链表中的结点个数
}List;
void InitList(List *list);//初始化单链表
void push_back(List *list, ElemType x);//在单链表的末尾插入元素
void push_front(List *list, ElemType x);//在单链表的头部插入元素
void show_list(List *list);//打印单链表
void pop_back(List *list);//删除单链表的最后一个元素
void pop_front(List *list);//删除单链表的第一个元素
void insert_val(List *list, ElemType val);//将数据元素插入到单链表中（要求此时单链表中的数据元素顺序排列）
Node* find(List *list, ElemType x);//查找单链表中数据值为x的结点
int length(List *list);//求单链表的长度
void delete_val(List *list, ElemType x);//按值删除单链表中的某个数据元素
void sort(List *list);//对单链表进行排序
void reverse(List *list);//逆置单链表
void clear(List *list);//清除单链表
void destroy(List *list);//摧毁单链表
#endif //__SLIST_H__

slist.cpp

#include"slist.h"
void InitList(List *list) {
  list->first = list->last = (Node*)malloc(sizeof(Node)); //头结点
  assert(list->first != NULL);
  list->first->next = NULL;
  list->size = 0;
}
void push_back(List *list, ElemType x) {
  //step 1：创建一个新的结点
  Node *s = (Node*)malloc(sizeof(Node));
  assert(s != NULL);
  s->data = x;
  s->next = NULL;
  //step 2：将新结点插入单链表的表尾
  list->last->next = s;
  list->last = s;
  //step 3：更新单链表的长度
  list->size++;
}
void push_front(List *list, ElemType x) {
  //step 1：创建一个新的结点
  Node *s = (Node*)malloc(sizeof(Node));
  assert(s != NULL);
  s->data = x;
  s->next = NULL;
  //step 2：将新结点插入单链表的表头
  s->next = list->first->next;
  list->first->next = s;
  //step 3：判断插入的结点是否是单链表的第一个结点，若是更新链表的尾指针
  if (list->size == 0)
    list->last = s;
  //step 4：更新单链表的长度
  list->size++;
}
void show_list(List *list) {
  //step 1：指针p指向单链表的第一个结点
  Node *p = list->first->next;
  //step 2：循环打印结点的信息
  while (p != NULL) {
    printf("%d->", p->data);
    p = p->next;
  }
  printf("Nul.\n");
}
void pop_back(List *list) {
  //step 1：判断单链表是否为空
  if (list->size == 0) return;
  //step 2：定义指针p使其指向目标结点的前一个结点
  Node *p = list->first;//从头结点开始
  while (p->next != list->last)
    p = p->next;
  //step 3：删除目标结点
  free(list->last);
  list->last = p;
  list->last->next = NULL;
  //step 4：更新单链表的长度
  list->size--;
}
void pop_front(List *list) {
  //step 1：判断单链表是否为空
  if (list->size == 0) return;
  //step 2：定义指针p使其指向目标结点的前一个结点
  Node *p = list->first->next;
  //step 3：删除目标结点
  list->first->next = p->next;
  free(p);
  //step 4：判断删除的结点是否是单链表的最后一个结点，若是则更新单链表的尾指针
  if (list->size == 1)
    list->last = list->first;
  //step 4：更新单链表的长度
  list->size--;
}
void insert_val(List *list, ElemType x) {
  //step 1：创建一个新的结点
  Node *s = (Node*)malloc(sizeof(Node));
  assert(s != NULL);
  s->data = x;
  s->next = NULL;
  //step 2：定义指针p使其指向待插入位置的前一个结点
  Node *p = list->first;//从头结点开始
  while (p->next != NULL && p->next->data < s->data)
    p = p->next;
  //step 3：判断结点的待插入位置是否是表尾，若是则更新单链表的尾指针
  if (p->next == NULL)
    list->last = s;
  //step 4：插入结点
  s->next = p->next;
  p->next = s;
  //step 5：更新单链表长度
  list->size++;
}
Node* find(List *list, ElemType x) {
  //step 1：指针p指向单链表的第一个结点
  Node *p = list->first->next;
  //step 2：按照循环顺序查找链表结点
  while (p != NULL && p->data != x)
    p = p->next;
  return p;
}
int length(List *list) {
  return list->size;
}
void delete_val(List *list, ElemType x) {
  //step 1：判断单链表是否为空
  if (list->size == 0) return;
  //step 2：确定结点在单链表中的位置，并判断其是否存在于单链表中
  Node *p = find(list, x);
  if (p == NULL) {
    printf("要删除的数据不存在！\n");
    return;
  }
  //step 3：判断结点位置是否是表尾
  if (p == list->last)//是表尾
    pop_back(list);
  else {//不是表尾
    Node *q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    list->size--;
  }
}
void sort(List *list) {
  //step 1：判断单链表中的结点数是否为0或1
  if (list->size == 0 || list->size == 1) return;
  //step 2：将单链表中第一个结点之后的链表部分截出，方便重新按顺序插入链表之中
  Node *s = list->first->next; // 指针s指向单链表的第一个节点
  Node *p = s->next;//q指向s后面的结点
  list->last = s;//单链表的尾指针指向单链表的第一个结点
  list->last->next = NULL;//截断链表
  //step 3：将截出的链表中的结点根据其数据域大小重新插入到原来链表中
  while (p != NULL) {
    s = p;
    p = p->next;
    Node *q = list->first;
    while (q->next != NULL && q->next->data < s->data)
      q = q->next;
    if (q->next == NULL)//判断q此时指向的是否是单链表的最后一个结点，若是则更新链表的尾指针
      list->last = s;
    //将结点重新插入链表
    s->next = q->next;
    q->next = s;
  }
}
void reverse(List *list) {
  //step 1：判断单链表中的结点数是否为0或1
  if (list->size == 0 || list->size == 1) return;
  //step 2：将单链表中第一个结点之后的链表部分截出，然后将截出的链表中的结点按头插法重新插入到原链表中
  Node *p = list->first->next;
  Node *q = p->next;
  list->last = p;
  list->last->next = NULL;
  while (q != NULL) {
    p = q;
    q = q->next;
    p->next = list->first->next;
    list->first->next = p;
  }
}
void clear(List *list) {
  //step 1：判断单链表是否为空
  if (list->size == 0) return;
  //step 2：释放单链表中的每一个结点
  Node *p = list->first->next;
  while (p != NULL) {
    list->first->next = p->next;
    free(p);
    p = list->first->next;
  }
  //step 3：头指针和尾指针重新都指向头结点
  list->last = list->first;
  //step 4：更新链表长度
  list->size = 0;
}
void destroy(List *list) {
  //step 1：清空单链表
  clear(list);
  //step 2：释放头结点
  free(list->first);
  //step 3：头指针和尾指针都赋值为空
  list->first = list->last = NULL;
}

main.cpp

#include"slist.h"
void main() {
  List mylist;
  InitList(&mylist);
  ElemType item;
  Node *p = NULL;
  int select = 1;
  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] reverse     [12] clear     *\n");
    printf("*[13*] destroy     [0] quit_system  *\n");
    printf("*******************************************\n");
    printf("请选择：>>");
    scanf("%d", &select);
    if (select == 0) break;
    switch (select) {
    case 1:
      printf("请输入要插入的数据（-1结束）:>");
      while (scanf("%d", &item), item != -1) {
        push_back(&mylist, item);
      }
      break;
    case 2:
      printf("请输入要插入的数据（-1结束）:>");
      while (scanf("%d", &item), item != -1) {
        push_front(&mylist, item);
      }
      break;
    case 3:
      show_list(&mylist);
      break;
    case 4:
      pop_back(&mylist);
      break;
    case 5:
      pop_front(&mylist);
      break;
    case 6:
      printf("请输入要插入的数据:>");
      scanf("%d", &item);
      insert_val(&mylist, item);
      break;
    case 7:
      printf("请输入要查找的数据:>");
      scanf("%d", &item);
      p = find(&mylist, item);
      if (p == NULL)
        printf("要查找的数据在单链表中不存在！\n");
      break;
    case 8:
      printf("单链表的长度为%d\n", length(&mylist));
      break;
    case 9:
      printf("请输入要删除的值:>");
      scanf("%d", &item);
      delete_val(&mylist, item);
      break;
    case 10:
      sort(&mylist);
      break;
    case 11:
      reverse(&mylist);
      break;
    case 12:
      clear(&mylist);
      break;
      //case 13:
      //destroy(&mylist);
      //break;
    default:
      printf("选择错误,请重新选择！\n");
      break;
    }
  }
  destroy(&mylist); //程序结束，摧毁链表
}

附：单链表优化版本

slist.h

#ifndef __SLIST_H__
#define __SLIST_H__
#include<cstdio>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;
typedef struct Node { //定义单链表中的结点信息
  ElemType data; //结点的数据域
  struct Node *next; //结点的指针域
}Node,*PNode;
typedef struct List { //定义单链表的链表信息
  PNode first; //first指向单链表中的第一个结点
  PNode last; //last指向单链表中的最后一个结点
  size_t size; //记录单链表中的结点个数
}List;
void InitList(List *list);//初始化单链表
void push_back(List *list, ElemType x);//在单链表的末尾插入元素
void push_front(List *list, ElemType x);//在单链表的头部插入元素
void show_list(List *list);//打印单链表
void pop_back(List *list);//删除单链表的最后一个元素
void pop_front(List *list);//删除单链表的第一个元素
void insert_val(List *list, ElemType val);//将数据元素插入到单链表中（要求此时单链表中的数据元素顺序排列）
Node* find(List *list, ElemType x);//查找单链表中数据值为x的结点
int length(List *list);//求单链表的长度
void delete_val(List *list, ElemType x);//按值删除单链表中的某个数据元素
void sort(List *list);//对单链表进行排序
void reverse(List *list);//逆置单链表
void clear(List *list);//清除单链表
void destroy(List *list);//摧毁单链表
//代码优化
Node* CreateNode(ElemType x); //创建一个单链表结点
Node* begin(List *list); //返回单链表的第一个结点
Node* end(List *list); //返回单链表中最后一个结点的下一个结点
void insert(List *list, Node *pos, ElemType x); //在单链表的特定位置（pos）插入新的结点
#endif //__SLIST_H__

slist.cpp

#include"slist.h"
void InitList(List *list) {
  list->first = list->last = (Node*)malloc(sizeof(Node)); //头结点
  assert(list->first != NULL);
  list->first->next = NULL;
  list->size = 0;
}
//push_back的优化
void push_back(List *list, ElemType x) {
  insert(list, end(list), x);
}
//push_front的优化
void push_front(List *list, ElemType x) {
  insert(list, begin(list), x);
}
void show_list(List *list) {
  //step 1：指针p指向单链表的第一个结点
  Node *p = list->first->next;
  //step 2：循环打印结点的信息
  while (p != NULL) {
    printf("%d->", p->data);
    p = p->next;
  }
  printf("Nul.\n");
}
void pop_back(List *list) {
  //step 1：判断单链表是否为空
  if (list->size == 0) return;
  //step 2：定义指针p使其指向目标结点的前一个结点
  Node *p = list->first;//从头结点开始
  while (p->next != list->last)
    p = p->next;
  //step 3：删除目标结点
  free(list->last);
  list->last = p;
  list->last->next = NULL;
  //step 4：更新单链表的长度
  list->size--;
}
void pop_front(List *list) {
  //step 1：判断单链表是否为空
  if (list->size == 0) return;
  //step 2：定义指针p使其指向目标结点的前一个结点
  Node *p = list->first->next;
  //step 3：删除目标结点
  list->first->next = p->next;
  free(p);
  //step 4：判断删除的结点是否是单链表的最后一个结点，若是则更新单链表的尾指针
  if (list->size == 1)
    list->last = list->first;
  //step 4：更新单链表的长度
  list->size--;
}
//insert_val的优化
void insert_val(List *list, ElemType x) {
  //step 1：创建一个新的结点
  Node *s = CreateNode(x);
  //step 2：定义指针p使其指向待插入位置的前一个结点
  Node *p = list->first;//从头结点开始
  while (p->next != NULL && p->next->data < s->data)
    p = p->next;
  //step 3：判断结点的待插入位置是否是表尾，若是则更新单链表的尾指针
  if (p->next == NULL)
    list->last = s;
  //step 4：插入结点
  s->next = p->next;
  p->next = s;
  //step 5：更新单链表长度
  list->size++;
}
Node* find(List *list, ElemType x) {
  //step 1：指针p指向单链表的第一个结点
  Node *p = list->first->next;
  //step 2：按照循环顺序查找链表结点
  while (p != NULL && p->data != x)
    p = p->next;
  return p;
}
int length(List *list) {
  return list->size;
}
void delete_val(List *list, ElemType x) {
  //step 1：判断单链表是否为空
  if (list->size == 0) return;
  //step 2：确定结点在单链表中的位置，并判断其是否存在于单链表中
  Node *p = find(list, x);
  if (p == NULL) {
    printf("要删除的数据不存在！\n");
    return;
  }
  //step 3：判断结点位置是否是表尾
  if (p == list->last)//是表尾
    pop_back(list);
  else {//不是表尾
    Node *q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    list->size--;
  }
}
void sort(List *list) {
  //step 1：判断单链表中的结点数是否为0或1
  if (list->size == 0 || list->size == 1) return;
  //step 2：将单链表中第一个结点之后的链表部分截出，方便重新按顺序插入链表之中
  Node *s = list->first->next; // 指针s指向单链表的第一个节点
  Node *p = s->next;//q指向s后面的结点
  list->last = s;//单链表的尾指针指向单链表的第一个结点
  list->last->next = NULL;//截断链表
  //step 3：将截出的链表中的结点根据其数据域大小重新插入到原来链表中
  while (p != NULL) {
    s = p;
    p = p->next;
    Node *q = list->first;
    while (q->next != NULL && q->next->data < s->data)
      q = q->next;
    if (q->next == NULL)//判断q此时指向的是否是单链表的最后一个结点，若是则更新链表的尾指针
      list->last = s;
    //将结点重新插入链表
    s->next = q->next;
    q->next = s;
  }
}
void reverse(List *list) {
  //step 1：判断单链表中的结点数是否为0或1
  if (list->size == 0 || list->size == 1) return;
  //step 2：将单链表中第一个结点之后的链表部分截出，然后将截出的链表中的结点按头插法重新插入到原链表中
  Node *p = list->first->next;
  Node *q = p->next;
  list->last = p;
  list->last->next = NULL;
  while (q != NULL) {
    p = q;
    q = q->next;
    p->next = list->first->next;
    list->first->next = p;
  }
}
void clear(List *list) {
  //step 1：判断单链表是否为空
  if (list->size == 0) return;
  //step 2：释放单链表中的每一个结点
  Node *p = list->first->next;
  while (p != NULL) {
    list->first->next = p->next;
    free(p);
    p = list->first->next;
  }
  //step 3：头指针和尾指针重新都指向头结点
  list->last = list->first;
  //step 4：更新链表长度
  list->size = 0;
}
void destroy(List *list) {
  //step 1：清空单链表
  clear(list);
  //step 2：释放头结点
  free(list->first);
  //step 3：头指针和尾指针都赋值为空
  list->first = list->last = NULL;
}
//优化
Node* CreateNode(ElemType x) {
  Node *s = (Node*)malloc(sizeof(Node));
  assert(s != NULL);
  s->data = x;
  s->next = NULL;
  return s;
}
Node* begin(List *list) {
  return list->first->next;
}
Node* end(List *list) {
  return list->last->next;
}
void insert(List *list, Node *pos, ElemType x) {
  //step 1：创建一个新的结点
  Node *s = CreateNode(x);
  //step 2：确定带插入位置
  Node *p = list->first;
  while (p->next != pos)
    p = p->next;
  //step 3：插入结点
  s->next = p->next;
  p->next = s;
  //step 4：判断结点是否插入到链表的表尾，若是则更新单链表的表尾指针
  if (pos == NULL)
    list->last = s;
  //step 5：更新单链表长度
  list->size++;
}

main.cpp

#include"slist.h"
void main() {
  List mylist;
  InitList(&mylist);
  ElemType item;
  Node *p = NULL;
  int select = 1;
  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] reverse     [12] clear     *\n");
    printf("*[13*] destroy     [0] quit_system  *\n");
    printf("*******************************************\n");
    printf("请选择：>>");
    scanf("%d", &select);
    if (select == 0) break;
    switch (select) {
    case 1:
      printf("请输入要插入的数据（-1结束）:>");
      while (scanf("%d", &item), item != -1) {
        push_back(&mylist, item);
      }
      break;
    case 2:
      printf("请输入要插入的数据（-1结束）:>");
      while (scanf("%d", &item), item != -1) {
        push_front(&mylist, item);
      }
      break;
    case 3:
      show_list(&mylist);
      break;
    case 4:
      pop_back(&mylist);
      break;
    case 5:
      pop_front(&mylist);
      break;
    case 6:
      printf("请输入要插入的数据:>");
      scanf("%d", &item);
      insert_val(&mylist, item);
      break;
    case 7:
      printf("请输入要查找的数据:>");
      scanf("%d", &item);
      p = find(&mylist, item);
      if (p == NULL)
        printf("要查找的数据在单链表中不存在！\n");
      break;
    case 8:
      printf("单链表的长度为%d\n", length(&mylist));
      break;
    case 9:
      printf("请输入要删除的值:>");
      scanf("%d", &item);
      delete_val(&mylist, item);
      break;
    case 10:
      sort(&mylist);
      break;
    case 11:
      reverse(&mylist);
      break;
    case 12:
      clear(&mylist);
      break;
      //case 13:
      //destroy(&mylist);
      //break;
    default:
      printf("选择错误,请重新选择！\n");
      break;
    }
  }
  destroy(&mylist); //程序结束，摧毁链表
}

希望本文所述对大家C语言程序设计有所帮助。

 类似资料：
  • C语言实现单链表实现方法

    本文向大家介绍C语言实现单链表实现方法，包括了C语言实现单链表实现方法的使用技巧和注意事项，需要的朋友参考一下 C语言实现单链表实现方法 链表和我们之前实现过的顺序表一样，都是简单的数据结构，链表分为单向链表、双向链表、循环链表。而单向链表又分为两种实现方法，一种为带头节点的单链表，一种为不带头节点的单链表。我们来具体看看不带头节点的单链表的实现 单链表：它是一种链式存储的线性表，用一组地址任意的

  • Go语言单链表实现方法

    本文向大家介绍Go语言单链表实现方法，包括了Go语言单链表实现方法的使用技巧和注意事项，需要的朋友参考一下 本文实例讲述了Go语言单链表实现方法。分享给大家供大家参考。具体如下： 1. singlechain.go代码如下： 2. main.go代码如下： 希望本文所述对大家的Go语言程序设计有所帮助。

  • C语言单链表的实现

    本文向大家介绍C语言单链表的实现，包括了C语言单链表的实现的使用技巧和注意事项，需要的朋友参考一下 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。 链表结构： SList.h SList.cpp Test.cpp 以上内容是小编给大家介绍的C语言单链表的实现代码，希望对大家有所帮助！

  • C语言实现单链表反转

    本文向大家介绍C语言实现单链表反转，包括了C语言实现单链表反转的使用技巧和注意事项，需要的朋友参考一下 一、理解指针 看懂链表的结构并不是很难，但是一旦把它和指针混在一起，就很容易让人摸不着头脑。所以，要想写对链表代码，首先就要理解好指针。 　　有些语言有“指针”的概念，比如 C 语言；有些语言没有指针，取而代之的是“引用”，比如 Java、Python。不管是“指针”还是“引用”，实际上，它们的

  • C语言单向链表的表示与实现实例详解

    本文向大家介绍C语言单向链表的表示与实现实例详解，包括了C语言单向链表的表示与实现实例详解的使用技巧和注意事项，需要的朋友参考一下 1.概述： C语言中的单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。 链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。 如下图所示

  • C语言单循环链表的表示与实现实例详解

    本文向大家介绍C语言单循环链表的表示与实现实例详解，包括了C语言单循环链表的表示与实现实例详解的使用技巧和注意事项，需要的朋友参考一下 1.概述： 对于一个循环链表来说,其首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，可以选择开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储

相关阅读

C语言单向链表的表示与实现实例详解C语言单循环链表的表示与实现实例详解C语言单链队列的表示与实现实例详解C语言双向链表的表示与实现实例详解C语言单链表实现多项式相加

相关文章

C语言随机数C语言位运算C语言共用体C语言结构体C语言宏定义

相关问答

实现双重链表的remove方法C语言中的单向链表操作，复杂度为O（1）CMake无法用C确定链接器语言C语言中带递归的双链表插入c - C语言的链表该如何删除尾节点呢？

相关工具

C 语言入门教程语言岛智能记单词算法(Rust语言描述)神语言Shen语言

相关文档

C/C++ 语言参考通过实例学习 C 语言C 语言教程学习 C 语言C 语言编程透视
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.