선형 테이블과 듀얼 체인 테이블 달성 방법을 간단히 소개합니다.

선형 미터는 선형 구조로, 동일한 유형 N (n ≥ 0) 데이터 요소를 갖는 제한된 시퀀스입니다.

1. 배열
어레이는 상한 및 하한을 가지며 배열의 요소는 상부 및 하한에서 연속적입니다.

10,20,30, 40, 50 50 배열의 개략도는 다음과 같습니다.

배열의 특징 : 데이터는 연속적입니다.
약간 더 복잡한 배열은 다차원 배열 및 동적 배열입니다. C 언어의 경우 다차원 배열은 하나의 차원 배열을 통해 실현됩니다. 동적 배열은 동적으로 성장할 수있는 인덱스 그룹의 배열입니다 벡터;

둘째, 일 -링크 링크 <BR /> one -way 링크 목록 (단일 링크 된 목록)은 링크 된 목록의 유형으로 구성됩니다.

단일 링크 된 목록의 개략도는 다음과 같습니다.

헤드의 헤드는 비어 있고, 헤드의 후속 노드는 "노드 10"(데이터 10의 노드)이고 "노드 10"의 후속 노드는 "노드 20"(데이터 10이 포함 된 데이터)입니다. ..

단일 체인 삭제 노드

"노드 30"삭제
삭제하기 전에 : "노드 20"의 후속 노드는 "노드 30"이고 "노드 30"의 후속 노드는 "노드 40"입니다.
삭제 후 : "노드 20"의 후속 노드는 "노드 40"입니다.

단일 링크 목록이 추가 된 노드

"노드 10"과 "노드 20"사이에 "노드 15"를 추가하십시오.
추가하기 전에 : "노드 10"의 후속 노드는 "노드 20"입니다.
추가 후 : "노드 10"의 후속 노드는 "노드 15"이고 "노드 15"의 후속 노드는 "노드 20"입니다.

단일 링크 목록의 특성은 노드의 링크 방향이 배열과 비교하여 단일 체인 목록의 임의의 액세스 속도는 느리지 만 단일 연결 목록 삭제/추가 데이터가 높다는 것입니다.

셋째, 두 개의 웨이 링크 목록
두 개의 way 링크 목록 (듀얼 링크 목록)은 링크 된 목록의 유형입니다. 단일 링크 목록과 마찬가지로 듀얼 체인 목록에는 각 데이터 노드에도 두 개의 포인터가 있습니다. 따라서 두 개의 웨이 링크 목록의 모든 노드에서 시작하여 전면 드라이브 노드 및 후속 노드에 쉽게 액세스 할 수 있습니다. 일반적으로, 우리는 모두 두 개의 원형 원형 연결 목록을 구성합니다.

듀얼 링크 목록의 개략도는 다음과 같습니다.

