《数据结构核心算法大全》由会员分享，可在线阅读，更多相关《数据结构核心算法大全（196页珍藏版）》请在金锄头文库上搜索。
1、1线性表单链表逆置/已知单链表 H，写一个算法将其逆置/H-head-32-63-18-50-26-NULL#include #include typedef struct nodechar data; /data 为结点数据信息struct node *next; /next 为指向后继结点的指针LNode; /单链表数据类型LNode *CreateLinkList() /生成单链表LNode *head,*p,*q;char x;head=(LNode *)malloc(sizeof(LNode); /生成头结点head-next=NULL;p=head;q=p; /q 始终指向链尾结点
2、printf(“Input any char string:n“);scanf(“%c“,while(x!=n)p=(LNode *)malloc(sizeof(LNode);2p-data=x;p-next=NULL;q-next=p; /在链尾插入q=p;scanf(“%c“,return head; /返回指向单链表的头指针headvoid Convert(LNode *H) /单链表的逆置LNode *p,*q;p=H-next; /p 指向剩余结点链表的第一个数据结点H-next=NULL; /新链表 H 初始为空while(p!=NULL)q=p; /从剩余结点链表中取出第一个结点
3、p=p-next; /p 继续指向剩余结点链表新的第一个数据结点q-next=H-next; /将取出的结点*q 插入到新链表 H 的链首H-next=q;void main()LNode *A,*p;3A=CreateLinkList(); /生成单链表 AConvert(A); /单链表逆置p=A-next; /输出逆置后的单链表while(p!=NULL)printf(“%c“,p-data);p=p-next;printf(“n“);双链表合并/对两个元素递增有序的单链表 A 和 B，编写算法将 A、B 合并成一个按元素递减有序的单链表 C，要求算法使用 AB 中原有的结点，不允许增加
4、新结点#include #include typedef struct nodeint data; /data 为结点的数据信息struct node *next; /next 为指向后继结点的指针LNode;LNode *CreateLinkList() /生成单链表LNode *head,*p,*q;int i,n;head=(LNode *)malloc(sizeof(LNode); /生成头结点4head-next=NULL;p=head;q=p; /指针 q 始终指向链尾结点printf(“Input length of list:n“);scanf(“%d“, /读入节点数据pri
5、ntf(“Input data of list:n“);for(i=1;idata);p-next=NULL;q-next=p; /在链尾插入q=p;return head; /返回单链表的头指针headvoid Merge(LNode *A,LNode *B,LNode *C) /将升序链表 AB 合并成降序链表 CLNode *p,*q,*s;p=A-next; /p 始终指向链表 A 的第一个未比较的数据结点q=B-next; /q 时钟指向链表 B 的第一个未比较的数据节点*C=A; /生成的链表的*C 的头结点(*C)-next=NULL;free(B); /回收链表 B 的头结点空
6、间5while(p!=NULLp=p-next;elses=q;q=q-next;s-next=(*C)-next; /用头插法将结点*S 插到链表*C 的头结点之后(*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;6void print(LNode *p) /输出单链表p=p-next;while(p!=NULL)printf(“%4d“,p-data);p=
7、p-next;printf(“n“);void main()LNode *A,*B,*C;printf(“Input data of list:n“);A=CreateLinkList(); /生成单链表 Aprintf(“Output list A:n“);print(A); /输出单链表Aprintf(“Input data of B:n“);B=CreateLinkList();printf(“Output list of B:n“);print(B);printf(“Make list C:n“);Merge(A,B, /将升序链表 A、B 合并成降序链表 Cprintf(“Outpu
8、t list of C:n“);7print(C);静态链表#include #include #define MAXSIZE 30typedef structchar data; /data 为结点数据信息int cursor; /cursor 标示直接后继结点SNode;void InsertList(SNode L,int i,char x) /在静态链表中插入元素int j,j1,j2,k;j=L0.cursor; /j 指向第一个数据结点if(i=1) /作为第一个数据结点插入if(j=0) /静态链表为空L1.data=x; /将 x 放入结点 L1中L0.cursor=1; /头指针 cursor 指向这个新插入的结点L1.cursor=0; /置链尾标示else8k=j+1;while(k!=j) /在数组中循环查找存放 x 的位置if(Lk.cursor=-1) /找到空位置break;elsek=(k+1)%MAXSIZE; /否则查找下一个位置if(k!=j) /在数组中查找一个空位子来存放 xLk.data=x;Lk.cursor=L0.cursor; /将其插入到静态链表表头L0.cursor=k;elseprintf
