论坛 › 数据结构与算法 › 算法一日一练 02

故乡的风 发表于 2013-7-20 08:50:18

算法一日一练 02

有序递增顺序表L，设计算法在表中查找数值为x的元素，若找到与其后继交换位置（为最后一个元素则不变），若找不到将x插入表中并使顺序表仍然有序递增。
试着设计在时间及空间两方面都尽量高效的算法，并将想法及源码贴出来（语言不限，最好C/C++）。我将适量给予评分，希望大家踊跃参与。

Potato丶 发表于 2013-7-20 10:17:58

{:7_166:}找到与其后继交换位置什么意思？ 使表不再有序？

故乡的风 发表于 2013-7-20 10:44:52

Potato丶 发表于 2013-7-20 10:17 static/image/common/back.gif
找到与其后继交换位置什么意思？ 使表不再有序？

其实目的就是找到x的值，找到后和后继元素交换位置，类似标识作用；没找到就插入到其中。这个函数并没实际意义，只是实现本算法来掌握算法基础而已。

Potato丶 发表于 2013-7-20 13:07:33

{:7_174:}没学到家啊。想不出什么巧妙的法子。
本想用折中查找+链表。奈何不知道链表如何折中……

故乡的风 发表于 2013-7-20 16:58:11

本帖最后由 故乡的风 于 2013-7-20 17:00 编辑

Potato丶 发表于 2013-7-20 13:07 static/image/common/back.gif
没学到家啊。想不出什么巧妙的法子。
本想用折中查找+链表。奈何不知道链表如何折中……
有序顺序表并不是链表，顺序表是线性表的顺序存储方式。你的想法没问题，采用折半查找效率最高。

Potato丶 发表于 2013-7-20 17:24:52

故乡的风 发表于 2013-7-20 16:58 static/image/common/back.gif
有序顺序表并不是链表，顺序表是线性表的顺序存储方式。你的想法没问题，采用折半查找效率最高。

{:7_178:}哦。这样啊。但插入数据的时候怎么破。就单纯的将后面的数据分别往后移一位？

四季如春へ★ 发表于 2013-7-20 17:32:56

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;

const int MAXSIZE=10000;
struct node
{
        int data,pre,nxt;//节点的值，前驱，后缀
}a;
int cmp(const void*a,const void*b)
{
        return (*(node *)a).data>(*(node *)b).data;
}
int n;          //总节点数
bool find=false;
int search(int x)
{
        int low=0,high=n-1,mid;
        if(a.data==x)
        {
                find=true;
                return low;
        }
        if(a.data==x)
        {
                find=true;
                return high;
        }
        while(low<=high)
        {
                mid=low+((high-low)/2);
                if(a.data==x)
                {
                        find=true;
                        return mid;
                }
                if(a.data>x)
                        high=mid-1;
                else
                        low=mid+1;
        }
        if(low>high)
                return low-1;
}
int main()
{
       printf("请输入数据的个数：");
       scanf("%d",&n);
       printf("请输入数据：\n");
       for(int i=0;i<n;i++)
               scanf("%d",&a.data);
       qsort(a,n,sizeof(node),cmp);//构造有序线性表
       for(int i=0;i<n;i++)
               printf("%d ",a.data);
       printf("\n");
       for(int i=0;i<n;i++)//建立双向链表
       {
               a.pre=i-1;
               a.nxt=i+1;
       }
       a.nxt=-1;
       int x,head=0;
       printf("请输入待查找元素：");
       scanf("%d",&x);//待查找的元素
       int pos=search(x); //二分查找，如果找到则find为true，否则为false
       if(find)
       {
               if(pos!=n-1)//与后继交换，此处略麻烦
               {
                       int before=a.pre,behind=a.nxt;
                       a.pre=pos+1;
                       a.nxt=behind;
                       a.pre=before;
                       a.nxt=pos;
                       a.nxt=pos+1;
                       a.pre=pos;
                       if(pos==0)
                               head=1;
               }
       }
       else
       {
               a.data=x;//没找到，假设这个新节点序号为n
               if(pos!=-1)
               {
                     a.nxt=n;
                       a.pre=-1;
               }
               else
               {
                       head=n;
                       a.pre=pos;
               }
               a.pre=n;
               if(pos!=n-1)
                     a.nxt=pos+1;
               else
                       a.nxt=-1;
               n++;
       }
       printf("操作后的数据：\n");
       int i=head;
       while(i!=-1)
       {
               printf("%d ",a.data);
               i=a.nxt;
       }
       printf("\n");
       return 0;
}

四季如春へ★ 发表于 2013-7-20 17:36:35

四季如春へ★ 发表于 2013-7-20 17:32 static/image/common/back.gif
#include
#include
#include


我这是查找一次，用二分查找加l链表，具体看代码吧，个人测了一下应该对的~

四季如春へ★ 发表于 2013-7-20 17:38:07

Potato丶 发表于 2013-7-20 17:24 static/image/common/back.gif
哦。这样啊。但插入数据的时候怎么破。就单纯的将后面的数据分别往后移一位？

每个数据建立一个节点struct，然后移动链表指针

晨风吹过 发表于 2013-8-28 09:58:24

学习了啊，谢谢

蒍嗳變乖/ka 发表于 2013-8-29 16:36:20

谢谢楼主分享啊 {:5_107:}

猪猪BBUn咕咕 发表于 2013-11-17 10:50:48

好文章转过来方便自己看

zch463170098 发表于 2013-11-17 11:50:07

,b, bn bnbvgkhghhf

猪猪BBUn咕咕 发表于 2013-11-18 15:25:22

找到与其后继交换位置什么意思？ 使表不再有序同样不明

jhlsp 发表于 2014-3-2 16:16:02

谢谢楼主分享啊

じO-联合 发表于 2014-3-2 18:45:36

观摩下看看那。。。。。

驻留的习惯 发表于 2014-3-15 19:37:59

学号c需要懂多少算法？

shenyaowen 发表于 2014-3-15 20:56:34

好厉害啊 :shy::shy::shy::shy::shy:

ywzhang2014 发表于 2014-11-28 11:02:39

:hug:

疯子~ 发表于 2014-12-1 19:54:21

激动人
心无法言表

查看完整版本: 算法一日一练 02