成都信息工程大学807程序设计基础易错知识点汇总

🌸易混知识点

关于new delete 与malloc free 的联系与区别描述？》
- 用malloc函数需要指定内存分配的字节数并且不能初始化对象，new 会自动调用对象的构造函数
- delete 会调用对象的destructor，而free 不会调用对象的destructor
- 都是在堆上取得内存。

char *p1 = "123", *p2 = "ABC", str［50］= "xyz";
strcpy(str + 2, strcat(p1, p2));
cout << str;
<!--0-->
 char str[20]="0123456789"; int a=strlen(str); //a=10; >>> strlen 计算字符串的长度，以结束符 0x00 为字符串结束。 int b=sizeof(str); //而b=20; >>> sizeof 计算的则是分配的数组 str[20] 所占的内存空间的大小，不受里面存储的内容改变。 上面是对静态数组处理的结果。
 <!--1-->

return 后面括号的值不一定是函数的值，譬如函数返回值与return 类型不一致需要类型转换，返回值为 int ，retun 3.2 ，那么肯定会进行转换的

实型字面值常量有两种表示方式：小数形式和指数形式

小数形式：由最前面的额正负号，数字0-9和小数点组成，不允许有其他符号；

指数形式；包括指数和尾数两个不可缺少的部分，用符号E(e)分割；E(e)左边是尾数，为十进制整数或小数形式的实数，右边为指数，必须为十进制整数，表示乘以10的多少次方

BSS（Block Started by Symbol）通常是指用来存放程序中未初始化的全局变量和静态变量的一块内存区域。特点是:可读写的，在程序执行之前BSS段会自动清0。所以，未初始的全局变量在程序执行之前已经成0了。
A.单链表的每个节点都具有唯一的前驱节点和唯一的后继节点，所以当两个单链表存在相交的节点时，这两个链表则同时拥有这个节点，以及这个节点的所有后继节点，当这个公共节点是尾节点时，他们则只含有公共一个节点——-尾节点。

B.快慢指针是判断单链表是否有环的一种方法：两个指针，每次移动的步长为2叫做快指针，每次移动步长为1的指针叫做慢指针。快慢指针同时从头结点出发，当快指针率先到达NULL的时候，则说明此单链表中不存在环，当快指针追上慢指针的时候，说明此单链表中存在环。

C.有环的单向链表和无环的单向链表不能相交，因为当相交的时候，无环的单向链表也会被迫存在一个环，只不过这个环的”起点“可能不是原来单向链表的头结点。

4.两个单向链表之间相交可以存在环。
存在这样的线性表：表中各结点都没有直接前趋和直接后继。–空表

%%d=%%和d

%%在屏幕上显示为%

d还是d

所以是和k没有关系了~

队列实现方式有链表存储和顺序表存储两种：链表存储可设计为带有尾指针的单链表，即可高效实现入队出队，无需循环链表；顺序表存储为解决存储空间浪费而设计为循环队列。因此循环队列仅有顺序表存储结构，与循环链表毫无关系。
一个非空的数据结构如果满足以下两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件，则称为线性结构，在数据结构中习惯称为线性表。双向链表结点具有两个指针域，属于线性结构， A 选项错误。循环链表所有结点的指针域都为非空，属于线性结构， B 选项错误。循环链表是链表，循环队列属于队列，队列只能在队尾入队，在排头退队，链表可以在任何位置插入、删除， C 选项错误。双向链表结点具有多个指针域， D 选项正确
%X.Ys的格式化输出，X是总长度，Y是从字符串中从左边取Y位，剩下的位数补空格

对于数据结构课程而言，简单地说，线性结构是n个数据元素的有序（次序）集合。

1．集合中必存在唯一的一个"第一个元素"；

2．集合中必存在唯一的一个"最后的元素"；

3．除最后元素之外，其它数据元素均有唯一的"后继"；

4．除第一元素之外，其它数据元素均有唯一的"前驱"。

数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。

非线性结构：数学用语，其逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。

A选项：在链表中，如果每个结点有两个指针域，则该链表一定是非线性结构，错，类似于传统的双链表，一个指向前一个结点，一个指向后一个结点，这种双链表还是一个线性结构。

B选项：在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是非线性结构。对，如果有两个结点的同一个指针域的值，那么被指向的这个点，有两个前驱，违背了唯一的特点，所以必须是非线性结构。

C选项：在链表中，如果每个结点有两个指针域，则该链表一定是线性结构，错。例如变种的双链表，一个指向后继结点，一个指向链表中的任意结点。如果指向同一结点的话，就类似B选项，所以这个选项是错的。

D选项：在链表中，如果有两个结点的同一个指针域的值相等，则该链表一定是线性结构，错。一个普通的链表中，不同的结点值可以相等，但是这种链表是线性结果。所以这个选项是错的

广义表的长度：若广义表不空，则广义表所包含的元素的个数，叫广义表的长度，数第一层括号内的逗号数目。

**广义表的深度： 广义表中括号的最大层数叫广义表的深度。**

长度：最外层包含元素的个数，即去掉最外层括号后含有的元素个数。

深度：表中含有括号数最多的括号层数加一。

head :返回列表的第一个元素，（不带括号）

tail：返回列表删除第一个元素后剩余的列表（带括号）

线性链表中的各元素在存储空间中的位置不一定是连续的，且各元素的存储顺序也是任意的
顺序表中逻辑相邻物理位置必定相邻。单链表中逻辑相邻物理位置不一定相邻。
结构体变量不管其包含有多少个成员，都应当看成是一个整体。在程序运行

期间，只要在变量的生存期内，所有成员一直驻留在内存中，不可能出现有的成员驻留内存，有的成员不驻留内存的情况
C 语言中用 “%%” 打印输出字符 “%”, 所以 %%d, 输出为 %d 两个普通字符 , 而不是格式控制符 “%d” 的含义
ava中只有byte, boolean是一个字节, char是两个字节, 所以对于java来说127不会发生溢出, 输出328
- 但是对于c/c++语言来说, char是一个字节, 会发生溢出, 对127加一发生溢出, 0111 1111 --> 1000 0000, 1000 0000为补码-128, 所以结果为200-128=72

广义表是一个递归的定义，它的元素可以是 (1)单个元素 (2)子表

一对确定的（表头，表尾）可以唯一确定一个广义表：

  1. 表头：广义表的第一个元素(广义) ，可能是一个元素(狭义)，也可能是一个子表(但它作为第一个元素(广义))

  2. 表尾：除表头外其余元素组成的子表，一定是一个表！

举一些特殊的例子：

表A = (e) ，则表头为e，表尾为() 

表B = ( ) ，即空表，长度=0
表C = (( ))，长度=1，表头为( )，表尾为( )

拆分二维数组

int a[4][3] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };

拆分成：

int b[3] = {1, 2, 3 };

int c[3] = {4, 5, 6 };

int d[3] = {7, 8, 9 };

int e[3] = {10, 11, 12 };

\2. 为何拆分？

以“b[3] = {1, 2, 3 }”为例：b是数组第一个元素的地址，这里b相当于整型指针！上述b，c，d，e都是整型指针。

那么就有：a[4] = { b, c, d, e };

这是一个一维数组，其中的**元素都是整型指针**。a是什么？是数组a中第一个元素b的地址！

根据上述这种理解，发现可以很方便的解出这道题。

分析：AC选项先看“int ( * prt)[3]=a”,相当于：int b[3];int *prt = &b;

即定义了一个指向“数组第一个元素的地址”的指针prt；而从1,2分析来看，a表示的正是b的地址。所以，这里等价于：prt = a。

我们看AC选项，先把ptr都换成a。

A：* (( * prt+1)[2])

*a 即a[0]，也就是b；

( b+1) 表示 元素2的地址，也就是a[0][1]的地址；

(b+1)[2] → *( (b+1) + 2 ) = *(b+3) = b[3]，越界了！其实就是c[0]，VS上验证过，输出也是4.

而答案提供的相当于*(b[3])，连数组元素都算不上！

*注：**下标和指针转化公式：***(a+n) = a[n]*

C：( * prt+1)+2( * a+1)+2 等价于(b+1) + 2 = b+3，是4的地址，也就是c[0]的地址；同样错误。不过可以验证*(( * prt+1)+2)，输出为4.

5. B选项分析：* ( * (p+5))

int *p = a[0]，相当于int *p = b，遇到p直接用b替换就行了！* (p+5)等价于b[5]，也就是c[2]，元素6，前面还多个*，所以这个错的也很明显。

6. D选项

**下标和指针转化公式：*****(a+n) = a[n]**，这个正反都可以使用，而且很好用。

%% 可以输出 %
用十进制整数来表示输出的最少位数。若实际位数多于定义的宽度，则按实际位数输出，若实际位数少于定义的宽度则补以空格或0。
不同数据类型之间的差别在于数据的表示范围及精度上，一般情况下，数据的表示范围越大、精度越高，其类型也越“高级”。
- 赋值运算中如果左值精度比右值精度低，将会出现截断，会导致精度丢失。
- 当函数调用时，所传实参与形参类型不一致时，也会把实参自动转换为形参类型后再赋值（类型以形参为准）
C++
1. char、short、int、long、bool 基本类型都可以用于switch语句。
2. float、double都不能用于switch语句。
  1. enum类型，即枚举类型可以用于switch语句。
  2. 所有类型的对象都不能用于switch语句。
  3. 字符串也不能用于switch语句
C语言中的文件的存储方式有（可以顺序存取，也可随机存取）
C语言是一种结构化程序设计语言
空指针是一个特殊的指针值。
- 空指针是指可以确保没有指向任何一个对象的指针。通常使用宏定义NULL来表示空指针常量值。NULL就代表系统的0地址单元
- 空指针确保它和任何非空指针进行比较都不会相等，因此经常作为函数发生异常时的返回值使用。
在printf中的%作为转义符，两个%才相当于1个%
free掉一个指针后，指针的值是不会自动置为NULL的，当然其指向的内存已经被释放，可以重新分配给其他进行使用，此时该指针被称为野指针。
- 对野指针进行操作，可能会破坏内存结构，因为并不知道当前指针指向的内容是什么，所以一般在free操作结束后，由程序猿将指针置为NULL。
C语言的指针的数据类型声明的是指针实际指向内容的数据类型
c = c^32 大小写互换
当顺利执行了文件关闭操作时，fclose函数的返回值是：如果正常关闭了文件，则函数返回值为0；否则，返回值为非0

以下函数用法正确的个数是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void test1(){
    unsigned char array[MAX_CHAR+1],i;
    for(i = 0;i <= MAX_CHAR;i++){
        array[i] = i;
    }
}
char*test2(){
    char p[] = "hello world";
    return p;
}
char *p = test2();
void test3(){
    char str[10];
    str++;
    *str = '0';
}


