一、周学习内容
1、9.18
数据结构(Day15)-CSDN博客
2、9.19
数据结构(Day16)-CSDN博客
3、9.20
-
链表
-
目的
-
插入删除不需要移动任何节点(元素)。
-
不需要预估存储空间大小,长度动态增长或减小。
-
-
概念
-
采用链式存储的线性表。
-
-
链表的种类
-
-
单向链表
-
单向链表的概念
-
每个节点都有2部分组成,一部分是存储数据,一部分是存储地址。
-
节点描述:存储数据的叫数据域,存储地址的叫指针域。
-
单链表节点存在第0号节点(头节点),不存储数据,只存储节点个数len。
-
-
结点结构体格式
-
typedef struct zhangzhen {union{int data;//用于正常节点,存储数据int len;//用于头节点,计算节点个数。};struct zhangzhen *next;//指针域,存储下一个节点地址 }link,*Plink;
-
-
单链表的相关操作(部分)
-
单链表的创建
-
Plink create()//创建头结点 {Plink p = malloc(sizeof(liink));if(NULL==p){printf("申请头节点失败\n");return NULL;}p->len = 0;p->next = NULL;return p;//返回头结点 }
-
头插法创建单链表
-
-
int front_insert(Plink L,int e)//头插法创建单链表 {if(L==NULL){printf("单链表不存在,创建失败\n");return -1;}Plink p = malloc(sizeof(liink));//申请新节点p->data = e;//数据域赋值p->next = L->next;//连线右边L->next = p;//连线左边L->len++;return 0; }
-
-
-
尾插法创建单链表
-
-
int rear_insert(Plink L,int e)//尾插法创建整表 {if(L==NULL){printf("单链表不存在插入失败\n");return -1;}Plink t =L;int i;for(i = 0;i<L->len;i++){t = t->next;}Plink p = malloc(sizeof(liink));//申请新节点p->data = e;//数据域赋值p->next = NULL;t->next = p;L->len++;return 0; }
-
-
-
-
-
链表遍历
-
-
int output_link(Plink L)//遍历单链表 {int i;Plink t = L;for(i = 0;i<L->len;i++)//循环len次{t = t->next;printf("%d\t",t->data);//数据域}printf("\n");return 0; }
-
-
-
任意位置插入
-
-
int anypos_insert(Plink L,int pos,int e)//任意位置插入 {if(L==NULL||pos<1||pos>L->len+1){printf("插入失败\n");return -1;}int i;Plink t = L;for(i = 1;i<pos;i++)//移动pos-1次指向待插入节点的前驱{t = t->next;}Plink p = malloc(sizeof(liink));//申请新节点p->data = e;//数据域赋值p->next = t->next;t->next = p;L->len++;return 0; }
-
-
-
任意位置删除
-
-
int anypos_dele(Plink L,int pos)//任意位置删除 {if(L==NULL||pos<1||pos>L->len){printf("删除失败\n");return -1;}int i;Plink t = L;for(i = 1;i<pos;i++)//移动pos-1次指向待删除节点的前驱{t = t->next;}Plink Q = t->next;//保留要删除的节点t->next = t->next->next;//删除L->len--;free(Q);Q=NULL;return 0; }
-
-
-
任意位置查找
-
int anypos_find(Plink L,int pos) {if(L==NULL||pos<1||pos>L->len){printf("查找失败\n");return -1;}int i;Plink t = L;for(i = 0;i<pos;i++)//移动pos次指向节点{t = t->next;}printf("查找成功,该节点:%d\n",t->data);return 0; }
-
-
任意位置修改
-
int anypos_change(Plink L,int pos,int e) {if(L==NULL||pos<1||pos>L->len){printf("修改失败\n");return -1;}int i;Plink t = L;for(i = 0;i<pos;i++)//移动pos次指向节点{t = t->next;}t->data = e;printf("修改成功\n");return 0; }
-
-
-
4、脑图集合
二、周作业
第一部分 选择题
1. 能正确表示 “当x的取值在[1, 10] 和 [200, 210]范围内为真,否则为假” 的表达式是 ( )
A. (x >= 1)&&(x <= 10) && (x >= 200) && (x <= 210)
B. (x > 1)||(x <= 10) || (x >= 200) || (x <= 210)
C. (x > =1)&&(x <= 10) || (x >= 200) && (x <= 210)
D. (x > 1)||(x <= 10) && (x >= 200) || (x <= 210)
解析:
A: (x >= 1)&&(x <= 10) && (x >= 200) && (x <= 210)
错误,因为 && 运算符要求 xxx 同时满足两个范围条件,这不可能,因为 xxx 不可能同时在两个不相交的区间内。
B: (x > 1)||(x <= 10) || (x >= 200) || (x <= 210)
错误,因为 || 运算符将条件拆散,导致一些不在要求区间内的 xxx 也会返回真。例如,当 x=0x = 0x=0 时,x≤10x \leq 10x≤10 条件为真,所以整体表达式为真,但这不符合题意。
C: (x >= 1)&&(x <= 10) || (x >= 200) && (x <= 210)
正确,这个表达式准确表示 xxx 需要在 [1,10][1, 10][1,10] 或 [200,210][200, 210][200,210] 区间内。
D: (x > 1)||(x <= 10) && (x >= 200) || (x <= 210)
错误,优先级问题会导致结果不正确。这种写法会产生混乱的逻辑判断,不能准确表达两个范围的条件。
解答:
C
2. 下面程序段的运行结果是()
Int y;
Int x = y = 0;
While(x < 15) y++, x+=++y;
Printf(“%d, %d”, y, x);
A. 20, 7 B. 6, 12 C. 20, 8 D. 8, 20
解析:
初始化:
int y = 0;
int x = y = 0;
结果是 x = 0,y = 0。
进入 while(x < 15) 循环:
第一次循环:
y++ 使 y 先递增 1:y = 1。
++y 再递增 1:y = 2。
x += y; 所以 x = x + y = 0 + 2 = 2。
第二次循环:
y++ 使 y 递增 1:y = 3。
++y 再递增 1:y = 4。
x += y; 所以 x = x + y = 2 + 4 = 6。
第三次循环:
y++ 使 y 递增 1:y = 5。
++y 再递增 1:y = 6。
x += y; 所以 x = x + y = 6 + 6 = 12。
第四次循环:
y++ 使 y 递增 1:y = 7。
++y 再递增 1:y = 8。
x += y; 所以 x = x + y = 12 + 8 = 20。
此时,x = 20,不再满足 x < 15 条件,循环结束。
解答:
D
3. 对两个数组a和b进行如下初始化char a[ ] = “ABCDEF”; char b[ ] = {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’};则以下叙述正确的数()
A. a与b数组完全相同 C. a与b长度相同
B. a和b中都存放字符串 D. a数组比b数组长度长
解析:
A. a与b数组完全相同
错误。数组 a 比数组 b 多一个空字符 \0,因此它们并不完全相同。
B. a和b中都存放字符串
错误。只有数组 a 存储的是一个字符串(因为字符串有一个结束符 \0)。数组 b 只是一个字符数组,不包含 \0,因此不能被视为字符串。
C. a与b长度相同
错误。a 的长度是 7,b 的长度是 6,长度不相同。
D. a数组比b数组长度长
正确。数组 a 的长度是 7,而数组 b 的长度是 6,因此 a 比 b 长。
解答:
D
4. 以下这3个函数哪个可能引起指针方面的问题()
Int *f1 ( void )
{
Int x = 10;
Return ( &x );
}Int *f2( void )
{
Int *ptr;
*ptr = 10;
Return ptr;
}Int *f3( void )
{
Int *ptr;
Ptr = (int *) mallloc (sizeof( int ));
Return ptr;
}A. 只有f3 B. f1 f2 f3 C. 只有f1 and f2 D. f1
解析:
f1 会引发指针问题(返回局部变量的地址)。
f2 会引发指针问题(未初始化的指针)。
f3 不会引发指针问题,但需要注意内存释放。
解答:
C
5. 以下不是无限循环的语句为()
A. for(y = 0, x = 1; x > ++y; x=i++) i=x; B. for(;; x++ = i);
B. While( 1 ){x++;} D. for(i = 10; ; i--) sum+=i;
解析:
A. for(y = 0, x = 1; x > ++y; x=i++) i = x;
该 for 循环的条件是 x > ++y。初始时,x = 1,y = 0。
在第一次迭代中,++y 使 y 变为 1,比较 x > y 为假,因此循环条件不成立,循环结束。
A 不是无限循环。
B. for(;; x++ = i);
这是一个典型的无限循环形式,因为 for(;;) 没有指定终止条件(;; 表示没有条件)。
虽然右侧 x++ = i; 的赋值语句会不断执行,但没有终止条件,导致无限循环。
B 是无限循环。
C. while(1) { x++; }
while(1) 是一个典型的无限循环结构,因为条件永远为真,循环不会停止。
C 是无限循环。
D. for(i = 10; ; i--) sum += i;
这个 for 循环没有终止条件(for(i = 10; ; i--)),因此也是一个典型的无限循环形式。
D 是无限循环。
解答:
A
6. 若i为整型变量, 执行语句for(i = 1; i++<4;);后变量i的值是()
A. 3 B. 4 C. 5 D. 不定
解析:
初始时,i = 1。
循环条件是 i++ < 4,即先比较 i < 4,然后再执行 i++(后置递增运算)。
第一次循环:
比较 i < 4,此时 i = 1,条件为真。
然后执行 i++,i 变为 2。
第二次循环:
比较 i < 4,此时 i = 2,条件为真。
然后执行 i++,i 变为 3。
第三次循环:
比较 i < 4,此时 i = 3,条件为真。
然后执行 i++,i 变为 4。
第四次循环:
比较 i < 4,此时 i = 4,条件为假,循环结束。
循环结束时,i = 4。
解答:
B
7. 下面程序的输出是()
Void main( )
{
Unsigned char ucNum;
For (ucNum = 0; ucNum < 500; ucNum++){
......
}
Printf(“%d”, ucNum);
}A. 499 B. 500 C. 501 D. 无输出
解析:
unsigned char ucNum 是一个无符号字符类型,通常占用 1 字节,它的取值范围为 0 到 255,即总共能表示的值为 0 到 255(共 256 个值)
由于 ucNum 是 unsigned char 类型,当它达到 255 后再执行 ucNum++,它会发生溢出,回到 0(因为 unsigned char 的最大值是 255),所以 ucNum 不能达到 500。
实际上,ucNum 在循环中从 0 到 255,不断溢出并返回 0。循环条件 ucNum < 500 一直为真,直到达到 ucNum 再次溢出并回到 0。
循环结束条件:
理论上,因为 ucNum 是 unsigned char,它无法表示 500 这个值,所以它会经历多次溢出后继续循环,直到总共完成 500 次递增,最终 ucNum 为 500 % 256 = 244。
但是,选项中没有给出 244 这个选项,因此程序的输出可能不会是这些选项中的任何一个。
解答:
D
8. 若二维数组a有m列(假如a[0][0]位于数组的第一个位置上), 则计算任一元素a[i][j] 在数组中位置的公式为()
A. i*m+j B. j*m+i C. i*m+j-1 D. i*m+j+1
解析:
二维数组 a[i][j] 中,i 表示行号,j 表示列号。
数组的每一行有 m 列,因此在第 i 行,第 j 列的元素之前,有 i 行元素,每一行有 m 个元素。
也就是说,在 a[i][j] 之前,有 i * m 个元素(前面 i 行),再加上当前行中前面的 j 个元素。
因此,元素 a[i][j] 在数组中的位置计算公式为:
位置 = i * m + j
解答:
A
9下面程序的输出是()
Void main ()
{
Char a;
Char *str = &a;
Strcpy(str, “hello”);
Printf(str);
}
解析:
strcpy 函数用于将字符串 "hello" 复制到 str 指向的内存位置。由于 str 指向的是单个字符变量 a,这会导致未定义行为,因为字符串 "hello" 需要 6 个字符的空间(5 个字母加上一个终止符 \0),而 a 只有 1 个字符的空间。printf 会尝试打印 str 指向的内容,但由于之前的 strcpy 操作是非法的,可能会导致程序崩溃、输出不正确或其他不可预测的行为。
解答:
不确定
10. 若有说明语句:char c=’\72’; 则变量c()。
A. 包含1个字符 B. 包含2个字符
C. 包含3个字符 D. 说明不合法,c的值不确定
解析:
在 C 语言中,字符常量 '\72' 是一个八进制转义序列。
这里的 72 是八进制数,它对应的十进制值是 7 * 8^1 + 2 * 8^0 = 56 + 2 = 58。
因此,'\72' 实际上代表 ASCII 值为 58 的字符,即字符 ':'。
解答:
A
11. 以下程序输出结果是()
void fun(int x, int y, int z)
{z = x*x+y*y; }
void main()
{ int a = 31;
fun(5, 2, a);Printf(“%d”, a);
}
A. 0 B. 29 C. 31 D. 无定值
解析:
在 main 函数中,变量 a 被赋值为 31。
调用 fun(5, 2, a); 时,a 的值(31)被复制到 fun 函数中的 z 参数,但在 fun 中对 z 的赋值不会影响 main 中的 a。
解答:
C
12. 已知int x = 10, y = 20, z = 30; 以下语句执行后x, y, z的值是()。
If(x > y)
z = x; x = y; y = z;
A. x = 10, y = 20, z = 30 B. x = 20, y = 30, z = 30
C . x = 20, y = 30, z = 10 D. x = 20, y = 30, z = 20
解析:
if (x > y) 的条件为 false,因为 10 并不大于 20。
因为条件不成立,整个 if 语句块的内容将不会被执行。
解答:
A
13. 下面程序输出是()
void main()
{
Char *s = “12134211”;
Int v1 = 0, v2 = 0, v3 = 0, v4 = 0, k;
For(k = 0; s[k]; k++) {
switch(s[k]) {Default: v4++;
Case ‘1’: v1++; break;
Case ‘3’: v3++;
Case ‘2’: v2++; break;
}
}Printf(“v1=%d, v2=%d, v3=%d,v4= %d\n”, v1, v2, v3, v4);
}
A. V1=4, v2=2, v3=1, v4=1 B. V1=5, v2=3, v3=1, v4=1
B. V1=5, v2=8, v3=6, v4=1 D. V1=8, v2=8, v3=8, v4=8
解析:
程序使用 for 循环遍历字符串 s,直到遇到空字符 (\0)。
switch 语句处理:
对每个字符,switch 语句根据字符的值进行匹配:
字符 '1':
匹配到 case '1',v1++ 增加 1,然后 break 跳出 switch。
字符 '2':
匹配到 case '2',v2++ 增加 1,然后 break 跳出 switch。
字符 '3':
匹配到 case '3',v3++ 增加 1,但没有 break,因此会继续执行到 case '2',v2++ 增加 1,然后 break 跳出 switch。
字符 '4':
没有匹配的 case,执行 default,v4++ 增加 1,但没有break,因此会继续执行到case‘1’,v1++,然后break跳出switch
因此,字符处理如下:
1 (4次): v1 增加 5
2 (3次): v2 增加 3
3 (1次): v3 增加 1
4 (1次): v4 增加 1
解答:
B
14. 有如下说明:int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, *p = a; 则数值为9的表达式是()
A. *P+9 B. *(p+8) C. *p+ = 9 D. p+8
解析:
A. *p + 9
计算结果是 1 + 9 = 10,不是 9。
B. *(p + 8)
p + 8 指向 a[8],即 *(p + 8) = a[8] = 9,这是正确的。
C. *p += 9
这是一个赋值操作,将 *p(即 a[0])加 9,结果并不返回一个数值,而是将 1 修改为 10。
D. p + 8
这只是返回指针 p 加上 8,得到的是指向 a[8] 的指针,而不是数值。
解答:
B
15. 以下程序的输出结果是()
#define f(x) x*x
Void main()
{
Int a = 6, b = 2, c;
C = f(a)/f(b);
Printf(“%d\n”, c);
}A. 9 B. 6 C. 36 D.18
解析:
C=f(a)/f(b)->C=6*6/2*2->C=6*3*2->C=36
解答:
C
第二部分 编程题
1. 编写strcpy函数,已知strcpy函数的原型是: char *strcpy(char *strDest, const char *strSeC);不调用C++/C 的字符串库函数,请编写函数strcpy。(10分)
代码解答:
#include <stdio.h>char *strcpy(char *strDest, const char *strSrc) {char *ptr = strDest; // 保存目标字符串的起始位置// 循环复制字符,直到遇到字符串结束符 '\0'while (*strSrc != '\0') {*ptr = *strSrc; // 复制字符ptr++; // 移动目标字符串指针strSrc++; // 移动源字符串指针}*ptr = '\0'; // 添加字符串结束符return strDest; // 返回目标字符串的指针
}int main() {char dest[50]; // 确保目标字符串有足够的空间const char *src = "Hello, World!";strcpy(dest, src); // 调用自定义 strcpy 函数printf("%s\n", dest); // 打印复制的字符串return 0;
}
2. 写一个函数找出一个整数数组中, 第二大的数。 自己设计函数的形式参数和返回值。(10分)
代码解答:
#include <stdio.h>
#include <limits.h>int findSecondLargest(int arr[], int size) {if (size < 2) {// 如果数组元素少于2个,无法找到第二大数return INT_MIN; // 返回最小整数作为错误指示}int first = INT_MIN; // 初始化最大值int second = INT_MIN; // 初始化第二大值for (int i = 0; i < size; i++) {if (arr[i] > first) {second = first; // 更新第二大数first = arr[i]; // 更新最大数} else if (arr[i] > second && arr[i] != first) {second = arr[i]; // 更新第二大数}}return (second == INT_MIN) ? INT_MIN : second; // 返回第二大数或指示未找到
}int main() {int arr[] = {5, 1, 3, 9, 7};int size = sizeof(arr) / sizeof(arr[0]);int secondLargest = findSecondLargest(arr, size);if (secondLargest != INT_MIN) {printf("第二个最大数是: %d\n", secondLargest);} else {printf("没有第二个最大数\n");}return 0;
}
第三部分 开放题
请清晰、简要的分析思路和步骤, 也可以画图等形式呈现。
假如让你主导设计和研发一款“校园图书管理系统”, 你会去怎么做?(提示:可以考虑需求、设计、容量、性能等各个方面)
思路:
需求分析
用户角色:
学生:借阅、归还、查询图书。
教师:借阅、归还、查询图书,推荐书籍。
管理员:添加、修改、删除图书,管理用户。
功能需求:
图书管理:添加、修改、删除图书信息。
用户管理:注册、登录、角色管理。
借阅管理:借书、还书、查询借阅记录。
查询功能:按书名、作者、ISBN、类别等搜索图书。
统计功能:借阅情况统计、用户活跃度分析。
系统设计
数据库设计:
设计数据表结构(如用户表、图书表、借阅记录表),考虑数据的完整性和约束条件。
用户界面设计:
确定用户界面的风格和布局,确保友好和易用。
三、周总结
学习内容概述
1. 位域(Bit Fields):
位域用于在结构体中精确控制数据成员的位数分配,通常在硬件编程中用于节省内存。
2. 共用体(Union):
多个数据成员共享同一块内存,但只能同时使用其中一个,主要用于节省内存。
3. 枚举(Enum):
定义一组命名常量,通常表示有限的选项,适合在需要明确选项的场景中使用。
4. 数据结构基本概念:
学习了逻辑结构与物理存储结构,包括集合结构、线性表、树形结构等。
5. 线性表:
掌握了顺序表和链表的实现原理,并编写了一个基于顺序表管理学生信息的项目,包含插入、删除、查找等操作。
6. 单链表:
学习了单链表的概念与相关操作,如头插法、尾插法创建链表,链表遍历,任意位置插入、删除和修改节点等。
学习难点
1. 位域的内存对齐与实际内存使用:
如何在数据类型之间分配适当的位数,同时避免浪费内存。
2. 共用体的使用规则:
确保在同一时间只使用共用体中的一个成员,避免数据损坏。
3. 顺序表的边界检查与内存管理:
在插入、删除操作中,确保操作位置合法,并通过动态分配内存管理顺序表的扩展和缩减。
4. 链表操作:
包括单链表的头插、尾插等基本操作,尤其在任意位置插入、删除节点时,如何正确维护链表的结构和长度。
5. 数据移动与去重功能:
在顺序表中插入和删除元素时,如何正确移动数组元素,并通过嵌套循环实现去重功能。
主要事项
1. 位域:
确保位域的成员定义不超过数据类型的最大位数,正确控制内存使用。
2. 共用体:
共用体中同时只能存储一个数据成员,必须合理控制成员的访问,避免数据覆盖。
3. 顺序表的操作:
顺序表的长度不能超过数组的容量,在操作过程中需动态调整顺序表长度,并在插入和删除操作时及时进行边界检查。
4. 单链表的创建与操作:
掌握头插法和尾插法的使用,在任意位置插入、删除、修改和查找节点时,确保链表结构的完整性和高效性。
5. 字符串操作与查找算法:
在管理学生信息时,正确使用`strcmp`函数进行字符串比较,确保查找、修改和去重操作的准确性。
未来学习的重点
1. 深入理解位域的应用场景:
特别是位域在硬件编程中的实际应用,如嵌入式系统中的内存优化。
2. 共用体的实际应用:
在复杂的资源受限场景下如何通过共用体节省内存,同时避免数据冲突或丢失。
3. 链表的高级操作与复杂数据结构:
进一步学习链表的高级操作(如双向链表、循环链表),并探索栈、队列、哈希表等复杂数据结构。
4. 优化顺序表的查找与去重操作:
通过引入二分查找、哈希表等高效算法,优化顺序表的查找和去重功能。
5. 链表的内存管理:
深入学习链表的内存管理,尤其是在动态申请和释放内存时,如何避免内存泄漏问题。