数据结构核心算法大全.doc

《数据结构核心算法大全.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、线性表单链表逆置//已知单链表H，写一个算法将其逆置//H->head->32->63->18->50->26->NULL#include#includetypedefstructnode{chardata;//data为结点数据信息structnode*next;//next为指向后继结点的指针}LNode;//单链表数据类型LNode*CreateLinkList()//生成单链表{LNode*head,*p,*q;charx;head=(LNode*)malloc(sizeof(LNode));//生成头结点head->next=N

2、ULL;p=head;q=p;//q始终指向链尾结点printf("Inputanycharstring:");scanf("%c",&x);while(x!=''){p=(LNode*)malloc(sizeof(LNode));p->data=x;p->next=NULL;q->next=p;//在链尾插入q=p;scanf("%c",&x);}returnhead;//返回指向单链表的头指针head}voidConvert(LNode*H)//单链表的逆置{LNode*p,*q;p=H->next;//p指向剩余结点链表的第一个数据结点H->next=NULL;

3、//新链表H初始为空while(p!=NULL){q=p;//从剩余结点链表中取出第一个结点p=p->next;//p继续指向剩余结点链表新的第一个数据结点q->next=H->next;//将取出的结点*q插入到新链表H的链首H->next=q;}}voidmain(){LNode*A,*p;A=CreateLinkList();//生成单链表AConvert(A);//单链表逆置p=A->next;//输出逆置后的单链表while(p!=NULL){printf("%c",p->data);p=p->next;}printf("");}双链表合并//对两个元素递增有序

4、的单链表A和B，编写算法将A、B合并成一个按元素递减有序的单链表C，要求算法使用AB中原有的结点，不允许增加新结点#include#includetypedefstructnode{intdata;//data为结点的数据信息structnode*next;//next为指向后继结点的指针}LNode;LNode*CreateLinkList()//生成单链表{LNode*head,*p,*q;inti,n;head=(LNode*)malloc(sizeof(LNode));//生成头结点head->next=NULL;p=head;

5、q=p;//指针q始终指向链尾结点printf("Inputlengthoflist:");scanf("%d",&n);//读入节点数据printf("Inputdataoflist:");for(i=1;i<=n;i++)//生成链表的数据结点{p=(LNode*)malloc(sizeof(LNode));//申请一个节点空间scanf("%d",&p->data);p->next=NULL;q->next=p;//在链尾插入q=p;}returnhead;//返回单链表的头指针head}voidMerge(LNode*A,LNode*B,LNode**C)//

6、将升序链表AB合并成降序链表C{LNode*p,*q,*s;p=A->next;//p始终指向链表A的第一个未比较的数据结点q=B->next;//q时钟指向链表B的第一个未比较的数据节点*C=A;//生成的链表的*C的头结点(*C)->next=NULL;free(B);//回收链表B的头结点空间while(p!=NULL&&q!=NULL)//将A、B两链表中当前比较节点中值小者赋给*S{if(p->datadata){s=p;p=p->next;}else{s=q;q=q->next;}s->next=(*C)->next;//用头插法将结点*S插到链表*C的

7、头结点之后(*C)->next=s;}if(p==NULL)//如果指向链表A的指针*P为空，则使*P指向链表Bp=q;while(p!=NULL)//将*P所指链表中剩余结点依次摘下插入的链表C的链首{s=p;p=p->next;s->next=(*C)->next;(*C)->next=s;}}voidprint(LNode*p)//输出单链表{p=p->next;while(p!=NULL){printf("%4d",p->data);p=p->next;}printf("");}voidma