数据结构（Day18）

一、周学习内容

1、9.18

数据结构（Day15）-CSDN博客

2、9.19

数据结构（Day16）-CSDN博客

3、9.20 

1. 链表

   1. 目的

      1. 插入删除不需要移动任何节点（元素）。

      2. 不需要预估存储空间大小，长度动态增长或减小。

   2. 概念

      1. 采用链式存储的线性表。

   3. 链表的种类

      • 

2. 单向链表

   • 单向链表的概念

     • 每个节点都有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. 链表的内存管理：

深入学习链表的内存管理，尤其是在动态申请和释放内存时，如何避免内存泄漏问题。