栈结构——顺序栈、链栈

Published on:
Tags: 数据结构 栈

栈结构的定义和属性#

定义：栈是一种与线性表相似的线性结构。
不同之处是当需要对节点做增删操作时，只能操作栈顶的节点，因此具有先进后出（或者后进先出）的特点。

按存储结构的不同，可分为顺序栈和链栈。

栈结构的几个属性：

  • 栈顶/栈底：可接受节点增删操作的一端称为栈顶，另一端称为栈底
  • 入栈：在栈顶一端新增节点的操作称为入栈
  • 出栈：在栈顶一端删除节点的操作称为出栈
  • 栈满：当栈中节点超过允许存储空间时，表示栈满（链栈无栈满的状态）
  • 栈空：当栈中无节点元素时，表示栈空

栈结构的抽象数据类型#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ADT Stack
{
数据对象：
    D = {ai | ai ∈ ElemType, i=1,2,…,n, n>=0 }              // ElemType为类型标识符
数据关系：
    R = {<ai, ai+1> | ai, ai+1∈D, i=1,3,…,n-1 }
数据操作：
    (1) stackSeq * InitStack();    				//	初始化栈
    (2) void DestroyStack(stackSeq *s); 		//	销毁栈
    (3) Bool StackEmpty(stackSeq *s);   		//	栈是否为空
    (4) Bool StackFull(stackSeq *s);    		//	栈是否为满
    (5) int StackLength(stackSeq *s);  			//	返回栈中元素个数——栈长度
    (6) Bool Push(stackSeq *s,ElemType e); 		//	入栈
    (7) void Pop(stackSeq *s,ElemType *e); 		//	出栈
    (8) Bool GetTop(stackSeq *s,ElemType *e); 	//	取栈顶数据元素
    (9) void DispStack(stackSeq *s);  			//	输出栈
}

对比线性表的抽象数据类型可以发现，栈的抽象数据类型少了 返回指定序号的元素 和 返回指定元素的序号 两个方法，并且插入节点和删除节点方法也有位置上的限制，这些在计算上的限制正是栈结构的特点，因此栈也被称为受限的线性表。

顺序栈#

顺序栈的存储结构是利用一组地址连续的存储空间依次存放自栈底到栈顶的数据元素，同时设置栈顶元素的下标 top 指向栈顶元素的位置。

定义顺序栈的存储结构：

1
2
3
4
5
6
7
8
#define MaxSize 50

typedef char ElemType;
typedef struct Node
{
    ElemType data[MaxSize];
    int top;                
} stackSeq;

顺序栈代码实现：

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
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 50
#define true 1
#define false 0

typedef int Bool;
typedef char ElemType;
typedef struct Node
{
    ElemType data[MaxSize];
    int top;                
} stackSeq;                          

//初始化栈
stackSeq * InitStack();    
//销毁栈
void DestroyStack(stackSeq *s);  
//栈是否为空
Bool StackEmpty(stackSeq *s);    
//栈是否为满
Bool StackFull(stackSeq *s);     
//返回栈中元素个数——栈长度
int StackLength(stackSeq *s);  
//入栈
Bool Push(stackSeq *s,ElemType e); 
//出栈
void Pop(stackSeq *s,ElemType *e); 
//取栈顶数据元素
Bool GetTop(stackSeq *s,ElemType *e); 
//输出栈
void DispStack(stackSeq *s);  

int main()
{
    ElemType e;
    stackSeq *s;
    printf("(1)初始化栈s\n");
    s = InitStack();
    printf("(2)栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(3)依次进栈元素a,b,c,d,e\n");
    Push(s,'a');
    Push(s,'b');
    Push(s,'c');
    Push(s,'d');
    Push(s,'e');
    printf("(4)栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(5)栈长度:%d\n",StackLength(s));
    printf("(6)从栈顶到栈底元素:");DispStack(s);
    printf("(7)出栈序列:");
    while (!StackEmpty(s))
    {
        Pop(s,&e);
        printf("%c ",e);
    }
    printf("\n");
    printf("(8)栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(9)释放栈\n");
    DestroyStack(s);
    return 0;
}

stackSeq * InitStack()
{
    stackSeq *tmp = (stackSeq *)malloc(sizeof(stackSeq));
    tmp->top = -1;
    return tmp;
}

Bool StackEmpty(stackSeq *s)
{
    if (s->top == -1)
        return true;
    else
        return false;  
}

Bool StackFull(stackSeq *s)
{
    if (s->top == MaxSize-1)
        return true;
    else
        return false;  
}

Bool Push(stackSeq *s,ElemType e)
{
    //  判断是否满栈
    if(StackFull(s)) return false;
    s->top++;
    s->data[s->top] = e;
    return true;
}

int StackLength(stackSeq *s)
{
    return s->top + 1;
}

void DispStack(stackSeq *s)
{
    int top = s->top;
    while (top > -1)
    {
        printf("%c\t",s->data[top]);
        top--;
    }
    printf("\n");
}

void Pop(stackSeq *s,ElemType *e)
{
    *e = s->data[s->top];
    s->top--;
}

void DestroyStack(stackSeq *s)
{
    free(s);
}

链栈#

链栈的实现与头插法的链表很相似。

链栈的存储结构定义为：

1
2
3
4
5
6
typedef int ElemType;
typedef struct Node
{
    ElemType data;              
    struct Node *next;      
} stackLink;

链栈的存储结构与链表一样，区别在于链表的指针始终指向第一个节点，而链栈的指针始终指向栈顶节点。

链栈的存储结构也可以定义为：

1
2
3
4
5
6
7
8
9
10
11
>typedef int ElemType;
>typedef struct Node
>{
   ElemType data;              
   struct Node *next;      
>} stackNode; 

>typedef struct
>{
   stackNode *top;
>} stackLink;

但是结构体变量 stackLink 只包含一个成员，所以直接把成员定义成变量。

因为 struct Node *next 与 stackNode *top 一样作用，所以直接使用结构体变量 stackNode 初始化链栈。

最后链栈的存储结构定义为：

1
2
3
4
5
6
>typedef int ElemType;
>typedef struct Node
>{
   ElemType data;              
   struct Node *next;      
>} stackLink;

链栈的抽象运算与顺序栈一致，但是由于存储结构不一样，所以具体实现也完全不一样。

链栈代码实现：

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
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

typedef char ElemType;
typedef int Bool;

typedef struct Node
{
    ElemType data;              
    struct Node *next;      
} stackLink;                      

//  初始化栈
stackLink * InitStack();    
//  销毁栈
void DestroyStack(stackLink *s);  
//  栈是否为空
Bool StackEmpty(stackLink *s);    
//  链栈没有栈满的概念
Bool StackFull(stackLink *s);     
//  返回栈中元素个数——栈长度
int StackLength(stackLink *s);  
//  入栈
Bool Push(stackLink *s,ElemType e); 
//  出栈
void Pop(stackLink *s,ElemType *e); 
//  取栈顶数据元素
Bool GetTop(stackLink *s,ElemType *e); 
//  输出栈
void DispStack(stackLink *s);  


