顺序表实现(下)(C语言)
发布时间：2024年01月08日
几道相关例题,帮助大家更好理解顺序表.
文章目录
- 一、顺序表
- 二、创建顺序表并初始化
- 三.删除非递减顺序表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有m+n个存储空间,将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有m+n个存储空间,将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]) {//a>b,B下标增加
j++;
}
else {//a<b说明当前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
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#define Max 20
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];
}
}
//例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有m+n个存储空间,将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]) {//a>b,B下标增加
j++;
}
else {//a<b说明当前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;
}?输出结果:
总结
写了几个经典的顺序表的题目,有些函数作用是创建表的,可以省略,主要是解决问题的思路和方法,输出结果比较常所以我分成了两张图片,大家自行比对,或者直接复制代码上机运行,有问题的地方可以私信我.
文章来源:https://blog.csdn.net/qq_55383558/article/details/135464387
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！
最新文章
- Python教程
- 深入理解 MySQL 中的 HAVING 关键字和聚合函数
- Qt之QChar编码（1）
- MyBatis入门基础篇
- 用Python脚本实现FFmpeg批量转换
- 《MySQL系列-InnoDB引擎03》MySQL文件相关介绍
- 力扣白嫖日记(sql)
- verilog的模块参数定义
- linux 抓包
- Python调用Carla接口生成仿真场景
- 我的一天：追求专业成长与生活平衡
- 曲线生成 | 图解贝塞尔曲线生成原理(附ROS C++/Python/Matlab仿真)
- 1278：【例9.22】复制书稿(book)
- 迎接更高效的数据安全合规与风险评估，美创科技DCAS正式商用发布！
- 19.Tomcat搭建