C语言实现的双链表功能完整示例

2024-12-01 14:46:32

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

Dlist.h

#ifndef __DLIST_H__
#define __DLIST_H__
#include<cstdio>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;
typedef struct Node {
  ElemType data;
  struct Node *prio;
  struct Node *next;
}Node,*PNode;
typedef struct List {
  PNode first;
  PNode last;
  size_t size;
}List;
void InitDlist(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* _buynode(ElemType x);//创建结点
#endif

Dlist.cpp

#include"Dlist.h"
Node* _buynode(ElemType x) {
  Node *s = (Node*)malloc(sizeof(Node));
  assert(s != NULL);
  s->data = x;
  s->prio = s->next = NULL;
  return s;
}
void InitDlist(List *list) {
  Node *s = (Node*)malloc(sizeof(Node));
  assert(s != NULL);
  list->first = list->last = s;
  list->first->prio = NULL;
  list->last->next = NULL;
  list->size = 0;
}
void push_back(List *list, ElemType x) {
  Node *s = _buynode(x);
  s->prio = list->last;
  list->last->next = s;
  list->last = s;
  list->size++;
}
void push_front(List *list,ElemType x) {
  Node *s = _buynode(x);
  if (list->first == list->last) {
    s->prio = list->first;
    list->first->next = s;
    list->last = s;
  }
  else {
    s->next = list->first->next;
    s->next->prio = s;
    s->prio = list->first;
    list->first->next = s;
  }
  list->size++;
}
void show_list(List *list) {
  Node *p = list->first->next;
  while (p != NULL) {
    printf("%d->", p->data);
    p = p->next;
  }
  printf("Nul.\n");
}
void pop_back(List *list) {
  if (list->size == 0) return;
  Node *p = list->first;
  while (p->next != list->last)
    p = p->next;
  free(list->last);
  list->last = p;
  list->last->next = NULL;
  list->size--;
}
void pop_front(List *list) {
  if (list->size == 0) return;
  Node *p = list->first->next;
  if (list->first->next == list->last) {
    list->last = list->first;
    list->last->next = NULL;
  }
  else {
    list->first->next = p->next;
    p->next->prio = list->first;
  }
  free(p);
  list->size--;
}
void insert_val(List *list, ElemType x) {
  Node *p = list->first;
  while (p->next != NULL && p->next->data < x)
    p = p->next;
  if (p->next == NULL)
    push_back(list, x);
  else {
    Node *s = _buynode(x);
    s->next = p->next;
    s->next->prio = s;
    s->prio = p;
    p->next = s;
    list->size++;
  }
}
Node* find(List *list, ElemType x) {
  Node *p = list->first->next;
  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) {
  if (list->size == 0) return;
  Node *p = find(list, x);
  if (p == NULL) {
    printf("要删除的数据不存在！\n");
    return;
  }
  if (p == list->last) {
    list->last = p->prio;
    list->last->next = NULL;
  }
  else {
    p->next->prio = p->prio;
    p->prio->next = p->next;
  }
  free(p);
  list->size--;
}
void sort(List *list) {
  if (list->size == 0 || list->size == 1) return;
  Node *s = list->first->next;
  Node *q = s->next;
  list->last = s;
  list->last->next = NULL;
  while (q != NULL) {
    s = q;
    q = q->next;
    Node *p = list->first;
    while (p->next != NULL && p->next->data < s->data)
      p = p->next;
    if (p->next == NULL) {
      s->next = NULL;
      s->prio = list->last;
      list->last->next = s;
      list->last = s;
    }
    else {
      s->next = p->next;
      s->next->prio = s;
      s->prio = p;
      p->next = s;
    }
  }
}
void reverse(List *list) {
  if (list->size == 0 || list->size == 1) return;
  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;
    p->next->prio = p;
    p->prio = list->first;
    list->first->next = p;
  }
}
void clear(List *list) {
  if (list->size == 0) return;
  Node *p = list->first->next;
  while (p != NULL) {
    if (p == list->last) {
      list->last = list->first;
      list->last->next = NULL;
    }
    else {
      p->next->prio = p->prio;
      p->prio->next = p->next;
    }
    free(p);
    p = list->first->next;
  }
  list->size = 0;
}
void destroy(List *list) {
  clear(list);
  free(list->first);
  list->first = list->last = NULL;
}

main.cpp

