第二章

队列

队列是一种特殊的线性结构，它只允许在队列的首部head进行删除，以及在尾部tail进行插入
这两种操作分别被称为“出队”和“入队”。而当队列中没有元素即head=tail时，称其为“空队列”

我们现在可以将队列的三个基本元素（一个数组，两个变量）封装为一个结构体类型

1
2
3
4
5
6
7
8
struct queue{
    int data[100] ; //存储内容的主体
    int head ;  //队首
    int tail ;  //队尾
};

//——————————————————————————
struct queuq q;//定义结构体变量，和其它数据类型一样

上面定义了以一个结构体类型，我们通常把它放在main外面，其定义末尾有一个;
其中，strcut是结构体的关键字，queue是我们为这个结构体起的名字
这个结构体有三个成员：整型数组data,整型head,tail。这样以来，我们就可以把它们当作一个整体来看待
访问结构体内的内部成员使用点(.)

下面这段代码就是我们用结构体实现队列操作的实例

##代码示例

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
struct queue{
    int data[100] ; //存储内容的主体
    int head ;  //队首
    int tail ;  //队尾
};

int main(){
    struct queue q ; 
    int i ;

    //下面初始化队列
    q.head = 1 ; 
    q.tail = 1 ;

    for(i = 1 ; i<= 9 ; i ++){
        //依次向队列中插入九个数
        scanf("%d",&q.data[q.tail]);
        q.tail++ ; 
    }

    while(q.head < q.tail){
        //当队列不为空的时候进行这个循环操作

        //打印队首并将队首出队
        printf("%d",q.data[q.head]);
        q.head++;

        //先将新的队首的数添加到队尾
        q.data[q.tail] = q.data[q.head];
        q.tail++;

        //再将队首出队
        q.head++ ;
    }

    getchar();getchar();
    return 0 ;
}

栈

栈是一种后进先出的数据结构，它就是栈
栈限定了它只能在一端进行插入和删除的操作，这决定了它“后进先出”的性质
栈的实现也比较简单：利用一个一维数组和一个指向栈顶部的变量（称它为top）即可，我们前面所讲的“插入”和“删除”的操作，就是通过这个”top”来实现的

入栈

入栈的操作很简易

1
2
top++ ； 
s[top] = x ; //s是定义出来储存的数组/char组

简化一下，就可以化成一行

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
s[++top] = a[i]; 
```  


### 代码实战
比如我们想要利用程序来检测一个字符串是否是回文
```c
//首先我们需要读取这个字符串
char a[101],s[101];
int i,len,mid,next,top ; 

gets(a);//读入一行字符串
len = strlen(a); // 得到字符串的长度
mid = len/2 -1 ; //得到字符串中心的那个数字

//下面进行栈的初始化
top = 0 ;
//将mid之前的字符依次入栈
for(i = 0 ; i <= mid  ; i++ ){
    s[++top] = a[i];
}

//之后判断字符串的长度是奇数还是偶数，并且找到我们需要进行字符匹配的起始下标
if(len%2 == 0 ){
    next = mid+1;
}else{
    next = mid+2; 
}

//开始进行字符的匹配
for(i=next;i<=len-1;i++){
    if(a[i] != s[top])
        break;
    top -- ; //向前检查
}

//如果top的值为0，则说明栈内所有的字符都被一一匹配了
if(top == 0 )   
    printf("YES");
else            
    printf("NO") ; 

getchar();getchar();
return 0 ;

链表(数组模拟)

链表也可以使用数组来实现，操作和基础知识比指针简单
但是个人觉得就思路和操作的清晰，以及对链表的理解而言，还是用指针好

模拟链表介绍

我们可以利用两个数组，分别记录链表要的两个东西：数据和地址
我们使用一个数组data，来存储每个结点的数据
使用另外一个数组right，来存储序列中每一个数右边的数的位置

比如现在二者如下：
位置 1 2 3 4 5 06 07 08 09
data: 2 3 5 8 9 10 18 26 32
right: 2 3 4 5 6 7 8 9 0

right[9] = 0 ,就代表data第九位的的右边没有数据

这里说一下，众所周知数组的第一位下标是0，但是书里按1开始算了
本着以书为本的原则，就没有修改，况且对于做链表而言也没区别
就是习惯了0开始数，看着难受

再如right[1]的值是2，指的是1号元素的右边的元素是2号元素（存放在data[2]中）

下面尝试按大小顺序，把6这个数值加入进去，那么该怎么做呢？
对于data数组比较简单，我们只需要做添加数据这个操作
让我们把这个数据添加到10号位置
位置 1 2 3 4 5 06 07 08 09 10
data: 2 3 5 8 9 10 18 26 32 6

