ZAM'S BLOG 2.3.3

《C语言快速入门：从指针到Segmentation Fault》

注意，本文编译环境为 Visual Studio 2019 on Windows 10 1903 X64

几个练手题

1.编程实现：用户给定一个整数，将该整数逆置之后输出。（如：输入 123，输出 321）。

限制条件

a.给定整数，不要用字符串来完成。
b.尽可能使时间复杂度小。
c.要求能够完成 214748364792 这个数字的逆置。

程序源码

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

int main() {
	long long int input;
	scanf_s("%lld", &input);
	long long int output = 0, digit;
	while (input > 0) {
		digit = input % 10;//取当前最末位数
		output = output * 10 + digit;//将当前的最末位数加到待输出结果的最后一位
		input /= 10;
	}
	printf("%lld", output);
	return 0;
}

运行结果

整数逆置

2.编程实现：给定一串任意字符串。要求，将其中的所有整数提取出来并存入整数数组

给定样例

1023fase415#145#

程序源码

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

int main(void)
{
	char str[1000];
	int a[100];
	int p, q;
	int i = 0, r = 0,count = 0;//i用于控制输出，r用于控制字符串内查找,count用于计算字符串内数字个数

	gets(str);

	r = 0;

	while (1)
	{
		while (str[r] && (str[r]<'0' || str[r]>'9'))
			r++;        //跳过字符串中非数字部分

		if (str[r])
		{
			p = r;      //p指向数字子串开头
			q = r + 1;  //q寻找数字串结尾
			a[i] = str[r] - '0';//将字符串中的0变为数字0

			while (str[q] >= '0' && str[q] <= '9')
			{
				a[i] = 10 * a[i] + (str[q] - '0');//计算数字
				q++;
			}
			count++;
			r = q;    //设定新起点
			i++;
		}
		else
			break;
	}
	for (i = 0; i < count; i++)
		printf("%d ", a[i]);
	printf("\n");

	return 0;
}

运行结果

提取整数

3.编程实现：给定一串任意字符串。要求，将其中的所有数字提取出来并存入 double 数组。

给定样例

10.23fase4.15#14.5#

程序源码

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

int main(void)
{
	char str[1000], num[1000];
	double a[100];
	int p, q;
	int i = 0, r = 0,count = 0;//i用于控制循环，r用于控制字符串内查找,count用于计算字符串内数字个数

	gets(str);

	r = 0;

	while (1)
	{
		while (str[r] && (str[r]<'0' || str[r]>'9')) {//查找数字字串开头部分
			r++;
		}
		if (str[r])
		{
			p = r;      //p指向数字子串开头
			q = r + 1;  //q寻找数字串结尾

			while ((str[q] >= '0' && str[q] <= '9')||str[q]=='.'){
				q++;
			}
		for (i = 0; i < q-p; i++) {//将数字字串转存到新字符串中，用于后续转化输出
				num[i] = str[p + i];
			}
			num[i] = '\0';
		a[count] = atof(num);
			count++;
			r = q;    //设定新起点
		}
		else
			break;
	}
	for (i = 0; i < count; i++)
		printf("%lf ", a[i]);
	printf("\n");

	return 0;
}

运行结果

提取数字

几个烧脑题

多级指针：观察下列代码，思考并解释程序运行结果

1

程序代码及解释

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
int main()
{
	char * c[] = { "ENTER", "NEW", "POINT", "FIRST" };//定义了四个指针c[0]-c[3]分别指向四个字符串
	char** cp[] = { c + 3, c + 2, c + 1, c };//定义了一个二级指针数组，其中的cp[0]-cp[3]分别依次对应c[3]-c[0]
	char*** cpp = cp;//定义了一个三级指针，指向二级指针数组的第一个元素cp[0]，此时cpp就相当于c[3]
	printf("%s\n", ** ++cpp);//** cpp经过间接引用运算后相当于是指针cp，指针cp自增后指向的是指针数组cp[]中的第二个元素,也即是c[2]
	printf("%s\n", * --* ++cpp + 3);//首先对指针cpp作了自增操作，使得cpp指向cp[2],此时cpp中的地址为c+1，再通过自减符使得指针 * cpp即cp[2] (注意不是cpp)的地址变为c，这时候*--* ++cpp相当于指向了一个字符数组{'E','N','T','E','R'}的首地址。+3的操作等价于在这个字符数组的首地址的基础上再右移三个地址，指向了第二个E，然后通过printf将第二个E和之后的所有剩余字符全部打印。
	printf("%s\n", * cpp[-2] + 3);//经过了上一条语句后，cpp指向cp[2],那么cpp[-2]指向cp[0]（注意，此时cpp内存储的地址并没有改变）,即c[3]此时的*cpp[-2]就相当于指向了一个字符数组{'F','I','R','S','T'}的首地址。+3的操作等价于在这个字符数组的首地址的基础上再右移三个地址，指向了S，然后通过printf将S和之后的所有剩余字符全部打印。
	printf("%s\n", * cpp[-1][-1] + 1);//同上理，此时cpp指向cp[2],cpp[-1]就会指向cp[1]，即c[2],那么cpp[-1][-1]就相当于指向c[1],即一个字符数组{'N','E','W'}的首地址。+1的操作等价于在这个字符数组的首地址的基础上再右移1个地址，指向了E，然后通过printf将E和之后的所有剩余字符全部打印。
	system("pause");
	return 0;
}