int main()
{
    ElemType e;
    stackLink *s;
    printf("(1)初始化链栈s\n");
    s = InitStack();
    printf("(2)链栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(3)依次进链栈元素a,b,c,d,e\n");
    Push(s,'a');
    Push(s,'b');
    Push(s,'c');
    Push(s,'d');
    Push(s,'e');
    printf("(4)链栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(5)链栈长度:%d\n",StackLength(s));
    printf("(6)从链栈顶到链栈底元素:");DispStack(s);
    printf("(7)出链栈序列:");
    while (!StackEmpty(s))
    {   Pop(s,&e);
        printf("%c ",e);
    }
    printf("\n");
    printf("(8)链栈为%s\n",(StackEmpty(s) == 1?"空":"非空"));
    printf("(9)释放链栈\n");
    DestroyStack(s);
    return 0;
}

//初始化栈
stackLink * InitStack()
{
    //栈头节点
    stackLink *tmp = (stackLink *)malloc(sizeof(stackLink));
    tmp->next = NULL;
    return tmp;
}

Bool StackEmpty(stackLink *s)
{
    if(s->next == NULL)
        return true;
    else
        return false; 
}

//  入栈
Bool Push(stackLink *s,ElemType e)
{
    stackLink *tmp = (stackLink *)malloc(sizeof(stackLink));
    tmp->data = e;
    tmp->next = s->next;
    s->next = tmp;
}

void DispStack(stackLink *s)
{
    stackLink *tmp;
    tmp = s->next;
    while(tmp != NULL){
        printf("%c\t",tmp->data);
        tmp = tmp->next;
    }
    printf("\n");
}

int StackLength(stackLink *s)
{
    int n = 0;
    stackLink *tmp;
    tmp = s->next;
    while(tmp != NULL){
        n++;
        tmp = tmp->next;
    } 
    return n;
}

//  出栈
void Pop(stackLink *s,ElemType *e)
{
    stackLink *tmp = s->next;
    *e = tmp->data;
    s->next = tmp->next;
    free(tmp);
}

//  销毁栈
void DestroyStack(stackLink *s)
{
    if(s != NULL) 
    {
        stackLink *tmp = s->next,*q;
        while (tmp != NULL)
        {
            q = tmp;
            tmp = tmp->next;
            free(q);
        }
        free(s);
    }
}

leetcode 128h 最长连续序列

Published on:
Tags: leetcode

题目描述#

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

1
2
3
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

算法#

  1. 对数组进行排序（基数排序算法）
  2. 计算最长连续序列的长度

因为基数排序算法满足时间复杂度O(n)，所以一看到题就有了思路，问题变成了如何使用基数排序。

题目时间上有隐含条件：

1.数组元素可能有负整数

2.可能是空数组

3.可能存储相同的元素

对于第2，只要在开始前做一下判断，即可避免；

对于第3点，则是记得要去重；

第1点比较麻烦，因为基数排序不能处理负数，所以需要把数组分成正整数和负整数。
首先把负整数数组暂时先换成正整数，然后分别对两个数组使用基数排序，返回两个有序的数组。
接着把负整数数组进行倒置，最后把两个数组进行拼接，得到一个有序的数组。

得到一个有序的数组后，接下来的问题就简单了。

C代码#

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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
} RDnode;


void displayPNode(RDnode *p);
RDnode* generalPNode(int* nums, int numsSize);
int longestConsecutive(int* nums, int numsSize);
int getBaseNum(int num,int numSt);
int getMaxNum(int* nums, int numsSize);
void radixSort(RDnode **p,int loop);

int main()
{
    //  考虑空数组，数据元素带有负数，重复元素
    int arr[] = {1,2,0,1};
    int n = 4;
    int res = longestConsecutive(&arr[0],n);
    printf("最长连续序列的长度=%d\n",res);
    return 0;
}

void displayPNode(RDnode *p)
{
    while (p !=NULL)
    {
        printf("data=%d\t",p->data);
        p = p->next;
    }
    printf("\n");
}
//  构造基数排序存储结构
RDnode* generalPNode(int* nums, int numsSize)
{
    int i;
    RDnode *p = NULL,*q = NULL,*tmp;
    for(i=0;i<numsSize;i++)
    {
        tmp = (RDnode *)malloc(sizeof(RDnode));
        tmp->data = nums[i];
        tmp->next = NULL;
        if(q == NULL)
        {
            q = tmp;
            p = q;
        }
        else
        {
            q->next = tmp;
            q = tmp;
        }
    }
    return p;
}

//  基数排序
void radixSort(RDnode **p,int loop)
{   
    RDnode *head[10],*tail[10],*tmp;
    int i,j,k;
    for(i=0;i<loop;i++)
    {
        for(j=0;j<10;j++)
            head[j] = tail[j] = NULL;

        while ((*p) != NULL)
        {
            k = getBaseNum((*p)->data,i+1);
            if(head[k] == NULL)
            {
                head[k] = (*p);
                tail[k] = (*p);
            }
            else
            {
                tail[k]->next = (*p);
                tail[k] = (*p);
            }
            (*p) = (*p)->next;
        }

        (*p) = NULL;
        for ( j = 0; j < 10; j++)
        {
            if(head[j] != NULL)
            {
                if((*p) == NULL)
                {
                    (*p) = head[j];
                    tmp = tail[j];
                }
                else
                {
                    tmp->next = head[j];
                    tmp = tail[j];
                } 
            }
        }
        tmp->next = NULL;
    }
}
//  求整数某一位数字
int getBaseNum(int num,int numSt)
{
    int numTimes = 1;
    int i,baseNum;
    for(i=1;i<numSt;i++)
    {
        numTimes *= 10;
    }
    baseNum = num/numTimes%10;
    return baseNum;
}
//  求数组最大绝对值，
int getMaxNum(int* nums, int numsSize)
{
    int i;
    int max = 0;
    for(i=0;i<numsSize;i++)
        if(max < abs(nums[i])) max = abs(nums[i]);
    return max;
}
//  求整数的位数
int	GetMaxLoop(int num)
{
	int bits = 1;
	num /= 10;
	while (num != 0)
	{
		++bits;
		num /= 10;
	}
	return bits;
}

