Juinjonn

数据结构之一对一

发表于 | 分类于 | | 阅读次数

系统按照最大数据类型对齐;

为什么同一结构,在不同平台大小不同?
因为:

  • 不同平台上相同类型所占(内存)字节不同
  • 不同平台对齐方式不一样

#pragma pack(1):系统按照一个字节对齐。
1

1
2
3
4
5
6
7
struct Node
{
int a;
short b;
char c;
short d;
}

小端存储:低字节写在低地址里
联合体内所有变量共用同一块地址空间
全局变量和静态变量默认初始化为0

数据结构有几种结构？
集合，一对一，一对多，多对多。四种！

OneByOne(一对一)

元素同属一个集合,前后元素有关系并单向
例如:线性表:
一个表里面元素a1到aN,a1没有直接前驱有且仅有一个直接后继,ai作为中间元素,有且仅有一个直接前驱
和一个直接后继,aN作为表的尾元素,没有直接后继,有且仅有一个直接前驱

直接前驱也叫直接前件

线性表的两种储存结构

  • 顺序储存→数组
  • 链式储存→链表

递归和循环的优缺点
递归:代码简单,逻辑简单(便于阅读),但是函数跳转浪费时间,函数参数占用空间
循环:相对于递归,节约资源,但是每层循环逻辑必须弄清

stack(栈)

特性:先进后出,且只能操作栈顶
本质:也许是数组,也许是链表
stack

常用栈:单向链表,头添加,头删除

八个基本操作

  • Push 添加元素
  • Pop 删除元素
  • Init 初始化栈
  • Clear 清空栈
  • Deatroy 销毁栈
  • GetCount 获得栈元素个数
  • GetTop 得到栈顶
  • IsEmpty 判断是否是空栈
    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
    #include<stdio.h>
    #include<stdlib.h>
    typedef struct node1
    {
    	int nValue;
    	struct node1 *pNext;
    }MyStack;
    typedef struct node2
    {
    	MyStack *pTop;
    	int nCount;
    }Stack;
    //初始化
    void s_Init(Stack **pStack)
    {
    	if(pStack == NULL)return;
    	*pStack = (Stack*)malloc(sizeof(Stack));
    	(*pStack)->pTop = NULL;
    	(*pStack)->nCount = 0;
    }
    //压栈
    void s_Push(Stack *pStack,int nNum)
    {
    	MyStack *pTemp = NULL;
    	if(pStack == NULL)
    	{
    		printf("栈没啦!!!\n");
    		return;
    	}
    	//开辟新节点装载值
    	pTemp = (MyStack*)malloc(sizeof(MyStack));
    	pTemp->nValue = nNum;
    	pTemp->pNext = pStack->pTop;
    	pStack->pTop = pTemp;
    	pStack->nCount++;
    }
    //出栈
    int s_Pop(Stack *pStack)
    {
    	MyStack *pDel = NULL;
    	int nNum;
    	if(pStack == NULL || pStack->pTop == NULL)return -1;
    	pDel = pStack->pTop;
    	nNum = pDel->nValue;
    	pStack->pTop = pStack->pTop->pNext;
    	free(pDel);
    	pDel = NULL;
    	pStack->nCount--;
    	return nNum;
    }
    //清空
    void s_Clear(Stack *pStack)
    {
    	if(pStack == NULL || pStack->pTop == NULL)return;
    	while(pStack->nCount)
    	{
    		s_Pop(pStack);
    	}
    }
    //销毁
    void s_Destroy(Stack **pStack)
    {
    	s_Clear(*pStack);
    	free(*pStack);
    	*pStack = NULL;
    }
    //获得栈内元素个数
    int s_GetCount(Stack *pStack)
    {
    	if(pStack == NULL)return -1;
    	return  pStack->nCount;
    }
    //获得栈顶
    MyStack *s_GetTop(Stack *pStack)
    {
    	if(pStack == NULL)return NULL;
    	return pStack->pTop;
    }
    //是否为空栈
    int s_IsEmpty(Stack *pStack)
    {
    	if(pStack == NULL)return -1;
    	return (pStack->nCount)?0:1;
    }
    int main()
    {
    	Stack *pStack = NULL;
    	s_Init(&pStack);
    	s_Push(pStack,1);
    	s_Push(pStack,2);
    	s_Push(pStack,3);
    	s_Push(pStack,4);
    	s_Push(pStack,5);
    	printf("%d\n",s_Pop(pStack));
    	printf("%d\n",s_Pop(pStack));
    	printf("-------------------------------------------------\n");
    	printf("%d\n",s_GetCount(pStack));
    	s_Destroy(&pStack);
    	s_Push(pStack,5);
    	return 0;
    }

二级指针的使用:一般是参数无中生有,和从有到无

递归相当于栈的实际应用
因为:解决大问题的方式与其子问题方式一致(定义)

斐波那契数列FIBONACCI

