当前位置:首页 >> 学科竞赛 >>

C程序设计语言基础


C程序设计语言
清镇市第一中学汪思言 2012年

第一章 类型、运算符与表达式

类型与变量、常量
? 类型的作用:类型规定了信息在计算机中的存储空间和方 式,以及这些信息所够进行的运算。 ? C语言的基本数据类型有:
– – – – 整数:int, long; 实数:float, double; 字符:

char 空: void

? 关键字:关键字是C语言组成的一部分,包括数据类型和 流程控制以及变量修饰的单词,如int, if/else, while...等 等。

类型的存储空间和值范围
类型
char unsigned char short(或short int) unsigned short(或unsigned short int) int unsigned int

名称
字符 无符号字符 短整型 无符号短整型 整型 无符号整型

存储占用空间
1字节 同上 2字节 2字节 2或4字节 同上

值范围
-128 至 127 0至255 -32768至32767 0至65535 16位机: -32768至32767 32位机: -2147483648至2147483647 16位机:0至65535 32位机:0至4294967295

long(或long int)
usigned long float double

长整型
无符号长整型 单精度实数 双精度实数

同int
同无符号整型 4字节 8字节

同int
同无符号整型 1.17549x10-38至3.40282x1038,小数点后 6位数字精度 2.22507x10-308至1.79769x10308,小数点 后15位数字精度

变量
变量:变量是内存地址的名称,用来方便我们在计算 过程中存储相应的数据信息。变量在使用前必须先定 义!
int a;

内存中某处的一个位置,我们把 这个位置称为a;

变量的定义

定义方式: ? 变量的定义位置在其他非定义语句之前。 ? 定义的格式:
(1) 定义一个变量: 类型名 变量名; (2) 一次定义多个变量:

注意: (1)变量名只能由大小写字母,数字和下 划线“_”组成,且不能以数字开头。 (2)定义完成后以分号结束。

类型名 变量名1, 变量名2, ... ,变量名n;
(3) 带初始化的变量定义:

类型名 变量名1=初值, 变量2=初值;

定义示范:
1.定义一个整数变量a: int a; 1.定义一个实数b, c, d: float b, c, d;
非法的变量名: 3a: 不能以数字开头 a 2:不能含有空格 $a: 只能由字母、数字或下 划线组成 int: 名称和关键字(类型名) 相同。

合法的变量名: a1,a2,num _flag

常量
? 概念:在运行过程中不会改变值的量。 ? 分类:
– 字面常量:如1.5, 3.14, 'a', "good~~~"等; – 符号常量:在变量的定义前使用const修饰符, 可以将一个量声明为常量。 如:const int pi=3.1415926; pi在整个过程中就成为一个常量,不能修改其 值,比如“pi=6.28”的语句就是非法的,无 效的。

表达式
? ? ? ? ? 赋值变达式 运算表达式 关系表达式 逻辑表达式 注释

赋表表达式
格式: 变量名 = 值 或 表达式; 例: a = 3.14; c = (a + b) * (a - b); d = sin(3.14);

运算表达式
? 前面的例子“c=(a + b) * (a - b) ”和 “a=sin(3.14) ”中等号“=”右边的部分 就是一个运算表达式。

? 本质:运算表达式的本质是可以含有函数 计算的四则混合运算表达式。 ? 优先级:() > *,/,% > +,-

关系表达式:
? 关系表达式的结果只有两种:1和0,分别代表 “真”和“假”。 ? 关系表达式就是指关系运算,有如下几种:
等于 小于 小于或等于
设:a=1, b=2,则有:

== < <= 0 1

不等于 大于 大于或等于 a != b a>b

!= > >= 1 0

a == b a<b

a <= b

1

a>=b

0

逻辑表达式
? 逻辑表达式与我们日常生活中的“并且”,“或者”、 “不是”等类似。
生活用语 并且 或者 不是 设有a=1, b=2, c=3 a>b && a<c !(a <b) a>b && a<c || b<c 0 0 1 a>b || a<c !(a > b) a>b || b>c && b<c 1 1 0 逻辑用语 与 或 非 运算符号 && || !

优先级:非 > 与 > 或

特殊的分号“;”
? 西文分号在C语言中有特殊作用,它表示一 个表达式的结束。在C语言中,不同语句之 前是通过“;”来分隔的,比如定义几个变 量:
int a, b, c, d;

上述语句的结束位置是变量d后面的“;”, 这也 意味着有些情况一下一行写不完某些语句的时 候可以换到下一行去接着写。

