1-线性表顺序存储

仅供学习记录参考

如果有人觉得我的代码能帮到的话也很好

有问题可以随时提问！

2017/7/11

1、顺序存储线性表基本功能的实现

  1 #include<iostream>
  2 #include<cstdlib>
  3 using namespace std;
  4 #define ture 1
  5 #define false 0
  6 #define maxsize 50
  7 #define listincreament 10
  8 #define ok 1
  9 #define error -3
 10 #define overflow -2
 11 typedef int Status;
 12 typedef int ElemType;
 13 
 14 typedef struct{
 15 ElemType *data;
 16 int length;
 17 int listsize;
 18 }SqList;
 19 
 20 Status initList_Sq(SqList &L)
 21 {
 22     L.data=(ElemType *)malloc(maxsize*sizeof(ElemType));
 23     L.length=0;
 24     L.listsize=maxsize;
 25     return ok;
 26 }
 27 Status ListInsert_Sq(SqList &L,int i,ElemType e)
 28 {
 29     ElemType *newbase,*p,*q;
 30     //顺序线性表L中第i个位置插入新的元素e
 31     if(i<1||i>L.length)return error;
 32     if(L.length>=L.listsize)
 33     {
 34         //存储空间满，增加分配。
 35         newbase=(ElemType *)realloc(L.data,(L.listsize+listincreament)*sizeof(ElemType));
 36         if(!newbase) exit(overflow);
 37         L.data=newbase;
 38         L.listsize+=listincreament;
 39     }
 40 
 41     for(int j=L.length;j>=i;j--)
 42     {
 43         L.data[j]=L.data[j-1];
 44     }
 45     L.data[i-1]=e;
 46     L.length++;
 47     return ok;
 48 }
 49 void showList(SqList &L)
 50 {
 51     ElemType *p;
 52     int i=0;
 53     for(int i=0;i<L.length;i++)
 54     {
 55         cout<<L.data[i];
 56         if(i!=L.length-1) cout<<' ';
 57         else cout<<endl;
 58     }
 59 }
 60 Status DeleteList_Elem(SqList &L,int i)
 61 {
 62     if(i<0||i>=L.length) return error;
 63     for(int j=i;j<L.length-1;j++)
 64     {
 65         L.data[j]=L.data[j+1];
 66     }
 67     L.length--;
 68     return ok;
 69 }
 70 int LocateElem(SqList &L,ElemType e)
 71 {
 72     int pos=-1;
 73     for(int j=0;j<L.length;j++)
 74     {
 75         if(L.data[j]==e)
 76             {pos=j;break;}
 77     }
 78     return pos+1;
 79 }
 80 //细节：返回值要+1
 81 int mergeList(SqList &a,SqList &b,SqList &c)
 82 {
 83     ElemType *x,*y,*z;
 84     int ia=0,ib=0,ic=0;
 85     while(ia<a.length-1&&ib<b.length-1)
 86     {
 87         if(a.data[ia]<b.data[ib])
 88         {
 89             c.data[ic++]=a.data[ia++];
 90         }
 91         else {c.data[ic++]=b.data[ib++];}
 92     }
 93     while(ia<a.length-1)
 94         c.data[ic++]=a.data[ia++];
 95     while(ib<b.length-1)
 96         c.data[ic++]=b.data[ib++];
 97     c.length=ic;
 98     return ok;
 99 }
100 
101 int main()
102 {
103     int w;
104     SqList L1,L2,L3;
105     w=initList_Sq(L1);
106     for(int i=0;i<10;i++)
107     {L1.data[i]=i+1;L1.length++;}
108     L1.length=10;
109 
110     initList_Sq(L2);
111     initList_Sq(L3);
112 
113     for(int i=0;i<7;i++)
114     {L2.data[i]=(i+1)*3;}
115     L2.length=7;
116 
117     //cout<<w;
118     showList(L1);
119     ListInsert_Sq(L1,4,33);
120     DeleteList_Elem(L1,7);
121     showList(L1);
122     int a=LocateElem(L1,33);
123     cout<<a<<endl;
124     mergeList(L1,L2,L3);
125     showList(L3);
126     return 0;
127 }

