20210326
微分方程（二）| 数据结构-线性表（六）| 恋词U5
微分方程（二）
常考题型与例题
- 方程求解
- 综合题
- 应用题
具体题目不在这里展示了。
数据结构-线性表-表的逆置（六）
逆置就是把表中元素调整成与原来相反的位置。
顺序表逆置
上面两图都是顺序表的逆置示意图，不同的是要逆置的元素个数不同，左边为偶数，右边为奇数。但是相同的是，两种情况下当i<j的时候，逆置结束（循环结束），所以不用做算法区分。
for (int i = left, j = right; i < j; ++i,--j)
{
tmep = a[i];
a[i] = a[j];
a[j] = temp;
}
单链表逆置
实现代码：
while(p->next != q)
{
t = p->next;
p->next = t->next;
t->next = q->next;
q->next = t;
}
例题
- 将一长度为n的数组的前端
k(k<n)个元素逆序后移动到数组后端，要求原数组中数据不丢失，其余元素的位置无关紧要。
分析：其实就是顺序表的逆置问题，只是循环条件改一下即可，只扫描到k个位置即可。
void reverse(int a[], int left, int right, int k)
{
int temp;
for(int i = left,j = right; i < left + k && i<j; ++i; --j)
{
tmep = a[i];
a[i] = a[j];
a[j] = temp;
}
}
注意：因为
left+k有可能大于表长的一半，所以需要i<j。
- 将一长度为n的数组的前端
k(k<n)个元素保持原序移动到数组后端要求原数组中数据不丢失，其余元素的位置无关紧要。
最容易想到的算法就是利用某种算法将前k个元素与后k个元素交换即可，但是这里不采用这种算法。可以先把前面要移动的元素逆置，第二步将已逆置前k个元素逆置到后端。
void moveToEnd(int a[], int n, int k)
{
reverse(a,0,k-1,k);
reverse(a,o,n-1,k);
}
408真题
将n(n>1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p(0<p<n)个位置，即将R中的元素(X0,X1..Xn-1)，经过移动后变成(Xp,Xp+1,..Xn-1,X0,X1,...Xp-1)。
(1) 给出算法的基本设计思想
(2) 根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。
(3) 说明你所设计算法的时间复杂度和空间复杂度。
分析：只需将
0~p-1位置的元素逆置，再将p~n-1位置的元素逆置，然后再将整个数组逆置即可。
1234567 //循环左移3位
4567123 //循环左移完毕
只需
123 -> 321 //将0~p-1位置元素逆置
4567 -> 7564 //将p~n-1位置元素逆置
3217654 //再将整个数组逆置
4567123 //完毕
答案
(1)其过程是将0~p-1位置的元素逆置，再将p~n-1位置的元素逆置，然后再将正数组逆置即可。
(2)
void reverse(int a[], int left, int right, int k)
{
int temp;
for(int i = left,j = right; i < left + k && i<j; ++i; --j)
{
tmep = a[i];
a[i] = a[j];
a[j] = temp;
}
}
void moveP(int a[], int n, int p)
{
revrese(a,o,p-1,p);
revrese(a,p,n-1,n-p);
reverse(a,0,n-1,n);
}
(3) 时间复杂度为：O(n)
空间复杂度为：O(1)
恋词U5
- define v.给..下定义；阐明；界定
- confine v.限制，使局限，关押，监禁 n.限制
- refine v.精炼；提炼；改进；改善
- might v.可能 n.力量
- revolve v.旋转，以...为中心
- evolve v.发展；演变；进化
- preoccupation n.抢先占有
- dwelling n.住宅；住所
- eliminate v.消除；排除
- preliminary adj.预备的；初步的
- metric adj.米制的，公制的
- reckon v.认为；估计；估算；指望；预计
- algorithm n.算法；计算程序
- acclaim v.向..欢呼；称赞；宣布
- disclaim v.放弃（财产、头衔等的权利）；拒绝承认
- exclaim v.（因兴奋、惊讶或愤怒而）呼喊，惊叫；大声说出
- assert v.断言、坚持、主张
- allege v.（未提出证据）断言
- contend v.竞争，辩论
- fiscal adj.财政的；国库的；税收的
- lucrative adj.赚大钱的，获利多的
- preface n.序言，前言；开端；序幕
- prescribe v.指定；规定；为..开药
- prescription n.处方；药方
- manuscript n.手稿；底稿；手抄本
- depict n.描述；描绘
- portray v.描绘；表演；刻画
- intellectual n.知识分子；脑力劳动者 adj.智力的，理智的；有才智的
- unanimous adj.全体一致的，一致同意的