【数据结构与算法】【考研】（三）：线性表——顺序表编程练习题_数据结构顺序表例题

顺序表编程题目（基础部分）

目录

1.数据元素的移动

2.数据元素的删除  

3.数据元素的插入

4.两个有序顺序表的合并

---

---

1.数据元素的移动

A）设顺序表无序且不含有重复值，将所有偶数移至奇数之前

例如：a={3,2,5,8,4,7,6,9}

结果：a={6 2 4 8 5 3 7 9}

       备注：结果不唯一，只要保证偶数在前技术在后即可

  分析：咱们是将偶数移动到奇数之前，也就是说，要把前面的奇数移动到后面，后面的偶数移动的前面，这个时候我就想到了快速排序，快速排序是大小，咱们这里改成奇偶，也就是说咱们要在前部分虚招一个奇数，后半部分找一个偶数，两者交换，当一次遍历完成所有偶数就到奇数前面了。

自己创作代码如下

int main()
{
	int a[8] = {3,2,5,8,4,7,6,9};
	int n = sizeof(a)/sizeof(a[0]);
    int i,j;
    for(int i=0,j=n-1;i < j;){
    	if((a[i]%2) == 1 &&(a[j]%2) == 0){
    		int t = a[i];
    		a[i] = a[j];
    		a[j] = t;
			i++;
			j--; 
		}else if((a[i]%2) == 0 &&(a[j]%2) == 0){
			i++;
		}else if((a[i]%2) == 1 &&(a[j]%2) == 1){
			j--;
		}else{
			i++;
			j--;
		}	
	}
	for(int i = 0; i<n ;i++){
		printf("%d ",a[i]);
	}
	return 0;
}

代码分析：分了四种情况

前奇数后偶数  交换

前偶数后偶数  前继续寻找奇数

前奇数后奇数  后继续寻找偶数

前偶数后奇数  前后继续寻找

标准答案

void Move(int a[],int n)
{
	int i,j;
	i=0;
	j=n-1;
	while(i<j){
		while(i<n&&a[i]%2==0) i++;
		while(j>-1&&a[j]%2) j--;
		if(i<j){
			int t = a[i];
    		a[i] = a[j];
    		a[j] = t;
		}
	}
}

代码分析：老师的代码在我看来思路和我的一直都是寻找奇偶进行交换，但是很明显比我的优化很多，首先在遍历中从千米按先找到一个奇数，然后从从后面找到一个偶数，是单独找，我的是同时找。

B. 将一个字符串从中间一分为二，前半段和后半段按顺序交换

、若有奇数个字符，中间字符不参与 

   例如：H  a  p  p  I  n  e  s  s  \0

         n  e  s  s  I  H  a  p  p  \0

         C  o  c  a  C  o  l  a  \0

         C  o  l  a  C  o  c  a  \0

分析：虽然说是前半段和后半段互换，其实是将前半段移动到了后面，可以采取一个一个移动的办法，也可以采取我下面这个，将整个数组逆置，此时咱们想要的前半段，已经到了后面，只不过顺序仍然是反的，再将前半段后后半段分别翻回来就可以了

代码如下：

#include<stdio.h>
void exchange(char a[],int l,int h){
	int i,j;
	for(i = l,j = h;i<j;i++,j--){
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}
}
int main()
{
	//char a[10]={'H','a','p','p','I','n','e','s','s','\0'};
	//H  a  p  p  I  n  e  s  s  \0
	char a[9] = {'C','o','c','a','C','o','l','a','\0'};
	//C  o  c  a  C  o  l  a  \0
	int n = sizeof(a)/sizeof(a[0]) - 1;
	exchange(a,0,n-1);
	exchange(a,0,n/2-1);
	exchange(a,((n%2==1)?(n/2+1):(n/2)),n-1);
	for(int i = 0;i<n;i++){
		printf("%c ",a[i]);
	}
	return 0;
}

标准答案

void Move(char a[],int n)
{
	int i,j;
	for(i = (n-1)/2,j=n-1;i>-1;i--,j--){
		int t=a[i];
		a[i]= a[j];
		a[j]= t;
	}
}

2.数据元素的删除  

设顺序表满足：

A.  无需无重复值，删除关键字为key的数据元素

分析：找到它，删除它。

