程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> C# 遞歸讀取XML菜單數據,

C# 遞歸讀取XML菜單數據,

編輯:C#入門知識

C# 遞歸讀取XML菜單數據,


在博客園注冊了有4年了,很遺憾至今仍未發表過博客,趁周末有空發表第一篇博客。小生不才,在此獻丑了!

最近在研究一些關於C#的一些技術,縱觀之前的開發項目的經驗,做系統時顯示系統菜單的功能總是喜歡把數據寫在數據庫表,然後直接讀取加載到菜單樹上顯示。

現在想把菜單數據都放在XML裡,然後遞歸讀取XML。

由於項目使用WCF,實體類使用了兩個,一個是業務邏輯層中的實體,一個是調用業務邏輯層遞歸方法後進行數據實體的轉換,XML讀取方法寫在業務邏輯層中。

思路:1.先讀取XML裡所有的菜單    2.根據用戶的權限顯示所屬用戶的菜單加載到頁面上

XML數據如下:

 1  <?xml version="1.0" encoding="utf-8"?>
 2  <ZCSoft.Net xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xsd="http://www.w3.org/2001/XMLSchema">
 3   <Applications>
 4      <Application ID ="OA" Text="OA管理系統">
 5        <Modules>
 6          <Module ID="OA_System" Text="系統管理">
 7            <Menus>
 8            <Menu ID="OA_System_UserManager" Text="人員管理" URL="System/UserManager/UserManagerList.aspx"> </Menu>
 9              <Menu ID="OA_System_RoleManager" Text="角色管理" URL="System/RoleManager/RoleManagerList.aspx"></Menu>
10              <Menu ID="OA_System_LoginLog" Text="登錄日志" URL="System/Log/LoginLogList.aspx"></Menu>
11            <Menu ID="OA_System_OperateLog" Text="操作日志" URL="System/Log/OperateLogList.aspx"></Menu>
12            </Menus>
13          </Module>
14  
15          <Module ID="OA_TargetManage" Text="目標管理">
16            <Menus>
17              <Menu ID="OA_TargetManage_TargetSetup" Text="目標設定" URL="OA/TargetManage/TargetSetupList.aspx">
18              </Menu>
19            </Menus>
20          </Module>
21        </Modules>
22      </Application>
23 </ZCSoft.Net>

 

菜單的業務邏輯實體類:

 1 public class MenuTreeSearchModel
 2     {
 3     //菜單ID
 4         public string ItemCode { get; set; }
 5 
 6     //菜單名稱
 7         public string ItemName { get; set; }
 8 
 9     //菜單顯示類型
10         public string ItemType { get; set; }
11 
12     //排序
13         public int ItemOrder { get; set; }
14 
15     //是否顯示
16         public bool Visible { get; set; }
17 
18     //菜單鏈接
19         public string ItemUrl { get; set; }
20 
21     //上級ID
22         public string ParentItem { get; set; }
23 
24     //系統平台ID
25         public string ApplicationCode { get; set; }
26 
27     //系統平台名稱
28         public string ApplicationName { get; set; }
29 
30     //模塊ID
31         public string ModuleCode { get; set; }
32 
33     //模塊名稱
34         public string ModuleName { get; set; }
35     }