> 重点不在于CHAR_MAX的取值是多少，而是在于i的取值范围是多少。
>
> 一般char的取值范围是-128到127，而u char 则是0~255，所以i的取值范围是0~255.
>
> 所以当CHAR_MAX常量大于255时，执行i++后，i不能表示256以上的数字，所以导致无限循环。
>
> 第二个问题：
>
> 重点在于函数中p的身份，他是一个指针，还是数组名；
>
> 如果是指针p，则p指向存放字符串常量的地址，返回p则是返回字符串常量地址值，调用函数结束字符串常量不会消失（是常量）。所以返回常量的地址不会出错。
>
> 如果是数组p，则函数会将字符串常量的字符逐个复制到p数组里面，返回p则是返回数组p，但是调用函数结束后p被销毁，里面的元素不存在了。
>
> 例子中p是数组名，所以会出错，p所指的地址是随机值。
>
> 若是把char p[]="hello";改成char *p="hello";就可以了。
>
> 第三个问题：
>
> 重点在于str++;这实际的语句就是str=str+1;而str是数组名，数组名是常量，所以不能给常量赋值。（可以执行str+1，但是不能str=.）

feesk中seek_end 的文件末尾指针在末尾最后一个字符后面，而非最后一个字符
使用”w”写文件也可以使用fwrite
对于32位系统，定义 int **a[3][4], 则变量a占有的内存空间为
- 此处定义的是指向指针的指针数组，对于32位系统，指针占内存空间4字节，因此总空间为3×4×4＝48。

用右左法则来看，首先往变量a的右边看，是【3】，再往左看，是，所以它首先是一个指针数组，数组里存放3个指针，然后再往右看是【4】，再往左看，是int *，说明前面3个指针每个指针都指向一个数组，每个数组里存放4个int *类型的指针，所以34有12个二级指针，每个指针在32位系统占4个字节，所以48个字节