int longestConsecutive(int* nums, int numsSize)
{
    if(numsSize < 2) return numsSize;
    int positiveArr[numsSize],positiveNum=0,nagetiveArr[numsSize],nagetiveNum=0;
    RDnode *nagetiveP=NULL,*positiveP=NULL;
    int longest = 1, tmp_longest = 1;
    int result[numsSize],i=0;

    int max = getMaxNum(&nums[0],numsSize);
    int	loop = GetMaxLoop(max);

    //  按正负数存储数据
    for(int i=0;i<numsSize;i++)
    {
        if (nums[i] < 0)
            nagetiveArr[nagetiveNum++] = abs(nums[i]);
        else
            positiveArr[positiveNum++] = nums[i];
    }

    //  构造基数排序结构，基数排序
    if(nagetiveNum>0) 
    {
        nagetiveP = generalPNode(&nagetiveArr[0],nagetiveNum);
        radixSort(&nagetiveP,loop);
    }
    if(positiveNum>0) 
    {
        positiveP = generalPNode(&positiveArr[0],positiveNum);
        radixSort(&positiveP,loop);
    }

    //  处理有负数的情况
    if(nagetiveNum > 0)
    {
        int temp;
        while(nagetiveP != NULL)
        {
            result[i++] = nagetiveP->data*-1;
            nagetiveP = nagetiveP->next;
        }
        for(int i=0;i<nagetiveNum/2;i++)
        {
            temp = result[i];
            result[i] = result[nagetiveNum-1-i];
            result[nagetiveNum-1-i] = temp;
        }
    }
    while(positiveP != NULL)
    {
        result[i++] = positiveP->data;
        positiveP = positiveP->next;
    }


    for (int i = 1; i < numsSize; i++)
    {
        if(result[i-1]+1 == result[i])
            tmp_longest++;
        else if(result[i-1] == result[i])
        {
            continue;   //去重
        }
        else        
        {
            longest = tmp_longest>longest?tmp_longest:longest;
            tmp_longest = 1;
        }
    }
    longest = tmp_longest>longest?tmp_longest:longest;
    return longest;
}

时间复杂度#

序号 函数 时间复杂度
1 getMaxNum O(n)
2 GetMaxLoop O(loop)
3 generalPNode O(n)
4 radixSort O(loop*(20+n))
5 结构语句 O(n)+O(n)

因此算法的时间复杂度为O(loop*(20+n)) = O(n)。

loop表示元素的最大位数，也是循环的最大趟数

线性表——顺序表、链表

Published on:
Tags: 数据结构 线性表

线性表的定义和属性#

定义：线性表是具有相同特性的数据元素的一个有序序列。按存储结构的不同，可分为顺序表和链表。

使用逻辑结构二元组表示：

B=(D,R)

D={di∣di∈ElemType,1<=i<=n,n>=0}

R={<rj−1,rj>∣1<=j<=m,m>=0}

线性表的几个属性：

  • 空表：当$n=0$时，表示线性表是一个空表，即表中不包含任何元素
  • 前驱：$a_{i-1}$是$a_i$的前驱，$2 <= i <= n$
  • 后继：$a_{i+1}$是$a_i$的后继，$1 <= i <= n - 1$
  • 表头元素：表中第一个元素$a_1$
  • 表尾元素：最后一个元素$a_n$

线性表的抽象数据类型#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ADT List
{
数据对象：
    D = {ai | ai ∈ ElemType, i=1,2,…,n, n>=0 }              // ElemType为类型标识符
数据关系：
    R = {<ai-1, ai> | ai-1, ai ∈ D, i=2,3,…,n }
数据操作：
    (1) tabSeq * InitList();	                            // 初始化一个空的线性表
    (2) void CreateList(tabSeq *L, ElemType a[], int n);	// 创建线性表
    (3) Bool ListEmpty(tabSeq *L);	                        // 判断线性表是否为空
    (4) int ListLength(tabSeq *L);	                        // 返回线性表的长度
    (5) void DispList(tabSeq *L);	                        // 输出线性表元素
    (6) Bool GetElem(tabSeq *L,int i,ElemType *e);	        // 返回指定序号的元素
    (7) int LocateElem(tabSeq *L, ElemType e);	            // 返回指定元素的序号
    (8) Bool ListInsert(tabSeq *L,int i,ElemType e);	    // 在指定序号位置插入元素
    (9) Bool ListDelete(tabSeq *L,int i,ElemType *e);	    // 在指定序号位置删除元素
    (10) void DestroyList(tabSeq *L);                       //  销毁线性表
}

线性表提供丰富的运算，来操作线性表上的元素节点。

顺序表#

线性表是基于逻辑结构的，而顺序表是基于存储结构的。

顺序表的存储结构是指把顺序表中的所有元素存储到一块连续的存储空间，我们可以认为是一个数组。于是顺序表的存储结构定义为：

1
2
3
4
5
6
7
#define MaxSize 50
typedef int ElemType;
typedef struct
{
    ElemType data[MaxSize];
    int length;
} tabSeq;

把顺序表中的元素依次存储到数据data，并且更新长度length。接下来具体实现抽象数据类型里定义的抽象方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//  初始化一个空的线性表
tabSeq * InitList();
// 创建线性表
void CreateList(tabSeq *L, ElemType a[], int n);
// 判断线性表是否为空
Bool ListEmpty(tabSeq *L);
// 返回线性表的长度
int ListLength(tabSeq *L);
// 输出线性表元素
void DispList(tabSeq *L);
//  返回指定序号的元素
Bool GetElem(tabSeq *L,int i,ElemType *e);
//  返回指定元素的序号
int LocateElem(tabSeq *L, ElemType e);
//  在指定序号位置插入元素
Bool ListInsert(tabSeq *L,int i,ElemType e);
//  在指定序号位置删除元素
Bool ListDelete(tabSeq *L,int i,ElemType *e);
//  销毁线性表
void DestroyList(tabSeq *L);

顺序表代码实现：

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
#include <stdio.h>
#include <stdlib.h>

#define MaxSize 150
#define true 1
#define false 0

typedef int ElemType;
typedef int Bool;

typedef struct
{
    ElemType data[MaxSize];
    int length;
} tabSeq;


//  初始化一个空的线性表
tabSeq * InitList();
// 创建线性表
void CreateList(tabSeq *L, ElemType a[], int n);
// 判断线性表是否为空
Bool ListEmpty(tabSeq *L);
// 返回线性表的长度
int ListLength(tabSeq *L);
// 输出线性表元素
void DispList(tabSeq *L);
//  返回指定序号的元素
Bool GetElem(tabSeq *L,int i,ElemType *e);
//  返回指定元素的序号
int LocateElem(tabSeq *L, ElemType e);
//  在指定序号位置插入元素
Bool ListInsert(tabSeq *L,int i,ElemType e);
//  在指定序号位置删除元素
Bool ListDelete(tabSeq *L,int i,ElemType *e);
//  销毁线性表
void DestroyList(tabSeq *L);

int main()
{
    tabSeq *T;
    T = InitList();
    ElemType x[6] = {1,2,3,4,5,6};
    if (ListEmpty(T)) printf("null\n");
    else printf("not null\n");
    CreateList(T,x,6);
    printf("CreateList\n");
    if (ListEmpty(T)) printf("null\n");
    else printf("not null\n");
    printf("length of list=%d\n",ListLength(T));
    DispList(T);
    int num;
    if(GetElem(T,3,&num)) printf("num = %d\n",num);
    else printf("false\n");
    printf("index of 6  = %d\n",LocateElem(T,6));
    ListInsert(T,1,0);
    DispList(T);
    if(ListDelete(T,1,&num)) printf("num = %d\n",num);
    else printf("false\n");
    DispList(T);
    DestroyList(T);
    return 0;
}

Bool ListDelete(tabSeq *L,int i,ElemType *e)
{
    i--;
    if (i<0 || i>L->length-1) return false;
    *e = L->data[i];
    for(int j=i;j<L->length;j++)
        L->data[j] = L->data[j+1];

    L->length--;
    return true;
}

