【中国大学MOOC】浙江大学——数据结构（PAT）（持续更新ing）

函数题 01-复杂度3 二分查找 (20 分)

本题要求实现二分查找算法。

函数接口定义：

Position BinarySearch( List L, ElementType X );

其中List结构定义如下：

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、Data; int end = L->Last; int start = 0; while(start Next=NULL; List P1=L1->Next; List P2=L2->Next; while(P1&&P2) { if( P1->DataData) { List newnode=(List)malloc(sizeof(struct Node)); newnode->Data=P1->Data; bupt->Next=newnode; P1=P1->Next; bupt=newnode; } else { List newnode=(List)malloc(sizeof(struct Node)); newnode->Data=P2->Data; bupt->Next=newnode; P2=P2->Next; bupt=newnode; } } bupt->Next= P2?P2:P1; L1->Next=NULL; L2->Next=NULL; return L; } 编程题 01-复杂度1 最大子列和问题 (20 分)

给定K个整数组成的序列{ N1, N2, …, NK }，“连续子列”被定义为{ Ni, Ni+1, …, Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。

本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：

• 数据1：与样例等价，测试基本正确性；
• 数据2：102个随机整数；
• 数据3：103个随机整数；
• 数据4：104个随机整数；
• 数据5：105个随机整数；

输入格式:

输入第1行给出正整数K (≤100000)；第2行给出K个整数，其间以空格分隔。

输出格式:

在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。

输入样例:

6
-2 11 -4 13 -5 -2

输出样例:

20

代码

#include
using namespace std;

int main()
{
    int n,x;
    cin>>n;
    int this_sum = 0 , max_num = 0;
    for(int i=0;i>x;
        this_sum += x;
        if(this_sum > max_num) max_num = this_sum;
        else if(this_sum a[i];
    for(int i=1;i0)
        {
            fushu=0;
            break;
        }
    }
    for(int i=1;iexp;
			pc->Next = temp;
			pc = temp;
			pa = pa->Next;			
		}
		
	}
	if(pa){
		while(pa){
			List temp = (List)malloc(sizeof(struct Node));
			temp->Next = NULL;
			temp->coe = pa->coe;
			temp->exp = pa->exp;
			pc->Next = temp;
			pc = temp;
			pa = pa->Next;	
		}
	}else{
		while(pb){
			List temp = (List)malloc(sizeof(struct Node));
			temp->Next = NULL;
			temp->coe = pb->coe;
			temp->exp = pb->exp;
			pc->Next = temp;
			pc = temp;
			pb = pb->Next;			
		}
	}
	pc->Next = NULL;
	return L;
}
List mul(List L1,List L2){
	List p1,p2,p3,L,Lm;
	L = (List)malloc(sizeof(struct Node));
	p1 = L1->Next;
	p2 = L2->Next;
	L->Next = NULL;
	if(p1&&p2){
		for(p1=L1->Next;p1;p1=p1->Next){
			Lm = (List)malloc(sizeof(struct Node));
			Lm->Next = NULL;
			p3 = Lm;
			for(p2=L2->Next;p2;p2=p2->Next){
				List p4=(List)malloc(sizeof(struct Node));
				p4->coe = p1->coe*p2->coe;
				p4->exp = p1->exp+p2->exp;
				p3->Next = p4;
				p3=p4;
			}
			p3->Next = NULL;
			L=add(L,Lm);
			free(Lm);
		}
	}
	return L;
}

02-线性结构3 Reversing Linked List (25 分)

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤105) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

Sample Output:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

代码：

#include
#include
#include    ///使用到reverse 翻转函数
using namespace std;
 
#define MAXSIZE 1000010   ///最大为五位数的地址
 
struct node    ///使用顺序表存储data和下一地址next
{
   int data;   
   int next;
}node[MAXSIZE];
 
int List[MAXSIZE];   ///存储可以连接上的顺序表
int main()
{
    int First, n, k;  
    cin>>First>>n>>k;   ///输入头地址 和 n，k；
    int Address,Data,Next;
    for(int i=0;i>Address>>Data>>Next;
        node[Address].data=Data;
        node[Address].next=Next;
    }
 
    int j=0;  ///j用来存储能够首尾相连的节点数
    int p=First;   ///p指示当前结点
    while(p!=-1)
    {
        List[j++]=p;
        p=node[p].next;
    }
    int i=0;
    while(i+k