数据结构:双向链表实现队列与循环链表

一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,除了插入和删除的时候需要更改两个指针变量,需要注意的是修改的顺序很重要,插入如图3-14-5,删除如图3-14-6。

链表的delete操作需要首先找到要摘除的节点的前趋,而在单链表中找某个节点的前趋需要从表头开始依次查找,对于n个节点的链表,删除操作的时间复杂度为O(n)。可以想像得到,如果每个节点再维护一个指向前趋的指针,删除操作就像插入操作(这里指只在头部插入)一样容易了,时间复杂度为O(1)。要实现双向链表只需在《图示单链表的插入和删除操作》中代码的基础上改动两个地方。

在linkedlist.h中修改链表节点的结构体定义: struct node

 { 

unsigned char item; 

link prev, next;

};

在linkedlist.c中修改insert和delete函数:

void insert(link p)
{
    p->next = head;
    if (head)
        head->prev = p;
    head = p;
    p->prev = NULL;
}
void delete(link p)
{
    if (p->prev)
        p->prev->next = p->next;
    else
        head = p->next;
    if (p->next)
        p->next->prev = p->prev;
}

由于引入了prev指针,insert和delete函数中都有一些特殊情况需要用特殊的代码处理,不能和一般情况用同样的代码处理,这非常不爽,如果在表头和表尾各添加一个Sentinel节点(这两个节点只用于界定表头和表尾,不保存数据),就可以把这些特殊情况都转化为一般情况了。如图26.6

在《队列的链式存储结构》中我们使用单链表实现队列的尾进头出,下面我们演示使用双向链表实现队列的头进尾出。

参考:《Linux C编程 一站式学习》

/*************************************************************************
    > File Name: doublylinkedlist.h
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: Fri 28 Dec 2012 08:02:35 PM CST
 ************************************************************************/

#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H

typedef structnode *link;

struct node
{
    unsigned char item;
    link prev;
    link next;
} ;

link make_node(unsigned char item);
void free_node(link p);
link search(unsigned char key);
void insert(link p);
void deletep(link p);
void traverse(void (*visit)(link));
void destroy(void);
void enqueue(link p);
link dequeue(void);

#endif

 C++ Code 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104

#include<stdio.h> #include<stdlib.h> #include "doublylinkedlist.h" struct node tailsentinel; struct node headsentinel = {0, NULL, &tailsentinel}; struct node tailsentinel = {0, &headsentinel, NULL}; static link head = &headsentinel; static link tail = &tailsentinel; link make_node(unsigned char item) {     link p =  malloc(sizeof(*p));     p->item = item;     p->prev = p->next = NULL;     printf("make node from Item %d\n", item);     return p; } void free_node(link p) {     printf("free node ...\n");     free(p); } link search(unsigned char key) {     link p;     printf("search by key %d\n", key);     for (p = head->next; p != tail; p = p->next)         if (p->item == key)             return p;     return NULL; } void insert(link p) {     printf("insert node from head ...\n");     p->next = head->next;     head->next->prev = p;     head->next = p;     p->prev = head; } void deletep(link p) {     printf("delete node from ptr ...\n");     p->prev->next = p->next;     p->next->prev = p->prev; } void traverse(void (*visit)(link)) {     link p;     printf("doublylinkedlist traverse ...\n");     for (p = head->next; p != tail; p = p->next)         visit(p);     printf("\n"); } void destroy(void) {     link q, p = head->next;     printf("destory doublylinkedlist ...\n");     head->next = tail;     tail->prev = head;     while (p != tail)     {         q = p;         p = p->next;         free_node(q);     } } void enqueue(link p) {     printf("enqueue from head ...\n");     insert(p); } link dequeue(void) {     if (tail->prev == head)         return NULL;     else     {         link p = tail->prev;         printf("dequeue from tail ...\n");         deletep(p);         return p;     } }

/*************************************************************************
    > File Name: main2.c
    > Author: Simba
    > Mail: dameng34@163.com
    > Created Time: Fri 28 Dec 2012 08:18:57 PM CST
 ************************************************************************/

#include<stdio.h>
#include "doublylinkedlist.h"

void print_item(link p)
{
    printf("print item %d \n", p->item);
}

