Day06-链表、栈括号匹配、递归
颜妮儿
帮助1人
链表
这里提到链表，也不得不再说说受顺序表了。
两者在内存中的存储形式：
顺序表和链表在逻辑上都是顺序结构，但在内存中，顺序表是顺序存储的，而链表是离散存储的，链表通过保存下一个元素的地址来实现逻辑上的顺序，两种表的存储结构也决定了其操作特点：
- 顺序表支持顺序访问和随机访问，但不便于对表进行随机添加和删除操作，因为可能需要大量移动元素。顺序表的表长一开始就确定了，且确定后不能修改；
- 链表只能进行顺序访问，在对元素进行随机添加和删除时不必移动其他元素。链表的表长虽然可以改变，但由于每个元素都要保存下一个元素的地址，浪费了一定的内存。
package day06;
public class LinkedList {
class Node {
/**
* The data.
*/
int data;
/**
* The reference to the next node.
*/
Node next;
/**
* The constructor
*
* @param paraValue The data.
*/
public Node(int paraValue) {
data = paraValue;
next = null;
}// Of the constructor
}// Of class Node
/**
* The header node. The data is never used.
*/
Node headerNode;
/**
* Construct an empty linked list.
*/
public LinkedList() {
headerNode = new Node(0);
}// Of the first constructor
/**
* Overrides the method claimed in Object, the superclass of any class.
*/
public String toString() {
String resulString = "";
if (headerNode.next == null) {
return "empty";
} // Of if
Node tempNode = headerNode.next;
while (tempNode != null) {
resulString = tempNode.data ", ";
tempNode = tempNode.next;
} // Of while
return resulString;
}// Of toString
/**
* Reset to empty. Free the space through garbage collection.
*/
public void reset() {
headerNode.next = null;
}// Of reset
/**
* Locate the given value. If it appears in multiple positions, simply return
* the first one.
*
* @param paraValue The given value.
* @return The position. -1 for not found.
*/
public int locate(int paraValue) {
int temPoseition = -1;
Node temNode = headerNode.next;
int tempCurrentPosition = 0;
while (temNode != null) {
if (temNode.data == paraValue) {
temPoseition = tempCurrentPosition;
break;
} // Of if
temNode = temNode.next;
tempCurrentPosition ;
} // Of while
return temPoseition;
}// Of locate
/**
* Insert a value to a position. If the list is already full, do notion.
*
* @param paraPosition The given position.
* @param paraValue The given value.
* @return Success or not.
*/
public boolean insert(int paraPosition, int paraValue) {
Node tempNode = headerNode;
Node tempNewNode;
for (int i = 0; i < paraPosition; i ) {
if (tempNode.next == null) {
System.out.println("The position " paraPosition " is illegal.");
return false;
} // Of if
tempNode = tempNode.next;
} // Of for i
// Construct a new node.
tempNewNode = new Node(paraValue);
// Now link them.
tempNewNode.next = tempNode.next;
tempNode.next = tempNewNode;
return true;
}// Of insert
/**
* Delete a value at a position.
*
* @param paraPosition The given position.
* @return Success or not.
*/
public boolean delete(int paraPosition) {
if (headerNode.next == null) {
System.out.println("Cannot delete element form an empty list. ");
return false;
}
Node tempNode = headerNode;
for (int i = 0; i < paraPosition; i ) {
if (tempNode.next == null) {
System.out.println("The position " paraPosition " is illegal.");
return false;
} // Of if
tempNode = tempNode.next;
} // Of for i
tempNode.next = tempNode.next.next;
return true;
}// Of delete
/**
* The entrance of the program.
*
* @param args Not used now.
*/
public static void main(String args[]) {
LinkedList tempFirstList = new LinkedList();
System.out.println("Initiilaized, the list is: " tempFirstList.toString());
for (int i = 0; i < 5; i ) {
tempFirstList.insert(0, i);
} // Of for i
System.out.println("Inserted, the list is: " tempFirstList.toString());
tempFirstList.insert(6, 9);
tempFirstList.delete(4);
tempFirstList.delete(2);
System.out.println("Deleted,the list is: " tempFirstList.toString());
for (int i = 0; i < 5; i ) {
if (tempFirstList.delete(0)) {
System.out.println("Looped delete,the list is: " tempFirstList.toString());
} // Of if
} // Of for i
}// Of main
}// Of class LinkedList
运行结果：
栈
栈的特性：后进先出，只允许在一端进行操作。
栈顶：允许进行插入删除的一端；
栈底：固定的一端，不允许插入删除。
采用顺序存储的栈称为顺序栈；采用链式存储的栈称为链栈。
栈的基本操作：
package day06;
public class CharStack {
/**
* The depth.
*/
public static final int MAX_DEPTH = 10;
/**
* The actual depth.
*/
int depth;
/**
* The data.
*/
char[] data;
/**
* Construct an empty char stack.
*/
public CharStack() {
depth = 0;
data = new char[MAX_DEPTH];
}// Of the first constructor
/**
* Overrides the method claimed in Object, the superclass of any class.
*/
public String toString() {
String resultString = "";
for (int i = 0; i < depth; i ) {
resultString = data[i];
} // Of of i
return resultString;
}// Of toString
/**
* Push an element.
*
* @param paraChar The given char.
* @return Success or not.
*/
public boolean push(char paraChar) {
if (depth == MAX_DEPTH) {
System.out.println("Stack full.");
return false;
} // Of if
data[depth] = paraChar;
depth ;
return true;
}// Of push
/**
* Pop an element.
*
* @return The popped char.
*/
public char pop() {
if (depth == 0) {
System.out.println("Nothing to pop");
return '\0';
} // Of if
char resultChar = data[--depth];
return resultChar;
}// Of pop
/**
* The entrance of the program.
*
* @param args Not used now.
*/
public static void main(String args[]) {
CharStack tempStack = new CharStack();
for (char ch = 'a'; ch < 'm'; ch ) {
if (tempStack.push(ch))
System.out.println("The current stack is: " tempStack);
} // Of for ch
char temChar;
for (int i = 0; i < 12; i ) {
temChar = tempStack.pop();
if (temChar != '\0') {
System.out.println("Poped: " temChar);
System.out.println("The current stack is: " tempStack);
} // Of if
} // Of for i
}// Of main
}// Of class CharStack
总结：根据栈的后进先出的特性，我觉得用栈的链式存储方式更合适，采用头插法，可以很方便实现push和pop操作且不用担心“溢出”。
栈的应用——括号匹配
匹配场景：
- 当我们匹配到一个左括号时，不知道后面是否有与之对应的右括号，所以先把它存起来；
- 当我们匹配到一个右括号时，可以看是否存有左括号。如果有，则表明最近存储的左括号有与之匹配的右括号，可以把它释放掉了；如果没有，则表明括号不匹配。
- 如果已经匹配完所有符号，但并没有把保存的左括号全部释放掉，则表明左括号多了，括号不匹配。
- 如果有多种括号，同样是保存左括号，遇到右括号时，找到最近保存的左括号，查看左括号与右括号类型是否相同，相同则释放该左括号并继续匹配，否则括号不匹配。
所以，左括号的保存和释放刚好和栈的后进先出的特点一致。
以下代码基于上面的栈代码：
/**
* Is the bracket matching?
*
* @param paraString The given expression.
* @return Match or not.
*/
public static boolean bracketMatching(String paraString) {
// Step 1. Initialize the stack through pushing a '#' at the bottom.
CharStack tempStack = new CharStack();
tempStack.push('#');
char tempChar, tempPopedChar;
// Step 2. Process the string. For a string,length() is a method instead of a
// member variable.
for (int i = 0; i < paraString.length(); i ) {
tempChar = paraString.charAt(i);
switch (tempChar) {
case '(':
case '[':
case '{':
tempStack.push(tempChar);
break;
case ')':
tempPopedChar = tempStack.pop();
if (tempPopedChar != '(') {
return false;
} // Of if
break;
case ']':
tempPopedChar = tempStack.pop();
if (tempPopedChar != '[') {
return false;
} // Of if
break;
case '}':
tempPopedChar = tempStack.pop();
if (tempPopedChar != '{') {
return false;
} // Of if
break;
default:
break;
}// Of switch
} // Of for i
tempPopedChar = tempStack.pop();
if (tempPopedChar != '#') {
return false;
} // Of if
return true;
}// Of bracketMatching
public static void main(String args[]) {
CharStack tempStack = new CharStack();
for (char ch = 'a'; ch < 'm'; ch ) {
if (tempStack.push(ch))
System.out.println("The current stack is: " tempStack);
} // Of for ch
char tempChar;
for (int i = 0; i < 12; i ) {
tempChar = tempStack.pop();
if (tempChar != '\0') {
System.out.println("Poped: " tempChar);
System.out.println("The current stack is: " tempStack);
} // Of if
} // Of for i
boolean tempMatch;
String tempExpressionString = "[2 (1 - 3)]*4";
tempMatch = bracketMatching(tempExpressionString);
System.out.println("Is the expression " tempExpressionString " bracket matching? " tempMatch);
tempExpressionString = "( ) )";
tempMatch = bracketMatching(tempExpressionString);
System.out.println("Is the expression " tempExpressionString " bracket matching? " tempMatch);
tempExpressionString = "()()(())";
tempMatch = bracketMatching(tempExpressionString);
System.out.println("Is the expression " tempExpressionString " bracket matching? " tempMatch);
tempExpressionString = "({}[])";
tempMatch = bracketMatching(tempExpressionString);
System.out.println("Is the expression " tempExpressionString " bracket matching? " tempMatch);
tempExpressionString = ")(";
tempMatch = bracketMatching(tempExpressionString);
System.out.println("Is the expression " tempExpressionString " bracket matching? " tempMatch);
}// Of main
括号匹配运行结果：
递归
函数调用的过程：
通过上图我们可以发现，最后被调用的函数会最先执行结束，然后是回到调用者继续执行后面的代码。（后进先出）
函数调用时，系统会开辟一个栈存储，用于保存调用返回地址、实参、局部变量信息。
如上面的函数调用栈为：
递归的过程就是函数调用自身的过程，在使用递归时，首先要明确递归体，然后是要确定递归出口，避免无限递归。
package day06;
public class Recursion {
/**
* Sum to N. No loop,however a stack sued.
*
* @param paraN The given value.
* @return The sum.
*/
public static int sumToN(int paraN) {
if (paraN <= 0) {
return 0;
} // Of if.
return sumToN(paraN - 1) paraN;
}// Of sumToN
public static int fibonacci(int paraN) {
if (paraN <= 0) {
// Negative values are invalid. Index 0 corresponds to the first element 0.
return 0;
}
if (paraN == 1) {
return 1;
} // Of if
return fibonacci(paraN - 1) fibonacci(paraN - 2);
}// Of fibonacci
/**
* The entrance of the program.
*
* @param args Not used now
*/
public static void main(String args[]) {
int tempValue = 5;
System.out.println("0 sum to " tempValue " = " sumToN(tempValue));
tempValue = -1;
System.out.println("0 sum to " tempValue " = " sumToN(tempValue));
for (int i = 0; i < 10; i ) {
System.out.println("Fibonacci " i ": " fibonacci(i));
} // Of for i
}// Of main
}// Of class Recursion
运行结果：
总结：循环其实也能达到我们想要的效果，但使用递归能逐步缩小问题规模，给我们更清晰的思路。
这篇好文章是转载于：学新通技术网
- 版权申明： 本站部分内容来自互联网，仅供学习及演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，请提供相关证据及您的身份证明，我们将在收到邮件后48小时内删除。
- 本站站名： 学新通技术网
- 本文地址： /boutique/detail/tanhhackjf
系列文章
更多
同类精品
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储，并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13