Bool ListInsert(tabSeq *L,int i,ElemType e)
{
    i--;
    if (i<0 || i>L->length) return false;
    for(int j=L->length;j>i;j--)
        L->data[j] = L->data[j-1];

    L->data[i] = e;
    L->length++;
    return true;
}

int LocateElem(tabSeq *L, ElemType e)
{
    if (ListEmpty(L)) return -1;
    for(int i=0;i<L->length;i++)
        if(L->data[i] == e) return i+1;

    return -1;
}

Bool GetElem(tabSeq *L,int i,ElemType *e)
{
    i--;
    if (i<0 || i>L->length-1) return false;
    *e = L->data[i];
    return true;
}

void DispList(tabSeq *L)
{
    printf("output elem: ");
    for(int i=0;i<L->length;i++)
        printf("%d\t",L->data[i]);

    printf("\n");
}

int ListLength(tabSeq *L)
{
    return L->length;
}

Bool ListEmpty(tabSeq *L)
{
    return L->length>0?false:true;
}

void CreateList(tabSeq *L, ElemType a[], int n)
{
    for(int i=0;i<n;i++)
        L->data[i] = a[i];
    
    L->length = n;
}

tabSeq* InitList()
{
    tabSeq *tmp = (tabSeq *)malloc(sizeof(tabSeq));
    tmp->length = 0;
    return tmp;
}

void DestroyList(tabSeq *L)
{
    free(L);
}

链表#

线性表的顺序存储结构使用数组实现，优点是空间利用率高，缺点是当对数据进行增删时，需要移动数据元素的位置，这个过程是很耗时的；而链式存储结构正好与其相反。

线性表链式存储结构，即是链表。使用指针实现，指针指向节点，每个节点包含数据域和指针域。数据域保存数据元素，指针域保存下个节点的地址由此构成链表。链表虽然空间利用率不高，但是对节点的增删调整比较方便。

链表的存储结构定义为：

1
2
3
4
5
6
typedef int ElemType;
typedef struct Node
{
    ElemType data;
    struct Node *next;
} tabLink;

链表实际上包含了两部分，分别是：数据节点组成的数据链表和一个指向数据节点的指针。
数据节点保存数据和后继节点的地址，指针默认指向第一个数据节点，主要作用是遍历数据链表。

初始化链表的时，返回一个指向数据节点的指针，并且默认数据链表为NULL

1
2
3
4
5
6
tabLink* InitList()
{
    tabLink *tmp = (tabLink *)malloc(sizeof(tabLink));
    tmp->next = NULL;
    return tmp;
}

数据链表有两种创建方法：头插法和尾插法。

想象你面前有一条数据链表，左边为头，右边为尾。指针指向头节点。

头插法即是每次新增元素，都放到最左边，具体做法是把头节点的地址保存到新增节点的指针域，把新增节点的地址保存到链表指针的指针域，此时新增节点就变成了头节点。

尾插法即是每次新增元素，都放到最右边，具体做法是使用链表指针遍历到最后一个节点，然后把新增节点的地址保存到最后一个节点的指针域，此时新增节点变成了最后一个节点。

链表的抽象运算与顺序表一致，但是由于存储结构不一样，所以具体实现也完全不一样。

链表代码实现：

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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0

typedef int ElemType;
typedef int Bool;

typedef struct Node
{
    ElemType data;
    struct Node *next;
} tabLink;


//  初始化一个空的链表
tabLink * InitList();
//  创建链表-头插法
void CreateListL(tabLink *L, ElemType a[], int n);
//  创建链表-尾插法
void CreateListR(tabLink *L, ElemType a[], int n);
// 判断链表是否为空
Bool ListEmpty(tabLink *L);
// 返回链表的长度
int ListLength(tabLink *L);
// 输出链表元素
void DispList(tabLink *L);
//  返回指定序号的元素
Bool GetElem(tabLink *L,int i,ElemType *e);
//  返回指定元素的序号
int LocateElem(tabLink *L, ElemType e);
//  在指定序号位置插入元素
Bool ListInsert(tabLink *L,int i,ElemType e);
//  在指定序号位置删除元素
Bool ListDelete(tabLink *L,int i,ElemType *e);
//  销毁线性表
void DestroyList(tabLink *L);

int main()
{
    tabLink *T;
    T = InitList();
    ElemType x[6] = {1,2,3,4,5,6};
    if (ListEmpty(T)) printf("null\n");
    else printf("not null\n");
    CreateListR(T,x,6);
    printf("CreateListR\n");
    if (ListEmpty(T)) printf("null\n");
    else printf("not null\n");
    printf("length of list=%d\n",ListLength(T));
    DispList(T);
    int num;
    if(GetElem(T,3,&num)) printf("num = %d\n",num);
    else printf("false\n");
    printf("index of 6  = %d\n",LocateElem(T,6));
    ListInsert(T,1,0);
    DispList(T);
    if(ListDelete(T,1,&num)) printf("num = %d\n",num);
    else printf("false\n");
    DispList(T);
    DestroyList(T);
    return 0;
}

Bool ListDelete(tabLink *L,int i,ElemType *e)
{
    int length = ListLength(L);
    if (i<1 || i>length) return false;
    int j = 0;
    while(j < i-1)
    {
        L = L->next;
        j++;
    }
    tabLink *tmp = L->next;
    L->next = tmp->next;
    *e = tmp->data;
    free(tmp);
    return true;
}

//  在第i个位置，插入节点e
//  关键在于找到第i-1个位置
Bool ListInsert(tabLink *L,int i,ElemType e)
{
    int length = ListLength(L);
    if (i<1 || i>length+1) return false;
    int j = 0;
    while (j < i-1)
    {
        L = L->next;
        j++;
    }
    
    tabLink *tmp = (tabLink *)malloc(sizeof(tabLink));
    tmp->data = e;
    tmp->next = L->next;
    L->next = tmp;
    return true;
}

int LocateElem(tabLink *L, ElemType e)
{
    if (ListEmpty(L)) return -1;
    tabLink *P = L->next;
    int i = 1;
    while(P != NULL)
    {
        if(P->data == e) return i;
        P = P->next;
        i++;
    }
    return -1;
}

Bool GetElem(tabLink *L,int i,ElemType *e)
{
    int length = ListLength(L);
    if (i<1 || i>length) return false;
    int j=0;
    while(j < i)
    {
        L = L->next;
        j++;
    }
    *e = L->data;
    return true;
}

void DispList(tabLink *L)
{
    printf("output elem: ");
    tabLink *P;
    P = L->next;
    while(P != NULL)
    {
        printf("%d\t",P->data);
        P = P->next;
    }
    printf("\n");
}

int ListLength(tabLink *L)
{
    if(ListEmpty(L)) return 0;
    int i = 0;
    while(L->next != NULL)
    {
        i++;
        L = L->next;
    }
    return i;
}

Bool ListEmpty(tabLink *L)
{
    return L->next==NULL?true:false;
}