注释
? 注释的作用:注释是用来给程序员编写代 码时便于理解代码而编写的内容,它本不 是代码的组成部分,在编译过程中,编译 器将完全忽略掉它的存在。 ? 注释的格式:C语言支持两种格式的注释
– 单行注释:// 注释内容 – 多行注释:/* 注释内容 */

注释示例
int time_t flag; // 查找标志 now = time(0); /* 获取当前时间 */

/** 函数: add * 功能:计算两个数的和 * 参数:a,b为整数 */ int add(int a, int

b) { ... }

注意:注释不能嵌套! 类似/* /*...*/ */的注释是不允许的。

第二章 控制流

控制流的作用
? 使得在条件满足的情 况下做某些事情。 ? 各控制语句的含义:
语句 if else while 含义 如果(条件成立)则…… 否则(须结合if使用) 当条件成立时重复执行 格式 if ( 条件 ) { ... } if( 条件 ) { ...} else { ... } while( 条件 ) { ... }

do...while

执行后检查条件,如果条件 成立,则返回重复执行。
如果条件成立,则重复执行

do { ... } while(条件);
for(变量=初值; 条件; 变量增减) { ... }

for

1. 分支结构if / else
? 格式: if(条件) { ... } else { ... }

? 示例1:
int a=1, b=2; if (a < b) { printf("a小于b"); } else { printf("a大于b"); }

以上程序将输出结果: a小于b

1. 分支结构 if/else
? 复合语句:
int a=1, b=2; if (a > b) { printf("a是最大值"); printf("a=%d", a); } else { printf("b是最大值"); }
左边程序将输出: b是最大值 左边 “{ printf("a是最大值"); printf("a=%d", a); }”称为复合语句,表示如果 a>b成立的情况下,这两条语 句都会被执行。

1. 分支结构if/else
? if/else的另一种形式:
if(条件) { ... } else if(条件2) { ... } else { ... }
? 示例:
int a=5,b=4,c=3; if(a<b) { printf("a<b"); } else if(a<c) { printf("a<c"); } else { printf("a是最大值!"); }

上面的程序将输出: a是最大值

2. 循环结构
? 循环的意义:即重复执行 ? 循环结构有三种: ? for/while/do..while

2.1. while循环
while(条件) { ... } 表示在条件成立的情况下,“{}” 中的语句将被重复执行,每 执行一次后又会检查一次条 件,如果成立则反复执行, 直到条件不成立为止。 上述程序的输出结果如下:
0,10,20,30,40,50,60,70,80,90, 语句“i % 10 == 0”的意思为如果i除 以10的余数为0。

? 示例:
int i = 0; while(i < 100) { if(i % 10 == 0) printf("%d,", i); i = i + 1; }

2.2 for循环
? for循环可以看作一个简化 了的while循环. ? 格式:
for(初始化;条件;变量迭代) { ... } 同样,for循环将先检测“条件” 是否成立,然后执行重复执行, 直到“条件”不成立为止。

? 示例:如前面的代码可以 改写成:
int i; for(i=0; i<100; i++) { if (i%10 == 0) printf("%d,", i); }

上述代码的输出同前一页 while循环的输出。

2.3 do...while循环
? 特点:先执行,后检 ? 示例:
int i=10; do { printf("%d,", i); i = i - 1; } while (i > 0);

查条件.

? 格式: do { ... } while(条件);

上述代码将输出: 10,9,8,7,6,5,4,3,2,1,

第三章 函数

函数的作用:
1.概念:可以重复使用的一个功能代码块。 2.作用
1.可将较大的任务分解成较小的任务,便于问的 解决,即1+1<2的原理。 2.将常用的代码提取出来成为函数,可以提高编 程的效率。

示例:
? 还记得我们数里常说的函数吗,C语言中的函数很多时候 和数学的函数一样,用来根据输入的参数返回计算的结果, 比如大家常用的正余弦函数:sin/cos ? C语言中也有sin和cos,它们的使用方式是这样的:
double x = 3.14; double y1 = sin(x), y2=cos(3.14);

其作用就如同数学公式y=sinx一样,分别把x的正余弦计算结果 分别放到了y1和y2这两个变量里。

函数的使用方法
? 第一步:定义函数——告诉编译器是如何 具体实现其计算功能的。 ? 第二步:调用函数——使用函数来解决我 们的计算问题。

函数的定义的方法:
? 无参数函数声明(函数不需要参数): 返回值类型 函数名() { ... } 如:int is_good() { ... } ? 有参数函数声明: 返回值类型 函数名(参数列表); 如(计算两个数相加): int add(int a, int b) { return a+b; }