上机验证

上机验证

2

程序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
struct Test
{
	int Num;
	char* pcName;
	short sDate;
	char cha[2];
	short sBa[4];
}*p;
int main()
{
	p = 0x100000;
	printf("%p\n", p + 0x1);//输出00100014
	printf("%p\n", (unsigned long)p + 0x1);//输出00100001
	printf("%p\n", (unsigned int*)p + 0x1);//输出00100004
	return 0;
}

解释

首先要明确，指针与整数的加减法公式为 p = p +/- sizeof（type * p）

第一行输出 00100014 的原因是结构体 Test 的存储空间大小为 sizeof(int) + sizeof(char* ) + sizeof(short) + sizeof(char)* 2 + sizeof(short)* 4 = 20,并且指针的地址是以十六进制数存放的，因此 p + 0x1 就相当于指针 p 向后移动了 sizeof(Test)的内存大小，因此输出的内存地址比 1000000 大 20，为 00100014。

第二行输出 001000001 的原因是(unsigned long)语句将* p 转换成了整数类型，因此此时做的只是普通的整数与整数之间的加减法。

第三行输出 00100004 的原因是 (unsigned int)语句将 Test 类型的 p 指针转换成了 int _ 类型，根据公式此时 sizeof(int_) = 4,因此输出 00100004。

上机验证

上机验证

3

程序代码

#include <stdio.h>

1
2
3
4
5
6
7
8
int main()
{
	int a[4] = { 1, 2, 3, 4 };
	int * ptr1 = (int * )(&a + 1);
	int * ptr2 = (int * )((int)a + 1);
	printf("%x\n%x\n", ptr1[-1], * ptr2);\\输出4 2000000
	return 0;
}

解释

首先，&a 指的是取数组 a 的地址，而&a + 1 指的是加上一个 int a[4]的长度，即 sizeof(int) * 4=16 字节，所以 ptr1 指向数组 a 后面的内存单元，如果用下标表示就是 a[5]

由指针与整数的加减法公式 p = p +/- sizeof（type _ p，ptr1[-1]表示 ptr1 指向的地址再减去 sizeof(int _ )，即指向 a[4]，所以第一个%x 输出对应的是 0x4.

(int)a+1 的值就是元素 a[0]的第二个字节的地址，然后把这个地址强制转化为（int)类型赋给 ptr2，也就是说ptr2 的值应该为元素 a[0]的第二个字节开始的连续 4 个 Byte 的内容。

不过要想理解为什么输出了 2000000，就要首先明白数字在数组中是怎么被存储的：

每个元素具体存储方式，取决于 CPU。 有两种：
1、小端(Little Endian)：
将低序字节存储在起始地址（低位编址）, 地址低位存储值的低位，地址高位存储值的高位 。
目前大多数 CPU 是按照这种方式存储的，包括 intel 和移动端最常见的 arm。
比如 4 字节整型值为 0x12345678 的情况，那么在内存中会存储为：
0x78 0x56 0x34 0x12
2、大端(Big Endian)：
与小端相反， 将高序字节存储在起始地址（高位编址），地址低位存储值的高位,地址高位存储值的低位。
之前的例子在大端情况下存储为：
0x12 0x34 0x56 0x78

因此，a[0]在内存中被存储为 0x01 0x00 0x00 0x00,a[1]在内存中被存储为 0x02 0x00 0x00 0x00，此时 ptr2 所指向的内存区域的值就是 0x00 0x00 0x00 0x02

