有意思的线性表操作(捡起我遗忘多年的c语言)

线性表是数据结构这门课程最开始讲的内容,也是平常写程序中最常用到得数据结构.下面就写一下一些有意思的线性表操作.

线性表的定义

在操作线性表之前,我先定义一下线性表的结构,方便之后看一些操作,阅读代码:

线性表的数据结构定义

1
2
3
4
typedef struct{
int *data;
int length ;
}List,*ListPoint;

线性表的基本操作

初始化一个线性表

1
2
3
4
5
6
7
8
9
10
void initList(List &list){
//初始化线性表
int i;
list.data = new int[MAX_LENGTH];
srand(int(time(0)));
for(i=0;i<10;i++){
list.data[i]=random(10);
}
list.length = i;
}

打印一个线性表中的元素

1
2
3
4
5
6
7
8
9
10
11
12
void printList(List &list){
/*
打印自身
*/
int i=0;
cout<<"the length of the list:"<<list.length<<endl;
cout<<"the num of the list:";
for(i=0;i<list.length;i++){
cout<<list.data[i]<<" ";
}
cout<<endl;
}

对线性表元素从小到大进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void sortList(List &list){
/*
利用冒泡法对元素进行排序
从小到达排列
*/
int i,j;
for(i=list.length-1;i>0;i--){
for(j=0;j<i;j++){
if(list.data[j]>list.data[j+1]){
list.data[j] = list.data[j+1]^list.data[j];
list.data[j+1] = list.data[j+1]^list.data[j];
list.data[j] = list.data[j+1]^list.data[j];
}
}
}
}

具体的操作要求

用空间复杂度为O(1),和时间复杂度为O(n)的算法,实现线性表的倒置

其实就是第一个与最后一个交换位置,第二个和倒数第二个交换位置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool reverseList(List &list){
/*
用空间复杂度为1的算法,实现list 倒置
*/
if(list.length==0) return false ;

int i=0 ;
for(i=0;i<list.length/2;i++){
/*
list.data[i] 与 list.data[list.length-1-i] 交换
*/
list.data[i] = list.data[i]^list.data[list.length-1-i];
list.data[list.length-1-i] = list.data[i]^list.data[list.length-1-i];
list.data[i] = list.data[i]^list.data[list.length-1-i];

}
return true;
}

用空复杂度为O(1)和时间复杂度为O(n)的算法,删除线性表所以值为x的元素

从头开始遍历线性表,用pos记录当前的线性表的长度,如果当前扫描的元素值不是x,就将他加入到线性表中,并且pos+1,如果是x,就什么也不做.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool deleteList(List &list,int x){

/*
在线性表中删除所有值为 x 的元素
要求空间复杂度为 o(1) , 时间复杂度为 o(n)
*/

if(list.length==0) return false ;
int pos=0,i=0;
for(i=0;i<list.length;i++){
if(list.data[i]!=x){
list.data[pos]=list.data[i];
pos++;
}
}
list.length = pos; //更新一下线性表的长度
return true ;
}

要求算法时间复杂度 O(n) 空间复杂度 O(1)的算法删除有序的线性表中值位于 s 和 t之间的元素.包含s和t

注意这里讲的是有序的表,那么值位于s和t之间的元素肯定是连在一起的
所以我们只需要找到第一个该删的元素,和最后一个该删的元素,就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool deleteListSection(List &list,int s,int t){
/*
删除 有序表 list中 处于 s和t之间的元素,包含 s和t
*/
if(s>=t || list.length==0) return false ;
sortList(list); //先进行排序,然后再操作
int i=0,j=list.length-1;
while( (i<list.length) && list.data[i]<s ) i++; // 找到第一个需要删除的
while( j>-1 && list.data[j]>t) j--; //找到最后一个要删除的元素
for(j=j+1;j<list.length;j++,i++){
list.data[i] = list.data[j];
}
list.length = i;
return true ;
}

要求算法时间复杂度 O(n) 空间复杂度 O(1)的算法删除无序的线性表值位于s和t之间的元素,包含s和t

从头开始扫描顺序表,用 k 记录下在s 与 t 之间的个数(初始值 k=0) ,对于当前要扫描的元素 如果值不在 s和t之间,则前移 k 个位置 ,如果在 s和t之间 ,就 k++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool deleteListSectionNoSort(List &list,int s,int t){
/*
删除顺序表中(无序的) 处于 s和t之间的元素
要求算法时间复杂度 O(n) 空间复杂度 O(1)
*/
if(s>=t || list.length==0) return false ;
/*
从头开始扫描顺序表,用 k 记录下在s 与 t 之间的个数(初始值 k=0) ,对于当前要扫描的元素
如果值不在 s和t之间,则前移 k 个位置 ,如果在 s和t之间 ,就 k++
*/
int i;
int k=0;
for(i=0;i<list.length;i++){
if(list.data[i]>=s && list.data[i] <=t){
k++;
}else{
list.data[i-k] = list.data[i];
}

}
list.length = list.length - k;

return true ;
}

