数据结构常用算法

PAGEPAGE11专升本考试计算机专业《数据结构》算法专题1．设计一个算法，计算单链表中数据域值为x的结点个数。逐个查找单链表中的结点x，并计数。intnumber(lnode*h,intx){intn=0；while(h){if(h->data==x)n++；h=h->next；}returns；}2．设计一个用前插法建立带表头结点的单链表的算法。前插法建立带表头结点的单链表算法中的tag为输人数据结束标志。Lnode*createhh(inttag){intx；Lnode*p，*h=(Lnode*)malloc(sizeof(Lnode))；h->next=NULL；printf("inputx:")；scanf("%d",&x);while(x!=tag){p=(Lnode*)malloc(sizeof(Lnode));p->data=x;p->next=h->next;h->next=p;scanf("%d",&x);}returnh;}3．解本题的基本思想是：先将顺序队列q中所有元素出队，并依次进入顺序栈s中，然后出栈，再依次入队。设队列中的元素为a1,a2,…,an，出队并进栈的序列为a1，a2，…，an，出栈并入队的序列为an，an-1，…，a1，可见顺序队列q中所有元素已逆置了。顺序队列的类型定义为：#defineMAX100typedefstruct{intdata[MAX]；intfront,rear；}Squeue；算法描述如下：voidinvert(Squeue*q){ints[MAX],top=0;while(q->front<q->rear)s[top++]=q->data[++q->front];q->front=-1;q->rear=0;while(top>0)q->data[q->rear++]=s[--top];}4．利用栈实现将十进制数x转换成二进制数并输出结果。VoidBNumber（intx）算法设计题：1.设计算法将一个带头结点的单循环链表A分解为两个具有相同结构的链表B、C，其中：B表中的结点为A表中元素的顺序号为奇数的结点，而C表中的结点为A表中元素的顺序号为偶数的结点。（要求利用原表结点。）2.已知S为顺序栈。写出S的存储结构类型描述。试编写算法实现将元素x插入栈S的入栈操作Push(S,x)和删除栈顶元素的出栈操作Pop(S)。3.已知队列Q以循环队列存储。写出Q的存储结构类型描述，并试编写算法实现将元素x插入队列Q的入队操作EnQueue(Q,x)和从队列Q中获取队首元素的函数GetTop(Q)。4.假设线性表L=(a1,a2,……,an)用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,……,a2,a1)。5.设有两个按升序排列的单链表X和Y，其头指针分别为p,q结点结构说明如下：typedefstructnodel{intdata;structnodel*next}node;试设计一个算法voidconcat(node*p,*q)将它们合并成一个以p为头指针的单链表Z，使其仍然有序。6.设有序表r长度为n，欲在表中查找键值为Kn的某元素。若查找成功，则返回该元素在有序表r中的位置，若不成功，则返回0值。用二分查找法，编写一算法完成上述操作，并给出该算法的平均查找长度。该有序表存储结构定义如下Typedefstruct{keytypekey;Elemtypedata;}rec;Typedefstruct

