数据结构有序表的归并.doc

1. 有序表的归并#include#includetypedef struct List int 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=(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,&length); 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 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(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!=0) if(p-date date ) head3=Insert(head3,p-date); p=p-next; flag1=IsLast(p); else head3=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); fclose(fp);2. 数据转换（用栈实现将十进制转换为二进制）#include#includetypedef struct stack int 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 flag; 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) return 1; else return 0; /判断栈是否为空，若空则返回1，否则返回0 stack *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 number:); scanf(%d,&n); 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 btree char date; struct btree *plchild; struct btree *prchild;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(qfront0 | qfront=qrear ) return 1; else return 0; / 判断队列是否为空void MakeEmpty() int i; qfront=-1;qrear=0; for(i=0;i=10) qrear=qrear%9; / 入队/没有考虑到队列满的情况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; /层序遍历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; scanf(%c,&ch); 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 *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(topNode); 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(child=n) if(childn & achildachild) break; else achild/2=achild; child=child*2;achild/2=rootdate; void headSort(int a,int n) int i,j; int temp; for(i=n/2;i0;i-) adjust(a,i,n); for(i=n-1;i0;i-) temp=ai+1,ai+1=a1,a1=temp; adjust(a,1,i); int main() int i;int a11=-1,26,5,77,1,61,11,59,15,48,19; headSort(a,10); for(i=1;i11;i+) printf(%d ,ai);6.归并排序（非递归）#includevoid MergeSort(int list,int n);void merge_pass(int list,int sorted,int n,int length);void merge(int list,int sorted,int i,int m,int n);void MergeSort(int list,int n) int length; int extra10; length=1; while(lengthn) merge_pass(list,extra,n,length); length=length*2; merge_pass(extra,list,n,length); length=length*2; void merge_pass(int list,int sorted,int n,int length) int iStartPos,j; for(iStartPos=0;iStartPosn-2*length;iStartPos=iStartPos+2*length) merge(list,sorted,iStartPos,iStartPos+length-1,iStartPos+2*length-1); if(iStartPos+lengthn) merge(list,sorted,iStartPos,iStartPos+length-1,n-1); else for(j=iStartPos;jn;j+) sortedj=listj; void merge(int list,int sorted,int i,int m,int n) int j,k,t; j=m+1; k=i; while( (i=m) & (j=n) ) if(listim) for(t=j;t=n;t+) sortedk+=listt; else for(t=i;t=m;t+) sortedk+=listt; int main() int i; int list10=26,5,77,1,61,11,59,15,48,19; MergeSort(list,10); for(i=0;i10;i+) printf(%5d,listi); 7.快速排序 #includevoid quickSort(int a,int left,int right) int pivot,i,j; int temp; if(leftright) i=left;j=right+1; pivot=aleft; do do i+;while(aipivot); if(i j) /交换i,j位置数据元素temp = ai;ai = aj;aj = temp; while(ij); aleft=aj; aj=pivot; for(i=0;i10;i+) printf(%5d,ai); printf(n); quickSort(a,left,j-1); quickSort(a,j+1,right); int main() int list=26,5,37,1,61,11,59,15,48,19; quickSort(list,0,9); 8.图的深度优先遍历+9.图的广度优先遍历 #include#includetypedef struct Gnode int i; Gnode *next;Gnode;Gnode *Adlist20; /邻接链表int cost2020; /costij,存放边的权值int visit20; /visiti=0,代表i节点未被访问int distance20;/ 最短路径typedef struct queue /队列元素 int t; struct queue *next;queue;queue *front,*rear; /队列头与队列尾void addq(int i) queue *q,*p; p=NULL; q=(queue *)malloc(sizeof(queue); q-t=i; q-next=NULL; if(front=NULL) front=rear=q; else p=front;while(p!=rear) p=p-next;p-next=q;rear=q; / 入队int deleteq() queue *q; q=front; if(front=NULL) printf(queue is empty n); return -1; front=front-next; return q-t; /出队void initial(int n) for(int i=0;in;i+) Adlisti=NULL; for(int j=0;jn;j+) costij=1000;/初始化邻接链表void creat(FILE *fp,int m) int v,e,p; Gnode *t,*q; for(int i=0;ii=e; q-next=NULL; if(Adlistv=NULL) Adlistv=q; else t=Adlistv; while(t-next!=NULL) t=t-next;t-next=q; costve=p; /构建邻接链表，和costij;void outputg(FILE *fp,int n) Gnode *t; for(int i