亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

python算法與數據結構之單鏈表的實現代碼

系統 1781 0

= 一、鏈表

鏈表是一種物理存儲單元上非連續、非順序的存儲結構,數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點(鏈表中每一個元素稱為結點)組成,結點可以在運行時動態生成。每個結點包括兩個部分:一個是存儲數據元素的數據域,另一個是存儲下一個結點地址的指針域。 相比于線性表順序結構,操作復雜。由于不必須按順序存儲,鏈表在插入的時候可以達到O(1)的復雜度,比另一種線性表順序表快得多,但是查找一個節點或者訪問特定編號的節點則需要O(n)的時間,而線性表和順序表相應的時間復雜度分別是O(logn)和O(1)。

使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點,鏈表結構可以充分利用計算機內存空間,實現靈活的內存動態管理。但是鏈表失去了數組隨機讀取的優點,同時鏈表由于增加了結點的指針域,空間開銷比較大。鏈表最明顯的好處就是,常規數組排列關聯項目的方式可能不同于這些數據項目在記憶體或磁盤上順序,數據的存取往往要在不同的排列順序中轉換。鏈表允許插入和移除表上任意位置上的節點,但是不允許隨機存取。鏈表有很多種不同的類型:單向鏈表,雙向鏈表以及循環鏈表。

二、單鏈表介紹

單向鏈表(單鏈表)是鏈表的一種,其特點是鏈表的鏈接方向是單向的,對鏈表的訪問要通過順序讀取從頭部開始。單鏈表是一種鏈式存取的數據結構,用一組地址任意的存儲單元存放線性表中的數據元素。鏈表中的數據是以結點來表示的,每個結點的構成: 元素(數據元素的映象) + 指針(指示后繼元素存儲位置) ,元素就是存儲數據的存儲單元,指針就是連接每個結點的地址數據。它的每個節點包含兩個域, 一個信息域(元素域)和一個鏈接域 。這個鏈接指向鏈表中的下一個節點,而最后一個節點的鏈接域則指向一個空值。

鏈式存儲結構的線性表將采用一組任意的存儲單元存放線性表中的數據元素。由于不需要按順序存儲,鏈表在插入、刪除數據元素時比順序存儲要快,但是在查找一個節點時則要比順序存儲要慢,使用鏈式存儲可以克服順序線性表需要預先知道數據大小的缺點,鏈表結構可以充分利用內存空間,實現靈活的內存動態管理。但是鏈式存儲失去了數組隨機存取的特點,同時增加了節點的指針域,空間開銷較大。

三、單鏈表結構

python算法與數據結構之單鏈表的實現代碼_第1張圖片

  • 表元素域elem用來存放具體的數據。
  • 鏈接域next用來存放下一個節點的位置(python中的標識)
  • 變量p指向鏈表的頭節點(首節點)的位置,從p出發能找到表中的任意節點。

四、單鏈表的常用操作圖解

1、頭插

python算法與數據結構之單鏈表的實現代碼_第2張圖片

2、尾插

python算法與數據結構之單鏈表的實現代碼_第3張圖片

3、指定為之插入

python算法與數據結構之單鏈表的實現代碼_第4張圖片

4、刪除

python算法與數據結構之單鏈表的實現代碼_第5張圖片

五、單鏈表的python代碼實現

            
# 創建節點
class Node(object):
  def __init__(self,item):
    self.element = item
    self.next = None
