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

el/2024/7/17 21:54:16

大话数据结构

一、双向链表(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函数:

C++ Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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编程 一站式学习》

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
/*************************************************************************
    > 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;
    }
}

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
/*************************************************************************
    > 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:


http://www.ngui.cc/el/5557052.html

相关文章

系统级性能分析工具--Systemtap

SystemTap 是一款诊断Linux系统性能的工具&#xff0c;可以跟踪内核以及用户态程序中的任意函数、syscall、语句甚至指令&#xff0c;可以用来动态地收集调试和性能信息的工具&#xff0c;不需要我们重新编译、重启内核。缺点&#xff1a;用户需要自己编辑脚本测试文件。 假如…

Mac安装pillow模块

pip install --use-wheel Pillow

NumPy、Pandas、Matplotlib、 scipy机器学习库安装

NumPy系统是Python的一种开源的数值计算扩展。这种工具可用来存储和处理大型矩阵&#xff0c;比Python自身的嵌套列表&#xff08;nested list structure)结构要高效的多&#xff08;该结构也可以用来表示矩阵&#xff08;matrix&#xff09;&#xff09;。据说NumPy将Python相…

Mac下TensorFlow的部署和安装

$ sudo easy_install pip $ sudo easy_install --upgrade six $ sudo pip install --upgrade https://storage.googleapis.com/tensorflow/mac/tensorflow-0.8.0rc0-py2-none-any.whl 安装完成后&#xff0c;即可运行测试用例 $ python ... >>> import tensor…

Java编译后产生class文件的命名规则

今天刚好有同学问了下Java编译后产生的.class文件名的问题&#xff0c;虽然一直都在使用Java做开发&#xff0c;但是之前对编译后产生的.class文件名的规范也基本没做了解过&#xff0c;也真的是忏愧啊&#xff01;今天无论如何都要总结下。下面是本人今天做的实验 1、创建类Cl…

centos6.9 安装tensorflow心得体会

综述&#xff1a;centos安装tensorflow太坑了&#xff0c;如何你是个使用linux的新手&#xff0c;建议你不要尝试了&#xff0c;可以换ubuntu或者mac系统进行安装配置tensorflow。 难点一&#xff1a; importError: /lib64/libc.so.6: version GLIBC_2.14 not found import …

ubuntu错误 let: not found解决办法

错误描述&#xff1a;运行shell脚本&#xff0c;报错误 test.sh: 4: test.sh: let: not found 解决办法&#xff1a; Its because Ubuntu uses the dash shell as default and doesnt always recognize when you try to set the shell in a script. Even if you enter "…

Python两个内置函数——locals 、globals 和命名空间说明

Python两个内置函数—— locals 和 globals 这两个函数主要提供&#xff0c;基于字典的访问局部和全局变量的方式。 在理解这两个函数时&#xff0c;首先来理解一下python中的名字空间概念。 Python使用叫做名字空间的 东西来记录变量的轨迹 。名字空间只是一个字典&#xff0c…

Ubuntu16.04 安装bazel

一、首先&#xff0c;安装jdk8 这里省略jdk8的安装过程 二、在包资源中增加Bazel的发布源 echo "deb [archamd64] http://storage.googleapis.com/bazel-apt stable jdk1.8" | sudo tee /etc/apt/sources.list.d/bazel.list curl https://bazel.build/bazel-releas…

Numpy基础笔记(1)

Numpy简介 Numpy&#xff08;Numerical Python的简称&#xff09;是高性能科学计算和数据分析的基础包。其部分功能如下&#xff1a; ①ndarray&#xff0c;一个具有矢量算术运算和复杂广播能力的快速且节省空间的 多维数组 。 ②用于对整组数据进行快速运算的标准数学函数…