int del(int a[],int n,int k){
	int i,j;
	for(i = 0;i<n&&a[i]-k;i++);
	if(n==i){
		printf("not found \n");
		return n; 
	}
	for(j = i; j < n-1;j++){   //for(j = i ;j<n-1&&(a[j]=a[j+1],1);j++); 作为代替 
		a[j] = a[j+1];
	}
	n--;
	return n;
}

B.  无序有重复值，删除关键字为key的数据元素   

分析：想象成两个数组，不是key就从a挪移到新的数组b，其实可以用一个数组，把后面是不是key的对前面是key的进行覆盖。

int del(int a[],int n,int key)
{
	int i,j;
	for(i = 0,j = 0;i < n ;i++){
		if(a[i]-key){
			a[j++] = a[i];
	}
	}
	return j;
}

C.  有序有重复值，删除关键字为key的数据元素

分析：寻找关键字一个范围，进行移动和删除一个数据元素类似的移动。

int del(int a[],int n,int k){
	int i,j,x,y;
	for(i = 0;i <n && a[i]-k;i++);
	for(j = n-1 ;j>-1&& a[j] - k;j--);
	for(x = i,y=j+1; y < n;x++,y++){
		a[x] = a[y];
	}
	n = n-(j-i+1);
	return n;
}

D.  有序有重复值  删除重复值元素

分析：类似于去重操作，遍历是从1开始的并且采用了++j，巧妙地跳过了第一个元素，因为是有序的，只要发现和当前的a[j]不同，就证明数变大了，就挪移到新的数组中去，其实是一个数组覆盖操作。

int del(int a[],int n){
	int i,j;
	for(i = 1,j=0;i<n;i++){
		if(a[i]-a[j]){
			a[++j]=a[i];
		}
	}
	return j+1;
}

例如：2 2 2 3 3 4 4 4 5 5

      2 3 4 5

3.数据元素的插入

顺序表数据元素升序有序，将关键字key插入到顺序表中是顺序表依然有序

分析：找到对应数据元素，对应元素以及后边的元素全部后移一个单位，然后插入。

int Insert(int a[],int n,int k)
{
	int i,j;
	for(i = 0;i < n && a[i] < k;i++);
	if(n<i){
		for(j = n;j > i;j--){
		a[j] = a[j-1];
		}
		a[i] = k;
		n++;	
	}
	return n;
}

4.两个有序顺序表的合并

A   设顺序表A 和B 是两个升序有序的顺序表且不含有重复值，将A和B 合并城一个顺序表C且不含重复值    

分析：合并操作我最先想到了归并排序，但是两个合并之后会有重复值，所以采取了去重，应该在合并中过程中应该也可以去重。

代码如下

int hebing(int a[],int m,int b[],int n,int t[])
{
	int i=0,j=0,k=0;
	while(i<m&&j<n){
		if(a[i]<b[j]){
			t[k++] = a[i++];
		}else{
			t[k++] = b[j++];
		}
	}
	while(i<m)  t[k++] = a[i++];
	while(j<n)  t[k++] = b[j++];
	for(i = 1,j=0;i<k;i++){
		if(t[i]-t[j]){
			t[++j]=t[i];
		}
	}
	return j+1;
}

标准答案：

int hebing2(int a[],int n,int b[],int m,int t[])
{
	int i=0,j=0,k=0,x;
	while(i<n || j<m){
		if(j>=m || i<n&&a[i]<b[j]){
			x = a[i++];
		}else{
			x = b[j++];
		}
		if(k==0){
			t[k++]=x;
		}else{
			if(t[k-1]-x){
				t[k++] = x;
			}
		}
	}
	return k;
}

分析：首先将数组中的值存到x中，通过判断实现去重写入，而关于a和b数组谁先遍历完成的问题，假设a先遍历完成，那么j<m仍然会进入while，并且j没有大于等于m或者i小于n，而且a已经不存在（i==n），所以走else实现b的写入；而b先遍历完成，会符合j>=m，会一直写入a数组，直到i==n，不在进入循环。

while(数组a或者数组b还有没有写入）{

if（数组b写完了   ||   存在a[i]并且a[i]<b[j]）  //一开始肯定b没有写完。

        {a写入}

else

        {b写入}

}