但是，在 printf 进行输出时，内存中的值是自右而左地被读出的，因此输出的值应该是 0x02000000

上机验证

上机验证

其余部分

就先咕为敬了，告辞
有空再补
咕咕咕
好了我胡汉三又回来了

malloc 函数的使用

在 C 语言中，malloc 是动态内存分配函数。

它的原型声明在 stdlib.h 头文件中：

1
void *malloc(unsigned int num_bytes);

num_bytes 是无符号整型，用于表示分配的字节数。
这个函数的返回值：如果分配成功则返回指向被分配内存的指针 void* (此存储区中的初始值不确定)，否则返回空指针 NULL。
void* 表示未确定类型的指针，void * 可以指向任何类型的数据，更明确的说是指申请内存空间时还不知道用户是用这段空间来存储什么类型的数据（比如是 char 还是 int 或者…）
这个函数的功能很简单：就是分配长度为 num_bytes 字节的内存块。
注意：由于 C 语言中缺少内存回收机制，所以当内存不再使用时，应使用 free()函数将内存块释放。函数返回的指针一定要适当对齐，例如说统一为 4 的倍数，使其可以用于任何数据对象。
关于该函数的原型，在以前 malloc 返回的是 char 型指针，新的 ANSIC 标准规定，该函数返回为 void 型指针，因此在使用是我们应要进行类型转换。
example:

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

#include<stdlib.h>//malloc()函数被包含在stdlib.h里面

int main(void)
{

char*a=NULL; //声明一个指向a的char*类型的指针

a=(char*)malloc(100*sizeof(char));//使用malloc分配内存的首地址，然后赋值给a

if(!a)//如果malloc失败，可以得到一些log

{
perror("malloc");
return-1;
}

sprintf(a,"%s","HelloWorld\n");//"HelloWorld\n"写入a指向的地址

printf("%s\n",a);//输出上边写入a的字符串

free(a);//释放掉使用的内存地址

return 0;//例2有无内存泄露？

}

而且，作为一名合格的码农，我们应当对一些特殊情况进行特殊处理，如这里的 malloc 函数若调用失败，则直接让程序退出，而不是让其运行下去，否则可能会造成更大的 bug，而且也不利于我们根据返回值进行 debug。

结构体指针->的使用

除了我们通过结构体变量名.成员名的方式引用结构体变量中的成员，我们还可以使用指针。
要想学会->这种指针的使用，首先我们就要学会一般的结构体指针使用方式：
(* 指针变量名).成员名
这个指针变量定义成什么类型呢？
只能定义成结构体类型，且指向什么结构体类型的结构体变量，就要定义成什么样的结构体类型。
比如指向 struct STUDENT 类型的结构体变量，那么指针变量就一定要定义成 struct STUDENT* 类型。
example:

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
# include <stdio.h>
# include <string.h>
struct AGE
{
    int year;
    int month;
    int day;
};
struct STUDENT
{
    char name[20];  //姓名
    int num;  //学号
    struct AGE birthday;  //生日
    float score;  //分数
};
int main(void)
{
    struct STUDENT student1; /* 用struct STUDENT结构体类型定义结构体变量student1*/
    struct STUDENT * p = NULL;  /* 定义一个struct STUDENT结构体类型的指针变量p*/
    p = &student1;  /* p指向结构体变量student1的首地址, 即第一个成员的地址*/
    strcpy((* p).name, "小明");  //(* p).name等价于student1.name
    (* p).birthday.year = 1989;
    (* p).birthday.month = 3;
    (* p).birthday.day = 29;
    (* p).num = 1207041;
    (* p).score = 100;
    printf("name : %s\n", (* p).name);  //(* p).name不能写成p,即使p指向的是student1.name的地址。
    printf("birthday : %d-%d-%d\n", (* p).birthday.year, (* p).birthday.month, (* p).birthday.day);
    printf("num : %d\n", (* p).num);
    printf("score : %.1f\n", (* p).score);
    return 0;
}

输出结果：

1
2
3
4
name : 小明
birthday : 1989-3-29
num : 1207041
score : 100.0

