第二周 線性結(jié)構(gòu)
主要講的是與鏈表秀菱、Stack（棧，LIFO）棍鳖、Queue（隊(duì)列炮叶，LILO）相關(guān)的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)以及相應(yīng)的方法實(shí)現(xiàn)。
題1：一元多項(xiàng)式的乘法與加法運(yùn)算
設(shè)計(jì)函數(shù)分別求兩個(gè)一元多項(xiàng)式的乘積與和渡处。
輸入格式:
輸入分2行镜悉，每行分別先給出多項(xiàng)式非零項(xiàng)的個(gè)數(shù)，再以指數(shù)遞降方式輸入一個(gè)多項(xiàng)式非零項(xiàng)系數(shù)和指數(shù)（絕對值均為不超過1000的整數(shù)）医瘫。數(shù)字間以空格分隔侣肄。
輸出格式:
輸出分2行，分別以指數(shù)遞降方式輸出乘積多項(xiàng)式以及和多項(xiàng)式非零項(xiàng)的系數(shù)和指數(shù)醇份。數(shù)字間以空格分隔稼锅，但結(jié)尾不能有多余空格。零多項(xiàng)式應(yīng)輸出0 0僚纷。
輸入樣例:
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
輸出樣例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
解決思路：
首先矩距，多項(xiàng)式由鏈表構(gòu)成，每一個(gè)節(jié)點(diǎn)對應(yīng)一項(xiàng)怖竭，包含其指數(shù)以及系數(shù)锥债。
加法
- 加法比較簡單，利用兩個(gè)cursor分別對應(yīng)1個(gè)多項(xiàng)式痊臭，當(dāng)指數(shù)相等時(shí)哮肚，系數(shù)相加，cursor均移動(dòng)广匙；當(dāng)指數(shù)不等時(shí)允趟，按指數(shù)大的取，對應(yīng)的1個(gè)cursor移動(dòng)鸦致。依次循環(huán)潮剪，直到兩個(gè)cursor都到末尾涣楷。
乘法
- 首先確定項(xiàng)數(shù)較少的那一個(gè)多項(xiàng)式，拿它的每一項(xiàng)與另一個(gè)多項(xiàng)式相乘鲁纠，并加到預(yù)先設(shè)定的空的多項(xiàng)式中总棵，然后cursor往后移動(dòng)一項(xiàng)。依次循環(huán)直至cursor到末尾改含。
import java.util.Scanner;
public class PolynMerge {
private Node head;
private Node end;
private int n;
private static class Node
{
private int coef;
private int expn;
private Node next;
public Node()
{ }
public Node(int coef, int expn)
{
this.coef = coef;
this.expn = expn;
}
}
public PolynMerge()
{
head = null;
end = null;
n = 0;
}
public void add(int coef, int expn)
{
Node newNode = new Node(coef, expn);
if (end != null) {
end.next = newNode;
end = newNode;
}
else {
head = newNode;
end = newNode;
}
n++;
}
public PolynMerge polyAdd(Node node_p1, Node node_p2)
{
PolynMerge result = new PolynMerge();
while (node_p1 != null && node_p2 != null)
{
if (node_p1.expn == node_p2.expn) {
int sum = node_p1.coef + node_p2.coef;
if (sum != 0)
result.add(sum, node_p1.expn);
node_p1 = node_p1.next;
node_p2 = node_p2.next;
}
else if (node_p1.expn > node_p2.expn) {
if (node_p1.coef != 0)
result.add(node_p1.coef, node_p1.expn);
node_p1 = node_p1.next;
}
else {
if (node_p1.coef != 0)
result.add(node_p2.coef, node_p2.expn);
node_p2 = node_p2.next;
}
}
while (node_p1 != null) {
result.add(node_p1.coef,node_p1.expn);
node_p1 = node_p1.next;
}
while (node_p2 != null) {
result.add(node_p2.coef,node_p2.expn);
node_p2 = node_p2.next;
}
return result;
}
public PolynMerge polyMulti(Node p1, Node p2)
{
PolynMerge result = new PolynMerge();
Node p2_head = p2;
int coef, expn;
while (p1 != null)
{
PolynMerge p3 = new PolynMerge();
while (p2 != null)
{
coef = p1.coef * p2.coef;
expn = p1.expn + p2.expn;
if (coef != 0)
{
p3.add(coef,expn);
}
p2 = p2.next;
}
if (result.n != 0)
result = result.polyAdd(result.head, p3.head);
else
result = p3;
p2 = p2_head;
p1 = p1.next;
}
return result;
}
public String toString()
{
if (n == 0)
return "0 0";
else {
Node node = head;
StringBuilder s = new StringBuilder();
while(node != null)
{
s.append(node.coef + " " + node.expn + " ");
node = node.next;
}
s.deleteCharAt(s.length() - 1);
return s.toString();
}
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
while (in.hasNext())
{
PolynMerge p1 = new PolynMerge();
PolynMerge p2 = new PolynMerge();
int N = in.nextInt();
int i = 0;
while (i < N)
{
p1.add(in.nextInt(), in.nextInt());
i++;
}
N = in.nextInt();
i = 0;
while (i < N)
{
p2.add(in.nextInt(), in.nextInt());
i++;
}
System.out.println(p1.polyMulti(p1.head, p2.head));
System.out.println(p1.polyAdd(p1.head, p2.head));
}
}
}
題2：Reversing Linked List
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
解題思路：
- 先按照順序形成一個(gè)初始的鏈表（沒有按給定的地址連接）
- 依據(jù)給定的頭地址以及每個(gè)元素的自己的名義地址與下一節(jié)點(diǎn)的名義地址情龄，再次形成一個(gè)需要的鏈表。
- 根據(jù)給定的k捍壤，判斷當(dāng)前cursor后的節(jié)點(diǎn)數(shù)量是否足以進(jìn)行reverse骤视。若可以reverse，則把鏈表的連接順序反轉(zhuǎn)[改變節(jié)點(diǎn)中next的值]鹃觉，特別要注意首尾節(jié)點(diǎn)的指向【對于當(dāng)前cursor所在的首節(jié)點(diǎn)指向末尾節(jié)點(diǎn)指向的節(jié)點(diǎn)专酗，末尾節(jié)點(diǎn)應(yīng)該被指向cursor的節(jié)點(diǎn)指向】。之后cursor移動(dòng)到末尾之后盗扇，依次循環(huán)祷肯，直到cursor指向null。
- 最后根據(jù)reverse之后的鏈表順序疗隶，修改節(jié)點(diǎn)中下一節(jié)點(diǎn)的名義地址佑笋。
import java.util.Scanner;
import java.util.regex.Pattern;
public class ReverseLinkV2 {
private Node head;
private Node end;
private int n;
private static class Node {
private String address;
private int num;
private String nextAddress;
private Node next;
public Node()
{ }
public Node(String address, int num, String nextAddress) {
this.address = address;
this.num = num;
this.nextAddress = nextAddress;
this.next = null;
}
}
public void add(String address, int num, String nextAddress) {
Node newNode = new Node(address, num, nextAddress);
if (head != null) {
end.next = newNode;
end = newNode;
}
else {
head = newNode;
end = newNode;
}
n++;
}
public void add(Node newNode) {
add(newNode.address, newNode.num, newNode.nextAddress);
}
public void delete(int num) {
Node node = head;
Node prev = null;
while (node != null && node.num != num) {
prev = node;
node = node.next;
}
if (node == null)
return;
else if (prev == null) {
head = node.next;
n--;
}
else {
prev.next = node.next;
n--;
}
}
public Node search(Node node, String address) {
while (node != null && !node.address.equals(address) ) {
node = node.next;
}
if (node != null)
return node;
else
return null;
}
public ReverseLinkV2 shift(String headAddress) {
ReverseLinkV2 trueList = new ReverseLinkV2();
trueList.add(search(head, headAddress));
delete(trueList.head.num);
Node newNode;
while (!trueList.end.nextAddress.equals("-1")) {
newNode = search(head, trueList.end.nextAddress);
trueList.add(newNode);
delete(trueList.end.num);
}
return trueList;
}
public void reverse(int k) {
Node end = hasSeqn(null, k);
Node current = head;
if (end != null) {
Node prev = reverse(end, k);
for (int i = 0; i < k ; i++) {
Node next = current.next;
current.next = prev;
prev = current;
current = next;
}
head = prev;
}
else
return;
}
public Node reverse(Node beforeHead, int k) {
Node end = hasSeqn(beforeHead, k);
Node head = beforeHead.next;
if (end != null) {
Node prev = reverse(end, k);
for (int i = 0; i < k; i++) {
Node next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
else {
return beforeHead.next;
}
}
public Node hasSeqn(Node head, int k) {
int i = 0;
if (head == null) {
head = this.head;
i = 1;
}
while (head != null && i < k) {
head = head.next;
i++;
}
return head;
}
public void correct() {
Node current = head;
while (current != null) {
if (current.next != null)
current.nextAddress = current.next.address;
else
current.nextAddress = "-1";
current = current.next;
}
}
public String toString() {
StringBuilder s = new StringBuilder();
if (n != 0) {
Node node = head;
while (node != null) {
s.append(node.address + " " + node.num + " " + node.nextAddress + "\n");
node = node.next;
}
s.deleteCharAt(s.length() - 1);
return s.toString();
}
else
return "Nothing in the list.";
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String address, nextAddress, headAddress;
int num, nNode, k;
while (in.hasNext()) {
ReverseLinkV2 originList = new ReverseLinkV2();
headAddress = in.next(Pattern.compile("[0-9]{5}"));
nNode = in.nextInt();
k = in.nextInt();
for (int i = 0; i < nNode; i++) {
address = in.next(Pattern.compile("[0-9]{5}"));
num = in.nextInt();
nextAddress = in.next(Pattern.compile("[0-9]{5}|-1"));
originList.add(address, num, nextAddress);
}
ReverseLinkV2 trueList = originList.shift(headAddress);
trueList.reverse(k);
trueList.correct();
System.out.println(trueList);
}
}
}
題3：Pop Sequence
Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.
Input Specification:
Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.
Output Specification:
For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.
Sample Input:
5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2
Sample Output:
YES
NO
NO
YES
NO
解題思路：
- 當(dāng)一個(gè)數(shù)被Pop出來，則必須要滿足兩個(gè)條件：1）小于它的數(shù)必須全部被已經(jīng)push進(jìn)去斑鼻；2）pop前蒋纬，stack的數(shù)量不能超過M。
- 設(shè)定哨兵位坚弱，a[0] = 0蜀备。然后從index=1開始讀取每一位數(shù)據(jù)，當(dāng)比前一位小時(shí)荒叶，說明這個(gè)數(shù)和前一個(gè)pop出來的數(shù)之間并沒有push新的數(shù)碾阁；當(dāng)比前一位大時(shí)，說明和前一個(gè)被pop出來的數(shù)之間有push些楣，通過差值判斷中間Push了幾個(gè)數(shù)瓷蛙，并判斷pop前是否超過M。
import java.util.Scanner;
public class StackPopSeq {
public static boolean isProb(int[] a, int M) {
int N = a.length;
int stNum = 0;
int maxNum = 0;
for (int i = 1; i < N; i++) {
if (a[i] < a[i-1])
stNum--;
else if (a[i] > maxNum) {
stNum = stNum + (a[i] - maxNum);
if (stNum > M)
return false;
maxNum = a[i];
stNum--;
}
else
return false;
}
return true;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int M, N, K;
while (in.hasNext()) {
M = in.nextInt();
N = in.nextInt();
K = in.nextInt();
int[] testNums = new int[N+1];
testNums[0] = 0;
for (int i = 0; i < K; i++) {
int j = 1;
while (j < N+1)
testNums[j++] = in.nextInt();
if (isProb(testNums, M))
System.out.println("YES");
else
System.out.println("NO");
}
}
}
}
