注册 登录
编程论坛 数据结构与算法

删除顺序表中值在S与T之间(S和T的大小关系任意)的所有元素,要求该算法的时间复杂度为O(n),若S和T不合理或顺序表位空则显示错误信息。

h2363752280 发布于 2013-01-04 23:50, 2310 次点击
删除顺序表中值在S与T之间(S和T的大小关系任意)的所有元素,要求该算法的时间复杂度为O(n),若S和T不合理或顺序表位空则显示错误信息。
顺序表的排序,要求该算法的时间复杂度为O(n㏒2n),然后调用函数输出处理之后的顺序表
#include <stdio.h>
#define N 10
#define size 10
typedef struct
{
    int s[N];
    int size;
}A;
void Delete(A *L,int s[],int t,int d)//t为要删除的数的位置
{
    int i;
    for(i=t;i<N;i++)
    {
        s[i-1]=s[i];
        L.size--;
        
    }
   
}
int main(void)
{
    A *L
    int s[N];
    int i,t,d;
    for(i=0;i<N;i++)
    {
        scanf("%d",&s[i]);
    }
    printf("请输入要删除元素的位置:\n");
    scanf("%d%d",&t,&d);
    Delete(L,s,t,d);
    for(i=0;i<N-d+t+1;i++)
    {
        printf("%d ",s[i]);
    }
    printf("\n");
    return 0;
}
求修改
12 回复
#2
yaobao2013-01-05 13:01
貌似楼主删除的是位置在S,T之间的,而不是值在S,T 之间的啊
就算删除位置在S,T之间的貌似也不对啊,楼主的
   for(i=t;i<N;i++)
    {
        s[i-1]=s[i];
        L.size--;
        
    }
代码只是向前挪了一下

我也刚学数据结构,瞎说的
#3
不玩虚的2013-01-05 14:00
数组实现的顺序表是没有办法删除的,可以找到那个元素,把那个元素赋为其他值,输出的时候判断下是否为你赋的那个值,不是再输出。
#4
不玩虚的2013-01-05 16:51
#include <iostream>
using namespace std;
typedef struct A
{    int c;
}A;
void Delete1(A *a,int n,int s,int t)
{    if(s<t&&(t<0||s>n))
    cout<<"删除位置不对:"<<endl;
    else
    {if(s>=t&&(t>n||s<0))
        cout<<"删除位置不对:"<<endl;
    }
    for(int i=0;i<n;i++)
    {if(s<t)
        {
        if(i<=t-1&&i>=s-1)
        a[i].c='#';
        }
    else   
    {if(i>=t-1&&i<=s-1)
        a[i].c='#';
    }
    }
}
void display(A *a,int n)
{for(int i=0;i<n;i++)
    {if(a[i].c!='#')
        cout<<a[i].c<<"  ";
    }
cout<<endl;
}
void Swap(A *array,int a,int b)
{    A temp;
    temp=array[a];
    array[a]=array[b];
    array[b]=temp;
}

void ShellSort(A *array,int n)
{   
    for(int delta=n/2;delta>0;delta/=2)
        for(int j=0;j<delta;j++)
        {for(int i=delta;i<n;i+=delta)
                for(int j=i;j>=delta;j-=delta)
            {if(array[j].c<array[j-delta].c)
             Swap(array,j,j-delta);

               
            }
        }
}