//  头插法
//  左为头，右为尾
void CreateListL(tabLink *L, ElemType a[], int n)
{
    tabLink *tmp;
    for(int i=0;i<n;i++)
    {
        tmp = (tabLink *)malloc(sizeof(tabLink));
        tmp->data = a[i];
        tmp->next = L->next;
        L->next = tmp;
    }
}

//  尾插法
//  左为头，右为尾
void CreateListR(tabLink *L, ElemType a[], int n)
{
    tabLink *tmp,*p;
    p = L;
    //  p指向链表的尾指针
    while(p->next != NULL) p = p->next;
    for(int i=0;i<n;i++)
    {
        tmp = (tabLink *)malloc(sizeof(tabLink));
        tmp->data = a[i];
        tmp->next = NULL;
        p->next = tmp;
        p = tmp;
    }
}

//  初始化链表
//  头节点不存储数据元素，指针域指向第一个节点
tabLink* InitList()
{
    tabLink *tmp = (tabLink *)malloc(sizeof(tabLink));
    tmp->next = NULL;
    return tmp;
}

void DestroyList(tabLink *L)
{
    tabLink *P;
    while(L->next != NULL)
    {
        P = L;
        L = L->next;
        free(P);
    }
    free(L);
}

数据结构三要素

Published on:
Tags: 数据结构

数据结构三要素#

包括：

  • 数据的逻辑结构
  • 数据的存储结构
  • 数据的运算

数据的逻辑结构#

指数据节点之间的逻辑关系，是数据在用户面前呈现的形式。

数据节点之间按逻辑结构可分为：

线性结构的特点：

  • 数据节点之间只存在一对一的关系
  • 开始节点和终端节点都是唯一的
  • 除了开始节点和终端节点以外，其余节点都有且仅有一个前驱节点，有且仅有一个后继节点

树形结构的特点：

  • 数据节点之间存在一对多的关系
  • 开始节点唯一，终端节点不唯一
  • 除了终端节点以外，每个节点有一个或多个后继节点
  • 除开始节点以外，每个节点有且仅有一个前驱节点

图形结构的特点：

  • 数据节点之间存在多对多的关系
  • 没有开始节点和终端节点，所有节点都可能有多个前驱节点和多个后继节点

数据的存储结构#

指数据节点及其关系在计算机存储器中的存储方式，也称为数据的物理结构。

数据节点按存储结构可分为：

  • 顺序结构：利用数组实现，空间利用率高
  • 链式结构：利用指针实现，便于增删调整修改
  • 索引结构：利用索引项实现，索引项包括关键字和地址，查找速度快，但是存储索引项会增加空间支出
  • 散列结构：利用哈希公式等计算并存储数值为地址，作为快速查找的依据，但是缺点是存储数值会占用大量空间，并且仅保存数据数值，不保存数据的逻辑关系

数据的运算#

施加在数据上的运算包括运算的定义和实现。

  • 运算的定义针对逻辑结构，指出运算的功能；

  • 运算的实现针对存储结构，指出运算的具体操作步骤。

数据结构
数据结构

逻辑结构二元组#

逻辑结构二元组是是表示数据逻辑结构的抽象工具。

逻辑结构二元组只关心两个问题：

  1. 数据是什么，包括：
    • 数据是什么类型，例如int、char、struct
    • 数据的数量
  2. 数据之间是什么关系
    • 数据之间是相邻关系，使用括号(e1,e2)表示
    • 数据之间是先后关系，使用尖括号<e1,e2>表示

逻辑结构二元组表示方法：
$B=(D,R)$。

  1. B是一种数据结构，由数据元素的集合D和D上二元关系的集合R所组成
  2. $D={d_i|d_i \in ElemType,1<=i<=n,n>=0}$，
    数据元素的集合
  3. $R={<r_{j-1},r_j>|1<=j<=m,m>=0}$，
    D上二元关系的集合

比如二元组示例：

1
2
3
4
B = （D，R）
D = {a，b，c，d，e，f，g，h，i，j}
R = {r}
r = { <a，b>，<a，c>，<a，d>，<b，e>，<c，f>，<c，g>，<d，h>，<d，i>，<d，j> }

从它的二元关系的序偶 <a,b> 中可以看出这是一个有向关系，那么其二元组关系对应的逻辑结构如下图所示：

数据结构二元组示例
数据结构二元组示例

抽象数据类型(ADT)#

抽象数据类型只关心数据节点的逻辑结构和抽象运算（即运算的定义），暂不考虑计算机的具体存储结构和运算的具体实现。实质上就是在用抽象的方法描述问题本身，目的是在不涉及具体的，和计算机系统相关的细节情况下，优先理解问题本身，在此基础上，实现用计算机求解问题的过程。

1
2
3
4
5
6
ADT <抽象数据类型>
{
    数据对象：<数据对象的定义>
    数据关系：<数据关系定义>
    基本操作：<基本操作定义>
}

对数据对象的定义和描述数据元素之间的关系，这个就是逻辑结构二元组的内容，所以，抽象数据类型就是逻辑结构二元组的扩展，在逻辑结构二元组的基础上增加对数据元素的基本运算定义。

线性表的抽象数据类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ADT List
{
数据对象：
    D = {ai | ai ∈ ElemType, i=1,2,…,n, n>=0 }              // ElemType为类型标识符int的别名
数据关系：
    R = {<ai-1, ai> | ai-1, ai ∈ D, i=2,3,…,n }
数据操作：
    （1）tabSeq * InitList();	                            // 初始化一个空的线性表，tabSeq为结构体类型
    （2）void CreateList(tabSeq *L, ElemType a[], int n);	// 创建线性表
    （3）Bool ListEmpty(tabSeq *L);	                        // 判断线性表是否为空
    （4）int ListLength(tabSeq *L);	                        // 返回线性表的长度
    （5）void DispList(tabSeq *L);	                        // 输出线性表元素
    （6）Bool GetElem(tabSeq *L,int i,ElemType *e);	        // 返回指定序号的元素
    （7）int LocateElem(tabSeq *L, ElemType e);	            // 返回指定元素的序号
    （8）Bool ListInsert(tabSeq *L,int i,ElemType e);	    // 在指定序号位置插入元素
    （9）Bool ListDelete(tabSeq *L,int i,ElemType *e);	    // 在指定序号位置删除元素
}

根据抽象数据类型的定义可以知道：

  • 数据元素集合D包含n个int类型整数；
  • R表示数据元素之间是有向的，具有前驱后继关系；
  • 最后定义了9个基本运算，涵盖初始化，创建，判断是否为空……等等。

ADT可以帮助理解问题本身，理解对外暴露的接口，在次基础上，根据实际需求，选择合适的存储结构，实现具体运算。

leetcode 1431e 拥有最多糖果的孩子

Published on:
Tags: leetcode

题目描述#

给你一个数组 candies 和一个整数 extraCandies ，其中 candies[i] 代表第 i 个孩子拥有的糖果数目。

对每一个孩子，检查是否存在一种方案，将额外的 extraCandies 个糖果分配给孩子们之后，此孩子有 最多 的糖果。注意，允许有多个孩子同时拥有 最多 的糖果数目。