int main(void)
{
    link p = make_node(10);
    insert(p);
    p = make_node(5);
    insert(p);
    p = make_node(90);
    insert(p);
    p = search(5);
    deletep(p);
    free_node(p);
    traverse(print_item);
    destroy();
    printf("..................\n");

    p = make_node(100);
    enqueue(p);
    p = make_node(200);
    enqueue(p);
    p = make_node(250);
    enqueue(p);
    while ((p = dequeue()))
    {
        print_item(p);
        free_node(p);
    }

    return 0;
}

输出为:

解决的error:

关于错误 error C2275: “XXX”: 将此类型用作表达式非法

在移植c++代码到c的时候,经常会出现一个奇怪的错误, error C2275: “XXX”: 将此类型用作表达式非法,这个错误是由于c的编译器要求将变量的定义放在所有函数调用语句之前,而c++没有这样的要求造成的。解决的办法就是把变量的定义全部放在变量的生存块的开始。

------------------------------------------------------------------------------------------------------------------------------------

二、将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环,这种头尾相接的单链表就称为单循环链表,

简称循环链表(circular linked list)。如下图所示。

其实循环链表和单链表的主要差异就在于循环的判断条件上,原来是判断p->next是否为空,现在则是p->next不等于头结点,则循环未结束。

我们在《队列的顺序存储结构(循环队列)》中使用数组实现了环形队列,我们还要“假想”它是首尾相接的,而如果基于链表实现环形队列,我们本来就可以用指针串成首尾相接的。把上面的程序改成双向环形链表也非常简单,只需要将

把doublylinkedlist.c中的 struct node tailsentinel;

struct node headsentinel = {0, NULL, &tailsentinel};

struct node tailsentinel = {0, &headsentinel, NULL};

static link head = &headsentinel;

static link tail = &tailsentinel;

改成:

struct node sentinel = {0, &sentinel, &sentinel};

static link head = &sentinel; 再把doublylinkedlist.c中所有的tail替换成head即可,相当于把head和tail合二为一了。如图26.7:

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏岑玉海

Carbondata源码系列(二)文件格式详解

在上一章当中,写了文件的生成过程。这一章主要讲解文件格式(V3版本)的具体细节。 1、字典文件格式详解 字典文件的作用是在存储的时候将字符串等类型转换为int类...

4206
来自专栏跟着阿笨一起玩NET

SQL Server数据库获取TEXT字段的内容长度的方法

SQL Server数据库如何获取TEXT字段的内容长度呢?本文我们就来介绍一下SQL Server数据库如何获取TEXT字段的内容长度的方法,是通过DATA...

593
来自专栏Golang语言社区

第十节 Go语言函数方法(下)

干货来了!!!为了让更多的小伙伴喜欢Golang、加入Golang之中来,Golang语言社区发起人彬哥联合业界大牛共同推出了Go语言基础、进阶、提高课程,目前...

681
来自专栏大愚Talk

Golang中函数传参存在引用传递吗?

官方文档已经明确说明:Go里边函数传参只有值传递一种方式,为了加强自己的理解,再来把每种传参方式进行一次梳理。

812
来自专栏用户2442861的专栏

《Java虚拟机原理图解》 1.1、class文件基本组织结构

http://blog.csdn.net/luanlouis/article/details/39892027

462
来自专栏分布式系统进阶

Librdkafka的基础数据结构 3 -- Buffer相关 1

872
来自专栏拂晓风起

C++调用C链接库会出现的问题

1073
来自专栏张善友的专栏

Enterprise Library 4 数据访问应用程序块

Enterprise Library 数据访问应用程序块简化了实现常规数据访问功能的开发任务。应用程序可以在各种场景中使用此应用程序块,例如为显示而读取数据、传...

2886
来自专栏程序员的知识天地

Python程序员必备的30个编程技巧

直接交换2个数字的位置 Python 提供了一种直观的方式在一行代码中赋值和交换(变量值)。如下所示:

482
来自专栏马洪彪

spss C# 二次开发 学习笔记(二)——Spss以及统计术语解释(IT人眼中的统计术语)

针对客户需求,需要对一些数据做统计分析。统计分析的第一步,即为数据查询,查找出要统计分析的数据。 查询得出的是一个行列表格的结果集,行、列、表格等这些IT的数据...

2605

扫码关注云+社区