音乐分享：
Collapsing World
点击收听

基本知识点

1、顺序表的存储密度大、可以随机存取
2、插入操作的合法位置为0到n
3、插入运算的平均移动数据元素的次数是：n/2

推导：合法的插入位置有n+1个
假设每个位置插入元素的概率都为：1/(n+1)
那么：0+1+2+...+(n-1)+n = (n+1)*n/2 
最后可得：n/2

4、删除操作的合法位置为0到n-1
5、删除运算的平均移动数据元素的次数是：(n-1)/2

推导：合法的删除位置有n个
假设每个位置插入元素的概率都为：1/n
那么：0+1+2+...+(n-2)+(n-1) = (n-1)/2 
最后可得：(n-1)/2

6、逆置操作：进行n/2次的交换

基本操作

1、查找

for(int i=0;iif(value == data[i])return i;
}
return -1; 

2、插入
从后往前走，将当前的数据元素放到其后一个位置
最后在i的位置处空下一个位置，将value放入即可

for(int j=curlength;j>i;j--)
{data[j] = data[j-1];
}
data[i] = value;
curlength++;

3、删除
从前往后走，从i开始将其后一个位置的value放到当前位置

for(int j=i;jdata[j] = data[j+1];
}
curlength--;

4、逆置
无论是奇数个元素还是偶数个元素都是n/2次

int temp = 0;
for(int i=0;itemp = data[i];data[i] = data[curlength-i-1];data[curlength-i-1] = temp;
}

题目练习1

1、存在顺序表A和B，其元素均按从小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。

算法代码

#define MAXSIZE 111typedef struct{int elem[MAXSIZE];int last;
}SeqList;void MergeSeqList(SeqList A,SeqList B,SeqList* C)
{int i = 0;	int j = 0;	int k = 0;	//last表示顺序表中最后一个元素在数组中的位置 while(i<=A.last&&j<=B.last){if(A.elem[i]<=B.elem[j]){C->elem[k++] = A.elem[i++];}else{C->elem[k++] = B.elem[j++];}}while(i<=A.last){C->elem[k++] = A.elem[i++];}while(j<=B.last){C->elem[k++] = B.elem[j++];}C->last = k-1;
} 
//时间复杂度：O(A.last+B.last)

题目练习2

2、顺序表A和B的元素都是非递减有序，将B表中的元素合并到A表中，使新的A表中的元素仍然保持非递减有序。

算法代码

//m和n分别为A和B表的长度
int m = 0;
int n = 0;int i = 0;
int j = 0;
int k = 0;m = A.curlength;
n = B.curlength;//k为合并之后的表的最后一个位置
//i和j分别为A表和B表的最后一个位置
k = m+n-1;
i = m-1;
j = n-1;//如果A表的空间不够了，可以扩容或者直接退出 
if((m+n)>A.MaxSize)
{//可以扩容或者退出 
} //核心步骤
while(i>=0&&j>=0)
{if(A.data[i]>=B.data[j]){A.data[k--] = A.data[i--];}else{A.data[k--] = B.data[j--];}
}//如果A表先遍历完成，就需要将B表剩余元添加到A表当中
//如果B表先遍历完成，就不需要操作，因为A表剩余元素就在A表当中
while(j>=0)
{A.data[k--] = B.data[j--];
}//最后合并之后的A表长度为m+n
A.curlength = m+n;//时间复杂度为:O(m+n) 

题目练习3

3、已知长度为n的线性表A采用顺序存储结构，写出时间复杂度为O(N)、空间复杂度为O(1)的算法，用来删除线性表中所有值为item的数据元素。

算法代码

//方法一：会改变数据元素之间的相对位置 
//样例：1 3 5 3 2 3 
int i = 0;
int j = curlength-1;while(i<=j)
{//从头开始找值为item的元素 while(i<=j&&alist[i]!=item)i++;//从尾开始找值不为item的元素 while(i<=j&&alist[j]==item)j++;if(ialist[i++] = alist[j--];}
}curlength = i;
---
//如果要求保持数据元素之间的相对顺序不改变
//方法二：
int i = 0;
int j = 0;while(jif(alist[j] == item)j++;elsealist[i++] = alist[j++];	//最后顺序表中的数据元素个数为i 
} 

循环左移和循环右移

循环左移(从头到尾、从左到右)

在数组r(长度为n，n>1)中保存的序列循环左移p个位置(0 原来数组：[1 2 3 4 5 6 7] p = 3
移动之后的数组：[4 5 6 7 1 2 3]

算法

1、逆置0到p-1
2、逆置p到n-1
3、逆置0到n-1

代码实现

int t = 0;//逆置0到p-1 
for(int i=0;i
t = r[i];r[i] = r[p-i-1];r[p-i-1] = t;
}//逆置p到n-1
for(int i=0;i<(n+p)/2;i++)
{t = r[i];r[i] = r[(n+p)-i-1];r[(n+p)-i-1] = t;
}//逆置0到n-1
for(int i=0;it = r[i];r[i] = r[n-i-1];r[n-i-1] = t;
}

循环右移(从尾到头、从右到左)

题目来源
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

原来数组：[1 2 3 4 5 6 7] k = 3
移动之后的数组：[5 6 7 1 2 3 4]

代码实现

//逆置函数
void reverse(int* nums,int left,int right)
{while(leftint temp = nums[left];nums[left] = nums[right];nums[right] = temp;left++;right--;}return ;
}void rotate(int* nums, int numsSize, int k){//如果k大于numsSizeif(k>=numsSize)k = k%numsSize;reverse(nums,numsSize-k,numsSize-1);reverse(nums,0,numsSize-k-1);reverse(nums,0,numsSize-1);return ;
}

总结

相同的算法、两种操作