熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

數據結構考研分類復習真題 第二章 答案[45]

2013-11-15 15:23:03  來源: 數據結構 

  .[題目分析] 將一個結點數據域為字符的單鏈表分解成含有字母字符數字字符和其它字符的三個循環鏈表首先要構造分別含有這三類字符的表頭結點然後從原鏈表第一個結點開始根據結點數據域是字母字符數字字符和其它字符而分別插入到三個鏈表之一的鏈表注意不要因結點插入新建鏈表而使原鏈表斷鏈另外題目並未要求鏈表有序插入采用前插法每次插入的結點均成為所插入鏈表的第一元素的結點即可

  void  OneToThree(LinkedList Llaldlo)∥L是無頭結點的單鏈表第一個結點的指針鏈表中的數據域存放字符本算法將鏈表L分解成含有英文字母字符數字字符和其它字符的帶頭結點的三個循環鏈表
  {la=(LinkedList)malloc(sizeof(LNode));∥建立三個鏈表的頭結點
  ld=(LinkedList)malloc(sizeof(LNode));
  lo=(LinkedList)malloc(sizeof(LNode));
  la>next=la;ld>next=ld;lo>next=lo;∥置三個循環鏈表為空表
  while(L!=null)∥分解原鏈表
  {r=L; L=L>next;  ∥L指向待處理結點的後繼
  if(r>data>=a&& r>data<=z|| r>data>=A&& r>data<=Z)
  {r>next=la>next;  la>next=r;}∥處理字母字符
  else if(r>data>=&& r>data<=)
  {r>next=ld>next;ld>next=r;}∥處理數字字符
  else {r>next=lo>next;lo>next=r;}∥處理其它符號
  }∥結束while(L!=null)
  }∥算法結束

  [算法討論] 算法中對L鏈表中每個結點只處理一次時間復雜度O(n)只增加了必須的三個表頭結點符合題目用最少的時間和最少的空間的要求

[]  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  []  


From:http://tw.wingwit.com/Article/program/sjjg/201311/23327.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.