《数据结构代码.docx》由会员分享，可在线阅读，更多相关《数据结构代码.docx（27页珍藏版）》请在课桌文档上搜索。
1、数据结构代码P2,例2-1voidunion(List&La,UstLb)1.aJen=ListLength(La);LbJen=UStLerIgth(Lb);for(i=l;i=Lb_len;i+)GetElem(Lb,i,e);if(!LocateElem(La,e,equal)UStIrlSert(La,+Lajen,e);P21例2-2,将voidMergeLiSt(L运tLa,ListLb,List&Lc)InitList(Lc);i=j=l;k=O;1.aen=ListLength(La);Lb_len=ListLength(Lb);while(i=La_Len)&(j=Lb_le
2、n)GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;elseListInsert(Lc,+k,bj);+jwhile(i=LaJen)GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j=Lb_len)GetElem(Lb,i+,bj);ListInsert(Lc,+k,bj);P22,线性表的依次存储结构#defineLIST_INIT_SIZE1OO#defineLISTINCREMENT10typedefstructElemType*elem;*线性表占用的数组空
3、间*/intlength;intlistsize;SqList;初始化操作StatusIniL运t_Sq(SqLiSt&L)1.elem=(ElemTypeA)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);1.Iength=O;1.listsize=LISTJNIT,SIZE;returnOK;P24,在依次表里插入一个元素StatusL运HnserJsq(SqLiSt&L,inti,ElemTypee)if(i=L.length+l)returnERROR;if(L.length=L.listsize)new
4、base=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizf(ElemType);if(!newbase)exit(OVERFLOW);1.elem=newbase;1.listsize+=LISTINCREMENT;q=&(L.elemi-l);for(p=&(L.elemL.length-l);p=q;p)*(p+l)=*p;*q=e;+L.length;returnOK；P24,在依次表里删除一个元素StatusLiStDelete_Sq(SqL运t&L,inti,ElemType&e)if(iL.length)return
5、ERROR;p=&(L.elemi-l);e=*p;q=L.elemL.length-1;for(+p;p=q;+p)*(p-l)=*p;L.length;returnOK;P25,在依次表里查找一个元素intLocatElem_Sq(SqListLjElemTypee,Status(*compare)(ElemType,ElemType)i=l；p=L.elem;while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length)returni;elsereturn0;P26,依次表的合并voidMergeL运t_Sq(SqL运tLa,SqListLb,S
6、qList&Lc)pa=La.elem;pb=Lb.elem;1.c.Iistsize=Lc.Iength=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTpe);if(!Lc.elem)exit(OVERFLOW);paast=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pajast&pb=pbjast)if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pajast)*pc+=*pa+;w
7、hile(pbnext;j=l；while(p&jnext;+j；if(!pIIji)returnERROR;e=p-data;returnok;P29,在单链表中插入一个元素StatusListInsert_L(LinkList&L,inti,ElmeTypee)p=L;j=O;while(p&jnext;+j；if(!pIIji-l)returnERROR;s=(LinkList)malloc(sizf(LNode);s-data=e;s-next=p-next;p-next=s;returnOK;P30,在单链表中删除一个元素StatusListDelete_L(LinkList&L,i
8、nti,Elemtype&e)p=L;j=O;while(p-next&jnext;+j;if(!(p-next)ji-l)returnERROR;q=p-next;p-next=q-next;e=q-data;free(q);returnOK;P30,建立单链表voidCreateList_L(LinkList&L,intn)1.=(Linklist)malloc(sizeof(Lnode);1.-next=NULL;for(i=n;i0;i)p=(LinkList)malloc(sizeof(Lnode);scanf(&p-data);p-next=L-next;1.-next=p;P31
9、,合并单链表voidmergelist_L(LinkList&La,LinkList&Lb,LinkLiSt&Lc)pa=La-next;pb=Lb-next;1.c=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;)else(pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);P3线性表的静态单链表存储结构#defineMAXSIZE1000typedefstructElemTypedata;intcur;component,SlinkListMAXSIZE;P3
10、2,定位函数intLocateElem_SL(SlinkLists,ElemTypee)i=sO.cur;while(i&si.data!=e)i=si.cur;returni;voidIniteSpace_SL(SlinkList&space)for(i=0;i=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCRE
11、MENT;*S.top+=e;returnOK;StatusPop(SqStack&S,SelemType&e)if(S.top=S.base)returnERROR;e=*S.top;returnOK;P48,转换为8进制voidconversion()InitStack(三);SCanf(“d”，&N);while(N)(Push(s,N%8);N=N/8;while(!StackEmpty(s)Pop(S,e);Printf(%d,e);P55,移动圆盘voidhanoi(intn,charx,chary,charz)*将塔座X上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到塔
12、座Z,Y可用作协助塔座*/if(n=l)move(x,l,z);/*将编号为1的圆盘从X移动Z*/else(hanoi(n-l,x,z,y);/*将X上编号为1至II-I的圆盘移到Y,Z作协助塔*/move(x,n,z);/*将编号为n的圆盘从X移到Z*/hanoi(n-l,y,x,z);/*将Y上编号为1至n-1的圆盘移动到Z,X作协助塔*/P6链式队列的定义# defineTRUE1# defineFALSE0typedefstructQNodeQElemTypedata;structQNode*next;QNode,*QueuePtr;typedefstruct(QueuePtrfron
13、t;QueuePtrrear;LinkQueue;P62,初始化StatusInitQueue(LinkQueue&Q)Q.front=Q.rear=(Queueptr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;returnOK;销毁队列StatusDestroyQueue(LinkQueue&Q)while(Q.front)Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;)returnOK;入队操彳StatusEnQueue(LinkQueue&Q,Qe
14、lemTypee)p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(OVERFLOW);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;StatusDeQueue(LinkQueue&Q,QelemType&e)if(Q.front=Q.rear)returnERROR;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);returnOK;P64,循环对列定义#defineMAXQSIZE100
15、*队列的最大长度*/typedefstructQElemType*base;/*队列的元素空间*/i11tfront;/*头指针指示器*i11trear;/*尾指针指示器*/SqQueue;初始化操作StatusInitQueue(SqQueue&Q)Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;)入队操作StatusEnQueue(SqQueue&Q,QElemTypee)if(Q.rear+1)%MAXQSIZE=Q.front
16、)returnERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;)出队操作StatusDeQueue(SqQueue&Q,QElemType&e)if(Q.front=Q.rear)returnERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;returnOK;)求队列1度intQueueLength(SqQueueQ)return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;P93/数组的依次存储表示#include# defineMAX_ARRAY_D
17、IM8typedefstructELemType*base;/数组元素基址i11tdim;/数组维数i11t*bounds;/数组维数基址i11t*constants;/数组映像函数常量基址Array;P98,三元数组依次表存储# defineMAXSIZE12500typedefstructinti,j；ElemTypee;Triple;typedefunionTripledataMAXSIZE+1;intmu,nu,tu;TSMatrix;P99,矩阵转置StatusTransposeSMatrix(TSMatrixM,TSMatrix&T)T.mu=M.nu;T.nu=M.mu;T.tu
18、=M.tu;if(T.tu)q=i;for(col=1;col=M.nu;+col)for(p=1;p=M.tu;+p)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;q;returnOK;/TransposeSMatrixStatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T)采纳三元组依次表存储表示，求稀疏矩阵M的转置矩阵ToT.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=l;col=M.nu;col+
19、)numcol=0;for(t=1;t=M.nu;+t)+numM.datat.j;/求M中每一列含非零元个数。coptl=l;/求第col列中第一个非零元在b.data中的序号for(col=2;col=M.nu;+col)cpotcol=cpotcol-l+numcol-l;for(p=1;pdata)5 if(PreOrderTraverse(T-lchild,ViSit)6 if(PreOrderTraverse(T-rchild,Visit)returnOK;returnERROR;9elsereturnOK;10StatusInOrderTraverse(BitreeT,Statu
20、s(*Visit)(TelemType1(2 if(T)3 (4 if(InOrderTraverse(T-lchild,Visit)5 if(V运it(T-data)6 if(InOrderTraverse(T-rchild,Visit)returnOK;7 returnERROR;8 9 elsereturnOK;10)P131,中序遍历二叉树StatusInOrderTraverse(BiTreeT,Status(*Visit)(TelemTypee)InitStack(S);Push(S,T);While(!StackEmpty(三)while(GetTop(S,p)&p)Push(S
21、,p-lchild);Pop(S,p);if(!StackEmpty(三)(Pop(S,p);if(!Visit(p-data)returnERROR;Push(S,p-rchild);if/WhilereturnOK;/InOrderTraverseStatusInrderTraverse(BiTreeT,Status(*Visit)(TelemTypee)(InitStack(S);p=T;While(pII!StackEmpty(三)if(p)Push(S,p);p=p-lchild;else(Pop(S,p);if(!Visit(p-data)returnERROR;p=p-rchil
22、d;)returnOK;voidPreOrder(BiTreeroot)*先序遍历输出二叉树中的叶了结点，root为指向二叉树根结点的指针7if(root!=NULL)if(root-LChild=NULL&root-RChild=NULL)printf(root-data);*输出叶子结点*/Prerder(root-LChild);*先序遍历左子树*/Prerder(root-RChild);/*先序遍历右子树*/统计叶子结点数目1.eafCount是保存叶子结点数目的全局变量，调用之前初始化值为。7voidleaf(BiTreeroot)(if(root!=NULL)(leaf(root
23、-LChild);leaf(root-RChild);if(root-LChild=NULL&root-RChild=NULL)1.eafCount+;*采纳递归算法，假如是空树，返回0;假如只仃一个结点，返回1;否则为左右子树的叶子结点数之和7intleaf(BiTreeroot)intLeafCount;if(root=NULL)1.eafCount=0;elseif(root-lchild=NULL)&(root-rchild=NULL)elseLeafCount = 1;LeafCount=Ieaf(root-lchild)leaf(root-rchild);*叶子数为左右子树的叶子数
24、目之和*/returnLeafCount;)Pl3建立二叉链表方式存储的二叉树StatusCreateBiTree(BiTree&T)scanf(&ch);if(ch=三,)T=NULL;else(if(!(T=(BiTNode*)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);returnOK;intPostTreeDepth(BiTreebt)后序遍历求二义树的1L算法7inthl,hr,max;if(bt!=NULL)hl=PostTreeDepth(
25、bt-LChild);*求左子树的深度*/hr=PostTreeDepth(bt-RChild);/*求右子树的深度*/max=hlhr?hl:hr;/*得到左、右子树深度较大者*/return(max+l);/*返回树的深度*/elsereturn(O);/*假如是空树，则返回0*/voidPrintTree(Bitreeroot,intnLayer),.)i二叉树*/if(root=NULL)return;PrintTree(root-rchild,nLayer+1);for(inti=0;idata);PrintTree(root-lchild,nLayerl);P135双亲表示法的形式
26、说明如下#defineMAX_TREE_SIZE100typedefstructPTNodeTelemTypedata;intparent;PTNode;typedefstruct(PTNodenodesMAX_TREE_SIZE;intr,n;Ptree;孩子表示法typedefstructCTNodeintchild;structCTNode*next;*ChildPtr;typedefstructTelemTypedata;ChildPtrfirstchild;CTBox;typedefstructCTBoxnodesMAX_TREE_SIZE;intn,r;Ctree;孩子兄弟表示法的类型定义如FtypedefstructCSNodeElemTypedata;structCSNode*firstchild,*nextsibling;CSNode,*CSTree;