遞歸方法,讀取每個模塊和模塊下的菜單:

 1  protected void GetChildMenuList(XElement root, List<MenuTreeSearchModel> menuTreeList)
 2         {
 3             var firstNode = root.FirstNode as XElement;//讀取root節點內的第一個節點
 4             if (null != firstNode)
 5             {
 6         //讀取root節點下面同級的所有節點
 7                 var appList =
 8                         from ele in root.Element(firstNode.Name.LocalName).Elements()
 9                         select ele;
10 
11                 bool thisVisible = true;//默認節點是可見的
12                 XAttribute thisAttr = root.Attribute("Display");
13                 if (null != thisAttr)//如果菜單的上級模塊有顯示屬性
14                 {
15                     string thisDisplay = thisAttr.Value;
16                     thisVisible = thisDisplay.ToLower() == "false" ? false : true;
17                 }
18 
19                 foreach (var application in appList)
20                 {
21                     //模塊Display屬性
22                     XAttribute modAttr = application.Attribute("Display");
23                     bool visible = true;
24                     if (null != modAttr)
25                     {
26                         string display = application.Attribute("Display").Value;
27                         visible = display.ToLower() == "false" ? false : true;
28                     }
29                     var nextNode = application.FirstNode as XElement;//該節點的下級節點
30                    
31                     string itemType = "Folder";//目錄還是菜單
32                     string itemUrl = null;//鏈接地址
33                     string parentItem = null;//上一節點ID
34                     string applicationCode = null;//平台編碼
35                     string applicationName = null;//平台名稱
36                     string moduleCode = null;//模塊編碼
37                     string moduleName = null;//模塊名稱
38 
39                     if (application.Name.LocalName == "Application")
40                     {
41                         applicationCode = application.Attribute("ID").Value;
42                         applicationName = application.Attribute("Text").Value;
43                     }
44 
45                     if (application.Name.LocalName == "Module")
46                     {
47                         moduleCode = application.Attribute("ID").Value;
48                         moduleName = application.Attribute("Text").Value;
49                         applicationCode = root.Attribute("ID").Value;
50                         applicationName = root.Attribute("Text").Value;
51 
52                         if (thisVisible) //如果該模塊的所屬平台中的Display屬性設置為可見true(注意:沒有設置則默認為可見),則模塊的上級為Application的ID
53                         {
54                             parentItem = root.Attribute("ID").Value;
55                         }
56                     }
57 
58                     if (application.Name.LocalName == "Menu")
59                     {
60                         itemType = "Menu";
61                         itemUrl = application.Attribute("URL").Value;
62                         moduleCode = root.Attribute("ID").Value;
63                         moduleName = root.Attribute("Text").Value;
64                         applicationCode = root.Parent.Parent.Attribute("ID").Value;
65                         applicationName = root.Parent.Parent.Attribute("Text").Value;
66 
67                         if (thisVisible) //如果該菜單的所屬模塊中的Display屬性設置為可見true(注意:沒有設置則默認為可見),則菜單的上級為Module的ID
68                         {
69                             parentItem = root.Attribute("ID").Value;
70                         }
71                         else//如果該菜單的所屬模塊中的Display屬性設置為不可見false,則菜單的上級為Application的ID
72                         {
73                             parentItem = root.Parent.Parent.Attribute("ID").Value;
74                         }
75                     }
76 
77                     MenuTreeSearchModel model = new MenuTreeSearchModel();
78                     model.ItemCode = application.Attribute("ID").Value;
79                     model.ItemName = application.Attribute("Text").Value;
80                     model.ItemType = itemType;
81                     model.ItemOrder = 0;
82                     model.Visible = visible;
83                     model.ItemUrl = itemUrl;
84                     model.ParentItem = parentItem;
85                     model.ApplicationCode = applicationCode;
86                     model.ApplicationName = applicationName;
87                     model.ModuleCode = moduleCode;
88                     model.ModuleName = moduleName;
89                     menuTreeList.Add(model);
90 
91                     if (null != nextNode)//如果還有下級節點
92                     {
93                      //調用遞歸
94                          GetChildMenuList(application, menuTreeList);
95                     }
96                 }
97             }
98         }


從XML文檔讀取:

 1 /// <summary>
 2         /// 從XML文件讀取菜單節點
 3         /// </summary>
 4         /// <returns></returns>
 5         public List<MenuTreeSearchModel> GetMenuTreeByReadXML()
 6         {
 7             List<MenuTreeSearchModel> list = new List<MenuTreeSearchModel>();
 8         //讀取XML文檔路徑,這裡我把XML放在網站的bin目錄裡
 9             string xmlPath = AppDomain.CurrentDomain.BaseDirectory + "Foundation.xml";
10             XElement root = XElement.Load(xmlPath);
11             var appList =
12                         from ele in root.Element("Applications").Elements()
13                         select ele;
14         //按系統平台篩選
15             foreach (var application in appList)
16             {
17                 MenuTreeSearchModel model = new MenuTreeSearchModel();
18                 model.ItemCode = application.Attribute("ID").Value;
19                 model.ItemName = application.Attribute("Text").Value;
20                 model.ItemType = "Folder";
21                 model.ItemOrder = 0;
22                 model.Visible = true;
23                 model.ItemUrl = null;
24                 model.ParentItem = null;
25                 model.ApplicationCode = application.Attribute("ID").Value;
26                 model.ApplicationName = application.Attribute("Text").Value;
27                 model.ModuleCode = null;
28                 model.ModuleName = null;
29                 list.Add(model);
30 
31         //遞歸調用
32                 GetChildMenuList(application, list);
33                 
34             }
35 
36             return list;
37         }