无计算结果的函数:
? 有时候,有些函数没有计算结果,比如打 印内容的printf函数,这种函数的声明需要 一种特别的类型void,以表明该函数没有 计算结果。 ? 如:void close() { ... }

函数的声明和定义的方法:
? 函数的定义:
返回值类型 函数名(参数列表) { // 处理代码... return 返回值; }

? 例1: void say_hello() { printf("hello\n"); } ? 例2: int add(int a, int b) { return a + b; }

函数的返回值问题:
? 函数在计算过程中使用“return 表达式;” 来返回其计算结果。比如,对于一个求解 两个整数的和的函数“add”,其实现如下:
int add(int a, int return a + b; } 在main函数中使用如下代码: int y = add(5, 10); 则y的值为15。 return语句除了返回一个值外,也意味着这个函数的执行的终结,函数里的其 他代码将不会再被执行! b) {

函数的返回值问题:
? 在无返回值的函数里,使用“return;”语句将直接导致 函数执行的终结。
void print_weekday(int d) { if( d==6 || d==7) { printf("休息日\n"); return; } printf("星期%d", d); } 当传入的参数等于6或者7时,函数将从“return;”处返回, “printf("星期%d", d);”这一条语句将不会被执行。

函数的调用:
? 1、无参调用: ? int a = rand(); // 产生一个随机数 ? 2、有参调用: ? 例1:double y = sin(3.14); ? 例2:printf("%d\t%d\t%d", 10, 20, 30);

形参与实参问题
? 在函数定义时,我们提供的参数名称为形式参数,简称形 参。形参是一个抽象的概念,可以看作是一个值尚未确定 的变量(因为在对函数调用之前,它的值是无法确定的), 再对函数进行调用时,所使用的具体值或变量称为实际参 数,简称实参。 ? 例如函数:
? int add(int a, int b) { return a+b; }

? 此时的a和b称为形式参数,其值现在是不能确定的,只有 当我们使用“int y=add(x, 10);”这样的语句的时候,a 和b的实际值才能确定下来,这个时候的x和10是实际参 数。

变量的作用域问题
? 在同一函数内同级的代码块间是不能定义名字相 同的变量的,因为这会因为歧义。如:
int a=10, b=9; char a='X'; printf("a=%d", a);

? 编译器将不知道该出的是10还是'X'。 ? 不同的函数间可以定义相同名称的变量不会引起 冲突,因为对于每个变量来说,其可见范围限定 在了定义它的这个函数中。这就好比不同城市间 可以有相同的电话号码,它们可以通过区号区分 一样。

示例:
int add(int a, int b) { int c = a + b; return c; } int sub(int a, int b) { int c = a - b; return c; }
void print_num() { printf("%d", c); }

左边的函数里共有两个a,b,c,它 们属于不同的函数范围,因此不 会发生冲突。
▲而最下方的函数print_num是一 个错误的函数,因为变量c在 print_num的范围内没有定义, 前面两个函数里边的变量c对 print_num函数来说是不可见 的。

特殊的函数main
? 在所有函数中main是一个特殊的函数,因 为它确定了程序从何处开始执行。C语言中 程序都是从main开始执行的。 ? 其名称必须为小写的main,而且通常C语 言中main必须是int的返回类型,一个程序 正常结束时,应该使用"return 0;"表示程 序被成功地执行。

main函数的几种格式
main() { ... }

int main() { ... return 0; }

int main(int argc, ... return 0; }

char *argv[]) {

全局变量的作用域问题:
? 变量根据定义变量的位置,可 以分为全局变量和局部变量。 ? 在所有函数之外定义的变量, 称为全局变量,函数内定义的 变量为局部变量。全局变量对 于所有函数都是可见的。 ? 如右边代码中g为全局变量。 ? 注意:太多的全局变量可能会 引起混乱,所以:尽量不要使 用全局变量!
? 例1-全局变量:文件"1.c"

#include <stdio.h> int g = 0; int add(int a, int b) { int c = a + b; return c; } void inc_g() { g++; } main() { int a=10, b=5; g = add(a + b); printf("%d", g); inc_g(); printf("%d", g); getchar(); }

第4章 数组与指针

数组的作用
? 用来存放一组同一类型的元素,如10个人 的性别,20个人的成绩等。

数组的定义
? 基本定义: ? 类型名 变量名[长度];
– 如: int a[10];

? 初始化:
类型名 变量名[长度]={值列表}; – 如:
int int a[3] = {1, 2, 3}; b[] = {1, 2, 3, 4, 5};

– 注意:长度必须是常量,对于整形的数组,如果初始化列表中的 元素个数少于数组长度的时候,其他值将默认以0填充。

数组元素的访问
? C语言中数组元素的下标从0开始计数,如 果一个数组a有10个元素,则其第1个元素 的下标为0, 第10元素为9; ? 存取方式为:数组名[下标] ? 例:
int a[]={1, 2, 3}; a[0]=10; // 将第1个元素修改为10 printf("%d", a[0]);

示例:数组元素的迭代访问:
#include <stdio.h> main() { int a[] = {1,2,3,4,5}; int i, s = 0; for(i=0; i<5; ++i) { printf("数组a的第%d个元素:%d\n", i, } for(i=0; i<5; ++i) { s += a[i]; } printf("数组a的和为:%d", s); getchar(); }

a[i]);