int main()
{    A *a;
    int n,i,s,t;
    cout<<"输入顺序表的长度n:"<<endl;
        cin>>n;
        a=new A [n];
        cout<<"输入顺序表的元素:"<<endl;
    for(i=0;i<n;i++)
        cin>>a[i].c;
        ShellSort(a,n);
        display(a,n);
cout<<"输入要删除s到t之间的所有元素:"<<endl;
        cin>>s>>t;
        Delete1(a,n,s,t);
        display(a,n);
   
    return 0;
}//楼主参考下
#5
h23637522802013-01-05 17:50
把结构体改成这样可以删除吗,求代码,
typedef struct
{
    int *s;
    int MAXLenth;//最大个数
    int    Lenth;//当前长度
}A;
thank you不玩虚的代码,这个之前我写过了,但是老师说不可以这么做,要用动态数组就可以
#6
不玩虚的2013-01-05 20:11
#include <stdio.h>
#define N 10
#define asize 10
typedef struct A
{    int s[N];
    int size;//结构体变量不能在定义时赋初值
}A;//结构体A是顺序表,size是表的长度,数组s的元素是表的元素
void Create(A *L)//创建顺序表
{   
    L->size=asize;
   
    for(int i=1;i<=L->size;i++)
    {
         scanf("%d",&L->s[i]);
    }
     
}
void Delete(A *L,int t)//删除表t位置的元素
{    if(t<0||t>L->size)
  printf("%d ","没有这个元素");
    else
    {for(int j=t+1;j<=L->size;j++)
        L->s[j-1]=L->s[j];
        L->size--;
    }
}
void Display(A *L)
{
   
      for( int i=1;i<=L->size;i++)
          printf("%d ",L->s[i]);
}
int main()
{    A L;
    int t;
    Create(&L);
    printf("输入删除位置t:");
      scanf("%d",&t);
    Delete(&L,t);
    Display(&L);

   
   
    return 0;
}//这个我帮你改了,楼主参考,你的说的那个可以的
#7
不玩虚的2013-01-05 20:50
#include <stdio.h>
#define Max 100
typedef struct A
{    int *s;
    int MAXLenth;
    int Lenth;
}A;
void Create(A *L,int n)
{  L->MAXLenth=Max;
   
    L->Lenth=n;
    L->s=new int [n];
    for(int i=1;i<=L->Lenth;i++)
    {
         scanf("%d",&L->s[i]);
    }
     
}
void Delete(A *L,int t)//删除表t位置的元素
{    if(t<0||t>L->Lenth||t>L->MAXLenth)
  printf("%d ","没有这个元素");
    else
    {for(int j=t+1;j<=L->Lenth;j++)
        L->s[j-1]=L->s[j];
        L->Lenth--;
    }
}
void Display(A *L)
{
   
      for( int i=1;i<=L->Lenth;i++)
          printf("%d ",L->s[i]);
}
int main()
{    A L;
    int t,n;
 printf("顺序表的长度n:");
    scanf("%d",&n);
printf("顺序表的元素:");
    Create(&L,n);
    printf("输入删除位置t:");
      scanf("%d",&t);
    Delete(&L,t);
    Display(&L);

   
   
    return 0;
}//楼主是这样的不,你参考。还有楼主你不要介意,我在三楼说的话啦,那是我贰了。我数据结构没学好,如果你们学的话教教我。排序可以用4楼的模板,希尔排序,时间复杂度应该是nlongn,删除s到t的元素,你想想,有问题载讨论。
#8
h23637522802013-01-05 23:49
删除顺序表中值在S与T之间(S和T的大小关系任意)的所有元素,要求该算法的时间复杂度为O(n),若S和T不合理或顺序表位空则显示错误信息。
怎样删除s到t之间的数尼,
void Delete(A *L,int t)//这里只删除表t位置的
{    if(t<0||t>L->Lenth||t>L->MAXLenth)
  printf("%d ","没有这个元素");
    else
    {for(int j=t+1;j<=L->Lenth;j++)
        L->s[j-1]=L->s[j];
        L->Lenth--;
    }
}
#9
不玩虚的2013-01-06 13:14
表示c语言的加减乘除不会啊。void Delete(A *L,int s,int t)//这里只删除表t位置的假设s<t
{    int c;
    c=t-s+1;
    L->Lenth=L->Lenth-c;
 printf("%d ",L->Lenth);

}//它居然算不对啊,真的没辙。思想我都给你想好了,
/*从t+1开始到L->Lenth的每个元素向前移t-s+1个位置,L->Lenth=L->Lenth-(t-s+1);这样的话刚好是O(n)。或者你将就那个删除函数,从s开始一个一个的删,删到t就可以啦,这样的话是O(n^2),还有你说的时间复杂度是删一个元素的时间复杂度吧!
*/
#10
不玩虚的2013-01-06 17:01
#include <iostream>
#include <iomanip>
using namespace std;
#define Max 100
typedef struct A
{    int *s;
    int MAXLenth;
    int Lenth;
}A;
void Create(A *L,int n)
{  L->MAXLenth=Max;
   
    L->Lenth=n;

    L->s=new int [n];
    for(int i=1;i<=L->Lenth;i++)
    {
         cin>>L->s[i];
    }
     
}
void Delete(A *L,int t)//删除表t位置的元素
{    if(t<0||t>L->Lenth||t>L->MAXLenth)
  cout<<"没有这个位置"<<endl;
    else
    {for(int j=t+1;j<=L->Lenth;j++)
        L->s[j-1]=L->s[j];
        L->Lenth--;
    }
}
void Delete1(A *L,int s,int t)
{ int c;
    c=t-s+1;
    for(int j=s+c;j<=L->Lenth;j++)
        L->s[j-c]=L->s[j];
        L->Lenth=L->Lenth-c;
   
}
int  Length(A *L)
{return (L->Lenth);
}
void Display(A *L)
{    cout<<"顺序表为:"<<endl;
      for( int i=1;i<=L->Lenth;i++)
          cout<<L->s[i]<<setw(4);
}
int main()
{    A L;
    int t,n,s,c=0;
cout<<"顺序表的长度n:"<<endl;
    cin>>n;
cout<<"顺序表的元素:"<<endl;
    Create(&L,n);
    cout<<"输入删除s到t之间的所有元素的位置s和t:"<<endl;
     cin>>s>>t;
    Delete1(&L,s,t);
    Display(&L);

   
   
    return 0;
}//楼主你参考,这个是O(n)的,你自己做,s,t越不越界的处理
#11
h23637522802013-01-06 17:11
这个是java的语法吧L->s=new int [n];
#12
不玩虚的2013-01-06 19:18
这是c++的,至于是不是java的呢,我就不知道了。一般  类型 *变量表示定义了一个这种类型的指针,类型 **变量定义了指向指针的的指针,变量=new 类型 [常量],变量=new 类型 *[变量]。举个例子吧,
float *a,**b,n;//如果你想动态的定义一维,二维数组可以这么用,其他情况就当指针用就可以啦
cin>>n;
a=new float [n];
b=new float *[n];
for(int i=0;i<n;i++)
b[i]=new float [n];
#13
不玩虚的2013-01-06 19:23
对了,你们学到图和树那传授下你们老师讲课的精髓啊,我逃了好多课,结果数据结构黑了。还得慢慢学啊,一年半不学习就是悲剧了,都不知道自己还是不是个学生啊
1