欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 科技 > 能源 > 数据结构(其二)--线性表

数据结构(其二)--线性表

2025/2/23 16:39:03 来源:https://blog.csdn.net/sjj_1234567/article/details/140260636  浏览:    关键词:数据结构(其二)--线性表

1. 基本概念

线性表:

(1).其中的各个元素,数据类型相同

(2).元素之间,有次序

(3).都有表头元素表尾元素

(4).除了表头表尾,每个元素都可以找到一个直接前驱直接后继

2.线性表的基本操作

表的从无到有

InitList(&L):初始化一个线性表

DestroyList(&L):销毁

ListInsert(&L, i, e):插入,在表L的第 i 处插入元素 e

ListDelete(&L, i, &e):删除,将表L的第 i 处元素删除,并用 e 返回该被删除的元素

LocateElem(L, e):按查找,在表中查找特定关键字e 的元素

GetElem(L, i):按查找,获取表中第 i 个元素的值

其他常规操作:

Length(L):求表长

PrintList(L):输出表的所有元素

Empty(L):判断表是否为空,返回true or false

高度概括,即为,创销与增删改查

3.顺序表

顺序存储方式储存数据的线性表

(1).静态分配

#define MAX 10
//顺序表(静态分配)
class SqList
{
public:int data[MAX];int length;
};
//初始化
void InitList(SqList &l)
{for(int i = 0 ;i < 10 ;i++){l.data[i] = 0;}l.length = 0;
}
//打印所有元素
void PrintList(SqList &l)
{for (int i = 0; i < 10; i++)cout << "第" << i << "个数:" << l.data[i] << endl;
}//测验
void test01()
{SqList l;InitList(l);PrintList(l);
}

(2).动态分配

#define InitSize 10
//顺序表(动态分配)
class SqList
{
public:int* data;		//指示动态分配数组的指针int MaxSize;	//指示最大容量int length;		//指示当前长度
};
//初始化顺序表
void InitList(SqList& l)
{l.data = new int[InitSize];l.MaxSize = InitSize;l.length = 0;for (int i = 0; i < l.MaxSize; i++){l.data[i] = 0;}
}
//增长数组空间
void IncreaseSize(SqList& l, int len)
{int* p = l.data;					//暂存原数组中的数据l.data = new int[10 + len];			//扩展新的数组for (int i = 0; i < l.length; i++)	//将原数据拷贝进新数组中{l.data[i] = p[i];}l.MaxSize = InitSize + len;			//修改数组的状态数据delete p;							//将p释放
}
//打印所有元素
void PrintList(SqList& l)
{for (int i = 0; i < 10; i++)cout << "第" << i << "个数:" << l.data[i] << endl;
}void test01()
{SqList l;InitList(l);PrintList(l);
}

(3).顺序表的插入(以静态分配为例)(示例代码中包含了一下必要的基本函数)

bool ListInsert(SqList& l, int d, int e)
{
    if (l.length >= MAX)                        //首先要判断表是否已满、插入是否合法
    {
        cout << "插入失败,已达上限" << endl;
        return false;
    }
        
    if (d < 1 || d > l.length + 1)
    {
        cout << "插入失败,无直接前驱" << endl;
        return false;
    }
    for (int j = l.length; j >= d; j--)         //将插入点之后的元素后移
        l.data[j] = l.data[j - 1];
    l.data[d - 1] = e;                          //插入,因为d指的是第几个数,在数组的换算中要减一
    l.length++;
    return true;
}

示例代码

#define MAX 10
//顺序表(静态分配)
class SqList
{
public:int data[MAX];int length;
};
//初始化
void InitList(SqList& l)
{for (int i = 0; i < 10; i++){l.data[i] = 0;}l.length = 0;
}
//打印所有元素
void PrintList(SqList& l)
{for (int i = 0; i < 10; i++)cout << "第" << i << "个数:" << l.data[i] << endl;
}
//存入数据
void InputElem(SqList& l, int e)
{int i = 0;while (i < MAX){if (l.data[i] == 0){l.data[i] = e;l.length++;break;}i++;}
}
//获取顺序表长度
int GetLength(SqList l)
{//cout << l.length << endl;return l.length;
}
//插入
bool ListInsert(SqList& l, int d, int e)
{if (l.length >= MAX)                        //首先要判断表是否已满、插入是否合法{cout << "插入失败,已达上限" << endl;return false;}if (d < 1 || d > l.length + 1){cout << "插入失败,无直接前驱" << endl;return false;}for (int j = l.length; j >= d; j--)         //将插入点之后的元素后移l.data[j] = l.data[j - 1];l.data[d - 1] = e;                          //插入,因为d指的是第几个数,在数组的换算中要减一l.length++;return true;
}
//查看情况
void CheckList(SqList& l)
{PrintList(l);cout << "当前长度为" << GetLength(l) << endl;
}//测验
void test01()
{SqList l;InitList(l);//输入部分数据InputElem(l, 1);InputElem(l, 2);InputElem(l, 3);InputElem(l, 4);CheckList(l);//开始插入if(ListInsert(l, 5, 6))CheckList(l);
}

 (4).顺序表的删除

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词