示例：

1
2
3
4
5
6
7
8
输入：candies = [2,3,5,1,3], extraCandies = 3
输出：[true,true,true,false,true] 
解释：
孩子 1 有 2 个糖果，如果他得到所有额外的糖果（3个），那么他总共有 5 个糖果，他将成为拥有最多糖果的孩子。
孩子 2 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。
孩子 3 有 5 个糖果，他已经是拥有最多糖果的孩子。
孩子 4 有 1 个糖果，即使他得到所有额外的糖果，他也只有 4 个糖果，无法成为拥有糖果最多的孩子。
孩子 5 有 3 个糖果，如果他得到至少 2 个额外糖果，那么他将成为拥有最多糖果的孩子。

提示：

  • 2 <= candies.length <= 100
  • 1 <= candies[i] <= 100
  • 1 <= extraCandies <= 50

即是：

  • 2 <= 孩子的数量 <= 100
  • 1 <= 孩子的糖果数量 <= 100
  • 1 <= 额外的糖果数量 <= 50

算法#

  1. 遍历每个小孩子的糖果数量，找到糖果数量最大值 maximum
  2. 把额外的糖果数量只分给一个小孩，找到此时糖果总数量 大于等于 糖果数量最大值 的小孩

C代码#

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
#include <stdio.h>
#include <stdlib.h>

#define true 1
#define false 0
typedef int bool;

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
bool* kidsWithCandies(int* candies, int candiesSize, int extraCandies, int* returnSize)
{
    int i;
    int maximum = 0;
    bool *output = (bool *)malloc(sizeof(bool) * candiesSize);

    // 遍历每个小孩子的糖果数量，找到糖果数量最大值 maximum
    for(i=0;i<candiesSize;i++)
    {
        if(candies[i] > maximum) maximum = candies[i];
    }

    //  把额外的糖果数量 extraCandies 只分给一个小孩，
    //  找到此时糖果总数量 大于等于 糖果数量最大值 的小孩，标记true，其余标记false
    for(i=0;i<candiesSize;i++)
    {
        if (candies[i] + extraCandies >= maximum)
            output[i] = true;
        else
            output[i] = false;
    }

    *returnSize = candiesSize;
    return output;    
}



int main()
{
    int candies[] = {1,2,3,4,5,6,7,8};
    int candiesSize = 8;
    int extraCandies = 2;
    int *returnSize;
    bool *result;
    result = kidsWithCandies(&candies[0],candiesSize,extraCandies,returnSize);
    printf("[");
    for(int i=0;i<*returnSize;i++)
    {
        if(result[i] == 1)
            printf("true");
        else
            printf("false");
        
        if(i < (*returnSize-1)) printf(",");
    }
    printf("]");
    free(result);
}

时间复杂度#

第一次for循环，时间复杂度为O(n)；

第二次for循环，时间复杂度也为O(n)。

因此算法的时间复杂度为O(n)。

算法的时间复杂度

Published on:
Tags: 算法
算法复杂度#

算法复杂度是评价一个算法是否高效的依据。

算法复杂度分为时间复杂度和空间复杂度，一个高效的算法具有用时短或者使用空间少的特点。

随着存储技术的发展，存储介质的容量也发生了翻天覆地的变化，更有出现一些以空间换时间的算法。因此，如今评价算法的效率更加关注“用时短”方面，即是时间复杂度。

时间复杂度#

简单的来说，算法的时间复杂度表示程序运行直至完成所需的总时间。

因为程序可以由不同的程序语言实现，可以在配置不同的机器上面运行，那么不同的程序语言和不同的配置机器之间就没有可比性。因此不能用程序执行的具体时间比较效率，而是要用基本运算的次数来度量算法的时间复杂度。

一个算法是由控制结构（顺序、分支和循环）和原操作（比如有四则运算，比较运算，赋值运算等）构成的，算法时间复杂度取决于两者的基本运算次数之和。进行基本运算的次数越少，其运行时间也就相对越少；基本运算次数越多，其运行时间也就相对越多。

时间复杂度的表示方法#

求解1~1000的累加和：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>

int main()
{
    int n = 1000;
    int sum = 0;
    for(int i=1;i<=n;i++)
    {
        sum += i;
    }
    printf("sum=%d\t",sum);
    return 0;
}

我们已经知道，算法的时间复杂度取决于算法的基本运算的次数。

以上程序的基本运算次数：$T_n = 3n+3$

算法的时间复杂度通常使用“大O表示法”（ big O notation）表示，大O符号的作用在于用简单的函数来描述复杂函数行为，给出一个上或下界。

算法中基本运算次数 $T_n$ 是问题规模 $n$ 的某个函数 $f_n$，记作：$T_n = O(f_n)$。

表示 $T_n$ 与 $f_n$ 是同量级函数，具有相同的增长率；
表示当 $n$ 趋于正无穷时，存在一个常数 $C$ ，总有 $T_n <= C * f_n$ ，
简单的来说，当 $n$ 趋于正无穷时，$T_n = f_n$。

计算时间复杂度#

由 $T_n = 3n + 3$ 可得，
时间复杂度 $O(f_n)=O(3n+3)=O(n)$ 。

计算时间复杂度的步骤：

  • 求出问题规模n的基本运算次数函数 $T(n)$
  • 只保留函数 $T(n)$ 的最高阶项
  • 忽略最高阶项的常数

例如：

$T_n=n^2+3n+4=O(n^2+3n+4)=O(n^2)$

$T_n=4n^2+2n+1=O(4n^2+2n+1)=O(n^2)$

常见的算法时间复杂及其大小#
时间复杂度 时间复杂度量级 大小（由小到大）
$O(1)$ 常数阶 1
$O(\log_2n)$ 对数阶 2
$O(n)$ 线性阶 3
$O(nlogn)$ 线性对数阶 4
$O(n^2)$ 平方阶 5
$O(n^3)$ 立方阶 6
$O(2^n)$ 指数阶 7

股票APP里的术语

Published on:
Tags: 股票
今开#

今日开盘价

昨收#

昨日收盘价

今开和昨收都是以集合竞价的方式产生

集合竞价#

在一段时间内（开盘前9:15～9:30，收盘前14:57～15:00）先不交易，大家集中报价，想报多少报多少，然后取能够使整个市场成交最多的价格作为交易价格，这个就是A股的开盘价和收盘价价格的由来。

最高#

当日交易股票的最高价格

最低#

当日交易股票的最低价格

成交量#

当日有效成交的股票总股数，上图里的成交量单位是手，所以总股数应该乘以100

成交额#

当日有效成交的总金额

均价#

当日（或者当时）交易股票的平均价格

当时累计的成交额 ÷ 当时累计的成交量 = 当时的均价

流通股本#

公司已发行股本中在外流通没有被公司收回的部分。是指可以在二级市场流通的股份。

总股本#

总股本包含流通股和限售股。

限售股一般是大股东持有的，或者后来增发的，在限售期限内，不可以拿到二级市场买卖。

当没有限售股时，流通股本 = 总股本。

流通市值#

流通市值对应流通股本。

流通市值 = 流通股本 × 股价