数组和字符串
? 字符串是一个特殊的数组,主要在定义的 初始化方面:
char s[] = "abcdefg"; char s[] = {'a', 'b', 'c', 'd', 'e', 'f', 'e', '\0'};

C语言中,字符串以'\0'(ASCII值为0)作为 安符串的结束。以上两个数组是完全等价 的。因为可以按照访问数组元素的方法访 问字符中的每一个字符。

指针

指针
? 概念:指针是在内存中的一个偏移地址, 它提供一种间接访问内容的方法。 ? 作用:
– – – – 指针为函数提供了修改参数的手段; 支持动态分配子程序; 可改善程序执行的效率; 为动态数据结构提供了支持。

指针的定义
? 定义: 1、类型名 *变量名; 2、类型名 *变量名=地址;
示例:
int a; int *p1; int *p2 = &a;

上述代码中p1的值未定,而p2的值则被赋予了变量a在 内存中的偏移地址。

指针的使用
? 使用: 指针操作需要两个操作符:&和* &操作符用于取得变量的在内存中的偏移地址; *操作符用来取得指针值所指偏移内存中的值。 ? 例:
int a = 10; int *p = &a; *p = 25;

上述代码中“*p=25;”这句代码将a的值修改成了25。

指针与函数:
? 值传递和引用传递
– 值传递:传递变量的值而非 变量本身地地址。 – 引用传递:通过将变量的地 址而非值传入函数,提供了 在函数中修必这个变量的值 的可能。 右边的程序将输出: a=10 a=10 a=-1
#include <stdio.h> void f(int a) { a = -1; } void g(int *a) { *a = -1; } main() { int a = 10; printf("a=%d\n", a); f(a); printf("a=%d\n", a); g(&a); printf("a=%d\n", a); }

数组与指针的关系
? 数组名本身即是一个指针: ? 比如一个字符串:
char s[] = "abcdefg"; char *p = s;

? p的值将为s在内存中的偏移地址。 ? 以上面代码为基础,下列地址是等价的:
&a[1], s+1, p+1

? 下列值是等价的:
a[1], *(s+1), *(p+1)

特殊的指针值:0
? 通常,在定义一个指针时,我们会将其初 值赋为0,代指该指针不指向内存中任何区 域,即我们所说的空指针。如下: int *p = 0; ? 有些时候,我们会看友NULL这个值,它是 用#define宏命令定义的一个宏,其值为0。 所以,下面的代码和上面是效能上等价的: int *p = NULL;

第5章 数据结构 ? 数据结构的两种基本形式: ? 线性(顺序)存储 ? 非线性(链式)存储

线性存储 ? 数据在内存中是连续的内存单元的存储的,比 如数组: ? int a[6] = {10,15,21,3,16,9};
10 15 21 3 16 9

非线性存储

? 非线性(链式)存储中,数据的存放不是连续 的,而是一种链式的存储结构,前一元素和后 一元素之间通过指针建立关联。 ? 例如对于具有同样元素的集合: ? S = {10,15,21,3,16,9};

10

15

21

3

9

null

16

实现非线性存储的基础:自定义数据类型

? struct数据类型。 ? struct用于将已有的数据类型组合在一起,形成 一种新的数据类型。 ? 比如对于一个用于描述学生姓名、年龄、性 别、班级等四项基本信息的数据类型,其抽象 结构如下:
学生 { 姓名, 年龄, 性别, 班级 };

struct的定义和使用

? 如前所述学生信息的数据类型用struct定义如下: struct STUDENT { char name[20]; int age; char sex[5]; int class_no; };
定义的基本方式: struct 自定义类型名 { 类型 成员变量名; 类型 成员变量名; …… 类型 成员变量名; };

struct的使用

