线性表C++的两种实现(顺序表示、单链表)

dingallen216 发表于 2021-5-5 15:24

本帖最后由 dingallen216 于 2021-5-5 15:28 编辑

在考研嘛，考408，数据结构肯定是跑不掉要学的。光看书光看书多少有点枯燥无聊，稍微实现些代码调节调节。本文是第一次写此类文章，之后随着复习进度的推进会继续整理。本文的代码通过c++实现，实现的基本操作与408考试大纲一致。如果有错误，或者有对计算机考研的建议，感谢您能够在评论区提出。
顺序表示的线性表
数据结构的定义
// 静态分配
template<typename ElemType>
struct SqList {
public:
ElemType data;
int length;
};

// 动态分配
template<typename ElemType>
struct SeqList {
public:
ElemType *data;
int maxSize, length;
};

基本操作的定义
本文仅实现了静态分配的线性表。
/*
* 顺序表示的静态分配线性表的基本操作定义。
* */

// 初始化表。构造一个空的线性表。
// 课本上是void InitList(SqList<ElemType> &L)，这在类型不确定的情况下多少有点不合理，故改为这样的定义。
// 此外，如果操作不违规，这一步其实是可以省略的。
template<typename ElemType>
bool InitList(SqList<ElemType> &L, ElemType v);

// 求表长。返回线性表L的长度，即L中数据元素的个数。
template<typename ElemType>
int Length(SqList<ElemType> L);

// 按值查找操作。在表L中查找具有给定关键字值的元素。
template<typename ElemType>
int LocateElem(SqList<ElemType> L, ElemType e);

// 按位查找操作。获取表L中第 i个位置的元素的值。这里我在实现的时候我想当然地把索引不合法的情况设置为返回值-1了，这个问题应该不是很大。
template<typename ElemType>
ElemType GetElem(SqList<ElemType> L, int i);

// 插入操作。在表L中的第i个位置上插入指定元素e。
template<typename ElemType>
bool ListInsert(SqList<ElemType> &L, int i, ElemType e);

// 删除操作。删除表L 中第 i 个位置的元素，并用e返回删除元素的值。
template<typename ElemType>
bool ListDelete(SqList<ElemType> &L, int i, ElemType &e);

// 输出操作。按前后顺序输出线性表L 的所有元素值。
template<typename ElemType>
void PrintList(SqList<ElemType> L);

// 判空操作。若L为空表，则返回 true，否则返回 false。
template<typename ElemType>
bool Empty(SqList<ElemType> L);

// 销毁操作。销毁线性表，并释放线性表L所占用的内存空间。
template<typename ElemType>
void DestroyList(SqList<ElemType> &L);

基本操作的实现
template<typename ElemType>
bool InitList(SqList<ElemType> &L, ElemType v) {

L.length = 0;
for (int i = 0; i < MaxSize; i++) {
   L.data = v;
}
return true;
}

template<typename ElemType>
int Length(SqList<ElemType> L) {
return L.length;
}

template<typename ElemType>
int LocateElem(SqList<ElemType> L, ElemType e) {

for (int i = 0; i < L.length; ++i) {
   if (L.data == e) return i + 1;
}
return -1;
}

template<typename ElemType>
ElemType GetElem(SqList<ElemType> L, int i) {

assert(i >= 1 && i <= L.length);

return L.data;
}

template<typename ElemType>
bool ListInsert(SqList<ElemType> &L, int i, ElemType e) {

if (i < 1 || i > L.length + 1) return false;
if (L.length >= MaxSize) return false;
for (int j = L.length; j >= i; j--)
   L.data = L.data;
L.data = e;
L.length++;
return true;
}

template<typename ElemType>
bool ListDelete(SqList<ElemType> &L, int i, ElemType &e) {

if (i < 1 || i > L.length) return false;
e = L.data;
for (int j = i; j < L.length; j++)
   L.data = L.data;
L.length--;
return true;
}

template<typename ElemType>
void PrintList(SqList<ElemType> L) {

for (int i = 0; i < L.length; i++) {
   std::cout << "线性表第" << i << "个位置的元素为：" << L.data << std::endl;
}
}

template<typename ElemType>
bool Empty(SqList<ElemType> L) {
return L.length > 0 ? true : false;
}

template<typename ElemType>
void DestroyList(SqList<ElemType> &L) {
delete L;
}

