算法一日一练 02

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

有序递增顺序表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

登录/注册后可看大图

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

其实目的就是找到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

登录/注册后可看大图

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

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

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

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

登录/注册后可看大图

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

{: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[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:36:35

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

登录/注册后可看大图

#include
#include
#include

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

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

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

登录/注册后可看大图

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

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

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

学习了啊，谢谢

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

谢谢楼主分享啊

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

好文章转过来方便自己看

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

,b, bn bn bvgkhghhf

猪猪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

马上注册，结交更多好友，享用更多功能^_^

评分

评分