数据结构复习资料

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||j>i-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(i<1||i>L->length) return ERROR;

for(k=i-1;klength-1;k++)

L->slist[k]=L->slist[k+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||j>i-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); }

}//conversion

5、函数实现串的模式匹配算法。

int index_bf(sqstring*s,sqstring *t,int start){ int i=start-1,j=0;

while(ilen&&jlen)

if(s->data[i]==t->data[j]){ 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; else{

hl=depth(t->lchild);

hr= depth(t->rchild) ; if( hl>hr ) return hl+1; else

return hr+1; } }

10.交换二叉树结点左右子树的递归算法 Bitree *function(Bitree *bt){ Bitree *t,*t1,*t2; if(bt==NULL) t=NULL; else{

t=(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，画出二叉树。

答案：二叉树形态

ABCEDFGH 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 vexs[N]; int arcs[N][N];

}graph;

void funtion(int i,graph *g){ int j;

printf(\ visited[i]=TRUE;

for(j=0;jvexnum;j++)

if((g->arcs[i][j]==1)&&(!visited[j])) function(j,g); }

14、对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：

（1）平均时间复杂度低于O（n2）的排序方法；希尔、快速、堆、归并 （2）所需辅助空间最多的排序方法；归并

15、编写算法,将一个头指针为head不带头结点的单链表改造为一个单向循环链表，并分析算法的时间复杂度。 答案：

void linklist_c(Lnode *head) {Lnode *p; p=head; if(!p) return ERROR;

while(p->next!=NULL)

p=p->next; p->next=head; }

设单链表的长度（数据结点数）为N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的while循环），所以该算法的时间复杂度为O（N）

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构复习资料在线全文阅读。