C/C++データ構造---線形順序記憶データ:クエリーが速く、削除が遅い

ちくじきおくこうぞう
シーケンスストレージ構造は主に配列を使用してデータを格納するので、クエリーが速く、削除が遅いのが特徴です.
なぜ増削除が遅いのですか?追加削除は挿入した位置要素を後ろに移動したり前に移動したりする必要があるため、効率が遅くなります.もちろん末尾に挿入するなら別です!
挿入されたコアコード:
for(i=arrayList->length;i>pos;i-){//要素後移arrayList->node[i]=arrayList->node[i-];//要素arrayList->node[pos]=(unsigned int)nodeを挿入します.arrayList->length++;
削除されたコアコード:
for (i = pos + 1; i < arrayList->length; i++) { arrayList->node[i - 1] = arrayList->node[i]; } arrayList->length--;
ヘッダファイルを見てみましょう.
seqList.h

#ifndef _SEQ_LIST_
#define _SEQ_LIST_
typedef void SeqList;
typedef void SeqListNode;

SeqList* seqList_create(int capacity);
void seqList_destory(SeqList* list);
void seqList_clear(SeqList* list);
int seqList_length(SeqList* list);
int seqList_capacity(SeqList* list);
int seqList_insert(SeqList* list,SeqListNode* node,int pos);
SeqListNode* seqList_get(SeqList* list,int pos);
SeqListNode* seqList_delete(SeqList* list,int pos);
#endif

実装の重点は挿入と削除の方法である
seqList.c

#include <string.h>
#include "seqList.h"
typedef struct _tag_list {
	int length;//    
	int capacity;//       
	unsigned int* node;//       
}ArrayList;


SeqList* seqList_create(int capacity) {
	int ret = 0;
	ArrayList *list = NULL;
	list = (ArrayList*)malloc(sizeof(ArrayList));//      
	if (list == NULL)
	{
		return NULL;
	}
	memset(list, 0, sizeof(ArrayList));
	list->node = (unsigned int *)malloc(sizeof(unsigned int)*capacity);//             
	if (list->node == NULL)
	{
		return NULL;
	}
	list->capacity = capacity;
	list->length = 0;
	return list;
}
//    
void seqList_destory(SeqList* list) {
	ArrayList *arrayList;
	if (list == NULL) { return; }
	arrayList = (ArrayList*)list;
	if (arrayList->node == NULL)
	{
		return;
	}
	free(arrayList->node);
	free(arrayList);

}
//          
void seqList_clear(SeqList* list) {
	ArrayList *arrayList;
	if (list == NULL) { return; }
	arrayList = (ArrayList*)list;
	arrayList->length = 0;
}
//    
int seqList_length(SeqList* list) {
	ArrayList *arrayList;
	if (list == NULL) { return -1; }
	arrayList = (ArrayList*)list;
	return arrayList->length;
}
//      
int seqList_capacity(SeqList* list) {
	ArrayList *arrayList;
	if (list == NULL) { return -1; }
	arrayList = (ArrayList*)list;
	return arrayList->capacity;
}
//      
int seqList_insert(SeqList* list, SeqListNode* node, int pos) {

	if (list == NULL || node == NULL || pos<0) {
		return -1;
	}
	int i = 0;
	ArrayList* arrayList = NULL;
	arrayList = (ArrayList*)list;
	if (arrayList->capacity <= arrayList->length) {//      
		return -1;
	}
	if (pos >= arrayList->length)
	{
		pos = arrayList->length;
	}

	for (i = arrayList->length; i > pos; i--) {
		//    
		arrayList->node[i] = arrayList->node[i - 1];
	};
	//    
	arrayList->node[pos] = (unsigned int)node;
	arrayList->length ++;
	return 0;
}
SeqListNode* seqList_get(SeqList* list, int pos) {
	ArrayList* arrayList = NULL;
	SeqListNode* ret = NULL;
	arrayList = (ArrayList*)list;
	if (list == NULL || pos<0||pos>= arrayList->length)
	{
		return NULL;
	}
	ret= (SeqListNode*)arrayList->node[pos];
	return ret;
}
SeqListNode* seqList_delete(SeqList* list, int pos) {
	if (list == NULL || pos<0)
	{
		return NULL;
	}
	int i = 0;
	ArrayList *arrayList = NULL;
	SeqListNode *node = 0;
	arrayList = (ArrayList*)list;
	node = (SeqListNode*)arrayList->node[pos];//  pos   
	for (i = pos + 1; i < arrayList->length; i++) {
		arrayList->node[i - 1] = arrayList->node[i];
	}
	arrayList->length--;
	return node;
}

テストコードを見てみましょう.

#define  _CRT_SECURE_NO_WARNINGS
#include <stdlib.h>
#include <stdio.h>
#include<string.h>
#include "seqList.h"

typedef struct mac {
	int pir;
	char name[64];

}Mac;


void main() {
	int i = 0;
	Mac m1,m2,m3;
	m1.pir = 3200;
	strcpy(m1.name,"m1");
	m2.pir = 3456;
	strcpy(m2.name, "m2");
	m3.pir = 1900;
	strcpy(m3.name, "m3");
	SeqList* list=seqList_create(10);
	seqList_insert(list, &m1, 0);
	seqList_insert(list,&m2, 0);
	seqList_insert(list,&m3,0);
	for ( i = 0; i <seqList_length(list); i++)
	{
		Mac* node=(Mac*)seqList_get(list,i);
		printf("pir=%d
", node->pir); 
		printf("name=%s
", node->name);
	}
	//      
	seqList_delete(list,0);
	printf("---------------
");
	for (i = 0; i <seqList_length(list); i++)
	{
		Mac* node = (Mac*)seqList_get(list, i);
		printf("pir=%d
", node->pir);
		printf("name=%s
", node->name);

	seqList_destory(list);
	printf("helloWord
");
	system("pause");
}

C++の実装を見てみましょう.

#pragma once
template<typename T>
class CircleList2
{
public:
	CircleList2(int cap);
	~CircleList2();
public:
	T get(int pos);
	int insert(T &t,int pos);
	int dele(int pos);
	int getLen();
private:
	T *ts;
	int len;
};

#include "CircleList2.h"


template<typename T>
CircleList2<T>::CircleList2(int cap)
{
	ts = new T[cap];
	this->len = 0;
}

template<typename T>
CircleList2<T>::~CircleList2()
{
	delete[]ts;
	ts = nullptr;
}



template<typename T>
T CircleList2<T>::get(int pos) {

	return ts[pos];
}


template<typename T>
int CircleList2<T>::insert(T & t, int pos)
{
	int i = 0;
	for ( i = len; i <pos ; i--)
	{
		ts[i] = ts[i - 1];
	}
	ts[i] = t;
	this->len++;
	return 0;
}

template<typename T>
int CircleList2<T>::dele(int pos)
{
	
	for (int i = len; i <pos ; i--)
	{
		ts[i] = ts[i + 1];
	}
len--;

	return 0;
}

template<typename T>
int CircleList2<T>::getLen()
{
	return len;
}

テストファイル:

#include<iostream>
using namespace std;
#include"CircleList2.cpp"

struct Teacher
{
	int age;

};

void main() {
	Teacher t1,t2;
	t1.age = 12;
	t2.age = 14;
	CircleList2<Teacher> list(10);
	list.insert(t1,0);
	list.insert(t2, 0);
	for (int i = 0; i < list.getLen(); i++)
	{
		Teacher t=list.get(i);
		cout << "age==" << t .age<<endl;
	}
	cin.get();
}