헤더는 비어 있고, 헤드의 후속 노드는 "노드 10"(Node 10 "의 후속 노드는"노드 20 "(데이터 10 노드),"노드 20 "사전 -입니다. 연속체는 "Node 20"의 후속 노드는 "Node 30"이며 "Node 20"입니다. .

이중 체인 시계 삭제 노드

"노드 30"삭제
삭제하기 전에 : "노드 20"의 후속 노드는 "노드 30"이고, "노드 30"의 사전 -노드는 "노드 20"입니다. "노드 30"의 후속 노드는 "노드 40"이고 "노드 40"의 프리너 노드는 "노드 30"입니다.
삭제 후 : "노드 20"의 후속 노드는 "노드 40"이고 "노드 40"의 사전 -노드는 "노드 20"입니다.

더블 링크 목록 추가 노드

"노드 10"과 "노드 20"사이에 "노드 15"를 추가하십시오.
추가하기 전에 : "노드 10"의 후속 노드는 "노드 20"이고 "노드 20"의 이전 노드는 "노드 10"입니다.
추가 후 : "노드 10"의 후속 노드는 "노드 15"이고 "노드 15"의 사전 -노드는 "노드 10"입니다. "노드 15"의 후속 노드는 "노드 20"이고, "노드 20"의 이전 노드는 "노드 15"입니다.

이중 체인 목록의 구현은 아래에 소개되며 C/C ++/Java의 세 가지 구현이 각각 소개됩니다.

1. c 이중 링크 목록을 구현합니다

코드 2- 웨이 링크 목록 파일 (double_link.h) 구현

 #ifndef_double_link_h#define_double_link_h // "2- 웨이 링크 목록"을 만듭니다. 성공, 그렇지 않으면 Nullextern int create_dlink ()를 반환합니다. 성공, 반환 0; 그렇지 않으면 -1extern int destrove_dlink ()로 돌아갑니다. 공허함을 위해 1로 돌아갑니다. extern int dlink_is_empty (); 성공, 그렇지 않으면 NULL을 반환하십시오. extern void* dlink_get (int index); 성공, 그렇지 않으면 NULL을 반환하십시오. extern void* dlink_get_first (); 성공, 그렇지 않으면 NULL을 반환하십시오. extern void* dlink_get_last (); // 인덱스 위치에 "값"을 삽입합니다. 성공, 반환 0; 그렇지 않으면 반품 -1. extern int dlink_insert (int index, void *pval); // 헤드 위치에 "값"을 삽입합니다. 성공, 반환 0; 그렇지 않으면 반품 -1. extern int dlink_insert_first (void *pval); 성공, 반환 0; 그렇지 않으면 반품 -1. extern int dlink_append_last (void *pval); 성공, 반환 0; 그렇지 않으면 -1extern int dlink_delete (int int index)로 돌아갑니다. 성공, 반환 0; 그렇지 않으면 dlink_delete_first ()로 -1extern으로 돌아갑니다. 성공, 반환 0; 그렇지 않으면 반환, -1extern int dlink_delete_last ();#endif로 돌아갑니다

Double_link.c는 두 개의 웨이 링크 목록에 있습니다

 #include <stdio.h> #include <malloc.h>/*** c lingle의 두 개의 way 링크 목록은 임의의 데이터를 저장할 수 있습니다. ** @author skywang* @date 2013/11/07*// 2- 링크 된 목록 구조물 tag_node {struct tag_node*; 헤드 값은 요소 값을 저장하지 않습니다! 교차로 교차로 정적 노드 *phead = null; static int count = 0; // 새 "노드"를 만듭니다. 성공, 그렇지 않으면 NULL을 반환하십시오. static node *create_node (void *pval) {node *pnode = null; "); return null;} // 기본값, 첫 번째 노드 및 후자의 노드는 자체 pnode-> prev = pnode-> next = pnode; // 노드 값이 pvalpnode-> p =를 가리 킵니다. PVAL;; "2- 웨이 링크 목록". 성공, 반환 0; 그렇지 않으면 반품 -1. int create_dlink () {// create_node (null)를 만들기 -1; return count == 0;} // "2- 웨이 링크 목록"int dlink_size () {return count;} // 두 개의 way 링크 목록의 인덱스 위치에서 "노드를 가져옵니다"정적 노드* get_. 노드 (int index) {ifx <0 || index> = count) {printf ( "%s 실패! index of bound!/n", __func __); if (index <= (count/2)) {int i = 0; int j = 0; int rindex = index -1; 노드 "정적 노드 * g et_first_node () () return get_node (0);} //"last node "static node를 가져옵니다 * get_last_node () {return get_node (count-);} //"인덱스 위치 요소 get get get get get get get get get get get get get get get get_node (count-); 양방향 링크 목록에서 ". 성공, 반환 노드 값, 그렇지 않으면 -1. void * dlink_get (int index) {node * pindex = get_node (! pindex) {printf ( "%s 실패!/n", __func __); 1 d”void* dlink_get_first () {return dlink_get (0);} // 获取“双向链表中最后 1 个元素的值”void* dlink_get_last () {return dlink_get (count-1);} // "PVAL"을 인덱스 위치에 삽입하십시오. 성공, 반환 0; 그렇지 않으면 반품 -1. int dlink_insert (int index, void * pval) {// 헤더 삽입 if (index == 0) return dlink_insert_first (pvalt (pval); // 삽입 할 위치에 해당하는 노드 노드를 가져옵니다.; if (if (if). if! pindex) return -1; // 创建 创建 "节点"node *pnode = create_node (pval); if (! pnode) return -1; pnode-> prev = pindex-> ​​prev; pnode-> next = pindex; pindex -> pindex-> ​​prnode; {pnod e = pnode-> phead-> phead-> pnode; ++; 반환 0; pnode-> phead-> phead-> prnode; 링크 된 목록 ". 성공, 반환 0; 그렇지 않으면 반품 -1. int dlink_delete (int index) {node *pindex = get_node (! pindex) {printf (faced! on in indect!/n);} pindex- > next-> prev = pindex-> ​​prev; pindex-> ​​prev-> next = pindex-> ​​next; free (pindex); count-; return 0;} // 删除第一个节点 int dlink_delete_first () {return dlink_delete (0);} // 노드 삭제 int dlink_delete_last () {return dlink_delete (count-);} // "양방향 링크 목록"을 다시 방문합니다. 성공, 반환 0; 그렇지 않으면 반품 -1. int destroy_dlink () {if (! phead) {printf ( "%s 실패!/n", __func __); while (pnode) {pnode-> free (pnode);

2- 웨이 연결 목록 테스트 프로그램 (DLINK_TEST.C)

 #include <stdio.h> #include "double_link.h"/*** c 언어는 두 가지 링크 링크 목록 테스트 프로그램을 구현합니다. ** (01) int_test ()* 두 개의 웨이 링크 목록에서 "int data"를 보여줍니다. * (02) string_teest ()* 두 개의 웨이 링크 목록에서 "스트린 데이터"를 보여줍니다. * (03) Object_Teest ()* 두 개의 웨이 링크 목록에서 "객체"를 보여줍니다. ** @Author Skywang* @Date 2013/11/07* // 2 방향 링크 목록 작업 int 데이터 void int_teest () {int iarr [4] = {10, 20, 30, 40}; n -----%s ------ ", __func __); create_dlink (); // 양방향 링크 된 목록 작성 dlink_insert (0, & iarr [0]); // 데이터 삽입 dlink_insert (0, & & & Ig & & IG & & & & & & & & 1]; data printf ( "dlink_is_empty () =%d/n", dlink_is_empty ()); 두 가지 링크 링크 목록의 크기 int *p에 대한 int *; ) dlink_get (i); 20 ","30 ","/n ----%s ----%s-/n ", __func __); 0, SARR [0]; // 양방향 링크 목록의 헤더에 DLINK_INSERT (0, SARR [1]); 두 개의 링크 링크 목록; // Data Printf 삽입 (Dlink_is_empty () =%d/n ", dlink_is_empty (); n ", dlink_size ()); // 두 way 링크 목록의 크기 // 두 개의 way 링크 목록에서 모든 데이터 int i를 인쇄; char *p; int sz = dlink_size (); for (i = 0; tag_stu {int id; char name;} stu; {40, {40, {40, {40, "40,"dan "},};#define arr_stu_size", __func __); create_dlink (); // 두 가지 링크 링크 목록 Dlink_insert (0, & arr_stu [0] ); // 데이터 링크 링크 목록에 링크 된 링크 된 목록 (0, 0, arr_stu [2]); "dlink_is_empty () =%d/n", dlink_is_empl ()); 두 개의 링크 된 목록 // int I int I int i; ) dlink_get (i); ); // "int data"를 두 개의 way 링크 목록으로 보여줍니다. string_test (); // "문자열 데이터"를 두 개의 way 링크 목록으로 보여줍니다. object_test (); 반환 0;}

실행 결과

 ---- int_test ----- Dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = 30d_get (1) = 20dlink_get 0dlink_size () = 3dlink_get (0) = Thirtydlink_get (1) = Twentydlink_get (2) = 10- -object_test ----- Dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = [30, Vic] dlink_get (1) = [20, jody] dlink_get (2) = [10, Sky]

2. C ++는 이중 체인 목록을 실현합니다

코드 2- 웨이 연결 목록 파일 (Doublelink.h) 구현

 #ifndef double_link_hxx#double_link_hxx#emplate <class t> public : t value; 이전, 다음) {this-> prev; int get (); int delete_last (private); ) {// "속도"를 만듭니다. 참고 : 헤드에 스토리지 데이터가 없습니다! phead = new dnode <t> (); phead-> phead-> 다음 = phead; > :: ~ doughlink () {// 모든 노드 <t>* pnode = phead-> while; PTMP 삭제;} // "head"삭제 Phead = null; 체인 목록 为空 템플릿 <class t> int doublelink <t> :: is_empty () {return count == 0;} // 获取第 index 位置的节点 템플릿 <class t> dnode <t>* doublelink <t> : : get_node (int index) {// 판단 매개 변수 유효성 (index <0 || index> = count) {cout << get node! / index <= count/ 2) {int i = 0; ;} / / 리버스 int J = 0; count -index -1; ;} / / 인덱스 위치 노드 <클래스 t> t doublelink <t> :: get (int index) {return get_node (index)-> value;} // 첫 번째 노드의 값을 가져옵니다. Temple <class t> trivelink <t> :: get_first () {return get_node (0)-> value;} // 마지막 노드의 값을 가져옵니다.> value;} // 노드 삽입 템플릿 전 인덱스 위치 <class t> int doublelink <t> :: insert (int index, t t) {ifx == 0) insert_first (t) ;; prev, pindex-> ​​pindex-> ​​prev = pnode;}; 템플릿 <class t> int doublelink <t> :: insert_fring (t) {dnode <t>* new dnode <t> (t, phead-> next-); > Pnode ++; > pnode; count ++;} // 인덱스 위치 <class t> int doublelink <t> (intind) > next-> pindex-> ​​pindex-> ​​다음; count-; retain <emplate <class t> int doublelink <t> :: delete_first () {return del (0);} // 템플릿 <class t> int doublelink <t> :: delete_last () {return del (count-);} #endif

2- 웨이 링크 된 목록 테스트 파일 (dlinktest.cpp)

 #include <iostream> #include "d -"<< endl; // 양방향 링크 목록을 만듭니다. Doublelink <int>* pdlink = new Doublelink <int> (); pdlink-> 삽입 (0, 20); // 첫 번째 위치 pdlink-에 20을 삽입하십시오. > 부록 (10); "is_empty () ="<< pdlink-> is_empty () << endl; // 양방향 링크 목록의 크기는 cout << ""size () = "<< pdlink-> size () << endl; get (i) << endl;} void string_test () {String Sarr [4] = {10 ","Twenty ","Forty "}; -"<< endl; SARR의 첫 번째 pdlink-> append_last (SARR [0]); // 링크 된 목록의 끝에서 SARR의 첫 번째 요소를 pdlink-> insert_fring (SARR [2]); 위치 // 양방향 링크 목록이 비어 있는지 << "is_empty () ="<< pdlink-> is_empty () << endl; = "<< pdlink-> size () << endl; // 모든 데이터 int sz = pdlink-> size (); for (int i = 0; i <sz; i ++)"< "=" << pdlink-> get (i) << endl;} int id; , {30, "vic"}, {40, "dan"},};#define arr_stu_size cout << "/n ---- 객체 _test ----"; List Doublelink <stu>* pdlink = new Doublelink <stu> (); insert (0, arr_stu [1 [1]; // arr_stu의 두 번째 요소를 pdlink-> backend_last의 첫 번째 위치에 삽입하십시오. (arr_stu [0]; // arr_stu의 첫 번째 요소를 링크 된 pdlink-> insert_fring의 끝에 추가 첫 번째 위치 // 양방향 링크 된 목록이 비어 있는지 << "is_empty () ="<< pdlink-> is_empty () << endl; << pdlink-> size () << endl; -> get (i); cout << pdlink ( "<< i <<") = [<< p.id << ","<< p .name << "]"<< endl;} int main. ) {int_teest (); string_test (); // "문자열 데이터"를 두 개의 way 링크 목록으로 보여줍니다. object_test (); 반환 0;}

예제 설명

위의 예에서는 헤더 파일에 Two -Way 링크 목록의 "명령문"및 "구현"을 넣습니다. 프로그래밍 사양은 우리에게 경고합니다 : 클레임의 선언 및 구현을 분리하고 헤더 파일 (.H 파일 또는 .hpp)의 양에는 문 만 포함되었으며 구현 파일 (.CPP 파일)에서 구현을 담당했습니다!
그렇다면 왜 이렇게합니까? 이는 두 개의 웨이 링크 목록을 구현할 때 템플릿이 채택되기 때문에 C ++ 컴파일러는 템플릿의 별도 컴파일을 지원하지 않습니다! 간단히 말해서, doublelink.h로 선언되고 Doublelink.cpp에서 구현되면 다른 범주에서 Doublelink의 객체를 만들면 오류가 컴파일됩니다. 특정한 이유로 "C ++ 컴파일러가 템플릿의 별도의 컴파일을 지원할 수없는 이유"를 참조하십시오.

실행 결과

 ---- int_test ---- Is_empty () = 0Size () = 3pdLink (0) = 30pdLink (1) = 20pdLink (2) = 10 ---- String_test ----- empty () = 0Size () = 3pdlink (0) = ThirdLink (1) = TwentyPdLink (2) = 10 ---- 객체_test ---- Is_empty () = 0Size () = 3PDLINK (0) = [30, VIC] PDLINK (1) = [ 20 20, Jody] pdlink (2) = [10, Sky]

3. Java는 이중 체인 목록을 깨닫습니다

Doublelink.java 구현

 /*** Java의 2- 웨이 링크 목록. * 참고 : Java의 컬렉션 패키지에는 Java.util.linkedList ** @Author Skywang* @Date 2013/11/07*/Public Class DoublElink <t> {/입니다. / // Mcount에 대한 Node Number; {this.value = value.prev = prev; 참고 : 헤드에 스토리지 데이터가 없습니다! mhead = new dnode <t> (null, null, null); 링크 된 목록이 빈 부울 isempty () {return mcount == 0;} // 노드 개인 dnode <t> getNode (int index) {index <0 || index> = MCOUNT는 if (index <= mcount/2)를 검색합니다 ;} // dnode <t> rnode = mhead.prev; int rindex = mcount -1; for (int j = 0; J ++) rnode = rnode; / getNode (0)의 값을 가져옵니다. <t> (t, mhead.next) t> (t, inode.prev, inode); public void insertfirst (t t) {insert (0, t);} // 링크 된 공개 void actendlast (t t) {dnode <t> new dnode <t> (t, mhead. prev mhead); mhead.prev.next = node; mcount ++; .next = inode.next.prev = inode = mcount-;}; Node public void deletelast () {del (mcount-);}}

테스트 프로그램 (dlinktest.java)

 /*** Java의 2- 웨이 링크 목록. * 참고 : 컬렉션 패키지에는 Java와 함께 제공되는 두 개의 way 링크 목록이 있습니다. 두 가지 링크 된 테이블 작동 int 데이터 개인 정적 void int_teest () {int [] {10, 20, 30, 40}; = New Doublelink <integer> (); INSERT (0, 20); 첫 번째 위치 // 두 개의 way 링크 목록이 빈 시스템인지 여부 d/n ", dlink.size ()); // (int i = 0; i <dlink.size (); i ++) system.out .println ("dlink ( "+i+")에 대한 모든 노드 인쇄 = "+dlink.get (i));} private static void string_test () {string [] sarr = {"10 ","30 ","forty ""}; /n ---- String_test ---- "); // 양방향 링크 목록 Doublelink <string> dlink = new Doublelink <string> (); [1]); // SARR에 두 번째 요소를 삽입 첫 번째 위치 dlink.appendlast (sarr [0]); 첫 번째 위치 // 두 개의 way 링크 된 목록이 빈 시스템인지 여부 =%d/ n ", dlink.size ()); // (int i = 0; i <dlink.size (); i ++) system.out.println ("dlink ( "+i+ ") ="+dlink.get (i));} // 내부 클래스 개인 정적 클래스 학생 {private String id 학생 (int id, string name) {this.id = id; ouverridepublic string tostring () { "+id+", "+name+"] ";} tudent [] studers = new Student [] {신입생 (10,"Sky "), 신입생 (20,"Jody "), New 학생 (30, vic "), 신입생 (40,"dan "),} {System.out.println ("/n ---- object_test ---- "); 양방향 링크 목록 Doublerink <tudent> dlink = new doublelink <tudent> (); 학생들의 첫 번째 요소는 dlink.insertfirst (학생 [학생 [학생 [2]); printf ( "isempty () =%b/n", dlink.isempty ()); "size () =%d/n", dlink.size (); (int i = 0; i <dlink.size ()) {system.out.println ( "+i+") = "+dlink.get (i)); static void main (string [] arts) {int_test (); string_test (); // "문자열 데이터"를 두 개의 way 링크 목록으로 보여줍니다. object_test (); }}

실행 결과

 ---- int_test ---- isempty () = falsesize () = 3dlink (0) = 30dlink (1) = 20dlink (2) = 10 -------------- 문자열 _test —-- isempty () = falsesize () = 3DLINK (0) = ThirtyDlink (1) = TwentyDlink (2) = 10 ---- Object_Teest --- isempty () = falsesize () = 3dlink (0) = [30, Vic] dlink (1) = [20 20 , Jody] Dlink (2) = [10, Sky]

위는이 기사의 모든 내용입니다.