C大程笔记

链表

链表的定义

存储一批数据：
- 类型相同
- 数目不固定、可长可短、动态可变
- 连续有次序（逻辑上）
- 在内存中的位置可能是混乱的

用链表存储多项式

struct PolyNode
{
	int coef//系数
    int expon//指数
    struct PolyNode* link//链表指针
}

链表的分类：单向链表、双向链表
结构的递归定义：在定义结构的同时，使用它定义了一个指针成员

能且只能使用结构的指针类型进行递归定义因为指针所占的内存大小是固定的（4个字节）

内存类函数相关补充（用于结点申请）

malloc

使用内存申请函数 – malloc，在内存的动态存储区中申请一块连续的内存空间，作为链表结点

void* malloc(unsigned size);
/*参数 size 指定所申请的内存大小（字节数）
返回值类型：void *，通用指针 / 无类型指针 / 内存地址
若申请成功，则返回所分配内存的起始地址
需要转换到特定的指针类型，便于使用
若不成功，则返回NULL（地址值为0的非法指针）*/
    
struct student* p;
p = (struct student *)malloc(sizeof(struct student) );
//调用malloc时，用 sizeof 计算存储块大小 - 注意：虽然内存块是动态分配的，但一旦分配成功后，它的大小也是确定的，不要越界使用 

if( p==NULL ) {
   //申请失败了，进行相应处理
}

free

当动态申请的内存块不再需要时，要及时释放它。调用内存释放函数：

void free(void *ptr);
/*释放以ptr为起始地址的内存块
该内存块必须是之前由动态申请得到的
要完全释放，不能是申请得到的一部分*/

calloc
功能：申请分配 n 个长度为 size 的连续空间也就是：分配一个长度为 n * size 的连续空间

返回值：如果成功，返回指向分配起始地址的指针；如果失败，返回NULL。
1
2
void * calloc(size_t n, size_t size)；
realloc（先了解）
realloc是在空间不足时，对其空间进行再次扩容；realloc是在空间不足时，对其空间进行再次扩容
1
2
3
void* realloc (void* ptr, size_t size); int *pc = (int *) realloc (p, sizeof(int) *n);

单向链表常用操作

链表的建立

重要元素：

用一个指针指向链表的第一个结点

1 2	`struct stud_node *head;`

建立第一个链表

1 2	`head = NULL；//建立了一个空链表（空链表是最简单的合法链表）`

链表的尾指针

指向链表的末尾节点

1
2
3

struct stud_node* tail;
//当链表为空时：tail 与 head 均为 NULL;当链表只有一个结点：tail 与 head 均指向该节点;

看一个栗子：

/* 链表结点结构 */
struct stud_node
{
    int    num;             // 学号
    char   name[20];        // 姓名
    int    score;           // 成绩
    struct stud_node *next; // 链表指针
};

