[数据结构与算法] 王道书代码实现(详细个人解析) C++版

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 王道书代码实现(详细个人解析) C++版 -> 正文阅读

[数据结构与算法]王道书代码实现(详细个人解析) C++版

第二章顺序表

顺序表基础操作

#define MaxSize 50
typedef struct{
    int data[MaxSize];
    int length;
}SqList;

void InitList(SqList &L){//初始化
    for(int i=0;i<MaxSize;i++){
        L.data[i]=0;
    }
    L.length=0;//初始表长0
}

1 从顺序表中删除具有最小值的元素（假设唯一），并由函数返回被删除的元素，空出的位置由最后一个元素填补，若线性表为空，返回错误信息！

bool Delete_Min(SqList &L,int &value){
    if(L.length==0){
        return false;
    }
    value=L.data[0];
    int min_pos=0;
    for(int i=1;i<L.length;i++){
        if(L.data[i]<value){//找最小值及其位置
            value=L.data[i];
            min_pos=i;
        }
    }
    L.data[min_pos]=L.data[L.length-1];
    L.length--;
    return true;
}

2 将顺序表逆置，要求空间复杂度为O(1)

void Reverse(SqList &L){
    int temp;
    for(int i=0;i<L.length/2;i++){
        temp=L.data[i];
        L.data[i]=L.data[L.length-i-1];
        L.data[L.length-i-1]=temp;
    }
}

3 删除顺序表中等于x的元素，要求时间复杂度O(n)，空间复杂度O(1)

void Delete_x(SqList &L,int x){
    int i,k;
    i=0,k=0;//k记录表中等于x的元素个数
    while(i<L.length){
        if(L.data[i]==x){
            k++;//累计等于x的个数
        }
        else{
            L.data[i-k]=L.data[i];//不等于x,当前记录前移k个位置
        }
        i++;
    }
    L.length=L.length-k;
}

4 删除有序顺序表中s到t中间的元素，要求s<t，显示错误信息（s和t也被删除了）

bool Delete_s_t(SqList &L,int s,int t){
    int i,j;
    if(s>=t||L.length==0){
        return false;
    }
    for(i=0;i<L.length&&L.data[i]<s;i++);//找到大于s的第一个元素
    if(i>L.length){//没找到
        return false;
    }
    for(j=i;j<L.length&&L.data[j]<=t;j++);//找到大于t的第一个元素
    for(;j<L.length;i++,j++){//将大于t的后面所有元素前移到以大于s的一个元素开始
        L.data[i]=L.data[j];
    }
    L.length=i;//此时表长就是i
    return true;
}

5 删除顺序表s到t中间的元素，要s<t，显示错误信息（s和t也被删除了）

bool Delete_s_t2(SqList &L,int s,int t){
    if(L.length==0||s>=t){
        return false;
    }
    int i,k=0;
    for(i=0;i<L.length;i++){
        if(L.data[i]>=s&&L.data[i]<=t){
            k++;//在s和t之间的元素累计个数
        }
        else{
            L.data[i-k]=L.data[i];
        }
    }
    L.length=L.length-k;
    return true;
}

6 删除有序顺序表中其值重复的元素，使得表中所有元素值不同

//注意是有序表
bool Delete_same(SqList &L){
    if(L.length==0){
            return false;
    }
    int i,j;//i指向前面未重复元素的最后一个，j工作指针
    for(i=0,j=1;j<L.length;j++){
        if(L.data[i]!=L.data[j]){
            i++;//与最后一个不相同，后移一个位置，存放后面的元素
            L.data[i]=L.data[j];
        }
    }
    L.length=i+1;
    return true;
}

如果是无序表

关键之处在于利用散列表的冲突来判断元素是否存在重复。于是解决散列表冲突的方式只能用拉链法，不能用开放地址法。散列表有数组和多个链表组成。数组里存储的是对应单个链表的首地址，链表中数据域用存储同义词。通过散列函数找到对应位置，继而判断是否存在相同元素。

！7 将两个有序顺序表合并成一个新的有序顺序表

bool Merge(SqList A,SqList B,SqList &M){
    if(A.length+B.length>MaxSize){
        return false;
    }
    int i=0,j=0,k=0;
    while(i<A.length&&j<B.length){
        if(A.data[i]<=B.data[j]){
            M.data[k++]=A.data[i++];
        }
        else{
            M.data[k++]=B.data[j++];
        }
    }
    while(i<A.length){
        M.data[k++]=A.data[i++];
    }
    while(j<B.length){
        M.data[k++]=B.data[j++];
    }
    M.length=k;
    return true;
}

8 将一个顺序表中的前m个元素和后n个元素进行整体互换，也就是将后面n个元素放在m个元素前面（思想：先整体逆置，然后将前n个元素再逆置，后m个元素再逆置）

//将顺序表，从left到right的元素逆置
void Reverse(SqList &L,int left,int right){//left表示顺序表的元素下标，并不是位序，要注意变通
    if(left>=right||right>MaxSize){
        return;
    }
    int mid=(left+right)/2;
    for(int i=0;i<=mid-left;i++){//left不一定是从0开始，mid-left表示逆置顺序表的一半元素个数
        int temp=L.data[i+left];
        L.data[i+left]=L.data[right-i];
        L.data[right-i]=temp;
    }
}

void Change(SqList &L,int m,int n){
    Reverse(L,0,m+n-1);//整体逆置
    Reverse(L,0,n-1);//后n个元素再逆置
    Reverse(L,n,m+n-1);//前m元素再逆置
}

13 给定一个含有n个整数的数组，设计时间上尽可能高效的算法，找出数组中没有出现的最小正整数

空间换时间，采用标记数组B[n]记录A中是否出现了1~n中的正整数，B[0]对应1，B[n-1]对应n; n个整数，返回的值可能是1-n+1,小于0和大于n的值可以不采取任何操作