以下是在調用服務契約方法時進行的實體類:

 1 public class PublicUserMenuTreeData
 2     {  
 3 //菜單ID
 4         public string ItemCode { get; set; }
 5 
 6     //菜單名稱
 7         public string ItemName { get; set; }
 8 
 9     //菜單顯示類型
10         public string ItemType { get; set; }
11 
12     //排序
13         public int ItemOrder { get; set; }
14 
15     //是否顯示
16         public bool Visible { get; set; }
17 
18     //菜單鏈接
19         public string ItemUrl { get; set; }
20 
21     //上級ID
22         public string ParentItem { get; set; }
23 
24     //系統平台ID
25         public string ApplicationCode { get; set; }
26 
27     //系統平台名稱
28         public string ApplicationName { get; set; }
29 
30     //模塊ID
31         public string ModuleCode { get; set; }
32 
33     //模塊名稱
34         public string ModuleName { get; set; }
35     //當前菜單下的菜單集合
36     public List<PublicUserMenuTreeData> UserMenuTreeDatas { set; get; }
37     }


實體轉換方法:

 1  public PublicUserMenuTreeData TransferUserMenuTreeToPublicUserMenu(MenuTreeData userMenuTreeData)
 2         {
 3             PublicUserMenuTreeData pubUserMenuTreeData = new PublicUserMenuTreeData();
 4             pubUserMenuTreeData.ItemCode = userMenuTreeData.ItemCode;
 5             pubUserMenuTreeData.ItemName = userMenuTreeData.ItemName;
 6             pubUserMenuTreeData.ItemType = userMenuTreeData.ItemType;
 7             pubUserMenuTreeData.ItemOrder = userMenuTreeData.ItemOrder;
 8             pubUserMenuTreeData.Visible = userMenuTreeData.Visible;
 9             pubUserMenuTreeData.ItemUrl = userMenuTreeData.ItemUrl;
10             pubUserMenuTreeData.ParentItem = userMenuTreeData.ParentItem;
11             pubUserMenuTreeData.ApplicationCode = userMenuTreeData.ApplicationCode;
12             pubUserMenuTreeData.ApplicationName = userMenuTreeData.ApplicationName;
13             pubUserMenuTreeData.ModuleCode = userMenuTreeData.ModuleCode;
14             pubUserMenuTreeData.ModuleName = userMenuTreeData.ModuleName;
15             return pubUserMenuTreeData;
16         }

用戶權限菜單方法:

 1  /// <summary>
 2         /// 有用戶權限樹獲取共用的用戶菜單列表
 3         /// </summary>
 4         /// <param name="listAllUserMenu"></param>
 5         /// <returns></returns>
 6         public List<PublicUserMenuTreeData> GetPublicUserMenuFromUserMenuTreeData(List<MenuTreeData> listAllUserMenu)
 7         {
 8             List<PublicUserMenuTreeData> listPublicUserMenuTreeData = new List<PublicUserMenuTreeData>();
 9             List<MenuTreeData> list = listAllUserMenu.FindAll(d => string.IsNullOrEmpty(d.ParentItem)).ToList();
10             foreach (var userMenuTreeData in list)
11             {
12                 PublicUserMenuTreeData pubUserMenuTreeData = TransferUserMenuTreeToPublicUserMenu(userMenuTreeData);
13                 pubUserMenuTreeData.UserMenuTreeDatas = GetChildData(pubUserMenuTreeData.ItemCode, listAllUserMenu);
14                 listPublicUserMenuTreeData.Add(pubUserMenuTreeData);
15             }
16             return listPublicUserMenuTreeData;
17         }
18         public List<PublicUserMenuTreeData> GetChildData(string parentId, List<MenuTreeData> listUserMenuTreeData)
19         {
20 
21             List<MenuTreeData> list = listUserMenuTreeData.FindAll(d => d.ParentItem == parentId).ToList();
22             if (list.Count > 0)
23             {
24                 List<PublicUserMenuTreeData> listPublicUserMenuTreeData = new List<PublicUserMenuTreeData>();
25                 foreach (var userMenuTreeData in list)
26                 {
27                     PublicUserMenuTreeData pubUserMenuTreeData = TransferUserMenuTreeToPublicUserMenu(userMenuTreeData);
28                     pubUserMenuTreeData.UserMenuTreeDatas = GetChildData(pubUserMenuTreeData.ItemCode, listUserMenuTreeData);
29                     listPublicUserMenuTreeData.Add(pubUserMenuTreeData);
30                 }
31                 return listPublicUserMenuTreeData;
32             }
33             return null;
34         }