删除有序的顺序表中重复的元素,使剩下来的元素都不相同

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void  deleteRepeate(List &list){
/*
在有序表中删除重复的元素,使剩下的元素都不相同
注意是有序表
*/
int i ;
int k=0 ;
for(i=0;i<list.length-1;i++){

if(list.data[i]==list.data[i+1])
{
k++;
}
else{
list.data[i-k] = list.data[i];
}
}
list.length = list.length - k ;
}

第二种思路

1
2
3
4
5
6
7
8
9
10
11
12
void deleteRepeate_2(List &list){
/*
删除有序表重复元素的第二种算法
*/
int i,j;
for(i=0,j=1;j<list.length;j++){
if(list.data[i]!=list.data[j]) {
list.data[++i] = list.data[j] ; // 注意是 先加再拷贝
}
}
list.length = i+1;
}

合并两个有序的顺序表到一个有序的顺序表中去

经典算法,应该都会

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool mergeList(List &lista,List &listb,List &list){
/*
合并两个有序的 顺序表到一个顺序表中.
*/
if(lista.length+listb.length>MAX_LENGTH) return false ;
int i=0,j=0,k=0 ;
while(i<lista.length&&j<listb.length){
if(lista.data[i]<listb.data[j])
list.data[k++]=lista.data[i++];
else
list.data[k++] = listb.data[j++];
}

while(i<lista.length)
list.data[k++] = lista.data[i++];
while(j<listb.length)
list.data[k++] = listb.data[j++];

list.length = lista.length+ listb.length ;
return true;
}

在 一个 顺序表 A[m+n]中存放着两个线性表 (a1,a2,a3,…,am) 和 (b1,b2,b3,….bn) 这里将 顺序表的前后位置互换 ,变为 (b1,b2,b3,….bn)和 (a1,a2,a3,…,am)

参照前面 reverseList 的方法 ,先把 (a1,a2,a3…am)变为 (am,am-1,am-2,…a3,a2,a1) ,对b也进行这样的处理 , 顺序表就变为(am,am-1,…,a3,a2,a1)(bn,bn-1,bn-2,…,b3,b2,b1), 然后在对整体做一个倒置,就变为 (b1,b2,b3,…,bn)(a1,a2,a3,…,an)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
	bool  reverseListScope(List &list, int left ,int right){
/*
这里的left right 都是顺序表的下标

实现把 (left,left+1,left+2...right) 变为 (right,...,left+2,left+1,left)
*/
if(left>=right || right >=list.length) return false ;
int mid = (left+right+1)/2;
int i;
for(i=left;i<mid;i++){
/*
交换 list.data[i] 和 list.data[right-i+left]
*/
list.data[i] = list.data[i]^list.data[right-i+left];
list.data[right-i+left] = list.data[i]^list.data[right-i+left];
list.data[i] = list.data[i]^list.data[right-i+left];
}
return true;
}

1
2
3
4
5
6
void exchangeList(List &list,int m ,int n){

reverseListScope(list,0,m-1);
reverseListScope(list,m,m+n-1);
reverseListScope(list,0,m+n-1);
}

用最短的时间在有序的顺序表中找到元素x,如果找到 ,就让其与与他后面的那个元素交换位置,如果没有找到,就把他插入到合适位置,保持顺序表递增有序

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
void searchExchangeInsert(List &list,int x){

int low=0,high = list.length-1,mid;
while(low<=high){
mid = (low+high)/2;
if(list.data[mid]==x) break;
if(list.data[mid]<x) low = mid+1;
if(list.data[mid]>x) high = mid-1;
}

/*
如果存在 ,且不是 最后一个 ,则与他后面一个位置互换
*/
if(list.data[mid]==x && mid!= list.length-1){
// list.data[mid] 和 list.mid[i+1] 互换
list.data[mid] = list.data[mid]^list.data[mid+1];
list.data[mid+1] = list.data[mid]^list.data[mid+1];
list.data[mid] = list.data[mid]^list.data[mid+1];
}
int i;

if(low>high){
for(i=list.length-1;i>high;i--){
list.data[i+1]=list.data[i];
}
list.data[i+1] = x;
list.length++;
}
}

用空间和时间复杂度最低的算法,实现顺序表循环左移 n 位

例如 1234 循环左移2位,其实就是 3412,其实前面已经写过了,只是参数不太一样
我们可以将 12 变为 逆序变为 21,然后 34 逆序变为43,再把整体 2143 逆序,就变为 3412 了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void shiftLeft(List &list,int n){

/*
将顺序表循环左移 n 位
例如 1234 循环左移2位,其实就是 3412
其实前面已经写过了
我们可以将 12 变为 逆序变为 21,然后 34 逆序变为43,再把整体 2143 逆序,就变为 3412 了
*/
// 跟exchangeList 实现的功能一样
reverseListScope(list,0,n-1);
reverseListScope(list,n,list.length-1);
reverseListScope(list,0,list.length-1);

}