编辑代码

#include <stdio.h>
int main () {
    //JSRUN引擎2.0,支持多达30种语言在线运行,全仿真在线交互输入输出。 
    printf("Hello world!     - c.jsrun.net.");
    return 0;
}  
//线性表的单链表存储结构
typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode,*LinkList;
//算法 2.7
Status GetElem L(LinkList L,int i, ElemType &e){
    //L为带头结点的单链表的头指针
    //当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR
    P=L->next;j=1;            //初始化,p指向第一个结点,j为计数器
    while(p&&j<i){            //顺指针向后查找,直到p指向第i个元素或p为空
        p=p->next;++j;
    }
    if(!p||j>i)return ERROR;  //第i个元素不存在
    e=p->data;                //取第i个元素
    return OK;
}//GetElem_L
//算法 2.8
Status ListInset_L(LinkList &L,int i, ElemType e){
    //在带头结点的单链线性表L中第i个位置之前插入元素e
    p=L;j=0;
    while(p&&j<i-1){p=p->next;++j;} //寻找第i-1个结点
    if(!p||j>i-1)return ERROR;               //i小于1或者大于表长+1
    s=(LinkList) malloc(sizeof(LNode));      //生成新结点
    s->data=e;s->next=p->next;               //插入L中
    p->next=s;
    return OK;
}//ListInsert_L

//算法  2.9
Status ListDelete_L(LinkList &L,int i,ElemType &e){
    //在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
    p=L;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; free(q);
    return OK;
}//ListDelete_L

//算法2.10
void CreateList_L(LinkList &L ,int n){
    //逆序输入n个元素的值,建立带头结点的单链线性表L。
    L=(LinkList) malloc(sizeof(LNode));
    L->next=NULL;           //先建立一个带头结点的单链表
    for(i=n;i>0;--i){
        p=(LinkList) malloc(sizeof(LNode)); //生成新结点
        scanf(&p->data); //输入元素值
        p->next=L->next;L->next=p;//插入到表头
    }
}//CreateList_L


//算法2.11
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    //已知单链线性表La和Lb的元素按值非递减排列
    //归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列。
    pa=La->next;pb=Lb->next;
    Lc=pc=La;          //用La的头结点作为Lc的头结点
    while(pa&&pb){
        if(pa->data<=pb->data){
            pc->next=pa;pc=pa;pa=pa->next;
        }
        else{pc->next=pb;pc=pb;pb=pb->next;}
    }
    pc->next=pa?pa:pb; //插入剩余段
    free(Lb);          //释放Lb的头结点
}//MergeList_L
// //-----------------------线性表的静态单链表存储结构-----------------------------------
// #define MAXSIZE 1000//链表的最大长度
// typedef struct{
//     ElemType data;
//     int      cur;
// }component,SLinkList[MAXSIZE]

//算法2.12
int LocateElem_SL(SLinkList S,ElemType e){
    //在静态单链线性表L中查找第1个值为e的元素
    //若找到,则返回它在L中的位序,否则返回0
    i=S[0].cur;                             //i指示表中第一个结点
    while(i&&s[i].data!=e)i=S[i].cur;       //在表中顺链表查找
    return i;
}//LocateElem_SL

//算法2.13
void InitSpace_SL(SLinkList &space){
    //将一维数组space中各分量链成一个备用链表,space[0].cur为头指针
    //“0” 表示空指针
    for(i=0;i<MAXSIZE-1;++i)space[i].cur;
    space[MAXSIZE-1].cur=0;
}//InitSpace_SL

//算法2.14
int Malloc_SL(SLinkList &space){
    //若备用空间链表非空,则返回分配的结点下标,否则返回0
    i=space[0].cur;
    if(space[0].cur)space[0].cur=space[i].cur;
    return i;
}//Malloc_SL

//算法2.15
void Free_SL(SLinkList &space,int k){
    //将下标为k的空闲结点回收到备用链表
    space[k].cur=space[0].cur;space[0].cur=k;
}//Free_SL

//算法2.16
void difference(SLinkList &space,int &S){
//依次输入集合A和集合B的元素,在一维数组space中建立表示集合(A-B)U(B-A)
//的静态链表,S为其头指针。假设备用空间足够大,space[0].cur为其头指针
    InitSpace_SL(space);       //初始化备用空间
    S=Malloc_SL(space);        //生成S的头结点
    r=S;                      //r指向S的当前最后结点
    scanf(m,n);                //输入A和B的元素个数
    for(j=1;j<=m;++j){         //建立集合A的链表
        i=Malloc_SL(space);   //分配结点
        scanf(space[i].data); //输入A的元素值
        space[r].cur=i;r=i;   //插入到表尾
    }//for
    space[r].cur=0;                              //尾结点指针为空
    for(j=1;j<=n;++j){                           //依次输入B的元素,若不在当前表中,则插入否则删除
        scanf(b);p=S;k=space[S].cur;             //k指向集合A中第一个结点
        while(k!=space[r].cur&&space[k].data!=b){//当前表中查找
            p=k;k=space[k].cur;
        }//while
        if(k==space[r].cur){                    //当前表中不存在该元素,插入在r所指结点之后,且r的位置不变
            i=Malloc_SL(space);
            space[i].data=b;
            space[i].cur=space[r].cur;
            space[i].cur=i;
        }//if
        else{                                    //该元素已在表中,删除之
            space[p].cur=space[k].cur;           
            Free_SL(space,k);
            if(r==k)r=p;                         //若删除的是r所指结点,则需要修改尾指针
        }//else
    }//for
}//difference

