2_4thinking.cpp 线性表

2017年9月24日 下午4:15

(1)
思路描述：
使用冒泡法。但是会交换变量，一个变量i不够用。这种方式不行；
i%10
i/10

i = 0*10 + 0 ;
while(i/10 < N-1){
	if(A[i/10] < A[i/10 + 1]){
		i = i/10 * 10 + A[i/10];
	}
	i = (i/10 +1) * 10 + A[i/10];
}

cout<<(i%10)<<endl;


#include<iostream>
using namespace std;
#define N  9
int main(){
    int i = 0;
    int A[N] = {8,2,3,4,5,6,7,1,9};
    i = 0 * 10 + A[0];//这里不能写成i = 0*10 + 0，否则0会作为比较的对象；这里用A中的谁都行
    
    while(i/10 < N-1){
        if(A[i/10] < i%10){//A[i/10] < A[i/10 + 1] 这里的比较对象错了。
            i = i/10 * 10 + A[i/10];
        }
        i = (i/10 +1) * 10 + i%10;
    }
    
    cout<<(i%10)<<endl;
}


// (2)
// 思路描述:
// 这要求L指向开始节点。
// 先统计一下一共有i个节点
// 然后统计每次i--;

void reprint(LNode *&L){
	LNode *
	while()
}

// 书本解释：在表不为空的情况下先递归的逆序打印表中的第一个数据之后的数据
我的解释：题可以这样理解：先打印出当前节点后面的data值，然后再打印当前节点的data值。
如果这么理解，把这句话翻译成程序的时候，不就自然使用递归了吗。
关键是你不会这么想
void rePrint(LNode *&L){
	if(L! = NULL){
		rePrint(L->next);
		cout<<L->data<<" ";
	}
}




// (3)
// 这道题中的一个条件3n/2这个条件，
// 我认为需要两个变量max min ，每次循环到一个A[i]的时候，就要比较两次，那么一共就要比较2n次
// 但是我忽略了min 和 max是相互矛盾的，所以比较一次就行了

// 其实也可以这样理解：书中的这种解法，就是抓住了矛盾，然后将我的算法优化了。
// 所以，优化的时候抓住矛盾对立面也是一种优化方式
void FindMaxMin(int A[],int n,int &max,int &min){
	max = min = A[1];
	for(int i = 2; i <= n;++i){
		if(A[i] > max){
			max = A[i];
		}
		else if(A[i] < min ){
			min = A[i];
		}
	}
}




// 综合应用题

// (1)
思路描述：
每个递归传入的都是i= 0；
先查询出当前节点后面的节点的个数，
然后自己本节点再i++;
判断自己是不是i==5
如果是则输出，并break
最后返回i，给上一个层


int findElem(LNode *&L,int i){

	if(L! = NULL){
		i = rePrint(L->next,i);
		i++;

		if(i==5){
			cout<<L->data<<" ";
			break;
		}
		return i;

	}
}



#include<iostream>
using namespace std;


typedef struct LNode{
    int data;
    struct LNode *next;
}LNode;


int findElem(LNode *&L){//由于这里每次都是传入i=0，所以可以直接写在程序里，不用作为参数。
    int i = 0;
    if(L != NULL){
        i = rePrint(L->next);
        i++;
        
        if(i==5){
            cout<<L->data<<endl;
            return 1;
        }
        return i;
        
    }
    return 0;
}

int main(){
    LNode *L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *r;
    r = L;
    
    LNode *p;//新产生的
    
    int a[7] = {1,2,3,4,5,6,7};
    int n = 7;//数组长度
    int i ;
    
    for(i = 0; i < n ;i++){
        p = (LNode *)malloc(sizeof(LNode));
        p->data=a[i];
        p->next = NULL;
        r->next =  p ;
        
        r = p;
        
    }
    findElem(L);
    
    
}



// 总结：我的这种使用递归的解法启发来源于上面的题，我在原来的基础上添加了返回值，也按上面说的把题概括成了能用递归来实现的语言。
// 但是我忽略了，题中要求返回值=1 代表成功，=0代表失败，这就说明我不能用返回值来表示层数，这就混乱了。
// 因此，我的解法是错的。


int findElem(LNode *&L){
	LNode *p = L->next;
	LNode *q = L;
	int i = 0;

	while(p!= NULL){

		p=p->next;
		i++;
		if(i>=5){ //这里不能写等于，大于5之后还有继续后移呢。
			q = q->next;
		}
	}

	if(q == L ){
		return 0;
	}
	else{
		cout<<q->data<<endl;
		return 1;
	}
		
}

// 总结：
// 我一开始的分析思路是：
// 第一步先循环到第5个
// 第二步判断是否有五个，如果有才开始从这里q才开始q = q->next;
// 如果没有5个直接return 0；

// 其实上面这的写程序也没问题。但是像书中的程序，他将第一步和第二步进行的融合，最后对于有没有5个，融合之后也有了统一的判断标准。

整体总结：
这篇thinking的题真的需要你思考
这些题不仅仅需要我们有在practice中总结的思维描述+特征
还加上了一些在完成功能的情况下，如何将代码进行优化，多个步骤的融合（上面这道题）+ 解决问题的技巧（第一道题） + 选择递归（第二题，需要对题进行递归的概括）+不是能完成功能的就是对的（上面这道题）


prictice :保证不要在思考算法过程中，还在为操作发愁。即便有了思维还担心自己写不出来，或者写的过程中被打断
thinking :需要一些思考，设计一些算法了。不是那种一看题就会的了。


// 如何提高自己设计算法的效率。

// （2）
// 基本思想：利用模n，比如说R[i]--> R[n-(k-i)] R[n-(k-i)]-->R[n-(k-i)]
// 实现步骤：

// 这道题我不会做！我知道最笨的方法。一个个移动。
// 问题出现哪里？：找不到其中的特点，不会使用其中的技巧。
这些题不是不会做，是找不到更好的方法。
好方法来源于哪呢？

void Reverse(int R[],int l ,int r){
	int i,j;
	int temp;
	for(i = l,j = r;i<j;++i,++j){
		temp = R[i];
		R[i] = R[j];
		R[j] = temp;
	}
}


void RCR(int R[],int n,int p){
	if(p<0||p>n){
		cout<<"ERROR"<<endl;
	}
	else{
		Reverse(R,0,p-1);
		Reverse(R,p,n-1);
		Reverse(R,0,n-1);
	}
}


// （3）
基本思想：计算全部元素出现的次数，直达一个元素个数过半。
优化：添加一个数组，标志每个元素是否已被查询过
实现步骤：双层循环遍历，复杂度（n方）

书中的算法：自己是肯定想不出来，我们不可能去推理证明这种算法的正确性，直接背会。
这些算法是其实是需要严格的理论证明，才可以使用的。
给我的感觉就是一道高数题，让你证明这个理论是正确的。

这么做的目的：将复杂度降为n（n)

int majority(int A[],int n){
	int i ,c ,count=1;
	c = A[0];
	for(i= 1; i<n;i++){
		if(A[i]==c){
			count++;
		}
		else{
			if(count > 0){
				count--;
			}
			else{
				if(cout>0){
					count--;
				}
				else{
					c= A[i];
					count= 1;
				}
			}
		}
	}


	if(count > 0 ){
		for(i = count = 0 ; i < n ;i++){//将count的清零，放在了for中
			if(A[i] == c){
				count++;
			}
		}
	}

	if(count>n/2){
		return c;
	}
	else{
		return -1;
	}


}