严蔚敏《数据结构》第二章线性表 2.2节线性表的顺序表示 C++实现

本文主要是介绍严蔚敏《数据结构》第二章线性表 2.2节线性表的顺序表示 C++实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

严蔚敏《数据结构》第二章线性表 2.2节线性表的顺序表示 C++实现

// sq_list.h
// By Envirian
#ifndef SQ_LIST_H_
#define SQ_LIST_H_
#include <algorithm>
using Status              = int;  // 返回值类型
const int TRUE            = 1;
const int FALSE           = 0;
const int OK              = 1;
const int ERROE           = 0;
const int INFEASIBLE      = -1;
const int kLIST_INIT_SIZE = 100;  // 线性表的初始容量
const int kLISTINCREASE   = 10;   // 线性表的容量增量
using ElemType            = int;  // 数据项类型
// 线性表，支持插入、删除、查找、随机访问操作
class SqList {
private:ElemType* elem_{nullptr};  // 储存空间基址int length_{0};            // 当前长度（元素个数）int list_size_{0};         // 当前容量（可以容纳的元素个数）
public:Status InitList(){// 顺序线性表的初始化elem_ = new ElemType[kLIST_INIT_SIZE];if (!elem_)return FALSE;  // 存储分配失败length_    = 0;list_size_ = kLIST_INIT_SIZE;return OK;}Status ListInsert(int i, const ElemType& e){// 在顺序线性表的第i个位置之前插入新的元素eif (i < 0 || i > length_)return ERROE;if (length_ >= list_size_) {// 容量已满，重新分配。// 不使用realloc的话，这需要一个Resize()函数来实现。if (!Resize(list_size_ + kLISTINCREASE))return FALSE;}ElemType* q = &elem_[i];  // q为插入位置for (ElemType* p = &elem_[length_ - 1]; p >= q; --p) {// 从最后一个元素开始，每个元素后移一位，直到插入位置。*(p + 1) = *p;}*q = e;     // 插入数据项++length_;  // 长度+1return OK;}Status Resize(int new_size){// 上面插入函数中的Resieze()，改变线性表的容量。if (new_size <= list_size_)return OK;else {ElemType* new_elem = new ElemType[new_size];if (!new_elem)return FALSE;for (int k = 0; k < list_size_; ++k) {new_elem[k] = elem_[k];}list_size_ = new_size;std::swap(elem_, new_elem);delete[] new_elem;}return OK;}Status ListDelete(int i, ElemType& e){// 在线性表中删除第i个元素，并用e返回其值if (i < 0 || i >= length_)return ERROE;         // i值不合法ElemType* p = &elem_[i];  // 要删除的元素地址e           = *p;ElemType* q = elem_ + length_;for (++p; p < q; ++p) {// 从要删除元素位置的下一个位置开始，前移一位，直到到达末尾*(p - 1) = *p;}--length_;return OK;}int LocateElem(const ElemType& e){// 查找元素e第一次出现的位置，没有找到则返回-1for (int i = 0; i < length_; ++i) {if (elem_[i] == e) {return i;}}return -1;}Status GetElem(int i, ElemType& e){// 获取第i个位置的元素,存放到e中if (i < 0 || i >= length_)return ERROE;  // i值不合法e = elem_[i];return OK;}int GetSize(){// 获取线性表大小return length_;}// 归并合并例程friend Status MergeList(const SqList& a, const SqList& b, SqList& c);
};Status MergeList(const SqList& a, const SqList& b, SqList& c)
{// 线性表a和b的元素按值非递减排列// 归并到c中，也按照值非递减排列if (!c.elem_)delete[] c.elem_;  // 清空线性表cElemType *pa = a.elem_, *pb = b.elem_;c.list_size_ = c.length_ = a.length_ + b.length_;ElemType* pc = c.elem_ = new ElemType[c.list_size_];if (!c.elem_)return FALSE;ElemType *pa_last = a.elem_ + a.length_, *pb_last = b.elem_ + b.length_;while (pa < pa_last && pb < pb_last) {if (*pa < *pb)*pc++ = *pa++;else*pc++ = *pb++;}while (pa < pa_last)*pc++ = *pa++;  // 插入a的剩余元素while (pb < pb_last)*pc++ = *pb++;  // 插入b的剩余元素return OK;
}#endif