//n个元素中找出没有出现的最小正整数
int findMissMin(int A[],int n){
    int B[n+1]={0};//n+1个元素空间是因为最小正整数可能出现的范围，B[]存放的就是1-n+1正整数是否出现
                    //没有出现的最小正整数的范围是1-n+1,负数和大于n的我们不用考虑，初始化为0
    int i;
    for(i=0;i<n;i++){
        if(A[i]>0&&A[i]<=n){
            B[A[i]-1]=1;//负数和大于n的数我们不用考虑，B[0]存放1是否出现，以此类推
        }
    }
    for(i=0;i<n;i++){//寻找第一个没有出现的最小正整数
        if(B[i]==0)
            break;
    }
    return i+1;
}

第二章链表

链表基础操作

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

//头插法建立单链表
LinkList ListHeadInsert(LinkList &L){
    int x;
    LNode *s;
    L=(LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    cout<<"输入一个整数：";
    cin>>x;
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode));
        s->data=x;
        s->next=L->next;
        L->next=s;
        cout<<"输入一个整数：";
        cin>>x;
    }
    return L;
}

//输出链表
void printLinkList(LinkList L){
    LNode *p;
    p=L->next;
    while(p!=NULL)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

1 设计递归方法，实现不带头结点的单链表中所有值为x的元素

void delete_x(LinkList &L,int x){
    LNode *p;
    if(L==NULL){
        return;
    }
    if(L->data==x){
        p=L;//p记录要删除的结点
        L=L->next;
        free(p);
        delete_x(L,x);//递归执行L为首的链表
    }
    else{
        delete_x(L->next,x);//指针下移继续判断
    }
}

2 在带头结点的单链表中，删除所有值为x的结点

void delete_x1(LinkList &L,int x){
    LNode *pre=L,*p=L->next,*q;//pre为p的前驱结点，q记录待删除结点
    while(p!=NULL){
        if(p->data==x){//其他删除的条件可以灵活更改if条件
            q=p;
            p=p->next;
            pre->next=p;
            free(q);
        }
        else{
            pre=p;
            p=p->next;
        }
    }
}

//尾插法实现
void delete_x2(LinkList &L,int x){
    LNode *p=L->next,*r=L,*q;//r指向尾结点，初始指向头，q记录待删结点
    while(p!=NULL){
        if(p->data!=x){//尾插到L后面
            r->next=p;
            r=p;
            p=p->next;
        }
        else{
            q=p;
            p=p->next;
            free(q);
        }
    }
}

3 递归实现链表逆置输出

//递归实现逆置输出
void Reverse_Print(LinkList L){
    if(L->next!=NULL){
        Reverse_Print(L->next);
    }
    if(L!=NULL){
        cout<<L->data<<" ";
    }
}

void R_print1(LinkList L){
    if(L!=NULL){
        Reverse_Print(L->next);
    }
}

4 从一个带头结点的单链表中删除元素值最小的结点（假设最小值结点唯一）

void delete_min(LinkList &L){
    LNode *pre=L,*p=L->next;//p,pre工作指针，pre是p的前驱
    LNode *minpre=pre,*minp=p;//minp,minpre记录当前最小值结点
    while(p!=NULL){
        if(p->data < minp->data){
            minp=p;
            minpre=pre;
        }
        pre=p;
        p=p->next;
    }
    minpre->next=minp->next;
    free(minp);
}

5 编写算法将带有头结点的链表就地逆置，（就地：空间复杂度O(1)）

注意下面两种方法的函数类型，一个是直接对原链表操作，一个是对复制品操作然后返回一个新链表

//头插法
void Reverse1(LinkList &L){
    LNode *r,*p;//p工作指针，r防止断链
    p=L->next;
    L->next=NULL;//头结点断链
    while(p!=NULL){
        r=p->next;
        p->next=L->next;
        L->next=p;
        p=r;
    }
}

//直接将各结点之间的指针反转
LinkList Reverse2(LinkList L){
    LNode *pre,*p=L->next,*r=p->next;//pre为p的前驱，p工作指针，r防止断链
    p->next=NULL;//第一个结点实际上是反转之后作为尾结点，next指向NULL
    while(r!=NULL){//三个指针实现反转
        pre=p;
        p=r;
        r=r->next;
        p->next=pre;//指针反转
    }
    L->next=p;//L头结点加到最后;
    return L;
}

6 有一个带头结点的单链表，设计算法使其递增有序

//直接插入排序思想实现链表升序排序
void list_Sort(LinkList &L){
    LNode *pre,*p=L->next,*r=p->next;
    p->next=NULL;//开始只含一个结点
    p=r;
    while(p!=NULL){
        r=r->next;
        pre=L;//每次排序pre都从头结点开始比较
        while(pre->next!=NULL && pre->next->data < p->data){//在有序表中找到*p插入的前驱，注意pre->next的运用（有插入操作，要记住前驱结点）
            pre=pre->next;
        }
        p->next=pre->next;//插入操作
        pre->next=p;
        p=r;
    }
}

7 在一个带头结点的单链表中元素无序，要求删除介于给定两个值中间的所有结点（和1对比）

void delete_s_t(LinkList &L,int s,int t){
    LNode *pre=L,*p=L->next,*q;
    while(p!=NULL){
        if(p->data>s && p->data<t){
            pre->next=p->next;
            q=p;
            p=p->next;
            free(q);
        }else{
            pre=p;
            p=p->next;
        }
    }
}

8 给定两个单链表，编写算法找出两个结点的公共结点

思想： 理解公共结点，若两个链表有公共结点，则公共结点之后的所有结点都重合，从尾结点向前都相同；由于两个链表长度不一样（假设两个链表长度之差k），我们先在长链表遍历k个结点（保证后面能同时到达尾结点，前面k个结点肯定没有公共结点），然后对两个链表共同遍历，第一个相同的结点就是公共结点

//链表长度
int list_Length(LinkList L){
    int i=0;
    LNode *p=L->next;
    while(p!=NULL){
        i++;
        p=p->next;
    }
    return i;
}

//寻找公共结点
LNode* search_Common(LinkList A,LinkList B){
    int len1=list_Length(A);
    int len2=list_Length(B);
    LNode *longList,*shortList;
    int dist;
    if(len1>len2){
        longList=A->next;
        shortList=B->next;
        dist=len1-len2;
    }else{
        longList=B->next;
        shortList=A->next;
        dist=len2-len1;
    }
    while(dist--){
        longList=longList->next;
    }
    while(longList!=NULL){
        if(longList==shortList){
            return longList;
        }
        longList=longList->next;
        shortList=shortList->next;
    }
    return NULL;
}

int main(){
    LinkList A;
    ListHeadInsert(A);
    printLinkList(A);
    LNode *p=A->next;
    int dist=4;
    while(dist--){
        p=p->next;
    }
    cout<<"p->data="<<p->data<<endl;

    LinkList B;
    B=(LinkList)malloc(sizeof(LNode *));//B头结点初始化
    B->next=NULL;

    B->next=p;//创造公共结点
    cout<<"B->next->data="<<B->next->data<<endl;
    printLinkList(B);
    LNode *common = search_Common(A,B);
    cout<<"共同结点："<<common->data<<endl;
    return 0;
}

9 给定一个带表头结点的单链表，设L为头指针，要求按递增次序输出单链表中各结点中的数据，并释放结点所占的存储空间（不允许使用数组作为辅助空间）

void min_delete(LinkList &L){
    LNode *pre,*p;//p工作指针，pre为最小值结点的前驱
    LNode *u;
    while(L->next!=NULL){//每次都会删除一个结点，只需判头结点L后面是否有结点,最后只剩头结点
        pre=L;
        p=L->next;
        while(p->next!=NULL){//一次遍历找到最小值结点
            if(pre->next->data > p->next->data){
                pre=p;//记录当前最小值结点的前驱
            }
            p=p->next;
        }
        cout<<pre->next->data<<endl;
        u=pre->next;//记录最小值结点
        pre->next=u->next;//释放最小值之前要把最小值从链表中单独出来，直接删除会造成后面数据丢失
        free(u);
    }
    free(L);//最后释放头结点
}

10 将一个带头结点的单链表A分解为两个带头结点的单链表A和B，使得A中含有原表中位序为奇数的元素，B中含有原表中位序为偶数的元素结点，且保持相对位置不变（尾插法）

//保证原来顺序，采用尾插法(A直接修改，B创建并返回)
LinkList divide_List(LinkList &A){
    LNode *B;
    B=(LinkList)malloc(sizeof(LNode *));
    B->next=NULL;
    int i=0;//遍历序号
    LNode *rb=B,*ra=A;//ra,rb指向A,B链表的尾指针
    LNode *p=A->next;//工作指针
    A->next=NULL;//断开表头，创建新的链表
    while(p!=NULL){
        i++;
        if(i%2!=0){//奇数，尾插法
            ra->next=p;
            ra=p;
        }
        else{
            rb->next=p;
            rb=p;
        }
        p=p->next;
    }
    ra->next=NULL;
    rb->next=NULL;
    return B;
}

11 设C={a1,b2,a2,b2,···,an,bn} ，采用带头结点的方式，将其拆分为A{a1,a2,···,an},B{bn,···,b2,b1}

**思想：**和10题类似，A表后插保证和原表顺序一致，B表前插实现逆序

//A后插，B前插
LinkList divide_List2(LinkList &A){
    LNode *B;
    B=(LinkList)malloc(sizeof(LNode *));
    B->next=NULL;
    LNode *p=A->next,*q;//p工作指针，q为B前插操作时防止断链
    LNode *ra=A;//A的尾指针
    A->next=NULL;
    while(p!=NULL){
        ra->next=p;//A表后插
        ra=p;
        p=p->next;

        if(p!=NULL){//p后移，需要重新判断一下，B表前插
            q=p->next;//防止断链
            p->next=B->next;
            B->next=p;
            p=q;
        }
    }
    ra->next=NULL;
    return B;
}

12 在一个有序单链表中，有数值相同的元素，设计算法删除相同的元素，使表中不再含有相同的元素。L={2,5,5,5,9,9,15,18,18,36}–>L{2,5,9,15,18,36}

void delete_same(LinkList &L){
    LNode *p=L->next,*q;
    if(p==NULL){//空链表直接返回
        return;
    }
    while(p->next!=NULL){
        q=p->next;
        if(p->data==q->data){
            p->next=q->next;
            free(q);//删除后面相同的元素
        }
        else{
            p=q;
        }
    }
}

13 有两个按递增次序排列的单链表，设计算法使得将这两个链表合并成按元素递减次序排列的单链表，要求利用原来的链表结点存放合并后的单链表

void merge_Des(LinkList &A,LinkList &B){
    LNode *r;//暂存后继指针，防止断链
    LNode *pa=A->next,*pb=B->next;
    A->next=NULL;//A表头作为合并后的新链表
    while(pa&&pb){
        if(pa->data < pb->data){
            r=pa->next;//防止断链
            pa->next=A->next;//头插法
            A->next=pa;
            pa=r;
        }
        else{
            r=pb->next;
            pb->next=A->next;
            A->next=pb;
            pb=r;
        }
    }
    if(pa){
        pb=pa;//pa和pb只会有一个不空，或者都为空，在这里统一起来，只需执行一段代码
    }
    while(pb){
        r=pb->next;
        pb->next=A->next;
        A->next=pb;
        pb=r;
    }
    free(B);
}

14 设A和B是两个带头结点的单链表，其中元素递增有序，设计一个算法从A和B中公共元素中产生新链表C

*思想：寻找两个链表公共结点，参照8题；（公共结点和公共元素不同）***此题寻找公共元素，这个题两个链表都是递增有序的，所以可以从表头依次比较，元素值不相等，小的元素指针后移再比较；元素值相等，创建一个新的结点，后插法保持有序

A={4,9,9,15,26,34,58,59,66},B={15,26,59,66,69,72},C={15,26,59,66}

//寻找公共元素构成新链表
LinkList get_Common(LinkList &A,LinkList &B){
    LinkList C=(LinkList)malloc(sizeof(LNode *));
    C->next=NULL;
    LNode *rc=C;//C链表的尾指针
    LNode *pa=A->next,*pb=B->next;
    while(pa&&pb){
        if(pa->data < pb->data){//pa小，后移一位；pb不动
            pa=pa->next;
        }
        else if(pa->data > pb->data){
            pb=pb->next;
        }
        else{//相等
            LNode *s=(LNode *)malloc(sizeof(LNode *));
            s->data=pa->data;
            rc->next=s;//后插法
            rc=s;

            pa=pa->next;
            pb=pb->next;
        }
    }
    rc->next=NULL;
    return C;
}

15 已知两个链表A和B分别表示两个集合，其元素递增有序，设计一个算法求A，B的交集，并存放在A中。(和上题类似，记得动手实现)

16 两个整数序列，A={a1,a2,···,an}，B={b1,b2,···,bn}，判断B是否是A的连续子序列

**思想：**其实是字符串模式匹配的链式表示，试着优化

//模式匹配
int pattern(LinkList A,LinkList B){
    LNode *pa=A->next;
    LNode *pb=B->next;
    LNode *pre=A->next;//pre记录A开始匹配的结点
    if(pa==NULL || pb==NULL){
        return 0;
    }
    while(pa&&pb){
        if(pa->data == pb->data){
            pa=pa->next;
            pb=pb->next;
        }
        else{
            pre=pre->next;
            pa=pre;
            pb=B->next;
        }
    }
    if(pb==NULL){//B链表先比较结束，匹配成功
        return 1;
    }
    else{
        return 0;
    }
}

循环双链表的基本操作

typedef struct DNode{
    int data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

//建立循环双链表
void buildDLink(DLinkList &L){
    L=(DLinkList)malloc(sizeof(DNode *));
    L->next=L;
    L->prior=L;
    DNode *s;
    int x;
    cout<<"输入一个整数：";
    cin>>x;
    while(x!=9999){
        s=(DNode *)malloc(sizeof(DNode *));
        s->data=x;
        s->next=L->next;
        L->next->prior=s;
        L->next=s;
        s->prior=L;
        cout<<"输入一个整数：";
        cin>>x;
    }
}

void printDLink(DLinkList L){
    DNode *p;
    p=L->next;
    while(p!=L){
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

17 判断带头结点循环双链表是否对称

**思想：**p从左到右，r从右到左，直到它们指向同一个结点（奇数个结点）或相邻结点（偶数个结点）为止。注意偶数结点的判断条件

//判断循环双链表是否对称
int judge_Symmetry(DLinkList L){
    DNode *p=L->next,*r=L->prior;//p从头开始，r从尾结点开始
    while(p!=r && r->next!=p){//p==r时，奇数个结点退出，r->next==p时，偶数个结点退出
        if(p->data==r->data){
            p=p->next;
            r=r->prior;
        }
        else{
            return 0;
        }
    }
    return 1;
}

循环单链表的基本操作

//头插法建立循环单链表
void ListHeadInsert0(LinkList &L){
    LNode *s;
    int x;
    L=(LinkList)malloc(sizeof(LNode *));
    L->next=L;//循环指针
    cout<<"输入一个整数：";
    cin>>x;
    while(x!=9999){
        s=(LNode *)malloc(sizeof(LNode *));
        s->data=x;
        s->next=L->next;
        L->next=s;
        cout<<"输入一个整数：";
        cin>>x;
    }
}

//输出循环单链表
void printLinkList0(LinkList L){
    LNode *p;
    p=L->next;
    while(p!=L)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

18 有两个循环单链表，链表头指针分别为A,B，编写函数将B连接到A之后，要求链接之后的链表仍保持循环链表形式

LinkList Link(LinkList &A,LinkList B){
    LNode *p=A->next,*q=B->next;//p,q寻找A,B链表的尾结点
    while(p->next!=A){
        p=p->next;
    }
    while(q->next!=B){
        q=q->next;
    }
    p->next=B->next;//B的头结点排除
    B->next=NULL;
    q->next=A;
    return A;
}

19 设有一个带头结点的循环单链表，结点均为正整数，设计一个算法，反复找出表中最小值结点并输出，然后将该结点删除，直到单链表空为止，最后释放头结点

void printDelete_Min(LinkList &L){
    LNode *pre,*p;
    LNode *minpre,*minp;
    while(L->next!=L){//未空
        pre=L;//四个指针变量每次循环都要重新赋值
        p=L->next;
        minpre=pre;
        minp=p;
        while(p!=L){//注意这个条件，不是p->next!=NULL(没有比较判断最后一个结点),
            if(p->data < minp->data){
                minp=p;
                minpre=pre;
            }
            pre=p;
            p=p->next;
        }
        cout<<minp->data<<" ";
        minpre->next=minp->next;//释放最小值结点
        free(minp);
    }
    free(L);
}

21 已知一个带头结点的单链表，在不改变链表结构的前提下，设计一个算法查找链表中倒数第k个位置上的元素；查找成功，输出结点的值，返回1；查找失败，返回0。

**思想：**两个指针变量p,q，初始时指向L->next，首先p指针移动到第k个元素时，q指针开始和p指针同步移动，当p移动到最后一个结点时，q当前所指就是倒数第k个结点。

//查找倒数第k个结点
int search_K(LinkList L,int k){
    LNode *p=L->next,*q=L->next;//p先
    int count=0;//不用单独遍历求表长，count记录p当前遍历的结点个数,用来判断k的合法性
    while(p!=NULL){
        if(count<k){
            count++;
        }
        else{//p遍历k个结点后
            q=q->next;
        }
        p=p->next;
    }
    if(count<k){//遍历整个链表之后，count等于链表L的长度，此时count<k表示k超出了限度
        cout<<"k越界"<<endl;
        return 0;
    }
    cout<<"倒数第"<<k<<"个位置的元素值："<<q->data<<endl;
    return 1;
}

22 寻找链表公共结点

23 用单链表保存m个整数，结点值|data|<=n(n为正整数)。要求设计一个时间复杂度尽可能高效的算法，对于链表中data的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点，例如L={21,-15,-15,-1,15}，经过算法之后，L={21,-15,-7}

void delete_Abs_Same(LinkList &L,int n){//n为链表中最大的绝对值
    LNode *p=L,*r;//p为工作指针，r记录待删结点
    int tag[n+2]={0};//申请n+1个标记，分别与m个结点值对应，值可能出现【0-n】
    int m;//存放结点的绝对值
    while(p->next!=NULL){//采用p->next可以保存待删结点的前驱(理解)
        m=abs(p->next->data);
        if(tag[m]==0){//检查对应位置的标记，第一个出现
            tag[m]=1;
            p=p->next;
        }
        else{//不是第一个出现，就删除
            r=p->next;
            p->next=r->next;
            free(r);
        }
    }
}

24 设计算法判断一个链表是否有环，如果有，返回环的入口结点

2(a+x)=a+n*r+x，即 a=n*r-x

LNode * FindLoopStart(LinkList L){
    LNode *fast=L->next,*slow=L->next;//快慢结点
    while(slow!=NULL && fast->next!=NULL){//slow直接判断是否为NULL,fast一次移动两个位置，要判断fast->next是否存在
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast){//找到相遇的结点
            break;
        }
    }
    if(slow==NULL || fast->next==NULL){
        return NULL;
    }
    //重点在转换，详细见分析的公式
    LNode *head=L->next,*meet=slow;//head指向第一个结点，meet指向相遇的结点
    while(head!=meet){//相遇时即为环的入口结点
        head=head->next;
        meet=meet->next;
    }
    return head;//或者meet
}

int main(){
    LinkList L;
    ListHeadInsert(L);
    printLinkList(L);
    LNode *p=L->next;
    
    int dist=4;
    while(dist--){
        p=p->next;
    }
    cout<<"p->data="<<p->data<<endl;
    
    LNode *r=L;
    while(r->next!=NULL){
        r=r->next;
    }
    r->next=p;
    LNode *s = FindLoopStart(L);
    cout<<"环的入口"<<s->data<<endl;
    return 0;
}

25 设线性表L={a1,a2,a3,···,an-2,an-1,an}，采用带头结点的单链表保存，设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列各元素，使L={a1,an,a2,an-1,a3,an-2,···}

**思想：**不能借助辅助空间（栈），为了方便取后半段的元素，将后半段元素原地逆置（前插法），否则每次取元素都要遍历一次链表

void change_List(LinkList &L){
    LNode *p,*r,*s,*t;
    p=L,r=L;
    while(r->next!=NULL){//找到中间结点，p一次走一步，r一次走两步
        p=p->next;
        r=r->next;
        if(r->next!=NULL){
            r=r->next;
        }
    }//结束时，p所指就是中间结点
    r=p->next;//r记录后半段，防止断链，下面进行后半段原地逆置操作
    p->next=NULL;//从中间结点断开

    while(r!=NULL){//后半段前插法接到前半段后面，实现后半段原地逆置
        t=r->next;//防止断链
        r->next=p->next;
        p->next=r;
        r=t;
    }

    r=p->next;//r记录后半段
    p->next=NULL;//断开,p当前所指就是最终链表的最后一个元素

    s=L->next;
    while(r!=NULL){//优先判断后半段是否先结束，因为后半段元素可能少前半段一个，或者等于前半段
                    //后半段依次插入前半段
        t=r->next;//防止断链
        r->next=s->next;
        s->next=r;
        s=r->next;//s移动到下一个插入的位置前驱，原前半段操作元素后一个
        r=t;
    }
}

第三章栈和队列

栈和队列基础操作

#define MaxSize 50

typedef struct{
    int data[MaxSize];
    int top;
}SqStack;

typedef struct{
    int data[MaxSize];
    int front,rear;
}SqQueue;
//初始化
InitStack(SqStack &S){
    S.top=-1;
}
//初始化
InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;
}

bool StackEmpty(SqStack S){
    if(S.top==-1){
        return true;
    }else{
        return false;
    }
}

bool QueueEmpty(SqQueue Q){
    if(Q.front==Q.rear){
        return true;
    }else{
        return false;
    }
}

//入栈
bool push(SqStack &S,int x){
    if(S.top==MaxSize-1){
        cout<<"栈满";
        return false;
    }
    S.data[++S.top]=x;
    return true;
}

//出栈
bool pop(SqStack &S,int &x){
    if(S.top==-1){
        cout<<"栈空";
        return false;
    }
    x=S.data[S.top--];
    return true;
}

//读栈顶元素
bool GetTop(SqStack S,int &x){
    if(S.top==-1){
        cout<<"栈空";
        return false;
    }
    x=S.data[S.top];
    return true;
}

//入队
bool EnQueue(SqQueue &Q,int x){
    if((Q.rear+1)%MaxSize==0){
        cout<<"队满"<<endl;
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    return true;
}

//出队
bool DeQueue(SqQueue &Q,int &x){
    if(Q.front==Q.rear){
        cout<<"队空"<<endl;
        return false;
    }
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    return true;
}

链式队列基本操作

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front,*rear;
}LinkQueue;

//初始化
void InitLinkQueue(LinkQueue &Q){//队头指针始终指向头结点，队尾指针指向最后一个元素
    Q.front=Q.rear=(LinkNode *)malloc(sizeof(LinkNode *));//头结点
    Q.rear->next=NULL;//初始为空
}

//判队空
bool LinkQueueEmpty(LinkQueue Q){
    if(Q.front==Q.rear){
        return true;
    }else{
        return false;
    }
}

//入队
void EnLinkQueue(LinkQueue &Q,int x){
    LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode *));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s;
    Q.rear=s;
}

//出队
bool DeLinkQueue(LinkQueue &Q,int &x){
    if(Q.rear==Q.front){
        return false;
    }
    LinkNode *q=Q.front->next;//队头元素为队头指针的下一个
    x=q->data;
    Q.front->next=q->next;//更新队头元素
    if(Q.rear==q){//如果只有一个元素
        Q.rear=Q.front;//调整队尾指针队空
    }
    free(q);
    return true;
}

第一节

4 设单链表头指针为L，data为字符型，设计算法判断该链表的全部n个元素是否对称

//判断链表是否对称，（利用栈）
int judge_Symmetry(LinkList L,int n){
    LNode *p;
    char s[n/2];//栈数组
    p=L->next;
    int i;
    for(i=0;i<n/2;i++){
        s[i]=p->data;
        p=p->next;
    }//此时p和i所处同一位置[n/2],
    i--;//i回退到前半段最后一个元素
    if(n%2==1){//奇数个结点
        p=p->next;//中间结点不用判断
    }
    while(p!=NULL && p->data==s[i]){
        i--;
        p=p->next;
    }
    if(i==-1){//i==-1,栈空，也说明p=NULL,
        return 1;
    }
    else{
        return 0;
    }
}

5 设计共享栈的出栈，入栈操作

typedef struct{
    int data[MaxSize];
    int top[2];
}SqStack;

//初始化
void InitStack(SqStack &S){
    S.top[0]=-1;
    S.top[1]=MaxSize;
}

//入栈
bool push(SqStack &S,int x,int i){//i是栈号
    if(i<0 || i>1){//栈号错误
        return false;
    }
    if(S.top[1]-S.top[0]==1){
        cout<<"栈满";
        return false;
    }
    switch(i){
        case 0:
            {
                S.data[++S.top[0]]=x;
                return true;
                break;
            }
        case 1:
            {
                S.data[--S.top[1]]=x;
                return true;
                break;
            }
    }
}

//退栈
int pop(SqStack &S,int i){
    if(i<0 || i>1){
        return -1;
    }
    switch(i){
        case 0:
            {
                if(S.top[0]==-1){
                    cout<<"栈空";
                    return -1;
                }
                else{
                    return S.data[S.top[0]--];
                }
                break;
            }
        case 1:
            {
                if(S.top[1]==MaxSize){
                    cout<<"栈空";
                    return -1;
                }
                else{
                    return S.data[S.top[1]++];
                }
                break;
            }
    }
}

第二节

1 希望循环队列都能得到利用，则需设置一个标志域tag，实现入队出队的算法

#define MaxSize 50
typedef struct{
    int data[MaxSize];
    int front,rear;
    int tag;
}SqQueue;

//初始化
void InitQueue(SqQueue &Q){
    Q.front=Q.rear=0;
    Q.tag=0;
}

//入队
bool EnQueue(SqQueue &Q,int x){
    if(Q.rear==Q.front && Q.tag==1){//栈满
        cout<<"栈满";
        return false;
    }
    Q.data[Q.rear]=x;
    Q.rear=(Q.rear+1)%MaxSize;
    Q.tag=1;
    return true;
}

//出队
bool DeQueue(SqQueue &Q,int &x){
    if(Q.rear==Q.front && Q.tag==0){//栈空
        cout<<"栈空";
        return false;
    }
    x=Q.data[Q.front];
    Q.front=(Q.front+1)%MaxSize;
    Q.tag=0;
    return true;
}

2 利用栈和队列实现对队列的逆置

//逆置队列中的元素
void Reverse_Queue(SqQueue &Q,SqStack &S){
    int x;
    while(!QueueEmpty(Q)){
        DeQueue(Q,x);
        push(S,x);
    }
    while(!StackEmpty(S)){
        pop(S,x);
        EnQueue(Q,x);
    }
}

3 利用两个栈模拟一个队列，已知栈有下面4个基础操作

**思想：**对S2的出栈操作用作出队，若S2为空，则先将S1中的所有元素送入S2；

对S1的入栈操作用作入队，若S1满，必须先保证S2为空，才能将S1中的元素全部插入S2中

//Push(S,x) 入栈
//Pop(S,x) 出栈
//StackEmpty(S) 判断栈空
//StackOverflow(S) 栈满

//入队
int QnQueue2(Stack &S1,Stack &S2,int e){
    if(!StackOverflow(S1)){
        Push(S1,e);
        return 1;
    }
    if(StackOverflow(S1) && StackEmpty(S2)){
        cout<<"队列满"<<endl;
        return 0;
    }
    if(StackOverflow(S1) && StackEmpty(S2)){
        while(!StackEmpty(S1)){
            Pop(S1,x);
            Push(S2,x);
        }
    }
    Push(S1,e);
    return 1;
}

//出队
void DeQueue2(Stack &S1,Stack &S2,int &x){
    if(!StackEmpty(S2)){
        Pop(S2,x);
    }
    else if(StackEmpty(S1)){
        cout<<"队列空"<<endl;
    }
    else{
        while(!StackEmpty(S1)){
            Pop(S1,x);
            Push(S2,x);
        }
    Pop(S2,x);
    }
}

//判断队列空
int QueueEmpty2(Stack S1,Stack S2){
    if(StackEmpty(S1)&&StackEmpty(S2)){
        return 1;
    }
    else{
        return 0;
    }
}

第三节

1 写一个算法实现括号匹配

//判断括号是否匹配
bool BracketCheck(char *str){
    SqStack S;
    InitStack(S);
    int i=0;
    int e;
    while(str[i]!='\0'){
        switch(str[i]){
            //左括号入栈
            case '{':
                Push(S,'{');
                break;
            case '[':
                Push(S,'[');
                break;
            case '(':
                Push(S,'(');
                break;
            case '}':
                Pop(S,e);
                if(e!='{'){
                    printf("匹配失败！");
                    return false;
                }
                break;
            case ']':
                Pop(S,e);
                if(e!='['){
                    printf("匹配失败！");
                    return false;
                }
                break;
            case ')':
                Pop(S,e);
                if(e!='('){
                    printf("匹配失败！");
                    return false;
                }
                break;
            default:
                break;
        }//switch
        i++;
    }//while
    if(!StackEmpty(S)){
        printf("匹配失败！");
        return false;
    }
    else{
        printf("匹配成功！");
        return true;
    }
}

bool bracketCheck(char str[],int length){
    SqStack S;
    InitStack(S);
    for(int i=0;i<length;i++){
        if(str[i]=='(' || str[i]=='[' || str[i]=='{'){
            Push(S,str[i]);//扫描左括号，入栈
        }else{
            if(StackEmpty(S)){
                return false;
            }
            char topElem;
            Pop(S,topElem);//栈顶元素出栈
            if(str[i]==')' && topElem!='(')
                return false;
            if(str[i]==']' && topElem!='[')
                return false;
            if(str[i]=='}' && topElem!='{')
                return false;
        }
    }
    return StackEmpty(S);
}

3 利用栈实现如下递归调用

struct newstack{
    int no;//保存当前栈的n
    double value;//保存Pn(x)的值
};

double P(int n,double x){
    newstack st[MaxSize];
    int top=-1;//栈指针
    int i;
    double fv1=1,fv2=2*x;
    for(i=n;i>=2;i--){//模拟递归调用函数栈
        top++;
        st[top].no=i;//n减小，最大的n在栈底
    }
    while(top>=0){
        st[top].value=2*x*fv2-2*(st[top].no-1)*fv1;//从栈顶开始计算，保存计算值
        fv1=fv2;
        fv2=st[top].value;//更新当前栈顶计算值
        top--;//出栈
    }
    if(n==0){
        return fv1;
    }
    return fv2;
}

4 某汽车轮渡口，过江渡船每次能载10辆车过江，过江车辆有客车和货车：同类车辆先到先上船；客车先与货车上船，且每上4辆客车，才能上一辆货车；若等待客车不足4辆，则以货车代替；若无货车等待，允许客车都上船。

void Manager(SqQueue &q1,SqQueue &q2,SqQueue &Q){//q1代表客车，q2代表货车,船的载渡队列
    int i=0,j=0;//j是载渡队列长度，i记录每波客车上船记录数
    while(j<10){
        int x;
        if(i<4 && !QueueEmpty(q1)){//客车队列条件满足，未上足4辆
            DeQueue(q1,x);
            EnQueue(Q,x);//客车加入载渡队列
            i++;
            j++;
        }
        else if(i==4 && !QueueEmpty(q2)){//货车队列条件满足，客车上足4辆
            DeQueue(q2,x);
            EnQueue(Q,x);//货车加入载渡队列
            j++;
            i=0;//
        }
        else{
            while(j<10 && i<4 && !QueueEmpty(q2)){//载渡队列未满，客车未上够4辆，客车队列未空
                DeQueue(q2,x);
                EnQueue(Q,x);//剩余货车加入载渡队列
                j++;
                i++;//i=4时退出，货车只是代替未满的的4辆客车
            }
            i=0;//若货车为空，则客车都上船
        }
        if(QueueEmpty(q1) && QueueEmpty(q2)){//客车和货车总共不足10辆
            j=11;//退出外层循环
        }
    }
}

第四章串

顺序存储

#define MAXLEN 255
typedef struct{
    char ch[MAXLEN];
    int length;
}SString

这种方式直接分配一个固定长度的存储区，销毁时系统会自动回收

堆分配存储（动态分配）

仍然是一组地址连续的存储单元存放串值，但是存储空间是动态分配得到的
```
typedef struct{
    char *ch;//按串长分配存储区，ch指向串的基地址
    int length;
}HString
    
//动态分配
S.ch=(char *)malloc(MAXLEN*sizeof(char));
```
在堆中的存储，用malloc()申请的空间，需要手动free()释放
块链存储

用链表方式存储字符串值

一个结点存放一个字符时存储密度低，可以存放多个字符

StrAssign(&T,chars)：赋值操作，把串T赋值为`chars``
``StrCompare(S,T)：S>T，则返回值>0；S=T,则返回值=0；若S<T，则返回值<0`
StrLength(S)：求串长
SubString(&Sub,S,pos,len)：求子串，用Sub返回串S的第pos个字符起长度为len的子串
Index(S,T)：定位操作，返回子串T在主串S中首次出现的位置
ClearString(&S)：S串清空
DestroyString(&S)：销毁，归还空间

//利用串的基础操作,字符串匹配，T在S中第一次出现的位置
int Index(SString S,SString T){
    int i=1;
    int n=StrLength(S);
    int m=StrLength(T);
    SString sub;
    while(i<=n-m+1){
        SubString(sub,S,i,m);//返回S中从i开始的m长度的串
        if(StrCompare(T,sub)!=0){//sub与T不匹配
            i++;
        }
        else{
            return i;//返回子串T在S中出现的位置
        }
    }
    return 0;//匹配失败
}

//暴力模式匹配
int Index2(SString S,SString T){
    int k=1;//k记录S每次匹配从哪个字符开始
    int i=k,j=1;
    while(i<=S.length && j<=T.length){
        if(S.ch[i-1]==T.ch[j-1]){
            i++;
            j++;
        }
        else{
            k++;
            i=k;
            j=1;
        }
    }
    if(j>T.length){//说明匹配完成
        return k;
    }
    else{
        return 0;
    }
}

第五章树和二叉树

5 已知一颗二叉树按顺序存储结构进行存储，求编号分别为 i 和 j 的两个结点的最近的公共祖先结点

**思想：**二叉树中两个任意结点必然存在最近的祖先结点，顺序存储结构中，任一结点 i 的双亲结点的编号为 i/2，一直往上层寻找，直到 i/2 等于 j/2 或者 j

char Comm_Ancestor(char T[],int i,int j){
    if(T[i]!='#' && T[j]!='#'){
        while(i!=j){
            if(i>j){//说明i在j的下一个层次
                i=i/2;
            }
            else{
                j=j/2;
            }
        }
        return T[i];
    }
}

递归遍历实现

typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//构造二叉树
BiTree createBiTree(){
    BiTNode *r;
    char s;//结点
    cin>>s;
    if(s=='#'){
        r=NULL;
    }
    else{
        r=(BiTNode *)malloc(sizeof(BiTNode *));
        r->data=s;
        cout<<"输入 "<<s<<" 的左孩子结点('#'表示为空):";
        r->lchild=createBiTree();//递归输入当前根结点的左子树
        cout<<"输入 "<<s<<" 的右孩子结点('#'表示为空):";
        r->rchild=createBiTree();//递归右子树
    }
    return r;
}

void visit(BiTNode *T){
    if(T!=NULL){
        cout<<T->data<<endl;
    }
}

//先序
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

//中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

//后序
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}