系統菜單類:

 1 /// <summary>
 2     /// 系統菜單
 3     /// </summary>
 4     [DataContract()]
 5     public class MenuTreeData 
 6     {
 7 
 8         [DataMember()]
 9         public string ItemCode { get; set; }
10 
11         [DataMember()]
12         public string ItemName { get; set; }
13 
14         [DataMember()]
15         public string ItemType { get; set; }
16 
17         [DataMember()]
18         public int ItemOrder { get; set; }
19 
20         [DataMember()]
21         public bool Visible { get; set; }
22 
23         [DataMember()]
24         public string ItemUrl { get; set; }
25 
26         [DataMember()]
27         public string ParentItem { get; set; }
28 
29         [DataMember()]
30         public string ApplicationCode { get; set; }
31 
32         [DataMember()]
33         public string ApplicationName { get; set; }
34 
35         [DataMember()]
36         public string ModuleCode { get; set; }
37 
38         [DataMember()]
39         public string ModuleName { get; set; }
40 
41     }

後台頁面加載Load代碼:

1 string menuData = string.Empty;
2  
3 var treeList= GetMenuTreeList();
4     if (treeList!= null)
5 {
6          List<MenuTreeData> listAllUserMenu = treeList.FindAll(d => d.Visible).OrderBy(d => d.ItemOrder).ToList();
7          List<PublicUserMenuTreeData> listPublicUserMenuTreeData = GetPublicUserMenuFromUserMenuTreeData(listAllUserMenu);
8           menuData = JsonConvert.SerializeObject(listPublicUserMenuTreeData);
9 }


