数据结构之顺序表（数组）

60 阅读 0 评论 40 点赞

我是靠谱客的博主搞怪大雁，最近开发中收集的这篇文章主要介绍数据结构之顺序表（数组），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

本学期带数据结构，那就索性复习下C语言，把所写的代码记录下来

题目如下：

1.	两个有序的顺序表A和B，包含的元素个数分别为m与n，设计一算法实现B=AUB
2.	设计一个算法从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变
3.	设计一高效算法删除顺序表中值为x的所有元素

代码如下：

</pre><pre class="cpp" name="code">写惯了JAVA，Python，要注意C语言没法动态构建数组，必须先申请数组空间，其次声明要写在最前面。

#include <stdio.h>
#include <stdlib.h>

#define len 100			//数组长度
#define endflag -99		//结束标记

//获得数组，返回长度
int getArray(int *p){
	int length =0;
	int i = 0;
	for(scanf("%d",&i);i!=endflag;scanf("%d",&i))
    {
		*p++ = i;
        length++;
    }
    return length;
}

//输出数组
void printArray(int *p, int length){
	int i;
	printf("数组：");
    for(i=0;i<length;i++)
		printf("%d  ",*(p+i));
    printf("n");
}

//有序数组的并集
int ArrayUnion(int *a,int A_len,int *b,int B_len,int *out){
	int *p,pLen,aLen,bLen;
    p = out;
	pLen = aLen = bLen = 0;

    while(aLen != A_len && bLen != B_len){
            
		if(aLen < A_len && bLen < B_len){
			if(*a > *b){
				 *p = *b;
				 b++;bLen++;
			}else if(*a == *b){
				*p = *b;
				a++;b++;
				aLen++;bLen++;
			}else{
				*p = *a;
				a++;aLen++;
			}
			p++;pLen++;
		}
        
        if(aLen<A_len && bLen == B_len){
				*p = *a;
				a++;aLen++;
				p++;pLen++;
        }
		
        if(aLen==A_len && bLen < B_len){
				*p = *b;
				 b++;bLen++;
				 p++;pLen++;
        }
		
    }
    
    return pLen;
}

// 删除数组的第k个元素
int ArrayDelElem(int *arr,int length,int k){
	int i;

	if(k>length) return 0;

	for(i=k;i<length;i++){
		arr[i] = arr[i+1];
	}
	return length - 1 ;
}

//删除数组中的j-k个元素
int ArrayDelRange(int *arr,int length,int j,int k){
	int i,range;
	range = k-j;

	if(k>length) return 0;

	for(i=j;i<length - range;i++){
		arr[i] = arr[i+range+1];
	}
	return length - range - 1 ;
}

//顺序表去重复，返回数组长度
int distinct(int *arr,int length){
	int i,k,reLen;
	k = 1;					//去除元素的个数
	reLen = length;

	for(i=0;i<length - k ;i++){
		if(arr[i] == arr[i+1]){
			reLen = ArrayDelElem(arr,reLen,i+1);
			k++;
			i--;  //抵消++的作用，从这个数继续往下比
		}
	}
	return reLen;
}

//删除顺序表中所有值为X的元素
int ArrayDelX(int *arr,int length,int x){
	int i,PreIndex,AfterIndex;

	for(i=1;i<length;i++){
		if(arr[i-1] < x){
			if(arr[i] == x) PreIndex = i;
		}else if(arr[i-1] == x){
			if(arr[i] > x){
				AfterIndex = i-1;
				break;
			}
		}
	}

	return ArrayDelRange(arr,length,PreIndex,AfterIndex);
}

int main()
{

    int A[len],A_len; 

    printf("请输入数组A，输入%d结束：n",endflag);
    A_len = getArray(A);
    //A_len = distinct(A,A_len);  	//第二题
    A_len = ArrayDelX(A,A_len,2);   //第三题
    printArray(A,A_len);

	/*//第一题
    int *out,k[2*len],A_len,B_len,outlen;
    int A[len],B[len]; 
    out = k;

    printf("请输入数组A，输入%d结束：n",endflag);
    A_len = getArray(A);
    printf("请输入数组B，输入%d结束：n",endflag);
    B_len = getArray(B);
    
    outlen = ArrayUnion(A,A_len,B,B_len,out);
    printArray(out,outlen);
	*/

    return 0;
}