main() { struct STUDENT s1; printf("录入学生信息:\n"); printf("姓名:"); scanf("%s", s1.name); printf("年龄:"); scanf("%d", &s1.age); printf("性别:"); scanf("%s", s1.sex); printf("班级:"); scanf("%d", &s1.class_no); printf("学生信息如下:"); printf("%s\t%d\t%s\t%d",s1.name, s1.age, s1.sex, s1.class_no); }

typedef语句的使用:
? typedef的作用是用来定义别名,比如 typedef int zs;
则zs成了int的别名,当我们使用 如下代码时: zs a, b; 就相当于使用int 类型定义了两个变量a和b,它和下面的语句是等价的: int a, b;

?

从前面的代码中我们观察到,凡是使用了struct自定义类型的地方,其定 义的时候,要是在自定义名称前面加上struct这个关键词,这并令人快 乐。幸好,我们有办法解决这一问题,那就是使用typedef语句,如前面的 STUDENT这一数据类型可以修改成如下定义: typdef struct _STUDENT {
char name[20]; int age; char sex[5]; int class_no; } STUDENT; 以后在程序的其他地方,我们就可以使用STUDENT而无需在前面加上struct关键字了。因为 STUDENT 就是类型struct _STUDENT的别名。

链表
?链表的分类: 1、根据链表的节点间的相互 关系,可将链表分为以下几 种:
– – – – 单向链表(单链表); 双向链表(双链表) 单向循环链表(单循环链表) 双向循环链表(双循环链表)

链表不是一种随机存取的数据 结构。

2、链表的建立需要依赖两个函数:
– void *malloc(size_t size); – void free(void *p);

? 其中malloc函数用于申请一个大小为size个字节 的内存空间。 ? free的作用是在不用时将已分配的内存空间释 放。
3、带头结点和不带头结点 4、链表的主要操作:
– 链表的建立 – 插入新结点 – 删除结点

单向链表的使用

1.链表节点的定义:
typedef struct _LISTNODE { int value; struct _LISTNODE *next; } LISTNODE; 链表结点由数据成员value和记录下一结点地址的指针next组成。

2. 创建链表
LISTNODE *create_list() { LISTNODE *head = malloc(sizeof(LISTNODE)); head->value = 0; head->next = NULL; return head; }

上述函数使用了一个malloc函数,这个函数用来向请操作 系统申请一段内存空间,它需要一个参数size用来指定申 请的空间大小。上述程序中,我们使用了 sizeof(LISTNODE)来指定一个可以存放一个LISTNODE节 点的空间。

3.插入元素
void list_add(LISTNODE *head, int value) { LISTNODE *p = head; LISTNODE *q = p->next; while(q) { p = q; q = q->next; } q = malloc(sizeof(LISTNODE)); q->value = value; q->next = NULL; p->next = q; }

4.删除元素 void list_delete(LISTNODE *head, int value) { LISTNODE *p = head; LISTNODE *q = p->next;
while(q) { if (q->value == value) { p->next = q->next; free(q); break; } p = q; q = q->next; } }

5、销毁链表 void destroy_list(LISTNODE *head) { LISTNODE *p = head, *q; while(p) { q = p->next; free(p); p = q; } } 6、打印链表 void print_list(LISTNODE *head) { LISTNODE *p = head->next; while(p) { printf("%d", p->value); p = p->next; if(p) printf(","); } }

不同数据结构的适用范围

? 线性存储用在数据元素个数固定的情况; ? 链式存储用在数据元素不定,需要根据实际需 要动态增长的情况。链式存储也是实现其他抽 象数据类型的基础手段。

第6章 文件操作

? 文件的基本操作:
– 打开和关闭文件 – 读/写文件

? ? ? ? ?

打开文件:fopen函数 关闭文件:fclose函数 读函数:fread/fgetc/fgets函数 写函数: fwrite/fputs/fputc/fprintf 读写相关函数:ftell/fseek/feof

1.文件写打开
? 以二进制写方式打开和程序同目录的―test1.dat‖文件,并向其写入 0-100(不包含100)之间的自然数:
#include <stdio.h> main() { int i=0; FILE *fp; if ((fp = fopen("test1.dat", "wb")) == NULL) { printf("打开文件失败!\n"); return; } for(i=0;i<100;i++) fwrite(&i, sizeof(i), 1, fp); fclose(fp); }

fopen的打开方式:

? ? ? ? ? ? ? ? ? ? ? ?

