第一章 线性表
1 顺序表
#include<stdlib.h>
#include<stdio.h>
#include<iostream>
using namespace std;
#define MaxSize 50 // 定义静态分配线性表最大长度
#define InitSize 10 // 定义动态分配线性表最大长度
//1)⭐静态分配(不常用)
//typedef struct
//{
// int data[InitList]; // 顺序表的元素,int可以ElemType
// int length; // 顺序表的当前长度
//}SqlList; // 顺序表的类型定义
//2)⭐动态分配(常用)
typedef struct
{
int *data; // 指示动态分配数组的指针
int length; // 数组的当前个数
int MaxSize; // 数组的最大容量
}SqlList; // 动态分配数组顺序表的类型定义
// 3)⭐初始化顺序表
void InitList(SqlList &L)
{
L.data = (int*)malloc(sizeof(int)*InitSize); // C的初始动态分配语句
// L.data = new int[InitSize]; // C++的初始动态分配语句
L.length = 0;
L.MaxSize = InitSize;
}
// 4)⭐增加顺序表的长度
void IncreaseSize(SqlList &L, int len)
{
int* p = L.data;
L.data = (int*)malloc((L.MaxSize + len) * sizeof(int));
for (int i = 0; i < L.length; i++)
L.data[i] = p[i];
L.MaxSize += len;
free(p);
}
// 5)⭐插入操作,在第i个位置插入元素e
bool ListInsert(SqlList &L, int i, int e)
{
if (i < 1 || i > L.length + 1) return false; // 判断i的范围是否有效
if (L.length >= L.MaxSize) return false; // 当前存储空间已满,不能插入
for (int j = L.length; j >= i; j--) // 在第i个元素及之后的元素后移
L.data[j] = L.data[j - 1];
L.data[i - 1] = e; // 在位置i处放入e
L.length ++; // 线性长度加1
return true;
}
// 6)⭐删除操作:删除第i个位置上的元素e
bool ListDelete(SqlList &L, int i, int &e)
{
if (i < 1 || i > L.length) return false; // 判断i的范围是否有效
e = L.data[i - 1]; // 将被删除的元素赋值给e
for (int j = i; j < L.length; j++) // 将第i个位置后的元素前移
L.data[j - 1] = L.data[j];
L.length--; // 线性表长度减1
return true;
}
// 7)⭐按位查找:回位序i的元素
int GetElem(SqlList L, int i) {
if (i<1 || i>L.length) return -1;
return L.data[i - 1];
}
// 8)⭐按值查找(顺序查找):查找第一个元素值等于e的元素,并返回其位序
int LocateElem(SqlList L, int e)
{
for (int i = 0; i < L.length; i++)
if (L.data[i] == e) return i + 1; // 下标为i的元素值等于e,返回其位序i + 1
return 0; // 否则退出循环,说明查找失败
}
// 9)⭐删除值位于s和t之间的数
bool Delete_s_t(SqlList& L, int s, int t) {
if (L.length == 0 || s >= t) return false;
int k = 0;
for (int i = 0; i < L.length; i++)
if (L.data[i]<s || L.data[i]>t)
L.data[k++] = L.data[i];
L.length = k;
return true;
}
int main() {
SqlList L;
InitList(L);
ListInsert(L, 1, 1);
ListInsert(L, 2, 6);
ListInsert(L, 3, 3);
ListInsert(L, 4, 8);
ListInsert(L, 5, 2);
for (int i = 0; i < L.length; i++)
cout << L.data[i] << " ";
cout << endl;
Delete_s_t(L, 2, 3);
for (int i = 0; i < L.length; i++)
cout << L.data[i] << " ";
cout << endl;
return 0;
}
2 单链表
#include<iostream>
#include<algorithm>
using namespace std;
// 1)⭐定义单链表结点类型
typedef struct LNode
{
int data; // 数据域
struct LNode *next; // 指针域
}LNode, *LinkList; //强调节点用LNode; 强调链表用LinkList
//struct LNode* == LinkList
// 2)⭐头插法建立单链表
LinkList List_HeadInsert(LinkList &L)
{
LNode* s; int x;
L = (LinkList)malloc(sizeof(LNode)); // 创建头结点
L->next = NULL; // 初始为空链表
scanf("%d", x); // 输入结点的值
while (x != 9999) // 输入9999表示结束
{
s = (LNode*)malloc(sizeof(LNode)); // 否则,创建新节点
s->data = x;
s->next = L->next;
L->next = s; // 将新节点插入表中,L为头指针
scanf("d", &x);
}
return L;
}
// 3)⭐尾插法建立单链表
LinkList List_TailInsert(LinkList& L) // 正向建立单链表
{
int x; // 设元素类型为整形
LNode *s, *r = L; // r表示表尾指针
L = (LinkList)malloc(sizeof(LNode)); // 创建头结点
while (x != 9999) // 输入9999表示结束
{
s = (LNode *)malloc(sizeof(LNode)); // 否则,创建新节点
s->data = x;
r->next = s;
L = s; // r指向新的表尾结点
scanf("d", &x);
}
r->next = NULL; // 尾结点指针置空
return L;
}
// 4)⭐按序号查找:从第一个结点出发,顺指针next域搜,直到i,否则返回最后一个指针结点域NULL
LNode *GetElem(LinkList L, int i)
{
int j = 1; // 计数,初始为1
LNode* p = L->next; // 第1个结点指针赋给p
if (i == 0) return L; // 若i等于0,则返回头结点
if (i < 1) return NULL; // 若i无效,则返回NULL
while (p && j < i) // 从第1个结点开始找,查找第i个结点
{
p = p->next;
j ++ ;
}
return p; // 返回第i个结点的指针,若i大于表长,则返回NULL
}
// 5)⭐按值查找:找到数据域等于e的点
LNode* LocateElem(LinkList L, int e)
{
LNode *p = L->next;
while (p != NULL && p->data != e) // 从第一个结点开始查找data域为e的结点
p = p->next;
return p; // 找到后返回该结点指针,否则返回NULL
}
// 6)⭐后插操作,在节点p之后插入元素e(通常使用后插)
bool InsertNextNode(LNode* p, int e)
{
if (p == NULL) return false;
LNode *s = (LNode*)malloc(sizeof(LNode)); // 定义结点s用来存放e,并将其放到链表中
if (s == NULL) return false;
s->data = e; // 先存数据
s->next = p->next; // 再
p->next = s; // 最后
return true;
}
// 7)⭐前插操作,在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e)
{
if (p == NULL) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (s == NULL) return false;
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
// 8)⭐删除操作:删除位序i的节点,e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
if (L == NULL) // 先检查删除位置的合法性
{
e = -1;
return false;
}
if (i < 1) return false;
if (i > 1)
{
LNode* p = GetElem(L, i - 1); // 查找删除位置的前驱结点
if (!p || !(p->next)) return false;
LNode* q = p->next; // 令q指向被删除结点
e = q->data;
p->next = q->next; // 将*q结点从链中断开
free(q); // 释放结点存储空间
}
else
{
if (L->next == NULL)
{
e = L->data;
L = NULL;
}
else
{
e = L->data;
L = L->next;
}
}
return true;
}
// 9)⭐删除指定节点*P:从头结点顺序找到前驱结点,然后执行删除操作
bool DeleteNode(LNode* p)
{
if (p->next == NULL) return false;
//下面这段代码有bug,不能删除最后一个节点,因此要是删除最后一个节点的话要重新进行操作
LNode* q = p->next;
p->data = q->data;
p->next = q->next;
free(q); // fee(q)的作用是由系统回收一个LNode型的结点,回收后的空间可供再次生成结点时用
return true;
}
// 10)⭐统计单链表的长度
int Length(LinkList L)
{
int len = 0;
LNode* p = L;
while (p)
{
len++;
p = p->next;
}
return len;
}
// 11)⭐输出链表
void print(LinkList L) {
LNode* s = L;
while (s!= NULL)
{
cout << s->data << " ";
s = s->next;
}
cout << endl;
}
int main() {
LinkList L;
List_HeadInsert(L);
cout << "头插法的结果" << endl;
print(L);
//List_TailInsert(L);
//cout << "尾插法的结果" << endl;
//print(L);
cout << "链表的第1个元素:" << GetElem(L, 1)->data << endl;
cout << "链表的长度:" << Length(L) << endl;
int e;
ListDelete(L, 5, e);
cout << "删除的第1个元素是:" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListInsert(L, 5, e);
cout << "插入的第1个元素是:" << e << endl;
cout << "当前的链表" << endl;
print(L);
LNode* s = LocateElem(L, 5);
return 0;
}
3 双链表(带头结点)
#include<iostream>
using namespace std;
typedef int ElemType;
// 1)⭐双链表中的结点类型描述
typedef struct DNode
{
ElemType data; // 数据域
struct DNode* prior, * next; // 前驱和后继指针
}DNode, * DLinkList;
// 2)⭐初始化双链表
bool InitDLinkList(DLinkList& L)
{
L = (DNode*)malloc(sizeof(DNode));
if (L == NULL) return false;
L->prior = NULL;
L->next = NULL;
return true;
}
// 3)⭐判断双链表是否为空
bool empty(DLinkList L)
{
if (L->next = NULL)
return true;
return false;
}
// 4)⭐按位查找:返回第i个结点的值
DNode* GetElem(DLinkList L, int i)
{
if (i < 0) return NULL;
int j = 0;
DNode* p = L;
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p;
}
// 5)⭐按值查找:找到第一个数据域为e的结点
DNode* LocateElem(DLinkList L, ElemType e) {
DNode* p = L;
if (p == NULL) return NULL;
p = p->next;
while (p != NULL && p->data != e)
{
p = p->next;
}
return p;
}
// 6)⭐插入操作:p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {
if (p == NULL || s == NULL) return false;
s->next = p->next; // 先把s和p后面的结点连接好
if(p->next != NULL)
p->next->prior = s;
s->prior = p; // 再把p和s连接好
p->next = s;
}
// 7)⭐在p节点后面插入值是e的节点
bool InsertNextDNode(DNode* p, ElemType e) {
if (p == NULL) return false;
DNode* q = (DNode*)malloc(sizeof(DNode)); // 先定义结点q,用来存放e
q->data = e;
q->next = NULL;
q->prior = p; // 因为是双链表的结点,所以指针都要处理好
if (p->next != NULL)
{
q->next = p->next;
p->next->prior = q;
}
p->next = q;
q->prior = p;
return true;
}
// 8)⭐按位插入:第i个位置插入值为e的节点(位序i)
bool InsertDLinkList(DLinkList& L, int i, ElemType e) {
if (i <= 0) return false;
DNode* p = GetElem(L, i - 1); // 先查找操作
return InsertNextDNode(p, e); // 再删除操作
}
// 9)⭐删除操作:删除p节点的后继节点
bool DeleteNextNode(DNode* p)
{
if (p == NULL) return false;
DNode* q = p->next; // 先定义结点q是p的下一个结点
if (q == NULL) return false;
p->next = q->next; // 让p的next指向q的next
if (q->next != NULL) q->next->prior = p; // 让q的next结点的prior指向p
free(q); // 释放q
return true;
}
// 10)⭐销毁双链表
bool DestoryList(DLinkList& L)
{
while (L->next != NULL)
DeleteNextNode(L);
free(L); // 释放头结点的空间
L = NULL;
return true;
}
// 11)⭐尾插法
DLinkList List_TailInsert(DLinkList& L) {
InitDLinkList(L);
DNode* p = L;
int x;
while (cin >> x)
{
InsertNextDNode(p, x);
p = p->next;
}
return L;
}
// 12)⭐头插法
DLinkList List_HeadInsert(DLinkList& L)
{
InitDLinkList(L);
int x;
while (cin >> x)
InsertNextDNode(L, x);
return L;
}
// 13)⭐求长度
int Length(DLinkList L)
{
DNode* p = L;
int len = 0;
while (p->next != NULL)
{
len++;
p = p->next;
}
return len;
}
// 14)⭐删除指定节点s
bool DeleteNode(DNode* s)
{
DNode* p;
p = s->prior;
p->next = s->next;
if (s->next != NULL)
s->next->prior = p;
free(s);
return true;
}
// 15)⭐删除位序i的节点,e是i节点的值
bool ListDelete(DLinkList& L, int i, ElemType& e)
{
if (i <= 0 || i > Length(L)) return false;
DNode* s;
s = GetElem(L, i);
if (s == NULL) return false;
e = s->data;
return DeleteNode(s);
}
// 16)⭐输出链表
void print(DLinkList L)
{
DNode* p = L->next;
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main() {
DLinkList L;
//cout << "头插法" << endl;
//List_HeadInsert(L);
//print(L);
cout << "尾插法" << endl;
List_TailInsert(L);
print(L);
cout << "长度:" << Length(L) << endl;
cout << "第1个元素为:" << GetElem(L, 1)->data << endl;
cout << "第5个元素为:" << GetElem(L, 5)->data << endl;
cout << "在第一个位置插入元素0" << endl;
InsertDLinkList(L, 1, 0);
print(L);
cout << "在最后一个位置插入元素6" << endl;
InsertDLinkList(L, 7, 6);
print(L);
int e;
ListDelete(L, 1, e);
cout << "删除第一个节点:" << e << endl;
cout << "当前链表为" << endl;
print(L);
ListDelete(L, 6, e);
cout << "删除最后一个节点:" << e << endl;
cout << "当前链表为" << endl;
print(L);
DestoryList(L);
return 0;
}
4 循环单链表
#include<iostream>
#include<algorithm>
using namespace std;
// 描述结点类型
typedef struct LNode
{
int data;
struct LNode* next;
}LNode, * LinkList;
//struct LNode* == LinkList
// 初始化循环单链表
bool InitList(LinkList& L)
{
L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
L->next = L;
return true;
}
//按位查找,返回第i个元素(带头节点)
LNode* GetElem(LinkList L, int i)
{
if (i < 0) return NULL;
if (i == 0) return L;
int j = 1;
LNode* p = L->next;
while (p != L && j < i)
{
p = p->next;
j++;
}
return p;
}
//按值查找,找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e)
{
LNode* p = L->next;
while (p != L && p->data != e)
p = p->next;
if (p->data == e) return p;
return NULL;
}
//统计单链表的长度
int Length(LinkList L) {
int len = 0;
LNode* p = L;
while (p->next != L)
{
len++;
p = p->next;
}
return len;
}
//后插操作,在节点p之后插入元素e
bool InsertNextNode(LNode* p, int e)
{
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
//带头节点的插入操作,在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e)
{
if (i < 1) return false;
LNode* p = GetElem(L, i - 1);
if (!p) return false;
return InsertNextNode(p, e);
}
//前插操作,在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e)
{
if (!p) return false;
LNode* s = (LNode*)malloc(sizeof(LNode));
if (!s) return false;
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
//前插操作,在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
if (!p || !s) return false;
s->next = p->next;
p->next = s;
swap(s->data, p->data);
return true;
}
//删除位序i的节点,e是i节点的值
bool ListDelete(LinkList& L, int i, int& e)
{
if (i < 1) return false;
LNode* p = GetElem(L, i - 1);
if (p == NULL || p->next == L) return false;
LNode* q = p->next;
e = q->data;
p->next = q->next;
free(q);
return true;
}
//删除指定节点P
bool DeleteNode(LinkList& L, LNode* p)
{
LNode* q = p->next;
p->data = q->data;
p->next = q->next;
if (L == q) {
L = p;
}
free(q);
return true;
}
//尾插法,带头结点
LinkList List_TailInsert(LinkList& L)
{
InitList(L);
LNode* s, * r = L; //r表示表尾指针
int x;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
}
r->next = L;
return L;
}
//头插法,带头结点
LinkList List_HeadInsert(LinkList& L) {
InitList(L);
LNode* s, * r = L;
int x;
bool isFirst = true;
while (cin >> x) {
s = (LNode*)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
if (isFirst) {
r = s;
isFirst = false;
}
}
r->next = L;
return L;
}
bool Empty(LinkList L) {
if (L->next == L) {
return true;
}
return false;
}
//判断是否为表尾节点
bool isTail(LinkList L, LNode* p) {
if (p->next == L) return true;
return false;
}
void print(LinkList L) {
LNode* s = L->next;
while (s != L) {
cout << s->data << " ";
s = s->next;
}
cout << endl;
}
int main() {
LinkList L;
//List_HeadInsert(L);
//cout << "头插法的结果" << endl;
//print(L);
List_TailInsert(L);
cout << "尾插法的结果" << endl;
print(L);
cout << "链表的第1个元素:" << GetElem(L, 1)->data << endl;
cout << "链表的第5个元素:" << GetElem(L, 5)->data << endl;
cout << "链表的长度:" << Length(L) << endl;
int e;
ListDelete(L, 5, e);
cout << "删除的第5个元素是:" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListInsert(L, 5, e);
cout << "插入的第5个元素是:" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListDelete(L, 1, e);
cout << "删除的第1个元素是:" << e << endl;
cout << "当前的链表" << endl;
print(L);
ListInsert(L, 1, e);
cout << "插入的第1个元素是:" << e << endl;
cout << "当前的链表" << endl;
print(L);
LNode* s = LocateElem(L, 5);
DeleteNode(L, s);
print(L);
return 0;
}
/*
输入样例:
1 2 3 4 5
*/
5 循环双链表
#include<iostream>
using namespace std;
typedef int ElemType;
typedef struct DNode {
ElemType data;
struct DNode* prior, * next;
}DNode, * DLinkList;
//初始化双链表
bool InitDLinkList(DLinkList& L) {
L = (DNode*)malloc(sizeof(DNode));
if (L == NULL) {
return false;
}
L->prior = L;
L->next = L;
return true;
}
//判断双链表是否为空
bool empty(DLinkList L) {
if (L->next = L) {
return true;
}
return false;
}
bool isTail(DLinkList L, DNode* p) {
if (p->next == L) return true;
return false;
}
//按位查找:返回第i个结点
DNode* GetElem(DLinkList L, int i) {
if (i < 0) return NULL;
if (i == 0) return L;
int j = 1;
DNode* p = L->next;
while (p != L && j < i) {
p = p->next;
j++;
}
if (p == L) return NULL;
return p;
}
//按值查找:找到第一个数据域为e的结点
DNode* LocateElem(DLinkList L, ElemType e) {
DNode* p = L;
if (p == NULL) return NULL;
p = p->next;
while (p != L && p->data != e) {
p = p->next;
}
if (p == L) return NULL;
return p;
}
//在p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {
if (p == NULL || s == NULL) {
return false;
}
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
}
//在p节点后面插入值是e的节点
bool InsertNextDNode(DNode* p, ElemType e) {
if (p == NULL) return false;
DNode* q = (DNode*)malloc(sizeof(DNode));
if (q == NULL) return false;
q->data = e;
q->prior = p;
p->next->prior = q;
q->next = p->next;
p->next = q;
return true;
}
//前插,在p节点前面插入节点s
bool InsertPriorDnode(DNode* p, DNode* s) {
return InsertNextDNode(p->prior, s);
}
//按位插入,在第i个位置插入值为e的节点(位序i)
bool InsertDLinkList(DLinkList& L, int i, ElemType e) {
if (i <= 0) return false;
DNode* p = GetElem(L, i - 1);
return InsertNextDNode(p, e);
}
//删除p节点的后继节点
bool DeleteNextNode(DNode* p) {
if (p == NULL) return false;
DNode* q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
return true;
}
//销毁双链表
bool DestoryList(DLinkList& L) {
while (L->next != L) {
DeleteNextNode(L);
}
free(L);
L = NULL;
return true;
}
//尾插法
DLinkList List_TailInsert(DLinkList& L) {
InitDLinkList(L);
DNode* p = L;
ElemType x;
while (cin >> x) {
InsertNextDNode(p, x);
p = p->next;
}
return L;
}
//头插法
DLinkList List_HeadInsert(DLinkList& L) {
InitDLinkList(L);
ElemType x;
while (cin >> x) {
InsertNextDNode(L, x);
}
return L;
}
int Length(DLinkList L) {
DNode* p = L;
int len = 0;
while (p->next != L) {
len++;
p = p->next;
}
return len;
}
//删除指定节点s
bool DeleteNode(DNode* s) {
DNode* p;
p = s->prior;
p->next = s->next;
s->next->prior = p;
free(s);
return true;
}
//删除位序i的节点,e是i节点的值
bool ListDelete(DLinkList& L, int i, ElemType& e) {
if (i <= 0 || i > Length(L)) return false;
DNode* s;
s = GetElem(L, i);
if (s == NULL) return false;
e = s->data;
return DeleteNode(s);
}
void print(DLinkList L) {
DNode* p = L->next;
while (p != L) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
void testDLinkList() {
DLinkList L;
//cout << "头插法" << endl;
//List_HeadInsert(L);
//print(L);
cout << "尾插法" << endl;
List_TailInsert(L);
print(L);
cout << "长度:" << Length(L) << endl;
cout << "第1个元素为:" << GetElem(L, 1)->data << endl;
cout << "第5个元素为:" << GetElem(L, 5)->data << endl;
cout << "在第一个位置插入元素0" << endl;
InsertDLinkList(L, 1, 0);
print(L);
cout << "在最后一个位置插入元素6" << endl;
InsertDLinkList(L, 7, 6);
print(L);
int e;
ListDelete(L, 1, e);
cout << "删除第一个节点:" << e << endl;
cout << "当前链表为" << endl;
print(L);
ListDelete(L, 6, e);
cout << "删除最后一个节点:" << e << endl;
cout << "当前链表为" << endl;
print(L);
DestoryList(L);
}
int main() {
testDLinkList();
return 0;
}
6 静态链表
#include<iostream>
using namespace std;
#define MaxSize 10 // 静态链表的最大长度
typedef struct
{
int data; // 存储数据元素
int next; // 下一个元素的数组下标
}SLinkList[MaxSize];
// 初始化静态链表
void InitSLinkList(SLinkList L)
{
for (int i = 0; i < MaxSize; i++)
L[i].next = -2; //-2表时链表这个位置是空的
L[0].next = -1;
}
//判断双链表是否为空
bool empty(SLinkList L)
{
if (L[0].next = -1) return true;
return false;
}
//得到第i个元素的下标
int Get_Index(SLinkList L, int i)
{
int j = 0; //模拟指针
int cnt = 0; //计数
while (j != -1 && cnt < i) {
cnt++;
j = L[j].next;
//cout << j << " " << L[j].next << endl;
}
if (cnt != i) return -1; //不存在
return j;
}
//得到第一个是空的元素的位序
int Get_First_Empty_Node(SLinkList L) {
for (int i = 1; i < MaxSize; i++) {
if (L[i].next == -2) return i;
}
}
// 返回L的第i个元素
ElemType GetElem(SLinkList L, int i)
{
int j = Get_Index(L, i);
return L[j].data;
}
//在第i个节点后面插入值是e的节点
bool InsertNextSNode(SLinkList L, int i, ElemType e) {
int j = Get_Index(L, i);
//cout << j << endl;
int k = Get_First_Empty_Node(L); //第一个空节点的位置
L[k].next = L[j].next;
L[j].next = k;
L[k].data = e;
return true;
}
//删除第i个节点 e是删除元素的值
bool DeleteNode(SLinkList L, int i, ElemType& e) {
int j = Get_Index(L, i);
//cout <<i<< " " << j << endl;
if (L[j].next == -1) { //最后一个要特判
//cout << "asdad" << endl;
int k = Get_Index(L, i - 1);
L[j].next = -2;
e = L[j].data;
L[k].next = -1;
return true;
}
//相当于交换次序,跟王道之前的删除方法类似
e = L[j].data;
int tmp = L[j].next;
L[j].data = L[L[j].next].data;
L[j].next = L[L[j].next].next;
L[tmp].next = -2;
return true;
}
//插入(默认开始是空的)
bool List_Insert(SLinkList L) {
int tot = 1 , pre = 0;
ElemType x;
while (cin >> x) {
L[tot].data = x;
L[tot].next = -1;
L[pre].next = tot;
pre = tot++;
}
return true;
}
void print(SLinkList L) {
int i = L[0].next;
while (~i) {
cout << L[i].data << " ";
i = L[i].next;
}
cout << endl;
}
void testSLinkList() {
SLinkList L;
InitSLinkList(L);
List_Insert(L);
print(L);
cout <<"第1个元素是:"<< GetElem(L, 1) << endl;
cout <<"第3个元素是:"<< GetElem(L, 3) << endl;
cout <<"第5个元素是:"<< GetElem(L, 5) << endl;
InsertNextSNode(L, 0, 0);
print(L);
InsertNextSNode(L, 1, 6);
print(L);
InsertNextSNode(L, 7, 7);
print(L);
//cout << "-------------" << endl;
//for (int i = 0; i <= 8; i++) {
// cout << L[i].next << endl;
//}
int e;
DeleteNode(L, 8, e);
cout << e << endl;
print(L);
DeleteNode(L, 2, e);
cout << e << endl;
print(L);
DeleteNode(L, 1, e);
cout << e << endl;
print(L);
}
int main() {
testSLinkList();
return 0;
}
/*
1 2 3 4 5
*/