数据结构代码

1、精选文档数据结构代码P20，例2-1void union (List &La, List Lb) La_len= ListLength (La); Lb_len= ListLength (Lb); for (i=1;i<= Lb_len;i+) GetElem (Lb,i,e); if(!LocateElem(La,e,equal) ListInsert(La,+ La_len,e); P21, 例2-2,将void MergeList(List La,List Lb,List &Lc)InitList(Lc);i=j=1;k=0;La_len=ListLength(La

2、);Lb_len=ListLength (Lb);while(i<=La_Len)&&(j<=Lb_len) GetElem(La,i,ai);GetElem(Lb,j,bj); if(ai<= bj)ListInsert(Lc,+k, ai);+i; else ListInsert(Lc,+k, bj);+jwhile (i<=La_len) GetElem(La, i+, ai);ListInsert(Lc, +k, ai);while (j<=Lb_len) GetElem(Lb, i+, bj);ListInsert(Lc, +k, bj)

3、; P22,线性表的顺序存储结构#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef struct ElemType *elem; /* 线性表占用的数组空间 */ int length； int listsize; SqList；P23,线性表顺序存储结构上的基本运算初始化操作Status IniList_Sq(SqList &L) L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length=

4、0; L.listsize=LIST_INIT_SIZE; return OK; P24,在顺序表里插入一个元素Status ListInsert_sq(SqList &L, int i, ElemType e) if(i<1|i>=L.length+1) return ERROR; if(L.length>=L.listsize) newbase=(ElemType*)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase)exit(OVERFLOW); L.elem=newb

5、ase; L.listsize+=LISTINCREMENT; q=&(L.elemi-1); for(p=&(L.elemL.length-1);p>=q;-p) *(p+1)=*p; *q=e; +L.length; return OK； P24,在顺序表里删除一个元素Status ListDelete_Sq(SqList &L,int i,ElemType &e)if( (i<1) | (i>L.length) ) return ERROR;p=&(L.elemi-1);e=*p; q=L.elem+L.length-1;for(

6、+p; p<=q; +p) *(p-1)=*p;-L.length;return OK;P25,在顺序表里查找一个元素int LocatElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType, ElemType)i=1;p=L.elem;while (i<=L.length && !(*compare)(*p+,e) +i;if (i<=L.length) return i;else return 0; P26,顺序表的合并void MergeList_Sq(SqList La, SqList Lb, Sq

7、List &Lc )pa=La.elem; pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTpe);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) if (*pa<=*pb) *pc+=*pa+; e

