計算機概論筆記-Implementing Data Structures

8-2 Implementing Data Structures

1.Homogeneous Arrays.

 

(1)row major order:a row finished , and then  next a row continue.

(2)column major order:a column finished , and then next a column continue.

 

2.Heterogeneous Arrays.

 

(1)   Everyone component in a separate location and then link them together by means of “pointer”.

 

3.Storing List

 

(1)Linked List:鏈結串列.

(2)NIL pointer:也等同於NULL pointer:表示說”list”的後面沒有其他項目.

 

4.Storing Stacks and Queues

 

(1)Stack pointer:To record this location , its address is stored in an additional memory Cell.

Ø          Adjust the stack pointer:調整堆疊指標.

Ø          The tail pointer always points to the first vacancy at the tail of the queue:

    尾指標總是指到序列末端的第一個空位.

Ø          Circular Queue:queues chases itself around within the block rather than wandering off  through memory.

 

5.Storing Binary Tree

 

(1)   Three item:

Ø          Data

Ø          A pointer points to first node.(first node è Left child pointer)

Ø          A pointer points to second node. .(second node è Right child pointer)

 

(2)   if child node does not exist ,pointer changes to “NIL”.

(3)   Root pointer:retain a special memory location to store the address of the “root node”.