数据结构：顺序表

SeqList.h

#pragma once
#include
#include
#include

typedef int SLDataType;
//#define NULL 0

typedef struct SeqList {
	SLDataType* a;
	int size;//顺序表中存储的有效元素的个数
	int capacity;//空间的大小
}SL;

void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SPrint(SL* ps);

void SLPopBack(SL* ps);
void SLPushBack(SL* ps,SLDataType x);
void SLCheckCapacity(SL* ps);

void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);

void SLInsert(SL* ps, int pos, SLDataType x);
int SLFind(SL* ps, SLDataType x);
void SLErase(SL* ps, int pos);
void SLModify(SL* ps, int pos, SLDataType x);
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

SeqList.c

#include"SeqList.h"

void SLInit(SL* ps) {
	assert(ps);
	ps->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (ps->a == NULL) {
		perror("malloc failed");
		exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
}

void SLDestroy(SL* ps){
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SPrint(SL* ps) {
	assert(ps);
	for (int i = 0; i < ps->size; i++) {
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SLPopBack(SL* ps) {
	assert(ps);
	//assert(ps->size > 0);
	//ps->size--;
	SLErase(ps, ps->size-1);
}

void SLPushBack(SL* ps, SLDataType x) {
	assert(ps);
	//SLCheckCapacity(ps);
	//ps->a[ps->size] = x;
	//ps->size++;
	SLInsert(ps, ps->size-1, x);
}

void SLCheckCapacity(SL* ps) {
	assert(ps);
	if (ps->size == ps->capacity) {
		SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));
		if (tmp == NULL) {
			perror("realloc failed");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = ps->capacity * 2;
	}
}

void SLPushFront(SL* ps, SLDataType x) {
	assert(ps);
	//SLCheckCapacity(ps);
	//int end = ps->size - 1;
	//while (end >= 0) {
	//	ps->a[end + 1] = ps->a[end];
	//	--end;
	//}
	//ps->a[0] = x;
	//ps->size++;
	SLInsert(ps, 0, x);
}

void SLPopFront(SL* ps) {
	assert(ps);
	//assert(ps->size > 0);
	//int begin = 1;
	//while (begin < ps->size) {
	//	ps->a[begin - 1] = ps->a[begin];
	//	++begin;
	//}
	//ps->size--;
	SLErase(ps, 0);
}

void SLInsert(SL* ps, int pos, SLDataType x) {
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheckCapacity(ps);

	int end = ps->size - 1;
	while (end >= pos) {
		ps->a[end + 1] = ps->a[end];
		--end;
	}
	ps->a[pos] = x;
	ps->size++;
}

int SLFind(SL* ps, SLDataType x) {
	assert(ps);
	for (int i = 0; i < ps->size; i++) {
		if (ps->a[i] == x) {
			return i;
		}
	}
	return -1;
}

void SLErase(SL* ps, int pos) {
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	int begin = pos + 1;
	while (begin < ps->size) {
		ps->a[begin - 1] = ps->a[begin];
		++begin;
	}
	ps->size--;
}

void SLModify(SL* ps, int pos, SLDataType x) {
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}
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

移除元素

int removeElement(int* nums, int numsSize, int val){
    int n = numsSize;
    int begin = 0;
    int end = 0;
    while(begin<n){
        if(nums[begin]!=val){
            nums[end] = nums[begin];
            end++;
            begin++;
        }else{
            begin++;
        }
    }
    return end;    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

合并两个有序数组

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int end1 = m-1;
    int end2 = n-1;
    int end = n+m-1;
    
    while(end1>=0 && end2>=0){
        if(nums1[end1]>=nums2[end2]){
            nums1[end] = nums1[end1];
            end--;
            end1--;
        }else{
            nums1[end] = nums2[end2];
            end--;
            end2--;
        }
    }
    while(end2>=0){
        nums1[end--] = nums2[end2--];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21