|
单链表的查找运算 ()按序号查找 ① 链表不是随机存取结构 在链表中即使知道被访问结点的序号i也不能像顺序表中那样直接按序号i访问结点而只能从链表的头指针出发顺链域 next逐个结点往下搜索直至搜索到第i个结点为止因此链表不是随机存取结构 ② 查找的思想方法 计数器j置为后扫描指针p指针从链表的头结点开始顺着链扫描当p扫描下一个结点时计数器j相应地加当j=i时指针 p所指的结点就是要找的第i个结点而当p指针指为null且j≠i时则表示找不到第i个结点 注意 头结点可看做是第个结点 ③具体算法实现 ListNode* GetNode(LinkList headint i) {//在带头结点的单链表head中查找第i个结点若找到(≤i≤n) //则返回该结点的存储位置否则返回NULL int j; ListNode *p; p=head;j=;//从头结点开始扫描 while(p>next&&jnext为NULL或i=j为止 p=p>next; j++; } if(i==j) return p;//找到了第i个结点 else return NULL;//当i<或i>时找不到第i个结点 } ④算法分析 算法中while语句的终止条件是搜索到表尾或者满足j≥i其频度最多为i它和被寻找的位置有关在等概率假设下平均时间复杂度为 () 按值查找 ①思想方法 从开始结点出发顺着链逐个将结点的值和给定值key作比较若有结点的值与key相等则返回首次找到的其值为key的结点的存储 位置;否则返回NULL ②具体算法实现 ListNode* LocateNode (LinkList headDataType key) {//在带头结点的单链表head中查找其值为key的结点 ListNode *p=head>next;//从开始结点比较表非空p初始值指向开始结点 while(p&&p>data!=key)//直到p为NULL或p>data为key为止 p=p>next;//扫描下一结点 return p;//若p=NULL则查找失败否则p指向值为key的结点 } ③算法分析 该算法的执行时间亦与输入实例中key的取值相关其平均时间复杂度分析类似于按序号查找为O(n) |