# 創建單鏈表類
class SingleLinkList(object):
  def __init__(self):
    self.header = None
    self.length = 0
  # 1、判斷是否為空
  def is_empty(self):
    if self.header == None:
      return True
    else:
      return False
  # 2、頭部插入
  def add(self,node):
    if self.is_empty():
      self.header = node
    else:
      node.next = self.header
      self.header = node
      # currentNode = self.header
    self.length += 1
  # 3、尾部插入
  def appent(self,node):
    currentNode = self.header
    if self.is_empty():
      self.add(node)
    else:
      while (currentNode.next != None):
        currentNode = currentNode.next
      currentNode.next = node
      self.length += 1
  # 4、指定位置插入
  def insert(self,node,index):
    currentNode = self.header
    if index>self.length+1 or index<=0:
      print("你要插入的位置不對,請重現選擇位置")
    if index == 1:
      self.add(node)
    elif index == 2:
      node.next = self.header.next
      self.header.next = node
      self.length += 1
    else:
      for i in range(1,index-1):
        currentNode = currentNode.next
      node.next = currentNode.next
      currentNode.next = node
      self.length += 1
  # 5、遍歷
  def travel(self):
    currentNode = self.header
    if self.length == 0:
      print("你要遍歷的鏈表沒有數據\n")
    else:
      print("你要遍歷的鏈表里面的元素有:",end=" ")
      for i in range(self.length):
        print("%s "%currentNode.element,end=" ")
        currentNode = currentNode.next
      print("\n")
  # 6、排序不用交換節點的位置,只需要交換節點上的數據值
  def list_sort(self):
    for i in range(0,self.length-1):
      currentNode = self.header
      for j in range(0,self.length-i-1):
        if currentNode.element > currentNode.next.element:
          temp = currentNode.element
          currentNode.element = currentNode.next.element
          currentNode.next.element = temp
        currentNode = currentNode.next
  # 7、按索引刪除
  def remove(self,index):
    if index<=0 or index>self.length:
      print("你輸入的下標不對,請重新輸入")
      return
    else:
      if index == 1:
        self.header = self.header.next
        currentNode = self.header
      elif index == 2:
        currentNode = self.header
        currentNode.next = currentNode.next.next
      else:
        currentNode = self.header
        for i in range(1,index-1):
          currentNode = currentNode.next
        currentNode.next = currentNode.next.next
    self.length -= 1
  # 8、查找是否包含,并返回下標
  def isContain(self,num):
    contain = 0
    currentNode = self.header
    for i in range(self.length):
      if currentNode.element == num:
        print("%d在鏈表中%d處\n"%(num,i))
        contain = 1
      currentNode = currentNode.next
    if contain == 0:
      print("%d不在鏈表中\n"%num)
  # 9、根據下標找節點
  def searchNodeByIndex(self,index):
    currentNode = self.header
    if index<=0 or index>self.length:
      print("你輸入的下標不對,請重新輸入\n")
      return 0
    else:
      for i in range(index-1):
        currentNode = currentNode.next
      return currentNode
  # 10、根據下標修改節點的值
  def modifyByIndex(self,index,num):
    currentNode = self.header
    if index<=0 or index>self.length:
      print("你輸入的下標不對,請重新輸入\n")
    else:
      for i in range(index-1):
        currentNode = currentNode.next
      currentNode.element = num
def main():
  # 創建一個節點對象
  node1 = Node(1)
  # 創建一個單鏈表對象
  single_link_list = SingleLinkList()
  print("驗證空鏈表的遍歷")
  single_link_list.travel()
  print("驗證頭插")
  single_link_list.add(node1)
  single_link_list.travel()
  print("驗證尾插")
  node2 = Node(2)
  single_link_list.appent(node2)
  single_link_list.travel()
  print("驗證按位置插入")
  node3 = Node(3)
  single_link_list.insert(node3,1)
  single_link_list.travel()
  print("繼續驗證頭插")
  node4 = Node(5)
  single_link_list.add(node4)
  single_link_list.travel()
  print("繼續驗證按位置插入")
  node5 = Node(4)
  single_link_list.insert(node5,4)
  single_link_list.travel()
  print("驗證刪除")
  single_link_list.remove(3)
  single_link_list.travel()
  print("驗證查找一個節點是否在鏈表中")
  single_link_list.isContain(8)
  print("驗證按下標查找節點")
  node = single_link_list.searchNodeByIndex(2)
  print("第二個節點的值為:%s"%node.element)
  print("\n驗證排序")
  single_link_list.list_sort()
  single_link_list.travel()
  print("驗證修改")
  single_link_list.modifyByIndex(2,10)
  single_link_list.travel()
if __name__ == '__main__':
  main()
          

運行結果為:

驗證空鏈表的遍歷
你要遍歷的鏈表沒有數據

驗證頭插
你要遍歷的鏈表里面的元素有: 1?

驗證尾插
你要遍歷的鏈表里面的元素有: 1? 2?

驗證按位置插入
你要遍歷的鏈表里面的元素有: 3? 1? 2?

