C++实现动态数组
#include<iostream>
using namespace std;
struct SeList{//struct结构体与class唯一的区别就是默认访问权限不一样
int *data;//struct默认是public的访问权限，所以方便用于作为节点结构体
int Max;//动态数组的整体思想是在结构体内声明指针，最大长度，实际长度，在外部函数中生成实际的数组，数组的这三个主要指标放在了结构体中
int length;
};
void initList(SeList &list,int x){//数组初始化
list.data=new int[x];
list.Max=x;
list.length=0;
}
void setList(SeList &list){//给数组赋值
for(int i=0;i<list.Max;++i){
list.data[i]=i+1;
if(list.length<list.Max){
list.length++;
}
}
}
void set_List(SeList &list){//给数组赋值
for(int i=0;i<list.Max/2;++i){
list.data[i]=i+1;
if(list.length<list.Max/2){
list.length++;
}
}
}
void printList(SeList &list){//打印数组
for(int i=0;i<list.length;++i){
cout<<list.data[i]<<" ";
}
cout<<endl;
}
void increaseList(SeList &list,int len){//增加数组长度
int *p=list.data;
list.data=new int[list.Max+len];
for(int i=0;i<list.length;++i){
list.data[i]=p[i];
}
list.Max=list.Max+len;
delete[] p;
}
bool deleteMin(SeList &list,int &value){//数组最后一个值替代最小值
if(list.length==0){
return false;
}
value=list.data[0];
int a=0;//辅助变量，记录最小元素的位置
for(int i=0;i<list.length;++i){
if(value>list.data[i]){
value=list.data[i];
a=i;
}
}
list.data[a]=list.data[list.length-1];
return true;
}
bool reverseList(SeList &list){//逆置数组元素
if(list.length==0){
return false;
}
int temp=0;//辅助变量
for(int i=0;i<list.length/2;++i){//无需考虑数组元素个数的奇偶性，因为length/2取整
temp=list.data[i];
list.data[i]=list.data[list.length-i-1];
list.data[list.length-i-1]=temp;
}
return true;
}
bool reverse_List(SeList &list,int m,int n){//逆置数组中指定位置范围的元素
if(list.length==0||m>=n){
return false;
}
int temp=0,k=0;
for(int i=m-1;i<=(n+m-2)/2;++i){
temp=list.data[i];
list.data[i]=list.data[n-1-k];
list.data[n-1-k]=temp;
++k;
}
}
void deleteX(SeList &list,int x){//删除数组中值为x的所有元素
int k=0;//记录非x的元素个数，也就是保留下来的元素个数
for(int i=0;i<list.length;++i){//顺序扫描数组，每判断一个非x值就加入结果数组
if(list.data[i]!=x){//非x元素保留下来，这里利用了i的值一定大于等于k的值，所以在一个循环中就可以解决问题
list.data[k]=list.data[i];
++k;
}
}
list.length=k;//修改数组长度
}
bool deleteST(SeList &list,int s,int t){//删除所有介于s和t之间（包含s与t）的元素
if(s>=t){
cout<<"输入范围错误"<<endl;
return false;
}
if(list.length==0){
cout<<"顺序表为空"<<endl;
return false;
}
int k=0;// 记录不在范围s与t之间的元素的个数
for(int i=0;i<list.length;++i){//顺序扫描数组，每判断到一个不属于s与t之间的元素就加入结果数组
if(list.data[i]<s||list.data[i]>t){
list.data[k]=list.data[i];
++k;
}
}
list.length=k;//修改数组长度
return true;
}
void deleteSame(SeList &list){//有序表中删除相同元素
int k=1;//非相同元素的个数
for(int i=1;i<list.length;++i){// 因为第一个肯定不重复，从第二个元素开始顺序扫描数组，每判断到一个不是相同的元素就将其加入结果数组
if(list.data[i]!=list.data[i-1]){
list.data[k]=list.data[i];
++k;
}
}
list.length=k;//修改数组长度
}
bool addList(SeList list1,SeList list2,SeList &list){//合并两个有序数组，合并结果存入第三个数组
if(list1.length+list2.length>list.Max){//如果前两个数组的长度之和大于第三个数组长度最大值，无法合并，返回错误
return false;
}
int i=0;//辅助变量，记录第一个数组的下标
int j=0;//辅助变量，记录第二个数组的下标
int k=0;//辅助变量，记录第三个数组的下标
while(i<list1.length&&i<list2.length){//这里使用while循环，对判断条件的设置比较关键；当两个数组都没有遍历完时，比较两个数组最前面的值，较小者加入结果数组
if(list1.data[i]<=list2.data[j]){
list.data[k]=list1.data[i];
k++;
i++;
}else{
list.data[k]=list2.data[j];
k++;
j++;
}
}
while(i<list1.length){//若只有第一个数组还没有遍历完，第一个数组剩余数据是表中较大的了，按顺序加入结果数组即可
list.data[k]=list1.data[i];
k++;
i++;
}
while(j<list2.length){
list.data[k]=list2.data[j];
k++;
j++;
}
list.length=k;
return true;
}
bool invertList(SeList &list,int m,int n){//将数组中的前m位与后n为的位置互换，可以看做先将数组整个逆置，之后对目前的两个数组分别再逆置，调用指定范围的逆置函数实现
reverseList(list);
reverse_List(list,1,n);
reverse_List(list,n+1,n+m);
return true;
}
bool insert_List(SeList &list,int x){//若查到值为x的元素，将其与其后的元素交换位置，若查不到，则将其插入顺序表中使得，顺序表仍然递增
int low=0;
int n=list.length-1;
int high=n;
int mid;
while(low<=high){
mid=(low+high)/2;
if(list.data[mid]==x){
break;
}else if(list.data[mid]<x){
low=mid+1;
}else{
high=mid-1;
}
}
if(list.data[mid]==x&&mid!=n){
list.data[mid]=list.data[mid+1];
list.data[mid+1]=x;
cout<<x<<endl;
}
if(low>high){
for(int i=n;i>high;--i){
list.data[i+1]=list.data[i];
list.data[i+1]=x;
cout<<x<<endl;
}
list.length++;
}
}
int main(){
SeList list1;
initList(list1,15);
setList(list1);//初始化并设置第一个数组
printList(list1);
SeList list2;
initList(list2,15);
set_List(list2);
printList(list2);//初始化并设置第二个数组
SeList list3;
initList(list3,30);
addList(list1,list2,list3);
printList(list3);
invertList(list1,6,9);
printList(list1);
insert_List(list2,5);
printList(list2);
return 0;
}