SatParamita六到彼岸

诵持三藏经律论 勤修六度波罗蜜

0%

数据结构-队列

无链表队列-车厢进出问题

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
#include <stdio.h>
#define BufferLen 100
struct Queue
{
    int Buffer[BufferLen];
    int head, tail; // head指向下一个出队元素，tail指向下一个入队位置
};
void swap(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
/*
int InitQueue(Queue *Q)
{
    Q->head = 0;
    Q->tail = 0;
    return 0;
}
调用 InitQueue(&Q)
*/
int InitQueue(Queue &Q)
{
    Q.head = 0;
    Q.tail = 0;
    return 0;
}
int push(Queue &Q, int data)
{
    if (((Q.tail + 1) % BufferLen) == Q.head)
        return -1;

    Q.Buffer[Q.tail] = data;
    Q.tail = (Q.tail + 1) % BufferLen;
    return 0;
}
int push_min(Queue &Q, int data)
// 约定出队时，值最小的元素出队
{
    if (((Q.tail + 1) % BufferLen) == Q.head)
        return -1;

    Q.Buffer[Q.tail] = data;
    Q.tail = (Q.tail + 1) % BufferLen;

    for (int i = Q.tail; i != Q.head; i = (i - 1) % BufferLen)
    {
        int j = (i - 1 + BufferLen) % BufferLen;
        if (Q.Buffer[j] <= data)
            break;
        swap(Q.Buffer[i], Q.Buffer[j]);
    }
    return 0;
}
bool empty(Queue &Q)
{
    return Q.head == Q.tail;
}
int top(Queue &Q)
{
    return Q.Buffer[Q.head]; //先进先出
}
int pop(Queue &Q)
{
    Q.head = (Q.head + 1) % BufferLen;
    return 0;
}

int main()
{
    struct Queue Q;
    InitQueue(Q);

    //先进先出
    int op, n = 1, m;
    while (scanf("%d", &op) == 1)
    {
        if (op == 0)
        {
            printf("%d号车厢运货进站。\n", n);
            push(Q, n);
            //push_min(Q, n); // 约定出队时，值最小的元素出队
            n++;
        }
        else if (op == 1)
        {
            if (empty(Q))
                printf("没有可用的车厢！\n");
            else
            {
                m = top(Q); //先进先出
                printf("%d号车厢运货出站。\n", m);
                pop(Q);
            }
        }
    }
    return 0;
}

链表队列-车厢进出问题

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
#include <stdio.h>
#define BufferLen 100

struct QueueNode
{
    int data;
    struct QueueNode *next;
};

struct Queue
{
    struct QueueNode *head, *tail; // head为出队端，tail指向入队端
};

int InitQueue(Queue &Q)
{
    Q.head = NULL;
    Q.tail = NULL;
    return 0;
}
bool empty(Queue &Q)
{
    return Q.head == NULL;
}
int push(Queue &Q, int data)
{
    struct QueueNode *q = new QueueNode;
    q->data = data;
    q->next = NULL;
    if (empty(Q)) //开始是空的
    {
        Q.head = q;
        Q.tail = q;
    }
    else
    {
        Q.tail->next = q; //尾插法
        Q.tail = q;
    }
    return 0;
}

int top(Queue &Q)
{
    return Q.head->data; //先进先出
}
int pop(Queue &Q)
{
    struct QueueNode *q;
    q = Q.head;
    Q.head = Q.head->next;
    delete q;
    if (Q.head == NULL)
        Q.tail = NULL;
    return 0;
}

int DestroyQueue(Queue &Q)
{
    struct QueueNode *q;
    while (Q.head != NULL)
    {
        q = Q.head;
        Q.head = Q.head->next;
        delete q;
    }
    Q.tail = NULL;
    return 0;
}
int main()
{
    //先进先出
    struct Queue Q;
    InitQueue(Q);
    int op, n = 1, m;

    while (scanf("%d", &op) == 1)
    {
        if (op == 0)
        {
            printf("%d号车厢运货进站。\n", n);
            push(Q, n);
            n++;
        }
        else if (op == 1)
        {
            if (empty(Q))
                printf("没有可用的车厢！\n");
            else
            {
                m = top(Q);
                printf("%d号车厢运货出站。\n", m);
                pop(Q);
            }
        }
    }
    DestroyQueue(Q);
    return 0;
}

顺序循环队列

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <stdio.h>
#define QueueSize 10   /*定义顺序循环队列的最大容量*/
typedef char DataType; /*定义顺序循环队列元素的类型为字符类型*/
typedef struct SeqQueue
{ /*顺序循环队列的类型定义*/
    DataType queue[QueueSize];
    int front, rear; /*队头指针和队尾指针*/
    int tag;         /*队列空、满的标志，不重要*/
} SeqQueue;

void InitQueue(SeqQueue *SQ)
/*将顺序队列初始化为空队列，只需要把队头指针和队尾指针同时置为0*/
{
    SQ->front = SQ->rear = 0; /*把队头指针和队尾指针同时置为0*/
}
int QueueEmpty(SeqQueue SQ)
/*判断队列是否为空，队列为空返回1，否则返回0*/
{
    if (SQ.front == SQ.rear) /*判断队头指针和队尾指针是否相等*/
        return 1;            /*当队列为空时，返回1；否则返回0*/
    else
        return 0;
}
int EnterQueue(SeqQueue *SQ, DataType e)
/*将元素e插入到顺序队列SQ中，插入成功返回1，否则返回0*/
{
    if (SQ->rear == QueueSize) /*判断队尾指针是否到达数组的最大值，即是否队列已满*/
        return 0;

    SQ->queue[SQ->rear] = e; /*在队尾插入元素x */
    SQ->rear = SQ->rear + 1; /*队尾指针向后移动一个位置*/
    return 1;
}
int DeleteQueue(SeqQueue *SQ, DataType *e)
/*删除顺序队列中的队头元素，并将该元素赋值给e，删除成功返回1，否则返回0*/
{
    if (SQ->front == SQ->rear) /*在删除元素之前，判断队列是否为空*/
        return 0;

    *e = SQ->queue[SQ->front]; /*将要删除的元素赋值给e*/
    SQ->front = SQ->front + 1; /*将队头指针向后移动一个位置，指向新的队头*/
    return 1;
}
void DisplayQueue(SeqQueue SQ)
/*顺序循环队列的显示输出函数。首先判断队列是否为空，输出时还应考虑队头指针和队尾指针值的大小问题*/
{
    if (QueueEmpty(SQ)) /*判断顺序循环队列是否为空*/
        return;

    if (SQ.front < SQ.rear)
        /*如果队头指针值小于队尾指针的值，则把队头指针到队尾指针指向的元素依次输出*/
        for (int i = SQ.front; i <= SQ.rear; i++)
            printf("%c", SQ.queue[i]);
    else
        /*如果队头指针值大于队尾指针的值，则把队尾指针到队头指针指向的元素依次输出*/
        for (int i = SQ.front; i <= SQ.rear + QueueSize; i++)
            printf("%c", SQ.queue[i % QueueSize]);
    printf("\n");
}
//求环形队列中元素的个数
int ComputeCount(SeqQueue SQ)
{
	int count = (SQ.rear - SQ.front + QueueSize) % QueueSize;
	return count;
}
int main()
{
    SeqQueue Q;    /*定义一个顺序循环队列*/
    InitQueue(&Q); /*初始化顺序循环队列*/
                   /*将3个元素A，B，C依次进入顺序循环队列*/
    printf("A入队\n");
    EnterQueue(&Q, 'A');
    printf("B入队\n");
    EnterQueue(&Q, 'B');
    printf("C入队\n");
    EnterQueue(&Q, 'C');
    /*将顺序循环队列中的元素显示输出*/
    printf("队列中元素：");
    DisplayQueue(Q);
    /*将顺序循环队列中的队头元素出队列*/
    printf("队头元素第一次出队\n");
    char e; /*定义一个字符类型变量，用于存放出队列的元素*/
    DeleteQueue(&Q, &e);
    printf("出队的元素：");
    printf("%c\n", e);
    printf("队头元素第二次出队\n");
    DeleteQueue(&Q, &e);
    printf("出队的元素：");
    printf("%c\n", e);
    /*将顺序循环队列中的元素显示输出*/
    printf("队列中元素：");
    DisplayQueue(Q);
    /*将3个元素D，E，F依次进入顺序循环队列*/
    printf("D入队\n");
    EnterQueue(&Q, 'D');
    printf("E入队\n");
    EnterQueue(&Q, 'E');
    printf("F入队\n");
    EnterQueue(&Q, 'F');
    /*将顺序循环队列中的元素显示输出*/
    printf("队列中元素：");
    DisplayQueue(Q);



    int a[] = {34, 3, 56, 43, 21, 51, 46, 89, 98, 76};
    InitQueue(&Q);
    for (int i = 0; i < 10; i++)
        EnterQueue(&Q, a[i]);
    printf("队列中的元素个数是：%2d\n", ComputeCount(Q));
    printf("出队列的元素依次是：");
    for (int i = 0; i < 10; i++)
    {
        DeleteQueue(&Q, &e);
        printf("%4d", e);
    }
    printf("\n清空队列后，队列中的元素个数是：%2d\n", ComputeCount(Q));

    return 0;
}

带头结点的链式队列

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <stdio.h>     
#include <stdlib.h>    
typedef struct QNode
{
	int data;
	struct QNode *next;
} LQNode, *QueuePtr;

typedef struct
{
	QueuePtr front;
	QueuePtr rear;
} LinkQueue;

void InitQueue(LinkQueue *LQ)
/*将带头结点的链式队列初始化为空队列需要把头结点的指针域置为0*/
{
	LQ->front = (LQNode *)malloc(sizeof(LQNode));
	LQ->front->next = NULL; /*把头结点的指针域置为为0*/
	LQ->rear = LQ->front;
}
int QueueEmpty(LinkQueue LQ)
/*判断链式队列是否为空，队列为空返回1，否则返回0*/
{
	if (LQ.front->next == NULL) /*当链式队列为空时，返回1，否则返回0*/
		return 1;
	else
		return 0;
}
int EnterQueue(LinkQueue *LQ, int e)
/*将元素e插入到链式队列LQ中，插入成功返回1*/
{
	LQNode *s = (LQNode *)malloc(sizeof(LQNode)); /*为将要入队的元素申请一个结点的空间*/
	s->data = e;		/*将元素值赋值给结点的数据域*/
	s->next = NULL;		/*将结点的指针域置为空*/
	LQ->rear->next = s; /*将原来队列的队尾指针指向p*/
	LQ->rear = s;		/*将队尾指针指向p*/
	return 1;
}
int DeleteQueue(LinkQueue *Q, int *x)
/* 将队列Q的队头元素出队，并存放到x所指的存储空间中 */
{
	if (Q->front == Q->rear)
		return 0;

	LQNode *p = Q->front->next;
	Q->front->next = p->next; /* 队头元素p出队 */
	if (Q->front == NULL)	  /* 如果队中只有一个元素p，则p出队后成为空队 */
		Q->rear = Q->front;
	*x = p->data;
	free(p); /* 释放存储空间 */
	return 1;
}
int DeleteQueue_1(LinkQueue *LQ, int *e)
/*删除链式队列中的队头元素，并将该元素赋值给e，删除成功返回1，否则返回0*/
{
    if (LQ->front == LQ->rear) /*在删除元素之前，判断链式队列是否为空*/
        return 0;

    LQNode *s = LQ->front->next; /*使指针p指向队头元素的指针*/
    *e = s->data;                /*将要删除的队头元素赋值给e*/
    LQ->front->next = s->next;   /*使头结点的指针指向指针p的下一个结点*/
    if (LQ->rear == s)
        LQ->rear = LQ->front; /*如果要删除的结点是队尾，则使队尾指针指向队头指针*/
    free(s);                  /*释放指针p指向的结点*/
    return 1;
}
int GetHead(LinkQueue LQ, int *e)
/*取链式队列中的队头元素，并将该元素赋值给e，取元素成功返回1，否则返回0*/
{
    if (LQ.front == LQ.rear) /*在取队头元素之前，判断链式队列是否为空*/
        return 0;

    LQNode *s = LQ.front->next; /*将指针p指向队列的第一个元素即队头元素*/
    *e = s->data;               /*将队头元素赋值给e，取出队头元素*/
    return 1;
}
/* 从队头到队尾依次对队列Q中每个元素输出 */
int QueueTraverse(LinkQueue Q)
{
    for (LQNode *p = Q.front->next; p != NULL; p = p->next)
        printf("%d ", p->data);
    return 1;
}
int QueueLength(LinkQueue Q)
{
    int i = 0;
    for (LQNode *p = Q.front; p != Q.rear; p = p->next)
        i++;
    return i;
}
int DestroyQueue(LinkQueue *Q) /* 销毁队列Q */
{
    while (Q->front)
    {
        Q->rear = Q->front->next;
        free(Q->front);
        Q->front = Q->rear;
    }
    return 1;
}
int ClearQueue(LinkQueue *Q) /* 清空队列 */
{
    Q->rear = Q->front;
    LQNode *p = Q->front->next;
    Q->front->next = NULL;
    while (p)
    {
        LQNode *q = p;
        p = p->next;
        free(q);
    }
    return 1;
}
int main()
{
    LinkQueue q;
    InitQueue(&q);
    printf("是否空队列？%d(1:空 0:否)  ", QueueEmpty(q));
    printf("队列的长度为%d\n", QueueLength(q));

    EnterQueue(&q, -5);
    EnterQueue(&q, 5);
    EnterQueue(&q, 10);
    printf("插入3个元素(-5,5,10)后,队列的长度为%d\n", QueueLength(q));
    printf("队列的元素依次为：");
    QueueTraverse(q);
    
    int d;
    if (GetHead(q, &d) == 1)
        printf("\n队头元素是：%d\n", d);

    DeleteQueue(&q, &d);
    printf("删除了队头元素%d\n", d);

    if (GetHead(q, &d) == 1)
        printf("新的队头元素是：%d\n", d);

    ClearQueue(&q);
    printf("清空队列后,q.front=%u q.rear=%u q.front->next=%u\n", q.front, q.rear, q.front->next);

    DestroyQueue(&q);
    printf("销毁队列后,q.front=%u q.rear=%u\n", q.front, q.rear);

    return 0;
}

双端队列

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
#include <stdio.h>     /*包含输出函数*/
#define QueueSize 8    /*定义双端队列的大小*/
typedef char DataType; /*定义数据类型为字符类型*/
typedef struct DQueue  /*双端队列的类型定义*/
{
    DataType queue[QueueSize];
    int end1, end2; /*双端队列的队尾指针*/
} DQueue;
int EnterQueue(DQueue *DQ, DataType e, int tag)
/*将元素e插入到双端队列中。如果成功返回1，否则返回0*/
{
    switch (tag)
    {
    case 1:                       /*1表示在队列的左端入队*/
        if (DQ->end1 != DQ->end2) /*元素入队之前判断队列是否为满*/
        {
            DQ->queue[DQ->end1] = e;               /*元素e入队*/
            DQ->end1 = (DQ->end1 - 1) % QueueSize; /*向左移动队列指针*/
            return 1;
        }
        else
            return 0;
    case 2:                       /*1表示在队列的左端入队*/
        if (DQ->end1 != DQ->end2) /*元素入队之前判断队列是否已满*/
        {
            DQ->queue[DQ->end2] = e;               /*元素e入队*/
            DQ->end2 = (DQ->end2 + 1) % QueueSize; /*向右移动队列指针*/
            return 1;
        }
        else
            return 0;
    }
    return 0;
}
int DeleteQueue(DQueue *DQ, DataType *e, int tag)
/*将元素出队列，并将出队列的元素赋值给e。如果出队列成功返回1，否则返回0*/
{
    switch (tag)
    {
    case 1:                                           /*1表示在队列的左端出队*/
        if (((DQ->end1 + 1) % QueueSize) != DQ->end2) /*在元素出队列之前判断队列是否为空*/
        {
            DQ->end1 = (DQ->end1 + 1) % QueueSize; /*向右移动队列指针，将元素出队列*/
            *e = DQ->queue[DQ->end1];              /*将出队列的元素赋值给e*/
            return 1;
        }
        else
            return 0;
    case 2:
        if (((DQ->end2 - 1) % QueueSize) != DQ->end1) /*在元素出队列之前判断队列是否为空*/
        {
            DQ->end2 = (DQ->end2 - 1) % QueueSize; /*向左移动队列指针，将元素出队列*/
            *e = DQ->queue[DQ->end2];              /*将出队列的元素赋值给e*/
            return 1;
        }
        else
            return 0;
    }
    return 0;
}
int main()
{
    DQueue Q;   /*定义双端队列Q*/
    char ch;    /*定义字符*/
    Q.end1 = 3; /*设置队列的初始状态*/
    Q.end2 = 4;
    /*将元素a，b，c在队列左端入队*/
    if (!EnterQueue(&Q, 'a', 1)) /*元素左端入队*/
        printf("队列已满，不能入队！");
    else
        printf("a左端入队：\n");
    if (!EnterQueue(&Q, 'b', 1))
        printf("队列已满，不能入队！");
    else
        printf("b左端入队：\n");
    if (!EnterQueue(&Q, 'c', 1))
        printf("队列已满，不能入队！");
    else
        printf("c左端入队：\n");
    /*将元素d，e在队列右端入队*/
    if (!EnterQueue(&Q, 'd', 2)) /*元素右端入队*/
        printf("队列已满，不能入队！");
    else
        printf("d右端入队：\n");
    if (!EnterQueue(&Q, 'e', 2))
        printf("队列已满，不能入队！");
    else
        printf("e右端入队：\n");
    /*元素c，b，e，d依次出队列*/
    printf("队列左端出队一次：");
    DeleteQueue(&Q, &ch, 1); /*元素左端出队列*/
    printf("%c\n", ch);
    printf("队列左端出队一次：");
    DeleteQueue(&Q, &ch, 1);
    printf("%c\n", ch);
    printf("队列右端出队一次：");
    DeleteQueue(&Q, &ch, 2); /*元素右端出队列*/
    printf("%c\n", ch);
    printf("队列右端出队一次：");
    DeleteQueue(&Q, &ch, 2);
    printf("%c\n", ch);
}