非递归实现遍历

**中序思想：**沿着根的左结点，结点依次入栈，直到左孩子为空，说明已经找到可以输出的结点；栈顶元素出栈并访问，如果其右孩子为空，继续执行出栈访问操作；若右结点不为空，将转向右结点

void InOrder2(BiTree T){
    SqStack S;
    InitStack(S);
    BiTNode *p=T;
    while(!StackEmpty(S) || p){
        if(p){
            Push(S,p);
            p=p->lchild;
        }
        else{
            Pop(S,p);
            visit(p);
            p=p->rchild;
        }
    }
}

**先序思想：**和中序类似，只是访问的时机在入栈之前

void PreOrder2(BiTree T){
    SqStack S;
    InitStack(S);
    BiTNode *p=T;
    while(!StackEmpty(S) || p){
        if(p){
            visit(p);
            Push(S,p);
            p=p->lchild;
        }
        else{
            Pop(S,p);
            p=p->rchild;
        }
    }
}

层次遍历

**思想：**将根结点入队，出队并访问，如果其存在左孩子，则将其入队，若存在右孩子，同样入队；然后队列不空时进行出队访问，左右孩子入队出队。

void leverOrder(BiTree T){
    BQueue Q;
    InitBQueue(Q);
    BiTree p;
    EnBQueue(Q,T);
    while(!emptyBQueue(Q)){
        DeBQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL){
            EnBQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL){
            EnBQueue(Q,p->rchild);
        }
    }
}

