数据结构（二）——线性表简介

2024-12-19 技术教程

数据结构（二）——线性表简介一、线性表简介1、线性表简介

线性表是具有相同类型的n个数据元素的有限序列A0，A1，A2，...，An-1。Ai是表项，n是表的长度。

2、线性表的表现形式

线性表的表现形式：
A、零个或多个数据元素组成的集合
B、数据元素在位置上是有序排列的
C、数据元素的个数是有限的
D、数据元素的类型必须相同

3、线性表的性质

线性表的性质：
A、A0为线性表的第一个元素，只有一个后继
B、An-1为线性表的最后一个元素，只有一个前驱
C、除A0与An-1外的其它元素既有前驱又有后继
D、直接支持逐项访问和顺序存取

4、线性表的常用操作

线性表的常用操作：
A、将元素插入线性表
B、将元素从线性表中删除
C、获取目标位置处元素的值
D、设置目标位置处元素的值
E、获取线性表的长度
F、清空线性表

二、线性表的抽象实现

#ifndef LIST_H#define LIST_H#include "Object.h"using namespace ScorpioStudio;template <typename T>class List:public Object{public: virtual bool insert(int index, const T& value) = 0; virtual bool remove(int index) = 0; virtual bool set(int index, const T& value) = 0; virtual bool get(int index, T& value) = 0; virtual int length()const = 0; virtual void clear() = 0;};#endif // LIST_H

Object.h:

#ifndef OBJECT_H#define OBJECT_Hnamespace ScorpioStudio{ class Object { public: void* operator new(unsigned int size) throw(); void operator delete(void* p); void* operator new[](unsigned int size) throw(); void operator delete[](void* p); virtual ~Object() = 0; };}#endif // OBJECT_H

Object.cpp:

#include "Object.h"#include <cstdlib>#include <iostream>using namespace std;namespace ScorpioStudio{ void* Object::operator new(unsigned int size) throw() { //cout << "Object::operator new" << endl; return malloc(size); } void Object::operator delete(void* p) { free(p); } void* Object::operator new[](unsigned int size) throw() { //cout << "Object::operator new[] " << size << endl; return malloc(size); } void Object::operator delete[](void* p) { free(p); } Object::~Object() { }}