【c++学习】数据结构中的顺序表

数据结构中的顺序表

顺序表强调数据的存储结构，表示数据在内存中连续存储。（线性表与链表相对，链表数据在内存中的存储空间是不连续的）

代码

下述代码实现了线性表及其接口
包括增、删、查、改以及其他一些简单的功能

#include <iostream>

using namespace std;

#define eleType int//可更改线性表的数据类型

//定义线性表
struct SequentialList{
    eleType *elements;
	int size;
	int capacity;
};

//初始化线性表（分配内存空间）
void initializeList(SequentialList *list, int capacity){
	list->elements = new eleType[capacity];
	list->size = 0;
	list->capacity = capacity;

}

//删除整个线性表
void destoryList(SequentialList *list){
    delete[] list->elements;
}

//线性表大小（注意区分线性表的大小和容量）
int size(SequentialList *list){
    return list->size;
}

//判断是否为空
bool isEmpty(SequentialList *list){
    return list->size == 0;
}

//线性表插入
void insert(SequentialList *list, int index, eleType value){
    if(index < 0 || index > list->size ) {//插入的位置索引是否合理
	    throw std::invalid_argument("invalid index");
	}
	if(list->size == list->capacity){//若容量不够需要扩容
	    int newCapacity = 2 * list->capacity;
		eleType *newElements = new eleType[newCapacity];
		for(int i = 0; i < list->size; i++) {
		    newElements[i] = list->elements[i];
		}
		delete[] list->elements;
		list->elements = newElements;
		list->capacity = newCapacity;
	}
	for(int i = list->size; i > index; i--){
	    list->elements[i] = list->elements[i-1];
	}
	list->elements[index] = value;//插入
	list->size ++;
}

//线性表删除某个元素
void deleteElement(SequentialList *list, int index){
    if(index < 0 || index >= list->size ) {
	    throw std::invalid_argument("invalid index");
	}
	for(int i = index; i< list->size-1; i++){
	    list->elements[i] = list->elements[i+1];
	}
	list->size--;
}

//通过数据查找索引
int findElement(SequentialList *list, eleType value){
    for(int i = 0; i <= list->size-1; i++){
	    if(list->elements[i] == value){
		    return i;
		}
	}
	return -1;
}

//通过索引查找数据
eleType getElement(SequentialList *list, int index){
    if(index < 0 || index >= list->size ) {
	    throw std::invalid_argument("invalid index");
	}
	return list->elements[index];
}

//更改线性表的某数据
void updateElement(SequentialList *list, int index, eleType value){
    if(index < 0 || index >= list->size ) {
	    throw std::invalid_argument("invalid index");
	}
	list->elements[index] = value;
}

//打印线性表的数据
void printList(SequentialList *list){
    for(int i = 0; i < list->size; i++){
	    cout << list->elements[i] << " ";
	}
	cout << endl;
}


int main()
{
    SequentialList myList;
	initializeList(&myList,10);
	for(int i=0; i<10; i++){
	    insert(&myList,i,i*10);
	}
	printList(&myList);
	cout << size(&myList) << endl;
	cout << findElement(&myList,80) << endl;
    cout << getElement(&myList,4) << endl;
	
	insert(&myList,1,100);
	printList(&myList);
	
	deleteElement(&myList,2);
	printList(&myList);
	
	updateElement(&myList,3,10000);
	printList(&myList);
   return 0;
}

于 2024-01-23 第一次整理编写

学习时整理，不当之处烦请指正
码字不易，留个赞再走吧