繼續驗證頭插
你要遍歷的鏈表里面的元素有: 5? 3? 1? 2?

繼續驗證按位置插入
你要遍歷的鏈表里面的元素有: 5? 3? 1? 4? 2?

驗證刪除
你要遍歷的鏈表里面的元素有: 5? 3? 4? 2?

驗證查找一個節點是否在鏈表中
8不在鏈表中

驗證按下標查找節點
第二個節點的值為:3

驗證排序
你要遍歷的鏈表里面的元素有: 2? 3? 4? 5?

驗證修改
你要遍歷的鏈表里面的元素有: 2? 10? 4? 5?

六、單鏈表的C語言代碼實現

            
#include 
            
              
typedef struct N
{
  int element;
  struct N *next;
}Node;
// 1、創建節點
Node *createNode(int num)
{
  Node *node;
  node = (Node *)malloc(sizeof(Node));
  node->element = num;
  node->next = NULL;
  return node;
}
// 2、創建鏈表
Node *createSingleLinkList(Node *node)
{
  Node *head = node;
  return head;
}
// 3、獲取鏈表長度
int getlength(Node *head)
{
  if (head == NULL)
  {
    return 0;
  }
  int count = 1;
  Node *current = head;
  while (current->next != NULL)
  {
    count++;
    current = current->next;
  }
  return count;
}
// 4、頭部插入
Node * add(Node *head, Node *node)
{
  if(head == NULL)
  {
    head = node;
    return head;
  }
  else
  {
    node->next = head;
    head = node;
    return head;
  }
}
// 5、尾部插入
Node * append(Node *head,Node *node)
{
  Node *current = head;
  if (current->next == NULL)
  {
    add(head, node);
  }
  else
  {
    int len = getlength(head);
    for (int i = 0; i
              
                next;
    }
    current->next = node;
  }
  return head;
}
// 6、按下標插入節點
Node * insert(Node *head,Node *node,int index)
{
  int len = getlength(head);
  if (index<=0||index>len+1)
  {
    printf("你要插入的位置不對,請重現選擇位置");
  }
  Node *current = head;
  if (index == 1)
  {
    head = add(head, node);
  }
  else if (index == 2)
  {
    node->next = head->next;
    head->next = node;
  }
  else
  {
    for (int i = 1; i
                
                  next;
    }
    node->next = current->next;
    current->next = node;
  }
  return head;
}
// 7、遍歷
void travel(Node *head)
{
  int len = getlength(head);
  printf("len = %d\n",len);
  Node *current = head;
  if (len == 0)
  {
    printf("你要遍歷的鏈表沒有數據\n");
  }
  else
  {
    printf("你要遍歷的鏈表里面的元素有: ");
    for (int i = 0; i
                  
                    element);
      current = current->next;
    }
    printf("\n");
  }
}
// 8、根據索引刪除
Node * delect(Node *head,int index)
{
  int len = getlength(head);
  if (index<=0||index>len)
  {
    printf("你輸入的下標不對,請重新輸入");
    return head;
  }
  else
  {
    if (index == 1)
    {
      head = head->next;
    }
    else if (index == 2)
    {
      head->next = head->next->next;
    }
    else
    {
      Node *current = head;
      for (int i = 1; i
                    
                      next;
      }
      current->next = current->next->next;
    }
  }
  return head;
}
// 9、查找是否包含,并返回下標
void isContain(Node *head,int num)
{
  int contain = 0;
  Node *current = head;
  int len = getlength(head);
  for (int i = 0; i
                      
                        element == num)
    {
      printf("%d在鏈表中的%d處\n",num,i+1);
      contain = 1;
    }
    current = current->next;
  }
  if (contain == 0)
  {
     printf("%d不在鏈表中\n",num);
  }
}
// 10、根據下標找節點
Node *searchByIndex(Node *head , int index)
{
  int len = getlength(head);
  Node *current = head;
  if (index<=0||index>len)
  {
    printf("你輸入的下標不對,請重新輸入");
    return head;
  }
  else
  {
    for (int i = 0; i
                        
                          next;
    }
    return current;
  }
}
// 11、根據下標修改節點的值
void modifyByIndex(Node *head,int index,int num)
{
  int len = getlength(head);
  Node *current = head;
  if (index<=0||index>len)
  {
    printf("你輸入的下標不對,請重新輸入");
  }
  else
  {
    for (int i = 0; i
                          
                            next;
    }
    current->element = num;
  }
}
int main(int argc, const char * argv[])
{
  printf("==========1、創建節點==========\n");
  Node * node1 = createNode(1);
  printf("==========2、創建單鏈表==========\n");
  Node * head = createSingleLinkList(node1);
  travel(head);
  printf("==========3、驗證頭插==========\n");
  Node *node2 = createNode(0);
  head = add(head, node2);
  travel(head);
  Node *node3 = createNode(2);
  head = add(head, node3);
  travel(head);
  printf("==========4、驗證尾插==========\n");
  Node *node4 = createNode(4);
  head = append(head,node4);
  travel(head);
  Node *node5 = createNode(5);
  head = append(head,node5);
  travel(head);
  printf("==========5、驗證按下標插入==========\n");
  Node *node6 = createNode(6);
  head = insert(head, node6, 1);
  travel(head);
  printf("==========6、驗證按下標刪除==========\n");
  head = delect(head, 2);
  travel(head);
  printf("==========7、驗證是否包含==========\n");
  isContain(head, 8);
  printf("==========8、驗證根據下標找節點==========\n");
  Node *n = searchByIndex(head, 1);
  printf("第一個節點是%d\n",n->element);
  printf("==========9、驗證根據下標修改==========\n");
  modifyByIndex
(head, 3, 9);
                            
??? travel(head);
??? return 0;
}