2、基于顺序表实现的一些算法：描述见代码注释（实在是太懒了，就不逐个分开来粘代码了）

  1 /*删除最小元素,返回元素值，空位由末尾元素填补*/
  2 int Delete_minelem(SqList &L)
  3 {
  4     int e=32767,pos;
  5     for(int i=0; i<L.length; i++)
  6     {
  7         if(L.data[i]<e)
  8         {
  9             e=L.data[i];
 10             pos=i;
 11         }
 12     }
 13     if(pos!=L.length-1)
 14     {
 15         L.data[pos]=L.data[L.length-1];
 16         L.length--;
 17     }
 18     else L.length--;
 19     return e;
 20 }
 21 /*空间复杂度O(1)的逆置顺序表*/
 22 void reverse_List(SqList &L,int op,int ed)
 23 {
 24     int mid=(ed+1-op)/2;
 25     for(int i=0; i<mid; i++)
 26     {
 27         int t=L.data[ed-i];
 28         L.data[ed-i]=L.data[op+i];
 29         L.data[op+i]=t;
 30     }
 31 }
 32 /*删除所有值为x的数据元素*/
 33 //用k记录顺序表l中不等于x的元素个数，一边扫描一边统计k，不等于x的元素向前放置到k位置上，最后修改L的长度。
 34 void delete_x(SqList &L,ElemType x)
 35 {
 36     int k=0;
 37     for(int i=0; i<L.length; i++)
 38     {
 39         if(L.data[i]!=x)
 40         {
 41 
 42             L.data[k]=L.data[i];
 43             k++;
 44         }
 45     }
 46     L.length=k;
 47 }
 48 /*删除值在指定的s、t之间的元素，若s、t不合法或者顺序表为空显示出错信息并且退出*/
 49 int delete_fstt(SqList &L,int s,int t)
 50 {
 51     int k=0;
 52     if(L.length==0||s>t) return 0;
 53     for(int i=0; i<L.length; i++)
 54     {
 55         if(L.data[i]>t||L.data[i]<s)
 56         {
 57             L.data[k]=L.data[i];
 58             k++;
 59         }
 60     }
 61     L.length=k;
 62 }
 63 /*删除有序表中所有值重复的元素*/
 64 int delete_same(SqList &L)
 65 {
 66     int k=0,i=0;
 67     while(i<L.length)
 68     {
 69         if(L.data[i]==L.data[k])
 70             i++;
 71         else
 72         {
 73             k++;
 74             L.data[k]=L.data[i];
 75         }
 76     }
 77     L.length=k+1;
 78 }
 79 //注意，此处k最后要加1才为正确所求。因为k在函数中起一个下标处理的作用，而数组是从0开始的，故最后要加一。
 80 /*互换指定一个线性表中两个子表的位置*/
 81 /*如A(a,b)->A(b,a) a:(0~a),b:(a+1~A.length-1)*/
 82 void reverse_sonofList(SqList &L,int a)
 83 {
 84     reverse_List(L,0,a);
 85     reverse_List(L,a+1,L.length-1);
 86     reverse_List(L,0,L.length-1);
 87 }
 88 //这个方法很奇妙，可以在空间复杂度为1的情况下解决数组位数循环的问题
 89 
 90 /*有序递增顺序表，在最少时间内于表中查找数值为x的元素，若找到使之与后继元素交换，找不到插入x于表中使得表元素仍然递增有序。*/
 91 /*因为要求是用最短时间查找，应该选择折半查找法*/
 92 void exchange(SqList &L,int x)
 93 {
 94     int low=0,high=L.length-1,mid;
 95     while(low<=high)
 96     {
 97         mid=(high+low)/2;
 98         if(L.data[mid]==x) break;
 99         else if(L.data[mid]>x)high=mid-1;//缩小上界
100         else low=mid+1;//缩小下界
101     }
102     if(L.data[mid]==x)
103         swap(L.data[mid],L.data[mid+1]);
104     else
105     {
106         int i;
107         for(i=L.length-1; i>high; i--)
108         {
109             L.data[i+1]=L.data[i];
110         }
111         L.data[i+1]=x;//插入的位置应为A[i+1]而不是i，若是手写代码的，这里应模拟一下保证正确度
112         L.length++;
113     }
114 }
115 /*给出两个等长升序数列，寻找共同的中位数*/
116 /*时间复杂度为O(n),空间复杂度为O（1）*/
117 int findmid(SqList &L1,SqList &L2)
118 {
119     int a1=0,a2=0,ans;
120     int cut=L1.length;
121 
122     while(cut--)
123     {
124 
125         if(L1.data[a1]<L2.data[a2])
126         {
127             ans=L1.data[a1];
128             a1++;
129 
130         }
131         else
132         {
133             ans=L2.data[a2];
134             a2++;
135         }
136     }
137 
138     return ans;
139 }
140 /*给出两个等长升序数列，寻找共同的中位数*/
141 /*解法二，时间复杂度为O(log2n)，空间复杂度为O(1)*/
142 int M_search(int A[],int B[],int n)
143 {
144     int s1=0,d1=n-1,m1,s2=0,d2=n-1,m2;
145     //分别表示了A、B序列的首位数、末尾数、中位数
146     while(s1!=d1||s2!=d2)//重复到两个序列只剩一个元素为止，比较小的为所求。
147     {
148         m1=(s1+d1)/2;
149         m2=(s2+d2)/2;
150         if(A[m1]==B[m2]) return A[m1];//a=b，a或者b为所求的中位数，算法结束
151         if(A[m1]<B[m2])//若a<b，舍弃A中较小的一半，同时舍去序列b中较大的一半，要求两次舍弃长度相等。
152         {
153             if((s1+d1)%2==0)//元素个数为奇数
154             {
155                 s1=m1;//舍弃A中间点以前的部分并且保留中间点
156                 d2=m2;//舍弃B中间点以后的部分并且保留中间点
157             }
158             else
159             {
160                 s1=m1+1;//舍弃A中间点以及中间点以前的部分
161                 d2=m2;//舍弃B中间点以后的部分，保留中间点
162             }
163 
164         }
165         else//若a>b，舍弃A中较大的一半，同时舍去序列b中较小的一半，要求两次舍弃长度相等。
166         {
167 
168             if((s1+d1)%2==0)//元素个数为奇数
169             {
170                 d1=m1;//舍弃A中间点以前的部分并且保留中间点
171                 s2=m2;//舍弃B中间点以后的部分并且保留中间点
172             }
173             else
174             {
175                 d1=m1;//舍弃A中间点以及中间点以前的部分
176                 s2=m2+1;//舍弃B中间点以后的部分，保留中间点
177             }
178         }
179     }
180     return A[s1]<B[s2]?A[s1]:B[s2];
181 }
182 //一般人怕是想不到orz
183 
184 /*寻找主元素：出现次数大于长度一般的元素，存在输出，不存在输出-1*/
185 int findmainelem(SqList &L)
186 {
187     int k=0,num;
188     num=L.data[0];//设置第一个为候选主元素
189     k++;
190     for(int i=0; i<L.length; i++)
191     {
192         if(L.data[i]!=num)
193         {
194             if(k>0)
195                 k--;
196             else
197             {
198                 num=L.data[i];
199                 k=1;
200             }
201         }
202         else k++;
203     }
204     int flag=1,countt=0;
205     for(int i=0; i<L.length; i++)
206     {
207         if(L.data[i]==num)
208             countt++;
209     }
210     if(countt>L.length/2)flag=!flag;
211     if(flag) return -1;
212     else return num;
213 }

1-线性表 顺序存储

1-线性表顺序存储