数据结构常用算法
作者/cherryqi　时间/2006-8-14 17:07:00　类别/数据结构 查看/
　发表评论　以论坛方式查看
标签：
数据结构常用算法 
数据结构常用算法主要归纳:
1.单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓"就地"指辅助空间应为O(1)。　　
分析：
　　可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：
　　(1)当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。
　　(2)当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的：
　　
　　LinkList ReverseList( LinkList head )
　　　{// 将head 所指的单链表(带头结点)逆置
　　　　ListNode *p ,*q ;//设置两个临时指针变量
　　　　if( head->next && head->next->next)
　　　　　{ //当链表不是空表或单结点时
　　　　　　p=head->next;
　　　　　　q=p->next;
　　　　　　p -> next=NULL; //将开始结点变成终端结点 
 

　　　　　　while (q)
　　　　　　　{ //每次循环将后一个结点变成开始结点　
　　　　　　　　p=q; 
　　　　　　　　q=q->next ;
　　　　　　　　p->next = head-> next ;
　　　　　　　　head->next = p;
　　　　　　　}
　　　　　　return head;
　　　　　}
　　　　return head; //如是空表或单结点表，直接返回head
　　　}
2.12 已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。

解：
　　分析：
　　由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。
　　具体算法如下：

　　LinkList Link( LinkList L1 , LinkList L2，int m,int n )
　　　{//将两个单链表连接在一起
　　　　ListNode *p , *q, *s ;
　　　　//s指向短表的头结点,q指向长表的开始结点，回收长表头结点空间 
　　　　if (m<=n)
　　　　　{s=L1;q=L2->next;free(L2);}
　　　　else {s=L2;q=L1->next;free(L1);}
　　　　p=s;
　　　　while ( p->next ) p=p->next; //查找短表终端结点
　　　　p->next = q; //将长表的开始结点链接在短表终端结点后
　　　　return s;
　　　}

　　本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为：
　　　　　O(min(m,n))
2.14 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。

