數(shù)據(jù)結(jié)構(gòu)代碼

1、精選文檔數(shù)據(jù)結(jié)構(gòu)代碼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,線性表的順序存儲結(jié)構(gòu)#define LIST_INIT_SIZE 100#define LISTINCREMENT 10 typedef struct ElemType *elem; /* 線性表占用的數(shù)組空間 */ int length； int listsize; SqList；P23,線性表順序存儲結(jié)構(gòu)上的基本運(yùn)算初始化操作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,線性表的單鏈表存儲結(jié)構(gòu)Typedef struct LNode   ElemType data; struct LNode *next;LNode ,*LinkList; /* LinkList為結(jié)構(gòu)指針類型*/ 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,線性表的靜態(tài)單鏈表存儲結(jié)構(gòu)#define MAXSIZE 1000typedef struct ElemType data;int cur;component,SlinkListMAXSIZE; P32,定位函數(shù)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,線性表的雙鏈表存儲結(jié)構(gòu)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,轉(zhuǎn)換為8進(jìn)制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個圓盤按規(guī)則搬到塔座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(jié),Z作輔助塔 */ move(x,n,z); /* 將編號為n的圓盤從X移到Z */ hanoi(n-1,y,x,z); /* 將Y上編號為1至n-1的圓盤移動到Z， X作輔助塔 */ P61,鏈?zhǔn)疥?duì)列的定義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; 銷毀隊(duì)列Status DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear = Q.front->next;free (Q.front);Q.front = Q.rear; return OK;入隊(duì)操作 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;出隊(duì)操作 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，循環(huán)對列定義#define MAXQSIZE 100 /*隊(duì)列的最大長度*/typedef struct QElemType *base; /* 隊(duì)列的元素空間*/ 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;入隊(duì)操作 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;） 出隊(duì)操作 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;求隊(duì)列長度int QueueLength (SqQueue Q) return (Q. rear - Q. front + MAXQSIZE) % MAXQSIZE;P93/-數(shù)組的順序存儲表示include<string.h># define MAX_ARRAY_DIM 8typedef struct ELemType *base; /數(shù)組元素基址 in

26、t dim; /數(shù)組維數(shù) int *bounds; /數(shù)組維數(shù)基址 int *constants; /數(shù)組映像函數(shù)常量基址 Array;P98,三元數(shù)組順序表存儲# define MAXSIZE 12500typedef struct int i, j ; ElemType e ;Triple ;typedef union Triple data MAXSIZE+1 ; int mu, nu, tu ;TSMatrix ; P99，矩陣轉(zhuǎn)置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的轉(zhuǎn)

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中每一列含非零元個數(shù)。 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) /* 先序遍歷輸出二叉樹中的葉子結(jié)點(diǎn), root為指向二叉樹根結(jié)點(diǎn)的指針 */ if (root! =NULL) if (root ->LChild=NULL && root ->RChild=NULL) printf (root ->data); /* 輸出葉子結(jié)點(diǎn) */ PreOrder(root ->LChild); /* 先序遍歷左子樹 */PreOrder(root ->

34、RChild); /* 先序遍歷右子樹 */ 統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目 LeafCount是保存葉子結(jié)點(diǎn)數(shù)目的全局變量, 調(diào)用之前初始化值為0 */void leaf(BiTree root) if(root! =NULL) leaf(root->LChild); leaf(root->RChild); if (root ->LChild=NULL && root ->RChild=NULL) LeafCount+; /* 采用遞歸算法，如果是空樹，返回0；如果只有一個結(jié)點(diǎn)，返回1；否則為左右子樹的葉子結(jié)點(diǎn)數(shù)之和 */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); /* 葉子數(shù)為左右子樹的葉子數(shù)目之和 */ return LeafCount; P131,建立二叉鏈表方式存儲的二叉樹Status CreateBiTree( BiTree &T ) sca