数据结构复习资料

1、函数实现单链表的插入算法。int ListInsert(LinkList L,int i,ElemType e) LNode *p,*s;int j; p=L;j=0; while(p!=NULL)&(jnext;j+; if(p=NULL|ji-1) return ERROR; s=(LNode *)malloc(sizeof(LNode); s-data=e; s-next=p-next )p-next=s return OK;/*ListInsert*/2、函数ListDelete_sq实现顺序表删除算法。int ListDelete_sq(Sqlist *L,int i) int k; if(iL-length) return ERROR;for(k=i-1;klength-1;k+) L-slistk=L-slistk+1 -L-Length return OK;3、函数实现单链表的删除算法。int ListDelete(LinkList L,int i,ElemType *s) LNode *p,*q; int j; p=L;j=0; while( p-next!=NULL )&(jnext;j+; if(p-next=NULL|ji-1) return ERROR; q=p-next; p-next=q-next ; *s=q-data; free(q); return OK;/*listDelete*/4、栈的基本操作函数：int InitStack(SqStack *S); /构造空栈int StackEmpty(SqStack *S);/判断栈空int Push(SqStack *S,ElemType e);/入栈int Pop(SqStack *S,ElemType *e);/出栈函数conversion实现十进制数转换为八进制数，请将函数补充完整。void conversion()InitStack(S);scanf(“%d”,&N);while(N) Push(S,N%8) ;N=N/8;while( !StackEmpty(S) )Pop(S,&e);printf(“%d”,e);/conversion5、函数实现串的模式匹配算法。int index_bf(sqstring*s,sqstring *t,int start) int i=start-1,j=0; while(ilen&jlen) if(s-datai=t-dataj) i+;j+; else i= i-j+1 ;j=0; if(j=t-len) return i-t-len+1 ; else return -1;/*listDelete*/6、二叉树后序遍历递归算法void function(Bitree *t)if(p!=NULL)function(p-lchild);function(p-rchild);printf(“%d”,p-data);7、编写求一棵二叉树中结点总数的算法。答案：（以先序遍历的方法为例）void count_preorder(Bitree *t, int *n) if(t!=NULL)*n+;count_preorder(t-lchild);count_preorder(t-lchild); 8、函数InOrderTraverse(Bitree bt)实现二叉树的中序遍历。void InOrderTraverse(BiTree bt)if( bt!=NULL )InOrderTraverse(bt-lchild);printf(“%c”,bt-data); InOrderTraverse(bt-rchild) ;9、函数depth实现返回二叉树的高度。int depth(Bitree *t)if(t=NULL)return 0;elsehl=depth(t-lchild);hr= depth(t-rchild) ;if( hlhr )return hl+1;elsereturn hr+1;10.交换二叉树结点左右子树的递归算法Bitree *function(Bitree *bt)Bitree *t,*t1,*t2;if(bt=NULL)t=NULL;elset=(Bitree *)malloc(sizeof(Bitree);t-data=bt-data;t1=function(bt-left);t2=function(bt-right);t-left=t2;t-right=t1;return(t);11、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。答案：二叉树形态 12、编写求一棵二叉树中结点总数的算法。答案：（以先序遍历的方法为例）void count_preorder(Bitree *t, int *n) if(t!=NULL)*n+;count_preorder(t-lchild);count_preorder(t-lchild); 13、实现图的深度优先遍历算法typedef struct int vexnum,arcnum; char vexsN; int arcsNN;graph;void funtion(int i,graph *g) int j; printf(node:%cn,g-vexsi); visitedi=TRUE; for(j=0;jvexnum;j+) if(g-arcsij=1)&(!visitedj) function(j,g);14、对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：（1）平均时间复杂度低于O（n2）的排序方法；希尔、快速、堆、归并（2）所需辅助空间最多的排序方法；归并15、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。答案：void linklist_c(Lnode *head) Lnode *p; p=head;