解：
　　要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点。由于为已知其是有序链表，则介于min 和max之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min结点中的最小结点的直接前趋结点*p后，依次删除小于max的结点，直到第一个大于等于max结点*q位置，然后将*p结点的直接后继指针指向*q结点。 
　　算法如下：
　　void DeleteList ( LinkList L, DataType min , DataType max )
　　　{
　　　　ListNode *p , *q , *s;
　　　　p=L;
　　　　while( p->next && p->next->data <=min ) 
　　　　//找比min大的前一个元素位置
　　　　　p=p->next;
　　　　q=p->next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结点
　　　　while(q &&q->data<max)
　　　　　{s=q;q=q->next;
　　　　　　free(s);//删除结点，释放空间
　　　　　}
　　　　p->next=q;//将*p结点的直接后继指针指向*q结点

　2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。

解：
　　本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。

　　具体算法：
　　　void DeleteList ( LinkList L )
　　　　{　
　　　　　ListNode *p , *q , *s;
　　　　　p=L-next;
　　　　　while( p->next&&p->next->next)
　　　　　　{
　　　　　　　q=p;//由于要做删除操作，所以q指针指向要删除元素的直接前趋
　　　　　　　while (q->next)
　　　　　　　　if (p->data==q->next->data)
　　　　　　　　　{s=q->next;q->next=s->next;free(s);//删除与*p的值相同的结点
　　　　　　　　　}
　　　　　　　　else q=q->next;
　　　　　　　p=p->next;
　　　　　　}
　　　　}　 

 


2.16 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。

解：
　　已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的直接前趋，然后用后删结点法，将结点*s的直接前趋结点删除即可。

　　算法如下：
　　　void DeleteNode( ListNode *s)
　　　　{//删除单循环链表中指定结点的直接前趋结点
　　　　　　ListNode *p, *q;
　　　　　　p=s;
　　　　　　while( p->next->next!=s) 
　　　　　　　p=p->next;
　　　　　　//删除结点
　　　　　　q=p->next;
　　　　　　p->next=q->next;
　　　　　　free(p); //释放空间
　　　　}

　　注意：
　　若单循环链表的长度等于1，则只要把表删空即可。
3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 

解：
　　算法如下：
　//先定义链队结构:
　typedef struct queuenode{
　　　Datatype data;
　　　struct queuenode *next;
　　}QueueNode; //以上是结点类型的定义

　typedef struct{
　　　queuenode *rear;
　　}LinkQueue; //只设一个指向队尾元素的指针

　(1)置空队
　　void InitQueue( LinkQueue *Q)
　　　{ //置空队：就是使头结点成为队尾元素
　　　　QueueNode *s;
　　　　Q->rear = Q->rear->next;//将队尾指针指向头结点
　　　　while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队
　　　　　{s=Q->rear->next;
　　　　　　Q->rear->next=s->next;
　　　　　　free(s);
　　　　　}//回收结点空间
　　　}

　(2)判队空 
　　int EmptyQueue( LinkQueue *Q)
　　　{ //判队空
　　　　//当头结点的next指针指向自己时为空队
　　　　return Q->rear->next->next==Q->rear->next;
　　　}

　(3)入队
　　void EnQueue( LinkQueue *Q, Datatype x)
　　　{ //入队
　　　　//也就是在尾结点处插入元素
　　　　QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点
　　　　p->data=x; p->next=Q->rear->next;//初始化新结点并链入
　　　　Q-rear->next=p; 
　　　　Q->rear=p;//将尾指针移至新结点
　　　}

　(4)出队
　　Datatype DeQueue( LinkQueue *Q)
　　　{//出队,把头结点之后的元素摘下
　　　　Datatype t;
　　　　QueueNode *p;
　　　　if(EmptyQueue( Q ))
　　　　　　Error("Queue underflow");
　　　　p=Q->rear->next->next; //p指向将要摘下的结点
　　　　x=p->data; //保存结点中数据
　　　　if (p==Q->rear)
　　　　　{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点
　　　　　　Q->rear = Q->rear->next; Q->rear->next=p->next;}
　　　　else 
　　　　　　Q->rear->next->next=p->next;//摘下结点p
　　　　free(p);//释放被删结点
　　　　return x;
24.已知两个单链表中的元素递增有序，试写一算法将这两个有序表归并成一个递增有序的单链表。算法应利用原有的链表结点空间。

答： 
  typedef struct node{
　　　KeyType key; //关键字域
　　　OtherInfoType info; //其它信息域，
　　　struct node * next; //链表中指针域
　　}RecNode; //记录结点类型

　typedef RecNode * LinkList ; //单链表用LinkList表示

　void mergesort(LinkList la,LinkList lb,LinkList lc)
　　{RecNode *p,*q,*s,*r;
　　　lc=la;
　　　p=la;//p是la表扫描指针，指向待比较结点的前一位置
　　　q=lb->next;//q是lb表扫描指针，指向比较的结点
　　　while(p->next)&&(q)
　　　　　if (p->next->key<=q->key)
　　　　　　p=p->next;
　　　　　else {s=q;q=q->next;
　　　　　　　　s->next=p->next;p->next=s;//将s结点插入到p结点后
　　　　　　　　p=s;}
　　　if (!p->next) p->next=q;
　　　free(lb);
　　}

7.19 试分别写出求DFS和BFS生成树(或生成森林)的算法，要求打印出所有的树边。 

 

答：
　  (1)求DFS生成树
　typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
　Boolean visited[MaxVertexNum]； //访问标志向量是全局量
　void DFSTraverseTREE(ALGraph *G)
　　{ //求深度优先生成树(以邻接表表示的图G)，而以邻接矩阵表示G时，
　　　//算法完全与此相同,只要将DFSTree(G，i)改为DFSMTree(G，i)即可
　　　int i；
　　　for(i=0;i<G->n;i++)
　　　　　visited=FALSE； //标志向量初始化
　　　for(i=0;i<G->n；i++)
　　　　　if(!visited) //vi未访问过
　　　　　　　DFSTree(G，i)； //以vi为源点开始DFS搜索,求DFS生成树的边
　　}//DFSTraverse

　void DFSTree(ALGraph *G，int i){ 
　　//以vi为出发点对邻接表表示的图G进行深度优先搜索,打印生成树(生成森林)的边
　　EdgeNode *p；
　　visited=TRUE； //标记vi已访问
　　p=G->adjlist.firstedge； //取vi边表的头指针
　　while(p){//依次搜索vi的邻接点vj，这里j=p->adjvex
　　　　　　　if (!visited[p->adjvex])//若vj尚未被访问
　　　　　　　　　{printf("(%c,%c)\n",G->adjlist.vertex,G->adjlist[p->adjvex].vertex) ；
　　　　　　　　　　// 打印边
　　　　　　　　　　DFSTree(g，p->adjvex);//则以Vj为出发点向纵深搜索
　　　　　　　　　}
　　　　　　　p=p->next； //找vi的下一邻接点
　　　　　　}
　}//DFS

　void DFSMTree(MGraph *G，int i)
　　{ //以vi为出发点对邻接矩阵表示的图G进行深度优先搜索,打印生成树(生成森林)的边
　　　int j；
　　　visited=TRUE；
　　　for(j=0；j<G->n；j++) //依次搜索vi的邻接点
　　　　　if(G->edges[j]==1&&!visited[j])
　　　　　　{
　　　　　　　printf("(%c,%c)\n",G->vexs,G->vexs[j]);// 打印边
　　　　　　　DFSMTree(G，j);//(vi，vj)∈E，且vj未访问过，故vj为新出发点
　　　　　　}
　　}//DFSMTree


　　(2)求BFS生成树
　typedef enum{FALSE，TRUE}Boolean；//FALSE为0，TRUE为1
　Boolean visited[MaxVertexNum]； //访问标志向量是全局量
　void BFSTraverseTREE(ALGraph *G)
　　{ //求广度优先生成树(以邻接表表示的图G)，而以邻接矩阵表示G时，
　　　//算法完全与此相同,只要将BFSTree(G，i)改为BFSMTree(G，i)即可
      int i；
      for(i=0;i<G->n;i++)
        visited=FALSE； //标志向量初始化
      for(i=0;i<G->n；i++)
　　　　if(!visited) //vi未访问过
　　　　　BFSTree(G，i)； //以vi为源点开始BFS搜索,求BFS生成树的边
　　}//BFSTraverse

　void BFSTree(ALGraph*G，int k)
　　　{// 以vk为源点对用邻接表表示的图G进行广度优先搜索,并求出BFS生成树边
　　　　　int i；
　　　　　CirQueue Q； //须将队列定义中DataType改为int
　　　　　EdgeNode *p；
　　　　　InitQueue(&Q)；//队列初始化
　　　　　visited[k]=TRUE； 
　　　　　EnQueue(&Q，k)；//vk已访问，将其人队。（实际上是将其序号人队）
　　　　　while(!QueueEmpty(&Q)){//队非空则执行
　　　　　　　i=DeQueue(&Q)； //相当于vi出队
　　　　　　　p=G->adjlist.firstedge； //取vi的边表头指针
　　　　　　　while(p){//依次搜索vi的邻接点vj(令p->adjvex=j)
　　　　　　　　　if(!visited[p->adivex]){ //若vj未访问过
　　　　　　　　　　　printf("(%c,%c)\n"，G->adjlist.vertex,G->adjlist[p->adjvex].vertex)；
　　　　　　　　　　　　//打印边
　　　　　　　　　　　visited[P->adjvex]=TRUE； 
　　　　　　　　　　　EnQueue(&Q，p->adjvex)；／／访问过的vj人队
　　　　　　　　　　}//endif
　　　　　　　　　p=p->next；//找vi的下一邻接点
　　　　　　　　}//endwhile
　　　　　　}//endwhile
　　　}//end of BFSTree 

　void BFSMTree(MGraph *G，int k)
　　{// 以vk为源点对用邻接矩阵表示的图G进行广度优先搜索,并求出BFS生成树边
　　　　int i，j；　
　　　　CirQueue Q；
        InitQueue(&Q)；
　　　　visited[k]=TRUE；
　　　　EnQueue(&Q，k)；
　　　　while(!QueueEmpty(&Q)){
　　　　　　i=DeQueue(&Q)； //vi出队
　　　　　　for(j=0;j<G->n;j++)//依次搜索vi的邻接点vj
　　　　　　　　if(G->edges[j]==1&&!visited[j]){//vi未访问
　　　　　　　　　　printf("(%c,%c)\n"，G->vexs,G->vexs[j])；//打印边
　　　　　　　　　　visited[j]=TRUE；
　　　　　　　　　　EnQueue(&Q，j)；//访问过的vj人队
　　　　　　　　　}
　　　　　}//endwhile
　　}//BFSMTree
26试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。

解：
　　只要对待判定的二叉树中的结点按层遍历并判断即可。在该算法中要用到队列保存已遍历的结点指针。

　typedef BinTNode *DataType;//循环队列中元素为二叉树结点指针 
　int BinSortStree(BinTree T)
　　{ 
　　　CirQueue Q;
　　　BinTNode *p;
　　　if (!T) return 1;//空树为二叉排序树
　　　InitQueue(&Q);
　　　EnQueue(&Q,T);
　　　while(!QueueEmpty(&Q))
　　　　{
　　　　　p=DeQueue(&Q);
　　　　　if (p->lchild)
　　　　　　if (p->data<p->lchild->data) return -1;//不是二叉排序树
　　　　　　else EnQueue(&Q,p->lchild);
　　　　　if (p->rchild)
　　　　　　if (p->data>p->rchild->data) return -1;//不是二叉排序树
　　　　　　else EnQueue(&Q,p->rchild);
　　　　}
　　　return 1;//是二叉排序树　

.27 以二叉链表为存储结构，分别写出在二叉树中查找值为x的结点及求x所在结点在树中层数的算法。 

解：
　　根据上几题的算法可以得出本题的算法如下：
　#define M 10 //假设二叉树最多的层数
　BinTree SearchBTree(BinTree *T,DataType x)
　　{//以前序遍历算法查找值为x的结点
　　　if(*T)
　　　　{
　　　　　if((*T)->data==x )return *T;
　　　　　SearchBTree(&(*T)->lchild,x);
　　　　　SearchBTree(&(*T)->rchild,x);
　　　　}
　　}int InLevel(BinTree T,DataType x)
　　{
　　int static l=0;//设一静态变量保存层数
　　　if(T)
　　　　{ 
　　　　　if(l==0)//若是访问根结点
　　　　　　{ 
　　　　　　　l++;//第1层
　　　　　　　if(T->data==x)return l;
　　　　　　　if(T->lchild||T->rchild) 
　　　　　　　　l++;//若根有子树，则层数加1
　　　　　　}
　　　　　else
　　　　　　{ //访问子树结点
　　　　　　　if(T->data==x)return l;
　　　　　　　if(T->lchild||T->rchild) 
　　　　　　　　l++;//若该结点有子树，则层数加1
　　　　　　　else return 0;
　　　　　　}
　　　　　InLevel(T->lchild,x);//遍历左子树
　　　　　InLevel(T->rchild,x);//遍历右子树

6.25 以二叉链表为存储结构， 写一算法交换各结点的左右子树。 

答：
　　要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。

　void ChangeBinTree(BinTree *T)
　　{ //交换子树
　　　if(*T) 
　　　　{ //这里以指针为参数使得交换在实参的结点上进行后序遍历
　　　　　BinTree temp;
　　　　　ChangeBinTree(&(*T)->lchild);
　　　　　ChangeBinTree(&(*T)->rchild);
　　　　　temp=(*T)->lchild;
　　　　　(*T)->lchild=(*T)->rchild;
　　　　　(*T)->rchild=temp;
　　　　6.25 以二叉链表为存储结构， 写一算法交换各结点的左右子树。 

答：
　　要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。

　void ChangeBinTree(BinTree *T)
　　{ //交换子树
　　　if(*T) 
　　　　{ //这里以指针为参数使得交换在实参的结点上进行后序遍历
　　　　　BinTree temp;
　　　　　ChangeBinTree(&(*T)->lchild);
　　　　　ChangeBinTree(&(*T)->rchild);
　　　　　temp=(*T)->lchild;
　　　　　(*T)->lchild=(*T)->rchild;
　　　　　(*T)->rchild=temp;
　　　　

.29 以二叉链表为存储结构，一算法对二叉树进行层次遍历(层次遍历的定义见6.13).提示：应使用队列来保存各层的结点。 
答： 
　#define M 100 //假设结点数最多为100
　typedef char DataType;//队列结点值类型
　typedef struct//定义一个队列
　　{
　　　int front;
　　　int rear;
　　　int count;
　　　DataType data[M];
　　}QBTree;

　static QBTree Q;//设一全局静态变量保存遍历结果
　void Levelorder(BinTree T)
　　{//层次遍历
　　　if(T)
　　　　{
　　　　　if(QueueEmpty(&Q))
　　　　　　{ //根结点及子树结点入队
　　　　　　　EnQueue(&Q,T->data);
　　　　　　　if(T->lchild)
　　　　　　　　EnQueue(&Q,T->lchild->data);
　　　　　　　if(T->rchild)
　　　　　　　　EnQueue(&Q,T->rchild->data);
　　　　　　}
　　　　　else
　　　　　　{ //子树结点入队
　　　　　　　if(T->lchild)
　　　　　　　　EnQueue(&Q,T->lchild->data);
　　　　　　　if(T->rchild)
　　　　　　　　EnQueue(&Q,T->rchild->data);
　　　　　　}
　　　　　Levelorder(T->lchild);//遍历左子树
　　　　　Levelorder(T->rchild);//遍历右子树
2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。
解：
　　根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。
　　算法如下：
　　LinkList MergeSort ( LinkList A , LinkList B )
　　　{// 归并两个带头结点的递增有序表为一个带头结点递减有序表
　　　　ListNode *pa , *pb , *q , *C ;
　　　　pa=A->next;//pa指向A表开始结点
　　　　C=A;C->next=NULL;//取A表的表头建立空的C表
　　　　pb=B->next;//pb指向B表开始结点
　　　　free(B);//回收B表的头结点空间
　　　　while ( pa && pb)
　　　　　{
　　　　　　if ( pb->data <= pa->data )
　　　　　　　{ // 当B中的元素小于等于A中当前元素时，将pa表的开始结点摘下
　　　　　　　　q=pa;pa=pa->next;
　　　　　　　}
　　　　　　else
　　　　　　　{// 当B中的元素大于A中当前元素时，将pb表的开始结点摘下
　　　　　　　　q=pb;pb=pb->next;}
　　　　　　q->next=C->next;C->next=q;//将摘下的结点q作为开始结点插入C表
　　　　　}
　　　　//若pa表非空，则处理pa表
　　　　while(pa){
　　　　　　q=pa;pa=pa->next;
　　　　　　q->next=C->next;C->next=q;}
　　　　//若pb表非空，则处理pb表
　　　　while(pb){
　　　　　　q=pb;pa=pb->next;
　　　　　　q->next=C->next;C->next=q;}
　　　　return(C);
　　　} 
　　该算法的时间复杂度分析如下：
　　算法中有三个while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间复杂度O(m+n)
6.23 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。
解：
　(1)求结点数的递归定义为：
　　若为空树，结点数为0
　　若只有根结点，则结点数为1；
　　否则，结点数为根结点的左子树结点数+右子树结点数+1
　(2)求叶子数的递归定义为：
　　若为空树，叶子数为0
　　若只有根结点，则叶子数为1；
　　否则，叶子数为根结点的左子树叶子数+右子树叶子数
　typedef char DataType;//定义DataType类型
　typedef struct node{
　　　　DataType data;
　　　　struct node *lchild, *rchild;//左右孩子子树
　　}BinTNode; //结点类型
　typedef BinTNode *BinTree ;//二叉树类型
　int Node(BinTree T)
　　{//算结点数
　　　if(T)
　　　　if (T->lchild==NULL)&&(T->rchild==NULL)
　　　　　return 1;
　　　　else return Node(T->lchild)+Node(T->rchild)+1;
　　　else return 0;
　　}
　int Leaf(BinTree T)
　　{ //算叶子数
　　　if(T)
　　　　if (T->lchild==NULL)&&(T->rchild==NULL)
　　　　　return 1;
　　　　else return Leaf(T->lchild)+Node(T->rchild);
　　　else return 0;
　　}  
13. 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。
解：
    重写的算法如下：
  void InsertSort(SeqList R)
　　{//对顺序表中记录R[0..n-1]按递增序进行插入排序
　　　int i,j;
　　　for(i=n-2;i>=0;i--) //在有序区中依次插入R[n-2]..R[0]
　　　　if(R.key>R[i+1].key) //若不是这样则R原位不动
　　　　　{ 
　　　　　　R[n]=R;j=i+1; //R[n]是哨兵
　　　　　　do{ //从左向右在有序区中查找插入位置
　　　　　　　　R[j-1]=R[j]; //将关键字小于R.key的记录向右移
　　　　　　　　j++;
　　　　　　　}while(R[j].key<R[n].key]);
　　　　　　R[j-1]=R[n]; //将R插入到正确位置上
　　　　　}//endif
　　}//InsertSort.
14.以单链表作为存储结构实现直接插入排序算法。 
解：
　#define int KeyType //定义KeyType 为int型
　typedef struct node{
　　　KeyType key; //关键字域
　　　OtherInfoType info; //其它信息域，
　　　struct node * next; //链表中指针域
　　}RecNode; //记录结点类型
　typedef RecNode * LinkList ; //单链表用LinkList表示
　void InsertSort(LinkList head)
　　{//链式存储结构的直接插入排序算法,head是带头结点的单链表
　　　RecNode *p,*q,*s; 
　　　if ((head->next)&&(head->next->next))//当表中含有结点数大于1
　　　　{
　　　　　p=head->next->next;//p指向第二个节点
　　　　　head->next=NULL;
　　　　　q=head;//指向插入位置的前驱节点
　　　　　while(p)&&(q->next)&&(p->key<q->next->key)
　　　　　　q=q->next;
　　　　　if (p)
　　　　　　{s=p;p=p->next;// 将要插入结点摘下
　　　　　　　s->next=q->next;//插入合适位置：q结点后
　　　　　　　q->next=s;
　　　　　　}
　　　　}
　　}
查看该用户更多文章>>