数据结构算法题

//获取叶子节点个数

int getLevers(BiTree p)
{
int leftCount;rightCount;

if(p == null)
return 0;
else if(p->lchild == null && p->rchild == null)
rururn 1;
else
return getLevers(p->lchild) + getLevers(p->rchild);

}

设计算法,从顺序表L中删除所有值为x的元素。要求算法的时间复杂度为O(n)，空间复杂度为0(1)。
void ListDelete(Sqlist &L,int x)
{
int count = 0;
for(int i = 0;i < L.length;i++ )
{
if(L.data[i]==x)
count++; //等于x跳过
else
data[i-count] = data[i]; //不等于x元素
//移动到等于x元素位置上
}
L.length=L.length-count;
}

设计算法，判断一个字符串是否是回文。如atbc3cb+a是回文序列，而
1++3==3+1不是回文序列。

int main()
{
char s[100];
int i = 0, j;
j = strlen(s) - 1;
while (i <= j && s[i] == s[j]) {
//每比较一次就i右移、j左移一位
i++; j–;
}
if (i <= j)
return false;
return true;
}

//设计算法，完成一趟快速排序算法。即将下标从low到high的元素以r[low]为基准分成两部分，小的在前、大的在后。

//快速排序
quickSort(int a[],int low = 0,int high)
{
int begin = low;
int end = high;
int temp = a[low];
while(low < high)
{
while(low < high && a[high] > temp)
–high;
a[low] = a[high]
while(low ++ low;
a[high] = a[low];
}
a[low] = temp;
quickSort(a,begin,low-1);
quickSort(a,low+!,end);
return a;
}

//试编写在链式存储结构实现求两个集合之差函数difference(A,B).令C=A-B,取仅当e是A中的一个元素，但不是B中的元素时，e是C中的一个元素。

void diff(list *la,list *lb)
{
node *pa = la;
node *pb = lb;
node *temp;

while(pa)
{
    pb = b;
    while(pb && pb->data != pa->data)
        pb = pb->next;
    if(pb)
    {
        if(pa == la)
            la = pa->next;
        temp = pa;
        pa = pa->next;
        free(temp);
    }
    else
        pa = pa->next;
}

}

//试设计在带头结点的单循环链表h中查找元素值为x的结点所在的位置的算法
LNode *LocateElem(linkList L, ElemType)
{
Lnode *p = L->next;
while (p != Null && p->next != e)
p = p->next;
return p;
}

3．写出中序线索二叉树中查找节点却中序后继的算法。
//在中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p){
if(p->rtag==1){
p=p->rchild;
}else{
p=FirstNode(p->rchild);
}
return p;
}

中序二叉树

//找到以p为根的子树中，第一个被中序遍历的结点
ThreadNode *FirstNode(ThreadNode *p){
while(p->ltag0){ //循环找到最左下结点
p=p->lchild;
}
return p;
}
//找到以p为根的子树中，最后一个被中序遍历的结点
ThreadNode *LastNode(ThreadNode *p){
while(p->rtag0){
p=p->rchild;
}
return p;
}
//在中序线索二叉树中找到结点p的后继结点
ThreadNode *NextNode(ThreadNode *p){
if(p->rtag==1){
p=p->rchild;
}else{
p=FirstNode(p->rchild);
}
return p;
}

//在中序线索二叉树中找到p的前驱结点
ThreadNode *PreNode(ThreadNode *p){
if(p->ltag==1){
p=p->lchild;
}else{
p=LastNode(p->lchild);
}
return p;
}

1.两个链式存储的线性表LA和LB,其元素均按从小到大的升序排列，编写一个算法将它们合并成一个链表LC,要求LC的元素从大到小的升序排列。要求利用原表长度(即LA表和LB表)的结点空间构造LC表,且算法时间性能达到两个表长之和。

void MergeList(SqList &La, SqList &Lb, SqList &Lc) {
int i = 0, j = 0, k = 0;
Lc.length = La.length + Lb.length;
while (i < La.length && j < Lb.length) {
if (La.elem[i] < Lb.elem[j]) {
Lc.elem[k] = La.elem[i];
i++;
}
else {
Lc.elem[k] = Lb.elem[j];
j++;
}
k++;
}
while (k < Lc.length) {
if (i == La.length) {
Lc.elem[k] = Lb.elem[j];
j++;
}
else {
Lc.elem[k] = La.elem[i];
i++;
}
k++;
}

有两个带头结点的循环单链表LA、LB,编写一个算法，将两个循外早链表合并为一个循环单链表，其头指针为LA,并给出时间复杂度。


linkList merage(linkList la,linkList lb)
{
    node *p,*q;
    p = la->next;
    q = lb->next;
    while(p->next != la)
        p = p->next;
    while(q->next != lb)
        q = q->next;
    p->next = lb->next;
    q->next = la;
    free(lb);
    return la;
}

int main(){
    node *la,*lb,*lc;
    la = creat();
    lb = creat();
    la = merage(la,lb);
    print(la);



3 折半查找的非递归算法

int srarch(int a[],int key)
{
    int low = 0,high = sizeof(a) -1,mid =0;
    while(low <= high)
    {
        mid = (low + high) /2;
        if(key == a[mid])
            return mid;
        else if(key > a[mid])
            low = mid + 1;
        else if(key < a[mid])
            high = mid -1;
    }
    return -1;


}


编写函数InsSort(a,n)，完成对数组a[n]的直接插入排序。
insort(int A[],int n)
{
    int i,j,temp;
    for (i=1;i 0 && A[j] > temp ; --j) {
                A[j+1] = A[j];
            }
            A[j+1] = temp;
        }
    }
}

写一算法，从顺序表中删除自第i个元素开始的k个元素

//顺序表的删除
Status Delete(SqList * L,int Location)
{
if(L->Length==0) //线性表为空
return ERROR;
if(LocationLength)
{
for(int i=Location;iLength;i++)
{
L->data[i-1]=L->data[i];
}
L->Length–;
}

    return OK;
}