中序线索化

typedef struct ThreadNode{
    char data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,*ThreadTree;

//线索化以p为根结点的二叉树
void InThread(ThreadNode *p,ThreadNode *pre){
    if(p!=NULL){//和中序遍历联系起来
        InThread(p->lchild,pre);//线索化左子树

        //visit()
        if(p->lchild==NULL){//左子树为空，左孩子指向中序前驱
            p->lchild=pre;
            p->ltag=1;
        }
        if(pre!=NULL && pre->rchild==NULL){//初始pre为NULL，中序前驱的右子树为空，右孩子指向中序后继
            pre->rchild=p;
            pre->rtag=1;
        }
        pre=p;//前驱指针后移

        InThread(p->rchild,pre);
    }
}

//创建中序线索树
void CreateInThread(ThreadTree T){
    ThreadNode *pre=NULL;//全局变量，pre作用于每个结点，pre还要对最后一个结点进行处理(如果不是全局变量，最后的pre会丢失)
    if(T!=NULL){
        InThread(T,pre);//结束时，pre与p指向中序最后一个结点
        pre->lchild=NULL;
        pre->rtag=1;
    }
}

//找到中序遍历第一个结点
ThreadNode *firstNode(ThreadNode *p){
    while(p->ltag==0){//线索化之后，p->ltag==0说明p有左孩子，或者直接采用原始方法(p->lchild!=NULL)
        p=p->lchild;
    }
    return p;
}

//找到中序遍历p结点的下一个结点
ThreadNode *nextNode(ThreadNode *p){
    if(p->rtag==0){//线索化之后，p->rtag==0说明p有右孩子，找到以p右子树中第一个访问的结点
        return firstNode(p->rchild);
    }
    else{//说明右孩子直接指向其中序后继
        return p->rchild;
    }
}

//线索二叉树中序遍历
void InOrder3(ThreadTree T){
    for(ThreadNode *p=firstNode(T) ; p!=NULL ; p=nextNode(p)){
        visit(p);
    }
}

中序线索化另外的方式

typedef struct ThreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int ltag,rtag;
}ThreadNode,* ThreadTree;

