数据结构
一、线性表
1. 顺序表(静态分配)
#include <iostream>
using namespace std;
#define TRUE 1 //逻辑真
#define FALSE 0 //逻辑假
#define OK 1 //正确
#define ERROR 0 //错误
#define INFEASIBLE -1 //不可能，非法操作
#define OVERFLOW -2 //溢出
typedef int Status;
typedef int ElemType;
#define MaxSize 100
typedef struct {
int data[MaxSize];
int Length;
} SqList;
Status InitList(SqList &L) {
for (int i = 0; i < MaxSize; i++) {
L.data[i] = 0; }
L.Length = 0; //顺序表初始长度为0
return OK;
}
Status TraverseListSq_Static(SqList L) {
int i;
for (i = 0; i < L.Length; ++i) {
cout << L.data[i] << " ";
}
cout << endl;
return OK;
}
Status ListInsert(SqList &L, int i, int e) {
if (i < 1 || i > L.Length + 1) {return FALSE;}
if (L.Length > MaxSize) {return FALSE;}
for (int j = L.Length; j > i - 1; j--) {
L.data[j] = L.data[j-1];
}
L.data[i-1] = e;
L.Length++;
return OK;
}
Status GetElem(SqList L, int i, int &e) {
if (i<1 || i>L.Length+1){
return ERROR;
}
e = L.data[i - 1];
return OK; //注意是i-1
}
int LocateListSq_Static(SqList L, ElemType e) {
int i;
for (i = 0; i < L.Length; ++i) {
if (L.data[i] == e) {
break;
}
}
return i;
}
Status ListDelete(SqList &L, int i, int &e) { // e用引用型参数
//判断i的范围是否有效
if (i < 1 || i > L.Length + 1) { return FALSE; }
e = L.data[i - 1]; //将被删除的元素赋值给e
for (int j = i-1; j < L.Length - 1; j++) { //将第i个后的元素前移
L.data[j] = L.data[j+1];
}
L.Length--; //长度减1
return OK;
}
int LengthListSq_Static(SqList L) {
return L.Length;
}
Status EmptyListSq_Static(SqList L) {
return L.Length == 0;
}
Status ClearListSq_Static(SqList &L) {
L.Length = 0;
return OK;
}
2. 顺序表(动态分配)
#include <iostream>
using namespace std;
#define TRUE 1 //逻辑真
#define FALSE 0 //逻辑假
#define OK 1 //正确
#define ERROR 0 //错误
#define INFEASIBLE -1 //不可能，非法操作
#define OVERFLOW -2 //溢出
typedef int Status;
typedef int ElemType;
#define ListMaxSize 100
//顺序表存储类型描述，SqList为顺序表类型
typedef struct {
ElemType *elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配的存储容量
} SqList;
Status InitListSq(SqList &L) {
L.elem = new ElemType[ListMaxSize];
if (!L.elem) return OVERFLOW;
L.length = 0;
L.listsize = ListMaxSize;
return OK;
}
//取元素
Status GetListSq(SqList L, int i, ElemType &e) {
if (i < 1 || i > L.length) return ERROR;
e = *(L.elem + i - 1);
return OK;
}
//定位
int LocateListSq(SqList L, ElemType e) {
int i;
ElemType *p;
i = 1;
p = L.elem;
while (i <= L.length && *p++ != e) i++;
if (i <= L.length) return i;
else return 0;
}
//插入
Status InsertListSq(SqList &L, int i, ElemType e) {
ElemType *p, *q;
if (i < 1 || i > L.length + 1) return ERROR;
if (L.length >= L.listsize) return OVERFLOW;
q = L.elem + i - 1;
for (p = L.elem + L.length - 1; p >= q; p--) *(p + 1) = *p;
*q = e;
L.length++;
return OK;
}
//删除
Status DeleteListSq(SqList &L, int i, ElemType &e) {
ElemType *p, *q;
if (i < 1 || i > L.length) return ERROR;
p = L.elem + i - 1;
e = *p;
q = L.elem + L.length - 1;
for (++p; p <= q; p++) *(p - 1) = *p;
L.length--;
return OK;
}
//遍历，这里是输出顺序表
void TraverseListSq(SqList L) {
ElemType *p;
p = L.elem;
while (p <= L.elem + L.length - 1)
cout << *p++ << " ";
cout << endl;
}
//求长度
int LengthListSq(SqList L) {
return L.length;
}
//判空
Status EmptyListSq(SqList L) {
return L.length == 0;
}
//清空
void ClearListSq(SqList &L) {
L.length = 0;
}
//销毁
void DestroyListSq(SqList &L) {
L.length = L.listsize = 0;
delete[] L.elem;
L.elem == NULL;
}
//复杂操作的实现
//顺序表逆置，即将顺序表首尾颠倒存放
void InverseListSq(SqList &L) {
ElemType *p, *q, temp;
for (p = L.elem, q = L.elem + L.length - 1; p < q; p++, q--) {
temp = *p;
*p = *q;
*q = temp;
}
}
//顺序表的逆置，对start，end之间的元素逆置
void Inverse(SqList &L, int start, int end) {
int i, j;
ElemType temp;
for (i = start, j = end; i < j; i++, j--) {
temp = L.elem[i - 1];
L.elem[i - 1] = L.elem[j - 1];
L.elem[j - 1] = temp;
}
}
//顺序表的左循环移位， m 表示向左移位个数，利用逆置算法
void CycMoveListSq(SqList &L, int m) {
if (m < 0) {
cout << "输入的左移位个数错误！" << endl;
return;
}
if (L.length <= 1) return;
m %= L.length;
Inverse(L, 1, L.length);
Inverse(L, 1, L.length - m);
Inverse(L, L.length - m + 1, L.length);
}
//顺序表排序，采用选择排序方法
void SortListSq(SqList &L) {
int i, j, k;
ElemType temp;
for (i = 0; i < L.length - 1; i++) {
k = i;
for (j = i + 1; j < L.length; j++)
if (*(L.elem + k) > *(L.elem + j)) k = j;
if (k != i) {
temp = *(L.elem + i);
*(L.elem + i) = *(L.elem + k);
*(L.elem + k) = temp;
}
}
}
//约瑟夫环问题，n表示圆桌上人的个数，s表示从第几个人开始报数，m表示数到几的人离开桌子
void Josephus(SqList &L, int n, int m, int s) {
//初始化圆桌
L.length = n;
for (int i = 0; i < n; i++)
L.elem[i] = i + 1;
cout << "圆桌初始状态：" << endl;
TraverseListSq(L);
int len = n;
int i;
int p = (s - 1) % len;
while (len > 1) {
p = (p + m - 1) % len;
int t = L.elem[p];
for (i = p + 1; i < len; i++)
L.elem[i - 1] = L.elem[i];
L.elem[len - 1] = t;
len--;
}
InverseListSq(L);
cout << "离开圆桌的顺序为：" << endl;
TraverseListSq(L);
}
3. 单链表
#include <iostream>
using namespace std;
//定义必须的常量和类型
#define TRUE 1 //逻辑真
#define FALSE 0 //逻辑假
#define OK 1 //正确
#define ERROR 0 //错误
#define INTEASIBLE -1 //不可能，非法操作
#define OVERFLOW -2 //溢出
//定义状态类型
typedef int Status;
//链表的数据元素类型为整型（可根据需要修改为其他类型）
typedef int ElemType;
//链表存储类型描述
typedef struct LNode {
ElemType data; //数据域
struct LNode *next; //指针域
} LNode, *LinkList;
//基本操作的实现
//初始化
Status InitList_L(LinkList &L) {
L = new LNode;
L->next = NULL;
if(!L){return ERROR;}
return OK;
}
void visit(LinkList L) //访问单个元素
{
cout<<L->data<<endl;
}
//遍历，这里是输出顺序表
void TraverseList_L(LinkList L) {
LinkList p=L->next;
while (p) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
//插入
Status ListInsert_L(LinkList &L, int i, ElemType e) {
// cout<<" ListInsert_L 执行了！";
LinkList p = L,s;
int j = 0;
while (p && j < i - 1) {
p = p->next;
++j; //寻找第i-1个结点
}
if (!p || j>i-1){
return ERROR; //i大于表长+1或者小于1
}
s = new LNode; //生成新结点s
s->data = e; //将结点s的数据域置为e
s->next=p->next;//将结点s插入L中
p->next=s;
return OK;
}
//删除
Status DeleteList_L(LinkList &L, int i, ElemType &e){
LinkList p=L,q;
int j=0;
while (p->next && j<i-1){//寻找第i个结点，并令p指向其前驱
p = p->next;
++j;
}
if (!(p->next)||j>i-1){
return ERROR;//删除位置不合理
}
q=p->next;//临时保存被删除结点的地址以备释放
p->next=q->next; //改变删除结点前驱结点的指针域
e=q->data; //保存删除结点的数据域
delete q;//释放删除结点的空间
return OK;
}
Status LocateElem_L(LinkList L, ElemType &e) {
LinkList p;
p = L->next;
int i=0;
while (p && p->data != e) {
p = p->next;
i++;
}
return i;//返回L中值为e的数据元素的位置，查找失败返回NULL
}
//头插发
void CreateList_F(LinkList &L,int n){
L=new LNode;
L->next=NULL; //先建立一个带头结点的单链表
for(int i=n;i>0;--i){
LinkList p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=L->next;
L->next=p; //插入到表头
}
}
void CreateList_L(LinkList &L,int n){
//正位序输入n个元素的值，建立带表头结点的单链表L
L=new LNode;
L->next=NULL;
LinkList r=L; //尾指针r指向头结点
for(int i=0;i<n;++i){
LinkList p=new LNode; //生成新结点
cin>>p->data; //输入元素值
p->next=NULL; r->next=p; //插入到表尾
r=p; //r指向新的尾结点
}
}
Status GetElem_L(LinkList L, int i, ElemType &e) {
LinkList p;
p = L->next;
int j = 1;//初始化
while (p && j < i) {//向后扫描，直到p指向第i个元素或p为空
p = p->next;
++j;
}
if (!p || j > i) {
return ERROR;//第i个元素不存在
}
e = p->data;//取第i个元素
return OK;
}
//求长度
int LengthList_L(LinkList L) {
// 返回L中元素个数
LinkList p;
p = L->next;//p指向第一个结点
int i = 0;
while (p) {
i++;
p = p->next;
}
return i;
}
//清空
Status ClearList(LinkList &L) {
//将L重置为空表
LinkList p, q;
p = L->next;//p指向第一个结点
while (p) //没到表尾
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;
return OK;
}
Status ListEmpty(LinkList L) {
//若L为空表，则返回OK，否则返回ERROR
if (L->next) {//非空
return OK;
} else {
return ERROR;
}
}
//销毁
Status DestroyList_L(LinkList &L) {
while (L) {
LinkList p;
p = L;
L = L->next;
delete p;
}
return OK;
}
//查找一个元素
int find(LinkList &L,int s)//查找元素s
{
LinkList p=L->next;
int i=0;
int j= LengthList_L(L);
while(p->data!=s && i!=j)
{
p=p->next;
i++;
}
if(i==j) cout<<"未找到";
else cout<<"第"<<i+1<<"个元素"<<endl;
return 0;
}
int reverse(LinkList &L)//链表逆置
{
LinkList p=L->next;
L->next=NULL;
while(p)
{
LinkList q=p->next;
p->next=L->next;
L->next=p;
p=q;
}
return 0;
}
int merge(LinkList &L,LinkList &s)//归并排序 从小到大
{
LinkList p=L->next;
L->next=NULL;
int L_len = LengthList_L(L);
int S_len = LengthList_L(s);
L_len+=S_len;
s=s->next;
LinkList o=L;
while(s&&p)
{
if(s->data<p->data)
{
LinkList q=s->next;
s->next=L->next;
L->next=s;
s=q;
}
else
{
LinkList q=p->next;
p->next=L->next;
L->next=p;
p=q;
}
L=L->next;
}
if(p) L->next=p;
else L->next=s;
L=o;
return 0;
}
4. 双链表
#include <iostream>
using namespace std;
//定义必须的常量和类型
#define TRUE 1 //逻辑真
#define FALSE 0 //逻辑假
#define OK 1 //正确
#define ERROR 0 //错误
#define INTEASIBLE -1 //不可能，非法操作
#define OVERFLOW -2 //溢出
//定义状态类型
typedef int Status;
//链表的数据元素类型为整型（可根据需要修改为其他类型）
typedef int ElemType;
//链表存储类型描述
typedef struct DulNode {
ElemType data; //数据域
struct DulNode *prior, *next; //前驱和后继指针
} DulNode, *DulLinkList;
//基本操作的实现
//初始化
Status InitDLinkList(DulLinkList &L) {
/* 产生空的双向循环链表L */
L = new DulNode;
if (!L) { return ERROR; }
L->prior = L; //头结点的prior指针永远指向NULL
L->next = L; //头结点之后暂时还没有结点
return OK;
}
int ListLength(DulLinkList L) { /* 初始条件：L已存在。操作结果： */
int i = 0;
DulLinkList p = L->next; /* p指向第一个结点 */
while (p != L) /* p没到表头 */
{
i++;
p = p->next;
}
return i;
}
//遍历，这里是输出顺序表
void TraverseList_L(DulLinkList L) {
DulLinkList p = L->next;
while (p!=L) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
Status GetElem(DulLinkList L, int i, ElemType &e) { /* 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */
int j = 1; /* j为计数器 */
DulLinkList p = L->next; /* p指向第一个结点 */
while (p != L && j < i) {
p = p->next;
j++;
}
if (p == L || j > i) /* 第i个元素不存在 */
return ERROR;
e = p->data; /* 取第i个元素 */
return OK;
}
DulLinkList GetElemP(DulLinkList L,int i) /* 另加 */
{ /* 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，*/
/* 返回NULL */
int j;
DulLinkList p=L; /* p指向头结点 */
if(i<0||i>ListLength(L)) /* i值不合法 */
return NULL;
for(j=1;j<=i;j++)
p=p->next;
return p;
}
int LocateElem(DulLinkList L, ElemType e, Status(*compare)(ElemType, ElemType)) { /* 初始条件：L已存在，compare()是数据元素判定函数 */
/* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int i = 0;
DulLinkList p = L->next; /* p指向第1个元素 */
while (p != L) {
i++;
if (compare(p->data, e)) /* 找到这样的数据元素*/
return i;
p = p->next;
}
return 0;
}
//插入
Status InsertDulLink(DulLinkList &L, int i, ElemType e) {
DulLinkList p, s;
if (i < 1 || i > ListLength(L) + 1) {
return ERROR;
}
p = GetElemP(L, i - 1); /* 在L中确定第i个元素前驱的位置指针p */
if (!p) /* p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱) */
return ERROR;
s = new DulNode; //生成新结点s
s->data = e;
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
return OK;
}
//删除
Status DeleteDulList(DulLinkList &L, int i, ElemType &e) {
DulLinkList p;
if (i<1){
return ERROR;
}
p = GetElemP(L,i);
if (!p){
return ERROR;
}
e = p->data; //保存删除结点的数据域
p->prior->next = p->next;
p->next->prior = p->prior;
delete p;//释放删除结点的空间
return OK;
}
//销毁
Status DestroyList_L(DulLinkList &L) {
DulLinkList q, p = L->next; /*p指向第一个结点*/
while (p != L) {
q = p->next;
delete p;
p = q;
}
delete L;
L = NULL;
return OK;
}
5. 静态链表
#include <iostream>
using namespace std;
#define TRUE 1 //逻辑真
#define FALSE 0 //逻辑假
#define OK 1 //正确
#define ERROR 0 //错误
#define INTEASIBLE -1 //不可能，非法操作
#define OVERFLOW -2 //溢出
//定义状态类型
typedef int Status;
//链表的数据元素类型为整型（可根据需要修改为其他类型）
typedef int ElemType;
#define MAXSIZE 1000 /*假设链表的最大长度是1000*/
typedef struct {
ElemType data;
int cur; /*游标(Cursor)，为0时表示无指向*/
} Component, StaticLinkList[MAXSIZE];
/*将一维数组space中各分量链成一备用链表*/
/*space[0].cur为头指针，"0"表示空指针*/
Status InitList(StaticLinkList &space) {
int i;
for (i = 0; i < MAXSIZE - 1; ++i) {
space[i].data=0;
space[i].cur = i + 1;
}
space[MAXSIZE - 1].cur = 0; /*目前静态链表为空，最后一个元素的cur为0*/
return OK;
}
/*若备用空间链表非空，则返会分配的结点下标，否则返会0*/
int Malloc_SLL(StaticLinkList &space) {
int i = space[0].cur; /*当前数组第一个元素的cur存的值，就是要返回的第一个备用空间的下标*/
if (space[0].cur) {
space[0].cur = space[i].cur; /*由于要拿出一个分量来使用了，所以我们就得把它的下一个分量用来做备用*/
}
return i;
}
int ListLength(StaticLinkList L) {
int j = 0;
int i = L[MAXSIZE - 1].cur;
while (i) {
i = L[i].cur;
j++;
}
return j;
}
/*在L中第i个元素前插入新的数据元素e */
Status ListInsert(StaticLinkList &L, int i, ElemType e) {
int j, k, l;
k = MAXSIZE - 1;/*注意k首先是最后一个元素的下标*/
if (i < 1 || i > ListLength(L) + 1) {
return ERROR;
}
j = Malloc_SLL(L);/*获得空闲分量的下标*/
if (j) {
L[j].data = e;/*将数据赋值给此分量的data*/
for (l = 1; l < i - 1; ++l) {/*找到第i个元素之前的位置*/
k = L[k].cur;
}
L[j].cur = L[k].cur;/*把第i个元素之前的cur赋值给新元素的cur*/
L[k].cur = j;/*把新元素的下标赋值给第i个元素之前元素的cur*/
return OK;
}
return ERROR;
}
void Free_SSL(StaticLinkList &space, int k) {
space[k].cur = space[0].cur;/*把第一个元素cur值赋给要删除的分量cur*/
space[0].cur = k;/*把要输出的分量下标赋值给第一个元素的cur*/
}
Status ListDelete(StaticLinkList &L, int i, ElemType &e) {
int j, k;
if (i < 1 || i > ListLength(L) + 1) {
return ERROR;
}
k = MAXSIZE - 1;/*注意k首先是最后一个元素的下标*/
for (j = 1; j <= i - 1; ++j) {
k = L[k].cur;
}
j = L[k].cur;
e = L[j].data;
L[k].cur = L[j].cur;
Free_SSL(L, j);
return OK;
}
Status ListTraverse_LS(StaticLinkList L) { /* 初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
int k=MAXSIZE-1;
while (L[k].cur){
k = L[k].cur;
cout<<L[k].data<<" ";
}
cout<<endl;
return OK;
}
int GetElem_LS(StaticLinkList L, int i, ElemType &e) { /* 初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
int j;
for (j = 0; j < ListLength(L); ++j) {
if (i - 1 == j) {
return L[j].data;
}
j = L[j].cur;
}
return -1;
}
int LocateElem_LS(StaticLinkList L, ElemType &e) { /* 初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
int j;
for (j = 0; j < ListLength(L); ++j) {
if (L[j].data == e) {
return L[j].cur;
}
j = L[j].cur;
}
return -1;
}
6. 循环链表
#include <iostream>
using namespace std;
//定义必须的常量和类型
#define TRUE 1 //逻辑真
#define FALSE 0 //逻辑假
#define OK 1 //正确
#define ERROR 0 //错误
#define INTEASIBLE -1 //不可能，非法操作
#define OVERFLOW -2 //溢出
//定义状态类型
typedef int Status;
//链表的数据元素类型为整型（可根据需要修改为其他类型）
typedef int ElemType;
//链表存储类型描述
typedef struct LNode {
ElemType data; //数据域
struct LNode *next; //指针域
} LNode, *LinkList;
/*初始化循环*/
Status InitList_CL(LinkList &L)
{ /* 操作结果：构造一个空的线性表L */
L=new LNode; /* 产生头结点,并使L指向此头结点 */
if(!L) /* 存储分配失败 */
return OVERFLOW;
L->next=L; /* 指针域指向头结点 循环链表的特性*/
return OK;
}
Status DestroyList_CL(LinkList &L)
{ /* 操作结果：销毁线性表L */
LinkList q,p=L->next; /* p指向头结点 */
while(p!=L) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
delete L;
L=NULL;
return OK;
}
Status ClearList_CL(LinkList *L) /* 改变L */
{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
LinkList p,q;
*L=(*L)->next; /* L指向头结点 */
p=(*L)->next; /* p指向第一个结点 */
while(p!=*L) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=*L; /* 头结点指针域指向自身 */
return OK;
}
Status ListEmpty_CL(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
if(L->next==L) /* 空 */
return TRUE;
else
return FALSE;
}
int ListLength_CL(LinkList L)
{ /* 初始条件：L已存在。操作结果：返回L中数据元素个数 */
int i=0;
LinkList p=L->next; /* p指向头结点 */
while(p!=L) /* 没到表尾 */
{
i++;
p=p->next;
}
return i;
}
Status GetElem_CL(LinkList L,int i,ElemType &e)
{ /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
int j=1; /* 初始化,j为计数器 */
LinkList p=L->next->next; /* p指向第一个结点 */
if(i<=0||i>ListLength_CL(L)) /* 第i个元素不存在 */
return ERROR;
while(j<i)
{ /* 顺指针向后查找,直到p指向第i个元素 */
p=p->next;
j++;
}
e=p->data; /* 取第i个元素 */
return OK;
}
int LocateElem_CL(LinkList L,ElemType e)
{ /* 初始条件：线性表L已存在，compare()是数据元素判定函数 */
/* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int i=0;
LinkList p=L->next->next; /* p指向第一个结点 */
while(p!=L->next)
{
i++;
if(p->data==e) /* 满足关系 */
return i;
p=p->next;
}
return 0;
}
Status PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
/* 否则操作失败，pre_e无定义 */
LinkList q,p=L->next->next; /* p指向第一个结点 */
q=p->next;
while(q!=L->next) /* p没到表尾 */
{
if(q->data==cur_e)
{
*pre_e=p->data;
return TRUE;
}
p=q;
q=q->next;
}
return FALSE;
}
Status NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继， */
/* 否则操作失败，next_e无定义 */
LinkList p=L->next->next; /* p指向第一个结点 */
while(p!=L) /* p没到表尾 */
{
if(p->data==cur_e)
{
*next_e=p->next->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
Status ListInsert_CL(LinkList &L,int i,ElemType e) /* 改变L */
{ /* 在L的第i个位置之前插入元素e */
LinkList p=L->next,s; /* p指向头结点 */
int j=0;
if(i<=0||i>ListLength_CL(L)+1) /* 无法在第i个元素之前插入 */
return ERROR;
while(j<i-1) /* 寻找第i-1个结点 */
{
p=p->next;
j++;
}
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data=e; /* 插入L中 */
s->next=p->next;
p->next=s;
if(p==L) /* 改变尾结点 */
L=s;
return OK;
}
Status ListDelete_CL(LinkList &L,int i,ElemType &e) /* 改变L */
{ /* 删除L的第i个元素,并由e返回其值 */
LinkList p=L->next,q; /* p指向头结点 */
int j=0;
if(i<=0||i>ListLength_CL(L)) /* 第i个元素不存在 */
return ERROR;
while(j<i-1) /* 寻找第i-1个结点 */
{
p=p->next;
j++;
}
q=p->next; /* q指向待删除结点 */
p->next=q->next;
e=q->data;
if(L==q) /* 删除的是表尾元素 */
L=p;
delete q; /* 释放待删除结点 */
return OK;
}
Status ListTraverse_CL(LinkList L)
{ /* 初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
LinkList p=L->next->next;
while(p!=L->next)
{
cout<<p->data<<" ";
p=p->next;
}
printf("\n");
return OK;
}
二、栈
1. 顺序栈
#include <iostream>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INTEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
//定义状态类型
typedef int Status;
//链表的数据元素类型为整型（可根据需要修改为其他类型）
typedef int SElemType;
typedef struct {
SElemType data[MAXSIZE];
int top; /* 用于栈顶指针 */
} SqStack;
/*初始化表*/
Status InitStack(SqStack &S){
S.top = -1; //初始化栈顶指针
return OK;
}
/*判栈空*/
Status StackEmpty(SqStack S){
if (S.top ==-1){
return TRUE;
} else {
return FALSE;
}
}
/*插入元素e为新的栈顶元素*/
Status Push(SqStack &S, SElemType e) {
if (S.top == MAXSIZE - 1) { /*栈满*/
return ERROR;
}
S.top++; /*栈顶指针增加一*/
S.data[S.top] = e; /*将新插入元素赋值给栈顶空间*/
return OK;
}
/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERROR */
Status Pop(SqStack &S, SElemType &e) {
if (S.top == -1) {
return ERROR;
}
e = S.data[S.top]; /*将要删除的栈顶元素赋值给e*/
S.top--; /*栈顶指针减一*/
cout<<"弹出栈:"<<e<<endl;
return OK;
}
Status GetTop(SqStack S, SElemType &e){
if (S.top == -1){
return FALSE;
}
e = S.data[S.top];
return TRUE;
}
2. 链栈
#include <iostream>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INTEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
//定义状态类型
typedef int Status;
//链表的数据元素类型为整型（可根据需要修改为其他类型）
typedef int SElemType;
typedef struct StackNode{
SElemType data;
struct StackNode *next;
}StackNode, *LinkStack;
Status InitStack(LinkStack &S){
S=NULL;
return OK;
}
Status StackEmpty(LinkStack &S){
if (S==NULL){
return TRUE;
} else {
return FALSE;
}
}
Status Push(LinkStack &S, SElemType e){
LinkStack p;
p = new StackNode; //生成新结点
if (!p){
return OVERFLOW;
}
p->data=e;
p->next=S;
S=p;
return OK;
}
Status Pop(LinkStack &S, SElemType &e){
LinkStack p;
if (S==NULL){
return ERROR;
}
e = S->data;
p=S;
S=S->next;
delete p;
return OK;
}
Status GetTop(LinkStack S, SElemType &e){
if (S==NULL){
exit(1);
} else {
return S->data;
}
}
3. 共享空间
#include <iostream>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INTEASIBLE -1
#define OVERFLOW -2
#define MAXSIZE 100
//定义状态类型
typedef int Status;
//链表的数据元素类型为整型（可根据需要修改为其他类型）
typedef int SElemType;
typedef struct {
SElemType data[MAXSIZE];
int top1; /* 用于栈1 栈顶指针 */
int top2; /* 用于栈2 栈顶指针 */
} SqDoubleStack;
/*
弹栈
*/
Status Pop(SqDoubleStack &S, SElemType &e, int stackNum) {
//栈不为空的情况，根据栈编号，pop相应的栈的元素。
//栈1空栈判断stack->top1!=-1 栈2空栈判断stack->top2 != MAXSIZE
if (stackNum == 1 && S.top1 != -1) {
e = S.data[S.top1];
S.top1--;
return OK;
}
if (stackNum == 2 && S.top2 != MAXSIZE) {
e = S.data[S.top2];
S.top2++;
return OK;
}
//栈为空或者编号不对
return ERROR;
}
/*
压栈操作
*/
Status Push(SqDoubleStack &S, SElemType e, int stackNum) {
//栈没有满的情况，根据栈编号，push相应的栈的元素。
//栈未满的条件都是stack->top1+1 < stack->top2
if (stackNum == 1 && S.top1 + 1 < S.top2) {
S.top1++;
S.data[S.top1] = e;
return OK;
}
if (stackNum == 2 && S.top1 + 1 < S.top2) {
S.top2--;
S.data[S.top2] = e;
return OK;
}
//栈已满或者编号不对
return ERROR;
}
/*
展示2个栈的元素
*/
void ShowStack(SqDoubleStack &S) {
for (int i = 0; i <= S.top1; i++) {
cout << S.data[i] << endl;
}
for (int i = S.top2; i <= MAXSIZE - 1; i++) {
cout << S.data[i] << endl;
}
cout << endl;
}
/*
清空栈元素
*/
Status ClearSeqDoubleStack(SqDoubleStack &S) {
S.top1 = -1;
S.top2 = MAXSIZE;
return OK;
}
/*
初始化栈
*/
Status InitSeqDoubleStack(SqDoubleStack &S) {
S.top1 = -1;
S.top2 = MAXSIZE;
return OK;
}
/*
栈元素个数
*/
int GetLengthSeqDoubleStack(SqDoubleStack &S) {
//stack->top1+1;//栈1元素个数
//MAXSIZE - stack->top2;//栈2元素个数
return S.top1 + 1 + MAXSIZE - S.top2;
}
int main() {
//int demo2() {
int n,e;
SqDoubleStack S;
cout << "创建顺序栈(分享空间)成功！\n";
if (InitSeqDoubleStack(S)) {
cout << "初始化顺序栈(分享空间)成功！\n";
}
//压栈
Push(S, 1, 1);
Push(S, 2, 1);
Push(S, 3, 1);
Push(S, 4, 1);
Push(S, 5, 1);
Push(S, 9, 2);
Push(S, 8, 2);
Push(S, 7, 2);
Push(S, 6, 2);
puts("展示元素:");
ShowStack(S);
printf("元素个数：%d\n", GetLengthSeqDoubleStack(S));
SElemType e1;
SElemType e2;
//弹栈
cout<<"弹栈\n";
cout<<"--------------------------------\n";
for (int i = 0; i < n; ++i) {
Pop(S,i,e);
cout<<"栈顶数据为"<<e<<endl;
}
ShowStack(S);
//清空
ClearSeqDoubleStack(S);
cout << endl;
return 0;
}
文档信息
- 本文作者：slience_me
- 本文链接：https://slienceme.xyz/2022/06/27/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0/
- 版权声明：自由转载-非商用-非衍生-保持署名（创意共享3.0许可证）