可以从简单到难进行理解，int *a[3]是一个指针数组数组中的每个元素就是一个指针，a的大小是3*4 = 12；int *a[3][4]是一个二维的指针数组，数组中的每一个元素是一个指针，a的大小是3*4*4 = 48；int **a[3]也是一个指针数组，只不过该数组的元素是一个二级指针，但是二级指针的本质还是指针，所以a的大小是3*4 = 12；int **a[3][4]是一个二维数组，数组中的每一个元素是一个二级指针，所以a的大小是3*4*4 = 48，就这么简单，不需要去分析什么从左到右从右到左看，反而容易搞混;
因为[]的优先级是大于号的优先级的，所以先从变量名a向右看是a[3][4]是一个二维数组，然后再将该二维数组看作一个整体向左看，int *是一个二级指针，说明该二维数组是一个数据类型为二级指针的指针数组，这种理解方法就跟普通的指针数组理解方式一样，比如：int *a[3]
我们理解是先向右看是a[3]拥有三个元素的数组，再向左看，int *说明数组的元素类型是整形的指针类型，所以是一个指针数组
```

%3o表示以八进制数形式输出，占3个空格的位置，右对齐，左边多余的位置补

空格，但实际数据的宽度为4大于规定的宽度，所以此时按实际宽度输出，故第一个y的输出为│4630│。%8o与%3o的差别就在于输出占8个空格的位置，所以左边要补4个空格，故第二个y的输出也为│□□□□4630│.%#8o与%8o的差别只是输出时必须输出八进制前导0，所以第三个y的输出为│□□□04630│.%08o与%8o的差别只是输出时左边多余的位置补0，所以第四个y的输出为│00004630│
2014对应的二进制为：0000 0000 000 0000 0000 0111 1101 1110
- 而x|（x+1）的作用是对一个数中二进制0的个数进行统计
1、【编译】是把c源程序翻译成汇编代码：.s；

2、【汇编】是把汇编代码翻译成二进制目标代码：.obj

3、【链接】是把多个二进制目标代码文件链接成一个可执行程序；因为一个工程某个文件调用了其他c文件的函数或变量一个程序需要上面三个步骤才能由源程序变成可执行程序。

      union s{
          int i;
          char c;
          float a;
      }temp;
      temp.i = 266;
      printf("%d", temp.c);

      //输出是10
      因为266>256.也因为temp一共占有四个字节，i和ch共用内存空间，但是ch 只占据最低的一个字节，即最低的8位，所以输出c的值也是只能输出这一字节内存中的二进制数表示的数，如果赋值的i是100,将会正常输出100

<!--5-->

      int fseek(FILE *stream, long offset, int fromwhere); 

      函数fseek将文件位置指针重定位到fromwhere（SEEK_SET文件头0,SEEK_CUR文件当前位置1,SEEK_END文件末尾2）开始偏移offset个字节的位置；返回成功0，失败-1；

      long ftell(FILE *stream);

      返回文件位置指针当前位置相对于文件首的偏移字节数；
<!--6-->

对指针变量赋0值和不赋值是不同的。指针变量未赋值时，值是随机的，是垃圾值，不能使用的，否则将造成意外错误。而指针变量赋0值后，则可以使用，只是它不指向具体的变量而已。

面试问题

无法高效获取长度，无法根据偏移快速访问元素，是链表的两个劣势。然而面试的时候经常碰见诸如获取倒数第k个元素，获取中间位置的元素，判断链表是否存在环，判断环的长度等和长度与位置有关的问题。这些问题都可以通过灵活运用双指针来解决。

Tips：双指针并不是固定的公式，而是一种思维方式~

先来看”倒数第k个元素的问题“。设有两个指针 p 和 q，初始时均指向头结点。首先，先让 p 沿着 next 移动 k 次。此时，p 指向第 k+1个结点，q 指向头节点，两个指针的距离为 k 。然后，同时移动 p 和 q，直到 p 指向空，此时 q 即指向倒数第 k 个结点。

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode *p = head, *q = head; //初始化
        while(k--) {   //将 p指针移动 k 次
            p = p->next;
        }
        while(p != nullptr) {//同时移动，直到 p == nullptr
            p = p->next;
            q = q->next;
        }
        return q;
    }
};

获取中间元素的问题。设有两个指针 fast 和 slow，初始时指向头节点。每次移动时，fast向后走两次，slow向后走一次，直到 fast 无法向后走两次。这使得在每轮移动之后。fast 和 slow 的距离就会增加一。设链表有 n 个元素，那么最多移动 n/2 轮。当 n 为奇数时，slow 恰好指向中间结点，当 n 为偶数时，slow 恰好指向中间两个结点的靠前一个(可以考虑下如何使其指向后一个结点呢？)。

下述代码实现了 n 为偶数时慢指针指向靠后结点。
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode *p = head, *q = head;
        while(q != nullptr && q->next != nullptr) {
            p = p->next;
            q = q->next->next;
        }
        return p;
    } 
};

是否存在环的问题。如果将尾结点的 next 指针指向其他任意一个结点，那么链表就存在了一个环。

上一部分中，总结快慢指针的特性 —— 每轮移动之后两者的距离会加一。下面会继续用该特性解决环的问题。
当一个链表有环时，快慢指针都会陷入环中进行无限次移动，然后变成了追及问题。想象一下在操场跑步的场景，只要一直跑下去，快的总会追上慢的。当两个指针都进入环后，每轮移动使得慢指针到快指针的距离增加一，同时快指针到慢指针的距离也减少一，只要一直移动下去，快指针总会追上慢指针。

据上述表述得出，如果一个链表存在环，那么快慢指针必然会相遇。实现代码如下：

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        while(fast != nullptr) {
            fast = fast->next;
            if(fast != nullptr) {
                fast = fast->next;
            }
            if(fast == slow) {
                return true;
            }
            slow = slow->next;
        }
        return nullptr;
    }
};

最后一个问题，如果存在环，如何判断环的长度呢？方法是，快慢指针相遇后继续移动，直到第二次相遇。两次相遇间的移动次数即为环的长度。

由于链表中从高位到低位存放了数字的二进制表示，因此我们可以使用二进制转十进制的方法，在遍历一遍链表的同时得到数字的十进制值。

以示例 1 中给出的二进制链表为例：

表示 n 是二进制整数。

链表的第 1 个节点的值是 1，这个 1 是二进制的最高位，在十进制分解中，1 作为系数对应的 2^2^
的指数是 2，这是因为链表的长度为 3。我们是不是有必要一定要先知道链表的长度，才可以确定指数 2 呢？答案是不必要的。

每读取链表的一个节点值，可以认为读到的节点值是当前二进制数的最低位；
当读到下一个节点值的时候，需要将已经读到的结果乘以 2，再将新读到的节点值当作当前二进制数的最低位；

如此进行下去，直到读到了链表的末尾。

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        ListNode* cur = head;
        int ans = 0;
        while (cur != nullptr) {
            ans = ans * 2 + cur->val;
            cur = cur->next;
        }
        return ans;
    }
};
     
     
     5÷2=2余1 
     2÷2=1余0 
     1÷2=0余1  
      ===> 得出二进制 101 .
     反推回去 商 x 除数 + 余数 
     => 0 x 2 + 1 = 1 
     -> 1 x 2 + 0 = 2
     -> 2 x 2 +1 = 5

C语言语法规定，字母e或E之前必须要有数字，且e或E后面的指数必须为整数。如e3、5e3.6、.e、e等都是非法的指数形式。
在方法体中定义的局部变量在该方法被执行时创建：错
- 不是局部变量再该方法被执行/调用时创建，而是应该为在该变量被声明并赋值时创建，可以理解为当代码执行到该变量被赋值的代码是才被创建。

C语言的源程序加工包括三步：预处理、编译和链接。

其中源程序加工的编译阶段又可细分为：预处理，编译，汇编三个阶段。

即C语言由源代码生成可执行程序的过程为：C源程序→编译预处理→编译→汇编程序→链接程序→可执行文件。

①预处理：

1、头文件的包含，#include预处理指令。

2、define定义符号的替换

#define  预处理指令

注释删除

②编译：

1、把C语言代码翻译成汇编代码。

2、语法分析
     
3、词法分析

4、语义分析

5、符号汇总

③汇编

1、把汇编指令翻译成二进制指令

2、形成符号表

④链接

1、合并段表

2、符号表的合并和符号表的重定位

函数fscanf不能从标准输入流读取数据 –错
程序员必须明确地用函数fopen打开标准输入流、标准输出流和标准错误流 –错
程序必须明确地调用函数fclose关闭文件 – 错

 int _tmain(int argc, _TCHAR* argv[])
 {
     char *p1 = "h
        ello";
     char *p2 = "world";
     char *p3 = "a piece of cake";
     char *str[] = { p1, p2, p3 };
     cout << sizeof(*str[0]) << " " << typeid(str[0]).name() << " " << *(str[0] + 1) << endl;//typeid是类型
     cout << sizeof(*&str[0]) << " " << typeid(&str[0]).name() << " " << *(&str[0] + 1) << endl;
     cout << sizeof(*str) << " " << typeid(str).name() << " " << *(str + 1) << endl;
     cout << sizeof(*&str) << " " << typeid(&str).name() << " " << *(&str + 1) << endl;
     return 0;
 }
 运行结果：
 1 char * e
 4 char * * world
 4 char * [3] world
 12 char * (*)[3] 00F7F734
 能看懂这个你就知道了，这个地方+1的时候都是说步长，步长就是说+1前面的这个对象 所指向的 数据类型的长度，比如 &str[0]类型是char * * 所指向的是char * 长度是指针的长度（不同机器不同）
<!--12-->

如果要输出剩余字符串，可用

1
fprintf(stderr, ``"%s\n"``, s);

● itoa()：将整型值转换为字符串。
● ltoa()：将长整型值转换为字符串。
● ultoa()：将无符号长整型值转换为字符串。
● gcvt()：将浮点型数转换为字符串，取四舍五入。
● ecvt()：将双精度浮点型值转换为字符串，转换结果中不包含十进制小数点。
● fcvt()：指定位数为转换精度，其余同ecvt()。

itoa()函数有3个参数：第一个参数是要转换的数字，第二个参数是要写入转换结果的目标字符串，第三个参数是转移数字时所用 的基数。在上例中，转换基数为10。10：十进制；2：二进制...

itoa并不是一个标准的C函数，它是Windows特有的，如果要写跨平台的程序，请用sprintf

# include <stdio.h>
# include <stdlib.h>
void main (void)
{
int num = 100;
char str[25];
itoa(num, str, 10);
printf("The number 'num' is %d and the string 'str' is %s. \n" ,
num, str);
}


int atoi (char s[])
{
int i,n,sign;
for(i=0;isspace(s[i]);i++)//跳过空白符;
sign=(s[i]=='-')?-1:1;
if(s[i]=='+'||s[i]==' -')//跳过符号
  i++;
for(n=0;isdigit(s[i]);i++)
       n=10*n+(s[i]-'0');//将数字字符转换成整形数字
return sign *n;

● atof()：将字符串转换为双精度浮点型值。
● atoi()：将字符串转换为整型值。
● atol()：将字符串转换为长整型值。
● strtod()：将字符串转换为双精度浮点型值，并报告不能被转换的所有剩余数字。
● strtol()：将字符串转换为长整值，并报告不能被转换的所有剩余数字。
● strtoul()：将字符串转换为无符号长整型值，并报告不能被转换的所有剩余数字。

int f1(float);
int f2(char);
void f3(float);
int (*pf)(float);

函数指针变量：

函数指针变量的声明方法为：

返回值类型 ( * 指针变量名) ([形参列表]);
根据定义，

int(*pf)(float); int (*p)(float)=&f1;
pf,p都是函数指针变量。

函数地址：

在编译时，每一个函数都有一个入口地址，该入口地址就是函数指针所指向的地址。

函数地址的获取，可以是函数名，也可以在函数名前加取地址符& 。

C错误是因为函数形参类型不匹配。

函数指针所指向的函数，返回值类型，形参列表必须完全匹配，对函数指针赋值可以采用以下方式pf＝&p1或者pf＝p1
按位运算是对字节或字中的实际位进行检测、设置或移位, 它只适用于字符型和整数型变量以及它们的变体, 对其它数据类型不适用。无论是float 还是double,在内存中的存储分为三部分：符号位，指数位，尾数位；位运算符对它们没有意义
float类型的变量赋值后为什么必须在值后加”f”/“F”
float x = 3.4F;
这里将“3.4”赋值给float类型的变量x，如果不加F，系统会默认把赋值的数字当作double类型处理 1，然后在把这个double类型的值赋给float类型，这样就会出现精度丢失。
float y = 3F;
这里将“3”赋值给float类型的变量y，如果将整数类型的“3”赋值给float，系统会自动将其转化为double类型1，然后再赋值给float类型，这样虽然会编译成功，但会导致精度缺失。
常量存储在常量缓冲区中，有且只有一份，常量缓冲区中的值默认空间大小，如果是整数，默认空间大小为32bit—-int，如果是小数，默认空间大小为64bit—-double。
%f用于输入float,%lf用于输入double,%le用于科学计数法输入double型变量
形参与实参的之间的传递分类
1、按值传递（实形无联系）

按值传递就是平常编程中经常用到的，定义一个基本数据类型的变量，在调用某函数时把该变量作为函数的实参传递给函数。这种传递方式采用的是单向值传递，实形无联系，形参改变不影响实参。

2、按地址传递（通过操作形参可能会改变实参）

按地址传递主要出现在函数参数是指针变量、数组等的时候。

注意：

实质上用指针做函数参数的情况下，在调用函数时，将实参变量的传递给形参变量，采取的依然是单向值传递。如果在被调函数中只是单纯改变了形参指针变量的值，在函数调用结束后这些形参被销毁，是不会影响调用函数时传入实参指针变量值。

只有当你在被调函数中通过操作形参指针变量，去改变了指针指向变量的值时，才可以改变实参指针变量所指向变量的值。也只有这种情况下形参改变才可能影响实参。

假设函数原型和变量说明如下：

1	void f3(int(*p)[4]);``int a[4]={1，2，3，4}，``int b[3][4]={{1，2，3，4}，{5，6，7，8}，{9，10，11，12}};

下面调用非法的是

f3(&a);
1
2

-

f3(b[1]);
1
2

-

f3(&b[1]);
1
2

-

f3(b);

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

       > 选**B**。根据题目结合选项来看考察的是对函数的传参调用，其中参数涉及到**数组指针** 。 
       >
       > void f3(**int(\*p)[4]**);  其参数是**数组指针** ，指向数组p的指针。
       >
       >
       > -     选项A：f3(**&a**); 参数为一个地址，符合指针定义。   
       > -     选项B：f3(**b[1]**); 参数为一个数组的具体元素，不符合指针定义。**所以B是非法的调用。**   
       > -     选项C：f3(**&b[1]**); 参数为一个数组元素的地址，符合指针定义。   
       > -     选项D：f3(**b**); 参数为数组名，表示该数组的首地址，符合指针定义。
       >
       > <font color='red'>`b[1]`和`&b[1]`虽然值相等，但是含义不一样，`&b[1]`是行指针，类型是`int (*)[4]`，和`a`的类型相同；而`b[1]`是个`int *`，和`&b[1][0]`等价。</font>
       >
       > - b[1]作为第二行数组的数组名，如果单独出现，则表示首元素的地址，即元素b[1][0]的地址，类型是int*；如果加取地址&，变成&b[1]，那么就是整个第二行数组的地址，和函数f(3)要求的形参保持一致，即该指针指向一个整型数组，数组共4个整型元素。并不是所谓的指针的<font color='red'>指针。</font>

135. C语言中，<font color='red'>未经赋值</font>的<font color='red'>全局变量</font>默认初始化为<font color='red'>0</font>，**auto类型、register类型不确定**

136. 所有的<font color='red'>静态局部变量</font>，即定义在函数内部的`static int name`形式的，默认初始化为<font color='red'>0</font>

137. 外部变量可以供其所在的程序文件中的任何函数使用   --- 错误

     - 全局变量也称为外部变量，它是在函数外部定义的变量，其作用域是从定义该变量的位置开始至源文件结束。全局变量不受作用域的影响（也就是说，全局变量的生命期一直到程序的结束）。 
       -    如果在一个文件中使用extern关键字来声明另一个文件中存在的全局变量，那么这个文件可以使用这个数据。    
       -    在全局变量前加一个static，使该变量只在这个源文件中可用，称之为全局静态变量。

138. 指针就是地址，因此一个变量的指针就是该变量的地址。请问这句话的说法是正确的吗？   <font color='red'>错误</font>

     - <font color='blue'>一个变量的指针指向的内容才是这个变量的地址</font>

139. - 若已包含标准库头文件及相关命名空间，用户也可以重新定义标准库函数，但是该函数将失去原有含义  -- <font color='red'>错误</font>
     - 若已包含标准库头文件及相关命名空间，则系统不允许用户重新定义标准库函数      --<font color='red'>正确</font>
     - 用户调用标准库函数前，不必使用预编译命令将该函数所在文件包括到用户源文件中     <font color='blue'>错误</font>
     - 用户调用标准库函数前，必须重新定义    --<font color='blue'>错误</font>
       - A选项，函数不能重新定义，只能重载，除非换作用域（那也不能叫重新定义）； B选项，<font color='red'>函数可以被重载而不能重新定义</font>，重载后函数具有不同的形参，原有定义并不失效； C选项，正确； D选项，调用库函数果断需要#include（预处理包含）头文件啊……否则找不到函数定义

140. 在 while 循环中以 EOF（<font color='red'>-1</font>） 作为文件结束标志，这种以 EOF 作为文件结束标志的文件，必须是文本文件。在文本文件中，数据都是以字符的 ASCII 代码值的形式存放。我们知道， ASCII 代码值的范围是 0~255 ，不可能出现 -1 ，因此可以用 EOF 作为文件结束标志

141. A 选项正确，`int a[10]={0, 0, 0, 0, 0}`; 前 5 个元素为 0，后面 5 个元素编译器补为 0
     B 选项正确，<font color='red'>int a[10]={ }</font>; 编译器<font color='green'>自动将所有元素置零</font>
     C 选项正确，`int a[] = {0}`; 编译器自动计算元素个数
     D 选项错误，`int a[10] = {10*a}`;a 是整型数组，10*a 操作非法

142. 排序方法    平均情况    最好情况    最坏情况    辅助空间    稳定性 

       冒泡排序     O(n^2)      O(n)       O(n^2)        O(1)        稳定 

       选择排序     O(n^2)     O(n^2)      O(n^2)        O(1)        不稳定 

       插入排序     O(n^2)      O(n)       O(n^2)        O(1)        稳定 

       希尔排序O(n*log(n))~O(n^2) O(n^1.3)    O(n^2)        O(1)       不稳定 

       堆排序     O(n*log(n))   O(n*log(n))   O(n*log(n))      O(1)       不稳定 

       归并排序    O(n*log(n))   O(n*log(n))   O(n*log(n))    O(n)          稳定 

       快速排序    O(n*log(n))   O(n*log(n))    O(n^2)         O(1)       不稳定 

       冒泡排序经过优化以后，最好时间复杂度可以达到O(n)。设置一个标志位，如果有一趟比较中没有发生任何交换，可提前结束，因此在正序情况下，时间复杂度为O(n)。选择排序在最坏和最好情况下，都必须在剩余的序列中选择最小（大）的数，与已排好序的序列后一个位置元素做交换，依次最好和最坏时间复杂度均为O(n^2)。^

     插入排序是在把已排好序的序列的后一个元素插入到前面已排好序(需要选择合适的位置)的序列中，在正序情况下时间复杂度为O(n)。堆是完全二叉树，因此树的深度一定是log(n)+1，最好和最坏时间复杂度均为O(n*log(n))。归并排序是将大数组分为两个小数组，依次递归，相当于二叉树，深度为log(n)+1，因此最好和最坏时间复杂度都是O(n*log(n))。快速排序在正序或逆序情况下，每次划分只得到比上一次划分少一个记录的子序列，用递归树画出来，是一棵斜树，此时需要n-1次递归，且第i次划分要经过n-i次关键字比较才能找到第i个记录，因此时间复杂度是\sum_{i=1}^{n-1}(n-i)=n(n-1)/2，即O(n^2)。

143. 算法的5个基本特征：确定性、有穷性、输入、输出、<font color='red'>可行性</font>。

144. 顺序查找的平均时间是多少？——<font color='red'>N/2</font>

     - 严格意义上确实 应该是(n+1)/2，因为目标数据可以在任意位置，分别查找1，2，3，4，.......，n次，一共为n*(n+1)/2，所以除以n，平均时间为(n+1)/2

145. `void hello(int a,int b=7,char* pszC="*");`

     - hello(5)

     - hello(5,8)

     - `hello(6,"#")`

     - hello(0,0,"#")

     - <font color='red'>参数从右向左匹配</font>，C项 a没有匹配到，`&quot`;相当于半个引号，`&quot ;#"=“#”`如上面D选项

       从左到右我们就说参数是  a   b   c     A，函数从右往左匹配。b,c有现有的就不给了，5给a  

       B,  8给b,5给a

        C,  那一坨给了c，6给了b,  没东西给a 。不能跳着给。6给a，b用先有的是不对的。

        D，挨个给就行了。

