顺序表的基本操作代码实现

78 阅读 0 评论 52 点赞

我是靠谱客的博主哭泣刺猬，这篇文章主要介绍顺序表的基本操作代码实现，现在分享给大家，希望可以做个参考。

顺序表：顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。即线性表采用顺序存储的方式存储就称之为顺序表。

下面直接上代码：

复制代码

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

 //SeqList.h

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

typedef int SLdatatype;

typedef struct SeqList
{
	SLdatatype *a;//存储数据空间的指针
	int capacity;//容量空间大小
	int size;//有效数据个数
}SeqList;

void SeqListInit(SeqList *psl);//初始化
void SeqListDestroy(SeqList *psl);//删除
void SeqListPrint(SeqList *psl);//输出
void SeqListPushBack(SeqList *psl, SLdatatype x);//尾插
void SeqListPushFront(SeqList *psl, SLdatatype x);//头插
void SeqListPopBack(SeqList *psl);//尾删
void SeqListPopFront(SeqList *psl);//头删
void SeqListInsert(SeqList *psl, int pos, SLdatatype x);//按位置插入元素
void SeListErase(SeqList *psl, int pos);//按位置删除元素

复制代码

//SeqList.c

#include"SeqList.h"

void SeqListInit(SeqList *psl)
{
	psl->a = (SLdatatype*)malloc(sizeof(SLdatatype)*4);
	if (psl->a == 0){
		printf("malloc failn");
		exit(-1);
	}
	memset(psl->a, 0, sizeof(SLdatatype) * 4);
	psl->size = 0;
	psl->capacity = 4;
}

void SeqListDestroy(SeqList *psl)
{
	free(psl->a);
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

void SeqListPrint(SeqList *psl)
{
	for (int i = 0; i < psl->size; i++){
		printf("%d ", psl->a[i]);
	}
	printf("n");
}

void CheckCapacity(SeqList* psl)
{
	if (psl->size == psl->capacity){
		SLdatatype *b = (SLdatatype*)realloc(psl->a, sizeof(SLdatatype)*psl->capacity * 2);
		if(b == NULL){
			printf("malloc failn");
			exit(-1);
		}
		psl->a = b;
		psl->capacity = psl->capacity * 2;
	}
}

void SeqListPushBack(SeqList *psl, SLdatatype x)
{
	    assert(psl);
		CheckCapacity(psl);
        psl->a[psl->size] = x;
	    psl->size++;

}

void SeqListPushFront(SeqList *psl, SLdatatype x)
{
	assert(psl);
	CheckCapacity(psl);
	for (int i = psl->size; i >0; i--){
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[0] = x;
	psl->size++;
}

void SeqListPopBack(SeqList *psl)
{
	assert(psl);
	assert(psl->size > 0);
	psl->size--;
}

void SeqListPopFront(SeqList *psl)
{
	assert(psl);
	assert(psl->size > 0);
	for (int i = 0; i < psl->size; i++){
		psl->a[i] = psl->a[i + 1];
	}
	psl->size--;
}

void SeqListInsert(SeqList *psl, int pos, SLdatatype x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	CheckCapacity(psl);
	int i;
	for (i = psl->size; i>=pos; i--){
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[pos] = x;
	psl->size++;
}

void SeListErase(SeqList *psl, int pos)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	for (int i = pos+1; i < psl->size; i++){
		psl->a[i - 1] = psl->a[i];
	}
	psl->size--;
}

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

 //SeqList.c

#include"SeqList.h"

void SeqListInit(SeqList *psl)
{
	psl->a = (SLdatatype*)malloc(sizeof(SLdatatype)*4);
	if (psl->a == 0){
		printf("malloc failn");
		exit(-1);
	}
	memset(psl->a, 0, sizeof(SLdatatype) * 4);
	psl->size = 0;
	psl->capacity = 4;
}

void SeqListDestroy(SeqList *psl)
{
	free(psl->a);
	psl->a = NULL;
	psl->capacity = psl->size = 0;
}

void SeqListPrint(SeqList *psl)
{
	for (int i = 0; i < psl->size; i++){
		printf("%d ", psl->a[i]);
	}
	printf("n");
}

void CheckCapacity(SeqList* psl)
{
	if (psl->size == psl->capacity){
		SLdatatype *b = (SLdatatype*)realloc(psl->a, sizeof(SLdatatype)*psl->capacity * 2);
		if(b == NULL){
			printf("malloc failn");
			exit(-1);
		}
		psl->a = b;
		psl->capacity = psl->capacity * 2;
	}
}

void SeqListPushBack(SeqList *psl, SLdatatype x)
{
	    assert(psl);
		CheckCapacity(psl);
        psl->a[psl->size] = x;
	    psl->size++;

}

void SeqListPushFront(SeqList *psl, SLdatatype x)
{
	assert(psl);
	CheckCapacity(psl);
	for (int i = psl->size; i >0; i--){
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[0] = x;
	psl->size++;
}

void SeqListPopBack(SeqList *psl)
{
	assert(psl);
	assert(psl->size > 0);
	psl->size--;
}

void SeqListPopFront(SeqList *psl)
{
	assert(psl);
	assert(psl->size > 0);
	for (int i = 0; i < psl->size; i++){
		psl->a[i] = psl->a[i + 1];
	}
	psl->size--;
}

void SeqListInsert(SeqList *psl, int pos, SLdatatype x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	CheckCapacity(psl);
	int i;
	for (i = psl->size; i>=pos; i--){
		psl->a[i] = psl->a[i - 1];
	}
	psl->a[pos] = x;
	psl->size++;
}

void SeListErase(SeqList *psl, int pos)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	for (int i = pos+1; i < psl->size; i++){
		psl->a[i - 1] = psl->a[i];
	}
	psl->size--;
}

复制代码

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

 //test.c

#include"SeqList.h"

int main()
{
	SeqList s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4);
	SeqListPushBack(&s1, 5);
	SeqListPrint(&s1);
	SeqListPushFront(&s1, 0);
	SeqListPrint(&s1);
	SeqListPopBack(&s1);
	SeqListPrint(&s1);
	SeqListPopFront(&s1);
	SeqListPrint(&s1);
	SeqListInsert(&s1,2,10);
	SeqListPrint(&s1);
	SeListErase(&s1,2);
	SeqListPrint(&s1);
}