#include "Dlist.h"
void main() {
  List mylist;
  InitDlist(&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++ 双链表之逆序的实例详解
利用C++实现双链表基本接口示例代码
C语言双向链表的表示与实现实例详解
C语言实现双向链表
C语言之双向链表详解及实例代码
C语言数据结构双向链表的建立与基本操作
C语言中双向链表和双向循环链表详解
C语言数据结构双向链表简单实例
C语言实现数据结构和双向链表操作

C/C++ 双链表之逆序的实例详解

C/C++ 双链表之逆序的实例详解一.结点结构双向链表的数据结构定义如下: typedef struct node { ElemType data; struct node *prior struct node *next; }list; 其中,ElemType可以是任意数据类型如int.float或者char等,在算法中,规定其默认为int类型. 二.带头结点本文描述的是双向链表逆序,链表逆序需要维护3个指针,分别指向前一个节点.当前节点和下一个节点,具体代码如下: list *reve
C语言实现双向链表

这个小代码是我凭自己对指针和链表的理解和认识,自己实现的,没有参考其他人的代码,如果有相同的地方,那真的只是巧合,代码我在ubuntu 15.04下测试通过,可能存在很多错误和漏洞． doublelist.c /************************************************************************* > File Name: doublelist.c > Author: ChenYiLiang > Mail: chenyilian
C语言实现数据结构和双向链表操作

数据结构双向链表的实现双向链表中的每一个结点都含有两个指针域,一个指针域存放其后继结点的存储地址,另一个指针域则存放其前驱结点的存储地址. 双向链表结点的类型描述: //双向链表的类型描述 typedef int ElemType; typedef struct node{ ElemType data; struct node *prior,*next; }DuLNode,*DuLinkList; 其中,prior域存放的是其前驱结点的存储地址,next域存放的是其后继结点的存储地址. 双
利用C++实现双链表基本接口示例代码

链表链表是一种物理存储单元上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的.链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成.每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域. 相比于线性表顺序结构,链表比较方便插入和删除操作. 本文主要给大家介绍了关于C++实现双链表基本接口的相关内容,分享出来供大家参考学习,话不多说,来一起看看详细的介绍吧. 首先先简单通过图示区分单链表和双链表的结构差异: 单链表
C语言数据结构双向链表简单实例

双向链表的基本操作 1．利用尾插法建立一个双向链表. 2．遍历双向链表. 3．实现双向链表中删除一个指定元素. 4．在非递减有序双向链表中实现插入元素e仍有序算法. 5．判断双向链表中元素是否对称若对称返回1否则返回0. 6．设元素为正整型,实现算法把所有奇数排列在偶数之前. 7．在主函数中设计一个简单的菜单调试上述算法. 实例代码: //排序的时候因为没有说明奇数和偶数需不需要各自再排序,我就没有排序,只是将奇数放在偶数后面. //创建链表的时候,因为这个实验没有要求输出链表的长度,所以我就输
C++ 双链表的基本操作(详解)

1.概念双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 结构图如下所示: 2.基本操作实例 DoubleList.cpp #include "stdafx.h" #include "DoubleList.h" #include <stdio.h> #include <malloc.h>
C语言数据结构双向链表的建立与基本操作

C语言数据结构双向链表的建立与基本操作双向链表比单链表有更好的灵活性,其大部分操作与线性表相同.下面总结双向链表与单链表之间的不同之处及我在实现过程中所遇到的问题. 1.双向链表的建立双向链表在初始化时,要给首尾两个节点分配内存空间.成功分配后,要将首节点的prior指针和尾节点的next指针指向NULL,这是十分关键的一步,因为这是之后用来判断空表的条件.同时,当链表为空时,要将首节点的next指向尾节点,尾节点的prior指向首节点. 2.双向链表的插入操作由于定义双向链表时指针域中
C数据结构之双链表详细示例分析

复制代码代码如下: typedef struct node{ struct node *prior; struct node *next; int num;}NODE;/*******双向链表的初始化********/NODE *Init_link(void){ int i; NODE *phead,*pb,*pi; phead = (NODE *)malloc(sizeof(NODE)); printf("please inpu
C语言之双向链表详解及实例代码

1,双向链表简介. 双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱.所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点.一般我们都构造双向循环链表. 2,例子要求: 完成双向链表的插入.删除以及查找,将学生管理系统使用的数组,以双向链表的方式实现,能够支持无限制的学生人数的增删改查以及保存. 3,代码实现. #include <stdio.h> #include <string.h> #include <
C语言中双向链表和双向循环链表详解

双向链表和双向循环链表和单向链表相比,多了一个前驱结点.如果他为空,那么next和prior都指向自己.而对于双循环链表,只需要最后一个元素的next指向head->next,head->next的prior指向最后一个节点即可. 插入操作新节点s插入链表,s->next给p结点,s->prior给p->prior,然后,p->prior->next指向s,p->prior再指向s.顺序需要注意 s->next = p; s->prior =
C语言双向链表的表示与实现实例详解

1.概述: C语言中一种更复杂的链表是"双向链表"或"双面链表".其表中的每个节点有两个连接:一个指向前一个节点,(当这个"连接"为第一个"连接"时,指向空值或者空列表):而另一个指向下一个节点,(当这个"连接"为最后一个"连接"时,指向空值或者空列表) 一个双向链表有三个整数值: 数值, 向后的节点链接, 向前的节点链接在一些低级语言中, XOR-linking 提供一种在双向链表中

C语言实现的双链表功能完整示例

您可能感兴趣的文章:

相关推荐

随机推荐