凡科网商城是正规网站吗,代运营是什么意思,郑州做网站报价,淘宝网店怎么注册开店几道相关例题,帮助大家更好理解顺序表. 文章目录 前言
一、顺序表二、创建顺序表并初始化三.删除非递减顺序表L中的重复元素四.在非递减顺序表中删除[s,t]之间的元素五.设计算法逆置顺序表L,并将序列L循环左移六.顺序表A和B的元素个数分别为m,n.A表升序排序,B表降序排序,两表中… 几道相关例题,帮助大家更好理解顺序表. 文章目录 前言
一、顺序表二、创建顺序表并初始化三.删除非递减顺序表L中的重复元素四.在非递减顺序表中删除[s,t]之间的元素五.设计算法逆置顺序表L,并将序列L循环左移六.顺序表A和B的元素个数分别为m,n.A表升序排序,B表降序排序,两表中都不存在相同元素七.给定两个非空集合A和B,分别用升序顺序表La,Lb存储,设计算法求解A交B 八.给定两个非空集合A和B,分别用升序表La与Lb存储,设计算法求解A-B(A中元素减去B中有的元素)九.测试总结 前言
几道相关例题,帮助大家更好理解顺序表. 一、顺序表
typedef int Elemtype;
//顺序表的动态分配
typedef struct Sqlist {Elemtype* qlist;int length;int maxsize;
};
//定义打印顺序表函数
void print(Sqlist L) {for (int i 0; i L.length; i) {//顺序遍历顺序表printf(%d , L.qlist[i]);}printf(\n顺序表长度为:%d\n, L.length);printf(总大小为:%d\n, L.maxsize);
} 二、创建顺序表并初始化
//例1:定义创建顺序表并初始化函数
void InitSqlist(Sqlist L) {//初始化空间为20,长度为15,{ 0,1,2,3,4,4,4,5,6,7,7,8,8,9,9 }L.maxsize Max;L.length 15;int arr[15] { 0,1,2,3,4,4,4,5,6,7,7,8,8,9,9 };L.qlist (Elemtype*)malloc(sizeof(Elemtype) * (L.maxsize));for (int i 0; i L.length; i) {L.qlist[i] arr[i];}
} 三.删除非递减顺序表L中的重复元素
//例6:删除非递减顺序表L中的重复元素
void deletesame(Sqlist L) {int curlenth 0;for (int i 0; i L.length; i) {//每次区元素与新表最后一个元素进行比较如果不相等加入新表if (curlenth 0 || L.qlist[i] ! L.qlist[curlenth - 1]) {L.qlist[curlenth] L.qlist[i];}}L.length curlenth;
}
四.在非递减顺序表中删除[s,t]之间的元素
//例7:在非递减顺序表中删除[s,t]之间的元素
void deletest2(Sqlist L, int s, int t) {int curlength 0;int i 0;for (; i L.length; i) {//从前往后找第一个大于或等于s的元素的位置if (L.qlist[i] s) {break;}}curlength i;i L.length - 1;for (; i 0; i--) {//从后往前找第一个小于或等于t的元素的位置if (L.qlist[i] t) {break;}}i i 1;//指向下一个元素才是要复制的元素for (; i L.length; i) {//复制元素L.qlist[curlength] L.qlist[i];}L.length curlength;
} 五.设计算法逆置顺序表L,并将序列L循环左移
//例8:设计算法逆置顺序表L,并将序列L循环左移
//定义逆置函数
void reverse1(Sqlist L) {int low 0;int high L.length - 1;while (low high) {//设置low和high指针对表中元素进行两两交换Elemtype tmp L.qlist[low];L.qlist[low] L.qlist[high];L.qlist[high] tmp;low;high--;}
}
void reverse2(Sqlist L,int low ,int high) {while (low high) {Elemtype tmp L.qlist[low];L.qlist[low] L.qlist[high];L.qlist[high] tmp;low;high--;}
}
void ROL(Sqlist L, int r) {reverse2(L, 0, L.length - 1);//整体逆置reverse2(L, 0, r-1);//前r个元素逆置reverse2(L, r, L.length - 1);//后面元素逆置
} reverse1是直接将顺序表全部逆置,reverse2是给定起始和终止逆置.
顺序表的循环左移r位,就是先整体逆置,前r个元素逆置,后面元素逆置.
六.顺序表A和B的元素个数分别为m,n.A表升序排序,B表降序排序,两表中都不存在相同元素
(1)将两表合并,两表中元素都储存在C中
(2)表A有mn个存储空间,将A,B两表合并所有元素都存储到A中
(3)对表A进行简单插入排序
//例9:顺序表A和B的元素个数分别为m,n.A表升序排序,B表降序排序,两表中都不存在相同元素
//(1)将两表合并,两表中元素都储存在C中
//创建La和Lb
void creatLaLb(Sqlist La, Sqlist Lb) {La.maxsize 11;La.length 6;int arr1[6] { 0,2,4,7,8,9 };La.qlist (Elemtype*)malloc(sizeof(Elemtype) * (La.maxsize));for (int i 0; i La.length; i) {La.qlist[i] arr1[i];}Lb.maxsize 11;Lb.length 5;int arr2[5] { 10,6,5,3,1 };Lb.qlist (Elemtype*)malloc(sizeof(Elemtype) * (Lb.maxsize));for (int i 0; i Lb.length; i) {Lb.qlist[i] arr2[i];}
}
//归并排序思想
void mergesort1(Sqlist La, Sqlist Lb, Sqlist Lc) {int length La.length Lb.length;Lc.qlist (Elemtype*)malloc(sizeof(Elemtype) * length);assert(Lc.qlist);Lc.maxsize length;int curlength 0;int i 0;int j Lb.length-1;while (i La.length j 0) {if (La.qlist[i] Lb.qlist[j]) {Lc.qlist[curlength] Lb.qlist[j];curlength;j--;}else {Lc.qlist[curlength] La.qlist[i];curlength;i;}}while (i La.length) {Lc.qlist[curlength] Lb.qlist[i];i;}while (j 0) {Lc.qlist[curlength] Lb.qlist[j];j--;}Lc.length curlength;
}
//(2)表A有mn个存储空间,将A,B两表合并所有元素都存储到A中
void mergesort2(Sqlist La, Sqlist Lb) {int curlength 0;int i La.length-1;//A表后int j 0;//B表头while (i 0 j Lb.length) {//将A表与B表元素进行比较将大的存入A表后if (La.qlist[i] Lb.qlist[j]) {La.qlist[La.maxsize - curlength - 1] La.qlist[i];curlength;i--;}else {La.qlist[La.maxsize - curlength - 1] Lb.qlist[j];curlength;j;}}while (i 0) {//将A表剩余元素直接复制到A表中La.qlist[La.maxsize - curlength - 1] La.qlist[i];curlength;i--;}while (j Lb.length) {//将B表剩余元素直接复制到A表中La.qlist[La.maxsize - curlength - 1] Lb.qlist[j];curlength;j;}La.length La.length Lb.length;
}
//(3)对表A进行简单插入排序
void selectsort(Sqlist L) {int i 0;int j 0;while (i L.length) {//每次选取一个元素Elemtype e L.qlist[i];j i - 1;while (j 0 e L.qlist[j]) {//寻找插入位置L.qlist[j 1] L.qlist[j];j--;}L.qlist[j 1] e;i;}
}
七.给定两个非空集合A和B,分别用升序顺序表La,Lb存储,设计算法求解A交B
//例10:给定两个非空集合A和B,分别用升序顺序表La,Lb存储,设计算法求解A交B
//创建两个升序La表和Lb表
void creatLaLb2(Sqlist La, Sqlist Lb) {La.maxsize 20;La.length 11;int arr1[11] { 1,1,2,2,3,3,4,4,5,5,6 };La.qlist (Elemtype*)malloc(sizeof(Elemtype) * (La.maxsize));for (int i 0; i La.length; i) {La.qlist[i] arr1[i];}Lb.maxsize 20;Lb.length 11;int arr2[11] { 1,1,2,2,4,4,5,5,6,6,7 };Lb.qlist (Elemtype*)malloc(sizeof(Elemtype) * (Lb.maxsize));for (int i 0; i Lb.length; i) {Lb.qlist[i] arr2[i];}
}
//求解A交B
void intersect(Sqlist La,Sqlist Lb) {int curlength 0;int i 0;int j 0;while (i La.length j Lb.length) {//A表和B表元素进行两两比较如果相等加入新表if (La.qlist[i] Lb.qlist[j]) {La.qlist[curlength] La.qlist[i];i;j;curlength;}else if(La.qlist[i] Lb.qlist[j]) {//B表当前元素小于表A当前元素B表下表加一j;}else {//A表当前元素小于表B当前元素A表下表加一i;}}La.length curlength;//元素个数改变
} 八.给定两个非空集合A和B,分别用升序表La与Lb存储,设计算法求解A-B(A中元素减去B中有的元素)
//例11:给定两个非空集合A和B,分别用升序表La与Lb存储,设计算法求解A-B(A中元素减去B中有的元素)
//算法思想跟上一题一样
void except(Sqlist La, Sqlist Lb) {int curlength 0;int i 0;int j 0;while (i La.length j Lb.length) {if (La.qlist[i] Lb.qlist[j]) {//相等下标都相加i;j;}else if (La.qlist[i] Lb.qlist[j]) {//ab,B下标增加j;}else {//ab说明当前A中元素一定是B中没有的La.qlist[curlength] La.qlist[i];curlength;i;}}while (i La.length) {//将A表剩余元素复制到新表La.qlist[curlength] La.qlist[i];curlength;i;}La.length curlength;//元素个数改变
}
九.测试
全部代码:
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includemalloc.h
#includeassert.h
#define Max 20typedef int Elemtype;
//顺序表的动态分配
typedef struct Sqlist {Elemtype* qlist;int length;int maxsize;
};
//定义打印顺序表函数
void print(Sqlist L) {for (int i 0; i L.length; i) {//顺序遍历顺序表printf(%d , L.qlist[i]);}printf(\n顺序表长度为:%d\n, L.length);printf(总大小为:%d\n, L.maxsize);
}//例1:定义创建顺序表并初始化函数
void InitSqlist(Sqlist L) {//初始化空间为20,长度为15,{ 0,1,2,3,4,4,4,5,6,7,7,8,8,9,9 }L.maxsize Max;L.length 15;int arr[15] { 0,1,2,3,4,4,4,5,6,7,7,8,8,9,9 };L.qlist (Elemtype*)malloc(sizeof(Elemtype) * (L.maxsize));for (int i 0; i L.length; i) {L.qlist[i] arr[i];}
}
//例6:删除非递减顺序表L中的重复元素
void deletesame(Sqlist L) {int curlenth 0;for (int i 0; i L.length; i) {//每次区元素与新表最后一个元素进行比较如果不相等加入新表if (curlenth 0 || L.qlist[i] ! L.qlist[curlenth - 1]) {L.qlist[curlenth] L.qlist[i];}}L.length curlenth;
}
//例7:在非递减顺序表中删除[s,t]之间的元素
void deletest2(Sqlist L, int s, int t) {int curlength 0;int i 0;for (; i L.length; i) {//从前往后找第一个大于或等于s的元素的位置if (L.qlist[i] s) {break;}}curlength i;i L.length - 1;for (; i 0; i--) {//从后往前找第一个小于或等于t的元素的位置if (L.qlist[i] t) {break;}}i i 1;//指向下一个元素才是要复制的元素for (; i L.length; i) {//复制元素L.qlist[curlength] L.qlist[i];}L.length curlength;
}
//例8:设计算法逆置顺序表L,并将序列L循环左移
//定义逆置函数
void reverse1(Sqlist L) {int low 0;int high L.length - 1;while (low high) {//设置low和high指针对表中元素进行两两交换Elemtype tmp L.qlist[low];L.qlist[low] L.qlist[high];L.qlist[high] tmp;low;high--;}
}
void reverse2(Sqlist L,int low ,int high) {while (low high) {Elemtype tmp L.qlist[low];L.qlist[low] L.qlist[high];L.qlist[high] tmp;low;high--;}
}
void ROL(Sqlist L, int r) {reverse2(L, 0, L.length - 1);//整体逆置reverse2(L, 0, r-1);//前r个元素逆置reverse2(L, r, L.length - 1);//后面元素逆置
}
//例9:顺序表A和B的元素个数分别为m,n.A表升序排序,B表降序排序,两表中都不存在相同元素
//(1)将两表合并,两表中元素都储存在C中
//创建La和Lb
void creatLaLb(Sqlist La, Sqlist Lb) {La.maxsize 11;La.length 6;int arr1[6] { 0,2,4,7,8,9 };La.qlist (Elemtype*)malloc(sizeof(Elemtype) * (La.maxsize));for (int i 0; i La.length; i) {La.qlist[i] arr1[i];}Lb.maxsize 11;Lb.length 5;int arr2[5] { 10,6,5,3,1 };Lb.qlist (Elemtype*)malloc(sizeof(Elemtype) * (Lb.maxsize));for (int i 0; i Lb.length; i) {Lb.qlist[i] arr2[i];}
}
//归并排序思想
void mergesort1(Sqlist La, Sqlist Lb, Sqlist Lc) {int length La.length Lb.length;Lc.qlist (Elemtype*)malloc(sizeof(Elemtype) * length);assert(Lc.qlist);Lc.maxsize length;int curlength 0;int i 0;int j Lb.length-1;while (i La.length j 0) {if (La.qlist[i] Lb.qlist[j]) {Lc.qlist[curlength] Lb.qlist[j];curlength;j--;}else {Lc.qlist[curlength] La.qlist[i];curlength;i;}}while (i La.length) {Lc.qlist[curlength] Lb.qlist[i];i;}while (j 0) {Lc.qlist[curlength] Lb.qlist[j];j--;}Lc.length curlength;
}
//(2)表A有mn个存储空间,将A,B两表合并所有元素都存储到A中
void mergesort2(Sqlist La, Sqlist Lb) {int curlength 0;int i La.length-1;//A表后int j 0;//B表头while (i 0 j Lb.length) {//将A表与B表元素进行比较将大的存入A表后if (La.qlist[i] Lb.qlist[j]) {La.qlist[La.maxsize - curlength - 1] La.qlist[i];curlength;i--;}else {La.qlist[La.maxsize - curlength - 1] Lb.qlist[j];curlength;j;}}while (i 0) {//将A表剩余元素直接复制到A表中La.qlist[La.maxsize - curlength - 1] La.qlist[i];curlength;i--;}while (j Lb.length) {//将B表剩余元素直接复制到A表中La.qlist[La.maxsize - curlength - 1] Lb.qlist[j];curlength;j;}La.length La.length Lb.length;
}
//(3)对表A进行简单插入排序
void selectsort(Sqlist L) {int i 0;int j 0;while (i L.length) {//每次选取一个元素Elemtype e L.qlist[i];j i - 1;while (j 0 e L.qlist[j]) {//寻找插入位置L.qlist[j 1] L.qlist[j];j--;}L.qlist[j 1] e;i;}
}
//例10:给定两个非空集合A和B,分别用升序顺序表La,Lb存储,设计算法求解A交B
//创建两个升序La表和Lb表
void creatLaLb2(Sqlist La, Sqlist Lb) {La.maxsize 20;La.length 11;int arr1[11] { 1,1,2,2,3,3,4,4,5,5,6 };La.qlist (Elemtype*)malloc(sizeof(Elemtype) * (La.maxsize));for (int i 0; i La.length; i) {La.qlist[i] arr1[i];}Lb.maxsize 20;Lb.length 11;int arr2[11] { 1,1,2,2,4,4,5,5,6,6,7 };Lb.qlist (Elemtype*)malloc(sizeof(Elemtype) * (Lb.maxsize));for (int i 0; i Lb.length; i) {Lb.qlist[i] arr2[i];}
}
//求解A交B
void intersect(Sqlist La,Sqlist Lb) {int curlength 0;int i 0;int j 0;while (i La.length j Lb.length) {//A表和B表元素进行两两比较如果相等加入新表if (La.qlist[i] Lb.qlist[j]) {La.qlist[curlength] La.qlist[i];i;j;curlength;}else if(La.qlist[i] Lb.qlist[j]) {//B表当前元素小于表A当前元素B表下表加一j;}else {//A表当前元素小于表B当前元素A表下表加一i;}}La.length curlength;//元素个数改变
}
//例11:给定两个非空集合A和B,分别用升序表La与Lb存储,设计算法求解A-B(A中元素减去B中有的元素)
//算法思想跟上一题一样
void except(Sqlist La, Sqlist Lb) {int curlength 0;int i 0;int j 0;while (i La.length j Lb.length) {if (La.qlist[i] Lb.qlist[j]) {//相等下标都相加i;j;}else if (La.qlist[i] Lb.qlist[j]) {//ab,B下标增加j;}else {//ab说明当前A中元素一定是B中没有的La.qlist[curlength] La.qlist[i];curlength;i;}}while (i La.length) {//将A表剩余元素复制到新表La.qlist[curlength] La.qlist[i];curlength;i;}La.length curlength;//元素个数改变
}
int main() {printf(\n);printf(对InitSqlist进行测试!\n);Sqlist L;InitSqlist(L);print(L);//打印顺序表以及信息printf(\n);printf(对deletesame进行测试!\n);deletesame(L);print(L);InitSqlist(L);printf(\n);printf(对deletest2进行测试!\n);deletest2(L, 4, 7);print(L);InitSqlist(L);printf(\n);printf(对reverse2进行测试!\n);reverse1(L);print(L);InitSqlist(L);reverse2(L, 0, L.length - 1);print(L);InitSqlist(L);printf(\n);printf(对ROL进行测试!\n);print(L);ROL(L,3);print(L);InitSqlist(L);printf(\n);printf(对例8进行测试!\n);Sqlist La,Lb,Lc;printf(创建La和Lb顺序表\n);creatLaLb(La, Lb);print(La);print(Lb);printf(归并La和Lb顺序表\n);mergesort1(La, Lb, Lc);print(Lc);printf(归并La和Lb顺序表用原空间\n);mergesort2(La, Lb);print(La);print(Lb);creatLaLb(La, Lb);//初始化一下Sqlist LA;LA.maxsize Max;LA.length 12;int arr[12] { 3,6,2,1,7,8,4,5,9,10,12,11 };LA.qlist (Elemtype*)malloc(sizeof(Elemtype) * (LA.maxsize));for (int i 0; i L.length; i) {LA.qlist[i] arr[i];}print(LA);printf(对表A进行简单选择插入排序!\n);selectsort(LA);print(LA);printf(\n);printf(对例10进行测试!\n);creatLaLb2(La, Lb);print(La);print(Lb);intersect(La, Lb);print(La);printf(\n);printf(对例11进行测试!\n);creatLaLb2(La, Lb);print(La);print(Lb);except(La, Lb);print(La);return 0;} 输出结果: 总结
写了几个经典的顺序表的题目,有些函数作用是创建表的,可以省略,主要是解决问题的思路和方法,输出结果比较常所以我分成了两张图片,大家自行比对,或者直接复制代码上机运行,有问题的地方可以私信我.
