C语言|数据结构代码实现

2022/06/27 C语言 数据结构 共 18889 字,约 54 分钟

数据结构

一、线性表

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;
}

文档信息

Search

    Table of Contents