DATA STRUCTURES 顺序表的搜索算法 template <class Type> int Seg list<Type>: Search type &i x ) const 搜索函数:在表中从前向后顺序查找x int i=o: while(i<-=last &&e datai=x) + if (i> last)return-I else return i Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES template <class Type> int SeqList<Type>::Search ( Type & x ) const { //搜索函数：在表中从前向后顺序查找 x int i = 0; while ( i <= last && data[i] != x ) i++; if ( i > last ) return -1; else return i; } 顺序表的搜索算法
DATA STRUCTURES 顺序表的查找、插入和删除 查找: int search(Type&x) 主要思想: (1)从表的第一个数据元素起,依次 和x进行比较,若存在某个表项的值和x相 等,则查找成功,并返回该表项的位置。 (2)如果查遍整个顺序表,都没有找 到其值和x相等的表项,则查找不成功, 并返回-1。 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 顺序表的查找、插入和删除 ◼ 查找： int Search ( Type & x ) 主要思想： （1）从表的第一个数据元素起，依次 和x进行比较，若存在某个表项的值和x相 等，则查找成功，并返回该表项的位置。 （2）如果查遍整个顺序表，都没有找 到其值和x相等的表项，则查找不成功， 并返回-1
DATA STRUCTURES last ast data 34571648 2534571648109 x x 25 57164809 2534|57164809 253457164809 253457161 2534|57 16I 4809 2513457164809 253457164809 253457164809 2534571648 l09 x=48 x=50 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES x = 50 x =48
DATA STRUCTURES 查找算法分析: 最好:1 最坏:n 相等概率 平均: ACN=∑(i+1)=(1+2+…+m) n i=0 1(1+n)*n1+n O(n) Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES 查找算法分析： ➢最好： ➢最坏： ➢平均： 2 1 2 1 (1 ) (1 2 ) 1 ( 1) 1 = 1 0 n n n n n n i n ACN n i + = + = + = + + + = − = 1 n * O(n) 相等概率
DATA STRUCTURES n插入: int Insert(Type&x,inti) 01234567 da2534516180963 插入x150 0123 567 data253457501648|09|63 Department of Computer Science Technology, Nanjing University fall
Department of Computer Science & Technology, Nanjing University fall DATA STRUCTURES ◼ 插入： int Insert ( Type & x, int i ) 25 34 57 16 48 09 63 0 1 2 3 4 5 6 7 data 插入 x 50 25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7 data 50 i