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

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

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

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#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;
}