算法设计题

单链表

typedef struct LNode{
    ElemType data;
    struct LNode *next;
}LNode, *LinkList;
//头插法建表
LinkList List_HeadInsert(LinkList &L){
    LNode *s; int x;
    L = (LinkList)malloc(sizeof(LNode));	//创建头结点
    L->next = NULL;		//初始为空链表
    scanf("%d", &x);	//输入结点的值
    while(x!=9999){		//输入9999表示结束
        s = (LNode*)malloc(sizeof(LNode));		//创建新结点
        s->data = x;
        s->next = L->next;
        L->next = s;	//将新结点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}
//按序号查找结点值
LNode *GetElem(LinkList L, int i){
    int j = 1;		//计数，初始为1
    LNode *p = L->next;		//第一个结点指针赋给p
    if(i==0)
        return L;		//若i等于0，则返回头结点
    if(i<1)
        return NULL;	//若i无效，则返回NULL
    while(p && j<i){	//从第一个结点开始找，查找第i个结点
        p = p->next;
        j++;
    }
    return p;		//返回第i个结点的指针，若i大于表长，则返回NULL
}
//按值查找表结点
LNode *LocateElem(LinkList L, ElemType e){
    LNode *p = L->next;
    while(p!=NULL && p->data!=e)
        p = p->next;
    return p;
}

栈

typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
}StackType;
//初始化
void InitStack(StackType **top){
    *top = (StackType *)malloc(sizeof(StackType));
    (*top)->next = NULL;
}
//入栈操作
int pushStack(StackType *top, ElemType x){
    StackType *p;
    p = (StackType *)malloc(sizeof(StackType));	//申请结点
    p->data = x;
    p->next = top->next;
    top->next;
    return true;
}
//出栈操作
ElemType popStack(StackType *top){
    StackType *p;
    ElemType x;
    if(top->next == NULL){
        printf("空栈！")
        return NULL;
    }
    else{
        p = top->next;
        top-next = p->next;
        x = p->data;
        free(p);
        return x;
    }
}
//取栈顶数据元素
ElemType GetTop(StackType *top){
    if(top->next = NULL){
        return NULL;
    }
    else{
        return (top->next->data);
    }
}

二叉树

typedef struct BiTNode{
    ElemType data;		//数据域
    struct BiTNode *lchild, *rchild;	//左，右孩子指针
}BiTNode, *BiTree;
//先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);		//访问根结点
        PreOrder(T->lchild);	//递归遍历左子树
        PreOrder(T->rchild);	//递归遍历右子树
    }
}
//中序遍历 InOrder
//后序遍历 PostOrder

快速排序

void QuickSort(ElemType A[], int low, int high){
    if(low<high){		//递归跳出的条件
        int pivotpos = Partition(A, low, high);		//划分
        QuickSort(A, low, pivotpos-1);		//左子表递归
        QuickSort(A, pivotpos+1, high);		//右子表递归
    }
}
//划分函数
int Partition(ElemType A[], int low, int high){		//一趟划分
    ElemType pivot = A[low];	//将当前表中第一个元素设为枢轴，对表进行划分
    while(low<high){	//循环跳出条件
        while(low<high && A[high]>=pivot) --high;
        A[low] = A[high];		//将比枢轴小的元素移动到左端
        while(low<high && A[low]<=pivot) ++low;
        A[high] = A[low];		//将比枢轴大的元素移动到右端
    }
    A[low] = pivot;		//枢轴元素存放到最终位置
    return low;		//返回存放枢轴元素的最终位置
}

折半查找

int Binary_Search(SeqList L, ElemType key){
    int low = 0, high = L.TableLen-1, mid;
    while(low<=high){
        mid = (low+high)/2;		//取中间位置
        if(L.elem[mid]==key)
            return mid;		//查找成功则返回所在位置
        else if(L.elem[mid]>key)
            high = mid-1;		//从前半部分继续查找
        else
            low = mid+1;		//从后半部分继续查找
    }
    return -1;		//查找失败，返回-1
}

-------------本 文 结 束 感 谢 您 的 阅 读-------------