"r" 打开一个用于读取的文本文件 "w" 创建一个用于写入的文本文件 "a" 附加到一个文本文件 "rb" 打开一个用于读取的二进制文件 "wb" 创建一个用于写入的二进制文件 "ab" 附加到一个二进制文件 "r+" 打开一个用于读/写的文本文件 "w+" 创建一个用于读/写的文本文件 "a+" 打开一个用于读/写的文本文件 "rb+" 打开一个用于读/写的二进制文件 "wb+" 创建一个用于读/写的二进制文件 "ab+" 打开一个用于读/写的二进制文件

文件的读示例:
? 将前述例子中test1.dat中的数据读取并显示出来:
#include <stdio.h> main() { int i=0; FILE *fp; if ((fp = fopen("test1.dat", "rb")) == NULL) { printf("打开文件失败!\n"); return; } // 循环读直到文件末尾 while(!feof(fp)) { fread(&i, sizeof(int), 1, fp); printf("%d\t", i); } fclose(fp); }

第八章 简单抽象数据类型

? 第一节 栈(Stack) ? 第二节 队列(Queue)

8.1 栈

? 特性:栈是一种只能在一端进行数据存取的数据结 构。其基本的特点是后进先出(LIFO)或者先进后出 (FILO),即,最后进入栈的元素可以最先出栈,任 何时刻,只能对栈底的元素进行存取。
? 栈的基本操作: ?创建(create):创建一 个栈,并初始化; ?入栈(push):把元素放 入栈中(最顶处); ?出栈(pop):取出并从 栈顶删除元素; ?检查栈是否为空(empty)

栈顶 指针 e3 e2 e1 e0

8.1.1 线性栈

? 栈的实现:栈的实现可以采用线性存储或是链式存 储来实现。 ? 线性存储实现方式(下列代码位于array_stack.h 中):
#define STACK_CAPACITY 1024

typedef struct _STACK { int top; int datas[STACK_CAPACITY]; } STACK;

8.1.1 线性栈

? 创建栈(array_stack.h):
STACK * create_stack() { STACK *s = (STACK*)malloc(sizeof(STACK)); s->top = 0; return s; }

? 入栈(array_stack.h):
int stack_push(STACK *s, int data) { if (!s || s->top == STACK_CAPACITY) return 0; s->datas[s->top] = data; s->top++;
return 1; }

8.1.1 线性栈

? 出栈(array_stack.h):
int stack_pop(STACK *s, int *data_ptr) { if (!s || s->top == 0) return 0; s->top--; // 传入的data_ptr为空时抛弃栈顶元素 if(data_ptr) *data_ptr = s->datas[s->top];

return 1;
}

? 检查栈是否为空(array_stack.h):
int stack_empty(STACK *s) { return !s || s->top == 0; }

8.1.1 线性栈
? 栈的应用实例1:将数转换成二进制表示并输出。 #include <stdio.h> #include "array_stack.h" int main() { int n, r; STACK *s=create_stack();
scanf("%d", &n); do { r = n % 2; // 取余压栈,个位最后输出(先进后出) stack_push(s, r); n /= 2; } while(n);

while(!stack_empty(s)) { stack_pop(s, &r); printf("%d", r); }
}

8.1.2 链栈

? 链栈:链栈使用链表这一非线性结构进行存 储。和线性栈比,链栈的定义退化为只有一个 栈顶指针,而没有了预分机的栈存储空间。
? 定义(list_stack.h):
// 栈元素表结点 typedef struct _STACK_NODE { int val; struct _STACK_NODE *next; } STACK_NODE;

// 栈 typedef struct _STACK { struct _STACK_NODE *top; } STACK;

8.1.2 链栈

? 创建栈(list_stack.h):
STACK *create_stack() { STACK *s = (STACK*) malloc(sizeof(STACK)); s->top = NULL; return s; }

? 入栈(list_stack.h):
int stack_push(STACK *s, int data) { STACK_NODE *p = (STACK_NODE*) malloc(sizeof(STACK_NODE)); if (s==NULL || p==NULL) return 0; p->val = data; p->next = s->top; s->top = p; return 1; }

8.1.2 链栈
? 出栈(list_stack.h):
int stack_pop(STACK *s, int *data) { STACK_NODE *p = s->top; if (s==NULL || p==NULL) return 0; *data = p->val; s->top = p->next; free(p);

return 1;
}

? 检查栈是否为空(list_stack.h):
int stack_empty(STACK *s) { return s==NULL || s->top==NULL; }

8.1.2 链栈

? 销毁栈(list_stack.h):
void destroy_stack(STACK *s) { STACK_NODE *p, *q; if(s==NULL) return; p = s->top; while(p) { q = p->next; free(p); p = q; } free(s); }