{rec

item［maxsize+1］;

intn;

}sqtable;7、利用表达式的逆波兰式计算表达式的值。提示：设栈S，顺序读表达式的逆波兰式，读一个操作数则入栈，读一个操作符则弹栈2次，并计算此操作，将结果重新入栈。数据结构算法2003年真题设计求二叉树深度的算法。intBTreeDepth(btree*b){ intleftdep,rightdep; if(t==NULL) return0; else{ leftdep=BTreeDepth(b->left); rightdep=BTreeDepth(b->right); if(leftdep>rightdep) returnleftdep+1; else returnrightdep+1;}}2005年真题1、二叉树采用连接存储结构，试设计一个算法计算一棵给定二叉树的单孩子结点数。（只写算法函数）（11分）intonechild(btree*b){ btree*t=b; if(t==NULL) return0; elseif(t->lchild==NULL&&t->rchild!=NULL||t->lchild!=NULL&&t->rchild==NULL) returnonechild(t->lchild)+onechild(t->rchild)+1; else returnonechild(t->lchild)+onechild(t->rchild);}2、已知线性表中的元素以值递增有序排列，并以单链表作为存储结构，试编写一高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删除结点空间，并分析你的算法的时间复杂度（10分）voidDelete_Equal(LNode*head) //时间复杂度O(n2){ intx; LNode*q,*t,*p; p=head->next; while(p!=NULL) { x=p->data; q=p; while(q->next!=NULL) { if(x==q->next->data) { t=q->next; q->next=t->next; free(t); } else { q=q->next; } } p=p->next; }}voiddelinfo(LNode*h) ////时间复杂度O(n){ structLNode*t,*p,*q; p=h->next; //删除重复元素 t=p; while(t->next!=NULL) { if(t->data==t->next->data) { q=t->next; t->next=q->next; free(q); } else { t=t->next; } }}voiddelinfo2(LNode*h)//时间复杂度O(n){ LNode*p,*q; p=h->next; if(p==NULL) return; while(p->next!=NULL) { if(p->data==p->next->data) { q=p->next; p->next=p->next->next; free(q); } else { p=p->next; } }}voidfun(LNode*h)//时间复杂度O(n){ LNode*p,*q; p=h->next; while(p!=NULL&&p->next!=NULL) { q=p->next; if(p->data!=q->data) { p=p->next; } else { p->next=q->next; free(q); } }}2007年真题试编写一个在带头结点的双向循环链表中值为x的结点之前，插入值为y的结点的算法。（要求：用C语言描述，结点类型定义为DlinkList）StatusInsertPrior-L(DlinkList*L,intx,inty)//x之前插入y结点{ DNode*s,*p; p=L->next; while(p!=L&&p->data!=x) p=p->next; if(p!=L) { s=(DNode*)malloc(sizeof(DNode)); s->data=y; s->next=p; s->prior=p->prior; p->prior->next=s; p->prior=s; }}2009年真题程序填空题：单链表中，无序单链表转化为有序单链表（10分）voidsort3(LNode*L)//无序链表排序，利用单链表就地逆置的思想{ LNode*p,*q,*s;//s保存新摘结点，p保存原有链表，q在新链表中找位置 if(L->next==NULL) return; p=L->next->next; //从第二个结点开始 L->next->next=NULL; while(p!=NULL) { s=p; p=p->next; //p保存原有链表 q=L; while(q->next!=NULL&&s->data>q->next->data)//查找插入位置 q=q->next; s->next=q->next; //插入结点 q->next=s; }}voidsort4(LNode*L)//无序链表排序，利用直接选择排序思想{ LNode*p,*q,*s;//p控制外层循环，q保存最小结点，s找位置 intx; if(L->next==NULL) return; p=L->next; //第一个结点 while(p!=NULL) { q=p;//假设当前结点值是最小的 s=p->next; //从第二个结点开始 while(s!=NULL)//循环找最小的结点，由q指向 { if(s->data<q->data) q=s; s=s->next; } x=p->data; //交换两个结点的数据域 p->data=q->data; q->data=x; p=p->next; //下一个结点 }}//直接选择排序是每次从n-i+1个结点中选择码值最小者，与第i个结点的码值进行交换，设p指向第i个结点，//min指向无序表中码值最小的结点，算法描述如下：voidselesort1(Lnode*h){ Lnode*p,*q,*min; intx; p=h->next; while(p) { min=p; q=p->next; while(q) { if(q->key<min->key) m=q; q=q->next; } if(min!=p) { x=p->key; p->key=min->key; min->key=x; } p=p->next; }}模拟二设n个整数存于数组x中，写一算法将所有偶数移到奇数之前，要求时间复杂度为O(n)。voidchange(inta[],intn){ inti=1,j=n; while(i<=j) { if(i%2==0) i++; elseif(j%2!=0) j--; else { a[0]=a[i];a[i]=a[j];a[j]=a[0]; i++;j--; } } }模拟三1．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。voidBubbleSort2(inta[],intn)//相邻两趟向相反方向起泡的冒泡排序算法{ inti,t,change,low,high; change=1;//有交换 low=0;high=n;//冒泡的上下界 while(low<high&&change) { change=0;//设不发生交换 for(i=low;i<high;i++)//从上向下起泡 if(a[i]>a[i+1]) { t=a[i]; a[i]=a[i+1];a[i+1]=t;change=1; }//有交换，修改标志change high--;//修改上界 for(i=high;i>low;i--)//从下向上起泡 if(a[i]<a[i-1]) { t=a[i]; a[i]=a[i-1];a[i-1]=t;change=1; } low++;//修改下界 }//while}//BubbleSort2模拟四1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试将新元素e插入表中第i-1个和第i个元素之间,写出算法。voidinsert(ElemTypest[],ElemTypee,inti,intn)//插入表元素{ intj; if(n==maxlen){ printf("数组已满,不能进行插入操作!\n"); return;} if(i<1||i>n+1) { printf("位置参数不正确,不能进行插入操作!\n"); return; } n++; for(j=n;j>i;j--) /*结点向后移动，腾出一个位置*/ { st[j]=st[j-1]; } st[j]=e;}2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Emptylist！”。Voiddisp(LNode*Head){ LNode*p=Head; If(p->next==NULL) Printf(“Emptylist!”); Else { Printf(“%c”,p->next->data); While(p->next!=NULL) { P=p->next; } Printf(“%c”,p->data); }}模拟五1.已知S为顺序栈。写出S的存储结构类型描述。试编写算法实现将元素x插入栈S的入栈操作Push(S,x)和删除栈顶元素的出栈操作Pop(S)。#defineMax50typedefcharElemType;typedefstructStack{ ElemTypestack[Max]; inttop;}SqStack;voidinitStack(SqStack*s){ s->top=-1;}voidpush(SqStack*s,ElemTypex){ if(s->top==Max-1) { printf("栈上溢！！"); exit(0); } s->top++; s->stack[s->top]=x;}voidpop(SqStack*s){ if(s->top==-1) { printf("空栈！！\n"); return; } s->top--;}2.假设线性表L=(a1,a2,……,an)用带头结点的单链表存储表示，试编写算法对其实现就地逆置，即利用原链表中每一个结点存储空间，使得元素的逻辑次序改变为(an,……,a2,a1)。structlNode { intdata; structlNode*next;};voidlreserve1(structlNode*head){ structlNode