对于right数组，会复杂一点，毕竟要排序和改地址
我们通过观察data数组，我们的6需要添加到5和8之间，也就是3号元素和4号元素之间

5对应的号数是3，8则是4.原本的地址是3号->4号，现在我们要加入6
那么我们新的次序是3号->10号->4号，即：
1.把3号“右边一位”改成10号
2.把10号“右边一位”改成4号
3.4号“右边一位”不变

位置 1 2 3 4 5 06 07 08 09 10
data: 2 3 5 8 9 10 18 26 32 6
right: 2 3 10 5 6 7 08 09 0 4

代码实例：

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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
# include <stdio.h>
int main(){
    int data[101],right[101];  //大小没有硬性要求，

    int i,n,t,len ; 

    //开始读入已有的数
    scanf("%d",&n) ; 

    for(i=1 ; i<=n ; i++){
        scanf("%d",&data[i]) ; 
    }

    len = n ; 

    //初始化数组

    for(i = 1 ; i<= n ,i++){
        if(i!=n)    right[i] = i+1;
        else        right[i] = 0 ;
    }

    //直接在数组data末尾增加一个数
    len++;
    scanf("%d",&data[len]);

    //从链表透开始遍历
    t = 1 ;
    while(t!=0){
        if(data[right[t]] > date[len]){
            //如果当前结点的下一结点的值大于待插入数，则把数插入
            right[len] = right[t];
            //新插入的数的下一结点的编号，等于当前结点的下一结点编号  

            right[t] = len ; 
            //当前结点的下一个结点编号，就是新插入的数的编号

            break ; //插入完成，我们跳出循环
        }

        t = right[t] ;
    }

    //输出链表中所有的数
    t = 1 ;
    while(t!=0){
        printf("%d",data[t]);
        r = tight[t] ; //根据right数组的设置，读取下一个数
    }
    
    getchar();
    getchar();

    return 0 ;
}
```  

### 小结    
模拟链表以两个对应的数组，代替了指针    
两者各有优劣，但是指针用的应该更多，毕竟你数组大小存在着限制    
可以把模拟链表作为简单/削弱版的链表     
不过，使用模拟链表一样可以实现双向链表和循环链表，这里就先不提了    

# 链表(指针)  
在存储一大波数的时候，如果使用数组，有时会感到数组显得不太灵活  
我们可以在C语言中使用指针和动态分配函数malloc来实现**链表**  
>关于指针，这里就不赘述了，默认已经了解相关知识  
  
### 指针实现  
##### malloc 
malloc 函数的作用就是从内存中申请分配指定**字节大小**的内存空间  
```c
malloc(4);  //这样就申请了四个字节大小的内存空间
```  
  
>如果不知道字节大小，那么使用sizeof()查看就好了  

malloc 函数的返回值是void*，也就是未确定类型的指针，它可以被强制转换为任何其它类型的指针  
```c
int *p ; 
p = (int *)malloc(sizeof(int)) ; 
```  
比如这样我们就得到了一个整型的指针，它可以存放整数  
>指针变量存放的是一个内存空间的首地址(第一个字节的地址)
>但是这个空间占用了多少个字节，用来存储什么类型的数据，则是由指针类型标明的  
下面让我们来实战试试这玩意  

### 代码实例  
```c
#include <stdio.h>
#include <stdlib.h>

int main(){
    int *p ;  //定义一个指针
    p = (int *)malloc(sizeof(int)) ; //指针p来获取动态分配的内存空间地址
    *p = 10  ; //向指针p所指向的内存空间存入10
    printf("%d",*p); //输出指针p所指向的内存中的值

    getchar();getchar();
    return 0 ;
}

```  

现在我们尝试使用链表

### 构建链表  
我们把链表存储数据的地方叫做**结点**，每一个结点有两个部分组成    
一部分用来存储具体数值，另一部分存储下一个结点的位置  
```c
struct node{
    int data ; 
    struct node *next ; 
}
```  

OK,我们已经定义了一个相关的结构体，那么下一步我们来构建链表  
1.首先，我们需要一个头指针head来指向链表的最开始的地方(链表还没有建立的时候头指针为空/指向空结点)  
2.创建一个结点，设置所需要的两个部分。这里顺便一提，访问结构体内部成员使用```->```而非点```.```，因为我们要访问的p是一个指针  
3.设置头指针  
### 代码实例  
```c
#include <stdio.h>
#include <stdlib.h>

//创建一个结构体表示链表的结点类型  
    struct node{
    int data ; 
    struct node *next ; 
} 

