什么是线性结构？

线性结构是一个有序数据元素的集合。其中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。
常用的线性结构有：线性表，栈，队列，双队列，数组，串。

线性结构中都包含什么内容？

总的来说，“线性结构”是一个有序数据元素的集合，包含以下内容：

集合中必存在唯一“第一个元素”；
集合中必存在唯一“最后一个元素”；
除了最后一个元素，所有元素均有唯一“后继结点”；
除了第一个元素，所有元素均有唯一“前趋结点”。

什么是线性表？

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

什么是顺序表？顺序表的分类？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为：

静态顺序表：使用定长数组存储。

// 顺序表的静态存储
#define N 100
typedef int SLDataType;
typedef struct SeqList
{
SLDataType array[N]; // 定长数组
size_t size; // 有效数据的个数
}SeqList;

动态顺序表：使用动态开辟的数组存储。

// 顺序表的动态存储
 typedef struct SeqList
 {
 SLDataType* array; // 指向动态开辟的数组
 size_t size ; // 有效数据个数
 size_t capicity ; // 容量空间的大小
 }SeqList;

完成动态顺序表的以下操作

链表的初始化
在链表s最后一个节点后插入值为data的节点
删除链表s最后一个节点
在链表s第一个节点前插入值为data的节点
删除链表s的第一个节点
在链表的pos位置后插入值为data的节点
删除链表s中pos位置的节点
在链表中查找值为data的节点，找到返回该节点的地址，否则返回NULL
获取链表中有效节点的个数
检测链表是否为空
将链表中有效节点清空
销毁链表

完整代码

头文件

#pragma once
// 动态的顺序表 
typedef int DataType;
typedef struct SeqList
{
	DataType* _array;
	int _capacity; // 顺序表的总大小 
	int _size; // 顺序表中有效元素的个数 
}SeqList, *PSeq;

//typedef struct SeqList SeqList; 
//typedef struct SeqList* PSeqList; 

// 顺序表的初始化 
void SeqListInit(PSeq ps, int capacity);

// 在顺序表的尾部插入值为data的元素 
void SeqListPushBack(PSeq ps, DataType data);

// 删除顺序表最后一个元素 
void SeqListPopBack(PSeq ps);

// 在顺序表的头部插入值为data的元素 
void SeqListPushFront(PSeq ps, DataType data);

// 删除顺序表头部的元素 
void SeqListPopFront(PSeq ps);

// 在顺序表pos位置插入值为data的元素 
void SeqListInsert(PSeq ps, int pos, DataType data);

// 删除顺序表中pos位置上的元素 
void SeqListErase(PSeq ps, int pos);

// 在顺序表中查找值为data的元素，找到返回该元素在顺序表中的下标，否则返回-1 
int SeqListFind(PSeq ps, DataType data);

// 检测顺序表是否为空，如果为空返回非0值，非空返回0 
int SeqListEmpty(PSeq ps);

// 返回顺序表中有效元素的个数 
int SeqListSize(PSeq ps);

// 返回顺序表的容量大小 
int SeqListCapacity(PSeq ps);

// 将顺序表中的元素清空 
void SeqListClear(PSeq ps);

// 删除顺序表中第一个值为data的元素 
void SeqListRemove(PSeq ps, DataType data);

// 销毁顺序表 
void SeqListDestroy(PSeq ps);

// 顺序表的扩容 
void CheckCapacity(PSeq ps);

void TestSeqList();

源文件

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "test.h"
// 顺序表的初始化 
void SeqListInit(PSeq ps, int capacity) {
	ps->_array = (DataType*)malloc(sizeof(DataType*) * capacity);
	if (ps->_array == NULL) {
		assert(0);
		return;
	}
	ps->_capacity = capacity;
	ps->_size = 0;
}

// 在顺序表的尾部插入值为data的元素 
void SeqListPushBack(PSeq ps, DataType data) {
	assert(ps);
	//顺序表满
	CheckCapacity(ps);
	ps->_array[ps->_size] = data;
	ps->_size++;

	//SeqListInsert(ps, ps->_size, data);
}

// 删除顺序表最后一个元素 
void SeqListPopBack(PSeq ps) {
	assert(ps);
	if (SeqListEmpty(ps)) {
		return;
	}
	ps->_size--;

	//SeqListErase(ps, ps->_size-1);
}

// 在顺序表的头部插入值为data的元素 
void SeqListPushFront(PSeq ps, DataType data) {
	assert(ps);
	//顺序表满
	CheckCapacity(ps);
	//将顺序表中所有元素统一向后移一个位置
	for (int i = ps->_size - 1; i >= 0; --i) {
		ps->_array[i + 1] = ps->_array[i];
	}

	//插入元素
	ps->_array[0] = data;
	ps->_size++;

	//SeqListInsert(ps, 0, data);
}

// 删除顺序表头部的元素 
void SeqListPopFront(PSeq ps) {
	assert(ps);
	for (int i = 0; i < ps->_size-1; ++i) {
		ps->_array[i] = ps->_array[i+1];
	}
	ps->_size--;
	//SeqListErase(ps, 0);
}

