数据结构复习资料7278.pdf

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);换二叉树结点左右子树的递归算法 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，画出二叉树。答案：二叉树形态 AFHGDECB 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;if(!p)return ERROR;while(p-next!=NULL)p=p-next;p-next=head;设单链表的长度（数据结点数）为 N，则该算法的时间主要花费在查找链表最后一个结点上（算法中的 while 循环），所以该算法的时间复杂度为 O（N）