《数据结构有序表的归并》由会员分享，可在线阅读，更多相关《数据结构有序表的归并（10页珍藏版）》请在金锄头文库上搜索。
1、1. 有序表的归并#include#includetypedef struct Listint date;struct List *next;List;List *head1,*head2,*head3;int IsEmpty(List *p) p=p-next;if(p=NULL)return 0;else return 1;/判断是否为空，是的话返回 0;int IsLast(List *p)if(p=NULL)return 0;else return 1; /判断链表是否达到最后一个，是的话返回 0List *Insert(List *head,int n) List *p,*q;p=(
2、List *)malloc(sizeof(List);p-date=n;p-next=NULL;q=head;while(q-next!=NULL)q=q-next;q-next=p;return head; /传入一个 date 值，将这个值插入到一 head 为头的链表中，返回head List *MakeList(List *head,FILE *fp) int length;fscanf(fp,%d,int dat;List *p=NULL;List *q=NULL;q=head;for(int i=0;idate=dat;q-next=p;p-next=NULL;q=p;return
3、 head; /创建以 head 为头，长度为 length 的链表 void ShowList(List *head,FILE *fp) int flag=1;List *p;p=head;while(flag) fprintf(fp,%d ,p-date);p=p-next; flag=IsLast(p); int main() / 以下是实验要求的实现 int flag1,flag2;List *p,*q;FILE *fp;fp=fopen(input.txt,r);head1=(List *)malloc(sizeof(List);head2=(List *)malloc(sizeof
4、(List);head3=(List *)malloc(sizeof(List);head1-date=0; head1-next=NULL; head2-date=0; head2-next=NULL; head3-date=0; head3-next=NULL;head1=MakeList(head1,fp); head2=MakeList(head2,fp);fclose(fp);fp=fopen(output.txt,w);p=head1-next; q=head2-next;flag1=IsLast(p); flag2=IsLast(q);while(flag1!=0 & flag2
5、!=0) if(p-date date ) head3=Insert(head3,p-date);p=p-next;flag1=IsLast(p);elsehead3=Insert(head3,q-date);q=q-next;flag2=IsLast(q);if(flag1!=0) while(flag1) head3=Insert(head3,p-date);p=p-next;flag1=IsLast(p);else while(flag2) head3=Insert(head3,q-date);q=q-next;flag2=IsLast(q);ShowList(head3-next,fp
6、); fclose(fp);2. 数据转换（用栈实现将十进制转换为二进制）#include#includetypedef struct stackint date;struct stack *next; stack;int fulength=100,length=0;stack *top=NULL;int IsFull(int length);stack *Create();stack *Push(stack *top,stack *p);stack *Pop(stack *top);int IsEmpty(int length);stack *Create() stack *p; int f
7、lag;flag=IsFull(length);if(flag=1) printf(stack is full);return top;else p=(stack *)malloc(sizeof(stack) ; return p; /创建一个结构体，返回指向该结构体的指针 int IsFull(int length) if(length=fulength)return 1;else return 0;/设定一个常量为 fulllength，当length=fulllength 时，为满 返回 1/否则 返回 0 int IsEmpty(int length)if(length=0) retu
8、rn 1;else return 0;/判断栈是否为空，若空则返回 1，否则返回 0stack *Push(stack *p,stack *top) p-next=top;length+;return p;/将 p 指向的结构体，插入到 top 指向的结构体，返回新的 top;stack *Pop(stack *top) length-;top=top-next;return top;/在链表中删除 top 指向的结构体，并且的指针为指向该结构体的下一个结构体 int main() int n,m;stack *p;while(1)printf(Please input the decimal
9、 number:);scanf(%d,if(n0) p=Create();m=n%2;n=n/2;p-date=m;top=Push(p,top);printf(The corresponding binary version is:) ;while(top!=NULL)printf(%d,top-date);top=Pop(top); printf(n); 3. 二叉树的中序遍历（非递归方式）+4.二叉树的层序遍历（构造图）#include#includetypedef struct btreechar date;struct btree *plchild;struct btree *prc
10、hild;Btree;Btree *queue10;Btree *stack10;int qfront=-1,qrear=0;int top=0;int leaf;int lheight,rheight,height;Btree *CreateNode(char date)Btree *p;p=(Btree *)malloc(sizeof(Btree);p-date=date;p-plchild=p-prchild=NULL;return p;/创建一个结点，存放的数据为date；int qIsEmpty()if(qfront=10) qrear=qrear%9;/ 入队/没有考虑到队列满的情
11、况Btree *DeQueue() Btree *q=NULL;if(qfront=10) qfront=qfront%9; return q; /出队void levelOrder(Btree *p) Btree *ptr;ptr=p;if(ptr=NULL) return;EnQueue(ptr);for(;)ptr=DeQueue();if(ptr!=NULL) printf(%c,ptr-date);if(ptr-plchild!=NULL)EnQueue(ptr-plchild);if(ptr-prchild!=NULL)EnQueue(ptr-prchild);else break
12、;/层序遍历void Leaf(Btree *p)if(p!=NULL) if(p-plchild=NULL & p-prchild=NULL) leaf+;Leaf(p-plchild);Leaf(p-prchild);int Height(Btree *p)if(p=NULL) return 0;else lheight=Height(p-plchild);rheight=Height(p-prchild);return(lheightrheight)?(lheight+1):(rheight+1);/ 计算树的高度Btree *maketree() Btree *bt;char ch;s
13、canf(%c,if(ch=#) bt=NULL;else bt=CreateNode(ch);bt-plchild=maketree();bt-prchild=maketree(); return bt;/创建如何题目要求的树int IsFull()if(top=8) return 1;else return 0;/若栈满则返回 1，否则返回 0void Push(Btree *p)if(top=8) printf(栈满); return;stacktop+=p; / 入栈int IsEmpty()if(top=0) return 1;else return 0;/ 栈是否为空 Btree
14、*Pop() Btree *p=NULL;if(IsEmpty() return p;p=stack-top;return p;/出栈void iterinorder(Btree *topNode)Btree *p;p=topNode;for(;)for(;p!=NULL;p=p-plchild)Push(p);p=Pop();if(p=NULL) break;printf(%c,p-date);p=p-prchild;/用 iterinorder 实现中序遍历int main()Btree *topNode;topNode=maketree(); /创建题目要求的树levelOrder(to
15、pNode);printf( 此为层序遍历 (通过队列实现)n); iterinorder(topNode);printf( 此为中序遍历(iternative version 方法)n);height=Height(topNode); /计算树的高度Leaf(topNode); /计算叶子数目printf(leaf=%d nheight=%dn,leaf,height);5.堆排序算法应用（一列无序数，用堆排序进行排序）#includevoid adjust(int a,int root,int n)int child ,rootdate;int temp;rootdate=aroot;child=2*root;while(childachild) break;elseachild/2=achild;child=child*2;achild/2=rootdate; void headS
