真题仿造

（1）p259
基本思路：
这道题的特点是：前负数后正数,无需进行精确排序
我的方法是：i从左向右，指向第一个>=0的数，j从右向左，指向第一个<0的数。直到相遇

void Resort(int R[],int n){
    int low = 0;
    int high = n-1;
    
    int temp ;
    
    while(low != high){
        // 找到下一大于等于0的
        while(R[low] < 0 && low < high){
            low++;
        }
        // 找到下一小于0的
        while(R[high] >= 0 && low < high){
            high--;
        }
        // low，high位置上元素交换
        if(high != low){
            temp = R[low];
            R[low] = R[high];
            R[high] = temp;
        }
    }
}


（2）p259
基本思路：
把题读完，吓我一跳，这只能是0,1,2,3......,n-1
和A一点关系都没有啊

for(i = 0; i < n; i++){
	B[i] = i;
}

书上的答案：
总结出来的规律是：关键字值本身即指向了这个关键字在数组中的位置。
void Sort(int A[],int B[], int n){
	int i;
	for(i = 0; i < n; i++){
		B[A[i]] = A[i];
	}
}

总结：
这道题出的真恶心！


综合应用题：p263

（1）p262
基本思路：
很简单，先统计出c，然后在R[c]中放入

void countSort(int A[],int n,int B[]){
    int i ,j;
    int c = 0;
    for(i = 0; i < n; i++){
        c = 0;
        // 统计
        for(j = 0; j < n ;j++){
            if(A[j] < A[i]){
                c++;
            }
        }
        // 插入
        B[c]= A[i];
    }
}



（3）
p263
基本思路：
以前的冒泡每次从R[0]开始遍历，都是相同的方向。每次遍历都拿出本次最大的数放在最后
这次：每趟遍历都是从左到右，再从右到左。在一趟中要找到一个最大值和一个最小值

void BubbleSort(int R[],int n){
    int p = 0;
    int q = n-1;
    int i;
    int temp;
    
    while(p < q){//这里不能写 p != q ,反例是R中元素是偶数
        // 右边最大值
        i = p;
        while(i < q){
            if(R[i] > R[i+1]){
                temp = R[i];
                R[i] = R[i+1];
                R[i+1] = temp;
            }
            i++;
        }
        q--;
        
        // 左边最小值
        i = q;
        while(i > p){
            if(R[i-1] > R[i]){
                temp = R[i];
                R[i] = R[i-1];
                R[i-1] = temp;
            }
            i--;
        }
        p++;
    }
}

问题：
1.结束的标志
2.相同值得情况：无所谓，换不换都行。

描述一个最通用情况：p指向左边第一个没有排序的，q指向右边第一个没有排序的，i指向当前指针位置
i = p开始，直到i+1 = q,此时找到一个最大值放在R[q],q--
从i = q开始，直到i-1 = p,此时找到一个最小的值放在R[p],p++
当 p < q是停止


（8）p264
基本思路：
我想起我一个数组的插入排序我就写的三次才对，就生气😡！
直接插入排序最基本步骤是：找到位置，插入
这道题中将数组变成了链表，链表适合于插入操作，因此，应该更容易操作

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


void insertSort(int R[],int n,LNode *&h){
	// 这里的h只是一个指针变量，还没有连接上头结点
	int i;
	LNode *temp;
	LNode *pre;

	// 初始化头结点
	h = (LNode *)malloc(sizeof(LNode));
	h->next = NULL;
	h->data = 0;


	// 循环，每次插入一个R[i]
	while(i < n){
		// 产生新的节点
		temp = (LNode *)malloc(sizeof(LNode));
		temp->data = R[i];
		temp->next = NULL;

		// 找到合适的位置,从后前向后找，知道这个元素小于下一个元素
		pre = h->next;
		while(pre->next->data < pre->data && pre->next != NULL){
			pre = pre->next;
		}

		// 插入
		temp->next = pre->next;
		pre->next = temp;

		// 下一次循环，下一个值
		i++;
	}
}

修正版：共两处修改
#include <iostream>
using namespace std;
#define maxSize 100
typedef struct LNode
{
    int data;
    struct LNode *next;
}LNode;


void insertSort(int R[],int n,LNode *&h){
    // 这里的h只是一个指针变量，还没有连接上头结点
    int i = 0;
    LNode *temp;
    LNode *pre;
    
    // 初始化头结点
    h = (LNode *)malloc(sizeof(LNode));
    h->next = NULL;
    h->data = 0;

    // 循环，每次插入一个R[i]
    while(i < n){
        // 产生新的节点
        temp = (LNode *)malloc(sizeof(LNode));
        temp->data = R[i];
        temp->next = NULL;
        
        // 找到合适的位置,从后前向后找，知道这个元素小于下一个元素
        pre = h;//修改地方1
        while(pre->next != NULL && pre->next->data < R[i]){//修改地方2
            pre = pre->next;
        }

        // 插入
        temp->next = pre->next;
        pre->next = temp;
        
        // 下一次循环，下一个值
        i++;
    }
}