146. 声明一个指向含有10个元素的数组的指针，其中每个元素是一个函数指针，该函数的返回值是int，参数是int*，正确的是（）                                        

     -

(int *p[10])(int*)
1
2

-

int [10]*p(int *)
1
2

-

int (*(*p)[10])(int *)
1
2

-

int ((int *)[10])*p
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

     - 先看未定义标识符p，p的左边是*，*p表示一个指针，跳出括号，由于[]的结合性大于*，所以*p指向一个大小为10的数组，即`(*p)[10]`。左边又有一个*号，修释数组的元素，*`(*p)[10]`表示`*p`指向一个大小为10的数组，且每个数组的元素为一个指针。跳出括号，根据右边`（int  *）`可以判断（*`(*p)[10]）`是一个函数指针，该函数的参数是`int*`,返回值是int。所以选C。

147. C语言中的一个变量可以被定义为两个或多个不同的类型。请问这句话的说法是正确的吗？

     - 如果不在一个函数体中，可以的；但是如果在一个函数体中，会出现调用混淆，不允许。

       而且这是两个变量，只是变量名相同而已，被存在不同的内存单元中。

     - 如果在同一个函数内，那肯定不行，重复的定义，如果一个是<font color='red'>全局</font>一个是<font color='red'>局部</font>那就可以，还有在两个不同的函数内，也是可以的

148. 双循环链表中，任意一结点的后继指针均指向其逻辑后继。

     - 逻辑后继:<font color='green'>指在存储时按照需要给定的逻辑顺序在其后的数据块</font>。循环链表中**尾节点的逻辑后继**应该为<font color='red'>null</font>而其**后继指针指向了头节点。**

149. 递归先序遍历一个节点为n，深度为d的二叉树，需要栈空间的大小为_

     - **因为二叉树并不一定是平衡的，也就是深度d！=logn，有可能d > > logn(远大于)，所以栈大小应该是O（d）**

150. 缓存策略中基于 LRU 的淘汰策略，在缓存满时，会把最近进入缓存的数据先淘汰，以保持高的命中率

     - 刚好说反了，LRU的过程如下（其实很好理解，访问的频率越高越不该丢弃）： 

             1. 新数据插入到链表头部； 

             2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部； 

             3. 当链表满的时候，将链表尾部的数据丢弃。

151. 顺序表删除需要移动元素，而链表删除不需要移动元素

152. <font color='red'>有环的单向链表跟无环的单向链表不可能相交</font> -正确

     - 有环的单向链表和无环的单向链表不能相交，因为当相交的时候，无环的单向链表也会被迫存在一个环，只不过这个环的”起点“可能不是原来单向链表的头结点

153. 如果两个单向链表<font color='red'>相交</font>，那这两个链表都一定不存在环 -错误

     - 单向链表相交<font color='red'>可以存在环</font>

     ![img](https://uploadfiles.nowcoder.com/images/20180717/4256577_1531815312082_BA893B14C7935C1B5F8296D83D999DDA)

     - 意思就是<font color='red'>链表相交，要么都有环，要么都无环</font>，不可能出现其他情况，出现其他情况就不是线性结构就不符合链表的定义

154. 执行"int x=1;int y=~x;"语句后,y的值为？ ——-2

     - 假设int占2个字节，那么1的二进制表示是 0000 0001 ，~表示按位取反，则 0000 0001变为 1111 1110，在计算机中整数用补码形式表示，正数的补码是它本身，负数的补码是原数值除符号位按位取反再加一，由补码求原数值也是按位取反再加一，那么 1111 1110 除符号位按位取反再加一变成 1000 0010，即 -2。

155. 若函数的定义出现在主函数之前且仅被主函数使用，则可以不必再说明

     - 正确（如果不是仅被主函数调用，就是错的）

156. 若一个函数（非主函数）没有return语句，返回类型是void

     - 错误（构造函数和析构函数都没有返回类型，也没有return语句）

157. <font color='red'>++、--不算做赋值运算</font>，只能说是一个表达式

158. 有char a[10]=”abc”;，则strlen(a)的值为3，<font color='red'>strlen</font>函数返回字符串的<font color='blue'>长度</font>，不包括末尾的’\0，sizeof(a)才是10

159. \#include命令的功能是（）

     - 在<font color='red'>命令处</font>插入一个文本文件（注意<font color='red'>不是</font>在<font color='blue'>文件首部</font>插入一个头文件）

160. 当顺利执行了文件关闭操作时，<font color='blue'>fclose函数的返回值</font>是（）

     - 如果<font color='red'>正常关</font>例了文件，则函数返回值为<font color='red'>0</font>；否则，返回值为<font color='red'>非0</font>

161. 定义类型并不会分配空间，只有在<font color='blue'>定义变量</font>时才会分配内存空间

162. `int  a[10];`

     - 问下面不可以表示a[1]地址的是（）

       - &a[0] + 1
       - <font color='blue'>a + sizeof(int)  </font>
       - (int*)&a + 1
       - `(int*)((char*)&a + sizeof(int))`

     - a为数组的时候 
       <font color='red'>&a + 1</font> 移动sizeof(数组)字节 

        <font color='red'> a + 1 </font>或者 <font color='red'>&a[0] + 1</font> 移动sizeof(int) ,即移动到<font color='red'>下一个数组元素 </font>

       B是指向a[4]

       C将a变成了指针 int *类型，指针+1 都是移动sizeof(int) ，移动到下一个元素的 

        D指针绕来绕去的，变成char* 后 +4 ，移动 4* (sizeof(char))，移动四个字节，然后又重新强转成了int*,依然指向下一个元素

163. 已知ii，j都是整型变量，下列表达式中，与下标引用`X[ii][j]`不等效的是（）

     - *（X[ii]+j）

     - <font color='red'>*(X+ii)[j]</font>

     - <font color='red'>*(X+ii+j)</font>

     - *(*(X+ii)+j)

       - <font color='red'>a[m]相当于*（a+m)</font>就是说 [] 符号如果要去掉的话，相加，括号，再取地址。。。反过来也一样

       - B应该也是错误的，由于<font color='red'>[]的优先级高于*</font>,因此，相当于对地址`（X+ii）[j]`取值，如果B改为`（*（X+ii））[j]`就对了
       - `a[i][j] =*(a[i]+j) = *(*(a+i)+j) =(*(a+i))[j]`

164. print函数声明为void print(int a,char b='b',int c=1); 下面函数调用正确的是（）

     - print('a');

       print(5,8);

       print(5,'#');

       print(5,'#',2);

     - C++在调用函数时，当实参和形参的数据类型不一致时，会发生数据类型转换！将低精度转换为高精度时，由编译器隐式完成；将高精度转换为低精度时，必须用强制类型转换运算符：static_cast<>()来转换才不会造成数据丢失。精度由低到高: char->int->double->long double。CD肯定对， A的话字符转为整数即为97, B 选项在将整数类型 8 复制给 char 时，会发生截断赋值。把整数的前3*8位去掉  直接后8位赋值给char 

165. fprintf函数只能以<font color='red'>字符串</font>的形式写入到文件中

166.

int` `s[4][5],(*ps)[5];
ps = s;

ps是一指向二维数组s的指针，ps+1表示指向数组s第2行首地址的指针；
(ps+3)表示数组s第4行的首地址；(ps+1)+3表示数组s第2行第4列元素的地址，


167. 浮点类型在内存中分布为：<font color='blue'>符号位+指数位（-127~128）+尾数部分 (有效数字 1<= M <2)</font>

