[数据结构与算法]数据结构期末考试算法总结

1.设计一个高效的算法，从顺序表L中删除所有值为x的元素，要求时间复杂度为O(n),空间复杂度为O(1).

//p71
#define MAXSIZE 100
typedef struct
{
    ElemType elem[MAXSIZE];
    int last;
}SeqList;

void delx(SeqList * L,ElemType x)
{
    int i = 0;
    int j = 0;
    while(i <= L->last)
    {
        if(L->elem[i]!=x)
        {
            L->elem[j] = L->elem[i];
            i++;
            j++;
        }
        else
            i++;
        
    }
    L->last = j-1;
}

2.算法实现带头节点单链表的就地址逆置问题。

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node, *LinkList;

void ReverseList(LinkList L)
{
    Node * p;
    Node * q;
    p = L->next;
    L->next = NULL;
    while(p!=NULL)
    {
        q = p->next;
        p->next = L->next;
        L->next = p;
        p = q;
    }
}

3.已知一个带头结点的单链表L，其结点的元素值以非递减顺序排列，设计算法删除该单链表中元素值重复的结点

typedef struct Node
{
    ElemType data;
    struct Node * next;
}Node, *LinkList;

void del(LinkList L)
{
    Node * p;
    Node * q;
    p=L->next;
    if(p==NULL)
        return error;
    while(p->next != NULL)
    {
        if(p->data != p->next->data)
            p = p->next;
        else
        {
            q = p->next;
            p->next = q->next;
            free(q);
        }
    }
}

4.以二叉链表做存储结构，编写算法输出二叉树中叶子结点(先序)。

typedef struct Node
{
    DataType data;
    struct Node * LChild;
    struct Node * RChild;

}BiTNode,*BiTree;

void InOrder(BiTNode root)
{
    if(root != NULL)
    {
        InOrder(root->LChild);
        Visit(root->data);
        InOrder(root->RChild);
    }
}

5.以二叉链表做存储结构，编写递归算法，求二叉树的高度(后序)。

typedef struct Node
{
    DataType data;
    struct Node * LChild;
    struct Node * RChild;

}BiTNode,*BiTree;

int PostTreeDepth(BiTree bt)
{
    int hl,hr,max;
    if(bt!=NULL)
    {
        hl = PostTreeDepth(bt->LChild);
        hr = PostTreeDepth(bt->RChild);
        max =hl>hr?hl:hr;
        return(max+1);
    }
    else
        return(0);
}

6.以二叉链表做存储结构，编写递归算法，求二叉树的高度(先序)。

typedef struct Node
{
    DataType data;
    struct Node * LChild;
    struct Node * RChild;

}BiTNode,*BiTree;

void PreTreeDepth(BiTree bt,int h)
{
    //先序遍历求二叉树bt高度的递归算法，h为bt指向结点所在层次，初值为1
    //depth 为当前求得的最大层次，为全局变量，调用前初值为0
    if(bt!=NULL)
    {
        if(h>depth)
        {
            depth = h;
        }
        PreTreeDepth(bt->LChild,h+1);
        PreTreeDepth(bt->RChild,h+1);
    }
}

7.折半查找法。

# define LIST_SIZE 20
typedef struct
{
    KeyType key;
    OtherType other_data;
}RecordType;

typedef struct
{
    RecordType r[LIST_SIZE+1]// r[0] 为工作单元
    int length;
} RecordList;

int BinSrch(RecordList l,KeyType k)
{
    int low = 1;
    int hight = l.length;//设置区间初值
    while(low<=hight)
    {
        mid=(low+hight) / 2;
        if(k==l.r[mid].key)
            return(mid);
        else if(k<l.r[mid].key)
            hight = mid-1;
        else
            low =mid+1;
    }
    return (0);
}