WHCSRL 技术网

数据结构顺序表

1. 顺序表的实现

//一般在生活中用到的是动态顺序表
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;//typedef的目的是方便以后修改存储什么类型的数据

typedef struct SeqList
{
	SLDataType* a;//指向动态开辟的数组
	int size;//有效数据的个数
	int capacity;//容量
}SL;

//定义顺序表的接口函数

void SeqListInit(SL* ps);//顺序表的初始化
void SeqListPrint(SL* ps);//顺序表的打印
void CheckCapacity(SL* ps);//增容函数

void SeqListPushBack(SL* ps,SLDataType x);//尾插
void SeqListPopBack(SL* ps);//尾删

void SeqListPushFront(SL* ps, SLDataType x);//头插
void SeqListPopFront(SL* ps);//头删

int SeqListFind(SL* ps, int pos);//查找接口
void SeqListInsert(SL* ps, int pos, SLDataType x);//在pos位置之前插入
void SeqListErase(SL* ps, int pos);//删除pos位置的数据
void SeqListDestory(SL* ps)//释放空间

  • 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

然后在sqlist.c文件中实现接口

#include"SeqList.h"

void SeqListPrint(SL* ps)
{
	for (int i = 0; i < ps->size; i++)
	{
		printf("%%d ", ps->a[i]);
	}
}
void SeqListInit(SL* ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void CheckCapacity(SL* ps)
{
	if (ps->size == ps->capacity)//如果size==capacity就得增容
	{
		int newcapacity = ps->capacity == 0 ? 4: 2 * (ps->capacity);//如果capacity=0,就给他赋值为4,如果不为0就赋值它的2倍
		SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));
		//用一个指针接收它realloc后的地址
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}
		ps->capacity = newcapacity;
		ps->a = tmp;
	}
}

void SeqListPushBack(SL* ps, SLDataType x)
{
	CheckCapacity(ps);//先判断是否需要增容
	ps->a[ps->size] = x;
	ps->size++;//个数增加
}

void SeqListPopBack(SL* ps)
{
//断言的作用:如果顺序表中一个数据也没有,就没法尾删(方便找到错误)
	assert(ps->size > 0);
	ps->size--;
	//size--就访问不到尾部,就能尾删
}

void SeqListPushFront(SL* ps, SLDataType x)
{
	CheckCapacity(ps);
	int end = ps->size;
	while (end)
	{
		ps->a[end] = ps->a[end - 1];//从尾部开始,依次往后挪动一位
		end--;
	}
	//这是end的值为0,ps->a[end]就是头
	ps->a[end] = x;
	ps->size++;
}

void SeqListPopFront(SL* ps)//头删
{
	assert(ps->size);
	int first = 1;
	while (first<ps->size)
	{
		ps->a[first - 1] = ps->a[first];//从第二个位置开始,依次往前挪动一位
		first++;
	}
	ps->size--;//数据个数减少
}

int SeqListFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->a[i] ==x)
		{
			return i;//i的位置就是pos的位置
		}
	}
	return -1;//如果找不到返回-1
}

void SeqListInsert(SL* ps, int pos, SLDataType x)
{
//断言的作用:避免访问到顺序表中不存在的位置
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);
	int end = ps->size;
	while (end != pos)
	{
		ps->a[end] = ps->a[end - 1];//从pos位置开始,依次往后挪动一位
		end--;
	}
	ps->a[pos] = x;//在pos位置插入数据
	ps->size++;
}

void SeqListErase(SL* ps, int pos)
{
	assert(pos >= 0 && pos <= ps->size);
	while (pos <ps->size-1)
	{
		ps->a[pos] = ps->a[pos + 1];//从pos+1开始,依次往前挪动一位
		pos++;
	}
	ps->size--;
}

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


  • 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

剩下的就是在test.c中进行增删查改等功能

void TestSeqList2()
{
	SL s1;
	SeqListInit(&s1);
	SeqListPushBack(&s1, 1);
	SeqListPushBack(&s1, 2);
	SeqListPushBack(&s1, 3);
	SeqListPushBack(&s1, 4); 
	SeqListPushBack(&s1, 5);
	SeqListPushBack(&s1, 6);
	int pos = SeqListFind(&s1, 4);
	if (pos != -1)
	{
		SeqListInsert(&s1, pos, 40);
	}

	pos = SeqListFind(&s1, 5);
	if (pos != -1)
	{
		SeqListErase(&s1, pos);
	}
	SeqListPrint(&s1);
	SeqListDestory(&s1);
	
}

int main()
{
	TestSeqList2();


	return 0;
}
  • 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

值得注意的是:

头插,尾插,头删,尾删都可以用 SeqListInsert 和 SeqListErase 代替
比如:
头插就可以直接调用SeqListInsert(ps,0,x);
尾插调用SeqListInsert(ps,ps->size,x);
头删调用SeqListErase(ps,0);
尾删调用SeqListErase(ps,ps->size);

推荐阅读