文章目录
前言
又是好久没更新，平时要做作业+摆烂，所以没怎么更新了，不过还是会保持一些更新频率的啦。这一期是我们数据结构中经典问题——最大子序列的解析以及作业，作业内容对应书本《Data Structures and Algorithm Analysis in C 2nd》即《数据结构与算法分析——C语言描述第二版》中的1-3章部分内容。
最大子序列和
这个题目是这一期作业里最重要的，是最基础的算法题目，接下来就是对各个算法的分析。
题目：
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。整数项可以是负数，如果所有整数都是负数，那么最大子序列和为0；示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。示例 2：
输入：nums = [1]
输出：1示例 3：
输入：nums = [5,4,-1,7,8]
输出：23
一、遍历法
首先我们思考这个问题的时候，先想想最简单的，再一步步优化。因为是整数的数组，我们最直接的方法不就是，把每一种组合都算出来，最后再计算最大值就可以啦。于是我们会这样写到：
int MaxSubsequenceSum( const int A[], int N )
{
int ThisSum, MaxSum=0, i, j, k;
for( i = 0; i < N; i++ )
for( j = i; j < N; j++ )
{
ThisSum = 0;
for( k = i; k <= j; k++ )
ThisSum += A[k];
MaxSum=(ThisSum>MaxSum)?ThisSum:MaxSum;
}
return MaxSum;
}分析：我们用i表示起始位置，j表示终止位置，计算每一种组合的和。因为i,j在计算的时候会被固定，所以还需要一层循环来计算和。所以这个算法的时间复杂度是O(N^3)，此时当N很大的时候，这个算法很大几率会超时，效率太低。
优化：我们需要优化一下这样的算法。我们发现现在这个算法里最大缺点就是i,j作为引索时被固定了，这样导致我们计算和的时候还需要一层循环。如果我们能在找的时候就比较，而不是最后算完再比较，这样就不需要再来一层循环额外计算了。
二、遍历法优化
结合上面提到的边循环边比较的思想，我们对算法一进行一些修改：
int MaxSubSequenceSum(const int A[], int N)
{
int ThisSum, MaxSum, i, j,k;
MaxSum = 0;
for(i=0;i < N; i++)
{
ThisSum = 0;
for(j=i;j < N;j++)
{
ThisSum += A[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}分析：同样的，我们把i和j作为引索，一样是计算区间内的和，但是这里是边循环边计算。每次j循环，即右边的引索位置改变时我们就增加进计算和的数组A[j]里，然后立刻判断现在的和（ThisSum）与最大和(MaxSum)的大小，然后通过循环改变j引索。这还是和之前一样相当于计算了所有的组合，但是因为每次右引索移动时就进行计算比较了，比算法一少一层循环，时间复杂度是O(N^2)，要快上不少。
优化：到了这一步，发现O(N^2)还是挺大的，但是怎么想都改变不了这样的算法至少要循环两次的问题了。于是我们只能转变思路。
三、分治法
我们看到这样的一直重复的算法一般都是两种解决方案，一种是循环，另一种是递归。我们下意识会认为递归会比循环效率低很多，这种情况一般发生在数据很大，递归调用没关闭导致占用很多的情况等等。那我们尝试使用一下递归来解决这个问题。
在这里，原来的整个的问题与每一个分解后子问题都有着反复执行的算法思想——即每次都是相同的计算子序列和，这就是一个相同的基本操作，所以可以用递归实现。
回到这题，如果我们只是把循环换成递归，那岂不是时间复杂度差不多甚至更慢嘛？而在递归中我们有一个非常好用的二分法，可以大大节省时间。
二分法的关键思想是：假设该数组的长度是N，那么二分以后子数组的长度是N/2，再对子数组二分后是N/4……直到二分到1结束。那么二分的次数就是基本语句执行的次数，于是我们可以设次数为X，我们列一个表：
| X（次数） | 结果 | 规律 |
|---|---|---|
| 1 | N/2 | N/2^1 |
| 2 | N/4 | N/2^2 |
| 3 | N/6 | N/2^3 |
| 4 | N/16 | N/2^4 |
我们发现它每次的结果都是N*(1/2)^X，是一个等比数列，公比为1/2。那我们最后二分的结果是1结束，那么我们列式：N*(1/2)^X=1 => X=logN，所以此时二分算法的时间复杂度是O(logN) < O(N^2)。于是我们就可以在递归中使用二分法来减少时间复杂度。
我们要使用二分法，必须要先把这个问题分成重复的小问题来解决。我们把将问题分解为规模更小的子问题；将这些规模更小的子问题逐个击破；将已解决的子问题合并，最终得出“母”问题的解的方法称为分治法。模型如下：
那么我们分析可以得出：求最大子序列和，我们可以将求最大子序列和的序列分解为两个大小相等的子序列，然后在这两个大小相等的子序列中，分别求最大子序列和（二分思想）。如果由原序列分解的这两个子序列还可以进行分解的话，进一步分解，直到不能进行分解为止，使问题逐步简化，最后求最简化的序列的最大子序列和。
那么可能出现的情况有三种：
- 最大子序列全部在数组左部分；
- 最大子序列全部在数组右部分；
- 最大子序列横跨左右数组。
前两种我们计算的方法是一样的，因为使用的是递归，我们每一次递归都传下去了一个左引索，即有一边是固定的，只需要循环右引索，然后像算法二那样边循环边计算最大值就可以找到这一层的最大值啦。（每一次传下去的都是一个子数组，即头部固定）
第三种情况我们先举个例子：
eg1. A{1,-1,1,3,5,-4,-3}，我们很容易看出最大子序列和是1+3+5=9，而我们把它二分，第一次二分左部分子数组是B{1,-1,1,3}，右部分为C{5,-4,-3}。
（PS：7/2是3，我们就把这个结果作为mid，所以如果是奇数的情况左边会多一个）
此时我们直接跳过递归部分，直接跳到算出左右最大的时候。左边最大和是1+3=4，右边最大和是5。此时如果是跨越中间的部分就是左边最大和+右边最大和=4+5=9，就会最大值。
但是有没有可能左侧的最大值不是靠近中间的部分，例如：
eg2. A{1,3,-1,2,5,-4,-3}，同理最大值是2+5=7。同样的二分，左边B{1,3,-1,2}，右边C{5,-4,-3}。
我们仔细分析左边部分，继续二分B，得到B1{1,3}，B2{-1,2}。
继续二分B11{1}，B12{3}，可以返回结果为3。
同时二分B21{-1}，B22{2}，可以返回结果2。
返回第二层，我们比较左右两边的最大值，很容易得到左边的最大结果3.同理找到右边的为5
此时我们再把它们加起来3+5>7了，此时就会得到一个错误的答案。
解决这个问题的方法也很显然，像右边一样固定的是靠近mid位置的元素开始遍历，我们只需要调整循环位置就可以了。
分析完，我们就可以写代码啦，代码如下：
static int MaxSubSum(const int A[], int Left, int Right)
{
if (Left == Right) /* 递归的基准情形 */
return a[Left];
int Center;
Center = (Left + Right) / 2; /* 求分界点 */
int MaxLeftSum;
MaxLeftSum = MaxSubSum(A, Left, Center); /* 递归，求左半部分子序列的最大子序列和 */
int MaxRightSum;
MaxRightSum = MaxSubSum(A, Center + 1, Right); /* 递归，求右半部分子序列的最大子序列和 */
/* 求横跨左半部分和右半部分的最大子序列和 */
/* 首先是左半部分子序列中包含最后一个元素的最大子序列和 */
int MaxLeftBorderSum = A[Center], LeftBorderSum = A[Center];
for (int i = Center - 1; i >= Left; --i)
{
LeftBorderSum += A[i];
if (LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}
/* 接着是右半部分子序列中包含第一个元素的最大子序列和 */
int MaxRightBorderSum = A[Center + 1], RightBorderSum = A[Center + 1];
for (int i = Center + 2; i <= Right; ++i)
{
RightBorderSum += A[i];
if (RightBorderSum > MaxRightBorderSum)
MaxRightBorderSum = RightBorderSum;
}
/* 返回左、右半部分子序列的最大子序列和以及横跨左、右半部分的最大子序列和中的最大者 */
if (MaxLeftSum > MaxRightSum && MaxLeftSum > MaxLeftBorderSum + MaxRightBorderSum)
return MaxLeftSum;
else if (MaxRightSum > MaxLeftSum && MaxRightSum > MaxLeftBorderSum + MaxRightBorderSum)
return MaxRightSum;
else
return MaxLeftBorderSum + MaxRightBorderSum;
}我们来计算这个算法的时间复杂度，首先是二分法，由之前的分析可以知道T(N1)=O(logN)；我们在循环中还有一层循环，这层循环时间复杂度为T(N2)=O(N)。我们来看二分法和循环的关系，循环中的变量是二分而确定的，故当使用二分的时候，其时间复杂度是由循环的时间复杂度*二分复杂度的，这里只有一层for，故最后它的时间复杂度为O(NlogN)。
缺点：这样的递归明显比O(N^2)的遍历法好很多，但是递归需要使用二分法才能有效降低时间复杂度，不用二分法的话速度还不如遍历法。二分法所需要思考与编写的代码量就会大大多于遍历法。用分治法一般都需要辅助数组，所需时间复杂度至少为O(NlogN)。而且只有当子问题的解通过合并可以得到原问题的解，并且子问题易解时才可用。不过算起来分治法是比较稳定的算法了。
四、联机算法
我们上面写出的分治法是基于递归的最优算法啦，我们循环和递归都测试过了，循环中影响时间复杂度的是循环，而递归中也是循环的层数，我们没有办法去优化这个循环了，所以还要优化的话我们就必须去掉循环才能使时间复杂度降低了。
我们先来看循环一般做些什么。在遍历法里：
for(int j=i;j<N;j++)
{
ThisSum += A[j];
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}这个循环是固定了左引索i，移动了右引索j，每次相加储存到ThisSum里计算和，再进行比较。其中有一个存储了计算数据的操作。
我们再看分治法中的循环：
for (int i = Center - 1; i >= Left; --i)
{
LeftBorderSum += A[i];
if (LeftBorderSum > MaxLeftBorderSum)
MaxLeftBorderSum = LeftBorderSum;
}这里是分治法中左部分的和，也是执行了相加求和，储存数据再比较的过程。
所以我们发现，最占时间的其实是存储数据的过程，因为遍历法和分治法中需要通过循环来相加得到结果，必须要存储上一步的数据才能进行相加。所以我们要想再对算法进行优化，就必须舍弃存储全部计算数据这个操作！
所以我们现在目标就是：一旦A[i] 被读入并被处理，它就不再需要被记忆。并且在任何时候算法都可以对这些数据进行处理。我们一般把这样特征的算法称为联机算法（Online Algorithm）。
我们举一个简单的例子来理解联机算法与我们平时常写的脱机算法的区别：
对联机算法而言，中途每一次读入数据产生的结果都是满足要求的结果，其结果的产生是基于对当前及过去的所有输入，可以理解为：“热炒热卖”、“炒多少，卖多少，炒好一盘上一盘”，相当于炒菜，这也正和“联机算法”中“Online”的意义不谋而合。
而脱机算法则是利用所有的数据参与计算，最终得到一个结果，其时间复杂度是非线性的，需要对数据多次扫描，无法像联机算法一样顺序读入并出结果，可以理解为：“菜全部做好了再开始营业”，相当于自助餐厅。
不需要记忆A[i]意味着，我们的顺序很重要，因为它只会读一次。所以就要求我们每一步都要做出在当前看来最好的选择。我们把整体最优解可以通过局部最优解找到时，在每一步总是做出在当前看来是最好的选择的算法称为贪心算法或贪婪算法（Greedy Algorithm）。
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。这就很符合联机算法的情况。
若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。所以我们还需要找到这样的一个不可行的情况才能实现贪心算法。
我们看回这题：
给你一个整数数组
nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组 是数组中的一个连续部分。整数项可以是负数，如果所有整数都是负数，那么最大子序列和为0；
观察计算过程，因为该问题不需要最大序列和的坐标输出，所以我们不需要记忆序列位置，仅仅记忆当前最大序列和的值即可。所以我们可能存在重复的地方就是计算了一个可能比目前最大值小的子序列和。
子序列的和是和之前的子序列的值加上当前元素组成的。我们用sum表示之前的子序列和，所以在第i个位置的子序列和ThisSum = sum + A[i]，接下来我们就需要进行比较了。
MaxSum = (MaxSum<ThisSum)?ThisSum:MaxSum;判断并更新（或没有更新）了最大值。
但是这样就会有一个问题，左引索一直是固定的，如果我们要移动左引索必须要使用两重循环，这就导致了我们计算了无用子序列。
什么是无用子序列呢？我们看看例如A{1,-2,2,3,-1}，我们计算到第二个子序列{1，-2}它们的和为-1<0，根据题目描述，如果全为负数结果为0，说明和为负数的项都是相加了一个负数而导致的，它就不可能是最大的子序列和，就应该淘汰包含这个子序列的其他子序列。
举例：{1,-2,2}是由该子序列生成的下一子序列，和为1，还不如单走一个2>1。所以包含{1，-2}的子序列都不是最佳答案。
当“连续和”为负数的时候就应该从下一个元素重新计算“连续和”，负数加上下一个元素 “连续和”只会变小不会变大。
所以这个由该子序列生成的子序列就是无用的了，我们就可以把它淘汰：{1,-2,2}、{1,-2,2,3}、{1,-2,2,3,-1}
所以我们发现了，要淘汰这些子序列，我们就需要对左引索进行更改而不使用两重循环。我们只需要把ThisSum给重置为0，就相当于了把左引索重置为了当前的i，之后的ThisSum计算就是从i开始的了。
到这里我们就已经清楚了：我们可以避免重复计算的地方是无效子序列生成的子序列，要记住的是最大的值和当前相加的值，还有一个重要的要求：
一个子序列，如果一旦他的前若干个数字组成的新的个数更少的子序列的和为负数，那么去掉这个子序列，便能得到了一个更优解。
去掉的方法就是重置当前已经计算的子序列和，从新的位置重新开始计算子序列和。
理解以后我们的代码就很容易了：
int MaxSubSequenceSum(const int A[], int N)
{
int ThisSum, MaxSum, j;
ThisSum = MaxSum = 0;
for (j= 0; j < N; j++)
{
ThisSum += A[j];
if (ThisSum > MaxSum)
{
MaxSum = ThisSum;
}
else if(ThisSum < 0)
{
ThisSum = 0;
}
}
return MaxSum;
}如此我们就使用联机算法解决了这个问题。它的好处就在，我们没有把每一个子序列和都计算出来比较，它只对数据进行一次扫描，一旦A[j]被读入并被处理，它就不再需要被记忆。
我们怎么证明这样的算法能正确的找到最大的子序列呢？我们通过一个实例来确认一下：
若A = {-2,1,-3,4,-1,2,1,-5,4}，下面的序号表示第(j+1)次循环的情况。初始状态下
ThisSum = MaxSum = 0;我们还用Sum表示第(j-1)次即上一次的ThisSum的值。
- j=0，A[j] = -2，Sum = 0 ，ThisSum = -2，-2<0 => MaxSum = 0；
- j=1，A[j] = 1，Sum = 0 ，ThisSum = 1， MaxSum = 1；
- j=2，A[j] = -3，Sum = 1 ，ThisSum = -2，-2<0 ， MaxSum = 1；
- j=3，A[j] = 4，Sum = 0 ，ThisSum = 4，4>1 => MaxSum = 4；
- j=4，A[j] = -1，Sum = 4 ，ThisSum = 3，3<4 => MaxSum = 4；
- j=5，A[j] = 2，Sum = 3 ，ThisSum = 5，5>4 => MaxSum = 5；
- j=6，A[j] = 1，Sum = 5 ，ThisSum = 6，6>5 => MaxSum = 6；
- j=7，A[j] = -5，Sum = 6 ，ThisSum = 1，1<6 => MaxSum = 6；
- j=8，A[j] = 4，Sum = 1 ，ThisSum = 5，5<6 => MaxSum = 6；
我们经过N步就找到了最优解6，因为在第一的时候，ThisSum<0，此时说明，以A[0]开头的子序列都不会是最优解，贪心算法不会选择这样的不是最优的情况，此时ThisSum被重置为0。第三步也如此。
我们第二步的时候就找到当时的最优解1，在第三步的时候因为ThisSum<0，所以继续保留最优解，直到第四步发现当时的更优解替换这个结果。
我们每一次都为了局部最优解，每一步只考虑一个数据来与最优解比较。这样就可以把避免那些非最优解的情况。
接下来基于上面的正确例子，我们使用反证法来证明贪心算法在这题中是最优解法：
反证的基本思想就是：先依靠贪心算法得出最优解，再证明：将任意步骤的决策替换为任意的其他选择，最后结果都不可能达到更优。
如上步骤，我们找到了最佳的结果就是：{4,-1,2,1}，其中在第三步时的ThisSum=-2<0，若我们没有重置ThisSum，那么就会找到结果{-2,4,-1,2,1}，很明显是一个以负数开头的子序列，它不可能是和最大的。同理在第八步也是如此。
我们设该算法找到的最佳结果是：{N1,N2,N3,N4,...,Nm}，现在用任意数N加入它们任意位置，则为{N,N1,N2,N3,N4,...,Nm}
- 如果N<0，此时很明显，这是一个以负数开头的子序列，故不可能是最好的结果。
- 如果N>0，此时因为是连续的序列，所以这个N在算法中一定会被算法认为最佳结果之一，故一定存在N=N1或N2或...Nm的情况，所以不会改变能找到最佳结果的事实，因为它的出现一定会被算入内。
这两种情况都不会得到更优的结果，故反证错误，原设成立。
我们还可以通过数学归纳法（递推法）来证明它：
原理就是：一旦我们证明了在某个起点值时命题成立，且证明出从一个值到下一个值的过程有效，那么任意值都可以通过反复使用这个方法推导出来
数组A：{N1,N2,N3,N4,...,Nm}
在第一步中，如果N1>0，此时的局部最优解很容易知道就是N1。如果N1<0，此时局部最优解还是0，因为题目说负数的数列最大值就是0。故算法成立。
设在在第k步时成立，即此时：
- 当Nk>0时，ThisSum = Sum+Nk, MaxSum = ThisSum;
- 当Nk<0时，
- 若ThisSum<0 => ThisSum = 0 , MaxSum = max{ThisSum, MaxSum};
- 若ThisSum>0 => ThisSum = Sum+Nk, MaxSum = max{ThisSum, MaxSum}.
欲证明：(k+1)步成立。 若设S为第k步时的Sum，
- 当N(k+1)>0时，此时的最优解就是加入这个值就能找到，
- 若Nk>0，那么此时N(k+1)步时：ThisSum = S+Nk+N(k+1), MaxSum = ThisSum;
- 若Nk<0，ThisSum = 0时，此时N(k+1)不能和Nk构成子序列，因为以负数开头的子序列和不可能是所有子序列里的最大和，ThisSum = N(k+1)，MaxSum = max{ThisSum, MaxSum};
- 若Nk<0，ThisSum > 0时，此时加上N(k+1)这个正数肯定是可以增加子序列和的，故ThisSum = S+Nk+N(k+1), MaxSum = ThisSum;
- 当N(k+1)<0时，
- 若Nk>0，ThisSum = S+Nk，
- 若ThisSum>0 => ThisSum = S+Nk+N(k+1), MaxSum = max{ThisSum, MaxSum};
- 若ThisSum<0 => ThisSum = 0, MaxSum = max{ThisSum, MaxSum};
- 若Nk<0，ThisSum = 0，此时无论怎么加，都是一个负数，故ThisSum = 0, MaxSum = max{ThisSum, MaxSum};
我们发现红体的式子存在从k到k+1的递推关系，故(k+1)步满足k步的方程，算法成立。
我们从例子可以发现，联机算法配合贪心算法非常适合这一题。是因为我们的整体最优解可以通过局部最优解求出。如果是不能的话则无法使用贪心算法。所以我们很容易得出贪心算法的适用范围：
满足贪心算法的题目一般需要：
- 最优子结构：规模较大的问题的解由规模较小的子问题的解组成，规模较大的问题的解只由其中一个规模较小的子问题的解决定；
- 无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
- 贪心选择性质：从局部最优解可以得到全局最优解。
我们最经典的情况就是找到最小生成树的Prim 算法和 Kruskal 算法，这里就不细说了之后会慢慢讲的。
作业
作业部分因为还没有上传，故该部分内容将在2022.10.3才会自动公开。
Lec01
problem1
请编写一个程序，它在一个字符串中进行搜索，查找所有在一个给定字符集合中出现的字符。这个函数的原型应该如下：
char *find_char(char const *source,char const *chars);它的基本想法是查找source字符串中匹配chars字符串中任何字符的字符，函数然后返回一个指向source中第1个匹配所找到的位置的指针。如果source中的所有字符均不匹配chars中的任何字符，函数就返回一个NULL指针。如果任何一个参数为NULL，或任何一个参数所指向的字符串为空，函数也返回一个NULL指针。
举个例子，假定source指向ABCDEF。如果chars指向XYZ、JURY或QQQQ，函数就返回一个NULL指针。如果chars指向XRCQEF，函数就返回一个指向source中C字符的指针。参数所指向的字符串是不会被修改的。
要求：a.你不应该使用任何用于操纵字符串的库函数（如strcpy,strcmp,index等）。
b.函数中的任何地方都不应该使用下标引用。
分析：这个题目其实就是给两个字符串，在source字符串中搜索到任何一个chars字符串中的字符时返回它的地址。注意是任何一个，不一定是全部匹配。这题还是比较简单的，这里直接给出我的解决方案。
char *find_char(char const *source, char const *chars)
{
if(chars == NULL) return NULL;
char *p_c=(char *)chars; //pointer of chars
char *p_s=(char *)source; //pointer of source
while(*p_s != '\0')
{
do
{
if(*p_s == *p_c)
return p_s;
} while (*p_c++ != '\0'); //相当于在source里找到一位字符，然后与chars每一位进行比较
p_s++;
}
return NULL;
}这里的*p_c++写法，因为*和++的优先级相同，它们的遍历顺序是从右到左，所以先执行++再执行*。++先返回了原来的值，让这个值进行了*操作，返回*操作的结果，再对指针p_c++。这里do...while导致了最后一次是和'\0'比较，会多一次比较，可以使用while代替do...while。
problem2
编写函数删除一个字符串中的一部分，函数原型如下：
int del_substr(char *str, char const *substr);函数首先应该判断substr是否出现在str中，如果它并未出现，函数就返回0；如果出现，函数应该把str中位于该子串后面的所有字符复制到该子串的位置，从而删除这个子串，然后函数返回1。如果substr多次出现在str中，函数只删除第一次出现的子串。函数的第2个参数绝不会被修改。
假定str指向“ABCDEFG”这个字符串，如果substr指向"FGH"、"CDF"或者“XABC”时，函数应该返回0，str未作修改。如果substr指向"CDE"，函数就把str修改为指向“ABFG”，方法是把‘F’、‘G’和最后的'\0'都一起复制到‘C’的位置，然后函数返回1。
要求：
a.你不应该使用任何用于操纵字符串的库函数（如strcpy,strcmp,index等）。
b.函数中的任何地方都不应该使用下标引用。
分析：这个题目是先找到str中的第一个子串substr，如果没找到就返回0，找到了就删除它，若有多个就删除第一个就行，最后返回1。其实我们要做的就是，先找到子串的位置，然后数组后面的数据往前覆盖即可。因为C语言中字符串读到第一个'\0'就结束了，故后面删除后多出的重复段可以不用管它，或者手动清除。这里也直接给出代码，其中寻找子串的函数是problem1修改的。
char *finds_char(char const *source, char const *chars)
{
if(chars == NULL) return NULL;
char first_char=*chars; //record first char
int len=0;
char *p_c=(char *)chars; //pointer of chars
while(*p_c++ != '\0') //get lenth of chars
len++;
char *p_s=(char *)source; //pointer of source
while(*p_s != '\0')
{
if(*p_s == first_char)
{
int flag=0; //flag records condition of match, if 0, we found. if 1, not.
for(int i=1;i<len;i++)
{
if(*(p_s+i) != *(chars+i))
{
flag=1;
break;
}
}
if(!flag) //found
return p_s;
}
p_s++;
}
}
int del_substr(char *str, char const *substr)
{
if(*str == '\0') return 0;
if(*substr == '\0') return 1; //do not need change
str=finds_char(str,substr);
if(str == NULL) return 0; //no found substr in str
int len=0;
char *p_sub=(char *)substr; //pointer of substr
while(*p_sub++ != '\0') //get lenth of substr
len++;
char *tail=str+len;
do
{
*str++ = *tail++; //tail array replaced
} while (*tail != '\0'); //avoid *tail==\0 and tail++ is not defined.
*str='\0';
return 1;
}注意：最后这里的*str++ = *tail++，是尾部指针跟随着子串位置移动，同之前problem1的方法看优先级。
Lec03
3.15 a
写出自调整(self-adjusting)表的数组实现。自调整表如同一个规则的表，但是所有的插入都在表头进行，当一个元素被Find 访问时，它就被移到表头而并不改变其余的项的相对顺序。
分析：这个很简单，就是当它被找到的时候把它移到数组头部即可，其他的依次后退。实际上只需要找到的那个元素前面的元素们往后覆盖一格就行。
int Find(int n, int *arr, int d)
{
int count=0;
for(int i=0;i<n;i++)
if(arr[i] == d)
{
for(int j=i;j>0;j--)
{
arr[j]=arr[j-1]; //replace position
}
*arr=d; //move to top
count++;
}
return count;
}注意：我返回的是找到的数量。
3.16 b'
假设我们有一个基于数组的表A[0... N-1] ，并且我们想要删除所有相同的元索。LastPosition 初始值为N - 1, 但该值随着相同元素被删除而变得越来越小。考虑图中的伪码程序段。过程Delete 删除位置j上的元素并使表破坏。
使用数组重写这个过程。
分析：我们看题目的代码感觉就像是冒泡法排序的类似想法去查重并删除，而用数组去实现也可以直接按照它的思想来做。
int Delete_Same(int *A, int n)
{
int LastPosition = n-1;
int flag=0;
for(int i=0;i<n-1;i++)
{
int j=i+1;
while(j <= n-1)
{
if(A[i] == A[j])
Delete(j,A,n),LastPosition--,flag=1; //flag means has deleted
else j++;
}
if(flag) Delete(i,A,n),LastPosition--;
flag=0;
}
return LastPosition;
}
void Delete(int x,int *A, int n)
{
for(int i=x;i<=n;i++)
A[i]=A[i+1];
}Lec04
3.15 b
写出自调整(self-adjusting)表的数组实现。自调整表如同一个规则的表，但是所有的插入都在表头进行，当一个元素被Find 访问时，它就被移到表头而并不改变其余的项的相对顺序。
用链表实现
分析：这题和前面的a题基本一样，不同的就是使用链表实现了，而链表不需要覆盖替换，只需要把next指针指向改变就可以啦。
typedef int Data_type;
typedef struct self_list
{
struct self_list *next;
Data_type d;
}L;
L* ini(int n, Data_type *arr);
L* ini(int n, Data_type *arr)
{
L* head=NULL;
L* t=head; //record previous node
for(int i=0;i<n;i++)
{
L* p=(L*)malloc(sizeof(L));
p->d=arr[i];
p->next=NULL;
if(i == 0) head=p;
else t->next=p;
t=p;
}
return head;
}
void Finds(L* head, Data_type d)
{
L*p=head;
int count=0;
while(p->next != NULL)
{
if(p->next->d == d) //find preview node
{
L* t=p->next->next; //record node's next node
p->next->next=head;
head=p->next; //move node to head
p->next=t; //link preview node to next node.
count++; //count found times
}
p=p->next;
}
printf("%d was found %d times, ",d,count);
printf("the first element of array is %d.\n",head->d);
}注意：我这里最后找的是目标节点之前的那个节点，因为使用的是单链表，next指针的替换需要知道前面的节点，不然不好连接，为了防止重新搜索一次，我们就直接搜索之前的节点就可以了。
3.16 b''
假设我们有一个基于数组的表A[0... N-1] ，并且我们想要删除所有相同的元索。LastPosition 初始值为N - 1, 但该值随着相同元素被删除而变得越来越小。考虑图中的伪码程序段。过程Delete 删除位置j上的元素并使表破坏。
使用链表重写这个过程。
分析：同样的，也是之前的3.16 b'的链表改编版，在这里我们要设计动态链表，删除的时候需要free节点。需要特判head节点，因为head没有前节点。
typedef struct Dlist
{
struct Dlist* next;
Data_type d;
}list;
list* Dini(int n, Data_type *arr)
{
list* head=NULL;
list* t=head; //record previous node
for(int i=0;i<n;i++)
{
list* p=(list*)malloc(sizeof(list));
p->d=arr[i];
p->next=NULL;
if(i == 0) head=p; //record head node
else t->next=p;
t=p; //move
}
return head;
}
list *Delete_bylist(list* head, Data_type d)
{
list *p=head;
int flag=0; //determine whether do delete, 0 not, 1 yes.
while(p)
{
list*t=p->next;
while(t)
{
list *tp=t->next; //record t->next, avoid t->next illegal since t was freed.
if(p->d == t->d)
{
Delete_Dlist(head,t);
flag=1;
}
t=tp;
}
list *tmp=p->next; //record p->next, avoid p->next illegal since p was freed.
if(flag) //delete itself
{
if(p == head) head=tmp; //if p is head, no not link preview node to next node.
Delete_Dlist(head,p);
flag=0; //reflash
}
p=tmp;
}
return head;
}
void Delete_Dlist(list* head, list* t)
{
list *p=head;
if(t == head) //if p is head, no not link preview node to next node.
{
free(t);
}
while(p)
{
if(p->next == t)
{
p->next=t->next;
free(t);
return;
}
p=p->next;
}
}
Comments NOTHING