Chapter 2 线性表

2-1线性表的基本操作 书2.1.2

• InitList(&L); //初始化线性表

• Length(L); //求表长，返回表长

• LocationElem(L,e); //按值查找，返回关键元素e的位置

• GetElement(L,i); //按位查找，范围指定位置元素值

• ListInsert(&L,i,e); //指定位置i插入指定的元素

• ListDelete(&L,i,&e);//删除指定位置i的值，并用e返回被删除元素值

• PrintList(L); //输出链表值

• Empty(L); //判断量表是否为空，并返回TRUE或FALSE

• DestroyList(&L);//销毁线性表，释放线性表所占的空间

2-2将La表与Lb表合并到La表中

void Union(SqList *La, SqList Lb){
    ElemType e;
    int La_len,Lb_len;
    int i;
     //求两个线性表的长度
     La_len = ListLength(*La);
     Lb_len = ListLength(Lb);
     for(i = 1; i < Lb_len; i++){
         e = GetElement(Lb,i);  //将第i个元素取出并赋值给e,每次变量e的值都会被修改
         if(!LocationElem(*La,e))   //在A中没有找到B的元素，则插入
            ListInsert(La,++La_len,e);  //在La的末尾插入
     }//for       
}

2-3已知线性表La和Lb的数据元素按值非递减排列

归并La和Lb得到新的线性表Lc,Lc的数据元素也按值非递减排

void MergeList(SqList La, SqList Lb, SqList *Lc)
{
    int i = 1, j = 1, k = 0;
    int La_len, Lb_len;
    ElemType ai,bj;
    InitList(Lc);
    //求两个线性表的长度
    La_len = ListLength(La);
    Lb_len = ListLength(Lb);
    while(i <= La_len && j <= Lb_len){
        ai = GetElement(La,i);
        bj = GetElement(Lb,j);
        if(ai <= bj){
            ListInsert(Lc, ++k, ai);
            ++i;
        }
        else{
            ListInsert(Lc, ++k, bj);
            ++j;
        }
        while( i <= La_len) //表La非空且表Lb空
        {
            ai = GetElement(La, i++);
            ListInsert(Lc, ++k, ai);
        }
while( i <= La_len) //表La非空且表Lb空
        {
            ai = GetElement(La, i++);
            ListInsert(Lc, ++k, ai);
        }
    }
}

Chapter 3 栈和队列

3-1 栈的基本操作

• InitStack(&S) //初始化一个空栈
• StackEmpty(S) //判断一个栈是否为空，返回
• Push(&S,x) //进栈，若栈不满，则加入x，使x成为新的栈顶
• Pop(&S,&x) //出栈，若栈不为空，则删除栈顶元素复制给x，并返回x
• Getop(S,&x) //读出栈顶元素，若栈不为空，则将栈顶元素赋值给x，并返回x
• DestroyStack(&S) //销毁栈

3-2 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数

算法思路，将十进制取模8依次进栈，再输出

void conversion()
{
    SqStack s;
    unsigned n;
    ElemType e;
    InitStack(&s);
    scanf("%u",&n); //输入非负的十进制数
    while(n){   //当n不等于0，所有余数入展
        Push(&s,n%8);   //入栈（n/8）的余数（8进制的低位）
        n=n/8;
    }
    while(!EmptyStack(S)){  //当栈不为空时
        Pop(&s,&e); //将栈元素弹出并赋值给e
        printf("%d",e); //输出e
    }
    printf("\n");
}

3-3 对于输入的字符串检验括号是否成对出现（假设只有())

bool Match(char exp[],int n)
{
    int i = 0;
    char e;
    bool match = true;
    LinkStNode *st;
    while(i < n && match){
        if(exp[i]=='(')
            Push(st,exp[i]);
        else if(exp[i]==')'){
            if(GetTop(st,e)==true){
                if(e!='(')
                    match = false;
                else    
                    Pop(st,e)
            }
            else match = false;
        }
        i++;
    }
    if(!StackEmpty(st))
        match = false;
    DestroyStack(st);
    return match;
}

3-4 队列的基本操作

• InitQueue(&Q) //初始化队列，构造一个空队列
• QueueEmpty(Q) //判断队列是否为空，并返回TRUE或FALSE
• EnQueue(&Q,x) //入队，若队列未满，则将x加入队列成为新的队尾
• DeQueue(&Q,&x) //出队，若队列不空，则删除队头元素，并将队头元素赋值给x返回
• GetHead(Q,&x) //读出队头元素，若队列非空则将队头元素赋值给x并返回

Chapter 4 树与二叉树