//------------------线性表的双向链表存储结构-------------------
typedef struct DuLNode{
         ElemType       data;
         struct DuLNode *prior;
         struct DuLNode *next;
}DuLNode,*DuLinkList;

Status ListInsert_DuL(DuLinkList &L,int i,ElemType e){
    if(!(p=GetElemP_DuL(L,i)))
    return ERROR;

    if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))) return ERROR;
    s->data=e;
    s->prior=p->prior; p->prior->next=s;
    s->data=e;         p->prior=s;
    return OK;
}//ListInsert_DuL


//算法2.17

//算法2.18
Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
    //删除带头结点的双链循环线性表L的第i个元素,i的合法值为1<=i<=表长
    if(!(p=GetElemP_DuL(L,i))    //在L中确定第i个元素的位置指针P
        return ERROR;            //p=NULL,即第i个元素不存在
    e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p); return OK;
}//ListDelete_DuL


//带头结点的线性链表类型定义如下:
typedef struct LNode{//结点类型
    ElemType      data;
    struct LNode  *next;
}*Link, *Position;

typedef struct{        //链表类型
    Link head,tail;    //分别指向线性链表中的头结点和最后一个结点
    int  len;          //指示线性链表中数据元素的个数
}LinkList;

Status MakeNode(Link &p,ElemType e);
//分配由p指向的值为e 的结点,并返回OK;若分配失败,则返回ERROR
void FreeNode(Link &L);
//释放p所指结点
Status InitList(LinkList &L);
//构造一个空的线性链表L
Status DestryList(LinkList &L);
//销毁线性链表L,L不再存在
Status ClearList(LinkList &L);
//将线性链表L重置为空表,并释放原链表的结点空间
Status InsFirst(Link h,Link s);
//已知h指向线性链表的头结点,将s所指结点插入在第一个结点之前
Status DelFirst(Link h,Link &q);
//已知h指向线性链表的头结点,删除链表中的第一个结点,并以q返回
Status Append(LinkList &L,Link s);
//将指针s所指的一串结点链接在线性链表L的最后一个结点


//算法2.19
Status ListInsert_L(LinkList &L ,int i,ElemType e ){
    //在带头结点的单链线性表L的第i个元素之前插入元素
    if(!LocatePos(L,i-1,h)) return ERROR;  //i值不合法
    if(!MakeNode(s,e)) return ERROR;       //结点存储分配失败
    InsFirst(h,s);                         //对于从第i个结点开始的链表,第i-1个结点是它的头结点
    return OK;
}//ListInsert_L

//算法2.20
Status MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc ,int (*compare)(ElemType,ElemType)){
    if(!InitList(Lc)) return ERROR;
    ha=GetHead(La); hb=GetHead(Lb);
    pa=NextPos(La,ha); pb=NextPos(Lb,hb);
    while(pa&&pb){
        a=GetCurElem(pa);b=GetCurElem(pb);
        if((*compare)(a,b)<=0){
            DelFirst(ha,q);Append(Lc,q);pa=NextPos(La,ha);
        }else{
            DelFirst(hb,q);Append(Lc,q);pb=NextPos(Lb,hb);
        }
        if(pa) Append(Lc,pa);
        else Append(Lc,pb);
        FreeNode(ha);  FreeNode(hb);
        return OK;
    }//MergeList_L
}
//算法2.21
//算法2.22
void AddPloyn(polynomial &Pa,polynomial *Pb){
    ha=GetHead(Pa); hb=GetHead(Pb);
    qa=NextPos(pa,ha);qb=NextPos(Pb,hb);
    while(qa && qb){
        a=GetCurElem(qa); b=GetCurElem(qb);
        switch(*cmp(a,b)){
            case -1:
                ha=qa;qa=NextPos(Pa,qa);break;
            case 0:
             sum=a.coef+b.coef;
             if(sum!=0.0){
                 SetCurElem(qa,sum); ha=qa;
             }else{
                 DelFirst(ha,qa);FreeNode(qa);
             }
             DelFirst(hb,qb); FreeNode(qb);qb=NextPos(Pb,hb);
             qa=NextPos(Pa,ha);break;
            case 1:
              DelFirst(hb,qb); InsFirst(ha,qb);
              qb=NextPos(Pb,hb);qa=NextPos(Pa,ha);break;
        }
    }
    if(!ListEmpty(pb)) Append(Pa,qb);
    FreeNode(hb);
}
//算法2.23
//算法2.24
//算法2.25




//ADT Stack的表示与实现
//栈的顺序存储表示
#define STACK_INIT_SIZE 100        //存储空间初始分配量
#define STACKINCREAMENT 10         //存储空间分配增量
typedef struct{
    SElemType *base;               //在栈构造之前和销毁之后,base的值为NULL
    SElemType *top;                //栈顶指针
    int stacksize;                 //当前已分配的存储空间,以元素为单位
}SqStack;
//基本操作的函数原型说明
Status InitStack(SqStack &S);
//构造一个空栈S
Status DestroyStack(SqStack &S);
//销毁栈S,S不再存在
Status ClearStack(SqStack &S);
//把S置为空栈
Status StackEmpty(SqStack &S);
//若栈S为空栈,则返回true,否则返回false