資訊專欄INFORMATION COLUMN
摘要：性質相對于數組，長度可變插入刪除更容易。為了正確的反轉一個鏈表，需要調整鏈表中指針的方向指針反向。注意，在單鏈表中，將一個節點的指向后繼的指針指向它的前驅，將會導致鏈表的斷裂。
雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復制黨
以下是算法導論第十章的學習筆記
1 棧棧頂指針 top (初始值top = -1)指向棧頂元素，插入時先修改指針再插入，刪除時先取棧頂元素再修改指針.
1.1 性質后進先出
入棧，出棧都是O(1)
javapublic class Stack {
private int[] array = new int[5];
private int top = -1;
public Boolean stackempty(){
if(top == -1){
return true;
}
else
return false;
}
public void push(int x){
if(top<=array.length-1){
array[++top] = x;
}
else{
System.out.println("overflow");
}
}
java public int pop() {
int number = -1;
if(stackempty() != true){
number = array[top];
top--;
return number;
}
else
{
System.out.println("underflow");
return -1;
}
}
2 隊列
用array[n]數組實現的至多含有n-1個元素的隊列的方法.
隊列具有屬性head[Q],指向隊列的頭. 屬性tail[Q]指向新元素要被插入的地方
head[Q] = tail[Q]時，隊列空；
head[Q] = tail[Q]+1時，隊列滿；
初始head[Q] = tail[Q] = 1
先進先出
入隊，出隊都是O(1)
javapublic class Queue {
private int[] array = new int[4];
private int head = 1;
private int tail = 1;
//入隊
public void enqueue(int x){
//處理上溢
try{
if(head != tail +1){
array[tail++] = x;
if(tail == array.length){
tail = 0;
}
}
else{
System.out.println("overflow");
throw new Exception("queue overflow");
}
}catch(Exception e){
e.printStackTrace();
}
}
java //出隊
public int dequeue(){
int number=0;
try{
if(tail != head){
number = array[head];
head++;
}
else{
throw new Exception("queue underflow");
}
}catch(Exception e){
System.out.println("underflow");
e.printStackTrace();
}
return number;
}
3. (雙向)鏈表
鏈表是面試時被頻繁提及的DS。 每個對象包括一個關鍵字域和兩個指針域prev,next;
鏈表為什么這么受歡迎？
鏈表是一種動態的數據結構，其操作需要通過指針進行。鏈表內存的分配不是在創建鏈表時一次性完成，而是每添加一個節點就分配一次內存。由于沒有閑置內存。他的空間效率比數組更高。
通過使用哨兵nil節點（增加一個nil節點）可以簡化邊界條件。
3.1 性質相對于數組，長度可變；插入刪除更容易。
3.2核心代碼（單向鏈表）
javapublic class LinkedList {
private Node head;
private Stack s;
LinkedList(){
head = null;
s = new Stack();
}
private static class Node{
int item;
Node next;
Node(){
this.item = 0;
this.next = null;
}
Node(int item, Node next){
this.item = item;
this.next = next;
}
}
public void insert(int x){
Node node = new Node(x, null);
Node p = head;
// 注意鏈表為空的時候的插入
if(head==null){
head = node;
}
// 尾插法
else{
while(p.next != null){
p = p.next;
}
p.next = node;
}
}
public void travese(Node head){
Node p = head;
while(p!=null){
System.out.println(p.item);
p = p.next;
}
}
(雙向鏈表)
javapublic class DoubleLinkedList {
// 哨兵節點nil(作為表頭指針)
private Node nil;
// 初始化一個鏈表
DoubleLinkedList(){
nil = new Node();
nil.next = nil;
nil.prev = nil;
count = 0;
}
// 鏈表長度
private int count;
private static class Node{
int item;
Node next;
Node prev;
Node(){
item = 0;
next = null;
prev = null;
}
Node(int item, Node next, Node prev){
this.item = item;
this.next = next;
this.prev = prev;
}
}
//返回當前鏈表的長度
public int length(){
return count;
}
//獲取value為k的節點
public Node listsearch(int k){
Node result = null;
Node head = nil;
while(head.next != nil){
if(head.next.item == k){
result = head.next;
break;
}
else
head = head.next;
}
return result;
}
//插入一個節點在隊首
public void listinsert(Node node){
node.next = nil.next;
nil.next.prev = node;
nil.next = node;
node.prev = nil;
count++;
}
//根據value刪除一個節點
public Node listdelete(Node node){
Node head = nil;
Node nodetodelete;
while(head.next!=nil){
if(head.next.item == node.item){
nodetodelete = head.next; //將要刪除的節點
head.next = nodetodelete.next;
nodetodelete.next.prev = head;
nodetodelete = null;
count--;
}
else{
head = head.next;
}
}
return node;
}
//輸出鏈表
public void traverse(){
Node head = nil;
while( head.next!= nil){
System.out.println(head.next.item);
head = head.next;
}
}
3.3 擴展
1. 從尾到頭打印鏈表
題目：輸入一個鏈表的頭節點，從尾到頭打印出來每個節點的值。
解法：遍歷，每遍歷到的元素存到棧，然后輸出棧即可。
代碼：
java public void reveaseoutput(Node head){
Node p = head;
if(p==null){
System.out.println("empty list");
}
while(p != null){
s.push(p.item);
p = p.next;
}
while(s.stackempty()!= true){
int n = s.pop();
System.out.println(n);
}
}
2. O(1)時間刪除鏈表節點
題目：給定單鏈表的頭指針和一個節點指針，O(1)時間刪除該鏈表節點
解法：下一個節點的內容復制到需要刪除的點，即覆蓋。然后刪該店的下一個節點。
這里需要考慮兩個邊界條件，1 要刪除的點位于尾部 2 鏈表只有一個節點
要考慮魯棒性。
代碼：
javapublic void deleteNode(Node head, Node pToDeleted){
if(head!=null){
//要刪除的是尾節點
if(pToDeleted.next == null){
//如果要刪除的是鏈表唯一的節點
if(head.next==null){
head = null;
System.out.println(head);
pToDeleted = null;
}
else{
Node p = head;
while(p.next!=pToDeleted){
p = p.next;
}
p.next = null;
pToDeleted =null;
}
}
//要刪除的不是尾節點，且節點數大于1
else{
pToDeleted.item = pToDeleted.next.item;
pToDeleted.next = pToDeleted.next.next;
pToDeleted = null;
}
}else{
System.out.println("the linklist is empty");
}
}
3. 倒數第k個節點
題目：輸入一個鏈表，輸出該鏈表第倒k個節點。（鏈表從1開始計數）
解法：定義兩個指針，第一個指針從鏈表的head指針開始遍歷，向前走k-1步的時候，第二個指針開始和它一起走。當第一個指針的next指向null的時候，第二個指針指向了倒數第k個。（這種一次遍歷，對時間要求比較高的程序，就需要借助空間，再開辟一個指針）
要考慮魯棒性。
代碼：
java //遍歷鏈表一次，刪除倒數第K個元素
public Node FindKthToTail(Node head, int k){
Node p=head;
Node q = head;
int i;
if(head==null || k==0){
return null;
}
for(i=0;i
4. 反轉鏈表
題目：定義一個函數，輸入鏈表頭節點，反轉該鏈表并輸出反轉后鏈表的頭節點。
解法：借助三個指針，prev, p, next. 避免指針斷裂。
（ 為了正確的反轉一個鏈表，需要調整鏈表中指針的方向【指針反向】。注意，在單鏈表中，將一個節點的指向后繼的指針指向它的前驅，將會導致鏈表的斷裂。導致無法在單鏈表中遍歷它的后繼節點，因此，在調整某一節點的 next 指針時，需要首先將其的后繼節點保存下來。）
代碼：
java
public Node reverse(){
Node p = head;
try{
if(p!=null){
Node pnext = p.next;
p.next = null;
while(pnext!= null){
Node r = pnext.next;
pnext.next = p;
p = pnext;
pnext = r;
}
}else{
throw new Exception("empty list");
}
}catch(Exception e){
e.printStackTrace();
}finally{
return p;
}
}
5 合并鏈表
題目：輸入兩個增序的鏈表，合并這兩個鏈表并使新鏈表仍然增序。
解法：重點強調魯棒性：兩個鏈表一個或者兩個都是null,兩個鏈表只有一個節點。
代碼：
java public Node merge(Node head1, Node head2){
if(head1 == null) {
return head2;
}
if(head2 == null){
return head1;
}
else{
Node newhead;
Node r;
Node p = head1;
Node q = head2;
java if(head1.item <= head2.item){
newhead = head1;
p = p.next;
}
else{
newhead = head2;
q = q.next;
}
r = newhead;
while(p!=null && q!=null){
if(p.item <= q.item){
r.next = p;
p = p.next;
r = r.next;
}
else{
r.next = q;
q = q.next;
r = r.next;
}
}
if(p!=null){
r.next = p;
}
if(q!=null){
r.next = q;
}
return newhead;
}
}
6 復雜鏈表的復制
題目：
解法：
代碼：
java //1. 根據原始鏈表的每個節點創建對應的copy節點
public void CloneNode(ComplexNode head){
ComplexNode p = head;
while(p!=null){
ComplexNode node = new ComplexNode(p.item,null,null);
node.next = p.next;
p.next = node;
p = node.next;
}
}
java //2. 設置復制出來的節點的sibling
public void connectsiblingnodes(ComplexNode head){
ComplexNode p = head;
while(p!=null){
ComplexNode q = p.next;
if(p.sibling!=null)
{
q.sibling = p.sibling.next;
}
p = q.next;
}
}
java //3. 拆分鏈表
public ComplexNode ReconnectNodes(ComplexNode head){
ComplexNode p = head;
if(p!=null){
ComplexNode newhead = p.next;
ComplexNode q = newhead;
while(q.next!=null){
p.next = q.next;
p = q.next;
q.next = p.next;
q = p.next;
}
return newhead;
}
else{
return null;
}
}
7 尋找第一個公共節點
題目：輸入兩個鏈表，找出第一個公共節點。
解法：Y形
代碼：
java public Node findfirstcommonnode(Node head1, Node head2){
Node p = head1;Node q = head2;
int length = int length1 = int length2= 0;
while(p!=null){
length1 = length1 + 1;
p = p.next;
}
while(q!=null){
length2 = length2 + 1;
q = q.next;
}
p = head1;q = head2;
if(length1>length2){
length = length1 - length2;
while(length>0){
p = p.next; length--;
}
}
if(length10){
q = q.next; length--;
}
}
while(p!=null&&q!=null&&p.item != q.item){
p = p.next; q = q.next;
}
return p;
}
想更一進步的支持我，請掃描下方的二維碼，你懂的~
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64294.html
摘要：在改進前使用數組的一個缺點是必須聲明數組的大小，所以棧有確定的容量。待解決的問題建立一個能夠增長或者縮短到任意大小的棧。下邊的圖是觀察時間開銷的另一種方式，表示了入棧操作需要訪問數組的次數。 前言 上一篇：算法分析下一篇：基本排序 本篇內容主要是棧，隊列 (和包)的基本數據類型和數據結構文章里頭所有的對數函數都是以 2 為底關于性能分析，可能還是需要一些數學知識，有時間可以回一下在很多...
摘要：一前言上一篇已經講過了鏈表實現單向鏈表了，它跟數組都是線性結構的基礎，本文主要講解線性結構的應用棧和隊列如果寫錯的地方希望大家能夠多多體諒并指正哦，如果有更好的理解的方式也希望能夠在評論下留言，讓大家學習學習二數據結構棧就是這么簡單數據結構 一、前言 上一篇已經講過了鏈表【Java實現單向鏈表】了，它跟數組都是線性結構的基礎，本文主要講解線性結構的應用：棧和隊列 如果寫錯的地方希望大家...
摘要：棧隊列雙端隊列都是非常經典的數據結構。結合了棧和隊列的特點。因此，在中，有棧的使用需求時，使用代替。迭代器之前源碼源碼之與字段中分析過，容器的實現中，所有修改過容器結構的操作都需要修改字段。 棧、隊列、雙端隊列都是非常經典的數據結構。和鏈表、數組不同，這三種數據結構的抽象層次更高。它只描述了數據結構有哪些行為，而并不關心數據結構內部用何種思路、方式去組織。本篇博文重點關注這三種數據結構...
摘要：會死循環，因為棧內不會彈出所以判斷會一直執行。集合用于模擬隊列這種數據結構，隊列通常是指先進先出的容器。集合不僅提供了的功能，還提供了雙端隊列，棧的功能。如果有多個線程需要訪問集合中的元素，需要考慮使用將幾個包裝成線程安全集合。 List判斷兩個對象相等只通過equals方法比較返回true即可。 public class A { @Override public ...
閱讀 2312·2021-09-26 10:21
閱讀 2785·2021-09-08 09:36
閱讀 3065·2019-08-30 15:56
閱讀 954·2019-08-30 12:57
閱讀 916·2019-08-26 10:39
閱讀 3555·2019-08-23 18:11
閱讀 3078·2019-08-23 17:12
閱讀 1070·2019-08-23 12:18
