投稿
  1. 高性能架构探索首页
  2. C/C++

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

admin • • C/C++ • 阅读 342

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

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

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

由于引入了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 
struct node

{

    
unsigned 
char item;

    
struct node *prev;

    
struct node *next;

} node;

typedef node *link;

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

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

#include<stdio.h>

#include<stdlib.h>

#include 
"doublylinkedlist.h"

node tailsentinel;

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

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

static link head = &headsentinel;

static link tail = &tailsentinel;

link make_node(
unsigned 
char item)

{

    link p =  malloc(
sizeof(node));

    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中的
node tailsentinel;

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

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

static link head = &headsentinel;

static link tail = &tailsentinel;

改成：

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

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

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



 


 

原文链接: https://www.cnblogs.com/javawebsoa/archive/2013/04/26/3045554.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

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

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/86133

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

赞 (0)
adminadmin
0 0
上一篇 2023年2月9日 下午10:24
下一篇 2023年2月9日 下午10:24

相关推荐