也叫黄金分割数列

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
#include<stdio.h.>
#include<stdlib.h>
int Fibonacci_1(int n)//迭代法
{
	if (n<=2)
	{
		return 1;
	}
	return Fibonacci_1(n-1)+Fibonacci_1(n-2);
}
int Fibonacci_2(int n)
{
	int i = 3;
	int a = 1;
	int b = 1;
	int c = 0;
	if (n<=2)
	{
		return 1;
	}
	for ( ;i <=n; i++)
	{
		c = a+b;
		a = b;
		b = c;
	}
	return c;
}
int main()
{
	printf("%d\n",Fibonacci_1(10));
	printf("%d\n",Fibonacci_2(10));
	return 0;
}

四则运算

后缀表达式(逆波兰表示法)。
中缀表示法:例如:19+41*5-7/6,也叫表达式

转换规则

中缀转后缀(官方版)

借助辅助栈,遇到数字或字符直接打印,遇到符号(+ - * /),拿当前符号与栈顶元素进行优先级比较。如果当前元素优先级高直接入栈,如果当前元素优先级低,则直接出栈直到比当前元素优先级比它低的,如果遇到左括号无条件入栈,如果遇到右括号,将栈内元素依次出栈直到左括号停下来,如果没有元素,就将栈内元素全部拿出。

非官方版

所以运算加括号,将运算符放到括号后面。

后缀转中缀

遇到数字或字符直接进栈,遇到符号将栈顶元素下一个和栈顶元素构成表达式。

Queue

实际应用:打印机
特性:先进先出
queue

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
#include<stdio.h>
#include<stdlib.h>
typedef struct node3
{
	int nValue;
	struct node3 *pNext;
}MyQueue;
typedef struct node4
{
	int nCount;
	MyQueue* pHead;
	MyQueue *pTail;
}Queue;
void q_Init(Queue **pQueue)
{
	if(pQueue == NULL)return;
	*pQueue = (Queue*)malloc(sizeof(Queue));
	(*pQueue)->nCount = 0;
	(*pQueue)->pHead = NULL;
	(*pQueue)->pTail = NULL;
}
void q_Push(Queue *pQueue,int nNum)
{
	MyQueue *pTemp = NULL;
	if(pQueue == NULL)return;
	pTemp = (MyQueue*)malloc(sizeof(MyQueue));
	pTemp->nValue = nNum;
	pTemp->pNext = NULL;
	if(pQueue->pHead == NULL)
	{
		pQueue->pHead = pTemp;
	}
	else
	{
		pQueue->pTail->pNext = pTemp;
	}
	pQueue->pTail = pTemp;
	pQueue->nCount++;
}
int q_Pop(Queue *pQueue)
{
	MyQueue *pDel = NULL;
	int nNum;
	if(pQueue == NULL || pQueue->pHead == NULL)return -1;
	pDel = pQueue->pHead;
	nNum = pDel->nValue;
	pQueue->pHead = pQueue->pHead->pNext;
	free(pDel);
	pDel = NULL;
	pQueue->nCount--;
	if(pQueue->nCount == 0)
	{
		pQueue->pTail = NULL;
	}
	return nNum;
}
int q_IsEmpty(Queue *pQueue)
{
	if(pQueue == NULL )return -1;
	return pQueue->nCount ? 0:1;
}

Queue To Stack