//全局变量pre
ThreadNode *pre=NULL;

//中序线索化
CreateInOrder(ThreadTree T){
    pre=NULL;
    if(T!=NULL){
        //中序遍历
        InThread(T);
        if(pre->rchild==NULL){//此时pre是中序最后一个结点
            pre->rtag=1;//右孩子指针线索化
        }
    }
}

//中序遍历,一边遍历一边线索化
InThread(ThreadTree T){
    if(T!=NULL){
        InThread(T->lchild);
        Visit(T);
        InThread(T->rchild);
    }
}

//线索化的过程
Visit(ThreadNode *q){
    if(q->lchild==NULL){//左子树为空，建立前驱线索
        q->lchild=pre;//q前驱指向pre
        q-ltag=1;//修改标志位
    }
    if(pre!=NULL&&pre->rchild==NULL){
        pre->rchild=q;
        pre-rtag=1;
    }
    pre=q;//前驱移动到p
}

5.3 非递归实现后序遍历

#define MaxSize 50
typedef struct BiTNode{
    char data;
    struct BiTNode *lchild,*rchild;
    int tag;//访问位
}BiTNode,*BiTree;

//构造二叉树
BiTree createBiTree(){
    BiTNode *r;
    char s;//结点
    cin>>s;
    if(s=='#'){
        r=NULL;
    }
    else{
        r=(BiTNode *)malloc(sizeof(BiTNode));
        r->data=s;
        r->tag=0;//初始化为0
        cout<<"输入 "<<s<<" 的左孩子结点('#'表示为空):";
        r->lchild=createBiTree();//递归输入当前根结点的左子树
        cout<<"输入 "<<s<<" 的右孩子结点('#'表示为空):";
        r->rchild=createBiTree();//递归右子树
    }
    return r;
}

//非递归实现后序遍历
void PostOrder2(BiTree T){
    struct BiTNode *stack[MaxSize];//声明栈结构
    int top=-1;
    BiTNode *p=T;
    while(p || top!=-1){//栈不空或者当前所指不空
        if(p){//p不空，需要入栈

            ///Push(S,p)
            top++;
            stack[top]=p;
            p=p->lchild;

        }
        else{//栈不空，需要判断右孩子是否存在和有没有被访问过

            p=stack[top];///GetTop(S,p)，只是获取，并不是出栈，此时还不能出栈
            if(p->rchild!=NULL && p->rchild->tag==0){//右孩子存在且没有被访问过
                p=p->rchild;//右移
            }
            else{//右孩子为空或者已经被访问过，出栈并访问，修改访问位

                ///Pop(S,p);
                p=stack[top];
                top--;
                p->tag=1;
                cout<<p->data<<endl;
                p=NULL;//此处必须置空，访问一个元素意味着需要栈弹出一个新的元素
            }
        }
    }
}