python/C++课程/待整理知识/啊哈算法/p55.cpp

/*
修正书中的错误:
https://blog.csdn.net/weixin_40804043/article/details/86501166

核心思路：查找是否存在一个节点的下一个节点的数据大于待插入的节点，即data[right[t]]>data[len]
如果找到了，就修改right指针域。最后根据right指针域打印其数据域的值
*/
#include <stdio.h>
int data[101];
int right[101];//每个节点都有一个指针域，所以这里的数组长度要和data数组一样长
int main() {
	/*n为用户首次录入的节点总数，用于控制初始化节点时的循环次数
	len为当前节点总数，为方便操作，data[0]和right[0]不放内容，从下标1开始遍历，因此data[len]就是最后一个元素
	*/
	
	int n,i,len,t;
	int flag = 1;
	scanf("%d",&n);
	//初始化数组data
	for(i = 1; i<=n; i++) {
		scanf("%d",&data[i]);
	}
	len = n;
	//初始化数组right
	for(i = 0; i<=n; i++) {
		if(i!=n) {
			right[i] = i+1;
		} else {
			right[i] = 0;
			//用0表示没有下一个元素
		}
	}
	//在data的末尾添加一个数
	len++;
	scanf("%d",&data[len]);
	/*
	通过遍历指针域，当找到某个节点的数据值大于插入的节点data[len]时，调整指针域的指向。
	直到指针域遍历完成为止
	*/
	t = 1; //对插入节点小于第一个节点的情况做特殊处理。（这里放在if..else里是出于无需再走循环的目的）
	if(data[len]<data[1]) {
		right[0] = len;
		right[len] = 1;
	} else {
		while(t!=0) {
			if(data[right[t]]>data[len]) {
				flag = 0;
				right[len] = right[t];
				right[t] = len;
				break;
			}
			t = right[t];
		}
		//插入节点大于最后一个节点的情况
		if(flag == 1) {
			right[len] = 0; /*这里只做简单处理，也可以查找right[t]==0的节点修改其指针域，
       		 只需在上面循环中加入if(right[t]==0){temp = t;}
       		 这里再改成right[temp] = len;
        	*/
			right[len-1] = len;
		}
	} //t为right[0]头节点指向的首节点的下标
	t = right[0];
	while(t!=0) {
		printf("%d ",data[t]);
		t = right[t];
	}
	//等待用户键盘录入，以起到暂停程序目的
	getchar();
	getchar();
	return 0;
}