168. ```c
     #include "stdio.h"
     #include "string.h"
     void fun(char *s){ 
         char t[7];
         s=t;
         strcpy(s, "example");
     }
     
     int  main(){ 
         char *s;    
         fun(s);    
         printf("%s",s);
         return 0;
     }

对于栈中内存如果没有初始化，则会出现“烫烫烫烫烫烫”。对于堆中内存如果没有初始化，则会出现“屯屯屯屯屯”

需要解释的就是编译错误和运行错误，编译错误可以理解成编译器能检查出来的错误，运行错误理解成逻辑错误，需要用户自己纠错
1.main函数里的s没有初始化就在fun函数里使用s，编译器会报警告，运行时会报错（局部变量未初始化）。答案选D。

2.就算s初始化了，在fun函数里，局部变量t的大小为7，而strcpy函数会复制example末尾的\0

所以example+’\0’一共8个字节空间，会溢出，程序会崩溃。

3.就算局部变量t的大小足够大，在fun函数运行结束后，局部变量t的内存空间会被释放掉，此时s成为野指针；返回main函数后，也不会输出example。

定义二维数组时，若第一维不确定第二维确定，则数组必须初始化;初始化后数组中元素个数除以第二维大小，若能整除，则商即第一维大小，若不能整除，则商加上1得到第一维大小;若第一二维全部确定，可以不初始化，默认元素全部为0;不允许第二维不定
- 二维数组的真实含义是，它的第一维就是一组数据的起始地址，第二维就是某组数据中的某个值，a[][3]表达的意思就是二维数组a的每一维都是由3个元素组成的一维数组
下面程序段的运行结果是 ( ) 。
1
2
3
char *s = "abcde";
s += 2;
printf("%d", s);
- 指针s保存的是字符串的首地址，s+=2后，指向了字符‘c’，格式化输出s就是字符‘c’的地址（十进制形式的地址，%p是十六进制的地址）

下面代码的执行结果是（）

#include <stdio.h>
int main(void) {
    char *p[] = {"TENCENT", "CAMPUS", "RECRUITING"};
    char **pp[] = {p + 2, p + 1, p};
    char ***ppp = pp;
    printf("%s ", **++ppp);
    printf("%s", *++*++ppp);
    return 0;
}

从题干当中，我们可以画出这样的一个图，这样就比较直观的看出了p,pp,ppp都指向哪里了，关键是最后两个printf语句。
（1）printf(“%s”,**++ppp);即，ppp当前所指向的位置，再往下移一个位置，即pp的位置2，而pp的位置2指向的是p的位置2，p的位置2指向的是CAMPUS，所以先输出CAMPUS

（2）printf(“%s”,*++*++ppp);这个语句等价于 printf(“%s”,*++（*++ppp)）;所以我们首先看,++ppp，第一个printf语句中ppp已经指向了pp的位置2，所以再往下移一个，指向了pp的位置3，而（*++ppp）则代表pp位置3所指向的内容，即p的位置1（pp的位置3指向的是p的位置1），在此基础上前面再加上一个++，则代表指针p在位置1的基础上再往下移动，即指针p的位置2，而p的位置2所指向的内容是CAMPUS，所以第二行输出的也是CAMPUS。
所以正确答案是：CAMPUS CAMPUS

scanf()函数是格式化输入函数，它从标准输入设备(键盘）读取输入的信息
- 输入== 读取、打印到屏幕==写
关于C语言中的float，下面哪种说法正确的是（）
- x的二次方大于等于0,对于float变量x总成立
  float 变量加法满足交换律
  条件0.9f == 0.9 的值为真
  条件9 == 0.9*10 的值为真
- C/C++中浮点数由符号位、阶码和尾数构成，其二进制表示并不直接对应浮点数的大小，因此浮点数类型不能进行位运算，否则编译器报错；所以如果A选项正确，其指的应该是x的二次幂；而不是x与2进行逐位异或……
- B不一定正确。虽然**浮点数标准**IEEE 754满足加法和乘法的交换律，不满足加法结合律，但是**C++标准不保证**IEEE 754标准的实现，于是C++编译器也不保证浮点数a+b的结果等于b+a
- C、D错误。浮点数存在误差，直接比较大小往往不是预期的结果；通常引入一个比要求精度还要小几个数量级的实数epsilon来帮助比较大小。在我的机器上，精度取1e-8，0.9f == 0.9为假（0.9f是单精度浮点，精度比0.9低）：
extern、register、static、auto分别是定义外部变量、寄存器变量、静态变量、自动变量
其中，自动变量(auto)和寄存器变量(register)属于动态存储，调用时临时分配单元；而静态变量(static)和外部变量(extern)属于静态存储，在整个程时都存在.
- 故，以下只有在使用时才为该类型变量分配内存的存储类型的是（）
  - auto和register
函数原型：指明函数的名字，返回的类型，有几个参数，这几个参数是什么类型，不需要函数体，也不需要形式参数的名字，其中用分号作为原型的结束符。

例如：void fun( int );
C语言程序能够在不同的操作系统下运行，这说明C语言具有很好的
- 移植性
  - 所谓移植性就是在某操作系统下编写的程序能够在其他操作系统下编译运行，而程序几乎不需要进行任何修改。所以选择B。
对于下面的代码，说法正确的是____

char* s1 = “Hello world”;
char s2[] = “Hello world”;
s1[2] = ‘E’; // 1
s2[2] = ‘E’; // 2
*(s1 + 2) = ‘E’; // 3
*(s2 + 2) = ‘E’; // 4
- “Hello World”在常量区，但s1存储在栈，并且可以做++运算，但*p不可更改，相当于const char *p
- 指针指向字符串时，字符串是常量，存储在常量区，而指针存储在栈区，不能对其操作修改。
- 而对于s2,”Hello world”存储在数组里，在栈区，是可以修改的
strlen和str.length()都是求字符串的长度，但strlen( )的参数必须是char*，而 str.length( )是string类对象str调用的成员函数。
%3d：输出时表示输出位数少于三位数时前面补0，多于三位数时按实际位数输出。输入时表示只输入三位数，少于三位数以空格补齐。
二路归并排序的时间复杂度为（）。
- 假设数据区域为[1:n]，归的过程，第一次将区间分为[1:n/2]和[n/2+1，n]，第二次将两个区间分为四个，总共会进行log2(n)次，总共分为了log2(n）层，每次分区间的时间复杂度为1，则总共归的过程时间复杂度为log2(n)，而并的过程会的归的过程分的区间进行排序，是两个有序数组合并的过程，每一层合并的时间复杂度为n，有log2(n)层，所以并的总共复杂度为nlog2(n)，而归并的复杂度为nlog2(n)+log2(n)，用大O表示法就是nlogn
用邻接矩阵存储有n个结点(0,1,…,n)和e条边的有向图 $0 \le e \le n(n - 1)$ )。在邻接矩阵中删除结点 $i(0 \le i \le n)$ 的时间复杂度是（）
- 删除节点B时，在邻接矩阵中需要把指向B的边全部删除，B指向的边也全部删除。
  
  而邻接矩阵表示法由一个顶点表（一维数组），一个边集（邻接矩阵，二维数组）组成。由顶点表查找i，复杂度为O(1)，然后查找二维数组i行i列，置i行i列均为0（即删除i节点），复杂度为2*O（n）。
  
  结果为O(n)，选择 B。
回溯法
1）（求解目标）回溯法的求解目标是找出解空间中满足约束条件的一个解或所有解。
2）（搜索方式：深度优先）回溯*\搜索整个解空间，当不满条件时，丢弃，继续搜索下一个儿子结点，如果所有儿子结点都不满足，向上回溯到它的父节点。

分支限界法
1）（求解目标）分支限界法的目标一般是在满足约束条件的解中找出在某种意义下的最优解，也有找出满足约束条件的一个解。
2）（搜索方式：广度优先）分支限界法以广度优先或以最小损耗优先的方式搜索解空间。
- 回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。
  
  回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
共用体变量可以作结构体的成员,结构体变量也可以作共用体的成员。
- 正确
文件指针和位置指针都是随着文件的读写操作在不断改变
- 错，文件指针位置不变
任何表达式语句都是表达式加分号结尾
- 正确
数组名不能与其他变量名相同
- 正确
函数形参的存储单元是动态分配的
- 错误，函数的变量一般是栈区，只要退出函数，系统就会自动回收栈区，而动态分配分配时分配堆区，堆区只能手动回收（free函数）
C语言随机操作只适用于文本文件
- 错误，随机操作文本指的是用seek函数重新定位文件指针进行读写操作，访问数组中的元素也是随机的，知道下标就可以，所以说随机操作不只是针对于文件来讲。
全局变量放在static静态区，不是在栈区；stack由编译器自动分配和释放,存放函数的参数值，局部变量
heap&stack 区别

1.heap是堆，stack是栈。

2.stack的空间由操作系统（不是编译器）自动静态分配和释放（进站和出栈可控）；heap的空间是手动申请和释放的，heap常用new关键字来动态分配（—“内存泄露”—— Memory Leak ）。

3.stack空间有限（经常有栈溢出，而不是堆溢出），heap的空间是很大的自由区。

在Java中，

若只是声明一个对象，则先在栈内存中为其分配地址空间，

若再new一下，实例化它，则在堆内存中为其分配地址。

4.举例：

数据类型变量名；这样定义的东西在栈区。

如：Object a =null; 只在栈内存中分配空间

new 数据类型();或者malloc(长度); 这样定义的东西就在堆区

如：Object b =new Object(); 则在堆内存中分配空间
若fp已正确定义并指向某个文件，当未遇到该文件结束标志时函数feof(fp)的值为0.
- 此时并未到文件尾部，否则返回非0，因为有数据时返回0
文件指针用于指向文件，文件只有被打开后才有对应的文件指针。
如果函数定义出现在函数调用之前,可以不必加函数原型声明
- 正确
输入操作称为写操作,将输入流中的信息存到内存时,使用写函数。
- 输入是指计算机将数据读取存入内存的过程，即这个过程是读入过程，即读操作，使用读函数
  - 类比scanf，计算将用户输入的数据从缓冲区读取出来存入内存；printf，计算机将内存中的数据写到输出设备上即屏幕
函数返回值的类型是由在定义函数时所指定的函数类型
指向数组的指针变量称为数组指针变量。
- 一个数组是由连续的一块内存单元组成的。
- 数组名就是这块连续内存单元的首地址。
- 一个数组也是由各个数组元素（下标变量）组成的。
- 每个数组元素按其类型不同占用几个连续的内存单元。
- 一个指针变量既可以指向一个数组，也可以指向一个数组元素。
  
  一般形式：
  类型说明符 *指针变量名。
  
  有了指针可以用两种方法访问数组元素:
  第一种方法为下标法。
  第二种方法为指针法。
指针变量可以存放指针(地址)、数值和字符
- 只能存储地址
内存中每个存储单元都有一个唯一的地址
- 正确

int main ()
{
    char arr[2][4];
    strcpy (arr[0],"you");
    strcpy (arr[1],"me");
    arr[0][3]='&';
    printf("%s \n",arr);
    return 0;
}
<!--27-->

- ```C
  ioctl
  <!--28-->

