#include <stdio.h>
#include <iostream>
#define MaxSize 50
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList;
void InitList(SqList& L)
{
L.length=0;
}
//求指定位置元素值的算法
int GetElem(SqList L,int i,ElemType &e)
{
if(i<1 || i>L.length) //逻辑位序
return 0;
e=L.data[i-1];
return 1;
}
//按元素值查找的算法
int LocateElem(SqList L,ElemType e)
{
int i=0;
while(i<L.length && L.data[i]!=e)i++;
if(i>=L.length)
return 0;
else
return (i+1);
}
//插入数据元素的算法
int ListInsert(SqList &L,int i,ElemType e)
{
int j;
if(i<1 || i>L.length+1) //逻辑位序
return 0;
i--;
for(j=L.length;j>i;j--)
L.data[j]=L.data[j-1];
L.data[i]=e;
L.length++;
return 1;
}
//删除数据元素的算法
int ListDelete(SqList &L,int i,ElemType &e)
{
int j;
if(i<1 || i>L.length)
return 0;
i--;
e=L.data[i];
for(j=i;j<L.length-1;j++)
L.data[j]=L.data[j+1];
L.length--;
return 1;
}
//有序表的归并算法
void Merge_SortedList(SqList L1,SqList L2,SqList& L3)
{
int i=0,j=0,k=0;
while(i<L1.length && j<L2.length)
{
if(L1.data[i]<L2.data[j])
{
L3.data[k]=L1.data[i];
i++;k++;
}
else if(L1.data[i]>L2.data[j])
{
L3.data[k]=L2.data[j];
j++;k++;
}
else
{
L3.data[k]=L1.data[i];
i++;j++;k++;
}
}
while(i<L1.length)
{
L3.data[k]=L1.data[i];
i++;k++;
}
while(j<L2.length)
{
L3.data[k]=L2.data[j];
j++;k++;
}
L3.length=k;
}
//遍历顺序表
void Traverse(SqList L)
{
printf("Traversing...: ");
for(int i=0;i<L.length;i++)
{
printf("%d ",L.data[i]);
}
printf("/n");
}
//2-2-10已知一个递增有序表(incrementing orderly table)
//,现插入x使其仍然递增
void insert_iot(SqList &L,ElemType x)
{
int i=0,j;
while(i<L.length && x>=L.data[i])
i++;
for(j=L.length-1;j>=i;j--)
L.data[j+1]=L.data[j];
L.data[i]=x;
L.length++;
}
//2-2-11设计一算法,将顺序表的所有元素逆置,要求
//算法复杂度为O(1)
void reverse(SqList &L)
{
int i;
ElemType x;
for(i=0;i<L.length/2;i++)
{
x=L.data[i];
L.data[i]=L.data[L.length-i-1];
L.data[L.length-i-1]=x;
}
}
//2-2-12设计一算法,删除所有值的x,
//要求空间复杂度O(1)
void delall(SqList& L,ElemType x)
{
int i=0,j;
//找到第一个
while(i<L.length && L.data[i]!=x)
i++;
for(j=i+1;j<L.length;j++)
if(L.data[j]!=x)
{
L.data[i]=L.data[j];
i++;
}
L.length=i;
}
//2-2-12方法二
//算法复杂度为O(n)
void delall2(SqList &L,ElemType x)
{
int i=0,k=0;
while(i<L.length)
{
if(L.data[i]==x)
k++;
else
L.data[i-k]=L.data[i];
i++;
}
L.length-=k;
}
//2-2-12 自己的方法
//算法不太好,另外将找到的结果先标记,
//再按照交换排序的方法前后交换
void delall_self(SqList &L,ElemType x)
{
int i=0,j=0;
while(i<L.length)
{
if(L.data[i]==x)
{
for(j=i;j<L.length-1;j++)
L.data[j]=L.data[j+1];
L.length--;
}
else
i++;
}
}
//2-2-13设计一算法,从给定的顺序表L中删除元素
//值在x到y(x<=y)的所有元素值,空间复杂度为O(1)
void delallxy(SqList &L,ElemType x,ElemType y)
{
int i=0,k=0;
while(i<L.length)
{
if(L.data[i]>=x && L.data[i]<=y)
k++;
else
L.data[i-k]=L.data[i];
i++;
}
L.length-=k;
}
//2-2-14有一顺序表L,其元素为整型数据,设计一算法
//将所有小于0的整数放在前半部分,大于等于0的整数
//放在后半部分
void move(SqList &L)
{
ElemType temp;
int i=0,j=L.length-1;
while(i<j)
{
while(i<j && L.data[i]<0)
i++;
while(i<j && L.data[j]>=0)
j--;
if(i<j)
{
temp=L.data[i];
L.data[i]=L.data[j];
L.data[j]=temp;
}
}
}
//2-2-15设计一算法从顺序表中删除重复的元素
//并使剩余的元素间的相对次序保持不变
void delsame(SqList &L)
{
//j记录合格的元素,
//i为指示标
//k辅助变量
int i,j,k;
if(L.length>0)
{
j=0;
for(i=1;i<L.length;i++)
{
k=0;
while(k<=j && L.data[k]!=L.data[i])
k++;
if(k>j)
{
j++;
L.data[j]=L.data[i];
}
}
L.length=j+1;
}
}
//2-2-16用顺序表表示集合,(如果有相同元素就不成立)
//设计一算法实现集合的求交集运算
void Intersection(SqList A,SqList B,SqList &C)
{
int i,j,k=0;
for(i=0;i<A.length;i++)
{
j=0;
while(j<B.length && B.data[j]!=A.data[i])
j++;
if(j<B.length)
C.data[k++]=A.data[i];
}
C.length=k;
}
//2-2-16自己的算法(主要是处理重复元素的情况)
void Intersection_self(SqList A,SqList B,SqList &C)
{
int i=0,j=0,k=0,m=0;
for(;i<A.length;i++)
{
m=0;
while(m<i)
{
if(A.data[m]==A.data[i])break;
m++;
}
if(m<i)continue;
j=0;
while(j<B.length && A.data[i]!=B.data[j])
j++;
if(A.data[i]==B.data[j])
{
C.data[k++]=A.data[i];
}
}
C.length=k;
}
//2-2-17顺序表表示集合,设计一算法实现
//集合的求并集运算
void Union(SqList A,SqList B,SqList &C)
{
int i,j,k=0;
for(i=0;i<A.length;i++)
C.data[i]=A.data[i];
C.length=A.length;
for(i=0;i<B.length;i++)
{
j=0;
while(j<A.length && B.data[i]!=A.data[j])
j++;
if(j==A.length)
C.data[C.length+k++]=B.data[i];
}
C.length+=k;
}
//2-2-17自己的算法(处理元素重复的情况)
void Union_self(SqList A,SqList B,SqList &C)
{
int i=0,k=0;
ElemType temp;
for(i=0;i<A.length+B.length-1;i++)
{
if(i<A.length)temp=A.data[i];
else temp=B.data[i-A.length+1];
for(k=0;k<C.length;k++)
{
if(temp==C.data[k])
break;
}
if(k>=C.length)
{
C.data[k]=temp;
C.length++;
}
}
}
//2-2-18顺序表表示集合,设计一合适
//的求差集运算
void Difference(SqList A,SqList B,SqList &C)
{
int i,j,k=0;
for(i=0;i<A.length;i++)
{
j=0;
while(j<B.length && B.data[j]!=A.data[i])
j++;
if(j==B.length)
C.data[k++]=A.data[i];
}
C.length=k;
}
//2-2-18自己的算法
void Difference_self(SqList A,SqList B,SqList &C)
{
int i=0,j=0,k=0,m=0;
while(i<A.length)
{
j=0;
while(j<i)
{
if(A.data[i]==A.data[j])break;
j++;
}
if(j>=i)
{
k=0;
while(k<B.length && B.data[k]!=A.data[i])
k++;
if(k>=B.length)
{
C.data[m++]=A.data[i];
}
}
i++;
}
C.length=m;
}
//2-2-19已知顺序表A、B,其中元素的个数
//分别为m,n,若表中的数据均是递增的,且
//这(m+n)个数据中没有重复的
//(1)将两表归并,存于新表C中
//时间复杂度为O(m+n)
void merge1(SqList A,SqList B,SqList &C)
{
int i=0,j=0,k=0;
while(i<A.length && j<B.length)
{
if(A.data[i]<B.data[j])
{
C.data[k]=A.data[i];
i++;k++;
}
else
{
C.data[k]=B.data[j];
j++;k++;
}
}
while(i<A.length)
{
C.data[k]=A.data[i];
i++;k++;
}
while(j<B.length)
{
C.data[k]=B.data[j];
j++;k++;
}
C.length=k;
}
//(2)如果B的大小为(m+n)个单元,是否可不利用顺序表C
//而将合成的线性表存于顺序表B中,设计此算法
//算法时间复杂度为O(m*n)
void merge2(SqList A,SqList &B)
{
int i=0,j=0,k;
while(i<A.length)
{
if(A.data[i]>B.data[B.length-1])
{
B.data[B.length]=A.data[i];
B.length++;i++;
}
else if(A.data[i]<B.data[j])
{
for(k=B.length-1;k>=j;k--)
B.data[k+1]=B.data[k];
B.data[j]=A.data[i];
B.length++;
i++;j++;
}
else j++;
}
}
//(2)self
void merge2_2(SqList A,SqList &B)
{
int i=0,j=0,k=0;
while(i<A.length)
{
while(j<B.length && A.data[i]>=B.data[j])
j++;
if(j<B.length)
{
for(k=B.length;k>j;k--)
B.data[k]=B.data[k-1];
B.data[j]=A.data[i];
B.length++;
j++;
}
i++;
}
}
//(3)设顺序表A有m+n个元素,且前m个有序
//,后n个有序,设计一个算法使整个有序
//时间复杂度为O(m*n)
void merge3(SqList &A,int m,int n)
{
int i=0,j=m,k;
ElemType tmp;
while(j<A.length && i<j)
{
if(A.data[j]>A.data[j-1])
break;
else if(A.data[j]<A.data[i])
{
tmp=A.data[j];
for(k=j-1;k>=i;k--)
A.data[k+1]=A.data[k];
A.data[i]=tmp;
i++;j++;
}
else//找合适的位置插入
i++;
}
}
//(3)self 想用交换排序,其实和插入
//排序差不多,有序的情况还是插入排
//较好
int main()
{
//std::cout<<1+1<<std::endl;
SqList l,s,total;
//初始化
InitList(l);
InitList(s);
InitList(total);
//插入
ListInsert(l,1,1);
ListInsert(l,2,1);
ListInsert(l,3,2);
ListInsert(l,4,4);
//2-2-10测试
//insert_iot(l,3);
Traverse(l);
//2-2-11测试
//reverse(l);
//printf("After reversing,the result is :/n");
//2-2-12测试
//delall(l,9);
//delall2(l,9);
//delall_self(l,9);
//printf("After deleting,the result is :/n");
//2-2-13测试
//delallxy(l,7,9);
//printf("After deleting,the result is :/n");
//2-2-14测试
//move(l);
//printf("After moving,the result is :/n");
//2-2-15测试
//delsame(l);
//printf("After deleting same elment,the result is :/n");
//2-2-16测试
//2-2-17测试
//2-2-18测试
//2-2-19测试
ListInsert(s,1,2);
ListInsert(s,2,3);
ListInsert(s,3,4);
printf("Traversing s: ");
Traverse(s);
//Intersection(l,s,total);
//Intersection_self(l,s,total);
//Union(l,s,total);
//Union_self(l,s,total);
//Difference(l,s,total);
//Difference_self(l,s,total);
//merge1(l,s,total);
//merge2(l,s);
merge2_2(l,s);
//merge3(l,2,2);
printf("Traversing total: ");
Traverse(s);
/*
//有序表的归并
ListInsert(s,1,2);
ListInsert(s,2,6);
ListInsert(s,3,6);
ListInsert(s,4,10);
Merge_SortedList(l,s,total);
printf("SqList l: ");
for(int i=0; i<l.length;i++)
printf("%d ",l.data[i]);
printf("/nSqList s: ");
for(i=0;i<s.length;i++)
printf("%d ",s.data[i]);
printf("/nSqList total: ");
for(i=0;i<total.length;i++)
printf("%d ",total.data[i]);
printf("/n");
//取元素
int get,e;
get=GetElem(l,1,e);
if(get)
printf("get first elment: %d/n",e);
else
printf("Error Get!");
//删除元素
int del;
del=ListDelete(l,2,e);
if(del)
printf("delete second elment: %d/n",e);
else
printf("Error Delete!");
//查找元素
int loc;
loc=LocateElem(l,4);
if(loc)
printf("elment 4 locates at :%d/n",loc);
else
printf("Can't Find!/n");
*/
return 0;
}