音乐分享：
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;i<curlength;i++)
{
	if(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;j<curlength-1;j++)
{
	data[j] = data[j+1];
}
curlength--;

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

int temp = 0;
for(int i=0;i<curlength/2;i++)
{
	temp = data[i];
	data[i] = data[curlength-i-1];
	data[curlength-i-1] = temp;
}

题目练习1

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

算法代码

#define MAXSIZE 111

typedef 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(i<j)
	{
		alist[i++] = alist[j--];
	}
}

curlength = i;
---
//如果要求保持数据元素之间的相对顺序不改变
//方法二：
int i = 0;
int j = 0;

while(j<n)
{
	if(alist[j] == item)
		j++;
	else
		alist[i++] = alist[j++];	
	//最后顺序表中的数据元素个数为i 
} 

---

循环左移和循环右移

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

在数组r(长度为nn>1)中保存的序列循环左移p个位置(0<p<n)。
原来数组：[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<p/2;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;i<n/2;i++)
{
	t = 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(left<right)
    {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++;
        right--;
    }
    return ;
}


void rotate(int* nums, int numsSize, int k){
    //如果k大于numsSize
    if(k>=numsSize)
        k = k%numsSize;
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-k-1);
    reverse(nums,0,numsSize-1);
    return ;
}

总结

相同的算法、两种操作