《数据结构复习资料.docx》由会员分享，可在线阅读，更多相关《数据结构复习资料.docx（7页珍藏版）》请在三一文库上搜索。
1、v1.0可编辑可修改1、函数实现单链表的插入算法。int List In sert(L in kList L,i nt i,ElemType e)LNode *p,*s;i nt j;P=L;j=O;while(p!=NULL)&&(j<i-1)p=p->n ext;j+;if(p=NULL|j>i-1) retur n ERROR; s=(LNode *)malloc(sizeof(LNode); s->data=e;s->n ext=p->n ext)p->n ext=sreturn OK;/*Listl nsert*/2、函数Li
2、stDelete_sq实现顺序表删除算法。int ListDelete_sq(Sqlist *L,i nt i)int k;if(i<1|i>L->length) return ERROR;for(k=i-1;k<L->le ngth-1;k+)7L->slistk= L->slistk+1-L->Le ngthreturn OK;3、函数实现单链表的删除算法。int ListDelete(LinkList L,int i,ElemType *s)LNode *p,*q;int j;P=L;j=0;while( p-> next!=NULL
3、)&&(j<i-1)p=p->n ext;j+;if(p->n ext=NULL|j>i-1) return ERROR;q=p->n ext;p->n ext=q->n ext;*s=q->data;free(q);return OK;/*listDelete*/4、栈的基本操作函数：int In itStack(SqStack *S);换二叉树结点左右子树的递归算法Bitree *fun ctio n(Bitree *bt)Bitree *t,*t1,*t2;if(bt=NULL)t=NULL;elset=(Bitree *)
4、malloc(sizeof(Bitree);t->data=bt->data;t仁fun ctio n(bt->left);t2=f un cti on( bt->right);t->left=t2;t->right=t1;return(t);11、已知二叉树的先序遍历序列为 ABCDEFGH中序遍历序列为CBEDFAGHB出 二叉树。答案：二叉树形态CDHEF-r12、编写求一棵二叉树中结点总数的算法。答案：(以先序遍历的方法为例)void coun t_preorder(Bitree *t, i nt *n)if(t!=NULL)*n+;coun t_p
5、reorder(t->lchild);coun t_preorder(t->lchild); 13、实现图的深度优先遍历算法typedef structint vex nu m,arc num;char vexsN;int arcsNN;graph;void fun ti on (i nt i,graph *g)int j;prin tf(" no de:%c n",g->vexsi);visitedi=TRUE;for(j=0;jvg->vex nu m;j+)if(g->arcsij=1)&&(!visitedj)fun c
6、tio n(j,g);14、对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排 序和归并排序等排序方法，分别写出：(1) 平均时间复杂度低于0(n2)的排序方法；希尔、快速、堆、归并(2) 所需辅助空间最多的排序方法；归并15、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。答案：void lin klist_c(L node *head)Lnode *p; p=head;if(!p) return ERROR;while(p-> next!=NULL)p=p->n ext;p->n ext=head;设单链表的长度(数据结点数)为 N,则该算法的时间主要花费在查找链表最后一个结点上(算法中的 while循环)，所以该算法的时间复杂度为 0( N)