- ```C
  write
  <!--29-->

malloc函数进行动态、静态内存分配是在什么阶段?
- 程序占用三种类型的内存：静态内存、栈内存、堆内存；
  静态内存：
  用来保存局部static对象、类static数据成员以及定义在任何函数之外的变量
  栈内存：
  
  用来保存定义在函数内的非static对象。
  
  分配在静态内存或栈内存中的对象由编译器自动创建和销毁。对于栈对象，仅在其定义的程序块运行时才存在；static对象在使用之前分配，在程序结束时销毁。
  
  堆内存：
  
  在程序运行时分配。动态对象的生存周期由程序（用户）来控制。
- 装载阶段、执行阶段
“-6.2e”的意思：

6 表示输出的位宽，如果结果小于6位，则不足的部分以空格补充，如果超于6位则没影响；

.2 保留两位小数

e 以指数形式输出，即10的n次幂，e+02即表示10^2

- 负号，表示左对齐还是右对齐，2.19e+02 占9位（代码执行测试得到，通过不断修改6的结果，直到改到10，才出现了%6.2e输出时，左侧添加空格占位）。所以 - 表示左对齐，结尾右侧补空格，而+情况是右对齐，即左侧开头补空格

所以对于218.82631输出结果应为2.19*10^2，转换成计算机的代码输出格式即2.19e+02
共用体：
- 共用体变量的地址和它的各成员的地址都是同一地址。
- 不能对共用体变量名赋值。
- 不能企图引用变量名来得到一个值。
- 不能在定义共用体变量时对它初始化。
- 不能用共用体变量名作为函数参数。
- 不能用函数返回共用体变量
- 可以定义共用体数组，共用体成员可以是数组
- 共用体类型定义和结构体类型定义可以互相嵌套
- 任何时间起作用的是最后一个成员（且只能任意时间只有一个成员起作用）
C 语言分隔符：逗号(变量和表达式之间)、分号(for语句内)、空白符(字符串之间)、冒号（case:)

变量的类型分为两种：储存和数据

所有的数据都有两种类型，一种是数据类型，一种是存储类型。
数据类型：如int，float等
存储类型：四种存储类型的变量，自动变量（auto）、静态变量（static）、外部变量（extern）、以及寄存器变量（register）。

存储类别	存储期	作用域	声明方式
auto	自动	块	块内
register	自动	块	块内,使用关键字register
static(局部)	静态	块	块内,使用关键字static
static(全局)	静态	文件内部	所有函数外,使用关键字static
extern	静态	文件外部	所有函数外

return后面括号里的表达式的值即是此函数的值。请问这句话的说法是正确的吗？
- 错误
- return 后面括号的值不一定是函数的值，譬如函数返回值与return 类型不一致需要类型转换，返回值为 int ，retun 3.2 ，那么肯定会进行转换的
!(x + y) + z-1 && y + z/2;
- 表达式的值是
- !(x + y) + z-1 && y + z/2即为(( !(x + y) )+ z-1) && (y + z/2)=(!7+5-1)&&(4+2)=(0+5-1)&&6=4&&6=1

用C语言编写的代码程序（）

可立即执行
1
2

-

是一个源程序
1
2

-

经过编译即可执行
1
2

-

经过编译解释才能执行
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

     - 1、【<font color='red'>编译</font>】是把c源程序翻译成汇编代码：*.s； 2、【<font color='red'>汇编</font>】是把汇编代码翻译成二进制目标代码：*.obj； 3、【<font color='red'>链接</font>】是把多个二进制目标代码文件链接成一个可执行程序；因为一个工程某个文件调用了其他c文件的函数或变量 一个程序需要上面三个步骤才能由源程序变成可执行程序。

     - C语言写的代码程序<font color='red'>肯定是源程序</font> 它<font color='blue'>不能立即执行，必须经过编译成可执行代码</font>
       如果这个源程序中不含有main函数，编译后的代码也是不可执行的 C语言不是解释执行的

209. 在32位机上，下面C程序的输出结果是

     ```C
     struct MyStruct
     {
         int i;
         char c;
         struct InnerStruct
         {
             int i;
             long l;
             double d;
             char c;
         } innerStruct;
     };
     union MyUnion
     {
         int i;
         char c;
     };
     int main()
     {
        printf("%d, %d", sizeof(MyStruct), sizeof(MyUnion));
     }

做选择题就要有做选择题的方法，除了掌握基本的知识。

对于struct来说，大小虽然要慢慢累加，但是最后必然为struct里最长类型的整数倍，即double为8字节，则肯定是8的整数倍，排除A,B（不用慢慢累加计算）

对于Union来说，就简单了，大小为最长类型的整数倍，即int为4字节，则为4，选C
结构体长度并不一定是double的长度8的整数倍，而是min(字节对齐长度,8)的倍数

如果默认编译器4字节对齐，这题就是28，如果是8字节，就是32

设对齐字节数为n(n = 4或8，区别于32位或者64位操作系统),每个成员内存长度为Li, Max(Li)为最大的成员内存长度,字节对齐规则是:

\1. 结构体对象的起始地址能够被Max(Li)所整除;

\2. 结构体中每个成员相对于起始地址的偏移量,即对齐值应是min(n,Li)的倍数.若不满足对齐值的要求,编译器会在成员之间填充若干个字节;

\3. 结构体的总长度值应是min(n,Max(Li))的倍数,若不满足总长度值的要求,编译器在为最后一个成员分配空间后,会在其后填充若干个字节.

两指针变量相减所得之差是两个指针所指数组元素之间相差的元素个数
fseek函数一般用于二进制文件。注意也可用于文本文件
一个变量的数据类型被强制转换后,它将保持被强制转换后的数据类型
- 错误

使用printf函数打印一个double类型的数据，要求：输出为10进制，输出左对齐30个字符，4位精度。以下哪个选项是正确的？

%-30.4e
1
2

-

%4.30e
1
2

-

%-30.4f
1
2

-

%-4.30f
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： 最小字段宽度

       .4： 精确度保留小数4位

       f： double精度浮点数

       e： 科学计数法

     - printf中，<font color='red'>%f通杀单精度和双精度</font>
       在<font color='red'>scanf</font>中，%f和%lf才<font color='red'>有区别</font>

214. 下面关于C语言中sizeof(int)说法正确的是（）

     - <font color='red'>编译时</font>
     - 运行时

215. C语言中的一个变量可以被定义为两个或多个不同的类型。请问这句话的说法是正确的吗

     - 如果同一个变量，分别作为全局变量和局部变量，根据局部优先原则，是可以定义为不同类型的。

216. ```C
     struct student {
         int num, age;
     };
     struct student stu[3] = {{6001, 20}, {6003, 21}, {6005, 19}};
     struct student *p = stu;

则下面的C语言表达式中,值为6003的是（）。

对于A选项：++(p->num)。表示取数组第一个元素的值(6001)，然后+1；

对于B选项：(p++)->num。后缀自增运算符(++)与成员选择运算符(->)处于同一优先级，从左到右结合，但是指针偏移的操作直到表达式结束才会进行，

这个表达式相当于(p)->num;p=p+1;

对于C选项：(*p++).num。后缀自增运算符(++)优先级高于取值运算符()，但是++直到表达式结束才会进行，这个表达式相当于`(p).num;p=p+1;`

对于D选项：(*++P).num。前缀自增运算符(++)优先级和取值运算符()一样，先执行p=p+1操作，相当于`((p+1)).num`;

下列函数正确的是

void test1(){
    unsigned char array[MAX_CHAR+1],i;
    for(i = 0;i <= MAX_CHAR;i++){
        array[i] = i;
    }
}
char*test2(){
    char p[] = "hello world";
    return p;
}
char *p = test2();
void test3(){
    char str[10];
    str++;
    *str = '0';
}

- 重点不在于CHAR_MAX的取值是多少，而是在于i的取值范围是多少。 一般char的取值范围是-128到127，而u char 则是0~255，所以i的取值范围是0~255. 所以当CHAR_MAX常量大于255时，执行i++后，i不能表示256以上的数字，所以导致无限循环。 第二个问题： 重点在于函数中p的身份，他是一个指针，还是数组名；  如果是指针p，则p指向存放字符串常量的地址，返回p则是返回字符串常量地址值，调用函数结束字符串常量不会消失（是常量）。所以返回常量的地址不会出错。 如果是数组p，则函数会将字符串常量的字符逐个复制到p数组里面，返回p则是返回数组p，但是调用函数结束后p被销毁，里面的元素不存在了。 例子中p是数组名，所以会出错，p所指的地址是随机值。 若是把char p[]="hello";改成char *p="hello";就可以了。第三个问题：  重点在于str++;这实际的语句就是str=str+1;而str是数组名，数组名是常量，所以不能给常量赋值。（可以执行str+1，但是不能str=.）

输出正确的是：
1
2
3
4
5
6
7
8
9
10
#include<stdio.h>
int main() {
char *a = "Trend";
char **b = &a;
*b = "commercial";
char *c = ++a;
a = "talents.";
printf("%c\n",*++c);
return 0;
}
- 一开始a指向Trend，b指向指针a，后面commercial的内容赋给了指针b，然后就改变了指针a的内容，a就指向了commercial，指针c指向a所指的第二个字符，也就是o，虽然后面a又指向了talents，但是c已经指向了commercial，所以++c，c就指向了m，*++c就输出m字符
在C中使用malloc时不需要强制类型转换，因为在C中从void*到其他类型的指针是自动隐式转换的；

在C++中使用malloc时必须要强制类型转换，否则会报错，但在c++中一般用new而不用malloc；
int a[10]={ }; 编译器自动将所有元素置零
对于以下结构定义，(*p)->str++中的++加在（）
1
struct { int len; char *str; } *p;
- p是指针，可以写p->str,但是（*p）只能写(*p).str;
结构体和共用体变量都不能进行比较操作，因为类型不一样，无法比较，除非强制转换或重载比较运算符
如果想在一个地方定义结构体，而在其他地方定义实际的结构体变量那么就必须使用标记名；如果定义结构体的同时就创建该结构体变量，则可以省略结构体的标记名，此时该结构体是一次性的、
typedef不是用来定义新的数据类型，而是创建易于记忆的类型名，给类型取别名
结构总是以传值的方式传递给函数
不管b_val为多少，while(b_val)等价于while(b_val！=0)，while(!b_val)等价于while(b_val==0)
在行尾放一个 \ ，编译器会忽略行尾的换行符，起到续行的作用。
include <file> //在标准库及默认搜索目录中寻找将要 include 的文件

include “file” //先在当前目录中搜索文件，然后再到默认搜索目录中搜寻。
- 因此标准库头文件应该用<>更快
%要求两边都是整数，如果你非要一个整数%另外一个非整数的可以用强制类型转换把它转换成整形

即使分母为0，编译器也不会编译出错，输出结果为inf,表示无穷大
所谓声明，就是告诉编译器变量的类型，编译器并不为其分配内存，此变量已经定义过，故声明可以多次进行。例如，声明外部变量 a。

extern int a;

（1）定义创建了变量，并为其分配内存；声明没有分配内存。

（2）一个变量在一定的区域内只能被定义一次，却可以被多次声明。
若有以下的定义:int t[3][2];

t[2] 能正确表示 t 数组某元素的地址。表述是否正确？
- 正确
程序行、语句、函数都是由字符构成的，字符是C语言的最小单位，最小执行单元是函数。

以下定义错误的是：

struct A{A  _a;};
1
2

-

struct A{A* _a;};
1
2

-

struct A{A& _a;};
1
2

-

struct B;
struct A{B& _b;};
struct B{A& _a;};
1
2
3
4

答案：A 

  解释：struct成员类型不可以是它自己。

因为会递归定义。
理论上这样导致结构体的大小不能被计算（无限大小）。所以不能在结构体里的成员类型是结构体本身。
但是成员可以定义为该结构体的指针。就像你上面这段代码。因为指针的大小是已知的（随编译器和操作系统而定）。
所以可以定义为该结构体的指针，但不是该结构体。
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

234. 表头可以是原子或子表，表尾一定是子表

235. 数组静态分配内存，链表动态分配内存；
      数组在内存中连续，链表不连续；（对于数组，对象是放在堆内存中的，对象的引用是放在栈内存中的）
      数组元素在栈区，链表元素在堆区；
      数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
      数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。

236. 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T（n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数.记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度.数学语言表达就是：存在足够大的正整数M，使得T（n）≤M×f（n）。

237. 一个C源程序不是必须包含一个main()函数，而是必须包含一个**程序的入口函数**，**程序的入口函数不一定是main()函数**

238. **1.default顾名思义是缺省情况，所有case条件不符合时才会执行；**

     2.case语句若不加break，则当一条满足条件的case语句执行后，其下面的case语句都会执行。

239. 必须在声明中对常量初始化，否则该常量值不确定且无法修改

240. 注意本题的索引下标是从1开始 所以循环队列中最多有n个元素
      在循环队列中,头指针指向队列当中的第一个元素,而尾指针指向最后一个元素的下一位

         假设循环队列的队尾指针是rear，队头是front，其中QueueSize为循环队列的最大长度。  

        (1)    入队时队尾指针前进1：(rear+1)%QueueSize  

        (2)    出队时队头指针前进1：(front+1)%QueueSize  

        (3)    队列长度：(rear-front+QueueSize)%QueueSize  

         现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)  

         答案：(rear-front+N)%N  

        (4) 队空和队满的条件  

         为了区分队空还是堆满的情况，有多种处理方式：  

        方式1：    牺牲一个单元来区分队空和队满，入队时少用一个队列单元，即约定以"队头指针在队尾指针的下一位置作为队满的标志"。  

         队满条件为：(rear+1)%QueueSize==front  

         队空条件为：front==rear  

         队列长度为：(rear-front++QueueSize)%QueueSize  

        方式2：    增设表示队列元素个数的数据成员size，此时，队空和队满时都有front==rear。  

         队满条件为：size==QueueSize  

         队空条件为：size==0  

        方式3：    增设tag数据成员以区分队满还是队空  

         tag表示0的情况下，若因删除导致front==rear，则队空；  

         tag等于1的情况，若因插入导致front==rear则队满

241. 一个结构体指针变量虽然可以用来访问结构体变量或结构体数组元素的成员，但是，**结构体指针变量不能指向一个成员**。也就是说不允许取一个成员的地址来赋予它。

     ```c
     错误：
     pdate = &Date[1].year;		//错误的