注意，_ p 两边的括号不可省略，因为成员运算符“.”的优先级高于指针运算符“ _ ”，所以如果 _ p 两边的括号省略的话，那么 _ p.num 就等价于 _ (p.num) 了。
从该程序也可以看出：因为指针变量 p 指向的是结构体变量 student1 第一个成员的地址，即字符数组 name 的首地址，所以 p 和 (_ p).name 是等价的。
但是，“等价”仅仅是说它们表示的是同一个内存单元的地址，但它们的类型是不同的。指针变量 p 是 struct STUDENT* 型的，而 (* p).name 是 char* 型的。所以在 strcpy 中不能将 (* p).name 改成 p。用 %s 进行输入或输出时，输入参数或输出参数也只能写成 (_ p).name 而不能写成 p。
同样，虽然 &student1 和 student1.name 表示的是同一个内存单元的地址，但它们的类型是不同的。&student1 是 struct STUDENT_ 型的，而 student1.name 是 char* 型的，所以在对 p 进行初始化时，“p=&student1；”不能写成“p=student1.name”。因为 p 是 struct STUDENT* 型的，所以不能将 char* 型的 student1.name 赋给 p。C 语言是一门强数据类型的语言，就在这里体现的淋漓尽致。
此外,为了使用的方便和直观，我们可以直接用指针变量名->成员名来代替。
p->num 的含义是：指针变量 p 所指向的结构体变量中的 num 成员。p->num 最终代表的就是 num 这个成员中的内容。
下面，我们可以用指针变量名->成员名的形式对我们刚刚的代码进行修改：

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
# include <stdio.h>
# include <string.h>
struct AGE
{
    int year;
    int month;
    int day;
};
struct STUDENT
{
    char name[20];  //姓名
    int num;  //学号
    struct AGE birthday;  /* 用struct AGE结构体类型定义结构体变量birthday, 生日*/
    float score;  //分数
};
int main(void)
{
    struct STUDENT student1; /* 用struct STUDENT结构体类型定义结构体变量student1*/
    struct STUDENT * p = NULL;  /* 定义struct STUDENT结构体类型的指针变量p*/
    p = &student1;  /* p指向结构体变量student1的首地址, 即第一项的地址*/
    strcpy(p->name, "小明");
    p->birthday.year = 1989;
    p->birthday.month = 3;
    p->birthday.day = 29;
    p->num = 1207041;
    p->score = 100;
    printf("name : %s\n", p->name);  //p->name不能写成p
    printf("birthday : %d-%d-%d\n", p->birthday.year, p->birthday.month, p->birthday.day);
    printf("num : %d\n", p->num);
    printf("score : %.1f\n", p->score);
    return 0;
}

输出同上。

链表的基本概念及简单使用

学了三个月，终于学到了第一种数据结构类型：链表。
那么，链表它到底是个啥？
链表，链表，首先它得是个线性表。根据《数据结构》书中介绍，一个线性表是 n 个数据元素的有限序列，它的长度可根据需要增长或缩短，还有一系列对线性表的操作。线性表可分为顺序存储结构和链式存储结构两种。
那么今天所学习的链表，全称就叫链式存储结构线性表。
线性链表可分为单链表，循环链表，双链表。

线性表特点是用一组任意的存储单元存储线性表的数据元素，同时还存储一个指向后继信息的信息，这两部分信息组成为结点。
结点包含两部分数据域和指针域。指针域存储信息成为指针或链。链表中只包含一个指针域，故称为单链表。
单链表

下面通过 c 语言实现单链表的基本操作：

1
2
3
4
5
6
7
8
9
10
11
#define MAXSIZE 20
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef int Status;
//上述是一些重命名和宏定义
//单链表的存储结构
typedef struct LNode{
    ElemType data;  //数据域
    struct Node * next; //指针域
}LNode，*LinkList;

读取链表第 i 个元素的数据：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Status GetElem(LinkList L, int i, ElemType *e){
    LinkList p;
    int j;
    p = L->next;
    j=1;
    while(p && j<i){
        p = p->next;
        ++j;
    }
    if(!p || j>i){
        return ERROR;
    }
    * e = p->data;
    return OK;
}

在带头结点的链表 L 的第 i 个位置之前插入元素 e:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status ListInsert(LinkList &L, int i, ElemType e){
    LNode p;
    int j;
    p = L;
    j=0;
    while(p && j<i-1){
        p = p->next;
        ++j;
    }
    if(!p || j>i-1){
        return ERROR;
    }
    LinkList s;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next =s;
    return OK;
}