单链表
单链表这块，没有像上面那样使用template来声明，因为这样实现会让代码的一些地方变得很不优雅，并且会做一些与教材本身无关的事情，故直接用int定义数据。
定义
// 单链表结点的定义。
typedef struct LNode {
int data;
struct LNode *next;
} LNode, *LinkList;

基本操作的定义
/*
* 带头结点的单链表的基本操作定义。
* */
bool InitList(LinkList &L);
int Length(LinkList L);
int LocateElem(LinkList L, int e);
LNode *GetElem(LinkList L, int i);
bool InsertNextNode(LNode *p, int e); // 后插操作：在p结点之后插入元素e
bool ListInsert(LinkList &L, int i, int e);
bool ListDelete(LinkList &L, int i, int &e);
void PrintList(LinkList L);
bool Empty(LinkList L);
void DestoryList(LinkList &L);

基本操作的实现
bool InitList(LinkList &L) {

L = new LNode;
if (L == NULL) return false;
L->next = NULL;
return true;
}

int Length(LinkList L) {

LNode *p = L;
int i = 0;
while (p->next != NULL) {
   p = p->next;
   i++;
}
return i;
}

int LocateElem(LinkList L, int e) {

LNode *p = L->next;
for (int i = 1; p != NULL; ++i) {
   if (p->data == e) return i;
   p = p->next;
}
return -1;
}

LNode *GetElem(LinkList L, int i) {

if (i < 0) return NULL;

LNode *p = L;
for (int j = 0; p != NULL && j < i; j++)
   p = p->next;

return p;
}

bool InsertNextNode(LNode *p, int e) {

if (p == NULL) return false;
LNode *s = new LNode;
if (s == NULL) return false;

s->data = e;
s->next = p->next;
p->next = s;
return true;
}

bool ListInsert(LinkList &L, int i, int e) {

if (i < 1) return false;
LNode *p = GetElem(L, i - 1);
return InsertNextNode(p, e);
}

bool ListDelete(LinkList &L, int i, int &e) {

if (i < 1) return false;
LNode *p = GetElem(L, i - 1);
if (p == NULL || p->next == NULL) return false;
LNode *q = p->next;
e = q->data;
p->next = q->next;
delete q;
return true;
}

void PrintList(LinkList L) {

LNode *p = L->next;
for (int i = 0; p != NULL; i++) {
   std::cout << "线性表第" << i << "个位置的元素为：" << p->data << std::endl;
}
}

bool Empty(LinkList L) {
return L->next != NULL ? true : false;
}

void DestoryList(LinkList &L) {

LNode *p = L;
LNode *temp;

while (p != NULL) {
   temp = p;
   p = p->next;
   delete temp;
}
}

尾插法和头插法建立单链表
// 尾插法建立单链表,输入9999表示结束。
LinkList List_TailInsert(LinkList &L) {

int x;
L = new LNode;
LNode *s, *r = L;
std::cin >> x;
while (x!=9999) {
   s = new LNode;
   s->data = x;
   r->next = s;
   r = s;
   std::cin >> x;
}
r->next = NULL;
return L;
}

// 头插法建立单链表，输入9999表示结束。
LinkList List_HeadInsert(LinkList &L) {

int x;
L = new LNode;
L->next = NULL;
LNode *s;
std::cin >> x;
while (x!=9999) {
   s = new LNode;
   s->data = x;
   s->next = L->next;
   L->next = s;
   std::cin >> x;
}
return L;
}

lyl610abc 发表于 2021-5-5 15:26

这个排版，有点恐怖啊，希望能整理一下排版{:301_975:}

dingallen216 发表于 2021-5-5 15:29

lyl610abc 发表于 2021-5-5 15:26
这个排版，有点恐怖啊，希望能整理一下排版

整理好了，谢谢提醒。

tlf 发表于 2021-5-5 17:06

Abrahams 发表于 2021-5-5 17:09

同样在学习数据结构！考研加油

dingallen216 发表于 2021-5-5 17:33

Abrahams 发表于 2021-5-5 17:09
同样在学习数据结构！考研加油

加油，兄弟

lin1 发表于 2021-5-5 17:38

加油，正好在学数据结构和算法，刚看到链表就看见你的贴了。

绝地飞鸿 发表于 2021-5-5 22:51

cao777 发表于 2022-8-15 16:50

标记一下这个不错的

页: [1]

吾爱破解 - 52pojie.cn's Archiver

线性表C++的两种实现(顺序表示、单链表)