8.1.2 链栈
? 栈的应用实例2:简单的1位数加法计算器。
1位数加法计算器.c #include <stdio.h> #include <ctype.h> #include "list_stack.h" int calc(int l, int r, char op) { int rslt = 0; switch(op) { case '+': rslt = l + r; break; case '-': rslt = l - r; break; } return rslt; }

8.1.2 链栈
main() { STACK *snum, *sop; char expr[100], *p; int rslt, l, op;
snum = create_stack(); sop = create_stack(); printf("请输入一个一位加(减)法表达式(不含有括号)\n>"); gets(expr); p = expr; while(*p != '\0') { if (isspace(*p)) { p++; continue; }

8.1.2 链栈
if (isdigit(*p)) { if (!stack_empty(snum) && !stack_empty(sop)) { stack_pop(snum, &l); stack_pop(sop, &op); stack_push(snum, calc(l, *p-'0', op)); } else stack_push(snum, *p-'0'); } else { if(*p == '+' || *p == '-') { stack_push(sop, *p); } else { printf("无效字符!程序将终止!\n"); break; } } p++; } if (!stack_empty(sop)) { printf("无效表达式!\n"); } else { stack_pop(snum, &rslt); printf("计算结果:%d\n", rslt); } destroy_stack(snum); destroy_stack(sop); }

8.2 队列

? 队列:队列是一种可在结构的两端进行存取操 作的数据结构,其基本特点是先进先出 (FIFO)。入队在称为队尾(tail)的地方进行, 出队在称为队首(head)的地方进行。

? 生活中不乏队列的例子:如银行存取款排队、 坐公交车排队等。
e0 队首 e1 e2 e3 队尾

8.2 队列

? 队列的基本操作:
– – – – – 创建(create_queue):创建一个队列; 入队(enqueue):将一个元素加入队列中; 出队(dequeue):从队列中取出一个元素进行处理; 检查是否为空(queue_empty) 销毁(destroy_queue):销毁队列

? 队列的实现:同栈一样,队列仍然可以使用线 性结构和链式结构实现其存储。但由于线性结 构的不便于队员位置的移动,实现代价过高, 故一般队列使用链式的非线性结构实现更为高 效。

8.2 队列

? 链式实现:list_queue.h
// 队节点 typedef struct _QUEUE_NODE { int val; struct _QUEUE_NODE *next; } QUEUE_NODE;

// 链队由一个队列头指针和尾指针组成 typedef struct _QUEUE { QUEUE_NODE *head; QUEUE_NODE *tail; } QUEUE;

8.2 队列
// 创建队列 QUEUE * create_queue() { QUEUE *q = (QUEUE *)malloc(sizeof(QUEUE)); q->head = q->tail = NULL; return q; } //入队 int enqueue(QUEUE *q, int data) { QUEUE_NODE *pnode = (QUEUE_NODE *) malloc(sizeof(QUEUE_NODE)); if (q==NULL || pnode==NULL) return 0; pnode->val = data; pnode->next = NULL; if (q->tail == NULL) { q->head = q->tail = pnode; } else { q->tail->next = pnode; q->tail = pnode; } return 1;

}

8.2 队列
// 销毁队 void destroy_queue(QUEUE *q) { QUEUE_NODE *p = q->head, *r; while(p) { r = p->next; free(p); p = r; } free(q); }

8.2 队列
// 出队 int dequeue(QUEUE *q, int *data_ptr) { QUEUE_NODE *pnode; if (q==NULL || q->head == NULL) return 0; if(data_ptr) *data_ptr = q->head->val; pnode = q->head->next; free(q->head); if (pnode == NULL) { q->head = q->tail = NULL; } else { q->head = pnode; } return 1; } // 检查队是否为空 int queue_empty(QUEUE *q) { return q==NULL || q->head == NULL; }

8.2 队列
队列的应用:模拟银行取款叫号
#include <stdio.h> #include <stdlib.h> #include "list_queue.h" main() { char buffer[100]; QUEUE *q; int id, id2; q = create_queue(); id = 0; for(;;) { printf("=========银行叫号程序 =========\n" "a:存/取款等个人业务(客户) \n" "b:处理存/取款业务 \n" "c:退出程序 \n" ">");

else if(buffer[0] == 'b') { if (queue_empty(q)) { printf("\n\n没有等待的客户\n\n"); } else { dequeue(q, &id2); printf("\n\n请%d号顾客到柜台办理业务\n\n", id2); } } else if (buffer[0] == 'c') { break; } else { printf("\n\n不能识别的指令\n\n"); } }

