C语言实现循环双链表

本文实例为大家分享了C语言实现循环双链表的具体代码,供大家参考,具体内容如下

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int DataType;
typedef struct Node
{
    DataType data;            //    数据域
    struct Node * prior;      //    前趋指针
    struct Node * next;       //    后继指针 

}LinkList;

LinkList* Init_List();                                //    初始化循环双链表
bool Creat_List(LinkList * L);                        //    创建链表
int Length_List(LinkList * L);                        //    链表长度
bool Empty_List(LinkList * L);                        //    判空
bool Insert_List(LinkList * L, int pos, DataType x);  //    插入
bool Delete_List(LinkList * L, int pos, DataType * x);//    删除
bool Destroy_List(LinkList * L);                      //    销毁链表
bool Traverse_List(LinkList * L);                     //    遍历链表
int Prior_Value(LinkList * L, int pos);               //    前趋结点的值 

int main()
{
    DataType x;
    int pos;

    LinkList * L = Init_List();
    if(Creat_List(L))
        printf("链表构造成功!\n");
    else
        printf("链表构造失败!\n");
    printf("遍历链表:");
    Traverse_List(L);

    printf("链表结点个数:%d\n\n", Length_List(L));

    printf("输入要求前趋结点的结点:");
    scanf("%d",&pos);
    printf("第%d个结点的前趋结点:%d\n\n",pos,Prior_Value(L, pos));

    Insert_List(L, 2, 5);
    printf("插入结点:第2个结点\n");
    printf("插入元素:5\n");
    printf("遍历链表:");
    Traverse_List(L);

    Delete_List(L, 3, &x);
    printf("删除结点:第3个结点\n");
    printf("被删除元素:%d\n",x);
    printf("遍历链表:");
    Traverse_List(L);

    if(Destroy_List(L))
        printf("销毁成功!\n");
    else
        printf("销毁失败!\n");

    return 0;
} 

LinkList* Init_List()
{
    LinkList * L = (LinkList *)malloc(sizeof(LinkList));    //    创建头结点
    if(!L)
    {
        printf("申请空间失败!\n");
        exit(-1);
    }

    L->next = L->prior = L;    //    空表,前趋指针和后继指针均指向其自身
    return L;                 //    返回头结点的地址
}

bool Creat_List(LinkList * L)
{
    int i,n,val;
    LinkList * p = L;    //    保证L始终指向头结点 

    printf("请输入循环双链表的结点个数:");
    scanf("%d",&n);

    for(i=0; i<n; ++i)
    {
        printf("第%d个结点:",i+1);
        scanf("%d",&val);

        LinkList * q = (LinkList*)malloc(sizeof(LinkList));
        q->data = val;
        p->next = q;
        q->prior = p;
        p = q;
    }

    p->next = L;    //    保证最后一个结点的后继指针指向头结点
    L->prior = p;    //    保证头结点的前趋指针指向最后一个结点
    return true;
}

int Length_List(LinkList * L)
{
    int len = 0;
    LinkList * p = L->next;    

    while(p!=L)    //    最后一个结点也要加上
    {
        len++;
        p = p->next;
    }

    return len;
}

bool Empty_List(LinkList * L)
{
    if(L->next==L&&L->prior==L)
        return true;
    else
        return false;
}

bool Insert_List(LinkList * L, int pos, DataType x)
{
    int i = 1;
    LinkList * p = L->next;

    if(pos<1||pos>Length_List(L))
        return false;

    while(i<pos-1&&L!=p)    //    指针移动到被插入结点的前一个结点
    {
        i++;
        p = p->next;
    }

    LinkList * q = (LinkList*)malloc(sizeof(LinkList));
    q->data = x;
    q->next = p->next;
    q->prior = p;
    p->next->prior = q;
    p->next = q;
    return true;
}

bool Delete_List(LinkList * L, int pos, DataType * x)
{
    int i = 1;
    LinkList * p = L->next;

    if(pos<1||pos>Length_List(L))
        return false;

    while(i<pos-1&&L!=p)
    {
        i++;
        p = p->next;
    }

    LinkList * q = p->next;
    *x = q->data;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}

bool Destroy_List(LinkList * L)
{
//    将循环双链表变成单链表
    LinkList * p = L->next;
    L->next = NULL;        //    空表时, 头结点的前趋指针、后继指针都是指向其自身
    L->prior = NULL;    //    销毁时,头结点前趋指针、后继指针指向空 

    while(p)
    {
        LinkList * q = p->next;
        free(p);
        p = q;
    }

    L = p = NULL;
    return true;
}

bool Traverse_List(LinkList * L)
{
    if(Empty_List(L))
        return false;

    LinkList * p = L->next;

    while(p!=L)
    {
        printf("%3d",p->data);
        p = p->next;
    }

    printf("\n\n");

}

