数据结构链表.doc

1.双链表的定义：我们熟悉一个新的事物，往往都会从自己已经熟悉且有固定经验的事物出发，去寻找相似点，
0 V2 V6 z8 F% g                           发现不同点，所以我们完全可以用这种思路去认识双向链表。双向链表和单链表的唯一区别就是
8 m" A* o9 }: Y1 S6 m                           双链表多了一个指针域，指向前驱结点。( o# [) U1 J. O8 I
                           typedef struct DNode3 D; M: P( R7 D3 p( ^
                           {
3 I( z* f5 i  `! U; q0 U1 `                                  int data;( N& d4 a/ y' T1 F! K, B7 @
                                  struct DNode *next;5 w# Y; m# l5 ^. R
                                  struct DNode *prior;    // 指向前驱结点+ D8 D" h% O$ ^: U
                           } DLinkList;
3 [1 ?( ]+ ?5 v  b; K) q                           我想这个真的是没甚麽（这货不是台湾人，这货不是台湾人……）好说的了* y) L1 U1 D& P) [# h" x2 Z5 l1 K
* J) E+ n+ T5 U" U3 r
2.头插法建立双链表：注意和头插法建单链表比较
( m" p: u# x# V8 J+ M0 b                                  void CreateListF (DLinkList *&L,int a [  ],int n)0 J" ]8 x8 @- F3 g: H9 \* y
                                   {6 {. }3 A. B/ {, j0 _7 c
                                          DLinkList *s;
; c" _% W+ v% z                                          L=(DLinkList *)malloc(sizeof(DLinkList));
; K* Z4 P3 N  S                                          L->prior=L->next=NULL;             // 双链表的情形下建立头结点
# \4 y% G1 b+ l  H% e                                          for (int i=0;i<n;i++)# r* b+ I; j4 T( h: o5 ?" ]+ }
                                          {
$ y( o8 z0 r9 y: f4 H9 M( N                                               s=(DLinkList *)malloc(sizeof(DLinkList));2 z- w: t, w4 ]6 }. L. n
                                               s->data=a [ i ];8 Q8 D) o; {( _9 T5 ]
                                               s->next=L->next;     // 将*s插在原开始结点之前，头结点之后- R) Y- e; n: M4 `4 ~3 v
                                               if (L->next != NULL); i- s9 [' J/ Z* `+ n
                                                   L->next->prior=s;: P- h/ V- M' S2 y+ w9 S
                                               L->next=s;
2 s% E  ?/ d- D3 W) R                                               s->prior=L;- x4 a3 |4 h0 X. i7 A5 x) v
                                          }0 t' e" B+ v, E! ~2 P
                                    }                                    . @) Q/ s7 Z" ^2 r0 p
                                    双链表的每个结点（包括头结点）都有三个域，两个指针域和一个数据域，所以，建立头结点的思路和单链表是8 }! m$ x- l5 q+ J+ }2 k
                                    和单链表完全一样的。OK，那我们再来回顾一下当年（前天……）是怎么用头插法建立单链表的头结点的，
6 w! f7 ?( Q+ p: ^4 g; U/ V                                    L->next=NULL;这句话的意思就是让头结点的指针域为空，那么同样的，到了双链表，也是要让头结点变空，这样
7 }% C8 J, [8 t3 M9 x4 a# \                                    自然就写出了L->prior=L->next=NULL;  怎么样，不难吧  So…………easy…………  
9 @, f6 j% |( ?4 [9 n9 j# `
2 R: l. P7 B6 B2 }, a5 J( Z                                    好嘞，咱们再往下走着…………这时我们再来温习一下头插法的思路：*s是要吸收进来的新结点，7 U9 f* t) z6 ^9 b
                                    *L是头结点，头插法是要每次新吸收的结点都要成为当时链表的开始结点。7 _5 d" z+ _2 N4 `, s- R4 Z
                                    if (L->next != NULL)3 }# C: A! ^3 ~1 }9 r& e
                                         L->next->prior=s;
/ p$ B1 X3 s2 u) F: }" ?) Q! ?                                    L->next=s;
  U  k: e0 g- T! c                                    s->prior=L;                                     所以，这几句就很容易啦，这几句的作用就是将*s放到*L的后面去，然后，两端连上就OK。这里3 f1 t9 u  J' n% n
                                    我要多说两句，大家看看它是怎么连上的？我为了说明方便，将*L称为第一个结点，*s为第二个结点，- w$ A) c5 @- W& P; f1 @7 Z" h
                                    *s后面的那个结点是第三个结点。5 i# J* T# O7 f% Y7 ?$ r& Q
                                    第一步：将第三个结点的->prior 指向第二个结点
$ T" N6 W( C2 u$ e; N6 k% @& W0 L: m: A                                    第二步：第一个结点的->next 指向第二个结点
- t* i+ P( a8 N5 P& @4 o                                    第三步：将第二个结点的->prior 指向第一个结点
' p. Q. y9 x) ]5 J/ C; n, d3 ^" t