链表练习

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

typedef struct student{
	int num;
	char name[10];
	char sex[4];
	int score[3];
	float ave;
}student;

typedef struct stuNode{
	student stu;
	struct stuNode *next;
}stuNode, *stuList;

//输入一个学生信息
student inputAStu();
//输入n 个学生信息， 返回学生数组 
student* inputStu(int n);
//输出学生信息
void printStu(student *stu, int n);
//为学生数据进行按照平均分大小进行降序排序（分别使用冒泡排序、选择排序、插入排序、快速排序实现）
void bubbleSortStu(student *stu, int n);
void insertSortStu(student *stu, int n);
void selectSortStu(student *stu, int n);
int patition(student *stu, int left, int right);
void quickSort(student *stu,int left, int right);
//创建带有头结点的链表(头插法)
stuList creat1(student *stu, int n);
//创建带有头结点的链表(尾插法)
stuList creat1_2(student *stu, int n);
//创建不带头结点的链表 (相当于尾插法)(可以写头插法，但是没必要，简单来说就是创建带有头结点的链表【同上】，最后返回的是head->next)
stuList creat2(student *stu, int n);
//统一使用使用不带头结点的遍历
void printList(stuList head);
//为链表添加一个学生信息(按平均分有序插入(带头结点))
void addStuNode(stuList *head, student stu);
//链表中删除姓名为delname的全部学生信息,删除成功返回1，否则返回0
int delStuNode(stuList *head, char *delname);
//将链表中的学生信息逆置(带头结点)【头插法实现逆置】
stuList reverseStuList(stuList head);
//将两个学生有序的链表合并，并保证合并后链表仍然有序(带头结点)
stuList mergeList(stuList L1, stuList L2);
//链表中删除平均分最小的节点
stuList delStuMinAve(stuList head);
//找到两个链表的公共学生信息（以姓名为基准）合并成一个新的链表
stuList getCommonStu(stuList L1, stuList L2);
//判断两个学生学生链表是否相交
int judgeInterSect(stuList L1, stuList L2);
//判断学生链表是否存在环
int judgeLoop(stuList head);
int main(){
	int n;
	printf("please input students number: ");
	scanf("%d", &n);
	student *stu;
	stu = inputStu(n);
	printf("----输出学生数组----\n");
	printStu(stu, n);
	
	printf("----输出排序后学生数组----\n");
	//bubbleSortStu(stu, n);
	//insertSortStu(stu, n);
	//selectSortStu(stu, n);
	quickSort(stu, 0, n - 1);
	printStu(stu, n);

	stuList head;
	//head = creat1(stu, n); //头结点头插法测试
	head = creat1_2(stu, n); //头结点尾插法测试
//	head = creat2(stu, n); //不带头结点尾插法测试
	printf("----输出学生链表----\n");
	printList(head->next);
	
//	printf("----Input插入学生信息---");
//	student e = inputAStu();
//	addStuNode(&head, e);
//	printf("----输出学生链表----\n");
//	printList(head);

//	printf("\n----Input待删除学生姓名---\n");
//	char delname[10];
//	getchar();
//	gets(delname);
//	if(delStuNode(&head, delname)){
//		printf("delete successful!\n");
//	}else{
//		printf("no find this student!\n");
//	}


//	printf("----逆置学生链表----\n");
//	head = reverseStuList(head);
//	
	
//	int n2;
//	printf("please input students number: ");
//	scanf("%d", &n2);
//	student *stu2;
//	stu2 = inputStu(n2);
//	printf("----输出学生数组----\n");
//	printStu(stu2, n2);
//	printf("----输出排序后学生数组----\n");
//	quickSort(stu2, 0, n2 - 1);
//	printStu(stu2, n2);
//	
//	stuList head2;
//	head2 = creat1_2(stu2, n2); //头结点尾插法测试
//	printf("----输出学生链表----\n");
//	printList(head2->next);
//	printf("----合并两个链表---\n");
//	stuList head3 =  mergeList(head, head2);
//	
//	printf("----输出合并后学生链表----\n");
//	printList(head3->next);
	
//	printf("----删除平均分最小的节点---\n");
//	head = delStuMinAve(head);

//	int n2;
//	printf("please input students number: ");
//	scanf("%d", &n2);
//	student *stu2;
//	stu2 = inputStu(n2);
//	printf("----输出学生数组----\n");
//	printStu(stu2, n2);
//	printf("----输出排序后学生数组----\n");
//	quickSort(stu2, 0, n2 - 1);
//	printStu(stu2, n2);
//	
//	stuList head2;
//	head2 = creat1_2(stu2, n2); //头结点尾插法测试
//	printf("----输出学生链表----\n");
//	printList(head2->next);
//	printf("----找到公共学生信息链表---\n");
//	stuList head3 =  getCommonStu(head, head2);
	
	printf("----输出删除的后学生链表----\n");
	printList(head->next);
	return 0;
}


//输入一个学生信息
student inputAStu(){
	student stu;
	printf("该学生(依次输入学号、姓名、性别、三门课成绩 ）：");
	scanf("%d%s%s", &stu.num, stu.name, stu.sex);
	int j, sum = 0;
	for(j = 0; j < 3; j++){
		scanf("%d", &stu.score[j]);
		sum += stu.score[j];
	}
	stu.ave = (float)sum / 3;
	return stu;
}
//输入n 个学生信息， 返回学生数组 
student* inputStu(int n){
	student *stu = (student *)malloc(sizeof(student) * n);
	int i;
	static int count = 0;
	printf("Input n students:\n"); 
	for(i = 0; i < n; i++){
		printf("No.%d (依次输入学号、姓名、性别、三门课成绩 ）：", ++count);
		scanf("%d%s%s", &stu[i].num, stu[i].name, stu[i].sex);
		int j, sum = 0;
		for(j = 0; j < 3; j++){
			scanf("%d", &stu[i].score[j]);
			sum += stu[i].score[j];
		}
		stu[i].ave = (float)sum / 3;
	}
	
	return stu; 
}
//输出学生信息
void printStu(student *stu, int n){
	int i;
	for(i = 0; i < n; i++){
		printf("第%d个学生：%d  %s  %s  %d  %d  %d  %.2f\n",i + 1, stu[i].num, stu[i].name, stu[i].sex, stu[i].score[0], stu[i].score[1], stu[i].score[2], stu[i].ave);
	}
}

//为学生数据进行按照平均分大小进行降序排序（分别使用冒泡排序、选择排序、插入排序、快速排序实现）
void bubbleSortStu(student *stu, int n){
	student temp;
	int i, j;
	for(i = 0; i < n - 1; i++){
		int flag = 0;
		for(j = n - 1; j > i; j--){
			if(stu[j - 1].ave-stu[j].ave < 1e-6){
				temp = stu[j];
				stu[j] = stu[j - 1];
				stu[j - 1] = temp;
				flag = 1;
			}
		}
		if(flag == 0){//此汤未发生交换则提前结束排序没因为已经有序
			break;
		}
	}
}
void insertSortStu(student *stu, int n){
	int i, j;
	student temp;
	for(i = 1; i < n; i++){
		if(stu[i - 1].ave-stu[i].ave < 1e-6){
			temp = stu[i];
			for(j = i - 1; j >= 0 && stu[j].ave-temp.ave < 1e-6; j--){
				stu[j + 1] = stu[j];
			}
			stu[j + 1] = temp;	
		}
	}
}
void selectSortStu(student *stu, int n){
	int i, j;
	student temp; 
	for(i = 0; i < n - 1; i++){
		int max = i;
		for(j = i + 1; j < n; j++){
			if(stu[max].ave-stu[j].ave < 1e-6){
				max = j;
			}
		}
		if(max != i){
			temp = stu[i];
			stu[i] = stu[max];
			stu[max] = temp;
		}
	}	
}
int patition(student *stu, int left, int right){
	student pivot = stu[left];
	
	while(left < right){
		while(left < right && stu[right].ave-pivot.ave <= 1e-6) right--;
		stu[left] = stu[right];
		while(left < right && stu[left].ave-pivot.ave >= 1e-6) left++;
		stu[right] = stu[left];
	}
	stu[left] = pivot;
	return left;
}
void quickSort(student *stu,int left, int right){
	if(left < right){
		int pation = patition(stu, left, right);
		quickSort(stu, left, pation - 1);
		quickSort(stu, pation + 1, right);
	}
}
//创建带有头结点的链表(头插法)
stuList creat1(student *stu, int n){
	stuList head = (stuNode *)malloc(sizeof(stuNode));
	head->next = NULL;
	stuList p;
	int i;
	for(i = 0; i < n; i++){
		p = (stuNode *)malloc(sizeof(stuNode));
		p->stu = stu[i];
		p->next = head->next;
		head->next = p;
	}
	
	return head;
}
//创建带有头结点的链表(尾插法)
stuList creat1_2(student *stu, int n){
	stuList head = (stuNode *)malloc(sizeof(stuNode));
	stuList p, r = head;//定义r为尾指针
	int i;
	for(i = 0; i < n; i++){
		p = (stuNode *)malloc(sizeof(stuNode));
		p->stu = stu[i];
		r->next = p;
		r = p;
	}
	r->next = NULL;
	return head;
}