運行結果為:

==========1、創建節點==========
==========2、創建單鏈表==========
len = 1
你要遍歷的鏈表里面的元素有: 1
==========3、驗證頭插==========
len = 2
你要遍歷的鏈表里面的元素有: 0 1
len = 3
你要遍歷的鏈表里面的元素有: 2 0 1
==========4、驗證尾插==========
len = 4
你要遍歷的鏈表里面的元素有: 2 0 1 4
len = 5
你要遍歷的鏈表里面的元素有: 2 0 1 4 5
==========5、驗證按下標插入==========
len = 6
你要遍歷的鏈表里面的元素有: 6 2 0 1 4 5
==========6、驗證按下標刪除==========
len = 5
你要遍歷的鏈表里面的元素有: 6 0 1 4 5
==========7、驗證是否包含==========
8不在鏈表中
==========8、驗證根據下標找節點==========
第一個節點是6
==========9、驗證根據下標修改==========
len = 5
你要遍歷的鏈表里面的元素有: 6 0 9 4 5

總結

以上所述是小編給大家介紹的python算法與數據結構之單鏈表的實現代碼 ,希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時回復大家的。在此也非常感謝大家對腳本之家網站的支持!
如果你覺得本文對你有幫助,歡迎轉載,煩請注明出處,謝謝!


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 91国高清视频| 日韩精品影视 | 国产在线精品一区二区三区 | 日日干日日操日日射 | 国产精品视频偷伦精品视频 | 日韩精品视频在线观看免费 | 黄色片网站大全 | 日产国产欧美视频一区精品 | 国产精品午夜免费福利视频 | 久草视频在线免费播放 | 一级毛片真人免费观看 | 亚洲黄色在线视频 | 亚洲美女亚洲精品久久久久 | 在线播放国产精品 | 操操干 | 天天操综| jizz孕妇孕交 | 免费一级毛片麻豆精品 | 亚洲天天在线日亚洲洲精 | 成人毛片网 | 日韩成人免费aa在线看 | 国产亚洲精品久久久久久午夜 | 91视频免费观看高清观看完整 | 欧美视频一区二区专区 | 国产成人mv在线观看入口视频 | 性欧美成人免费观看视 | 亚洲国产精品日韩在线观看 | 亚洲十欧美十日韩十国产 | 99免费在线观看视频 | 四虎网址最新 | 激情五月婷婷基地 | 四虎在线免费播放 | 国产亚洲视频在线观看 | 亚欧视频在线观看 | 久99久精品视频免费观看v | 一本影院| 国产美女拍拍拍在线观看 | 伊人一区二区三区 | 久久久久国产一级毛片高清版 | 日日干天天| 综合图区亚洲 |