int Prior_Value(LinkList * L, int pos)
{
    int i = 1;
    LinkList * p = L->next;

    if(pos<1||pos>Length_List(L))
        return false;

    while(i<pos&&L!=p)    //    指向pos要求的结点
    {
        i++;
        p = p->next;
    }

    return p->prior->data;

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

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

    本文实例讲述了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; }

  • C语言实现循环双链表

    本文实例为大家分享了C语言实现循环双链表的具体代码,供大家参考,具体内容如下 #include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef int DataType; typedef struct Node { DataType data; // 数据域 struct Node * prior; // 前趋指针 struct Node * next; // 后继指针 }LinkList; LinkLis

  • 数据结构 C语言实现循环单链表的实例

    数据结构 C语言实现循环单链表的实例 实例代码: //=========杨鑫========================// //循环单链表的实现 #include <stdio.h> #include <stdlib.h> typedef int ElemType; //定义结点类型 typedef struct Node { ElemType data; struct Node *next; }Node,*LinkedList; int count = 0; //1.单循环

  • Go 语言数据结构之双链表学习教程

    目录 双链表 创建节点 双链表遍历 扩展功能 链表长度 插入 删除 反转双链表 总结 双链表 双链表 (Doubly Linked List),每个节点持有一个指向列表前一个元素的指针,以及指向下一个元素的指针. 双向链表的节点中包含 3 个字段: 数据域 Value 一个 Next 指针指向双链表中的下一个节点 一个 Prev 指针,指向双链表中的前一个节点 结构体如下: type Node struct { Prev *Node Value int Next *Node } 实际应用: 音乐

  • C语言用循环单链表实现约瑟夫环

    用循环单链表实现约瑟夫环(c语言),供大家参考,具体内容如下 源代码如下,采用Dev编译通过,成功运行,默认数到三出局. 主函数: main.c文件 #include <stdio.h> #include "head.h" #include "1.h" int main() { Linklist L; int n; printf("请输入约瑟夫环中的人数:"); scanf("%d",&n); Create

  • 详解java数据结构与算法之双链表设计与实现

    在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

  • C语言数据结构之单链表与双链表的增删改查操作实现

    目录 前言 单链表的增删改查 定义结构体以及初始化 增加结点 删除结点 查找修改结点 移除结点 最终效果 双链表的基本操作 初始化建表 遍历双链表 指定位置插入结点 指定位置删除结点 查找结点位置 最终效果 结语 前言 上篇博客分享了创建链表传入二级指针的细节,那么今天就分享几个c语言课程实践设计吧.这些程序设计搞懂了的话相当于链表的基础知识牢牢掌握了,那么再应对复杂的链表类的题也就能慢慢钻研了.学习是一个积累的过程,想要游刃有余就得勤学苦练! 单链表的增删改查 (1)项目需求 构造带有头结点的

  • C语言线性表之双链表详解

    目录 定义 1.删除 2.插入 3.建立 4.查找 总结 定义 链表是通过一组任意的存储单元来存储线性表中的数据元素,每一个结点包含两个域:存放数据元素信息的域称为数据域,存放其后继元素地址的域称为指针域.因此n个元素的线性表通过每个结点的指针域连接成了一个“链条”,称为链表.若此链表的每个结点中包含两个指针域,则被称为双链表. 双链表的结点结构定义如下: typedef struct node { DataType data; struct node *llink; struct node *

  • javascript数据结构之双链表插入排序实例详解

    本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

  • 简单介绍线性表以及如何实现双链表

    线性表是一种线性结构,它是具有相同类型的n(n≥0)个数据元素组成的有限序列. 一.数组 数组有上界和下界,数组的元素在上下界内是连续的. 存储10,20,30,40,50的数组的示意图如下: 数组的特点:数据是连续的:随机访问速度快. 数组中稍微复杂一点的是多维数组和动态数组.对于C语言而言,多维数组本质上也是通过一维数组实现的.至于动态数组,是指数组的容量能动态增长的数组:对于C语言而言,若要提供动态数组,需要手动实现:而对于C++而言,STL提供了Vector:对于Java而言,Colle

  • Python双链表原理与实现方法详解

    本文实例讲述了Python双链表原理与实现方法.分享给大家供大家参考,具体如下: Python实现双链表 文章目录 Python实现双链表 单链表与双链表比较 双链表的实现 定义链表节点 初始化双链表 判断链表是否为空 双链表尾部添加元素 双链表头部添加节点: 双链表表头删除 双链表按位置插入 双链表删除指定节点 完整代码 单链表与双链表比较 双链表比单链表多一个前驱指针位置,空间效率不占优势 由于双链表中的节点既可以向前也可以向后,相比单链表在查找方面效率更高(可使用二分法) 双链表的实现 定

随机推荐