// 在顺序表pos位置插入值为data的元素 
void SeqListInsert(PSeq ps, int pos, DataType data) {
	assert(ps);
	if (pos<0 || pos>=ps->_size) {
		return;
	}
	//CheckCapacity();

	for (int i = ps->_size - 1; i >= pos; --i) {
		ps->_array[i + 1] = ps->_array[i];
	}
	ps->_array[pos] = data;
	ps->_size++;
}

// 删除顺序表中pos位置上的元素 
void SeqListErase(PSeq ps, int pos) {
	assert(ps);
	if (pos < 0 || pos >= ps->_size) {
		return;
	}

	for (int i = pos + 1; i < ps->_size; ++i) {
		ps->_array[i - 1] = ps->_array[i];
	}
	ps->_size--;
}

// 在顺序表中查找值为data的元素，找到返回该元素在顺序表中的下标，否则返回-1 
int SeqListFind(PSeq ps, DataType data) {
	assert(ps);
	for (int i = 0; i < ps->_size; ++i) {
		if (ps->_array[i] == data) {
			return i;
		}
	}
	return -1;
}

// 检测顺序表是否为空，如果为空返回非0值，非空返回0 
int SeqListEmpty(PSeq ps) {
	assert(ps);
	return ps->_size == 0;
}

// 返回顺序表中有效元素的个数 
int SeqListSize(PSeq ps) {
	return ps->_size;
}

// 返回顺序表的容量大小 
int SeqListCapacity(PSeq ps) {
	return ps->_capacity;
}

// 将顺序表中的元素清空 
void SeqListClear(PSeq ps) {
	assert(ps);
	ps->_size = 0;
}

// 删除顺序表中第一个值为data的元素 
void SeqListRemove(PSeq ps, DataType data) {
	assert(ps);
	SeqListErase(ps, SeqListFind(ps, data));
}

void SeqListRemoveAll(PSeq ps, DataType data) {
	int pos = -1;
	while (-1 != (pos = SeqListFind(ps, data))) {
		SeqListErase(ps, pos);
	}
	//时间复杂度O(N^2)
}

// 销毁顺序表 
void SeqListDestroy(PSeq ps) {
	if (ps->_array) {
		free(ps->_array);
		ps->_array = NULL;
		ps->_capacity = 0;
		ps->_size = 0;
	}
}

// 顺序表的扩容 
void CheckCapacity(PSeq ps) {
	assert(ps);
	if (ps->_size == ps->_capacity) {
		int newCapacity = ps->_capacity * 2;
		//realloc(p,size)
		//申请新空间
		int* pTemp = (DataType*)malloc(sizeof(DataType*)*newCapacity);
		if (pTemp == NULL) {
			assert(0);
			return;
		}
		//拷贝元素
		for (int i = 0; i < ps->_size; ++i) {
			pTemp[i] = ps->_array[i];
		}
		//释放旧空间
		free(ps->_array);
		
		//更新
		ps->_array = pTemp;
		ps->_capacity = newCapacity;
	}
}

//打印顺序表
void SeqListPrint(PSeq ps) {
	for (int i = 0; i < ps->_size; ++i) {
		printf("%d ", ps->_array[i]);
	}
	printf("\n");
}

//测试
void TestSeqList() {
	SeqList s;
	int pos = -1;
	SeqListInit(&s, 10);

	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	//SeqListPushBack(&s, 1);
	//SeqListPushBack(&s, 2);
	//SeqListPushBack(&s, 3);
	//SeqListPushBack(&s, 4);
	//SeqListPushBack(&s, 1);
	//SeqListPushBack(&s, 2);

	SeqListPrint(&s);

	//printf("size=%d\n", SeqListSize(&s));
	//printf("capacity=%d\n", SeqListCapacity(&s));

	//SeqListPushBack(&s, 3);
	//SeqListPushBack(&s, 4);

	//printf("size=%d\n", SeqListSize(&s));
	//printf("capacity=%d\n", SeqListCapacity(&s));

	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListPushFront(&s, 5);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPrint(&s);

	SeqListInsert(&s,2,4);
	SeqListPrint(&s);

	pos = SeqListFind(&s, 4);
	if (pos != -1) {
		printf("4 is in %d !\n", pos);
	}
	else {
		printf("4 is not in %d !\n", pos);
	}

	SeqListErase(&s,2);
	SeqListPrint(&s);

	pos = SeqListFind(&s, 4);
	if (pos != -1) {
		printf("4 is in %d !\n", pos);
	}
	else {
		printf("4 is not in %d !\n", pos);
	}

	SeqListRemove(&s,2);
	SeqListPrint(&s);

	printf("size=%d\n", SeqListSize(&s));
	printf("capacity=%d\n", SeqListCapacity(&s));

	SeqListDestroy(&s);
}

int main() {
	TestSeqList();
	system("pause");
	return 0;
}

测试

数据结构02——线性结构之顺序表

数据结构02——线性结构之顺序表

目录

什么是线性结构？

线性结构中都包含什么内容？

什么是线性表？

什么是顺序表？顺序表的分类？

完成动态顺序表的以下操作

完整代码

头文件

源文件

测试

相关推荐