总市值#

总市值对应总股本。

总市值 = 总股本 × 股价

换手（率）#

换手率 = 当日（或者当时）累计的成交量 ÷ 流通股本 × 100%

涨停#

涨停 = 昨收 × （1 + 10%）

跌停#

涨停 = 昨收 × （1 - 10%）

为了减少股市交易的投机行为，证监会规定每个股票每个交易日的最大涨跌幅度为±10%，对特别处理的ST股票规定每个交易日的最大涨幅度为±5%。

振幅#

股票开盘后的当日最高价和最低价之间的差和前日收盘价的比值。

振幅 = （最高价 - 最低价） ÷ 昨收

如果一只股票的振幅较小，说明该股不够活跃，反之则说明该股比较活跃。

委差#

当前5个价位买入挂单与卖出挂单的差值，反映的是买卖双方的力量对比。

委差 = 当前5个价位买入挂单总和 — 当前5个价位卖出挂单总和

委比#

委比 = 委差 ÷ (当前委托买量总和 + 当前委托卖量总和) × 100%

委比反应的是实际操盘中买卖盘相对强度的指标，委比的取值范围为 [-100%,+100%]。

委比等于-100%，表示当前只有委托卖盘，没有委托买盘，最后可能会跌停；

委比等于100%，表示当前只有委托买盘，没有委托卖盘，最后可能会涨停；

委比值大于0（即委差大于0，买盘量大于卖盘量），表示委托买盘量 大于 委托卖盘量，股价上升；

委比值小于0（即委差小于0，卖盘量大于买盘量），表示委托卖盘量 大于 委托买盘量，股价下升；

例如：当前股价为9.38元，在9.33～9.37元(5个价位)共计买入挂单4000手，9.38～9.42(5个价位)共计6000手卖出挂单，则：

委差 = 买入挂单总和 - 卖出挂单总和 = 4000手 - 6000手 = -2000手

委比 = 委差 ÷ （买入挂单总和 + 卖出挂单总和） × 100% = -2000手 ÷ （ 4000手 + 6000手） × 100% = -20%。

量比#

量比是衡量相对成交量的指标。

它是开市后每分钟的平均成交量与过去5个交易日每分钟平均成交量之比。

量比 ＝ [现成交总手 ÷ 当日累计开市时间(分)] ÷ 过去5个交易日平均每分钟成交量 × 100%

净资产与每股净资产#

公司的净资产包括资产和负债，也叫股东权益。

每股净资产 = 净资产 ÷ 总股本。

市净率（Price-to-Book Ratio）#

市净率 = 股价 ÷ 每股净资产

一般来说市净率较低的股票，投资价值较高，相反，则投资价值较低；

收益#

收益即是每股收益。

每股收益 = 公司净利润 ÷ 公司股份数。

所以公司净利润越高，股数越少，每股收益就越大。

市盈率（PE ratio）#

市盈率分 动态市盈率 和 静态市盈率。都是以当前股票价格除以 已知的最近公开的每股收益后的比值。

静态市盈率 = 股价 ÷ 上一年每股收益

动态市盈率 = 股价 ÷ (最近一季度的每股收益 × 4)

如上图：

恒顺醋业2019年每股收益0.4142元，2020年第一季度每股收益0.0969元

静态市盈率 = 23.24 ÷ 0.4142 = 56.11

动态 = 23.24 ÷ (0.0969 × 4) = 23.24 ÷ 0.3876 = 59.96

市盈率是个性价比指标，表示获取企业的每一元利润，所需支付的价格，市盈率使不同规模不同盈利水平的股票，存在了一定可比性。市盈率还使得股票可以与其他不同类别的资产相比较。

内盘#

内盘常用S表示。

在成交量中以主动性叫卖价格成交的数量

外盘#

外盘用B表示。

在成交量中以主动性叫买价格成交的数量

内盘 + 外盘 = 成交量

净利润#

净利润 = 每股收益 × 总股本

净资产收益率（Rate of Return on Common Stockholders’ Equity ）#

净资产收益率 = 净利润 ÷ 净资产 × 100%

净资产收益率是衡量股东资金使用效率的重要指标，可以反映公司运用自有资产的效率，指标数据越高，说明投资该股票的收益越高。

CDN

Published on:
Tags: cdn

CDN是什么#

CDN的是Content Delivery Network的简称，即内容分发网络。CDN的本质就是缓存。

CDN的作用#

提高访问效率#

通过在现有的网络中增加一层新的网络架构，将网站的内容发布到最接近用户的网络“边缘”，使用户可以就近取得所需的内容，提高用户访问网站的响应速度，提高访问效率；提高访问效率还体现在解决了跨运营商带来的耗时问题。

减轻源服务器负载#

用户可以就近取得内容，不仅可以提高访问效率，还可以减轻源服务器负载，因为请求被转发到了CDN节点，所以源服务器的负载自然得到减轻。

隐藏源服务器IP#

通过设置反向代理，隐藏源服务器IP。

访问原理#

1.当用户向某个URL发起请求时，经过本地DNS系统解析，返回CDN节点信息。如果本地DNS无缓存CDN节点信息，则本地DNS系统会将域名的解析权交给CNAME指向的CDN智能DNS负载均衡系统。

2.CDN智能DNS负载均衡系统根据用户的IP，URL中携带的内容名称，还有服务器的负载能力等因素，综合分析后，向用户返回响应速度最快的节点IP。

3.用户向指定缓存服务器发起请求，缓存服务器响应用户请求，将用户所需内容传送到用户终端。如果缓存服务器上没有用户想要的内容，那么这台服务器就要向它的上一级缓存服务器请求内容，直至追溯到网站的源服务器将内容拉到本地。

CDN访问过程
CDN访问过程

使用Cloudflare的免费CDN

Published on:
Tags: cdn cloudflare

Cloudflare是一家以向客户提供基于反向代理的内容分发网络（Content Delivery Network, CDN）及分布式域名解析服务（Distributed Domain Name Server）为主要业务的美国IT企业。

在 Cloudflare 注册一个账号，通过简单几步设置，就可以免费使用CDN了。

添加站点#

到域名的 控制面板 页面的右上角，点击添加站点，输入域名。

截图使用163.com域名
截图使用163.com域名

选择免费计划#

免费计划
免费计划

同步DNS记录#

自动扫描域名的DNS记录
自动扫描域名的DNS记录

显示同步过来的DNS记录
显示同步过来的DNS记录

此处同步过来的DNS记录为已经在域名提供商后台的设置信息，如果没有的话，可以在这里添加DNS记录。添加完成点击下一步。

更改名称服务器#

Cloudflare名称服务器
Cloudflare名称服务器

到域名提供商的后台（比如阿里云）更改名称服务器，更改名称服务器需要一定时间才能完成，通过dig命令查看更改结果。 更改名称服务器
更改名称服务器

使用dig命令检验#

1
dig ns domain
dig命令结果
dig命令结果

ANSWER SECTION 结果显示，域名有两条名称服务器记录，分别对应上面的名称服务器1 和 名称服务器2，说明名称服务器已经更改生效。

