算法一日一练 02

故乡的风

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

Potato丶

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

故乡的风

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

                               
登录/注册后可看大图

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

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

Potato丶

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

故乡的风

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

                               
登录/注册后可看大图

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

有序顺序表并不是链表，顺序表是线性表的顺序存储方式。你的想法没问题，采用折半查找效率最高。

Potato丶

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

                               
登录/注册后可看大图

有序顺序表并不是链表，顺序表是线性表的顺序存储方式。你的想法没问题，采用折半查找效率最高。

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

四季如春へ★

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

const int MAXSIZE=10000;
struct node
{
        int data,pre,nxt;//节点的值，前驱，后缀
}a[MAXSIZE];
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[low].data==x)
        {
                find=true;
                return low;
        }
        if(a[high].data==x)
        {
                find=true;
                return high;
        }
        while(low<=high)
        {
                mid=low+((high-low)/2);
                if(a[mid].data==x)
                {
                        find=true;
                        return mid;
                }
                if(a[mid].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[i].data);
         qsort(a,n,sizeof(node),cmp);//构造有序线性表
         for(int i=0;i<n;i++)
                 printf("%d ",a[i].data);
         printf("\n");
         for(int i=0;i<n;i++)//建立双向链表
         {
                 a[i].pre=i-1;
                 a[i].nxt=i+1;
         }
         a[n-1].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[pos].pre,behind=a[pos+1].nxt;
                         a[pos].pre=pos+1;
                         a[pos].nxt=behind;
                         a[pos+1].pre=before;
                         a[pos+1].nxt=pos;
                         a[before].nxt=pos+1;
                         a[behind].pre=pos;
                         if(pos==0)
                                 head=1;
                 }
         }
         else
         {
                 a[n].data=x;  //没找到，假设这个新节点序号为n
                 if(pos!=-1)
                 {
                     a[pos].nxt=n;
                         a[n].pre=-1;
                 }
                 else
                 {
                         head=n;
                         a[n].pre=pos;
                 }
                 a[pos+1].pre=n;
                 if(pos!=n-1)
                     a[n].nxt=pos+1;
                 else
                         a[n].nxt=-1;
                 n++;
         }
         printf("操作后的数据：\n");
         int i=head;
         while(i!=-1)
         {
                 printf("%d ",a[i].data);
                 i=a[i].nxt;
         }
         printf("\n");
         return 0;
}

四季如春へ★

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

                               
登录/注册后可看大图

#include
#include
#include

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

四季如春へ★

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

                               
登录/注册后可看大图

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

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

晨风吹过

学习了啊，谢谢

蒍嗳變乖/ka

谢谢楼主分享啊

猪猪BBUn咕咕

好文章转过来方便自己看

zch463170098

,b, bn bn  bvgkhghhf

猪猪BBUn咕咕

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

jhlsp

谢谢楼主分享啊

じO-联合

观摩下看看那。。。。。

驻留的习惯

学号c需要懂多少算法？

shenyaowen

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

ywzhang2014

:hug:

疯子~

激动人
心  无法言表