頁面加載腳本,這裡使用Jquery:

 1 var obj = menuData;
 2 GetMenuInfo(obj);
 3  function GetMenuInfo(obj) {
 4             var str = "";
 5            
 6             var objInfo = "";
 7             if (obj) {
 8                 objInfo = obj.split("|");
 9                 if (objInfo[0] != "") {
10                     var PublicUserMenuTreeData = JSON.parse(objInfo[0]);
11                     for (var i = 0; i < PublicUserMenuTreeData.length; i++) {
12                         str += ("<li>");
13                         var tempmenu= PublicUserMenuTreeData[i];
14                         if (tempmenu.ItemType && tempmenu.ItemType == "Menu") {
15                             str += ("<a href='#' onclick='" + tempmenu.ItemCode + "()' id='" + tempmenu.ItemCode + "'>" + tempmenu.ItemName + "</a>");
16                             str += ("<script> function " + tempmenu.ItemCode);
17                             str += ("() { tabframe1.newTab({ title: '" + tempmenu.ItemName + "',");
18                             if (tempmenu.ItemUrl.indexOf('?') != -1) {
19                                 str += ("src: '" + tempmenu.ItemUrl + "&applicationid=" + tempmenu.ApplicationCode + "&moduleid=" + tempmenu.ModuleCode + "',");
20                             } else {
21                                 str += ("src: '" + tempmenu.ItemUrl + "?applicationid=" + tempmenu.ApplicationCode + "&moduleid=" + tempmenu.ModuleCode + "',");
22                             }
23 
24                             str += ("  id: 'oa-system-" + tempmenu.ItemCode + "',");
25                             str += ("  closable: true  }); jQuery('#mainmenulist').hide();  return false; }<\/script>");
26                         } else {
27                             str += ("<a href='#' id='" + PublicUserMenuTreeData[i].ItemCode + "'>" + PublicUserMenuTreeData[i].ItemName + "</a>");
28                         }
29 
30                         if (PublicUserMenuTreeData[i].UserMenuTreeDatas) {
31                             str += GetRecurrenceData(PublicUserMenuTreeData[i].UserMenuTreeDatas);
32                         }
33 
34                         str += (" </li>");
35                     }
36 
37 
38                 }
39             }
40 
41 function GetRecurrenceData(listPublicUserMenuTreeData) {
42             var str = "";
43             if (listPublicUserMenuTreeData && listPublicUserMenuTreeData.length>0) {
44                 str += (" <ul>");
45                 for (var j = 0; j < listPublicUserMenuTreeData.length; j++) {
46                     str += ("<li class='divFontWeight'>");
47                     if (listPublicUserMenuTreeData[j].ItemType && listPublicUserMenuTreeData[j].ItemType == "Menu") {
48                         str += ("<a href='#' onclick='" + listPublicUserMenuTreeData[j].ItemCode + "()' id='" + listPublicUserMenuTreeData[j].ItemCode + "'>" + listPublicUserMenuTreeData[j].ItemName + "</a>");
49                         str += ("<script> function " + listPublicUserMenuTreeData[j].ItemCode);
50                         str += ("() { tabframe1.newTab({ title: '" + listPublicUserMenuTreeData[j].ItemName + "',");
51                         if (listPublicUserMenuTreeData[j].ItemUrl.indexOf('?') != -1) {
52                             str += ("src: '" + listPublicUserMenuTreeData[j].ItemUrl + "&applicationid=" + listPublicUserMenuTreeData[j].ApplicationCode + "&moduleid=" + listPublicUserMenuTreeData[j].ModuleCode + "',");
53                         } else {
54                             str += ("src: '" + listPublicUserMenuTreeData[j].ItemUrl + "?applicationid=" + listPublicUserMenuTreeData[j].ApplicationCode + "&moduleid=" + listPublicUserMenuTreeData[j].ModuleCode + "',");
55                         }
56 
57                         str += ("  id: 'oa-system-" + listPublicUserMenuTreeData[j].ItemCode + "',");
58                         str += ("  closable: true  }); jQuery('#mainmenulist').hide();  return false; }<\/script>");
59                     } else {
60                         str += ("<a href='#' id='" + listPublicUserMenuTreeData[j].ItemCode + "'>" + listPublicUserMenuTreeData[j].ItemName + "</a>");
61                     }
62 
63 
64                     var ListMenuDatas = listPublicUserMenuTreeData[j].UserMenuTreeDatas;
65                     str += GetRecurrenceData(ListMenuDatas);
66 
67                     str += ("</li>");
68                 }
69                 str += (" </ul>");
70             }
71             return str;
72         }

效果圖:

 這裡補充一下:菜單中如果在模塊Module裡設置屬性Display="false",則模塊不顯示出來,可是模塊下的菜單可顯示出來。

itemType=“Folder”顯示類型是目錄,itemType=“Menu”顯示類型是菜單


一個C語言冒泡排序法的簡單程序

main()
{
int i,j,temp;
int a[10];
for(i=0;i<10;i++)
scanf ("%d,",&a[i]);
for(j=0;j<=9;j++)
{ for (i=0;i<10-j;i++)
if (a[i]>a[i+1])
{ temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;}
}
for(i=1;i<11;i++)
printf("%5d,",a[i] );
printf("\n");
}

--------------
冒泡算法
冒泡排序的算法分析與改進
交換排序的基本思想是:兩兩比較待排序記錄的關鍵字,發現兩個記錄的次序相反時即進行交換,直到沒有反序的記錄為止。
應用交換排序基本思想的主要排序方法有:冒泡排序和快速排序。

冒泡排序

1、排序方法
將被排序的記錄數組R[1..n]垂直排列,每個記錄R看作是重量為R.key的氣泡。根據輕氣泡不能在重氣泡之下的原則,從下往上掃描數組R:凡掃描到違反本原則的輕氣泡,就使其向上"飄浮"。如此反復進行,直到最後任何兩個氣泡都是輕者在上,重者在下為止。
(1)初始
R[1..n]為無序區。

(2)第一趟掃描
從無序區底部向上依次比較相鄰的兩個氣泡的重量,若發現輕者在下、重者在上,則交換二者的位置。即依次比較(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);對於每對氣泡(R[j+1],R[j]),若R[j+1].key<R[j].key,則交換R[j+1]和R[j]的內容。
第一趟掃描完畢時,"最輕"的氣泡就飄浮到該區間的頂部,即關鍵字最小的記錄被放在最高位置R[1]上。

(3)第二趟掃描
掃描R[2..n]。掃描完畢時,"次輕"的氣泡飄浮到R[2]的位置上……
最後,經過n-1 趟掃描可得到有序區R[1..n]
注意:
第i趟掃描時,R[1..i-1]和R[i..n]分別為當前的有序區和無序區。掃描仍是從無序區底部向上直至該區頂部。掃描完畢時,該區中最輕氣泡飄浮到頂部位置R上,結果是R[1..i]變為新的有序區。

2、冒泡排序過程示例
對關鍵字序列為49 38 65 97 76 13 27 49的文件進行冒泡排序的過程

3、排序算法
(1)分析
因為每一趟排序都使有序區增加了一個氣泡,在經過n-1趟排序之後,有序區中就有n-1個氣泡,而無序區中氣泡的重量總是大於等於有序區中氣泡的重量,所以整個冒泡排序過程至多需要進行n-1趟排序。
若在某一趟排序中未發現氣泡位置的交換,則說明待排序的無序區中所有氣泡均滿足輕者在上,重者在下的原則,因此,冒泡排序過程可在此趟排序後終止。為此,在下面給出的算法中,引入一個布爾量exchange,在每趟排序開始前,先將其置為FALSE。若排序過程中發生了交換,則將其置為TRUE。各趟排序結束時檢查exchange,若未曾發生過交換則終止算法,不再進行下一趟排序。

(2)具體算法
void BubbleSort(SeqList R)
{ //R(l..n)是待排序的文件,采用自下向上掃描,對R做冒泡排序
int i,j;
Boolean exchange; //交換標志
for(i=1;i&......余下全文>>
 

一個C語言冒泡排序法的簡單程序

main()
{
int i,j,temp;
int a[10];
for(i=0;i<10;i++)
scanf ("%d,",&a[i]);
for(j=0;j<=9;j++)
{ for (i=0;i<10-j;i++)
if (a[i]>a[i+1])
{ temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;}
}
for(i=1;i<11;i++)
printf("%5d,",a[i] );
printf("\n");
}

--------------
冒泡算法
冒泡排序的算法分析與改進
交換排序的基本思想是:兩兩比較待排序記錄的關鍵字,發現兩個記錄的次序相反時即進行交換,直到沒有反序的記錄為止。
應用交換排序基本思想的主要排序方法有:冒泡排序和快速排序。

冒泡排序

1、排序方法
將被排序的記錄數組R[1..n]垂直排列,每個記錄R看作是重量為R.key的氣泡。根據輕氣泡不能在重氣泡之下的原則,從下往上掃描數組R:凡掃描到違反本原則的輕氣泡,就使其向上"飄浮"。如此反復進行,直到最後任何兩個氣泡都是輕者在上,重者在下為止。
(1)初始
R[1..n]為無序區。

(2)第一趟掃描
從無序區底部向上依次比較相鄰的兩個氣泡的重量,若發現輕者在下、重者在上,則交換二者的位置。即依次比較(R[n],R[n-1]),(R[n-1],R[n-2]),…,(R[2],R[1]);對於每對氣泡(R[j+1],R[j]),若R[j+1].key<R[j].key,則交換R[j+1]和R[j]的內容。
第一趟掃描完畢時,"最輕"的氣泡就飄浮到該區間的頂部,即關鍵字最小的記錄被放在最高位置R[1]上。

(3)第二趟掃描
掃描R[2..n]。掃描完畢時,"次輕"的氣泡飄浮到R[2]的位置上……
最後,經過n-1 趟掃描可得到有序區R[1..n]
注意:
第i趟掃描時,R[1..i-1]和R[i..n]分別為當前的有序區和無序區。掃描仍是從無序區底部向上直至該區頂部。掃描完畢時,該區中最輕氣泡飄浮到頂部位置R上,結果是R[1..i]變為新的有序區。

2、冒泡排序過程示例
對關鍵字序列為49 38 65 97 76 13 27 49的文件進行冒泡排序的過程

3、排序算法
(1)分析
因為每一趟排序都使有序區增加了一個氣泡,在經過n-1趟排序之後,有序區中就有n-1個氣泡,而無序區中氣泡的重量總是大於等於有序區中氣泡的重量,所以整個冒泡排序過程至多需要進行n-1趟排序。
若在某一趟排序中未發現氣泡位置的交換,則說明待排序的無序區中所有氣泡均滿足輕者在上,重者在下的原則,因此,冒泡排序過程可在此趟排序後終止。為此,在下面給出的算法中,引入一個布爾量exchange,在每趟排序開始前,先將其置為FALSE。若排序過程中發生了交換,則將其置為TRUE。各趟排序結束時檢查exchange,若未曾發生過交換則終止算法,不再進行下一趟排序。

(2)具體算法
void BubbleSort(SeqList R)
{ //R(l..n)是待排序的文件,采用自下向上掃描,對R做冒泡排序
int i,j;
Boolean exchange; //交換標志
for(i=1;i&......余下全文>>
 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved