//顺序表(数组实现)
//要实现的操作有:初始化表:Initlist( &l) 销毁表 Destorylist(&l)
//判断表是否为空:Emptylist (l) 求表长度:Lengthlist( l)
//输出表: Displist(l) 查找表中的元素:Locatelist(l,x)
// 当然还有最重要的两个 Insertlist(&l,i,e) Deletelist(&l,i)
#include<bits/stdc++.h>
#define max 1000
using namespace std;
typedef struct{
int data[max];
int length;
}sqlist;
void Initlist(sqlist*&l){
l=(sqlist*)malloc(sizeof(sqlist));
l->length=0;
}
void Destorylist(sqlist*&l){
free(l);
}
bool Emptylist(sqlist*&l){
return (l->length==0);
}
int Lengthlist(sqlist*&l){
return l->length;
}
void Displist(sqlist*&l){
for(int j=0;j<l->length;j++){
cout<<l->data[j]<<" ";
}
}
int Locatelist(sqlist*&l,int x){ //查找x在表中的位置,没找到则返回false
for(int j=0;j<l->length;j++){
if(l->data[j]==x)
return j;
}
return false;
}
bool Insertlist(sqlist*&l,int i,int x){ //这里插入的数据必须为整型,i为插入的位置(从0开始),x为插入的数据值
int j;
if(i<0||i>l->length)
return false ;
for(j=l->length;j>=i;j--)
l->data[j+1]=l->data[j];
l->data[i]=x;
l->length++;
return true;
}
bool Deletelist(sqlist*&l,int i){
int j;
if(i<0||i>l->length-1)
return false;
for(j=i;j<l->length-1;j++)
l->data[j]=l->data[j+1];
l->length--;
return true;
}
int main(){
sqlist * l;
Initlist(l);//这样才可以存储数据,必须先初始化,接下来插入数据,
for(int i=0;i<10;i++)
Insertlist(l,i,i);//将0-9 插入链表中
}
//顺序表基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef int ElemType;
typedef struct
{ ElemType data[MaxSize]; //存放顺序表元素
int length; //存放顺序表的长度
} SqList; //顺序表的类型
void CreateList(SqList *&L,ElemType a[],int n)
//建立顺序表
{
L=(SqList *)malloc(sizeof(SqList));
for (int i=0;i<n;i++)
L->data[i]=a[i];
L->length=n;
}
void InitList(SqList *&L)
{
L=(SqList *)malloc(sizeof(SqList)); //分配存放线性表的空间
L->length=0;
}
void DestroyList(SqList *&L)
{
free(L);
}
bool ListEmpty(SqList *L)
{
return(L->length==0);
}
int ListLength(SqList *L)
{
return(L->length);
}
void DispList(SqList *L)
{
for (int i=0;i<L->length;i++)
printf("%d ",L->data[i]);
printf("\n");
}
bool GetElem(SqList *L,int i,ElemType &e)
{
if (i<1 || i>L->length)
return false;
e=L->data[i-1];
return true;
}
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;
}
bool ListInsert(SqList *&L,int i,ElemType e)
{
int j;
if (i<1 || i>L->length+1)
return false;
i--; //将顺序表位序转化为elem下标
for (j=L->length;j>i;j--) //将data[i]及后面元素后移一个位置
L->data[j]=L->data[j-1];
L->data[i]=e;
L->length++; //顺序表长度增1
return true;
}
bool ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if (i<1 || i>L->length)
return false;
i--; //将顺序表位序转化为elem下标
e=L->data[i];
for (j=i;j<L->length-1;j++) //将data[i]之后的元素前移一个位置
L->data[j]=L->data[j+1];
L->length--; //顺序表长度减1
return true;
}
int main(){
}
我的想法很简单,只需要从左向右扫描比基准小于等于的数和从右向左扫描大于基准的数,当扫描到则立刻交换,继续扫描,直到两个扫描的标杆相遇。
//假设这个顺序表的数为3,8,2,7,1,5,3,4,6,0
#include<bits/stdc++.h>
#define max 1000
using namespace std;
typedef struct{
int data[max];
int length;
}sqlist;
void Initlist(sqlist*&l){
l=(sqlist*)malloc(sizeof(sqlist));
l->length=0;
}
void Destorylist(sqlist*&l){
free(l);
}
bool Emptylist(sqlist*&l){
return (l->length==0);
}
int Lengthlist(sqlist*&l){
return l->length;
}
void Displist(sqlist*&l){
for(int j=0;j<l->length;j++){
cout<<l->data[j]<<" ";
}
}
int Locatelist(sqlist*&l,int x){ //查找x在表中的位置,没找到则返回false
for(int j=0;j<l->length;j++){
if(l->data[j]==x)
return j;
}
return false;
}
bool Insertlist(sqlist*&l,int i,int x){ //这里插入的数据必须为整型,i为插入的位置(从0开始),x为插入的数据值
int j;
if(i<0||i>l->length)
return false ;
for(j=l->length;j>=i;j--)
l->data[j+1]=l->data[j];
l->data[i]=x;
l->length++;
return true;
}
bool Deletelist(sqlist*&l,int i){
int j;
if(i<0||i>l->length-1)
return false;
for(j=i;j<l->length-1;j++)
l->data[j]=l->data[j+1];
l->length--;
return true;
}
void exchangelist(sqlist*&l){
int i=0,j=l->length;
while(i<j){
while(i<j&&l->data[i]<=l->data[0])//从左向右,找大于基准的数
i++;
while(i<j&&l->data[j]>l->data[0])//从右向左,找小于等于基准的数
j--;
if(i<j)
swap(l->data[i],l->data[j]);
}
swap(l->data[0],l->data[i-1]);//这里从左向右必须找大于基准的数,不能换成大于等于,最后将基准数移到中间
}
int main(){
sqlist*l;
//先初始化表,这里我是用自己写的表做的
Initlist(l);
Insertlist(l,0,3);
Insertlist(l,1,8);
Insertlist(l,2,2);
Insertlist(l,3,7);
Insertlist(l,4,1);
Insertlist(l,5,5);
Insertlist(l,6,3);
Insertlist(l,7,4);
Insertlist(l,8,6);
Insertlist(l,9,0);
exchangelist(l);
Displist(l);
}
运行结果: 5 0 2 3 1 3 7 4 6 8 ——————————– Process exited after 0.5798 seconds with return value 0 请按任意键继续. . .
//这个算法必须先从右向左扫描,此外这个算法是快速排序的过程
void exchangelist(sqlist*&l){
int i=0,j=l->length,pivot=l->data[0];
while(i<j){
while(i<j&&pivot<l->data[j])//从右向左找小于等于基准的数
j--;
l->data[i]=l->data[j];
while(i<j&&pivot>=l->data[i])//从左向右找大于基准的数
i++;
l->data[j]=l->data[i];
}
l->data[i]=pivot;
}
//第一种解法和之前类似,不写了
//假设这个顺序表的数为3,8,2,7,1,5,3,4,6,0
#include<bits/stdc++.h>
#define max 1000
using namespace std;
typedef struct{
int data[max];
int length;
}sqlist;
void Initlist(sqlist*&l){
l=(sqlist*)malloc(sizeof(sqlist));
l->length=0;
}
void Destorylist(sqlist*&l){
free(l);
}
bool Emptylist(sqlist*&l){
return (l->length==0);
}
int Lengthlist(sqlist*&l){
return l->length;
}
void Displist(sqlist*&l){
for(int j=0;j<l->length;j++){
cout<<l->data[j]<<" ";
}
}
int Locatelist(sqlist*&l,int x){ //查找x在表中的位置,没找到则返回false
for(int j=0;j<l->length;j++){
if(l->data[j]==x)
return j;
}
return false;
}
bool Insertlist(sqlist*&l,int i,int x){ //这里插入的数据必须为整型,i为插入的位置(从0开始),x为插入的数据值
int j;
if(i<0||i>l->length)
return false ;
for(j=l->length;j>=i;j--)
l->data[j+1]=l->data[j];
l->data[i]=x;
l->length++;
return true;
}
bool Deletelist(sqlist*&l,int i){
int j;
if(i<0||i>l->length-1)
return false;
for(j=i;j<l->length-1;j++)
l->data[j]=l->data[j+1];
l->length--;
return true;
}
//算法的时间复杂度为0(n),空间复杂度为o(1)
void movelist(sqlist*&l){
int i=-1,j;
for(j=0;j<=l->length;j++){
if(l->data[j]%2!=0){
i++;
if(i!=j)
swap(l->data[j],l->data[i]);
}
}
}
int main(){
sqlist*l;
//先初始化表,这里我是用自己写的表做的
Initlist(l);
Insertlist(l,0,3);
Insertlist(l,1,8);
Insertlist(l,2,2);
Insertlist(l,3,7);
Insertlist(l,4,1);
Insertlist(l,5,5);
Insertlist(l,6,3);
Insertlist(l,7,4);
Insertlist(l,8,6);
Insertlist(l,9,0);
movelist(l);
Displist(l);
}
3 7 1 5 3 8 2 4 6 0 ——————————– Process exited after 2.87 seconds with return value 0 请按任意键继续. . .