データ構造の理解
205764 ワード
転載先:http://blog.csdn.net/andrexpert/article/details/77900395
Android Javaデータ構造Android基礎技術核心帰納(一)Java基礎技術核心帰納(一)データ構造基礎知識核心帰納(一)Android基礎技術核心帰納(二)Java基礎技術核心帰納(二)データ構造基礎知識核心帰納(二)Android基礎技術核心帰納(三)Java基礎技術核心帰納(三)データ構造基礎知識核心帰納(三)Android基礎技術核心帰納(四)
いつの間にかまた1年の9月で、今日1人の師弟とチャットして、彼の今の面接のいくつかの情況について話して、突然自分がその年もこのように歩いてきたことを思い出して、急に感慨深いです.Android/Java経験まとめシリーズ記事は、当初自分が卒業したときの筆記試験や面接、プロジェクト開発に関するまとめであり、あまり深くないものであり、きちんとまとめられていないものの、Android、アルゴリズム、Javaについては大まかに把握しておくのは問題ないと思いますが、今日はわざわざこれらの記事を出して、このシリーズを見た卒業生の皆さんに少しでも助けてほしいですね.もちろん、当时の知识の制限を受けているので、きちんとまとめられていないかもしれませんが、疑问があればコメントしてください.
1.スタック、キュー、スタックの違いを簡単に説明しますか?1.ヒープ:ヒープは木状のデータ構造です.一般的にプログラマによってリリースが割り当てられ、newによって作成するオブジェクトと配列(Cではmallocによってリリースされ、freeによってリリースされる)が格納され、JVMはこのオブジェクトを不定期に表示し、このオブジェクトを参照しなければ回収する.
(1)利点:メモリサイズを動的に割り当てることができ、生成サイクルは事前にコンパイラに教える必要がなく、Javaゴミ回収自動回収データ;(2)欠点:運転時にメモリを動的に割り当てる必要があるため、データ記憶速度が
より遅い.スタック:一端のみの挿入と削除を許可する線形テーブルです.すなわち、先進的な後出です.コンパイラによって自動的に割り当てられて解放され、関数のパラメータ値、ローカル変数の値などの基本タイプの変数とオブジェクトの参照が格納されます.(1)利点:メモリ速度比較ブロックは、レジスタに次いでスタックデータが共有可能である;(2)欠点:スタックに存在するデータサイズと生存期間は確定しなければならない(int y=4,yはスタックに4バイトを占める)、柔軟性に欠ける.≪キュー｜Queue｜oem_src≫:エンド・エンドでのみデータ要素の挿入を許可し、エンド・エンド・エンドでデータ要素を削除するリニア・テーブルです.つまり、FIFOを先に出力します.キューでは、データ要素は任意に増減できますが、データ要素の順序は変わりません.キューからデータ要素が取り出されるたびに、後ろのデータ要素は一度に1ビット前進します.参照先:http://www.sxt.cn/u/1349/blog/23302.配列とチェーンテーブルの違いを簡単に話しますか?(1)論理構造から見ると,配列は一定の長さ(要素個数)を定義し,データの動的増減に適応できない場合を実現しなければならない.データが増加すると、オーバーフローを引き起こす可能性があります.データが減少するとメモリが浪費され、配列にデータ項目が挿入、削除されると、他のデータ項目を移動する必要があります.チェーンテーブルは動的にストレージ割り当てを行い、データを動的に増減させることができ、メモリを節約でき、データデータ項目の挿入、削除を容易にすることができる.(2)メモリストレージから見ると、(静的)配列はスタックから空間を割り当て(注:newで作成されたスタックに割り当て)、ストレージ速度は速いが柔軟性に欠けている.チェーンテーブルはスタックから空間を割り当て、柔軟性は良いが、申請管理は面倒である.(3)アクセス方式から見ると,配列はメモリに連続的に格納されているため,下付きインデックスによるランダムアクセスが可能である.チェーンテーブルはチェーンストレージ構造であり,要素にアクセスする際には線形の方法で前後から順次アクセスするしかないため,アクセス効率は配列よりも低い.3.単一チェーンテーブルの作成、挿入、削除操作1.単一チェーンテーブル作成、挿入、削除(1)ノード構造体
Android Javaデータ構造Android基礎技術核心帰納(一)Java基礎技術核心帰納(一)データ構造基礎知識核心帰納(一)Android基礎技術核心帰納(二)Java基礎技術核心帰納(二)データ構造基礎知識核心帰納(二)Android基礎技術核心帰納(三)Java基礎技術核心帰納(三)データ構造基礎知識核心帰納(三)Android基礎技術核心帰納(四)
いつの間にかまた1年の9月で、今日1人の師弟とチャットして、彼の今の面接のいくつかの情況について話して、突然自分がその年もこのように歩いてきたことを思い出して、急に感慨深いです.Android/Java経験まとめシリーズ記事は、当初自分が卒業したときの筆記試験や面接、プロジェクト開発に関するまとめであり、あまり深くないものであり、きちんとまとめられていないものの、Android、アルゴリズム、Javaについては大まかに把握しておくのは問題ないと思いますが、今日はわざわざこれらの記事を出して、このシリーズを見た卒業生の皆さんに少しでも助けてほしいですね.もちろん、当时の知识の制限を受けているので、きちんとまとめられていないかもしれませんが、疑问があればコメントしてください.
1.スタック、キュー、スタックの違いを簡単に説明しますか?1.ヒープ:ヒープは木状のデータ構造です.一般的にプログラマによってリリースが割り当てられ、newによって作成するオブジェクトと配列(Cではmallocによってリリースされ、freeによってリリースされる)が格納され、JVMはこのオブジェクトを不定期に表示し、このオブジェクトを参照しなければ回収する.
(1)利点:メモリサイズを動的に割り当てることができ、生成サイクルは事前にコンパイラに教える必要がなく、Javaゴミ回収自動回収データ;(2)欠点:運転時にメモリを動的に割り当てる必要があるため、データ記憶速度が
より遅い.スタック:一端のみの挿入と削除を許可する線形テーブルです.すなわち、先進的な後出です.コンパイラによって自動的に割り当てられて解放され、関数のパラメータ値、ローカル変数の値などの基本タイプの変数とオブジェクトの参照が格納されます.(1)利点:メモリ速度比較ブロックは、レジスタに次いでスタックデータが共有可能である;(2)欠点:スタックに存在するデータサイズと生存期間は確定しなければならない(int y=4,yはスタックに4バイトを占める)、柔軟性に欠ける.≪キュー｜Queue｜oem_src≫:エンド・エンドでのみデータ要素の挿入を許可し、エンド・エンド・エンドでデータ要素を削除するリニア・テーブルです.つまり、FIFOを先に出力します.キューでは、データ要素は任意に増減できますが、データ要素の順序は変わりません.キューからデータ要素が取り出されるたびに、後ろのデータ要素は一度に1ビット前進します.参照先:http://www.sxt.cn/u/1349/blog/23302.配列とチェーンテーブルの違いを簡単に話しますか?(1)論理構造から見ると,配列は一定の長さ(要素個数)を定義し,データの動的増減に適応できない場合を実現しなければならない.データが増加すると、オーバーフローを引き起こす可能性があります.データが減少するとメモリが浪費され、配列にデータ項目が挿入、削除されると、他のデータ項目を移動する必要があります.チェーンテーブルは動的にストレージ割り当てを行い、データを動的に増減させることができ、メモリを節約でき、データデータ項目の挿入、削除を容易にすることができる.(2)メモリストレージから見ると、(静的)配列はスタックから空間を割り当て(注:newで作成されたスタックに割り当て)、ストレージ速度は速いが柔軟性に欠けている.チェーンテーブルはスタックから空間を割り当て、柔軟性は良いが、申請管理は面倒である.(3)アクセス方式から見ると,配列はメモリに連続的に格納されているため,下付きインデックスによるランダムアクセスが可能である.チェーンテーブルはチェーンストレージ構造であり,要素にアクセスする際には線形の方法で前後から順次アクセスするしかないため,アクセス効率は配列よりも低い.3.単一チェーンテーブルの作成、挿入、削除操作1.単一チェーンテーブル作成、挿入、削除(1)ノード構造体
-
/***struct Node *
-
struct Node ** */
-
typedef
struct
-
{
-
int data;
// ，
-
struct Node *next;
// ， next struct Node * ( )
-
}Node,*LinkList;
//Node ，*LinkList
(2)
： ， p， p。 ， j 1 ， j
-
/* ： i ，1<=i<=ListLenght(L)
-
e */
-
#define UNSUCCESS -1
-
#define SUCCESS 1
-
typedef Status
int;
-
Status GetElem(LinkList L,int i,int *e)
-
{
-
int j=
1;
-
LinkList p;
// p
-
p=L->next;
// p L
-
while(p&&j// ， j=i-1， p i-1
-
p=p->next;
// p ,
-
++j;
-
}
-
if(!p || j>i)
// p null j ，
-
return UNSUCCESS ;
-
*e=p->data;
// ， i e
-
return SUCCESS;
-
}
(3)
： ， ， i ； ， s s ； ， p s ， s 。
-
/* ： e i */
-
#define UNSUCCESS -1
-
#define SUCCESS 1
-
typedef Status
int;
-
Status ListInsert(LinkList *L,int i,ElemType e)
-
{
-
int j=
1;
-
LinkList p,s;
// p
-
p=*L;
// p L
-
while(p&&j// ， j=i-1， p i-1
-
p=p->next;
// p
-
++j;
-
}
-
if(!p || j>i)
// p null j ，
-
return UNSUCCESS ;
-
s=(LinkList)
malloc(
sizeof(Node));
// ，
-
s->data=e;
// ， e s
-
s->next =p->next;
// p s (p->next p )
-
p->next=s;
// p s
-
return SUCCESS ;
-
}
(4)
： ， q ， i ； ， i q； ， q ( p ) p ； ， i (q) e ，free(q) q 。
-
/*** ： L i ( )
-
e ***/
-
#define UNSUCCESS -1
-
#define SUCCESS 1
-
typedef Status
int;
-
Status ListInsert(LinkList *L,int i,ElemType *e)
-
{
-
int j=
1;
-
LinkList p,q;
// p
-
p=*L;
-
// ， j=i-1， p i-1
-
while(p->next&&j
-
{
-
p=p->next;
// p
-
j++;
-
}
-
if(!p || j>i)
-
return UNSUCCESS;
-
q=p->next;
// q p , i q
-
p->next=q->next;
// q p
-
*e=q->data;
// q e
-
free(q);
// ， ，
-
return SUCCESS;
-
}
：LinkList s ， ， 。
2.
： ， (*L)， NULL； ， p， ， (*L) ( NULL)； ， p 。
-
/***
-
n ， L( )***/
-
//
-
typedef
struct{
-
int data;
-
struct Node* next;
-
}Node;
-
//
-
Node* CreateList(int *a, int count)
-
{
-
if(
NULL == a)
-
return
NULL;
-
// ： ， 、
-
Node* head = (Node*)
malloc(
sizeof(Node));
-
head->data= a[
0];
-
head->next =
NULL;
-
-
-
// p
-
Node* p = head;
-
for (
int i =
1; i < count; ++i)
-
{
-
p->next = (Node*)
malloc(
sizeof(Node));
-
p->next->data= a[i];
-
p->next->next =
NULL;
-
p = p->next;
-
}
-
return head;
//
-
}
， main ， ：
int a[]={5,9,3,1,2,7,8,6,4};
Create_LinkList(a,sizeof(a)/sizeof(int)); // ， ，
3.
(1) ： ， ， O(1)， O(n)
(2) 、 ： ： i ；
★ ， ： O(n)。 i ， ， 。 i ， 10 ， ， n-i ， O(n)。 ， i ， O(n)， ， O(1)。
： ， 。
4.
◆
(1)
(2) ，
◆
(1) ： O(1); O(n)
(2) ： ， O(n); ， O(1)
◆
(1) ， ， ， ；
(2) ， ，
5.
(1) ： ， ( )。 ， ， 。
(2) ： ， 。 ， 。
4. ？
1.
， ， ， 。
(1)
A、B ， rearA、rearB。
a. A rearA (rearA->next)B ( );
b. B rearB (rearB->next)A ， 。
(2)
-
p=rearA->next;
// p， A
-
rearA->next=rearB->next->next;
-
// B ( ) rearA->next( A )
-
rearB->next=p;
// A rearB->next
-
free(p);
// p, p
： ， p->next 。 p->next ; p->next ， rear， rear->next 。
2.
， 。 ， ， ， 。 。
(1)
：
a) s， 、
s->prior=p;
s->next=p->next;
b) s p->next (p->next->prior)
p->next->prior = s;
c) s p (p->next)
p->next = s;（b.c ， p->next->prior = p）
(2)
：
-
p->prior->next=p->next;
// p->next p->prior
-
p->next->prior=p->prior;
// p->prior p->next
-
free(p);
// p
5. ( ) ( )？
1. –
(1) ： ，prev NULL，head A，next A B。 A ， A next prev， prev NULL， A ， head next ， B B C（ next B ， A next ）， A 。 ， ， B、C、D ， head Null 。
：
-
head->next = prev;
// A next prev
-
prev = head;
// prev A
-
head = next;
// head B
-
next = head->next;
// next( head->next) C
(2) ：
-
61
LINK_NODE *ReverseLink(LINK_NODE *head) // head
-
62 {
-
63 LINK_NODE *next;
-
64 LINK_NODE *prev =
NULL;
//
-
66
while(head !=
NULL)
//
-
67 {
-
68 next = head->next;
// next head->next
-
69 head->next = prev;
-
70 prev = head;
-
71 head = next;
-
72 }
-
74
return prev;
-
75 }
2..
， ， ， 。
(1) ： ，pA ，pB ， …… ， pB==NULL， （ NULL）， ； pB==pA( )， ， 。
(2)
-
int RingJudge(LINK_NODE *head){
-
LINK_NODE *p,*q;
-
/* h */
-
if((
NULL == head) || (
NULL == head->next))
/* ， ， */
-
{
-
return
0;
-
}
-
p = q = head;
/* p q ， */
-
while(
1)
-
{
-
p = p->next;
-
q = (q->next)->next；
-
if((
NULL == p) || (
NULL == q))
-
{
-
printf(“No Ringn”);
/* ， */
-
return
0;
-
}
-
if(p == q)
/* */
-
{
-
printf(“Ring occurred
”);
-
return
1;
-
}
-
}
-
}
：http://blog.csdn.net/autumn20080101/article/details/7607148
6. K ？
1.
(1) a k
(2) b ， a k ， a ， b k 。
2.
n，a k n-k ， b n-k ， b =n-(n-k)=k
-
LINK_NODE *GetKElem(LINK_NODE *head,int k,ElemType *e){
-
if(head == null){
//
-
return null;
-
}
-
LINK_NODE *first,*second;
// ，
-
first = second = head;
-
/*
-
*(1) k ， first k
-
*/
-
while(k !=
0){
-
if(first == null)
// k
-
return null;
-
first = first->next;
-
k--;
// first k
-
}
-
/*
-
*(2) first ， second ， first k
-
* first->next Null ， ， second K
-
*/
-
while(first != null){
-
first = first->next;
-
second = second->next;
-
}
-
if(second != null && second != head)
// K e
-
*e = second->data;
-
return second;
-
}
7. ？ [O(nlogn)]，
， ， ， ， 。
1. （ ）
(1) ： ， ， ， ， 。 ：
a. ， ；
b. ， ；
c. ， 。
：
(2)
-
LinkNode* SortLinkListInsertion(LinkNode* head)
-
{
-
// ， ，
-
if (
NULL == head ||
NULL == head->next){
-
return head;
-
}
-
// ，
-
LinkNode* r = head->next;
-
LinkNode* tmp;
-
head->next =
NULL;
//
-
while(
NULL != r) {
//
-
if (r->data < head->data) {
-
// ， ，
-
tmp = r->next;
-
r->next = head;
-
head = r;
-
r = tmp;
-
}
-
else{
-
// ，
-
LinkNode* p = head;
-
while(
NULL != p->next){
-
// ，
-
// ！
-
if (r->data < p->next->data) {
-
tmp = r->next;
-
r->next = p->next;
-
p->next = r;
-
r = tmp;
-
continue;
// ，
-
}
-
else {
-
p = p->next;
-
}
-
}
-
// ，p ，
-
if (
NULL == p->next){
-
tmp = r->next;
-
r->next =
NULL;
-
p->next = r;
-
r = tmp;
-
}
-
}
//end else
-
}
//end while(NULL != r)
-
return head;
-
}
2. （ ）
(1) ： ， ， 。 。 ， ， （ trick， ）， ： 。 ， ， 。 ， 。
(2)
-
LinkNode* SortLinkListSelection2(LinkNode* head)
-
{
-
// ， ，
-
//if (NULL == head || NULL == head->next)
-
//{
-
// return head;
-
//}
-
-
LinkNode* p =
NULL;
//
-
LinkNode* pminpre =
NULL;
//
-
LinkNode L = {
0,
NULL};
// ，
-
LinkNode* Ltail = &L;
//Ltail
-
-
while (
NULL != head &&
NULL != head->next)
// 2
-
{
-
pminpre = head;
-
p = head->next;
-
while(
NULL != p &&
NULL != p->next)
//
-
{
-
if (p->next->val < pminpre->next->val)
// pminpre
-
pminpre = p;
-
p = p->next;
-
}
-
if (head->val <= pminpre->next->val)
// ， ，
-
{
-
Ltail = Ltail->next = head;
-
head = head->next;
-
}
-
else
-
{
-
Ltail = Ltail->next = pminpre->next;
-
pminpre->next = pminpre->next->next;
-
}
-
}
-
-
Ltail = Ltail->next = head;
//
-
Ltail->next =
NULL;
//
-
-
return L.next;
-
}
if < <= ， 。
3. （ ）
(1) ： ， 。 end ， ，end ， N-1 。 ， pre，cur，n ， 。
：
-
//asscending sort link list
-
LinkNode* SortLinkListBubble(LinkNode* head)
-
{
-
if (
NULL == head)
-
{
-
return head;
-
}
-
//init end pointer
-
LinkNode* end =
NULL；
-
while(
true)
-
{
-
LinkNode* n = head->next;
-
if (n == end)
-
break;
-
// ，
-
if (n->val < head->val)
-
{
-
head->next = n->next;
-
n->next = head;
-
head = n;
-
}
-
-
LinkNode* pre = head;
-
LinkNode* cur = head->next;
-
LinkNode* tmp;
-
n = cur->next；
-
while(n != end)
-
{
-
if (n->val < cur->val)
-
{
-
tmp = n->next;
-
cur->next = n->next;
-
n->next = cur;
-
pre->next = n;
-
n = tmp;
-
}
-
else
-
{
-
n = n->next;
-
}
-
pre = pre->next;
-
cur = cur->next;
-
}
-
end = cur;
-
}
-
return head;
-
}
4. （ ）
， QsortList ， ， ， ， QsortList 3 ， 。 ， ， ， ， ， 。
(1) ： （ ）， pivot， ， pivot， pivot， pivot 。 ， 。
(2)
， ， 。
-
void QsortList(LinkNode*& head, LinkNode* end)
-
{
-
if(head ==
NULL || head == end)
-
return;
-
LinkNode* pivot = head;
-
LinkNode* p = head->next;
-
LinkNode* head1 =
NULL, *tail1 =
NULL;
-
LinkNode* head2 =
NULL, *tail2 =
NULL;
-
while(p != end)
-
{
-
if(p->val < pivot->val)
-
{
-
if(head1 ==
NULL)
-
{
-
head1 = tail1 = p;
-
}
-
else
-
{
-
tail1->next = p;
-
tail1 = p;
-
}
-
}
-
else
-
{
-
if(head2 ==
NULL)
-
{
-
head2 = tail2 = p;
-
}
-
else
-
{
-
tail2->next = p;
-
tail2 = p;
-
}
-
}
-
p = p->next;
-
}
-
if (tail1)
-
tail1->next = pivot;
-
if (head2)
-
pivot->next = head2;
-
else
-
pivot->next = end;
-
if (tail2)
-
tail2->next = end;
-
if (head1)
-
head = head1;
-
else
-
head = pivot;
-
QsortList(head, pivot);
// head, head1， head
-
-
// pivot->next head2，
-
QsortList(pivot->next, end);
-
}
QsortList QsortList(L, NULL);
， ； ， ， ， 。
：http://blog.sina.com.cn/s/blog_6fb300a30100ng0s.html
8. ？
， ， La ， Lb 。 ， ：
a. ， ( ) ；
b. ， 。
2.
(1)
， ， ， ， 。
， ： ？— ： fast slow， ，slow ，fast ， ， fast ， slow ， 。 fast Null， ， 。
(2)
3.
(1)
， ， ， ， 。 ： ， ， ， 。
(2)
O(length1 + length2)
O(length1)
： ， ， ， O（length1） ， 。
4.
( )， O(len1*len2)， ， 。
：http://www.cnblogs.com/BeyondAnyTime/archive/2012/07/06/2580026.html
http://blog.csdn.net/jiqiren007/article/details/6572685
1： C ， （n） 。
【 】 L, 4 ： prior、 next、 data freq。 freq 0. L.Locate（x） ， x freq 1， ， ， ， 。
【 】
-
void Locate(int &x)
-
{
-
< >
-
// ， x
-
*p = first->next;
-
while (p != first &&
1 p->data!=x )
-
p = p->next;
-
if (p != first)
-
{
-
2 p->freq++;
// ， freq 1
-
< >
-
*current = p;
-
current->prior->next = current->next;
-
current->next->prior = current->prior;
-
p = current->prior;
-
// ，
-
while (p != first &&
3 p->freq<=x)
-
p = p->prior;
-
current->next =
4 p->next;
-
current->prior = p;
-
p->next->prior = current;
-
p->next =
5 current;
-
}
-
else
-
printf(“Sorry. Not find!
”); \* *\
-
}