gets(buffer); strlwr(buffer); if (buffer[0] == 'a') { id++; enqueue(q, id); printf("\n\n你的排队号码为:%d\n\n", id); }

destroy_queue(q); return 0;
}

第九章

? 练习
– – – – 练习1:回形取数问题 练习2:删数字问题 练习3:产生N个不重复的随机数 练习4:随机抽取N个的人的问题

9.1 回形取数问题

?文件numbers.in有若干行,每一行为一个2位十 进制数,形如下面: 12 34 56 78
现要求:编写程序从文件读取这些数,并按照回 形输出这些数字,如上面的文件应输出: 1 3 5 7 8 6 4 2

9.1 回形取数

? 算法分析: 分析前面的示例数据可以得出,每行中的 数的十位显示顺序同我们读取的行顺序是一致 的,是一种先读先出的结构,而个位则相反, 则是先读后出的一种结构。因此,可在读行的 过程中将十位入队,个位入栈,最后出队出栈 即可。 通过归纳,上问题主要考察我们对于栈和 队列的理解和应用。
? 考察点:栈和队列的基本特性和应用

9.1 回形取数
#include <stdio.h> #include "list_queue.h" #include "list_stack.h" int main() { FILE *fp; char buffer[10]; QUEUE *q = create_queue(); STACK *s = create_stack(); int data; if ((fp = fopen("numbers.out", "r")) == NULL) { printf("open file failed!\n"); return 0; } while(!feof(fp)) { if (fgets(buffer, sizeof(buffer)-1, fp)) { printf("%s", buffer); enqueue(q, buffer[0]); stack_push(s, buffer[1]); } } } fclose(fp); printf("\n\nresult:\n"); while(!queue_empty(q)) { dequeue(q, &data); printf("%c ", data); } while(!stack_empty(s)) { stack_pop(s, &data); printf("%c ", data); }

destroy_stack(s); destroy_queue(q); return 0;

谢谢观赏

WPS Office
Make Presentation much more fun
@WPS官方微博 @kingsoftwps


相关文章:
初学C语言程序设计的基本方法和技巧(强烈推荐)
初学C语言程序设计基本方法和技巧(强烈推荐)_工学_高等教育_教育专区。初学C语言程序设计基本方法和技巧(强烈推荐)无论哪所大学的计算机专科和本科都需要学习 C...
C语言程序设计基础知识要点
01.C 程序基本结构一、C 语言的特点: 1、C 语言源程序基本组成单位是函数;一个 C 程序可由若干个函数组成,其中必须有且仅有一个以 main 命名的主 函数,...
C语言程序设计基础_复习资料一
C语言程序设计基础_复习资料一_IT认证_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档 C语言程序设计基础_复习资料一_IT认证_资格考试/认证_教育...
程序设计基础教程(c语言版)课后答案
程序设计基础教程(c语言版)课后答案_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 程序设计基础教程(c语言版)课后答案_理学_高等教育_教育专区。...
C语言 程序设计基础试题一及答案
C语言 程序设计基础试题一及答案_工学_高等教育_教育专区。程序设计基础——C语言,计算机二级期末考试看这几套试题一定有帮助,而且后边还附有答案。《...
c语言《程序设计基础》课后习题参考答案与解析
c语言程序设计基础》课后习题参考答案与解析_IT认证_资格考试/认证_教育专区。《程序设计基础》习题参考答案与部分解析 第 1 章 C 语言概述 一、填空 a) C ...
C语言程序设计基础教程_习题答案
C语言程序设计基础教程_习题答案_计算机软件及应用_IT/计算机_专业资料。习题答案 第1章 1.1 填空题 1.1.1 应用程序 ONEFUNC.C 中只有一个函数,这个函数的...
C语言编程开发入门基础教程
中国Unix/Linux 软件开发联盟 http://www.lisdn.com C 语言编程开发入门基础...这种机制是当代大多数程序设计语言实现子程序 结构的基础,是使得递归成为可能。...
C语言基础编程练习
C语言基础编程练习_计算机软件及应用_IT/计算机_专业资料。自己学习C语言敲的简单程序1.屏幕上输入:This is a C program #include <stdio.h> int main() { ...
更多相关标签:
c语言程序设计基础pdf | 程序设计基础c语言版 | c语言程序设计基础ppt | 程序设计语言理论基础 | 程序设计语言基础 | 基础汇编语言程序设计 | 程序设计语言基础答案 | java语言程序设计基础 |