用两个Queue(队列)实现Stack(栈)

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
#include<stdio.h>
#include<stdlib.h>
typedef struct node3
{
	int nValue;
	struct node3 *pNext;
}MyQueue;
typedef struct node4
{
	int nCount;
	MyQueue* pHead;
	MyQueue *pTail;
}Queue;
typedef struct node
{
	Queue *pQueue1;
	Queue *pQueue2;
	int nCount;
}Stack;
void q_Init(Queue **pQueue)
{
	if(pQueue == NULL)return;
	*pQueue = (Queue*)malloc(sizeof(Queue));
	(*pQueue)->nCount = 0;
	(*pQueue)->pHead = NULL;
	(*pQueue)->pTail = NULL;
}
void q_Push(Queue *pQueue,int nNum)
{
	MyQueue *pTemp = NULL;
	if(pQueue == NULL)return;
	pTemp = (MyQueue*)malloc(sizeof(MyQueue));
	pTemp->nValue = nNum;
	pTemp->pNext = NULL;
	if(pQueue->pHead == NULL)
	{
		pQueue->pHead = pTemp;
	}
	else
	{
		pQueue->pTail->pNext = pTemp;
	}
	pQueue->pTail = pTemp;
	pQueue->nCount++;
}
int q_Pop(Queue *pQueue)
{
	MyQueue *pDel = NULL;
	int nNum;
	if(pQueue == NULL || pQueue->pHead == NULL)return -1;
	pDel = pQueue->pHead;
	nNum = pDel->nValue;
	pQueue->pHead = pQueue->pHead->pNext;
	free(pDel);
	pDel = NULL;
	pQueue->nCount--;
	if(pQueue->nCount == 0)
	{
		pQueue->pTail = NULL;
	}
	return nNum;
}
int q_IsEmpty(Queue *pQueue)
{
	if(pQueue == NULL )return -1;
	return pQueue->nCount ? 0:1;
}
void s_Init(Stack **pStack)
{
	if(pStack == NULL)return;
	*pStack = (Stack*)malloc(sizeof(Stack));
	(*pStack)->nCount = 0;
	(*pStack)->pQueue1 = NULL;
	(*pStack)->pQueue2 = NULL;
	//初始化两个队列
	q_Init(&((*pStack)->pQueue1));
	q_Init(&((*pStack)->pQueue2));
}
void s_Push(Stack *pStack,int nNum)
{
	MyQueue *pTemp = NULL;
	if(pStack == NULL || pStack->pQueue1 == NULL || pStack->pQueue2 == NULL)return;
	
	//将数值放入非空队列
	if(!q_IsEmpty(pStack->pQueue1))
	{
		q_Push(pStack->pQueue1,nNum);
	}
	else
	{
		q_Push(pStack->pQueue2,nNum);
	}
}
int s_Pop(Stack *pStack)
{
	int nNum;
	if(pStack == NULL || (pStack->pQueue1 == NULL && pStack->pQueue2 == NULL))return -1;
	//检测非空队列
	if(!q_IsEmpty(pStack->pQueue1))
	{
		//将队列元素依次放入空队列里 直到剩一个的时候停下来
		while(pStack->pQueue1->nCount != 1)
		{
			q_Push(pStack->pQueue2, q_Pop(pStack->pQueue1) );
		}
		nNum = q_Pop(pStack->pQueue1);
	}
	else
	{
		//将队列元素依次放入空队列里 直到剩一个的时候停下来
		while(pStack->pQueue2->nCount != 1)
		{
			q_Push(pStack->pQueue1, q_Pop(pStack->pQueue2) );
		}
		nNum = q_Pop(pStack->pQueue2);
	}
	return nNum;
}

Stack To Queue

用两个栈实现队列

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
#include<stdio.h>
#include<stdlib.h>
typedef struct node1
{
	int nValue;
	struct node1 *pNext;
}MyStack;
typedef struct node2
{
	MyStack *pTop;
	int nCount;
}Stack;
typedef struct node3
{
	Stack *Mystack_1;
	Stack *Mystack_2;
	int nCount;
}MyQueue;
//初始化
void s_Init(Stack **pStack)
{
	if(pStack == NULL)return;
	*pStack = (Stack*)malloc(sizeof(Stack));
	(*pStack)->pTop = NULL;
	(*pStack)->nCount = 0;
}
//压栈
void s_Push(Stack *pStack,int nNum)
{
	MyStack *pTemp = NULL;
	if(pStack == NULL)
	{
		printf("栈没啦!!!\n");
		return;
	}
	//开辟新节点装载值
	pTemp = (MyStack*)malloc(sizeof(MyStack));
	pTemp->nValue = nNum;
	pTemp->pNext = pStack->pTop;
	pStack->pTop = pTemp;
	pStack->nCount++;
}
//出栈
int s_Pop(Stack *pStack)
{
	MyStack *pDel = NULL;
	int nNum;
	if(pStack == NULL || pStack->pTop == NULL)return -1;
	pDel = pStack->pTop;
	nNum = pDel->nValue;
	pStack->pTop = pStack->pTop->pNext;
	free(pDel);
	pDel = NULL;
	pStack->nCount--;
	return nNum;
}	
//是否为空栈
int s_IsEmpty(Stack *pStack)
{
	if(pStack == NULL)return -1;
	return (pStack->nCount)?0:1;
}
void q_Init(MyQueue **queue)
{
	if (queue == NULL )return;
	(*queue) = (MyQueue*)malloc(sizeof(MyQueue));
	(*queue)->Mystack_1 = NULL;
	(*queue)->Mystack_2 = NULL;
	s_Init(&(*queue)->Mystack_2);
	s_Init(&(*queue)->Mystack_1);
	(*queue)->nCount = 0;
}
void q_Push(MyQueue *queue,int nValue)
{
	s_Push(queue->Mystack_2,nValue);
	return;
}
int q_Pop(MyQueue *queue)
{
	int num;
	if (s_IsEmpty((queue)->Mystack_1))
	{
		while (queue->Mystack_2->nCount != 1)
		{
			s_Push((queue)->Mystack_1,s_Pop((queue)->Mystack_2));
		}
		num = s_Pop((queue)->Mystack_2);
		while (queue->Mystack_1->nCount != 0)
		{
			s_Push((queue)->Mystack_2,s_Pop((queue)->Mystack_1));
		}
	}
	return num;
}
技术无价，一元美滋滋！