int main(int argc, const char * argv[]) {
    int n = 7;
    int R[7]={3,6,5,1,4,2,7};
    LNode *h;
    insertSort(R, n, h);
    
    LNode *pre = h->next;
    while(pre != NULL){
        cout<<pre->data<<endl;
        pre = pre->next;
    }
    return 0;
}




下面是作者的方法：
他的思路是：先把所有的R中的元素全部连接成链表，然后在链表中排序;并且它的选取的数据类型是char

void CreateLink(LNode *&h,char R[],int n){
	int i ;
	LNode *s,*t;
	// 建立头结点
	h = (LNode*)malloc(sizeof(LNode));
	h->next = NULL;
	t = h;
	// 把R中的元素放到链表中
	for(i = 0; i < n ;i++){
		s = (LNode *)malloc(sizeof(LNode));
		s->data = R[i];

		t->next = s;
		t = s;
	}
	// 做好
	t->next = NULL;
}


void Sort(LNode *h){
	LNode *p,*p1;
	LNode *q,*pre;

	if(h->next != NULL){
		p = h->next->next;//p指向第二个关键字节点
		h->next->next = NULL;//产生只带一个节点的有序表

		while(p != NULL){
			pre = h;
			q = pre->next;

			// 在有序表中找到一个节点q,起data值刚好大于p->data
			while(q != NULL && q->data < p->data){
				pre = q;
				q= q->next;
			}

			p1 = p->next;
			p->next = pre->next;
			pre->next = p;
			p = p1;
		}

	}
}
总结：
我没看懂他写的 sort()f方法！！！！！





时间复杂度 + 是否稳定 

把这些方法汇总一下
每种方法的作用

插入类排序：
1.直接插入
2.折半插入
3.希尔排序：这里我没有写他的代码，我就是想了解一下，有时间的后面补充

