09年自考《數據結構》各章要點一[4]

　　單鏈表運算

　　·建立單鏈表

　　·頭插法s>next=head;head=s;生成的順序與輸入順序相反平均時間復雜度均為O(n)

　　·尾插法head=rear=null;if(head=null) head=s;else r>next=s;r=s; 平均時間復雜度均為O(n)

　　·加頭結點的算法對開始結點的操作無需特殊處理統一了空表和非空表

　　·查找

　　·按序號與查找位置有關平均時間復雜度均為O(n)

　　·按值與輸入實例有關平均時間復雜度均為O(n)

　　·插入運算p=GetNode(Li);s>next=p>next;p>next=s;平均時間復雜度均為O(n)

　　·刪除運算p=GetNode(Li);r=p>next;p>next=r>next;free(r);平均時間復雜度均為O(n)

　　單循環鏈表是一種首尾相接的單鏈表終端結點的指針域指向開始結點或頭結點鏈表終止條件是以指針等於頭指針或尾指針

　　采用單循環鏈表在實用中多采用尾指針表示單循環鏈表優點是查找頭指針和尾指針的時間都是O()不用遍歷整個鏈表

　　雙鏈表就是雙向鏈表就是在單鏈表的每個結點裡再增加一個指向其直接前趨的指針域prior形成兩條不同方向的鏈由頭指針head惟一確定

　　雙鏈表也可以頭尾相鏈接構成雙(向)循環鏈表

　　雙鏈表上的插入和刪除時間復雜度均為O ()

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/22844.html