数据结构算法实现

/*algo2-1.c实现算法2.1的程序*/#includec1.htypedefintElemType;#includec2-1.h/*采用线性表的动态分配顺序存储结构*/#includebo2-1.c/*可以使用bo2-1.cpp中的基本操作*/#includefunc2-3.c/*包括equal()、comp()、print()、print2()和print1()函数*/#includebo2-1.c/*可以使用bo2-1.c中的基本操作*/voidUnion(SqList*La,SqListLb)/*算法2.1*/{/*将所有在线性表Lb中但不在La中的数据元素插入到La中*/ElemTypee;intLa_len,Lb_len;inti;La_len=ListLength(*La);/*求线性表的长度*/Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i++){GetElem(Lb,i,&e);/*取Lb中第i个数据元素赋给e*/if(!LocateElem(*La,e,equal))/*La中不存在和e相同的元素，则插入之*/ListInsert(La,++La_len,e);}}voidmain(){SqListLa,Lb;intj;InitList(&La);/*创建空表La。如不成功，则会退出程序的运行*/for(j=1;j=5;j++)/*在表La中插入5个元素，依次为1、2、3、4、5*/ListInsert(&La,j,j);printf(La=);/*输出表La的内容*/ListTraverse(La,print1);InitList(&Lb);/*创建空表Lb*/for(j=1;j=5;j++)/*在表Lb中插入5个元素，依次为2、4、6、8、10*/ListInsert(&Lb,j,2*j);printf(Lb=);/*输出表Lb的内容*/ListTraverse(Lb,print1);Union(&La,Lb);/*调用Union()，将Lb中满足条件的元素插入La*/printf(newLa=);/*输出新表La的内容*/ListTraverse(La,print1);}/*algo1-1.c计算1-1/x+1/x*x…*/#includestdio.h#includesys/timeb.hvoidmain(){structtimebt1,t2;longt;doublex,sum=1,sum1;inti,j,n;printf(请输入xn：);scanf(%lf%d,&x,&n);ftime(&t1);/*求得当前时间*/for(i=1;i=n;i++){sum1=1;for(j=1;j=i;j++)sum1=-sum1/x;sum+=sum1;}ftime(&t2);/*求得当前时间*/t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);/*计算时间差*/printf(sum=%lf用时%ld毫秒\n,sum,t);}/*algo1-2.cpp计算1-1/x+1/x*x…的更快捷的算法*/#includestdio.h#includesys/timeb.hvoidmain(){structtimebt1,t2;longt=0;doublex,sum1=1,sum=1;inti,n;printf(请输入xn:);scanf(%lf%d,&x,&n);ftime(&t1);/*求得当前时间*/for(i=1;i=n;i++){sum1=-sum1/x;sum+=sum1;}ftime(&t2);/*求得当前时间*/t=(t2.time-t1.time)*1000+(t2.millitm-t1.millitm);/*计算时间差*/printf(sum=%lf用时%ld毫秒\n,sum,t);}/*algo1-3.c用函数指针代替C++的引用参数*/#includestdio.hvoidfa(inta)/*在函数中改变a，将不会带回主调函数(主调函数中的a仍是原值)*/{a++;printf(在函数fa中：a=%d\n,a);}voidfb(int*a)/*a为指针类型，在函数中改变*a，改变后的值将带回主调函数*/{(*a)++;printf(在函数fb中：*a=%d\n,*a);}voidmain(){intn=1;printf(在主程中，调用函数fa之前：n=%d\n,n);fa(n);printf(在主程中，调用函数fa之后,调用函数fb之前：n=%d\n,n);fb(&n);/*实参为n的地址*/printf(在主程中，调用函数fb之后：n=%d\n,n);}/*algo1-4.cpp说明exit()函数作用的程序*/#includec1.hinta(inti){if(i==1){printf(退出程序的运行\n);exit(1);}returni;}voidmain(){inti;printf(请输入i：);scanf(%d,&i);printf(a(i)=%d\n,a(i));}/*algo2-3.c实现算法2.7的程序*/#includec1.htypedefintElemType;#includec2-1.h#includebo2-1.c#includefunc2-3.c/*包括equal()、comp()、print()、print2()和print1()函数*/voidMergeList(SqListLa,SqListLb,SqList*Lc)/*算法2.7*/{/*已知顺序线性表La和Lb的元素按值非递减排列。*//*归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列*/ElemType*pa,*pa_last,*pb,*pb_last,*pc;pa=La.elem;pb=Lb.elem;(*Lc).listsize=(*Lc).length=La.length+Lb.length;/*不用InitList()创建空表Lc*/pc=(*Lc).elem=(ElemType*)malloc((*Lc).listsize*sizeof(ElemType));if(!(*Lc).elem)/*存储分配失败*/exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&&pb=pb_last)/*表La和表Lb均非空*/{/*归并*/if(*pa=*pb)*pc++=*pa++;/*将pa所指单元的值赋给pc所指单元后，pa和pc分别+1(指向下一个单元)*/else*pc++=*pb++;/*将pb所指单元的值赋给pc所指单元后，pa和pc分别+1(指向下一个单元)*/}/*以下两个while循环只会有一个被执行*/while(pa=pa_last)/*表La非空且表Lb空*/*pc++=*pa++;/*插入La的剩余元素*/while(pb=pb_last)/*表Lb非空且表La空*/*pc++=*pb++;/*插入Lb的剩余元素*/}voidmain(){SqListLa,Lb,Lc;intj;InitList(&La);/*创建空表La*/for(j=1;j=5;j++)/*在表La中插入5个元素，依次为1、2、3、4、5*/ListInsert(&La,j,j);printf(La=);/*输出表La的内容*/ListTraverse(La,print1);InitList(&Lb);/*创建空表Lb*/for(j=1;j=5;j++)/*在表Lb中插入5个元素，依次为2、4、6、8、10*/ListInsert(&Lb,j,2*j);printf(Lb=);/*输出表Lb的内容*/ListTraverse(Lb,print1);MergeList(La,Lb,&Lc);/*由按非递减排列的表La、Lb得到按非递减排列的表Lc*/printf(Lc=);/*输出表Lc的内容*/ListTraverse(Lc,print1);}/*algo2-4.c修改算法2.7的第一个循环语句中的条件语句为开关语句，且当*//**pa=*pb时，只将两者中之一插入Lc。此操作的结果和算法2.1相同*/#includec1.htypedefintElemType;#includec2-1.h#includebo2-1.c#includefunc2-3.c/*包括equal()、comp()、print()、print2()和print1()函数*/voidMergeList(SqListLa,SqListLb,SqList*Lc){/*另一种合并线性表的方法(根据算法2.7下的要求修改算法2.7)，La、Lb和Lc均为按递增排列的表*/ElemType*pa,*pa_last,*pb,*pb_last,*pc;pa=La.elem;pb=Lb.elem;(*Lc).listsize=La.length+Lb.length;/*此句与算法2.7不同*/pc=(*Lc).elem=(ElemType*)malloc((*Lc).listsize*sizeof(ElemType));if(!(*Lc).elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&&pb=pb_last)/*表La和表Lb均非空*/switch(comp(*pa,*pb))/*此句与算法2.7不同*/{case0:pb++;case-1:*pc++=*pa++;break;case1:*pc++=*pb++;}while(pa=pa_last)/*表La非空且表Lb空*/*pc++=*pa++;while(pb=pb_last)/*表Lb非空且表La空*/*pc++=*pb++;(*Lc).length=pc-(*Lc).elem;/*加此句*/}voidmain(){SqListLa,Lb,Lc;intj;InitList(&La);/*创建空表La*/for(j=1;j=5;j++)/*在表La中插入5个元素，依次为1、2、3、4、5*/ListInsert(&La,j,j);printf(La=);/*输出表La的内容*/ListTraverse(La,print1);InitList(&Lb);/*创建空表Lb*/for(j=1;j=5;j++)/*在表Lb中插入5个元素，依次为2、4、6、8、10*/ListInsert(&Lb,j,2*j);printf(Lb=);/*输出表Lb的内容*/ListTraverse(Lb,print1);MergeList(La,Lb,&Lc);/*由按递增排列的表La、Lb得到按递增排列的表Lc*/printf(Lc=);/*输出表Lc的内容*/ListTraverse(Lc,print1);}/*algo2-5.c实现算法2.11、2.12的程序*/#includec1.htypedefintElemType;#includec2-2.h#includebo2-2.c#includefunc2-3.c/*包括equal()、comp()、print()、print2()和print1()函数*/voidCreateList(LinkList*L,intn)/*算法2.11*/{/*逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L*/inti;LinkListp;*L=(LinkList)malloc(sizeof(structLNode));(*L)-next=NULL;/*先建立一个带头结点的单链表*/printf(请输入%d个数据\n,n