线性表顺序存储结构

所用的教材是：《数据结构与算法》第四版 廖明宏 郭福顺 张岩 李秀坤老师编著的

线性结构中线性表分为三种：数组存储结构、链式存储结构以及游标存储结构 这一部分先讲解线性表的数组存储结构：

1、线性表的数组存储结构：

using namespace std;

template

struct node{

T *ele;

int lengthl, sizel;

};

2、c++模板类实现线性表的基本操作

template class arrayl { public:

arrayl(); ~arrayl(); bool isNull(); bool isFull(); int getLength(); void getEle(int); void getL(T); void insertl(T, int); void deletel(int); void displayl(); private: node *p; };

3、各个函数的实现

template arrayl::arrayl()

//构造函数 //析构函数 //判断是否为空 判断是否满

//返回当前线性表的实际长度 //某个位置的节点值

//此值在线性表中第一个位置 //插入到某个位置 //删除某个位置 //打印 // {

p = new node; p->sizel = MAX;

p->ele = new T[p->sizel]; p->lengthl = 0; }

template arrayl::~arrayl(){ delete[]p->ele; }

template

bool arrayl::isNull() {

if (p->lengthl>0) return false; else return true; }

template

bool arrayl::isFull()

{

if (p->lengthl == p->sizel) return true; else return false; }

template

int arrayl::getLength() {

return p->lengthl; }

template

void arrayl::getEle(int x) {

if(x>p->lengthl||x<0) cout<<\"Error !\"<cout<<\"值为：\"<ele[x]<template

void arrayl::getL(T t) {

int temp=0;

for(int i=0;ilengthl;i++) {

if(t==p->ele[i]) {

temp=1;

cout<<\"位置为：\"<if(temp==0) cout<<\"没有\"<void arrayl::insertl(T t, int x) //插入到排在x处 {

if (isFull()) cout << \"Full !\" << endl; else {

if (x>p->lengthl) cout << \"Error !\" << endl; else{

p->ele[x] = t;

for (int i = p->lengthl - 1; i > x; i--) p->ele[i + 1] = p->ele[i]; p->lengthl++; } } } template

void arrayl::deletel(int x) //删除第x个节点 {

if (x>p->lengthl || x<0) cout << \"Error !\" << endl; else {

for (int j = x - 1; jlengthl; j++) p->ele[j] = p->ele[j + 1]; p->lengthl--; } }

template

void arrayl::displayl() {

if (isNull()) cout << \"Null !\" << endl;

else {

for (int j = 0; jlengthl; j++) cout << p->ele[j] << \" \"; cout << endl; } }

4、主函数main int main() {

arrayl newl; int t, x;

for (int i = 0; i<30; i++) //初始线性表 newl.insertl(i, i);

cout << \"当前线性表的长度：\" << newl.getLength() << endl; newl.displayl();

cout<<\"输入要查询的位置：\"; cin>>x; newl.getEle(x);

cout<<\"输入要查询的节点：\"; cin>>t; newl.getL(t);

cout << \"输入要插入的t,插入的位置x:\";

cin >> t >> x; newl.insertl(t, x);

cout << \"当前线性表的长度：\" << newl.getLength() << endl; newl.displayl();

cout << \"输入要删除的位置x:\"; cin >> x; newl.deletel(x);

cout << \"当前线性表的长度：\" << newl.getLength() << endl; newl.displayl(); system(\"pause\"); return 0; }

5、运行结果

程序源代码： #include

#define MAX 100 using namespace std; template struct node{ T *ele;

int lengthl, sizel; };

template class arrayl { public:

arrayl(); ~arrayl(); bool isNull(); bool isFull(); int getLength(); void getEle(int); void getL(T); void insertl(T, int); void deletel(int); void displayl(); private: node *p; };

template arrayl::arrayl() {

//构造函数 //析构函数 //判断是否为空 判断是否满

//返回当前线性表的实际长度 //某个位置的节点值

//此值在线性表中第一个位置 //插入到某个位置 //删除某个位置 //打印 // p = new node; p->sizel = MAX;

p->ele = new T[p->sizel]; p->lengthl = 0; }

template arrayl::~arrayl(){ delete[]p->ele; }

template

bool arrayl::isNull() {

if (p->lengthl>0) return false; else return true; }

template

bool arrayl::isFull() {

if (p->lengthl == p->sizel) return true; else return false; }

template

int arrayl::getLength() {

return p->lengthl; }

template

void arrayl::getEle(int x) {

if(x>p->lengthl||x<0) cout<<\"Error !\"<cout<<\"值为：\"<ele[x]<template

void arrayl::getL(T t) {

int temp=0;

for(int i=0;ilengthl;i++) {

if(t==p->ele[i]) {

temp=1;

cout<<\"位置为：\"<if(temp==0) cout<<\"没有\"<void arrayl::insertl(T t, int x) //插入到排在x处 {

if (isFull()) cout << \"Full !\" << endl; else {

if (x>p->lengthl) cout << \"Error !\" << endl; else{

p->ele[x] = t;

for (int i = p->lengthl - 1; i > x; i--) p->ele[i + 1] = p->ele[i]; p->lengthl++; } } } template

void arrayl::deletel(int x) //删除第x个节点 {

if (x>p->lengthl || x<0) cout << \"Error !\" << endl; else {

for (int j = x - 1; jlengthl; j++) p->ele[j] = p->ele[j + 1]; p->lengthl--; } }

template

void arrayl::displayl() {

if (isNull()) cout << \"Null !\" << endl; else {

for (int j = 0; jlengthl; j++) cout << p->ele[j] << \" \"; cout << endl; } }

int main() {

arrayl newl; int t, x;

for (int i = 0; i<30; i++) //初始线性表 newl.insertl(i, i);

cout << \"当前线性表的长度：\" << newl.getLength() << endl; newl.displayl();

cout<<\"输入要查询的位置：\"; cin>>x; newl.getEle(x);

cout<<\"输入要查询的节点：\"; cin>>t; newl.getL(t);

cout << \"输入要插入的t,插入的位置x:\"; cin >> t >> x; newl.insertl(t, x);

cout << \"当前线性表的长度：\" << newl.getLength() << endl; newl.displayl();

cout << \"输入要删除的位置x:\"; cin >> x; newl.deletel(x);

cout << \"当前线性表的长度：\" << newl.getLength() << endl; newl.displayl(); system(\"pause\"); return 0; }

欢迎访问我的博客：http://blog.sina.com.cn/u/5066584704