在带头结点的链表 L，删除第 i 个位置的元素，并由 e 返回其值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Status ListDelete(LinkList &L, int i, ElemType &e){
    LNode p;
    int j;
    p = L;
    j=0;
    while(p && j<i-1){
        p = p->next;
        ++j;
    }
    if(!(p->next) || j>i-1){
        return ERROR;
    }
    LinkList q;
    q = p->next;
    p = q->next;
    e = q->data;
    free(q);
    return OK;
}

循环链表是另外一种存储形式的链式存储结构，特点是表中最后一个结点的指针域指向头结点，与单链表比较相像，故不再赘述。
双向链表：是指针域指向前驱结点和后继结点。
存储结构为：

1
2
3
4
5
typedef struct DuLNode{
    ElemType data;
    struct DuLNode * prior;
    struct DuLNode * next;
}DuLNode, * DuLinkList;

链表延伸

1.编程创建一个单链表。可不断读取用户输入的整数并存储进链表里。并在最后将链表里面的数据打印出来。 2.编程实现：将上述任务中已经创建完毕的单链表逆置（如将 1->2->3->4->null 逆置为 4->3->2->1->）

程序代码

简明起见，我将两个任务写在一个程序里了

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
#include <stdio.h>
#include <stdlib.h>
#define SUCCESS 10000
#define FAILURE 10001
typedef int ElemType;
typedef struct Node
{
	ElemType data;
	struct Node* next;
}Link;

int  InitLink(Link** l)//初始化链表
{
	if (NULL == l)
	{
		return FAILURE;
	}
	* l = (Link*)malloc(sizeof(Link));
	if (NULL == * l)
	{
		return FAILURE;
	}
	(* l)->next = NULL;
	(* l)->data = 0;
	return SUCCESS;
}
int  InsertLink(Link* l, int place, ElemType e)//插入链表
{
	int k = 1;
	if (NULL == l)
	{
		return FAILURE;
	}
	if (place > l->data + 1 || place <= 0)
	{
		return FAILURE;
	}
	Link* head = l;
	while (k < place)
	{
		k++;
		l = l->next;
	}
	Link* tmp = (Link*)malloc(sizeof(Link));
	if (NULL == tmp)
	{
		return FAILURE;
	}
	tmp->next = l->next;
	l->next = tmp;
	tmp->data = e;
	head->data++;
	return SUCCESS;
}
int TraverseLink(Link* l)//遍历链表
{
	int length;
	if (NULL == l)
	{
		return FAILURE;
	}
	length = l->data;
	while (length > 0)
	{
		length--;
		l = l->next;
		printf("%d ", l->data);
	}
	return SUCCESS;
}
void ReverseList(Link* L)//逆置链表
{
	Link* curnode = L->next; //当前节点，指向表头
	Link* temp = curnode->next; //临时节点

	curnode->next = NULL;
	L->next = curnode;

	while (temp != NULL)
	{
		curnode = temp;
		temp = curnode->next;
		curnode->next = L->next;
		L->next = curnode;
	}
}
int SortInsert(Link* l, ElemType e)
{
	int flag = 1;
	int length, place;
	if (NULL == l)
	{
		return FAILURE;
	}
	Link* head = l;
	length = l->data;
	l = l->next;
	place = 0;
	if (0 == length){
	 	InsertLink(head, place + 1, e);
	 }
	else{
	while (place < length)
	{
		if (e < l->data)
		{
			InsertLink(head, place + 1, e);
			flag = 0;
			break;
		}
		else
		{
			l = l->next;
			place++;
		}

	}
	if (1 == flag)
	{
		InsertLink(head, length + 1, e);
	}
	}
	return SUCCESS;
}
int main()
{
	Link* list;
	ElemType e;

	InitLink(&list);
	printf("Please input numbers,input other character to end!\n");
	while(scanf_s("%d",&e) == 1)
	{
		printf("Please input numbers,input other character to end!\n");
		SortInsert(list, e);
		// printf("Length = %d\n", list->data);

	}
	printf("The output is :");
	TraverseLink(list);
	ReverseList(list);
	printf("\nThe  reverse List output is: ");
	TraverseLink(list);
	return 0;
}

程序运行结果

程序运行结果

Leetcode

都不会做
好难啊
我太菜了


博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://blog.zam-meow.cn/2019/10/16/AST-Task2/

评论




博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本站使用 Zam's Blog 作为主题，总访问量为 次
字数统计：47k 载入天数...载入时分秒...

Copyright © 2019-2021 Zam