详解堆栈的几种实现方法——C语言版
基本的抽象数据类型(ADT)是编写C程序必要的过程,这类ADT有链表、堆栈、队列和树等,本文主要讲解下堆栈的几种实现方法以及他们的优缺点。
堆栈(stack)的显著特点是后进先出(Last-In First-Out, LIFO),其实现的方法有三种可选方案:静态数组、动态分配的数组、动态分配的链式结构。
静态数组:特点是要求结构的长度固定,而且长度在编译时候就得确定。其优点是结构简单,实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制,适用于知道明确长度的场合。
动态数组:特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活,缺点是由此会增加程序的复杂性。
链式结构:特点是无长度上线,需要的时候再申请分配内存空间,可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存,在链式结构中访问一个特定元素的效率不如数组。
首先先确定一个堆栈接口的头文件,里面包含了各个方案下的函数原型,放在一起是为了实现程序的模块化以及便于修改。然后再接着分别介绍各个方案的具体实施方法。
堆栈接口stack.h文件代码:
[cpp]view plaincopy
1./*
2.** 堆栈模块的接口 stack.h
3.*/
4.#include
5.
6.#define STACK_TYPE int /* 堆栈所存储的值的数据类型 */
7.
8./*
9.** 函数原型:create_stack
10.** 创建堆栈,参数指定堆栈可以保存多少个元素。
11.** 注意:此函数只适用于动态分配数组形式的堆栈。
12.*/
13.void create_stack(size_t size);
14.
15./*
16.** 函数原型:destroy_stack
17.** 销毁一个堆栈,释放堆栈所适用的内存。
18.** 注意:此函数只适用于动态分配数组和链式结构的堆栈。
19.*/
20.void destroy_stack(void);
21.
22./*
23.** 函数原型:push
24.** 将一个新值压入堆栈中,参数是被压入的值。
25.*/
26.void push(STACK_TYPE value);
27.
28./*
29.** 函数原型:pop
30.** 弹出堆栈中栈顶的一个值,并丢弃。
31.*/
32.void pop(void);
33.
34./*
35.** 函数原型:top
36.** 返回堆栈顶部元素的值,但不改变堆栈结构。
37.*/
38.STACK_TYPE top(void);
39.
40./*
41.** 函数原型:is_empty
42.** 如果堆栈为空,返回TRUE,否则返回FALSE。
43.*/
44.int is_empty(void);
45.
46./*
47.** 函数原型:is_full
48.** 如果堆栈为满,返回TRUE,否则返回FALSE。
49.*/
50.int is_full(void);
一、静态数组堆栈
在静态数组堆栈中,STACK_SIZE表示堆栈所能存储的元素的最大值,用top_element 作为数组下标来表示堆栈里面的元素,当top_element == -1的时候表示堆栈为空;当
top_element == STACK_SIZE - 1的时候表示堆栈为满。push的时候top_element加1,top_element == 0时表示第一个堆栈元素;pop的时候top_element减1。
a_stack.c 源代码如下:
[cpp]view plaincopy
1./*
2.**
3.** 静态数组实现堆栈程序 a_stack.c ,数组长度由#define确定
4.*/
5.
6.#include"stack.h"
7.#include
8.#include
9.
10.#define STACK_SIZE 100 /* 堆栈最大容纳元素数量 */
11.
12./*
13.** 存储堆栈中的数组和一个指向堆栈顶部元素的指针
14.*/
15.static STACK_TYPE stack[STACK_SIZE];
16.static int top_element = -1;
17.
18./* push */
19.void push(STACK_TYPE value)
20.{
21. assert(!is_full()); /* 压入堆栈之前先判断是否堆栈已满*/
22. top_element += 1;
23. stack[top_element] = value;
24.}
25.
26./* pop */
27.void pop(void)
28.{
29. assert(!is_empty()); /* 弹出堆栈之前先判断是否堆栈已空 */
30. top_element -= 1;
31.}
32.
33./* top */
34.STACK_TYPE top(void)
35.{
36. assert(!is_empty());
37.return stack[top_element];
38.}
39.
40./* is_empty */
41.int is_empty(void)
42.{
43.return top_element == -1;
44.}
45.
46./* is_full */
47.int is_full(void)
48.{
49.return top_element == STACK_SIZE - 1;
50.}
51.
52./*
53.** 定义一个print函数,用来打印堆栈里面的元素。
54.*/
55.void print(void)
56.{
57.int i;
58. i = top_element;
59. printf("打印出静态数组堆栈里面的值: ");
60.if(i == -1)
61. printf("这是个空堆栈\n");
62.while(i!= -1)
63. printf("%d ",stack[i--]);
64. printf("\n");
65.}
66.int main(void)
67.{
68. print();
69. push(10); push(9); push(7); push(6); push(5);
70. push(4); push(3); push(2); push(1); push(0);
71. printf("push压入数值后:\n");
72. print();
73. printf("\n");
74. pop();
75. pop();
76. printf("经过pop弹出几个元素后的堆栈元素:\n");
77. print();
78. printf("\n");
79. printf("top()调用出来的值: %d\n",top());
80.return 1;
81.}
结果如下图:
二、动态数组堆栈
头文件还是用stack.h,改动的并不是很多,增加了stack_size变量取代STACK_SIZE 来保存堆栈的长度,数组由一个指针来代替,在全局变量下缺省为0。
create_stack函数首先检查堆栈是否已经创建,然后才分配所需数量的内存并检查分配是否成功。destroy_stack函数首先检查堆栈是否存在,已经释放内存之后把长度和指针变量重新设置为零。is_empty 和is_full 函数中添加了一条断言,防止任何堆栈函数在堆栈被创建之前就被调用。
d_stack.c源代码如下:
[cpp]view plaincopy
1./*
2.** 动态分配数组实现的堆栈程序 d_stack.c
3.** 堆栈的长度在创建堆栈的函数被调用时候给出,该函数必须在任何其他操作堆栈的函数被调
用之前条用。
4.*/
5.#include"stack.h"
6.#include
7.#include
8.#include
9.
10./*
11.** 用于存储堆栈元素的数组和指向堆栈顶部元素的指针
12.*/
13.static STACK_TYPE *stack;
14.static int stack_size;
15.static int top_element = -1;
16.
17./* create_stack */
18.void create_stack(size_t size)
19.{
20. assert(stack_size == 0);
21. stack_size = size;
22. stack = (STACK_TYPE *)malloc(stack_size * sizeof(STACK_TYPE));
23.if(stack == NULL)
24. perror("malloc分配失败");
25.}
26.
27./* destroy */
28.void destroy_stack(void)
29.{
30. assert(stack_size > 0);
31. stack_size = 0;
32. free(stack);
33. stack = NULL;
34.}
35.
36./* push */
37.void push(STACK_TYPE value)
38.{
39. assert(!is_full());
40. top_element += 1;
41. stack[top_element] = value;
42.}
43.
44./* pop */
45.void pop(void)
46.{
47. assert(!is_empty());
48. top_element -= 1;
49.}
50.
51./* top */
52.STACK_TYPE top(void)
53.{
54. assert(!is_empty());
55.return stack[top_element];
56.}
57.
58./* is_empty */
59.int is_empty(void)
60.{
61. assert(stack_size > 0);
62.return top_element == -1;
63.}
64.
65./* is_full */
66.int is_full(void)
67.{
68. assert(stack_size > 0);
69.return top_element == stack_size - 1;
70.}
71.
72.
73./*
74.** 定义一个print函数,用来打印堆栈里面的元素。
75.*/
76.void print(void)
77.{
78.int i;
79. i = top_element;
80. printf("打印出动态数组堆栈里面的值: ");
81.if(i == -1)
82. printf("这是个空堆栈\n");
83.while(i!= -1)
84. printf("%d ",stack[i--]);
85. printf("\n");
86.}
87.int main(void)
88.{
89. create_stack(50);
90. print();
91. push(10); push(9); push(7); push(6); push(5);
92. push(4); push(3); push(2); push(1); push(0);
93. printf("push压入数值后:\n");
94. print();
95. printf("\n");
96. pop();
97. pop();
98. printf("经过pop弹出几个元素后的堆栈元素:\n");
99. print();
100. printf("\n");
101. printf("top()调用出来的值: %d\n",top()); 102. destroy_stack();
103.return 1;
104.}
结果如下图:
三、链式堆栈
由于只有堆栈顶部元素才可以被访问,因此适用单链表可以很好实现链式堆栈,而且无长度限制。把一个元素压入堆栈是通过在链表头部添加一个元素实现。弹出一个元素是通过删除链表头部第一个元素实现。由于没有长度限制,故不需要create_stack函数,需要destroy_stack进行释放内存以避免内存泄漏。
头文件stack.h 不变,l_stack.c 源代码如下:
[cpp]view plaincopy
1./*
2.** 单链表实现堆栈,没有长度限制
3.*/
4.#include"stack.h"
5.#include
6.#include
7.#include
8.
9.#define FALSE 0
10.
11./*
12.** 定义一个结构以存储堆栈元素。
13.*/
14.typedef struct STACK_NODE
15.{
16. STACK_TYPE value;
17.struct STACK_NODE *next;
18.} StackNode;
19.
20./* 指向堆栈中第一个节点的指针 */
21.static StackNode *stack;
22.
23./* create_stack */
24.void create_stack(size_t size)
25.{}
26.
27./* destroy_stack */
28.void destroy_stack(void)
29.{
30.while(!is_empty())
31. pop(); /* 逐个弹出元素,逐个释放节点内存 */
32.}
33.
34./* push */
35.void push(STACK_TYPE value)
36.{
37. StackNode *new_node;
38. new_node = (StackNode *)malloc(sizeof(StackNode));
39.if(new_node == NULL)
40. perror("malloc fail");
41. new_node->value = value;
42. new_node->next = stack; /* 新元素插入链表头部 */
43. stack = new_node; /* stack 重新指向链表头部 */
44.}
45.
46./* pop */
47.void pop(void)
48.{
49. StackNode *first_node;
50.
51. assert(!is_empty());
52. first_node = stack;
53. stack = first_node->next;
54. free(first_node);
55.}
56.
57./* top */
58.STACK_TYPE top(void)
59.{
60. assert(!is_empty());
61.return stack->value;
62.}
63.
64./* is_empty */
65.int is_empty(void)
66.{
67.return stack == NULL;
68.}
69.
70./* is_full */
71.int is_full(void)
72.{
73.return FALSE;
74.}
75.
76.
77./*
78.** 定义一个print函数,用来打印堆栈里面的元素。
79.*/
80.void print(void)
81.{
82. StackNode *p_node;
83. p_node = stack;
84. printf("打印出链式堆栈里面的值: ");
85.if(p_node == NULL)
86. printf("堆栈为空\n");
87.while(p_node != NULL)
88. {
89. printf("%d ", p_node->value);
90. p_node = p_node->next;
91. }
92. printf("\n");
93.}
94.int main(void)
95.{
96. print();
97. push(10); push(9); push(7); push(6); push(5);
98. push(4); push(3); push(2); push(1); push(0);
99. printf("push压入数值后:\n");
100. print();
101. printf("\n");
102. pop();
103. pop();
104. printf("经过pop弹出几个元素后的堆栈元素:\n"); 105. print();
106. printf("\n");
107. printf("top()调用出来的值: %d\n",top()); 108. destroy_stack();
109.return 1;
110.}
结果如下图:
栈的应用:C实现简单计算器(表达式的计算) 作为栈的著名应用,表达式的计算可以用下面方法实现: 首先建立两个栈,操作数栈NUM_S和运算符栈OPR_S。 其中,操作数栈用来存储表达式中的操作数;运算符栈用来存储表达式中的运算符。可以用字符‘=’来表示表达式结束符。 自左至右的扫描待处理的表达式,并假设当前扫描到的符号为W,根据不同的符号W 做如下不同的处理: 1.若W为操作数,则将W压入操作数栈NUM_S,且继续扫描下一个字符; 2.若W为运算符,则根据运算符的性质做相应的处理: (0)若符号栈为空,无条件入栈当前指针指向的字符 (1)若w为不大于运算符栈栈顶的运算符,则从操作数栈NUM_S中弹出两个操作数,设先后弹出的操作数为a、b,再从运算符栈 OPR_S中弹出一个运算符,比如为+,然后作运算a+b,并将运算结果压入操作数栈NUM_S。 (2)若w为左括号或者运算符的优先级大于运算符栈栈顶的运算符,则将运算符W 压入运算符栈OPR_S,并继续扫描下一个字符。 (3)若运算符W为右括号,循环操作(设先后弹出的操作数为a、b,再从运算符栈OPR_S中弹出一个运算符,比如为+,然后作运 算a+b, 并将运算结果压入操作数栈NUM_S),直到从运算符栈中弹出第一个左括号。 (4)若运算符W为表达式结束符‘=’,循环操作(设先后弹出的操作数为a、b,再从运算符栈OPR_S中弹出一个运算符,比如为 +,然后作运算a+b, 并将运算结果压入操作数栈NUM_S),直到运算符栈为空为止。此时,操作数栈栈顶元素即为表达式的 值。 ====================================================================== === 举例:计算3+(5-2*3)/4-2= (1)开始栈为空,3入栈,+入栈,(无条件入栈,5入栈,-号优先级比(高,所以-号入栈,2入栈,*优先级比目前栈顶的-号优先级高,所以*入栈,3入栈,接着扫描到)括号,)括号不入栈 | | | | --------- ---------- | 3 | | * | --------- ---------- | 2 | | - |
一个由C/C++编译的程序占用的内存分为以下几个部分 1、栈区(stack)—由编译器自动分配释放,存放函数的参数值,局部变量的值等。其 操作方式类似于数据结构中的栈。 2、堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。 3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。 - 程序结束后由系统释放。 4、文字常量区—常量字符串就是放在这里的。程序结束后由系统释放 5、程序代码区—存放函数体的二进制代码。 二、例子程序 这是一个前辈写的,非常详细 //main.cpp int a = 0; 全局初始化区 char *p1; 全局未初始化区 main() { int b; 栈 char s[] = "abc"; 栈 char *p2; 栈 char *p3 = "123456"; 123456\0在常量区,p3在栈上。 static int c =0;全局(静态)初始化区 p1 = (char *)malloc(10); p2 = (char *)malloc(20); 分配得来得10和20字节的区域就在堆区。 strcpy(p1, "123456"); 123456\0放在常量区,编译器可能会将它与p3所指向的"123456" 优化成一个地方。 } 二、堆和栈的理论知识 2.1申请方式 stack: 由系统自动分配。例如,声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空间 heap: 需要程序员自己申请,并指明大小,在c中malloc函数 如p1 = (char *)malloc(10); 在C++中用new运算符 如p2 = new char[10]; 但是注意p1、p2本身是在栈中的。
基于模糊控制的速度控制 ——地面智能移动车辆速度控制系统问题描述 利用模糊控制的方法解决速度跟踪问题,即已知期望速度(desire speed),控制油门(throttle output)和刹车(brake output)来跟踪该速度。已知输入:车速和发动机转速(值可观测)。欲控制刹车和油门电压(同一时刻只有一个量起作用)。 算法思想 模糊控制器是一语言控制器,使得操作人员易于使用自然语言进行人机对话。模糊控制器是一种容易控制、掌握的较理想的非线性控制器,具有较佳的适应性及强健性(Robustness)、较佳的容错性(Fault Tolerance)。利用控制法则来描述系统变量间的关系。不用数值而用语言式的模糊变量来描述系统,模糊控制器不必对被控制对象建立完整的数学模式。 Figure 1模糊控制器的结构图 模糊控制的优点: (1)模糊控制是一种基于规则的控制,它直接采用语言型控制规则,出发点是现场操作人员的控制经验或相关专家的知识,在设计中不需要建立被控对象的精确的数学模型,因而使得控制机理和策略易于接受与理解,设计简单,便于应用。 (2)由工业过程的定性认识出发,比较容易建立语言控制规则,因而模糊控制对那些数学模型难以获取,动态特性不易掌握或变化非常显著的对象非常适用。 (3)基于模型的控制算法及系统设计方法,由于出发点和性能指标的不同,容易导致较大差异;但一个系统语言控制规则却具有相对的独立性,利用这些控制规律间的模糊连接,容易找到折中的选择,使控制效果优于常规控制器。 (4)模糊控制是基于启发性的知识及语言决策规则设计的,这有利于模拟人工控制的过程和方法,增强控制系统的适应能力,使之具有一定的智能水平。 简化系统设计的复杂性,特别适用于非线性、时变、模型不完全的系统上。 模糊控制的缺点
堆、栈及静态数据区详解 五大内存分区 在C++中,内存分成5个区,他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。 栈,就是那些由编译器在需要的时候分配,在不需要的时候自动清楚的变量的存储区。里面的变量通常是局部变量、函数参数等。 堆,就是那些由new分配的内存块,他们的释放编译器不去管,由我们的应用程序去控制,一般一个new就要对应一个delete。如果程序员没有释放掉,那么在程序结束后,操作系统会自动回收。 自由存储区,就是那些由malloc等分配的内存块,他和堆是十分相似的,不过它是用free 来结束自己的生命的。 全局/静态存储区,全局变量和静态变量被分配到同一块内存中,在以前的C语言中,全局变量又分为初始化的和未初始化的,在C++里面没有这个区分了,他们共同占用同一块内存区。 常量存储区,这是一块比较特殊的存储区,他们里面存放的是常量,不允许修改(当然,你要通过非正当手段也可以修改,而且方法很多) 明确区分堆与栈 在bbs上,堆与栈的区分问题,似乎是一个永恒的话题,由此可见,初学者对此往往是混淆不清的,所以我决定拿他第一个开刀。 首先,我们举一个例子: void f() { int* p=new int[5]; } 这条短短的一句话就包含了堆与栈,看到new,我们首先就应该想到,我们分配了一块堆内存,那么指针p呢?他分配的是一块栈内存,所以这句话的意思就是:在栈内存中存放了一个指向一块堆内存的指针p。在程序会先确定在堆中分配内存的大小,然后调用operator new分配内存,然后返回这块内存的首地址,放入栈中,他在VC6下的汇编代码如下: 00401028 push 14h 0040102A call operator new (00401060) 0040102F add esp,4 00401032 mov dword ptr [ebp-8],eax 00401035 mov eax,dword ptr [ebp-8]
PWM调速的C语言程序编写 关于PWM的原理在上一篇文章中已经说的很详细了,现在就细说一下pwm C语言程序的编写。 C语言中PWM的编写有这么几种方法;一、用普通的I/O口输出的PWM ,二、使用定时计数器编写,三、就是使用片内PWM了。 1 先说使用普通的I\O口编写PWM程序了。 使用I/O口输出PWM波形你必须首先明白PWM他的实质是:调制占空比,占空比就是波形中高电平的长度与整个波长的比值。我们写C语言的目的是写PWM波形的一个周期。在这个周期内高低电平的比值是可以改变的。这也就符合了PWM的原意脉宽调制。即高电平的宽度的调制。当然了PWM他也可用于改变频率,我们这里只先说他改变脉宽。 一旦我们的C语言程序写完那么他产生的PWM波形的频率就一定了。(也可写频率变化的PWM,难度有点大)一般我们控制使用1K到10K的PWM波进行控制。当然了你也可在要求不是很高的地方使用频率更低的PWM波。比如在飞思卡尔智能车比赛中我们学校使用的PWM波频率只有600HZ. 我们要改变一个PWM波周期内的高电平的宽度显然需要将一个PWM波的周期分成单片机可以控制的N个小的周期,N的
取值越大你的调速等级越高,但产生的PWM频率就越低。我们下面以实现100级调速为例编写PWM程序。 先写出程序再慢慢给大家分析 void pwm (uchar x,uint y) //X 为占空比 Y为函数使用时间 { uint i,j,a,b; for(i=y;i>0;i--) //定时外函数 { for(j=7;j>0;j--) //定时内函数 { for(a=y;a>0;a--) //PWM波高电平宽度 { PORTA=0X01; }
一、预备知识—程序的内存分配 一个由c/C++编译的程序占用的内存分为以下几个部分 1、栈区(stack)—由编译器自动分配释放,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。 2、堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。 3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。- 程序结束后有系统释放 4、文字常量区—常量字符串就是放在这里的。程序结束后由系统释放 5、程序代码区—存放函数体的二进制代码。 二、例子程序 这是一个前辈写的,非常详细 //main.cpp int a = 0; 全局初始化区 char *p1; 全局未初始化区 main() { int b; 栈 char s[] = "abc"; 栈 char *p2; 栈 char *p3 = "123456"; 123456\0在常量区,p3在栈上。 static int c =0;全局(静态)初始化区 p1 = (char *)malloc(10); p2 = (char *)malloc(20); 分配得来得10和20字节的区域就在堆区。 strcpy(p1, "123456"); 123456\0放在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方。 } 二、堆和栈的理论知识 2.1申请方式 stack: 由系统自动分配。例如,声明在函数中一个局部变量int b; 系统自动在栈中为b开辟空间heap: 需要程序员自己申请,并指明大小,在c中malloc函数 如p1 = (char *)malloc(10); 在C++中用new运算符 如p2 = (char *)malloc(10); 但是注意p1、p2本身是在栈中的。
五种编程方式实现流水灯的单片机C程序 //功能:采用顺序结构实现的流水灯控制程序 /*此方式中采用的是字操作(也称为总线操作)*/ #include
电动车控制器C语言源代码 . #define _E_BIKE_W79E83X_C_ #include "intrins.h" #include "E_BIKE_W79E83X.H" #include"W79E834.h" /******************************************************************** ********* * 主函数 ******************************************************************** * *********/ void main(void) { Init(); // 初始化 Init_IO(); // 初始化端口 H_Sample(); // 霍尔信号采样 Phase_Change(); // 相位变换 AutoHelpEN(1,0x1AA,200); /* 第一个参数设定助力功能允许不否,1为允许,0为禁止 第二个参数设定助力力量(PWM占空比),数值围:0~0x355,数值越大,力量 越大 第三个参数设定助力时间,数值越大,时间越长 */
Keep_SpeedEN(1,0x20,6); /* 第一个参数设定定速巡航功能允许不否,1为允许,0为禁止第二个参数设定定速巡航最低速设置 . . 第三个参数设定在巡航点保持多长时间后才进入巡航 */ Current_Lim(0xB48); /* 过流保护上限值设定 0xB00对应限电流最大大约为2.6A 0xB80对应限流值最大大约为3.8A */ LowVoltage_Lim(0x9B0); /* 欠压保护下限值设定 电池电压为47.9V时ADC采样值为0xB6 ==> 0xB60 推算电池电压为41V时的采样值为0x9B ==> 0x9B0 推算电池电压为40V时的采样值为0x98 ==> 0x980 */ EABS_Set(1,1); /* 第一个参数为滑行充电功能使能,1为允许,0为禁止
堆栈详解(数据与内存中的存储方式) char* r = "hello word!";char b[]="hello word!"*r = 'w';*b='w';其实应该是语法错误,可是VC++6.0没有警告或者错误,r指向的是文字常量区,此区域是编译的时候确定的,并且程序结束的时候自动释放的,*r = 'w';企图修改文字常量区引起错误,b的区别在于其空间是在栈上分配的,因此没有错误。const char* r = "hello word!";*r = 'w';一个由 c/C++编译的程序占用的内存分为以下几个部分1、栈区(stack)—由编译器自动分配释放,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。2、堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。- 程序结束后有系统释放4、文字常量区—常量字符串就是放在这里的。程序结束后由系统释放5、程序代码区—存放函数体的二进制代码。二、例子程序//main.cppint a = 0; 全局初始化区char *p1; 全局未初始化区main(){int b; 栈char s[] = "abc"; 栈char *p2; 栈char *p3 = "123456"; 123456\0在常量区,p3
在栈上。static int c =0;全局(静态)初始化区p1 = (char *)malloc(10);p2 = (char *)malloc(20);分配得来得10和20字节的区域就在堆区。strcpy(p1, "123456"); 123456\0放在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方。}二、堆和栈的理论知识2.1申请方式stack:由系统自动分配。例如,声明在函数中一个局部变量int b; 系统自动在栈中为b开辟空间heap:需要程序员自己申请,并指明大小,在c中malloc函数如p1 = (char *)malloc(10);在C++中用new运算符如p2 = (char *)malloc(10);但是注意p1、p2本身是在栈中的。 2.2申请后系统的响应栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢出。堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。2.3申请大小的限制栈:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的
音量控制M62446的驱动C程序 音量控制M62446 m62446 pdf //------------------------------------------------------------------------- // M62446 drving routines, VER 1.0 // // COPYRIGHT (C) 2000, Enbia Technology Inc. // Target: 8031 // AUTHOR: STEVEN LUO // // Revision History: // 2001/1/5 - Original Version // //------------------------------------------------------------------------- #include
一、设计思想 计算算术表达式可以用两种方法实现: 1.中缀转后缀算法 此算法分两步实现:先将算术表达式转换为后缀表达式,然后对后缀表达式进行计算。具体实现方法如下: (1)中缀转后缀 需要建一个操作符栈op和一个字符数组exp,op栈存放操作符,字符数组用来存放转换以后的后缀表达式。首先,得到用户输入的中缀表达式,将其存入str数组中。 对str数组逐个扫描,如果是数字或小数点,则直接存入exp数组中,当扫描完数值后,在后面加一个#作为分隔符。 如果是操作符,并且栈为空直接入栈,如果栈不为空,与栈顶操作符比较优先等级,若比栈顶优先级高,入栈;如果比栈顶优先级低或相等,出栈将其操作符存到exp数组中,直到栈顶元素优先等级低于扫描的操作符,则此操作符入栈;如果是左括号,直接入栈,如果是右括号,出栈存入exp数组,直到遇到左括号,左括号丢掉。然后继续扫描下一个字符,直到遇到str中的结束符号\0,扫描结束。结束后看op栈是否为空,若不为空,继续出栈存入exp数组中,直到栈为空。到此在exp数组最后加结束字符\0。 我们就得到了后缀表达式。 (2)后缀表达式计算 此时需要一个数值栈od来存放数值。对exp数组进行逐个扫描,当遇到数字或小数点时,截取数值子串将其转换成double类型的小数,存入od栈中。当遇到操作符,从栈中取出两个数,进行计算后再放入栈中。继续扫描,知道扫描结束,此时值栈中的数值就是计算的结果,取出返回计算结果。 2.两个栈实现算法 此算法需要两个栈,一个值栈od,一个操作符栈op。将用户输入的数学表达式存入str数组中,对其数组进行逐个扫描。 当遇到数字或小数点,截取数值子串,将其转换成double类型的数值存入od栈中; 当遇到左括号,直接入op栈;遇到右括号,op栈出栈,再从值栈od中取出两个数值,计算将其结果存入值栈中,一直进行此操作,直到操作符栈栈顶为左括号,将左括号丢掉。 如果遇到操作符,若op栈为空,直接入栈;若栈不为空,与栈顶元素比较优先等级,若比栈顶操作符优先等级高,直接入op栈,如果低于或等于栈顶优先等级,op栈出栈,再从值栈中取出两个数值,计算将其结果存入值栈中,一直进行此操作,直到栈顶优先等级低于扫描的操作符等级,将此操作符入op栈。继续扫描直到遇到str中的结束字符\0,扫描结束。此时看操作符栈是否为空,若不为空,出栈,再从值栈中取出两个数值进行计算,将其结果存入值栈,一直进行此操作,直到操作符栈为空。此时把值栈中的数值取出,即为所得的最终计算结果。 二、算法流程图 第一种算法:中缀转后缀算法
局部变量、全局变量、堆、堆栈、静态和全局【】 预备知识—程序的内存分配 一个由C/C++编译的程序占用的内存分为以下几个部分 ?栈区(stack)—由编译器自动分配释放,存放函数的参数值,局部变量的值等。 其操作方式类似于数据结构中的栈。 ?堆区(heap)—一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表。 ?全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量、未初始化的静态变量在相邻的另一块区域。- 程序结束后有系统释放 ?文字常量区—常量字符串就是放在这里的。程序结束后由系统释放 ?程序代码区—存放函数体的二进制代码。 一个正常的程序在内存中通常分为程序段、数据端、堆栈三部分。程序段里放着程序的机器码、只读数据,这个段通常是只读,对它的写操作是非法的。数据段放的是程序中的静态数据。动态数据则通过堆栈来存放。 在内存中,它们的位置如下: +------------------+ 内存低端 | 程序段| |------------------| | 数据段| |------------------| | 堆栈| +------------------+ 内存高端 堆栈是内存中的一个连续的块。一个叫堆栈指针的寄存器(SP)指向堆栈的栈顶。堆栈的底部是一个固定地址。堆栈有一个特点就是,后进先出。也就是说,后放入的数据第一个取出。它支持两个操作,PUSH和POP。PUSH是将数据放到栈的顶端,POP是将栈顶的数据取出。 在高级语言中,程序函数调用、函数中的临时变量都用到堆栈。为什么呢?因为在调
P I D控制算法的C语言 实现完整版 文件编码(008-TTIG-UTITD-GKBTT-PUUTI-WYTUI-8256)
P I D控制算法的C语言实现一P I D算法原理最近两天在考虑一般控制算法的C语言实现问题,发现网络上尚没有一套完整的比较体系的讲解。于是总结了几天,整理一套思路分享给大家。 在工业应用中PID及其衍生算法是应用最广泛的算法之一,是当之无愧的万能算法,如果能够熟练掌握PID算法的设计与实现过程,对于一般的研发人员来讲,应该是足够应对一般研发问题了,而难能可贵的是,在我所接触的控制算法当中,PID控制算法又是最简单,最能体现反馈思想的控制算法,可谓经典中的经典。经典的未必是复杂的,经典的东西常常是简单的,而且是最简单的,想想牛顿的力学三大定律吧,想想爱因斯坦的质能方程吧,何等的简单!简单的不是原始的,简单的也不是落后的,简单到了美的程度。先看看PID算法的一般形式: PID的流程简单到了不能再简单的程度,通过误差信号控制被控量,而控制器本身就是比例、积分、微分三个环节的加和。这里我们规定(在t 时刻): 1.输入量为rin(t); 2.输出量为rout(t); 3.偏差量为err(t)=rin(t)-rout(t); pid的控制规律为
理解一下这个公式,主要从下面几个问题着手,为了便于理解,把控制环境具体一下: 1.规定这个流程是用来为直流电机调速的; 2.输入量rin(t)为电机转速预定值; 3.输出量rout(t)为电机转速实际值; 4.执行器为直流电机; 5.传感器为光电码盘,假设码盘为10线; 6.直流电机采用PWM调速转速用单位转/min表示; 不难看出以下结论: 1.输入量rin(t)为电机转速预定值(转/min); 2. 输出量rout(t)为电机转速实际值(转/min); 3.偏差量为预定值和实际值之差(转/min); 那么以下几个问题需要弄清楚: 1.通过PID环节之后的U(t)是什么值呢 2.控制执行器(直流电机)转动转速应该为电压值(也就是PWM占空比)。
一、预备知识(程序的内存分配) 一个由C/C++编译的程序占用的内存分为以下几个部分: 1、栈区(stack):由编译器自动分配释放,存放函数的参数值,局部变量的值等。其操作方式类似于数据结构中的栈。 2、堆区(heap):一般由程序员分配释放,若程序员不释放,程序结束时可能由OS回收。注意它与数据结构中的堆是两回事,其分配方式倒是类似于链表。 3、全局区(静态区static):全局变量和静态变量的存储是放在一块的,初始化的全局变量和静态变量在一块区域,未初始化的全局变量和未初始化的静态变量在相邻的另一块区域。程序结束后有系统释放。 4、文字常量区:常量字符串就是放在这里的。程序结束后由系统释放。 5、程序代码区:存放函数体的二进制代码。 看看下面的例子程序,这是一个前辈写的,非常详细。 //main.cpp int a = 0; 全局初始化区 char *p1; 全局未初始化区 main() { int b; 栈 char s[] = "abc"; 栈 char *p2; 栈 char *p3 = "123456"; 123456\0在常量区,p3在栈上。 static int c =0;全局(静态)初始化区 p1 = (char *)malloc(10); p2 = (char *)malloc(20); 分配得来得10和20字节的区域就在堆区。 strcpy(p1, "123456"); 123456\0放在常量区,编译器可能会将它与p3所指向的"123456"优化成一个地方。 } 二、堆和栈的理论知识 2.1、申请方式 stack:由系统自动分配。例如:声明在函数中一个局部变量int b,系统自动在栈中为b开辟空间。heap:需要程序员自己申请,并指明大小,在c中用malloc函数,如p1 = (char *)malloc(10); 在C++中用new运算符:如p2 = (char *)malloc(10); 但是注意p1、p2本身是在栈中的。 2.2 、申请后系统的响应 stack:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报错提示栈溢出。heap:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表中删除,并将该结点的空间分配给程序。另外,对于大多数系统,会在这块内存空间中的首地址处记录本次分配的大小。这样,代码中的delete语句才能正确的释放本内存空间。另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部分重新放入空闲链表中。 2.3、申请大小的限制 stack:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意思是
用单片机控制直流电动机的正反转、加减速的程序如何用C语言写 参考一下这个例子吧。 #include
带括号的四则运算表达式的求值(栈实现) 利用栈这种数据结构来实现一个加减乘除以及带括弧的混合数学表达式的计算,对于数学表达式的计算,可以设置一个运算符栈和一个数字栈,分别来保存运算符、数字或者中间计算得到的结果。将整个表达式看做一个字符串,从开头依次判断每个字符是运算符还是数字,若是运算符,则根据运算符优先级来确定是将其压栈还是弹栈进行计算;若是数字,则先将其转化并计入一个临时double型变量中,看下一个字符是否为运算符栈,若是,则将临时变量压进数字栈,否则读取下一个数字字符并进行相关处理后累加到临时变量中,直到下一个字符为运算符,将临时变量压进数字栈。最后,当字符为"="时,结束计算,得到计算结果。本算法需要先设置一个运算符优先级表,下表可供参考: +-*/()= +>><<<>> ->><<<>> *>>>><>> />>>><>> (<<<<<= )>>>>?>> =<<<<= 参考代码如下: 注:本代码输入表达式时末尾不需要“=”,程序中会自动添加 #include #include #include #include #include using namespace std; char Precede(char a, char b) { { point = 10; else num = s[i] - 48; j = i + 1;
while(!IsOper(s[j])) { { point = 10; j++; continue; } if(!point)? 5 - 7 / 2 + 3. - .1 1 + 2 / ( 2 - / ) - 3 2 * ( ( 3 + 2 ) - 3 */ 本代码生成的程序,在输入表达式时,数字与运算符之间可以有若干空格或者没有;对于小数,可以没有整数部分(即小数点之前没有数字),也可以没有小数部分(即小数点之后没有数字);表达式可以为无效表达式(如括号不匹配或者出现除数为0的情况等);如以上的样例输入。对于以上样例输入,其对应输出结果为: The divisor cannot be zero! The parentheses do not match!
一、内存基本构成 可编程内存在基本上分为这样的几大部分:静态存储区、堆区和栈区。他们的功能不同,对他们使用方式也就不同。 静态存储区:内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。它主要存放静态数据、全局数据和常量。 栈区:在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中,效率很高,但是分配的内存容量有限。 堆区:亦称动态内存分配。程序在运行的时候用malloc或new申请任意大小的内存,程序员自己负责在适当的时候用free或delete释放内存。动态内存的生存期可以由我们决定,如果我们不释放内存,程序将在最后才释放掉动态内存。但是,良好的编程习惯是:如果某动态内存不再使用,需要将其释放掉,否则,我们认为发生了内存泄漏现象。 二、三者之间的区别 我们通过代码段来看看对这样的三部分内存需要怎样的操作和不同,以及应该注意怎样的地方。 例一:静态存储区与栈区 char* p = “Hello World1”; char a[] = “Hello World2”; p[2] = …A?; a[2] = …A?; char* p1 = “Hello World1;” 这个程序是有错误的,错误发生在p[2] = …A?这行代码处,为什么呢,是变量p和变量数组a都存在于栈区的(任何临时变量都是处于栈区的,包括在main()函数中定义的变量)。但是,数据“Hello World1”和数据“Hello World2”是存储于不同的区域的。 因为数据“Hello World2”存在于数组中,所以,此数据存储于栈区,对它修改是没有任何问题的。因为指针变量p仅仅能够存储某个存储空间的地址,数据“Hello World1”为字符串常量,所以存储在静态存储区。虽然通过p[2]可以访问到静态存储区中的第三个数据单元,即字符…l?所在的存储的单元。但是因为数据“Hello World1”为字符串常量,不可以改变,所以在程序运行时,会报告内存错误。并且,如果此时对p和p1输出的时候会发现p和p1
PID控制算法的C语言实现一PID算法原理 最近两天在考虑一般控制算法的C语言实现问题,发现网络上尚没有一套完整的比较体系的讲解。于是总结了几天,整理一套思路分享给大家。 在工业应用中PID及其衍生算法是应用最广泛的算法之一,是当之无愧的万能算法,如果能够熟练掌握PID算法的设计与实现过程,对于一般的研发人员来讲,应该是足够应对一般研发问题了,而难能可贵的是,在我所接触的控制算法当中,PID控制算法又是最简单,最能体现反馈思想的控制算法,可谓经典中的经典。经典的未必是复杂的,经典的东西常常是简单的,而且是最简单的,想想牛顿的力学三大定律吧,想想爱因斯坦的质能方程吧,何等的简单!简单的不是原始的,简单的也不是落后的,简单到了美的程度。先看看PID算法的一般形式: PID的流程简单到了不能再简单的程度,通过误差信号控制被控量,而控制器本身就是比例、积分、微分三个环节的加和。这里我们规定(在t时刻): 1.输入量为rin(t); 2.输出量为rout(t); 3.偏差量为err(t)=rin(t)-rout(t); pid的控制规律为
理解一下这个公式,主要从下面几个问题着手,为了便于理解,把控制环境具体一下: 1.规定这个流程是用来为直流电机调速的; 2.输入量rin(t)为电机转速预定值; 3.输出量rout(t)为电机转速实际值; 4.执行器为直流电机; 5.传感器为光电码盘,假设码盘为10线; 6.直流电机采用PWM调速转速用单位转/min表示; 不难看出以下结论: 1.输入量rin(t)为电机转速预定值(转/min); 2. 输出量rout(t)为电机转速实际值(转/min); 3.偏差量为预定值和实际值之差(转/min); 那么以下几个问题需要弄清楚: 1.通过PID环节之后的U(t)是什么值呢 2.控制执行器(直流电机)转动转速应该为电压值(也就是PWM占空比)。 3.那么U(t)与PWM之间存在怎样的联系呢
水仙花 #include
的排列后再去掉不满足条件的排列。 2.程序源代码: #include "stdio.h" #include "conio.h" main() { int i,j,k; printf("\n"); for(i=1;i<5;i++) /*以下为三重循环*/ for(j=1;j<5;j++) for (k=1;k<5;k++) { if (i!=k&&i!=j&&j!=k) /*确保i、j、k三位互不相同*/ printf("%d,%d,%d\n",i,j,k); } getch(); } 【程序2】 题目:企业发放的奖金根据利润提成。利润(I)低于或等于10万元时,奖金可提10%;利润高于10万元,低于20万元时,低于10万元的部分按1 0%提成,高于10万元的部分,可可提成7.5%;20万到40万之间时,高于20万元的部分,可提成5%;40万到60万之间时高于40万元的部分,可提成3%;60万到100万之间时,高于60万元的部分,可提成1.5%,高于100万元时,超过100万元的部分按1%提成,从键盘输入当月利润I,求应发放奖金总数? 1.程序分析:请利用数轴来分界,定位。注意定义时需把奖金定义成长整型。 2.程序源代码:
详解堆栈的几种实现方法 基本的抽象数据类型(ADT)是编写C程序必要的过程,这类ADT有链表、堆栈、队列和树等,本文主要讲解下堆栈的几种实现方法以及他们的优缺点。 堆栈(stack)的显著特点是后进先出(Last-In First-Out, LIFO),其实现的方法有三种可选方案:静态数组、动态分配的数组、动态分配的链式结构。 静态数组:特点是要求结构的长度固定,而且长度在编译时候就得确定。其优点是结构简单,实现起来方便而不容易出错。而缺点就是不够灵活以及固定长度不容易控制,适用于知道明确长度的场合。 动态数组:特点是长度可以在运行时候才确定以及可以更改原来数组的长度。优点是灵活,缺点是由此会增加程序的复杂性。 链式结构:特点是无长度上线,需要的时候再申请分配内存空间,可最大程度上实现灵活性。缺点是链式结构的链接字段需要消耗一定的内存,在链式结构中访问一个特定元素的效率不如数组。 首先先确定一个堆栈接口的头文件,里面包含了各个方案下的函数原型,放在一起是为了实现程序的模块化以及便于修改。然后再接着分别介绍各个方案的具体实施方法。 堆栈接口stack.h文件代码: [cpp] view plain copy 1 /*** 堆栈模块的接口 stack.h #include