我的错误答案1：
void InsertSort(int R[],int n){//又是数组的标准参数模式
    int i, j;
    int temp;
    
    for(i = 0; i < n; i++){
        for(j = i-1; j >= 0; j++){
            if(R[i] < R[j]){
                temp = R[i];
                R[i] = R[j];
                R[j] = R[i];          
        }
    }
}


我的错误答案2：
void InsertSort(int R[],int n){//又是数组的标准参数模式
	int i, j;
	int temp;

	for(i = 0; i < n; i++){
		// 拿上当前这个，把他放到正确的位置，其他的后移
		// 有特殊情况
		temp = R[i];
		for(j = i-1 ; j >= 0;j--){
			if(R[j] > temp){
				// 后移
				R[j+1] = R[j];
			}
		}

		// j+1的位置是空的
		R[j+1] = temp;
	}
}


我的正确答案：
void InsertSort(int R[],int n){//又是数组的标准参数模式
    int i, j;
    int temp;
    
    for(i = 0; i < n; i++){
        // 拿上当前这个，把他放到正确的位置，其他的后移
        // 有特殊情况
        temp = R[i];
        for(j = i-1 ; j >= 0;j--){
            if(R[j] > temp){
                // 后移
                R[j+1] = R[j];
            }
            else{
                break;//当找到第一个R[j] <= temp 就停止了！！！！！
            }
        }
        // j+1的位置是空的
        R[j+1] = temp;
    }
}


书上的答案：
void InsertSort(int R[], int n){
	int i,j;
	int temp;

	for(i = 1; i < n;i++){
		temp = R[i];
		j = i-1;
		// 找到第一个刚刚大于前一个数的位置就停止，顺便再把位置移动了。
		while(j >= 0 && temp < R[j]){
			R[j+1] = R[j];
			j--;
		}
		// 将当前数放到找到的位置上
		R[j+1] = temp;
	}
}


总结：
刚刚开始第一个排序就狠狠地摔了一跤！！！！
总结其原因发现：是排序的这些题，在生活中太常见了，觉得看一眼就会了。但是，正是这样让我没有仔细的去分析总结他的规律步骤，囫囵吞枣，知道点大概意思就去动手写程序，我不错谁错。
解决方法：“想法转换成步骤”这第一步，就要老老实实的举例子，分析总结他的规律步骤，特别是循环的条件，边界，以及步骤有哪些，这是分析的重点。分析清楚了再去写程序


折半插入（二分查找）
我不理解书上p238的折半最优时间复杂度为 O(nlog2n) 
http://www.cnblogs.com/QG-whz/p/5194569.html
这个要涉及到我按算法涉及课上虚的时间复杂度的计算。

基本思路：
折半插入于直接插入的最大改进：他们查找插入位置的方法不同。

#include <iostream>
using namespace std;
#define maxSize 100

void binarySort(int R[],int n,int num){
    // 找见位置
    int i = 0;//标志左边
    int j = n-1;//标志右边
    int mid;
    
    while(i <= j){
        // 求中间位置,向下取整
        mid = (i+j)/2;
        
        // 判断中间值得大小，改变区域的范围
        if(R[mid] > num){
            j = mid - 1;
        }
        else{
            i = mid + 1;
        }
    }
    
    // 移动
    for(int k = n-1; k>=i ;k--){
        R[k+1] = R[k];
    }
    
    // 插入
    R[i] = num;
}


int main(int argc, const char * argv[]) {
    int n = 4;
    int R[8]={1,3,5,7};
    binarySort(R, n, 7);
    
    int i;
    for(i = 0; i < 5;i++){
        cout<<R[i]<<endl;
    }
  
    return 0;
}
注：我这里只是插入了一个数据

思考这道题的思维过程：
先提出问题：这里的特殊情况有？
1.R中有偶数个元素，和奇数个元素
2.循环继续的条件是 i < j 还是 i <= j？
3.如果我插入的元素R中已存在，是否还是正确的？

上面的这些问题，不是推理出来的，是拿例子试出来的。

你可能会问的几个问题：
为啥 while(i <= j) ? 这里的i <= j是如何确定的
为啥 R[i] = num;？这里为啥插入点是i，j不行吗？
为啥  R[mid] == num 为啥要算到i = mid + 1里？

回答：让我想起一句话“经试验证明......是对的”！！！！！！！！！！！！！！！！！！！

综上所述：
根据上面总结中的这章知识的特点，我觉认为学习这章最重要的是：通过各种不同情况的下的例子，各种特殊情况都要进行测试，最后找到所谓的通式。并且对于循环的条件、边界、步骤要专门的整理。
也就是说：要侧重于“想法转换成步骤”，写程序可以先放放

这章的东西总的来说，粗鲁野蛮，没有逻辑，就是这，你要咋！
这章教会了一个做人的道理：哪有那么多为啥，让你干啥你干啥就行，婆婆妈妈的！😀


交换类排序
1.起泡排序
2.快速排序

void BubbleSort(int R[],int n){
	// 一共有n轮，第一轮n个元素，第二轮n-1个元素......每轮都选取本轮中元素最大的值放到最后
	int i,j;
	int temp;

	for(i = 0; i < n;i++){
		for(j = 0 ; j < (n-i)-1; j++){//n个元素只需比较n-1次
			if(R[j] > R[j+1]){
				temp = R[j];
				R[j] = R[j+1];
				R[j+1] = temp;
			}
		}
	}
}


void BubbleSort(int R[],int n){
	// 一共有n轮，第一轮n个元素，第二轮n-1个元素......每轮都选取本轮中元素最大的值放到最后
	int i,j;
	int temp;
	int flag;

	for(i = 0; i < n;i++){
		flag = 0;
		for(j = 0 ; j < (n-i)-1; j++){//n个元素只需比较n-1次
			if(R[j] > R[j+1]){
				temp = R[j];
				R[j] = R[j+1];
				R[j+1] = temp;

				flag = 1;
			}
		}
		if(flag == 0){//一趟排序如果没有关键字发生交换，则证明序列有序，排序结束
			return;
		}
	}
}

总结：
记住这个flag，来减少一下工作量


快速排序：
基本思想：
输入是给定起始和终止的数组
输出是空
使用递归，每层递归的任务是：找到给定数组中的一个关键字（通常是第一个），在当前序列中保证关键字左边小右边大，最后分发左右在去完成递归

void QuickSort(int R[],int low,int high){//这里的low 和high是下标

	if(high > low){
		int i = low;
		int j = high;
		int key;
		// 找到关键字
		key = R[i];

		// 一趟快排
		while(j > i){
			// j找小的，判j < i ,放到i位置上
			while(j >= low && R[j] >= key){//注意点1：这里如果写成R[j] > key 那么就不能处理相同点的情况
				j--;

				if(j == i){
					break;
				}
			}
			
			R[i] = R[j];

			// i找大的，判j < i ,放到j位置上
			while(i <= high && R[i] < key){
				i++;

				if(j == i){
					break;
				}
			}
			
			R[j] = R[i];
		}

		R[i] = key;
		// 递归分发
		QuickSort(R, low, i);//注意点2：这里不能写成QuickSort(R, low, i+1);QuickSort(R, i, high); 这样也同样不能处理相同点的情况。书上的哪个具体的例子就可以清楚的反应出来
		QuickSort(R, i+1, high);
	}
}


书上的答案：
#include <iostream>
using namespace std;
#define maxSize 100

void QuickSort(int R[],int low,int high){//这里的low 和high是下标
    
    if(high > low){
        int i = low;
        int j = high;
        int key;
        // 找到关键字
        key = R[i];
        
        // 一趟快排
        while(j > i){
            // j找小的，判j < i ,放到i位置上
            while(j > i && R[j] >= key){//注意：这里是>=
                j--;
            }
            if(i < j){
                R[i] = R[j];
                i++;
            }
            
            // i找大的，判j < i ,放到j位置上
            while(i < j && R[i] < key){//注意：这里是 < 
                i++;
            }
            if(i < j){
                R[j] = R[i];
                j--;
            }
        }
        
        R[i] = key;//不要忘了最后将key放入
        // 递归分发
        QuickSort(R, low, i);
        QuickSort(R, i+1, high);
    }
    
}

int main(int argc, const char * argv[]) {
    int n = 8;
    int R[8]={49,38,65,97,76,13,27,49};
    QuickSort(R, 0, 7);
    
    int i;
    for(i = 0; i < n;i++){
        cout<<R[i]<<endl;
    }
  
    return 0;
}
作者的想法是：
如果j在向i方向走时，如果没有找到小于key的点时，那么，就让j停在i的位置上（不能超过i），此时i=j
也就是说，这一路上全是大于key的点。
实现的方法就是：  while(j > i && R[j] >= key)中的  j > i

作者比我的好在了：
在整个一趟快排的过程中，始终要求j >= i,其中的j = i就说明了他们相遇了，可以结束这趟快排了。
这就解决了我怕找不到相遇点的情况。
我的解决方法是：每次找到一个点时，我先判断一下此时j==i? 是的话，结束循环就行了。我没要的就是这个点，找到了就行了，其他的不管。


总结：
这道题中的特殊情况有：
1.数组中如果有相同的值，如何处理？
	代码注释中：注意点1+注意点2
2.如何能够找到相遇的点？
3.从左边开始，还是右边？


选择类排序
基本思路：
进行n-1次选择，第一次从0~n位置中选最小的,放在0位置上，第二次从1~n位置个中选最小的......



void SelectSort(int R[],int n){
	int i,j;
	int min;
	int temp;

	for(i = 0; i < n-1;i++){//n-1次
		min = R[i];
		// 选出最小的
		for(j = i; j < n;j++){
			if(min > R[j]){
				min = R[j];
			}
		}
		// 放入数组中
		R[i] = min;
	}
}

如果像上面一样那么数组中就会丢失数据
解决办法是：我们记住最小值的坐标，然后和第一个值R[i]进行交换


void SelectSort(int R[],int n){
	int i,j;
	int min;
	int temp;

	for(i = 0; i < n-1;i++){//n-1次
		// min每次初始化为第一个值
		min = i;
		// 选出最小的
		for(j = i; j < n;j++){
			if(R[min] > R[i]){
				min = j;
			}
		}
		// 放入数组中
		temp = R[min];
		R[min] = R[i];
		R[i] = temp;
	}
}


堆排序

// 本函数完成在数组R[low]到R[high]的范围内对在位置low上的节点进行调整
void Sift(int R[],int low,int high){
	int i = low,j = 2*i;//完全二叉树的性质
	int temp = R[i];
	while(j <= high){
		if(j < high && R[j] < R[j+1]){//若右孩子较大，则把j指向右孩子
			j++;
		}

		if(temp < R[j]){
			R[i] = R[j];
			i = j;
			j = 2*i;
		}
		else{
			break;
		}
	}
	R[i] = temp;
}

void heapSort(int R[],int n){
	int i ;
	int temp;
	// 建立堆
	for(i = n/2;i >= 1;i--){
		Sift(R,i,n);
	}
	// 进行n-1次循环，完成堆排序
	for(i = n; i >= 2;i--){
		// 以下三句换出了根节点中的关键字，将其放入最终的位置
		temp = R[1];
		R[1] = R[i];
		R[i] = temp;

		Sift(R,1,i-1);
	}
}

总结：
这道题我做不出的原因：
1.我提炼不出关键函数 sift(),这是由于我对题理解的不够透彻
2.我对这个关键函数用程序模拟不出这个过程
	1.这的树不是真的让你用指针去链一个树，就是一个一维数组。这是属于数据结构都不知道还做啥。
	2.这个过程中有很多不同的情况，我觉的很复杂。

我现在对“把思路转换成步骤”，这一步比较有经验了，主要有以下几点
1.要特意的去考虑特殊情况
2.先找见一个的比较大众，包含性强的情况去解决，然后在加上其他的特殊情况。（这样就条例很多了）


二路归并排序

void mergeSort(int A[],int low,int high){
	if(low < high){
		// 找到分界点
		int mid = (low+high)/2;
		// 把两边都排好序
		mergeSort(A,low,mid);
		mergeSort(A,mid+1,high);
		// 最后合并一下
		merge(A,low,mid,high);
	}
}

merge函数分析：
依照：“思路转换成步骤”
特殊情况有：
1.两边个数不相等，一奇一偶
2.如果两边有相同的数
3.一边的数全大于另一边的数


#include <iostream>
using namespace std;
#define maxSize 100

void merge(int A[],int low,int mid,int high){
    if(low != high){
        int i = low;//标志
        int j = mid+1;//标志
        int k;
        
        int B[maxSize];
        
        // 复制一份，因为在A上直接操作可能会丢失数据
        for(k = low; k <= high ;k++){
            B[k] = A[k];
        }
        
        k = low;
        while(1){
            // 找i,j对应位置数，比大小（相等时，选i）,小的数放入k位置上，k++；对应的i++/j++
            if(B[i] <= B[j]){
                A[k++] = B[i];
                i++;
            }
            else{
                A[k++] = B[j];
                j++;
            }
            // 看是否i++/j++之后到了边界,根据不同的情况，看是否继续循环
            if(i > mid || j > high){
                break;
            }
        }
        
        while(i <= mid){
            A[k++] = B[i++];//这里给忘了i++了，成了死循环
        }
        
        while(j <= high){
            A[k++] = B[j++];
        }
    }
}

void mergeSort(int A[],int low,int high){
    if(low < high){
        // 找到分界点
        int mid = (low+high)/2;
        // 把两边都排好序
        mergeSort(A,low,mid);
        mergeSort(A,mid+1,high);
        // 最后合并一下
        merge(A,low,mid,high);
    }
}

int main(int argc, const char * argv[]) {
    int n = 8;
    int R[8]={49,38,65,97,76,13,27,49};
    mergeSort(R, 0, 7);
    
    int i;
    for(i = 0; i < n;i++){
        cout<<R[i]<<endl;
    }
  
    return 0;
}

这章的基础能力：将矩阵（二维数组）压缩存储，顺序存储，链式存储都有。
最基本的就是要能通过代码能转换压缩成功。

当做一个题的时候，我们可能会因为想不出第一层的算法，而做不出题。这个是硬伤，没办法。
但是，又有很多时候，我们能表述出来我的的思想，但是就是没法下手，然后思想很有可能就走神了。
出现这种”我知道，但是我就是写不出来“的问题，我总结下来，很多时候都是自己的数据结构没有设计出来。
数据结构（结构体，数组，树，图，众多的变量...）这些其实是一个算法的实现起来的核心，
当数据结构设计出来的时候，也就是说明你的思维依托于代码已近走过一遍了，心中有谱了
因此，数据结构是代码实现的精髓。
当我们需要去记住一个算法的时候，他的数据结构设计一定是我们首先搞定的。


// 5-4 p117
第三层
#define maxSize 100;

void createTrimat(float A[][maxSize],int m,int n){//没有三元数组B[][3]
	//扫描有几个元素,建立三元组数组

	//再扫描，边扫边给三元组赋值
}


void createTrimat(float A[][maxSize],int m,int n,Trimat B[]){//有三元数组Trimat B[]
}

void createTrimat(float A[][maxSize],int m,int n,float B[][3]){//有三元数组float B[][3]
	//这里的B是空的，B[0]也是空的
	int i,j;
	int k = 1;//这里要从1开始

	//扫描，如果不为0，那么添加到B中
	for(i = 0 ; i < m;i++){
		for(j = 0 ; j < n ;j++){
			if(A[i][j] != 0){
				B[k][0] = A[i][j];
				B[k][1] = i;
				B[k][2] = j;

				k++;
			}
		}
	}
	B[0][0] = k -1;
	B[0][1] = m;
	B[0][2] = n;
}

总结：
1.以后记住，类似于这种"转换"类型的函数，转换前和转换后变量都作为参数传递
2.这里的类型是float，容易忽视

void print(float B[][3]){
	//i,j全部遍历。B中找到输出，找不到输出0

	int i,j;
	int k = 1;//从1开始

	for(i = 0;i < B[0][1];i++){
		for(j = 0; j < B[0][2];j++){
			if(B[k][1] == i && B[k][2] == j){
				cout<<B[k][0]<<" ";
				k++;
			}
			else{
				cout<<0;
			}
		}
		cout<<endl;
	}
}

void print(float B[][3]){
	//i,j全部遍历。B中找到输出，找不到输出0

	int i,j;
	int k = 1;//从1开始

	for(i = 0;i < B[0][1];i++){
		for(j = 0; j < B[0][2];j++){
			if((int)B[k][1] == i && (int)B[k][2] == j){//这里忘了将float类型强制转换了，jj
				cout<<B[k][0]<<" ";
				k++;
			}
			else{
				cout<<0;
			}
		}
		cout<<endl;
	}
}

// 5-5 p120
十字链表

普通节点结构定义：
typedef struct OLNode
{
	int row,col;
	struct OLNode *right,*down;
	float val;//这里是float型
}OLNode;

头结点结构定义：
typedef struct 
{
	OLNode *rhead,*chead;
	int m,n,k;
}CrossList;
int createCrossListmat(float A[][maxSize],int m,int n , int k ,CrossList &M){
	if(M.rhead){
		free(M.rhead);
	}

	if(M.chead){
		free(M.chead);
	}

	M.m = m;
	M.n = n;
	M.k = k;

	// 申请头结点数组空间
	if(M.rhead = (OLNode *)malloc(sizeof(OLNode)*m)) return 0 ;

	if(M.chead = (OLNode *)malloc(sizeof(OLNode)*n)) return 0 ;

	// OLNode r[m];
	// OLNode c[n];

	// M.rhead = r;
	// M.chead = c;

	// 头结点数组right down 指针置空
	for(int i = 0; i < m;i++){
		M.chead[i].right = NULL;
		M.chead[i].down = NULL;
	}

	for(int i = 0; i < n;i++){
		M.rhead[i].right = NULL;
		M.rhead[i].down = NULL;
	}

	OLNode *temp_r[maxSize];//建立列链表的赋值指针数组
	for(int j = 0 ; j < m;++j){
		temp_r[j] = &(M.chead[j]);
	}

	for(int i = 0;i < m;++i){
		OLNode *c = &(M.rhead[i]);
		for(int j = 0 ; i < n;j++){
			if(A[i][j]!=0){
				OLNode *p = (OLNode *)malloc(sizeof(OLNode));
				p->row = i;
				p->col = j;
				p->val = A[i][j];

				p->down = NULL;
				p->right = NULL;

				c->right = p;
				c= p;

				temp_r[j]->down = p;
				temp_r[j]=p;

			}
		}
	}
	return 1;
}

总结：
1.涉及链表的操作中，malloc创建节点，初始化节点，连接节点，这三步是永远不会少的
2.关于malloc生产数组，可以直接通过[]来使用，和我们平常的数组使用起来一模一样。
3.->  . 不要混了。操作对象是指针才用->,在这里我就没有想M是个啥，下意识的使用->。以后要专门注意一下函数的参数类型是不是指针
4.最重要的
	建立十字链表最核心内容：在遍历的时候，怎么样能让新malloc出来的节点之间正确的连接？
	这里的思路是：
		先提出问题，能总结出自己的问题也是水平
		这时不要想程序怎么写，依然还是在现实中寻找思路
		找到思路之后，然后再想怎样用程序实现

	这个思路和我以前总结的四层的关系？
		当我们在第三层写完注释，开始遍码的时候，就会觉得那里难住了，无法下手
		这时我们就需要上面的思路，走出编码，先去寻找思路
		也就是说，这个思路是我们遇到问题，解决问题的方法。
		而四层，是我们所有题的基本方法，这个思路是我们在进行四层时遇到问题的解决方案


#include<iostream>
using namespace std;


#define maxSize 20

typedef struct OLNode
{
    int row,col;
    struct OLNode *right,*down;
    float val;//这里是float型
}OLNode;

typedef struct
{
    OLNode *rhead,*chead;
    int m,n,k;
}CrossList;

int createCrossListmat(float A[][4] ,int m ,int n ,int k ,CrossList &M){
    if(M.rhead){
        free(M.rhead);
    }
    
    if(M.chead){
        free(M.chead);
    }
    
    M.m = m;
    M.n = n;
    M.k = k;
    
    // 申请头结点数组空间
   if(!(M.rhead = (OLNode *)malloc(sizeof(OLNode)*m))) return 0 ;

   if(!(M.chead = (OLNode *)malloc(sizeof(OLNode)*n))) return 0 ;
    
     // OLNode r[m];
     // OLNode c[n];

     // M.rhead = r;
     // M.chead = c;
    
    // 头结点数组right down 指针置空
    for(int i = 0; i < m;i++){
        M.chead[i].right = NULL;
        M.chead[i].down = NULL;
    }
    
    for(int i = 0; i < n;i++){
        M.rhead[i].right = NULL;
        M.rhead[i].down = NULL;
    }
    
    
    OLNode *temp_r[maxSize];//建立列链表的赋值指针数组
    for(int j = 0 ; j < m;++j){
        temp_r[j] = &(M.chead[j]);
    }
    
    for(int i = 0;i < m;++i){
        OLNode *c = &(M.rhead[i]);
        for(int j = 0 ; j < n;j++){
            if(A[i][j]!=0){
                OLNode *p = (OLNode *)malloc(sizeof(OLNode));
                p->row = i;
                p->col = j;
                p->val = A[i][j];
                
                p->down = NULL;
                p->right = NULL;
                
                c->right = p;
                c= p;
                
                temp_r[j]->down = p;
                temp_r[j]=p;
                
            }
        }
    }
    
    cout<<M.chead[2].down->val<<endl;
    cout<<M.chead[3].down->down->val<<endl;
    cout<<M.rhead[1].right->val<<endl;
    
    return 1;
}
int p(){
    return 1;
}
int main(){
    float A[4][4];
    for(int i = 0;i < 4;i++){
        for(int j = 0; j < 4; j++){
            A[i][j] = 0;
        }
    }
    
    A[0][3] = 1;
    A[1][2] = 3;
    A[1][3] = 2;
    A[2][0] = 1;
    A[3][1] = 2;
    
    CrossList M;
    M.rhead = NULL;
    M.chead = NULL;//这里要初始化为空，否则在free的报错
    
    createCrossListmat(A,4,4,5,M);
    
    cout<<M.chead[2].down->val<<endl;
    cout<<M.chead[3].down->down->val<<endl;
    cout<<M.rhead[1].right->val<<endl;
    
    return 0;
}

总结：
这道题中涉及到了结构体指针（结构体内部定义），动态分配数组（malloc），链表添加，二维数组做参数（float A[][4]），结构体的实体做参数（CrossList &M），复杂的结构体、指针操作（输出的时候）
所以说这道题对于巩固基础知识是很有帮助的
malloc 和数组 的区别：数组是在栈中，当运行完一个函数之后，那么在这个函数中生命的数组就被释放（这里我也不太确定），但是事实是，当我们在将题中的malloc换成数组之后，如果在createCrossListmat函数内部输出的话，malloc和数组是一样的，当时当我将输出放在mian之后，就会报错，此时createCrossListmat内部的输出语句依然正常。
结论：在函数中声明一个数组，我们用malloc就行了

判断我们函数的参数是时候实体还是指针？例如这里的CrossList &M
根据我们在函数中怎么用来决定，我们这里的M.***,所以我们传实体本身就行。


// 综合应用题
（1）p122
第一层：比较简单，重点让一个指针p一直指向左边第一个空位置就行

#include<iostream>
using namespace std;

#define maxSize 20

void moveElemet(int A[],int n){
    int i;
    int p = 0;
    
    //什么时候p该加呢？这时想我的“一个方法”。当值向前移动，那么移动到这个值的后面，或者i和p相等的
    for(i = 0; i < n;i++){
        if(A[i] != 0){
            A[p++] = A[i];//一个数组当成两个用
        }
    }
}


int main(){
    int A[10] = {1,2,0,3,0,4,5,6,7};
    
    moveElemet(A, 10);
    
    for(int i =0 ; i < 10;i++){
        cout<<A[i]<<endl;//多输出的了
    }
    return 0;
}

// （2）p122

这里最简单的dp

int findMax(float A[],int n){
	if(n == 0){
		return 0;
	}
	else{
		result = findMax(A[],n-1);
		if(A[n-1]>result) return A[n];
		else return A[n];
	}
}

int sum(float A[],int n){
	if(n == 0){
		return 0;
	}
	else{
		return A[n-1] + sum(A,n-1);
	}
}

递归：
新的解决问题的范式：新的分解问题的方式，他的可行性验证就是最内部的是否可以简单求解

int average(float A[],int n){//返回值要使用float类型
	if(n == 0){
		return 0;
	}
	else{
		return (A[n-1] + (n-1)average(A,n-1))/n;
	}
}


float average(float A[],int n){
    if(n == 0){
        return 0;
    }
    else{
        return (A[n-1] + (n-1)*average(A,n-1))/n;
    }
}

总结：
求平均值要求函数返回float类型


// （3）p123
i：从左向右  指向第一个偶数
j: 从右向左  指向第一个奇数

循环终止：i < j

void divide(int A[],int n){
	int i  = 0;
	int j  = n-1;
	int temp ;

	while(i < j ){
		//找到下一个i
		for(int k = i ; k < n;k++){
			if(A[k]%2 == 0){
				i = k;
				break;
			}
		}
		//找到下一个j
		for(int k = j ; k >=0;k--){
			if(A[k]%2 == 1){
				j = k;
				break;
			}
		}
		//验证通过，交换值，重新初始化
		if(i<j){//这回终于记住在while中要多次判断了
			temp = A[i];
			A[i] = A[j];
			A[j] = temp;

			j--;//又忘了在修改之后，重新修改指针
			i++;
		}
	}
}

注意：这道题虽然是两层循环，但是实际上仅对数组进行了一次遍历，此时时间复杂度为o(n)

// （4）p123

i：从左向右 指向第一个大于num的数
j: 从右向左 指向第一个小于num的数
i < j 

void divide(int A[],int n){
	int i  = 0;
	int j  = n-1;
	int temp;
	int num = A[n-1];

	while(i != j ){
		//找到下一个i
		for(int k = i ; k < n;k++){
			if(A[k] > num){
				i = k;
				break;
			}
		}
		//找到下一个j
		for(int k = j ; k >=0;k--){
			if(A[k] < num){
				j = k;
				break;
			}
		}
		//验证通过，交换值，重新初始化
		if(i<j){//这回终于记住在while中要多次判断了
			temp = A[i];
			A[i] = A[j];
			A[j] = temp;

			j--;//又忘了在修改之后，重新修改指针
			i++;
		}
	}
}
我这里的问题是：我不会处理A[n-1]如何放在正确的位置上
总结：
解决不了这个问题的按照我的“一个方法”，其实是我的算法有问题，不是简简单单的打点补丁就可以了。也就是说，需要我返回最开始的第一层去完全重新开始
明白，有些问题就是需要我们从头开始，不要怕浪费时间，大家都是这样

void divide(int A[],int n){
    int temp ;
    int i = 0 ,j = n-1;
    temp = A[i];
    A[i] = A[j];
    A[j] = temp;
    
    temp = A[i];
    
    while(i < j){
        //找到右边第一个不满足大于temp的，即小于temp的
        while(j > i && A[j] > temp) --j;
        //将这个最大的值给了i位置
        if(i < j){
            A[i] = A[j];
            ++i;
        }
        //找左边第一个不满足小于temp的，即大于temp的
        while(i < j && A[i] < temp)++i;
        //将这个最小的给了j所指向位置
        if(i < j){
            A[j] = A[i];
            --j;
        }
    }
    A[i] = temp;
}

书上的这个算法使用了快排的思想
快排其实代表着一种解决问题的方式
这种解决问题的思维方式才是快排最重要的地方。----------------------------等到了排序那章在总结


// （5）p123
先找见一行中最小的，和最大的；然后再去那这个值去列中对比，如果还是最大、最小，那么则输出


#include<iostream>
using namespace std;


#define maxSize 20
void printMin(int A[][5],int m,int n){
    int i,j;
    int min;
    
    for(i = 0; i < m;i++){
        //假设为每行第一个，然后测试交换
        min = A[i][0];
        //标志一下最小所在的列,初始化为0，第一个元素
        int k[2]={i,0};//在i行，0列
        //先着找见一行中最小的
        for(j = 0 ; j < n ; j++){
            if(min > A[i][j]){
                min = A[i][j];
                k[0] = i;
                k[1] = j;
            }
        }
        
        int tag = 1;
        
        //去min所在的列进行全部的比较
        for(j = 0 ; j < m; j++){//j表示的是行
            //若过有一个大于min，那么tag= 0 break；
            if(A[j][k[1]] < min){
                tag = 0;
                break;
            }
        }
        
        if(tag == 1){
            cout<<min<<endl;
            cout<<"i = "<<k[0]<<"j = "<<k[1]<<endl;
        }
    }
}

int main(){
    int A[4][5] ={
        {6,2,3,4,5},
        {1,2,3,4,5},
        {11,2,3,4,5},
        {13,2,3,4,5}
    };
    printMin(A,4,5);
    
    return 0;
}

// （7）p123
void revert(int A[][3],int B[][3]){

	B[0][0] = A[0][0];
	B[0][1] = A[0][2];
	B[0][2] = A[0][1];

	//遍历，按列号为一组的找
	int i ,j;
	int k = 0;
	for(i = 0;i < A[0][2];i++){
		for(j = 1;j <= A[0][0];j++){
			if(A[j][2] == i){
				B[k][0] = A[j][0];
				B[k][1] = A[j][2];
				B[k][2] = A[j][1];

				//又忘了k++了
				k++;
			}
		}
	}
}
总结：
这道题的算法我不知道，直接看的书，书中说出了具体的步骤，自然很好实现
看完之后实现，发现很简单：挑出来元素，然后放在另一个地方
还是比较简单的


// （8）p123
思路的整理：
如何处理一边为0，一边不为0的情况？顺序表的添加麻烦，还得按顺序
先按行，再按列排序。
怎样保证两边的同步？
就和前面一维数组的题一样，我两边都拿上一个，我比较一下，取上的那一边下标移动到下一个，方便下一次操作

和两个一维数组合并思想是一样的

void add(int A[][3],int B[][3],int C[][3]){
	int i = 1;
	int j = 1;
	int k = 1;

	//遍历A B直到一个为空 
	while(i <= A[0][0] && j <= B[0][0]){
		//比较 行列是否相同
		if(A[i][1] == B[j][1] && A[i][2] == B[j][2]){
			//如果位置相同则直接相加
			
			int temp = A[i][0]+B[j][0];
			if(temp != 0){//temp有可能为0，不为0的才能添加到C中（这个细节我就忘了）
				C[k][0] = A[i][0]+B[j][0];
				C[k][1] = A[i][1];
				C[k][2] = A[i][2];	
				k++;
			}
			i++;
			j++;
			
		}
		//若果位置不同则加0
		else if(A[i][1] > B[j][1]){//谁小取谁
			C[k][0] = B[j][0];
			C[k][1] = B[j][1];
			C[k][2] = B[j][2];

			j++;
			k++;

		}
		else if(A[i][1] < B[j][1]){
			C[k][0] = A[i][0];
			C[k][1] = A[i][1];
			C[k][2] = A[i][2];

			i++;
			k++;
			
		}
		else if(A[i][1] == B[j][1] && A[i][2] > B[j][2]){//行相同时
			C[k][0] = B[j][0];
			C[k][1] = B[j][1];
			C[k][2] = B[j][2];

			j++;
			k++;
			
		}
		else if(A[i][1] == B[j][1] && A[i][2] < B[j][2]){//行相同时
			C[k][0] = A[i][0];
			C[k][1] = A[i][1];
			C[k][2] = A[i][2];

			i++;
			k++;
		}
	}

	//把剩下的一个添加到c

	if(i <= A[0][0]){
		while(i <= A[0][0])
			C[k][0] = A[i][0];
			C[k][1] = A[i][1];
			C[k][2] = A[i][2];

			k++;
			i++;
		}
	}

	if(j <= B[0][0]){
		while(j <= B[0][0])
			C[k][0] = B[j][0];
			C[k][1] = B[j][1];
			C[k][2] = B[j][2];

			k++;
			j++;
		}
	}

	C[0][0] = k-1;
	C[0][1] = A[0][1];
	C[0][2] = A[0][2];

}

总结：
我一开始读完题，错误的以为是要在本身数组上进行操作，那么必定涉及到顺序表位置的大量移动
我这就是自己给自己添加难度，有病
还有，我有一个特殊情况没有考虑进去，就是连个表数据相加可能为0


// （9）p123
思路整理：
这道题和上面三道题是同一类型：关于矩阵的运算+ * 转置
他们都是在原来基本的二维矩阵运算上，存储结构改变为三元组
当然，存储结构一遍，算法基本思想虽让相同，但是值找起来的方式去完全不同了
这也同样说明了存储结构的重要性

重点在于发现找到对应值位置的方式

二维数组的时候，我能直接拿
现在，我只能先找，找到了再拿 多了一步

遍历

总结：
什么样的题简单
稀疏矩阵：以后直接默认使用三元组就行，千万别闲得没事干找十字链表去做，