从Cloudflare删除站点#

最后如果不想使用Cloudflare了，到域名的 控制面板 页面，右下角的 高级操作 ，选择 从Cloudflare中删除站点。

删除站点
删除站点

使用SMTP协议和POP3协议手动收发邮件

Published on:
Tags: email 协议

通过上一篇博文理解电子邮件的收发过程我们知道，SMTP服务器是遵循SMTP协议的发送邮件服务器，用来发送邮件的。POP3服务器是遵循POP3协议的服务器，用来接收电子邮件的。接下来就开始体验，通过终端窗口，使用SMTP协议和POP3协议来收发邮件。

使用SMTP协议发送邮件#

邮件客户端与SMPT服务器通过指令连接，并且使用一问一答的方式来发送消息。

连接#

使用telnet命令与163邮箱的SMTP服务器建立连接，25表示端口号 

1
telnet smtp.163.com 25
认证#

1.告诉SMTP服务器发送者的域名 

1
ehlo 163.com

2.选择登录认证方式，一般选择的是login

1
auth login

3.接着输入经过base64加密的账号

1
emFvZ*******oZW4

4.输入经过base64加密的密码 

1
UVRXSU**************5RQw

一般的，邮箱服务商默认是不允许用户在邮件客户端软件登陆的，但如果需要，需要去后台开启，并且获得授权码，使用邮箱地址+授权码在邮件客户端登陆。

认证成功会返回

235 Authentication successful

输入发件人与收件人#

分别输入发件人与收件人 

1
2
3
mail from:<za*****en@163.com>

rcpt to:<fe*****ng@163.com>

输入正确会返回

250 Mail OK

输入邮件数据#

输入 data 命令，然后编写要发送的邮件内容。

表示发件人，```to``` 表示收件人（可多个），```cc``` 表示抄送，```bcc``` 表示暗抄送，```subject```表示邮件标题。
1
2
3

接着 ```空一行```，然后输入邮件内容，最后以点 ```.``` 结束数据输入。

data

from:za*****en@163.com
to:fe*****ng@163.com
cc:erdo*****ong@163.com
bcc:51****521@qq.com
subject:This is a test email. Ignore it

This is the HTML message body in bold bold bold!

.

1
2
3
4
5
6
7
8
9
10
11

##### 断开连接

使用 ```quit``` 命令断开连接。



#### 使用POP3[<sup>2</sup>](#reference)协议接收邮件

##### 连接
使用telnet命令与163邮箱的pop3服务器建立连接，110表示端口号

telnet pop3.163.com 110

1
2
3
4
5

##### 认证状态
与POP3服务器成功建立连接后，POP3服务器会话此时处于认证状态，客户端需要提供账号和密码来为自己认证。


user za*****en

pass QTWIF*****STQC

1
2
3
4
5
6
7
> POP3认证的时候，账号密码使用原文。

##### 事务状态
客户端认证成功后，POP3服务器进入事务状态，具体操作是：POP3服务器锁住并且打开邮箱。

处于事务状态可以执行以下命令来操作邮件：

STAT Command ………… 查询邮箱中的统计信息
LIST Command ………… 列出邮箱中的邮件信息
RETR Command ………… 获取某封邮件的内容
DELE Command ………… 给某封邮件设置删除标记
NOOP Command ………… 检查客户端与POP3服务器的连接情况
RSET Command ………… 清除所有邮件的删除标记

1
2
3
4
5


使用 ```list``` 命令查看邮件列表，返回邮件列表序号和邮件的存储大小，单位字节。


list
+OK 35 11563487
1 6488
2 16067
3 88116
4 34166
5 39133
6 43443
7 3747
8 42304
9 2366
10 2100
11 85673
12 3337
13 12782
14 90477
15 10484
16 21241
17 81829
18 1591
19 3132
20 2033
21 1626
22 1601
23 3120
24 85708
25 1626
26 2143
27 97037
28 16652
29 16708
30 85513
31 4788181
32 5839338
33 23664
34 8468
35 1593
.

1
2
3
4
5


使用 ```retr msg``` 命令获取邮件内容，参数msg为邮件序号


retr 35
+OK 1593 octets
Received: from qq.com (unknown [113.96.223.68])
by mx40 (Coremail) with SMTP id WsCowAAH4Dv04MRekurPAA–.17594S3;
Wed, 20 May 2020 15:49:08 +0800 (CST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=qq.com; s=s201512;
t=1589960948; bh=Rg9Ilk6oCZAHksj409f6LHX6GuP72cTqrNUPvlZJqnM=;
h=From:To:Subject:Mime-Version:Date:Message-ID;
b=rtqnxFIs3rmz4zLMErF3Q1rjULVsgBujmpY/wzoFYYa8OKTbr4yg4oN3qP8WC0NPW
MIPQYWPXfZ99rbe9aEWLam7D4CB+qzTuS9LY/x2D7TizGrRcjsvrwJ0xKhkCXocx2G
GBqd7+3iRQhZQiF0SLDvr81rqZkvfDuIIh73WzEs=
From: “=?gb18030?B?Y2hlbnphb2Zlbmc=?=” 51****521@qq.com
To: zaen@163.com
Subject: =?gbk?B?19S2r7vYuLQ6aGVsbG8gd29ybGQ=?=
Mime-Version: 1.0
Content-Type: text/html;
charset=”gbk”
Content-Transfer-Encoding: base64
Date: Wed, 20 May 2020 15:49:07 +0800
Message-ID: tencent_2A0A7603148F38FD5B986F86@qq.com
X-QQ-MIME: TCMime 1.0 by Tencent
X-Mailer: QQMail 2.x
X-QQ-Mailer: QQMail 2.x
X-QQ-HolidayReply: true
X-QQ-mid: bglocal204t1589960947t3211568
X-QQ-SENDSIZE: 520
Received: from qq.com (unknown [127.0.0.1])
by smtp.qq.com (ESMTP) with SMTP
id ; Wed, 20 May 2020 15:49:07 +0800 (CST)
Feedback-ID: bglocal:qq.com:bgspam:bgspam8
X-CM-TRANSID:WsCowAAH4Dv04MRekurPAA–.17594S3
Authentication-Results: mx40; spf=pass smtp.mail=51521+auto_=zaofe
ngchen=163.com@qq.com; dkim=pass header.i=@qq.com
X-Coremail-Antispam: 1Uf129KBjDUn29KB7ZKAUJUUUUU529EdanIXcx71UUUUU7v73
VFW2AGmfu7bjvjm3AaLaJ3UbIYCTnIWIevJa73UjIFyTuYvjxUg7UUDUUUU
Sender: 51521+auto_=zaen=163.com@qq.com

xPq1xNPKvP7O0tLRvq3K1bW9wcujrNC70LujoQ==
.

```

更新状态#

当客户端从事务状态发出 quit 命令时，POP3会话从事务状态进入更新状态。

如果会话因客户端以外的原因被终结，那么POP3不会进入更新状态，也不会操作（包括删除、移动等）邮箱里面的邮件

#### 参考

[1] smtp-rfc2821

[2] pop3-rfc1939