Python實(shí)現(xiàn)基本線性數(shù)據(jù)結(jié)構(gòu)

數(shù)組的設(shè)計(jì)

數(shù)組設(shè)計(jì)之初是在形式上依賴內(nèi)存分配而成的，所以必須在使用前預(yù)先請求空間。這使得數(shù)組有以下特性：
     1、請求空間以后大小固定，不能再改變（數(shù)據(jù)溢出問題）；
     2、在內(nèi)存中有空間連續(xù)性的表現(xiàn)，中間不會存在其他程序需要調(diào)用的數(shù)據(jù)，為此數(shù)組的專用內(nèi)存空間；
     3、在舊式編程語言中（如有中階語言之稱的C），程序不會對數(shù)組的操作做下界判斷，也就有潛在的越界操作的風(fēng)險(xiǎn)（比如會把數(shù)據(jù)寫在運(yùn)行中程序需要調(diào)用的核心部分的內(nèi)存上）。
因?yàn)楹唵螖?shù)組強(qiáng)烈倚賴電腦硬件之內(nèi)存，所以不適用于現(xiàn)代的程序設(shè)計(jì)。欲使用可變大小、硬件無關(guān)性的數(shù)據(jù)類型，Java等程序設(shè)計(jì)語言均提供了更高級的數(shù)據(jù)結(jié)構(gòu)：ArrayList、Vector等動態(tài)數(shù)組。

Python的數(shù)組

從嚴(yán)格意義上來說:Python里沒有嚴(yán)格意義上的數(shù)組。

List可以說是Python里的數(shù)組，下面這段代碼是CPython的實(shí)現(xiàn)List的結(jié)構(gòu)體:    
typedef struct {
 PyObject_VAR_HEAD
 /* Vector of pointers to list elements. list[0] is ob_item[0], etc. */
 PyObject **ob_item;
 
 /* ob_item contains space for 'allocated' elements. The number
  * currently in use is ob_size.
  * Invariants:
  *  0 <= ob_size <= allocated
  *  len(list) == ob_size
  *  ob_item == NULL implies ob_size == allocated == 0
  * list.sort() temporarily sets allocated to -1 to detect mutations.
  *
  * Items must normally not be NULL, except during construction when
  * the list is not yet visible outside the function that builds it.
  */
 Py_ssize_t allocated;
} PyListObject;

當(dāng)然，在Python里它就是數(shù)組。
后面的一些結(jié)構(gòu)也將用List來實(shí)現(xiàn)。

堆棧

什么是堆棧

堆棧（英語：stack），也可直接稱棧，在計(jì)算機(jī)科學(xué)中，是一種特殊的串列形式的數(shù)據(jù)結(jié)構(gòu)，它的特殊之處在于只能允許在鏈接串列或陣列的一端（稱為堆疊頂端指標(biāo)，英語：top）進(jìn)行加入資料（英語：push）和輸出資料（英語：pop）的運(yùn)算。另外堆疊也可以用一維陣列或連結(jié)串列的形式來完成。堆疊的另外一個相對的操作方式稱為佇列。

由于堆疊數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作。
特點(diǎn)
     1、先入后出，后入先出。
     2、除頭尾節(jié)點(diǎn)之外，每個元素有一個前驅(qū)，一個后繼。
操作
從原理可知，對堆棧(棧)可以進(jìn)行的操作有:
     1、top() :獲取堆棧頂端對象
     2、push() :向棧里添加一個對象
     3、pop() :從棧里推出一個對象
實(shí)現(xiàn)    
class my_stack(object):
 def __init__(self, value):
  self.value = value
  # 前驅(qū)
  self.before = None
  # 后繼
  self.behind = None
 
 def __str__(self):
  return str(self.value)
 
 
def top(stack):
 if isinstance(stack, my_stack):
  if stack.behind is not None:
   return top(stack.behind)
  else:
   return stack
 
 
def push(stack, ele):
 push_ele = my_stack(ele)
 if isinstance(stack, my_stack):
  stack_top = top(stack)
  push_ele.before = stack_top
  push_ele.before.behind = push_ele
 else:
  raise Exception('不要亂扔?xùn)|西進(jìn)來好么')
 
 
def pop(stack):
 if isinstance(stack, my_stack):
  stack_top = top(stack)
  if stack_top.before is not None:
   stack_top.before.behind = None
   stack_top.behind = None
   return stack_top
  else:
   print('已經(jīng)是棧頂了')

隊(duì)列

什么是隊(duì)列

和堆棧類似，唯一的區(qū)別是隊(duì)列只能在隊(duì)頭進(jìn)行出隊(duì)操作，所以隊(duì)列是是先進(jìn)先出（FIFO, First-In-First-Out）的線性表

特點(diǎn)

      1、先入先出,后入后出

      2、除尾節(jié)點(diǎn)外,每個節(jié)點(diǎn)有一個后繼

      3、（可選）除頭節(jié)點(diǎn)外,每個節(jié)點(diǎn)有一個前驅(qū)

操作

      1、push（） :入隊(duì)

      2、pop（） ：出隊(duì)

實(shí)現(xiàn)

普通隊(duì)列    
class MyQueue():
 def __init__(self, value=None):
  self.value = value
  # 前驅(qū)
  # self.before = None
  # 后繼
  self.behind = None
 
 def __str__(self):
  if self.value is not None:
   return str(self.value)
  else:
   return 'None'
 
 
def create_queue():
 """僅有隊(duì)頭"""
 return MyQueue()
 
 
def last(queue):
 if isinstance(queue, MyQueue):
  if queue.behind is not None:
   return last(queue.behind)
  else:
   return queue
 
 
def push(queue, ele):
 if isinstance(queue, MyQueue):
  last_queue = last(queue)
  new_queue = MyQueue(ele)
  last_queue.behind = new_queue
 
 
def pop(queue):
 if queue.behind is not None:
  get_queue = queue.behind
  queue.behind = queue.behind.behind
  return get_queue
 else:
  print('隊(duì)列里已經(jīng)沒有元素了')
 
def print_queue(queue):
 print(queue)
 if queue.behind is not None:
  print_queue(queue.behind)
鏈表
什么是鏈表
鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會按線性的順序存儲數(shù)據(jù)，而是在每一個節(jié)點(diǎn)里存到下一個節(jié)點(diǎn)的指針(Pointer)。由于不必須按順序存儲，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點(diǎn)或者訪問特定編號的節(jié)點(diǎn)則需要O(n)的時(shí)間，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。

特點(diǎn)

使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大。

操作
      1、init() :初始化

      2、insert() : 插入

      3、trave() : 遍歷

      4、delete() : 刪除

      5、find() : 查找

實(shí)現(xiàn)

此處僅實(shí)現(xiàn)雙向列表    
class LinkedList():
 def __init__(self, value=None):
  self.value = value
  # 前驅(qū)
  self.before = None
  # 后繼
  self.behind = None
 
 def __str__(self):
  if self.value is not None:
   return str(self.value)
  else:
   return 'None'
 
 
def init():
 return LinkedList('HEAD')
 
 
def delete(linked_list):
 if isinstance(linked_list, LinkedList):
  if linked_list.behind is not None:
   delete(linked_list.behind)
   linked_list.behind = None
   linked_list.before = None
  linked_list.value = None
總結(jié)
以上就是利用Python實(shí)現(xiàn)基本線性數(shù)據(jù)結(jié)構(gòu)的全部內(nèi)容