8、lse *pc+=*pb+;while(pa<=pa_last) *pc+=*pa+;while(pb<=pb_last) *pc+=*pb+; P28,线性表的单链表存储结构Typedef struct LNode   ElemType data; struct LNode *next;LNode ,*LinkList; /* LinkList为结构指针类型*/ P29,查找元素Status GetElem_L(LinkList L, int i, ElemType &a

9、mp;e)  p=L->next;  j=1; while (p && j<i)       p=p->next;    +j; if ( !p | j>i) return  ERROR; e=p->data; return  ok; P29,在单链表中插入一个元素Status ListInsert_L(LinkList &L, int

10、0;i, ElmeType e )p=L;j=0; while( p && j<i-1) p=p->next; +j;if( !p | j>i-1)  return  ERROR;s=(LinkList)malloc(sizeof(LNode);s->data=e; s->next=p->next; p->next=s;return  OK; P30,在单链表中删除一个元素Status ListDelete_L(LinkList 

11、;&L, int i, Elemtype &e)p=L;j=0;while ( p->next && j<i-1)p=p->next; +j;if ( !(p->next) | j>i-1)  return  ERROR q = p->next; p->next=q->next;e = q->data; free(q);return OK; P30,建立单链表void  

12、CreateList_L(LinkList &L, int n)L=(Linklist) malloc(sizeof(Lnode);L->next=NULL;for(i=n; i>0; -i)p=(LinkList)malloc(sizeof(Lnode);scanf(&p->data);p->next=L->next; L->next=p; P31,合并单链表void mergelist_L(LinkList &La,LinkList &Lb,LinkList &a

13、mp;Lc)pa=La->next; pb=Lb->next;Lc=pc=La;while( pa && pb) if( pa->data <= pb->data)      pc->next=pa; pc=pa; pa=pa->next;      else pc->next=pb; pc=pb; pb=pb->next;pc->next= pa ? pa : pb;free(Lb); P

14、31,线性表的静态单链表存储结构#define MAXSIZE 1000typedef struct ElemType data;int cur;component,SlinkListMAXSIZE; P32,定位函数int LocateElem_SL(SlinkList s, ElemType e)i=s0.cur;while( i && si.data!=e)   i=si.cur;return i; P33,void IniteSpa

15、ce_SL(SlinkList &space)for(i=0; i<MAXSIZE-1; +i) spacei.cur=i+1;spaceMAXSIZE-1.cur=0; int Malloc_SL(SlinkList &space)i=space0.cur;if (space0.cur) space0.cur=spacei.cur;return i; P35,线性表的双链表存储结构typedef struct DulNode      ElemType 

16、; data;      struct DulNode  *prior, *next;DulNode,*DuLinklist; P46,栈的顺序存储define TRUE 1define FALSE 0typedef struct SElemType * base; SElemType *top; int stacksize; /栈可使用的最大容量 SqStack; P47，栈的初始化Status InitStack (SqStack &S) S.base=(SElemType *)ma

17、lloc (STACK_INIT_SIZE *sizeof(SElemType); if (! S.base) exit (OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;取栈顶元素Status GetTop(SqStack S, SElemType &e) if (S.top = = S.base) return ERROR; e= * (S.top-1); return OK;入栈Status Push(SqStack &S, SElemType e) if (S.top - S.base>

18、;= 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+=STACKINCREMENT; *S.top+=e; return OK; 出栈Status Pop(SqStack &S, SelemType &e) if( S.top= =S.base) return ERROR; e=*-S.top; retu

19、rn OK;P48,转换为8进制void conversion()InitStack(S);scanf(“%d”,&N);while(N)Push(s, N % 8 );N=N / 8;while( !StackEmpty(s)Pop(S,e);printf(“%d”,e); P55,移动圆盘void hanoi(int n,char x,char y,char z) /*将塔座X上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到塔座Z上， Y可用作辅助塔座 */ if(n=1) move(x,1,z); /* 将编号为1的圆盘从X移动Z */ else hanoi(n-1,x

20、,z,y); /* 将X上编号为1至n-1的圆盘移到Y,Z作辅助塔 */ move(x,n,z); /* 将编号为n的圆盘从X移到Z */ hanoi(n-1,y,x,z); /* 将Y上编号为1至n-1的圆盘移动到Z， X作辅助塔 */ P61,链式队列的定义define TRUE 1define FALSE 0typedef struct QNode QElemType data; struct QNode *next;QNode, *QueuePtr;typedef struct QueuePtr front; QueuePtr rear;LinkQueue;P62,初始化Status

21、InitQueue(LinkQueue &Q) Q.front = Q.rear = (Queueptr) malloc(sizeof(QNode); if(!Q.front) exit ( OVERFLOW); Q.front ->next = NULL; return OK; 销毁队列Status DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear = Q.front->next;free (Q.front);Q.front = Q.rear; return OK;入队操作 Status EnQueue (LinkQ

22、ueue &Q, QelemType e) p= (QueuePtr) malloc(sizeof(QNode); if (!p) exit ( OVERFLOW); p->data = e; p->next = NULL; Q.rear -> next =p; Q.rear = p; return OK;出队操作 Status DeQueue (LinkQueue &Q, QelemType &e) if ( Q.front = Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.fro

23、nt->next =p->next; if (Q.rear = p) Q.rear = Q.front; free(p); return OK;P64，循环对列定义#define MAXQSIZE 100 /*队列的最大长度*/typedef struct QElemType *base; /* 队列的元素空间*/ int front; /*头指针指示器* int rear; /*尾指针指示器*/SqQueue; 初始化操作 Status InitQueue (SqQueue &Q) Q.base = (QElemType * )malloc(MAXQSIZE * size

24、of (QElemType); if ( ! Q. base) exit (OVERFLOW); Q. front = Q. rear = 0; return OK;入队操作 Status EnQueue (SqQueue &Q, QElemType e) if (Q. rear+ 1) % MAXQSIZE = Q. front) return ERROR; Q.baseQ.rear = e; Q.rear = (Q. rear + 1) % MAXQSIZE; return OK;） 出队操作 Status DeQueue (SqQueue &Q, QElemType &a

25、mp;e) if (Q. front = = Q. rear) return ERROR; e = Q. baseQ. front; Q. front = (Q. front + 1) % MAXQSIZE; return OK;求队列长度int QueueLength (SqQueue Q) return (Q. rear - Q. front + MAXQSIZE) % MAXQSIZE;P93/-数组的顺序存储表示include<string.h># define MAX_ARRAY_DIM 8typedef struct ELemType *base; /数组元素基址 in

26、t dim; /数组维数 int *bounds; /数组维数基址 int *constants; /数组映像函数常量基址 Array;P98,三元数组顺序表存储# define MAXSIZE 12500typedef struct int i, j ; ElemType e ;Triple ;typedef union Triple data MAXSIZE+1 ; int mu, nu, tu ;TSMatrix ; P99，矩阵转置Status TransposeSMatrix ( TSMatrix M, TSMatrix & T ) T.mu=M.nu; T.nu=M.mu;

27、 T.tu=M.tu; if( T.tu ) q=1; 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; return OK; / TransposeSMatrix P100Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T )/采用三元组顺序表存储表示，求稀疏矩阵M的转

28、置矩阵T。 T.mu=M.nu; T.nu=M.mu; T.tu=M.tu; if(T.tu) for(col=1;col<M.nu；col+) numcol=0; for(t=1; t<=M.nu;+t) +numM.datat.j; /求M中每一列含非零元个数。 copt1=1; / 求第col列中第一个非零元在b.data中的序号 for(col=2;col<=M.nu; +col) cpotcol=cpotcol-1+numcol-1; for(p=1; p<=M.tu;+p) col=M.datap.j ; q=cpotcol; T.dataq.i=M.dat

29、ap.j; T.dataq.j=M.datap.i; T.dataq.e=M.datap.e; +cpotcol; /for /if return ok;/ FastTranposeSMatrix; P129,先序遍历Status PreOrderTraverse ( Bitree T, Status ( * Visit ) ( TelemType e ) )12 if ( T ) 3 4 if ( Visit ( T->data ) )5 if ( PreOrderTraverse ( T->lchild , Visit ) ) 6 if ( PreOrderTraverse (

30、 T->rchild, Visit ) ) return OK;7 return ERROR;8 9 else return OK;10 中序遍历 Status InOrderTraverse ( Bitree T, Status ( * Visit ) ( TelemType e ) )12 if ( T ) 3 4 if ( InOrderTraverse ( T->lchild , Visit ) )5 if ( Visit ( T->data ) )6 if ( InOrderTraverse ( T->rchild, Visit ) ) return OK;7

31、 return ERROR;8 9 else return OK;10 P131,中序遍历二叉树Status InOrderTraverse( BiTree T, Status ( * Visit ) ( TelemType e ) ) InitStack ( S ); Push ( S, T ); While( !StackEmpty ( S ) ) while ( GetTop ( S, p ) &&p) Push ( S, p->lchild ); Pop ( S, p ); if ( !StackEmpty ( S ) ) Pop ( S, p ); if ( !

32、Visit ( p->data ) ) return ERROR; Push ( S, p->rchild ); / if / While return OK;/ InOrderTraverse Status InOrderTraverse ( BiTree T, Status ( *Visit ) ( TelemType e ) ) InitStack ( S ); p=T; While ( p | !StackEmpty ( S ) ) if ( p ) Push ( S, p ); p=p->lchild; else Pop ( S, p ); if ( !Visit

33、( p->data ) ) return ERROR; p=p->rchild; return OK; void PreOrder(BiTree root) /* 先序遍历输出二叉树中的叶子结点, root为指向二叉树根结点的指针 */ if (root! =NULL) if (root ->LChild=NULL && root ->RChild=NULL) printf (root ->data); /* 输出叶子结点 */ PreOrder(root ->LChild); /* 先序遍历左子树 */PreOrder(root ->

34、RChild); /* 先序遍历右子树 */ 统计叶子结点数目 LeafCount是保存叶子结点数目的全局变量, 调用之前初始化值为0 */void leaf(BiTree root) if(root! =NULL) leaf(root->LChild); leaf(root->RChild); if (root ->LChild=NULL && root ->RChild=NULL) LeafCount+; /* 采用递归算法，如果是空树，返回0；如果只有一个结点，返回1；否则为左右子树的叶子结点数之和 */int leaf(BiTree root) int LeafCount; if(root=NULL) LeafCount =0; else if(root->lchild=NULL)&&(root->rchild=NULL) LeafCount =1; else LeafCount =leaf(root->lchild)+leaf(root->rchild); /* 叶子数为左右子树的叶子数目之和 */ return LeafCount; P131,建立二叉链表方式存储的二叉树Status CreateBiTree( BiTree &T ) sca