scanf("%d%s%d", &num, name, &score);
    while( num != 0 ) {  
        // 学号为0，表示结束
        p = (struct stud_node *) malloc(size); // 申请结点
        p->num = num;    // 将学生信息存入结点
        strcpy(p->name, name);   
        p->score = score; 
        p->next = NULL;  // 将该结点链表指针清零 

		// 将结点p添加到链表末尾
        if(head == NULL) // 若原来是空链表
            head = p;
        else  
            tail->next = p; // 将结点p添加到链表末尾
        tail = p; // 更新链表的尾指针
        scanf("%d%s%d", &num, name, &score);

以上为将结点p添加到链表的尾部，若要加到表头位置：

if(head = NULL) // 若原来是空链表
    tail = p;
else 
    p->next = head; // 将结点p插入导表头前面
head = p; //更新链表的头文件

链表的遍历（打印）

继续上面的例子

假设指针p指向一个学生结点，那么学号是：p->num 姓名是：p->name 成绩是：p->score 下一个学生是：p->next

如果p->next==NULL,那么：p是最后一个结点，遍历结束

void Print_Stu_Doc(struct stud_node * head) 
{ 
    struct stud_node * p;
    if(head == NULL){
        printf("\nNo Records\n");
        return;
     }
     printf("\nThe Students' Records Are: \n");
     printf("    Num   Name   Score\n");
     for( p = head; p!=NULL; p = p->next )
        printf("%8d %20s  %6d \n", p->num, p->name, 
	 	p->score);
}

插入结点

先连后断
1
2
s->next = ptr->next; ptr->next = s;

删除结点

先连后删：删除ptr1后的结点：

1
2
3

del = ptr1->next;
ptr->next->next = del->next;//建立新链接
free(del);//释放结点内存

通用链表的实现

维护一个链表,关键在于维护链表的“链”指针
- 无论实际存储的数据是什么样的，对“链”的操作都是一样的。
通用的链表 – 将实际的数据用一个void*指针记录

在处理数据时，再将dataptr转换为实际的类型指针（用户自己知道）

一个小项目

编写程序：读入两个多项式，计算并输出他们的和、差和乘积。要求基于课件中提到的三个表示方法，分别实现3个方法。多项式系数为整数最后的结果中不保留系数为0的项输出结果按照幂次递减排列。

指针进阶1

本章要点：指针数组和指向指针的指针是如何被定义和使用的？指针如何作为函数的返回值？指向函数的指针的意义是什么？

指针回顾

指针是一种新的数据类型

存放变量的地址

存放数据单元的地址

int x, *p;
p = &x;//x为取地址运算符,给指针赋值
*p = 3;//访问指针所指向的变量
x = *p;

指针作为函数参数，传递结果，改变主调函数的变量值

void swap(int *x, int *y)
{
   int temp = *x;
   *x = *y;
   *y = temp;
}

void main()
{
   int a=1, b=2;
   swap(&a, &b);
}

指针与数组
- 数组名实际上代表了一个指针，指向数组的首元素
- 数组名是一个指针常量，不能改变它的地址值
  1
  2
  3
  4
  int a[100], c， *p; a = & c; /*不可以*/ p = a; /*可以*/
- 指针的加法：指针 + 整数n；结果：将指针往后移动n个单元；即：地址值增加了n * sizeof(数据类型)
指针比较与减法
- 两指针可以比较大小，其结果等价于比较它们地址的大小；两同类型指针可相减，其结果等于它们之间所能存储的数据个数
  
  即：
  1
  2
  3
  4
  5
  6
  7
  8
  // p地址-q地址 // p–q = ---------------- // sizeof(类型） double a[10], *p, *q; p = a; q = &a[4]; q - p = 4; (int)q - (int)p = 32;

指针与数组

int a[100];

指针a指向首元素a[0];

指针a+i指向元素a[i];

表达式a[i]等价于 *(a+i)

数组元素的指针作为函数参数

void bubble(int *a, int n);
void bubble(int a[ ], int n);
int sum(int a[], int n); 

假设有int b[100]; 那么：
sum(b, 100)的结果是 b[0]+b[1]+…+b[99]
sum(b, 88) 的结果是 b[0]+b[1]+…+b[87]
sum(b+7,9) 的结果是 b[7]+b[8]+…+b[15]
sum(&b[7],9) 的结果也是 b[7]+b[8]+…+b[15]

字符串和字符指针
- char sa[] = “array”;
  
  定义了一个数组，并被初始化为 array\0
  
  char *sp = “point”;
  
  定义了一个指针sp，而非数组。指针指向了一个字符串常量，而该字符串常量存储在何处呢？ - Somewhere decided by the system.

常用的字符串处理函数：

strcpy(char *s, char *t)
strcat(char *s, char *t)
strcmp(char *s, char *t)
strlen(char *s)
gets/scanf ： gets函数读入一整行(包括空格），直到回车为止；scanf函数读入字符，直到空格和回车为止
puts/printf：puts函数输出后会自动换行

sscanf/sprintf：从字符串中读入数据将数据，打印输出到字符串，例如：

char t[256] = “1234”;
sscanf(t, “%d”, &x);
sprintf(t, “value = %d”,x);

/* sscanf/sprintf应用举例
 - libgraphics simpleGUI demo */
char s[256],t[256];
double value; if( textbox(GenUIID(0),x,y,w,h,s,sizeof(s)) )
{
    sscanf(numstr,"%lf",&value);
    sprintf(t, "input value is: %f", value);
}

指针数组

首先它是一个数组；其次，它的元素是指针

char * color[5] = { “red”, “blue”, “yellow”, “green”, “black” };
for( i=0; i<5; i++ )
   printf("%d-th color = %s\n", i, color[i]);

指向指针的指针

定义语法格式：类型名 **指针变量名
1
2
3
4
int a = 10; int *p = &a; int **pp = &p;

指针数组与二级指针

char * color[5] = { “red”, “blue”, “yellow”, “green”, “black” };

数组名color是一指针，指向首元素color[0]。
char **pc = &color[0] /*或者 color */
指针数组名也是一个二级指针

指针数组与二维数组

ccolor是一个二维数组
1
2
3
4
5
6
7
char ccolor[][7] = { “red”, “blue”, “yellow”, “green”, “black” }; char * pcolor[5] = { “red”, “blue”, “yellow”, “green”, “black” };
它的每一行都是一个一维数组
- ccolor + i 是一个指针，指向第i行上的一维数组
  
  ccolor+i 类型 “长度为7的一维数组”的指针
  
  ccolor[i] 是一维数组

函数指针

指向函数的指针，定义语法格式：

类型名 (*变量名)(参数类型表);

例如 int (*funptr)(float, double);

定义了一个函数指针，它的类型是一个指针，可以存储一个“返回值是int, 有两个分别是float和doulbe参数的函数” 的地址。

函数名字本身可以作为函数指针，使用编译器不区分： add 和 &add 、 fp 和 (*fp)

int add(int a, int b)
{
   return (a+b);
}
void main()
{
   int x, y;
   int (*fp)(int,int);
   fp = add;
   fp = &add;
   x = fp(3, 4);
   y = (*fp)(5, x);
}

函数指针作为参数

/* 用梯形公式计算一个函数的积分 */
double calc(double (*fp)(double),
            double a, double b)
{
   double z;
   z = (b-a)/2 * (fp(a)+fp(b));
   return z;
}

double f1(double x)
{ 
  return x*x; 
}

double f2(double x)
{
  return sin(x)/x; 
}

void main()
{
    double result;
    double (*fp)(double);
    fp = f1;
    result = calc(fp, 1,2);
    result = calc(f2, 1,2);
}

typedef语句进阶

指针类型的typedef语句：
- typedef 旧类型名 * 指针类型名;
- 例如：typedef int * INTP;
  
  将 INTP 定义为一个整数指针类型。
  
  以下是等价的： INTP p; <=> int * p;
数组类型的typedef语句（注意辨析）
- typedef 元素类型名数组类型名[长度常量];
- 例如：typedef int IntArray[10];
  
  将 IntArray 定义为一个长度为10的整数数组类型。
  
  以下是等价的： int a[10]; <=> IntArray a;
- IntArray *ap; /* ap是什么类型变量 */
  
  ap 是一个指针变量，是数组指针ap 能够指向的类型（简称基类型）是长度为10的数组（数组指针）
- 如果没有用typedef定义IntArray, 如何定义数组指针ap?
  
  int (*ap)[10];
  
  注意和下面定义的区别
  
  int *ap[10]; (这是指针数组)
写typedef语句的一般方法
- 首先定义一个目标类型的变量 int a[10];
- 然后将变量名替换为新类型名 int IntArray[10];
- 最后在前面加上typedef typedef int IntArray[10];

练习1：输出为：d

typedef char CA[5];
CA* conv(char s[])
{
	return (CA*)s;//返回指针.
}
void main()
{      char h[ ] = “HelloWorld”;
	printf(“%c”, conv(h)[1][4]);
}

//思考：不用typedef，怎么写？
char (*conv)(char s[])[5]
{
	return (char (*)[5]) s;
}

练习2：将一个长度为100的数组，作为列宽为5的二维数组使用

void main()
{
    int a[100], (*p)[5], k, j;
    p = (int (*)[5]) a;
    for( k = 0; k<20; k++ )
	for( j = 0; j<5; j++ )
		p[ k ][ j ] = k + j;
}

typedef 函数类型

首先定义一个目标类型的变量 int f(int a, int b);

然后将变量名替换为新类型名 int Func (int a, int b);

最后在前面加上typedef typedef int Func(int a, int b);
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef int FuncType(int x, int y); int add( int a, int b) { return a + b; } void main() { FuncType * fp = add; printf(“3 + 4 = %d\n”, fp(3,4)); }
typedef函数指针类型

首先定义一个目标类型的变量 int (*f)(int a, int b);

然后将变量名替换为新类型名 int (*FPtr)(int a, int b);

最后在前面加上typedef typedef int (*FPtr)(int a, int b);
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef int (*FuncPtr)(int x, int y); int add( int a, int b) { return a + b; } void main() { FuncPtr fp = add; printf("3 + 4 = %d\n", fp(3,4)); }

交互式编程的回调函数

typedef void (*KeyboardEventCallback) (int key, int event);

typedef void (*CharEventCallback) (char c);

typedef void (*MouseEventCallback) (int x, int y, int button, int event);

typedef void (*TimerEventCallback) (int timerID);
关于交互式编程

指针进阶2（1的补充）

楔子

问题：计算矩阵的行列式。

编写函数计算一个 NxN 矩阵 A 的行列式，N <= 100；

矩阵 A 可以用一个二维数组表示，a[i] [j]表示第i行、第j列的元素Aij
今天我们不关注算法实现

定义函数的原型double Det(double a[100] [100], int n);

函数原型可以等价地写成

double Det(double a[ ] [100], int n);

double Det(double (*a)[100], int n);

为什么捏？数组到底是什么？

指针的要素

指针的要素：*基类型、地址值 => 类型名 指针变量名

int *p1; p1的基类型是int

char *p2; p2的基类型是char

double *p3; p2的基类型是double

double **p4； p4的基类型是double*

double ***p5； p5的基类型是double**

使用指针之前，一定要赋值

scanf("%s", s);  
//根据指针s的地址，将读取的字符串存放到内存的相应地方
scanf("%d"，p);
//根据指针p的地址，将读取的整数存放到内存的相应地方(本身即存放数组，故不需要“&”)
c = 3 + *p;
//根据指针p的地址，从内存的相应地方读取一个整数（p的基类型是整数）

指针的基类型与地址值

指针的加法对地址值的影响：地址值的增量 = sizeof(基类型）

定义	基类型	p所指向对象的地址（假设）	p+1指向
char *p;	char (1 byte)	1000020	1000021
short *p;	short (2 bytes)	1000040	1000042
long *p;	long (4 bytes)	1000080	1000084
…	…	…	…

指针与数组的关系

理解运算符[]

以下程序输出什么？

void main(){
    int a[5] = {1,3,5,7,9},*p = a;
    printf("%d %d",a[3],3[a]);
}

*运算符 [ ]的意义：x[y] <=> *(x+y)
所以 a[3] <=> *(a+3) <=> *(3+a) <=> 3[a]
因此，输出是: 7 7

*因为p和a具有相同的地址值，所以 a[i] 和 p[i] 是一样的

自定义类型 - typedef语句

typedef命令语法格式（详情见之前的指针进阶1）
回答一开始的问题，为何函数原型可以那样等价写出？
- 作为形式参数 a[ ] 与 *a 等价
- 注意一下区别： double *a[100]; a是（指针）数组
- double (*b)[100]; b是（数组）指针，即行指针

多级指针

思考问题：

int a = 10;
int *p = &a;
int **pp = &p;

//思考 pp = &(&a); 
不可以！！
运算符&取得“操作数”的地址
该操作数必须在内存中有对应地址

&a变量a的地址值，是一个常量
常量没有地址值，例如5,7,10等等


int a[5][10] = { 55 }, b = 66；
int *p = &b, **pp = &p;

//思考 *p是什么？**pp是什么？
**pp 等于 66
思考 pp = a;
发生了类型强制转换：行指针(int[10]) => int**
a的地址值 = a[0]的地址值 = a[0][0]的地址
    
//*pp是什么？等于什么？
*pp 是 int*，它的值是 55；
**pp是地址为55的内存数据（4个字节作为整数处理）
如果执行：int x = **pp；一般会报错

一个多级指针程序解析

char *c[] = {"ENTER", "NEW", "POINT", "FIRST"};
char **cp[]= {c+3, c+2, c+1, c};
char ***cpp = cp;
void main()
{
    printf("%s", **++cpp);
    printf("%s", *--*++cpp);
    printf("%s", *cpp[-2]+3);
    printf("%s\n", cpp[-1][-1]+1);
}

//综合结果 POINTENTERSTEW

语句printf(“%s”, **++cpp):

执行情况分析：

执行++cpp后，cpp指向了cp[1]，此时的*cpp等价于cp[1]，**cpp等价于*cp[1]，也即c[2]（因为此时的cp[1]指向c[2]，如图示）。

最后打印结果：POINT

语句printf(“%s”, *- -*++cpp)：

执行情况分析：

执行++cpp后，cpp指向了cp[2], 此时的*cpp等价于cp[2], - -*cpp等价于- -cp[2]，执行后cp[2]指向了c[0]， **cpp等价于c[0]。

打印结果：ENTER

语句printf(“%s”, *cpp[-2]+3);

执行情况分析：

注意，经过了上面两条语句的执行，此时的cpp指向了cp[2]。cpp[-2]等价于*（cpp-2），即cp[0]。
*cpp[-2] <=> *cp[0] <=> c[3] <=> 字符串“FIRST”的首地址。
*cpp[-2]+3 <=> c[3]+3 <=> 字符串“ST”的首地址。

打印结果：ST

语句printf(“%s\n”, cpp[-1] [-1]+1);

执行情况分析：

此时的cpp仍然指向cp[2]。
cpp[-1] [-1] <=> (*(cpp-1))[-1] <=> (cp[1])[-1] <=>*(cp[1]-1) <=> c[1] <=> 字符串“NEW”的首地址。
cpp[-1] [-1]+1 <=> c[1]+1 <=> “EW”

打印结果：EW

行指针（数组指针）[续]

#include <stdio.h>
#include <string.h>
char (*defy(char *p))[5]
{
  int i;
  for(i=0; i<3; i++)
    p[strlen(p)] = 'A';
  return (char(*)[5])p+1;
}
void main()
{
  char a[] = "FROG\ØSEAL\ØLION\ØLAMB";
  puts( defy(a)[1]+2 );
}

先看函数头: char (* defy(char *p)) [5]
- 按“从右到左”，找到defy
  - 它的右边是()，所以defy是一个函数；
- 该函数有一个参数 char *p；
- defy左边是 *，表明defy()返回一个指针
  
  char (* defy(char *p)) [5]
- 假设函数的返回值是 x, 那么x的类型定义是char (*x)[5];
所以，函数的返回值是一个指针，而且是行指针；它的基类型是：长度为5的字符数组

如何更清晰地定义函数defy:

利用typedef命令，程序更清晰

typedef char CA5[5];

CA5 *defy(char *p)
{
  int i;
  for(i=0; i<3; i++)
    p[strlen(p)] = 'A';
  return (CA5*)p+1;
}

函数defy的返回值:

return (char (*)[5])p + 1;

(char (*)[5])是一个强制类型转换
- 表示目标类型为数组指针（行指针）
- 该指针指向由5个char构成的一维数组。
- 注意这里的*必须用()括起来，强调指针优先
  - 理解的时候可以设想*后面有一个变量p；
分析defy(a)的执行结果:

char a[] = “FROG\ØSEAL\ØLION\ØLAMB”;

puts( defy(a)[1]+2 );
- 先看defy(a)的执行
  - 将字符串结束符\0变成A
  - 执行三次
- 再看defy的返回值
  - (CA*)p是一个行指针
  - (CA*)p+1指向下一行
  - 即指向： SEALA
puts( defy(a)[1]+2 )的实际参数:

执行defy(a)之后，数组a中数据是

“FROGASEALALIONALAMB”
- defy(a)的返回值是一个行指针
  
  指向 SEALA
- defy(a)[1] <=> *(defy(a)+1)
  
  defy(a)[1]的类型 CA5
  - 前面定义：typedef char CA5[5]; (长为5的字符数组)
  - defy(a)[1]也是char * 指针。
- defy(a)[1]+2
  
  指向 LIONA
==因此，函数puts的输出是：ONALAMB==

Note

#C #Note #In-class

【Note】C大程笔记（part I）

http://jiangguanyu.top/2023/03/29/【Note】C大程笔记/

作者

Django_Jungle

发布于

2023年3月29日

许可协议

【Note】Some Important Words and Expression of Discrete Mathematics and Its Application 上一篇

【Lecture】沈春华教授专题报告会 - 《计算机视觉发展介绍》下一篇