int main(){
    //相关变量
    struct node *head,*p,*q,*t ; 
    int i,n,a ; 

    scanf("%d",&n);//读入多少数

    head = NULL ; //头指针为空
    for(i=1;i<=n,i++){
        //利用循环读入n个数
        scanf("%d",&a);
        //动态申请一个空间来存放一个结点，并且使用临时指针p来指向这个结点  
        p = (struct node *)malloc(sizeof(struct node));
        p->data = a ; //把刚才读到的数据存储到当前结点的data域中
        p->next = NULL ; //设置当前结点的后继指针指向空。也就是当前结点的一个结点为空

        if(head == NULL){
            head = p ; //如果是第一个创建的结点，则把头指针指向他
        }else{
            q->next = p ;//如果不是第一个，那么将上一个结点的后继指针指向当前结点
        }

        q = p ; //把q也指向这个结点  
    }

    //下面试一下输出链表所有数
    t = head ; 
    while(t!=NULL){
        printf("%d",t->data);
        t = t->next ; //继续下一个结点
    }

    getchar();getchar();

    return 0 ;
}

如上所示，我们得到了一个链表。但是只得到链表是不够的，我们还需要加减数据

链表数据的加减

这里以加数据为例子，删数据同理。方法如下：
1.创建一个临时指针，并且从链表头部一直往下遍历
2.按照条件筛选位置，成功后，将对应的指针修改。让这个被添加的数据处于原本前后两个地址的中间

增加数据的代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//下面来读数据  
scanf("%d",&a) ; 

t = head ; //t是临时指针，从链表的头部开始遍历  
while(t!=NULL){
    //没有到达链表尾部之前，我们都进行循环遍历  
    if(t->next == NULL  || t->next->data > a){
        //如果当前结点是最后一个结点，或者我们找到了需要插入的位置
        //这里以“按顺序插入”为例子

        p = (struct node *)malloc(sizeof(struct node)) ; 
        //动态申请一个空间，来存放新结点  
        p->data = a ;
        p->next = t->next ; 
        //新增结点的后续指针，当然是要指向当前指针后继指针指向的点
        t->next = p ;
        //当前结点的后继指针指向新增结点

        break; //插入完毕时退出循环
    }

    t = t->next ; 
}

含插入的完整代码

#include <stdio.h>
#include <stdlib.h>

//创建一个结构体表示链表的结点类型  
    struct node{
    int data ; 
    struct node *next ; 
} 

int main(){
    //相关变量
    struct node *head,*p,*q,*t ; 
    int i,n,a ; 

    scanf("%d",&n);//读入多少数

    head = NULL ; //头指针为空
    for(i=1;i<=n,i++){
        //利用循环读入n个数
        scanf("%d",&a);
        //动态申请一个空间来存放一个结点，并且使用临时指针p来指向这个结点  
        p = (struct node *)malloc(sizeof(struct node));
        p->data = a ; //把刚才读到的数据存储到当前结点的data域中
        p->next = NULL ; //设置当前结点的后继指针指向空。也就是当前结点的一个结点为空

        if(head == NULL){
            head = p ; //如果是第一个创建的结点，则把头指针指向他
        }else{
            q->next = p ;//如果不是第一个，那么将上一个结点的后继指针指向当前结点
        }

        q = p ; //把q也指向这个结点  
    }

    //下面我们尝试插入数据
    scanf("%d",&a) ; 

    t = head ; //t是临时指针，从链表的头部开始遍历  
    while(t!=NULL){
    //没有到达链表尾部之前，我们都进行循环遍历  
    if(t->next == NULL  || t->next->data > a){
        //如果当前结点是最后一个结点，或者我们找到了需要插入的位置
        //这里以“按顺序插入”为例子

        p = (struct node *)malloc(sizeof(struct node)) ; 
        //动态申请一个空间，来存放新结点  
        p->data = a ;
        p->next = t->next ; 
        //新增结点的后续指针，当然是要指向当前指针后继指针指向的点
        t->next = p ;
        //当前结点的后继指针指向新增结点

        break; //插入完毕时退出循环
    }

    t = t->next ; //继续下一个结点
}


    //下面试一下输出链表所有数
    t = head ; 
    while(t!=NULL){
        printf("%d",t->data);
        t = t->next ; //继续下一个结点
    }

    getchar();getchar();

    return 0 ;
}

小结

个人认为利用指针，能更好地理解链表的思想
虽然学习和消化的时间比较长，但是是值得的
下一节，还有不用指针的模拟链表，但是个人认为少了那种精髓