2016-941

2016-941

1.查找倒数第k个值

• 一个带有表头结点的单链表，结点结构为（data，link）
• 链表只给出了头指针list
• 在不改变链表的前提下，查找出链表中倒数第k个位置上的结点
• 若查找成功，输出该结点的data域的值，并返回1；否则，只返回0

（1）描述算法基本思想

• 先求出链表的长度
• 再用链表长度减去倒数第k个，就为倒数第k个的正向下标
• 例如：链表长度为6，求倒数第2个值，即正数6-2=4下标
• 在正向循环得出即可

（2）写出代码

（3）分析时间复杂性

typedef struct LNode{     //定义单链表结点类型
    int data;             //数据域
    struct LNode *link;   //指针域，指向下一个结点的指针
}LNode,*LinkList;         //LNode是结构体的别名，用LNode即可代替typedef struct LNode
                          //LinkList是结构体指针的别名，用LinkList指针代替struct LNode *next
int DaoshuK(LinkList list，int k){
    int len = 0;
    int i = -1;//
    LNode *p = list, *q = list;   //p用来求链表长度,q开始查找倒数第k个值的下标
    while(p != NULL){             //求链表长度
        len++;
        p = p -> link;
    }
    while(q->link){
        i++;
        if(i == len-k){           //找倒数第k个值
            int data = q->data;
            return data,1；
        }
        q = q -> link;
    }
    return 0;    
}

2.输出二叉树序列S

• 输出二叉树序列，以r为树根
• 给出二叉树序列，输出二叉树

（1）算法思想

• 引入一个辅助栈，以树的先序非递归遍历思想为基础，根据所给序列正向建树。
• 若当前p指向结点非空，对应序号为0，则他的左右孩子赋值为空；
• 对应序号为1，则创建一个结点，其左指针指向新创建的结点；
• 若对应序号为2，则创建两个结点，其左右指针分别指向两个结点

（2）代码

BiTree CreateTree(BiTree &r,int A[],int len){
    //该算法根据数组A中序建树，序列长度就是数组长度len
    BiTree Stack[MaxSize];
    int top = -1;//栈初始化
    int i = 0;//计数值，判断序列结束
    BiTree p = r, bt = NULL;//p用来遍历，bt用来辅助创造结点
    while(p != NULL || top != -1 && i < len){
        if(p != MULL){
            if(A[i] == 0){
                p -> lchild = NULL;
                P -> rchild = NULL;
                Stack[++top] = p;
            }
            if(A[i] == 1){
                bt = (BiTree)malloc(sizeof(BiTree));
                p -> lchild = bt;
                P -> rchild = NULL;
                Stack[++top] = NULL;
            }
            if(A[i] == 2){
                bt = (BiTree)malloc(sizeof(BiTree));
                p -> lchild = bt;
                bt = (BiTree)malloc(sizeof(BiTree));
                P -> rchild = bt;
                Stack[++top] = p;
            }
            i++;
            p = p -> lchild
        }else{
            p = Stack[top--];
            p = p -> rchild;
        }
    }
    return r;
}