//创建不带头结点的链表 (相当于尾插法)(可以写头插法，但是没必要，简单来说就是创建带有头结点的链表【同上】，最后返回的是head->next)
stuList creat2(student *stu, int n){
	stuList head = (stuNode *)malloc(sizeof(stuNode));
	stuList p, q;
	head = NULL;
	int i;
	for(i = 0; i < n; i++){
		p = (stuNode *)malloc(sizeof(stuNode));
		p->stu = stu[i];
		if(head == NULL){
			head = p;
			q = head;
		}else{
			q->next = p;
			q = p;
		}
	}
	q->next = NULL;
	return head;
}

//统一使用使用不带头结点的遍历
void printList(stuList head){
	stuList p = head;
	int i = 0;
	while(p != NULL){
		printf("第%d个节点：", ++i);
		student stu = p->stu;
		printf("%d  %s   %s  %d  %d  %d  %.2f\n", stu.num, stu.name, stu.sex, stu.score[0], stu.score[1], stu.score[2], stu.ave);
		p = p->next;
	}
}

//为链表添加一个学生信息(按平均分有序插入(带头结点))
void addStuNode(stuList *head, student stu){
	stuList p = *head, s = (stuList)malloc(sizeof(stuNode));
	s->stu = stu;
	s->next = NULL;
	int flag = 0;
	while(p->next != NULL){
		if(p->next->stu.ave - stu.ave <= 1e-6){
			s->next = p->next;
			p->next = s;
			flag = 1;
			break;
		}
		p = p->next;
	}
	if(flag == 0){//如果当前学生的成绩最小，即需要插入到链表末尾
		p->next = s;
	}
}
//链表中删除姓名为delname的全部学生信息,删除成功返回1，否则返回0
int delStuNode(stuList *head, char *delname){
	stuList p = *head, q;
	int flag = 0;
	while(p->next != NULL){
		if(strcmp(p->next->stu.name, delname) == 0){
			q = p->next;
			p->next = p->next->next;
			q->next = NULL;
			flag = 1;
			free(q); 
		}else{
			p = p->next;
		}
	}
	return flag;
}
//将链表中的学生信息逆置(带头结点)【头插法实现逆置】
stuList reverseStuList(stuList head){
	stuList p = head->next, q;
	head->next = NULL;
	while(p != NULL){
		q = p->next; //q节点暂存p的后继
		p->next = head->next; //头插遍历
		head->next = p;
		p = q;
	}
	return head;
}
//将两个学生有序的链表合并，并保证合并后链表仍然有序(带头结点)
stuList mergeList(stuList L1, stuList L2){
	stuList head = (stuList)malloc(sizeof(stuNode)), p1 = L1->next, p2 = L2->next, r = head;
	stuNode *s;
	while(p1 != NULL && p2 != NULL){
		s = (stuNode *)malloc(sizeof(stuNode));
		if(p1->stu.ave - p2->stu.ave < 1e-6){//归并思想 大的先插（尾插法）
			s->stu = p2->stu;
			r->next = s;
			r = s;
			p2 = p2->next;
		}else{
			s->stu = p1->stu;
			r->next = s;
			r = s;
			p1 = p1->next;
		}
	}
	if(p1){
		r->next = p1;
	}
	if(p2){
		r->next = p2;
	}
	
	return head;
}
//链表中删除平均分最小的节点
stuList delStuMinAve(stuList head){
	stuList L = head, p = head->next;
	char delname[20];
	float min = p->stu.ave;
	strcpy(delname, p->stu.name);
	while(p != NULL){
		if(p->stu.ave - min < 1e-6){
			min = p->stu.ave;
			strcpy(delname, p->stu.name);
		}
		p = p->next;
	}
	//直接调用前面写好的接口
	printf("%s\n", delname);
	
	if(delStuNode(&L, delname)){
		printf("成功\n");
	}else{
		printf("失败\n");
	}
	
	return L;
}
//找到两个链表的公共学生信息（以姓名为基准）合并成一个新的链表
stuList getCommonStu(stuList L1, stuList L2){
	stuList head = (stuList)malloc(sizeof(stuNode)), p1 = L1->next, p2 = L2->next, r = head;
	stuNode *s;
	while(p1 != NULL){
		while(p2 != NULL){
			if(strcmp(p1->stu.name, p2->stu.name) == 0){
				s = (stuNode *)malloc(sizeof(stuNode));
				s->stu = p1->stu;
				r->next = s;
				r = s;
			}
			p2 = p2->next;
		}
		p2 = L2->next;
		p1 = p1->next;
	}
	r->next = NULL;
	
	return head;
}
//判断两个学生学生链表是否相交
int judgeInterSect(stuList L1, stuList L2){
	stuList p1 = L1, p2 = L2;
	while(p1->next != NULL){
		p1 = p1->next;
	}
	while(p2->next != NULL){
		p2 = p2->next;
	}
	//如果两个链表相交，那么他们的最后一个节点一定相同
	return p1 == p2;
}
//判断学生链表是否存在环
int judgeLoop(stuList head){
	stuList p1 = head->next, p2 = head->next;
	
	//判断有环的问题，一般使用快慢指针，快指针一次走两步，慢指针一次走一步，那么最终
	//如果有环，那么快指针和慢指针一定会相遇，如果无环，快指针一定能先走到NULL节点，此时退出
	while(p2 != NULL){
		p2 = p2->next;
		if(p2 != NULL){
			p2 = p2->next;
		}
		if(p1 == p2){
			return 1;
		}else{
			p1 = p1->next;
		}
	}
	
	
	
	return 0;
}

栈队列

1、堆栈与队列的基本概念与操作

1）、堆栈的基本概念与操作

堆栈：只能在表的一端进行操作的线性表，一般的操作就是插入和删除，允许操作的一端称为栈顶，栈顶元素由栈顶指针给出，没有元素时为空栈
后进先出，先进后出
插入（入栈，进栈）
删除（出栈，退栈）
判空
判满
检索当前栈顶元素
特殊性：1、操作时一般线性表的子集；2、插入和删除的位置受到限制

    
2)、队列的基本概念与操作

    队列：队列简称队，是一种只能由一端进行插入，另一端进行删除的线性表。进行插入的一端称为队尾，用rear表示，删除的一端称为队头，用front指针表示
    先进先出，后进后出
    插入（进队，入队）
    删除（出队，退队）
    判空
    检索当前队头元素
    创建空队
    特殊性：1、操作时一般线性表的子集；2、插入和删除的位置受到限制


    
    
2、堆栈与队列的顺序存储结构与链式存储结构的构造原理

1）、堆栈的顺序存储结构

    一维数组SCACK[0..n-1],定义一个整型变量给出栈顶元素，但是不同于数组，数组时静态结构，堆栈是动态结构

   溢出：上溢：栈满时进行插入操作 top = n-1；下溢：栈空时进行删除操作  top = -1
   定义：

1
2
3
#define M 1000
int STACK[M];
int top = -1;  //初始的时候top为-1，表示栈空


2)、堆栈的链式存储结构

    用线性链表表示，栈顶指针为NULL是为空

1
2
3
4
typedef struct node{
     int data;
     struct node *link;
}STNode, *STLink;


3）、队列的顺序存储结构

1
2
3
4
5
6
7
8
9
一维数组QUEUE[0..n-1],两个变量front和rear指出队头和队尾元素的位置。
约定：rear指出实际队尾元素的位置
      front指出队头元素的前一个位置
      初始队列为空front = -1 ； rear = -1； 
      判断队列为空的条件：front = rear；
      
#define M 1000
int QUEUE[M];
int front, rear;


4）、队列的链式存储结构

1
2
3
4
5
6
7
用线性链表表示，rear指出队尾，front指出队头
空队列 front = NULL；

typedef struct node{ 
    int data;
    struct node *link;
}QNode, *QLink;



3、在不同存储结构上对堆栈和队列进行插入和删除操作的算法设计

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
初始化
     
  void Init(int &top)
  {
       top = -1;
  }
     
  判空
     
  int Empty(int top)
  {
       return top == -1;
  }
     
  判满
     
  int FULL(int top)
  {
       return top == M-1;
  }
     
  插入（进栈）
     
  int Push(int Stack[], int &top, int element)
  {
       if(FULL(top)
       return 0;
       else{
           Stack[++top] = element;
           return 1;
       }
  }
     
  删除（出栈）
  int Pop(int Stack[], int &top, int element)
  {
       if(Empty(top))
           return 0;
       else{
           element = Stack[top--];
           return 1;
       }
  }


2）、链式存储上对堆栈进行操作

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
初始化
void Init(STLink &top)
{
    top = NULL;
}

判空
int Empty(STLink top)
{
    return top == NULL;
}

插入（进栈）不用判满
int Push(STLink &top, int item)
{
    STLink p;
    if(!(p = (STLink)malloc(sizeof(STNode))))
        return 0;
    else{
        p->data = item;
        p->link = top;
        top = p;
        return 1;
    }
}

删除（出栈）
int Pop(STLink &top, int &item)
{
    STLink p;
    if(Empty(top))
        return 0;
    else{
        p = top;
        item = p->data;
        top = top->link;
        free(p);
        return 1;
    }
}



    
3）、在顺序存储结构上对队列进行操作

    初始化

    void Init(int &front, int &rear)
    {
        front = -1;
        rear = -1;
    }

    判空

    int Empty(int front, int rear)
    {
        return rear == front;
    }

    插入 
    int ADDQ(int Queue[], int &rear, int item)
    {
        if(rear == M-1)    //假溢出
            return 0;
        else{
            Queue[++rear] = item;
            return 1;
        }
    }

    删除 
    int DELQ(int Queue[], int &front, int rear, int &item)
    {
        if(Empty(front, rear))
            return 0;
        else{
            item = Queue[--front];
            return 1;
        }
    }

    循环队列：将队列想象成头尾相连的表，使得队头删除的元素的空间能够尽可能被利用

    算法1：删除之后将每个元素前移一位。
            缺点：浪费空间

    算法2：求余

    添加：

    int ADDQ(int Q[], int &rear, int &front, int item)
    {
        if((rear+1)%M == front)
            return 0;
        else{
            Q[++rear%M] = item;
            return 1;
        }
    }

    删除：

    int DELQ(int Q[], int &front, int &rear, int &item)
    {
        if(front == rear)
            return 0;
        else{
            front = (front + 1)%M;
            item = Q[front];
            return 1;
        }
    }

4）、在链式存储结构上对队列进行操作

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
初始化

void Init(QLink front, QLink rear)
{
    front = NULL;
    rear = NULL;
}

判空

int Empty(QLink front)
{
    return fron == NULL;
}

插入

int ADDQ(QLink &front, QLink &rear, int item)
{
    QLink p;
    if(!(p = (QLink)malloc(sizeof(QNode))))
        return 0;
    else{
        p->data = item;
        p->link = NULL;
        if(front == NULL)
            front = p;
        else
            rear->link = p;
        
        rear = p;
        return 1;
    }
}

删除 

int DELQ(QLink &front, QLink &rear, int &item)
{
    QLink p;
    if(Empty(front, rear))
        return 0;
    else{
        p = front;
        front = front->link;
        item = p->data;
        free(p);
        return 1;
    }
}