20210404

清·明 | 回顾 | 田静语法-C1-S2-1-1 | 数据结构-线性表习题

Table of Contents

清·明

算起来我已经三年没有去扫墓了。自从上了“远门大学”之后,清明节就没有回过去,回想起清明时节“热闹”的气氛,一个家族聚在一起,去祭奠家族中的祖先,尽管在山上总是被烟呛得掉眼泪,但也不也是我现在回想起来最深刻的记忆吗,害。

突然有点想家了。

回顾

恋词U1,U2,U3,U4,U5,U6


数据结构-习题-线性表(九)

  1. image.png

无需比较的元素越多,那么总的比较次数就越少呗!那怎么样无需比较的元素越多呢?

图一:(假定为升序归并)普遍归并操作为图一;可以发现当其中一个表归并完成之后,剩余的那个表表中元素一定是有序的并且都是大于结果表中的元素的,所以挨个插入到后面即可,无需比较。也就是剩余的这种无需比较的元素个数越多,总的比较次数就越少。 那怎么样总的比较次数最少呢?

图二:当然就是如图2的情景,其中一个表的最小的元素(即5)仍大于另外一个表的最大(即4)的元素,这样的结果就是4所在那个表都与5比较了一下,然后全部插入到结果表中,即5所在表中其他元素都不会参与比较,那么就是比较n次。

图三中,假定在归并之前先检查一下,其中某个表的第一个元素是否大于另外一个表的最后一个元素,如果大于,就把第一个表全部插入到结果表中,然后将第二个表也直接插入到结果表中即可,那么只需要比较1次。但是,但是归并操作就是逐个比较表头元素然后插入表中的操作,并不包含对特殊情况的检测,所以还是死心吧。

  1. image.png

学过头插法建表,建出来的表和输入顺序是相反的,这道题则类似。

void reverse(LNode *L)
{
LNode *p = L->next, *q;
L->next = NULL;
while(p != NULL)
{
q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
  1. image.png

顺序表找最值,按照学过的应该是找一个循环变量和临时变量来存最值。但题中要求不能用临时变量,只给了循环变量i。那么关键就在于位整数。可以将i用作两个用途,既可以作为循环变量也可以作为临时存储最值的变量。因为最值都是个位数,所以可以用i的个位来存储最值,i的高位(即除去个位之外的位数)来作为循环变量。

void findMin(int A[], int &i)
{
i = A[0]; //把A[0]存在i的个位上
while(i/10 <= N - 1) //把i/10作为循环变量
{
if(i%10 > A[i/10]) //i%10的意思是对i的个位数取值。这里意思为存储最小值的变量
{
i = i - i%10;
i = i + A[i % 10];
}
i = i + 10;
}
i = i % 10;
}
  1. image.png
  1. 逆序打印一个链表的值方法很多。比如可以把链表的值从头到尾压入到栈中,把栈中的数据逐个出栈,按出栈顺序打印的就是链表的逆序打印结果
  2. 递归函数。分治策略。
void reprint(LNode *L)
/* *L指的是要被逆序打印的单链表,L已经指向了开始结点 */
{
if ( L != NULL)
{
reprint(L->next);
cout<<L->data<<" ";
}
}

思想转变一下:写完函数头之后就假设已经完成了reprint(),他已经可以把一个链表逆序输出了,只要传入这个链表的开始结点即可。

在表不空的情况下先递归地逆序打印表中第一个数据之后的数据,然后打印第一个数据,即可实现单链表中数据的逆序打印。

奇妙!!............................ 文章指引->哎!

递归思想和分治策略引路->

  1. image.png

集合怎么比较相等?对应元素及个数也要相等。扫描两个链表,比较扫描到的元素,相等就跳过,扫描下一对。不等即能判定集合不相等。

int isEqual(LNode* A, LNode* B)
{
LNode* p = A->next;
LNode* q = B->next;
while(p != NULL && q != NULL)
{
if(p->data == q->data)
{
p = p->next;
q = q->next;
}
else
return 0;
}
if( p != NULL || q != NULL)
return 0;
else
return 1;
}

田静语法-C1-S2

C1-S1回顾

双宾是人+物,宾语+宾补是可以用“是”去连接的。

eg: ...our president calls himself "the Decider".
himself is "the Decider"。√,所以是主谓宾补结构。

C1-S2-1-谓语动词的时态

谓语动词出现一定伴随时态!!!

image.png

课后练习

比较简单,不在这里展示了!

哈哈哈哈哈哈哈草

image.png