线性表的顺序存储结构（数组实现）
自己写的线性表
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
//顺序表（数组实现） //要实现的操作有：初始化表：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 插入链表中 } |
教材上的标准顺序表
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
//顺序表基本运算算法 #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(){ } |
例2.4 有一个顺序表L，假设元素类型是整型，设计一个尽可能高效的算法，以第一个元素为分界线（基准），将所有小于等于它的元素移到该基准的前面，将所有大于它的元素移到该基准的后面。
自己写的
我的想法很简单，只需要从左向右扫描比基准小于等于的数和从右向左扫描大于基准的数，当扫描到则立刻交换，继续扫描，直到两个扫描的标杆相遇。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
//假设这个顺序表的数为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
请按任意键继续. . .
我也就想到了这么一个办法，接下来看看书上给的方法吧。
书上的第一种解法思想和我的差不多，来看第二种
基本思想，i和j分别两个标杆，从表头和表尾出发，设i从左向右找比基准数大于的数，当找到时候将这个数给标杆j，然后标杆j从右向左找小于等于基准的数，当找到的时候给标杆i，当碰面后即停止循环。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
//这个算法必须先从右向左扫描，此外这个算法是快速排序的过程 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; } |
有一个顺序表L，假设元素类型为整型，设计一个尽可能高效的算法，将所有的奇数移到到偶数的前面。
为了节约时间，我直接看了书上的两种解法
解法一：类似上面一题的解法一
解法二：标杆i取-1不动，标杆j从从左向右寻找奇数，当找到时直接交换两个标杆的值，标杆j到数组最后长度时，循环结束
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
//第一种解法和之前类似，不写了 //假设这个顺序表的数为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
请按任意键继续. . .
