數(shù)據(jù)結(jié)構(gòu)上機(jī)編程匯總

《數(shù)據(jù)結(jié)構(gòu)上機(jī)編程匯總》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)上機(jī)編程匯總（36頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)編程匯總2-1鏈表#include#include#include#include#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define NULL 0typedef int Status;typedef int ElemType;typedef struct LNode ElemType data; struct LNode *next;LNode, *LinkList;Status GetElem_L(LinkList L, in

2、t i, ElemType &e) /L涓哄甫澶寸粨鐐圭殑鍗曢摼琛殑澶存寚閽堛? /褰撶i涓厓绱犲瓨鍦椂錛屽叾鍊艱祴緇檈騫惰繑鍥濷K錛屽惁鍒欒繑鍥濫RROR LinkList *p; int j; p = L-next; j = 1; /鍒濆鍖栵紝p鎸囧悜絎竴涓粨鐐癸紝j涓鴻鏁板櫒 while(p & jnext; +j; if(!p | ji) return ERROR; /絎噼煱饏鷯绱鸞笉鄆姃湪 e = p-data; /鍙瀬i鍏冪礌 return OK;/ GetElem_LStatus ListInsert_L(LinkList &L, int i, ElemType e) /鍦甫澶寸

3、粨鐐圭殑鍗曢摼綰挎觥涓i涓綅緗箣鍓嶆彃鍏儑殑鍏檖礌e LinkList *p, *s; p = L; j = 0; while(p & jnext; +j; /瀵繪氒絎噼-1煱粨鐐? if(!p | ji-1) return ERROR; /i灝忎簬1鎴栬呭浜庤闀?1 s = (LinkList)malloc(sizeof(LNode);/鐢熸垚鏂扮粨鐐? s-data = e; s-next = p-next;/鎻掑叆L涓? p-next = s; return OK;/ ListInsert_LStatus ListDelete_L(LinkList &L, int i, ElemType

4、 &e) /鍦甫澶寸粨鐐圭殑鍗曢摼綰挎觥涓紝鍒犻櫎絎琲涓厓绱狅紝騫舵湁e榪斿洖鍏跺? LinkList *p,*q; int j; p = L; j= 0; while(p-next & jnext; +j; if(!(p-next)|ji-1) return ERROR;/鍒犻櫎浣嶇疆涓嶅悎鐞? q = p-next; p-next = q-next; /鍒犻櫎騫墮噴鏀劇粨鐐? e = q-data; free(q); return OK;/ ListDelete_Lvoid CreateList_L(LinkList &L, int n) /閫嗕綅搴忚緭鍏涓厓绱犵殑鍊鹼紝寤虹珛甯澶寸粨鐐圭

5、殑鍗曢摼綰挎觥 LinkList *p; L = (LinkList)malloc(sizeof(LNode); L-next = NULL;/鍏堝緩绔嬩竴涓甫澶寸粨鐐圭殑鍗曢摼琛? for(i = n; i 0; -i) p=(LinkList)malloc(sizeof(LNode);/鐢熸垚鏂扮粨鐐? scanf(%d,&p-data); p-next = L-next; L-next = p; /CreateList_Lvoid MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) /宸茬煡鍗曢摼綰挎觥a鍜孡b鐨勫厓绱犳寜鍊奸潪閫掑

6、噺鎺掑垪 /褰掑茍La鍜孡b寰楀埌鏂扮殑鍗曢摼綰挎觥c錛孡c鐨勫厓绱犱篃鎸夊奸潪閫掑噺鎺掑垪 LinkList *pa , *pb , *pc; pa = La-next; pb = Lb-next; Lc = pc = pa;/鐢Aa鐨勫緇撶偣浣滀負(fù)Lc鐨勫緇撶偣 while(pa & pb) if(pa-data data) pc-next = pa; pc = pa; pa = pa-next; elsepc-next = pb; pc = pb; pb = pb-next; pc-next = pa ? pa:pb;/鎻掑叆鍓綑孌? free(Lb);/閲婃斁Lb鐨勫緇撶偣/Merge

7、List_Lint LocateELem_SL(SLinkLIst S, ElemType e) i = S0.cur; while (i & Si.data != e)i = Si.cur; return i;2-2線性表#define LIST_INIT_SIZE 100 /綰挎觥瓨鍌闂寸殑鍒濆鍒嗛?#define LISTINCREMENT 10/綰挎觥瓨鍌闂寸殑鍒嗛厤澧為?#define OK 1typedef int Status;typedef int ElemType;typedef struct ElemType *elem;/瀛樺偍絀洪棿鍩哄潃 int length;/褰撳墠

8、闀垮害 int listsize;/褰撳墠鍒嗛厤鐨勫瓨鍌閲?SqList;SqList L , newbase;SqList *q , *p , *pa , *pb , *pc , *pa_last , *pb_last;Status InitList_Sq(SqList &L)/鏋勯犱竴涓鐨勭嚎鎬觥 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!L.elem) exit(OVERFLOW); L.length = 0; L.listsize = LIST_INIT_SIZE; return OK; /InitLis

9、t_SqStatus ListInsert_Sq(SqList &L, int i, ElemType e) /鍦搴忕嚎鎬觥涓i涓綅緗箣鍓嶆彃鍏柊鐨勫厓绱爀銆? /i鐨勫拰娉曞間負(fù)1銆?i銆?ListLength_Sq(L)+1 if(iL.length+1) return ERROR;/i鍊間笉鍚堟硶 if(L.length=L.listsize)/褰撳墠瀛樺偍絀洪棿宸叉弧錛屽鍔犲垎閰? newbase = (ElemType*)malloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType); if(!newbase) exit(OVERF

10、LOW); /瀛樺偍鍒嗛厤澶辮觸 L.elem = newbase; /鏂板熀鍧 L.listsize+ = LISTINCREMENT; /澧炲姞瀛樺偍瀹歸噺 q = &(L.elemi-1); /q涓烘彃鍏綅緗? for(p = &(L.elemL.length-1);p = q; -p) *(p+1) = *p; /鎻掑叆浣嶇疆鍙?qiáng)涔嬪悗鐨勫厓绱犲彸?*q = e; /鎻掑叆e +L.length; /琛暱澧? return OK;/ListInsert_SqStatus ListDelete_Sq(SqList &L, int i, ElemType &e) /鍦搴忕嚎鎬鰜VL煱胥垹闄

11、傚馣i煱厓绱狅紝騫剁敤e榪斿洖鍏跺? /i鐨勫悎娉曞間負(fù)1銆?i銆?ListLength_Sq(L) if(iL.length) return ERROR; /i鍊間笉鍚堟硶 p = &(L.elemi-1); /p涓鴻鍒犻櫎鍏冪礌鐨勪綅緗? e = *p; /琚垹闄傘鷯绱犵殑鍊艱祴緇檈 q = L.elem+L.length-1; /琛鄴鍏檖礌鐨勪綅緗? for(+p;p=q;+p) *(p-1)=*p; /琚垹闄厓绱犱箣鍚庣殑鍏冪礌宸 -L.length; /琛暱鍑? return OK; /ListDelete_Sqint LocateElem_Sq(SqList L, ElemType

12、 e, Status (*compare)(ElemType , ElemType) /鍦搴忕嚎鎬觥涓煡鎵劇1涓奸亣e婊凍compare()鐨勫厓绱犵殑浣嶅簭 /鑻儐氒鍒幫紝鍒烺繑鍥炲叾鍦煱皴殑煰嶅簭錛屽惁鍒烺繑鍥? int i = 1; /i鐨勫垵鍊間負(fù)絎?煱饏鷯绱犵殑潒忎綅 p = L.elem; /p鐨勫垵鍊間負(fù)絎?煱厓绱犵殑瀛樺偍浣嶇疆 while(i=L.length & !(*compare)(*p+,e) +i; if(i=L.length) return i; else return 0;/LocateElem_Sqvoid MergeList_Sq(SqList La, Sq

13、List Lb, SqList &Lc) /宸茬煡欏哄簭綰挎觥a鍜孡b鐨勫厓绱犳寜鍊奸潪閫掑噺鎺掑垪 /褰掑茍La鍜孡b寰楀埌鏂扮殑欏哄簭綰挎觥c錛孡c鐨勫厓绱犱篃鎸夊奸潪閫掑噺鎺掑垪 pa = La.elem; pb = Lb.elem; Lc.listsize = Lc.length = La.length + Lb.length; pc = Lc.elem = (ElemType*)malloc(Lc.listsize*sizeof(ElemType); if(!Lc.elem) exit(OVERFLOW); /瀛樺偍鍒嗛厤澶辮觸 pa_last = La.elem + La.leng

14、th-1; pb_last = Lb.elem + Lb.length-1; while(pa = pa_last&pb = pb_last) /褰掑茍 if(*pa = *pb) *pc+ = *pa +; else *pc+ = *pb+; while(pa = pa_last) *pc+ = *pa+; /鎻掑叆La鍓綑鐨勫厓绱? while(pb =s.stacksize)s.base=(int *)realloc(s.base,(s.stacksize+INCR)*sizeof(int);if(!s.base)exit(0);s.top=s.base+s.stacksize;s.st

15、acksize+=INCR;*(s.top)=e;(s.top)+;int gettop(sqstack &s,int *e)if(s.top=s.base)return 0;*e= *(s.top-1); return 1;struct migongint flag;int dir;struct migong a1010;int masepath(int i,int j,int m,int n,sqstack &s)if(aij.flag=1)printf(n鍏儏彛閿烺顰n);return 0;do if (i=m&j=n)push(s,i);push(s,j);return 1;else

16、if(aij.dir=1) if(aij+1.flag=1) aij.dir+; else push(s,i);push(s,j);aij.flag=1;j+;continue;if(aij.dir=2) if(ai+1j.flag=1) aij.dir+; else push(s,i);push(s,j);aij.flag=1;i+;continue;if(aij.dir=3) if(aij-1.flag=1) aij.dir+; else push(s,i);push(s,j);aij.flag=1;j-;continue;if(aij.dir=4) if(ai-1j.flag=1) ai

17、j.dir+; else push(s,i);push(s,j);aij.flag=1;i-;continue;elseaij.flag=1;pop(s,&j);pop(s,&i);aij.flag=0;while(s.top!=s.base);printf(n娌亷湁鍑鴻礬n);return 2;void main()int m,n,x,y,i,j,r=1;sqstack s1,s2;initstack(s2);initstack(s1);int b1010= 1,1,1,1,1,1,1,1,1,1, 1,0,0,1,0,0,0,1,0,1, 1,0,0,1,0,0,0,1,0,1, 1,0,

18、0,0,0,1,1,0,0,1, 1,0,1,1,1,1,1,0,0,1, 1,0,0,0,1,0,0,0,0,1, 1,0,1,0,0,0,1,0,0,1, 1,0,1,1,1,0,1,1,0,1, 1,1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,;printf(馭寤鴻糠瀹涓嬪浘錛屽叾涓?琛偢澧欙紝0琛偢閫氳礬n);printf( 0 1 2 3 4 5 6 7 8 9nn);for(i=0;i10;i+)printf( %d ,i);for(j=0;j10;j+) aij.flag=bij;printf(%d ,bij);aij.dir=1;printf(

19、n);printf(璇瘋緭鍏儏嚭鍙倓綅緗甛n);scanf(%d,&m);scanf(%d,&n);masepath(1,1,m,n,s1);while(s1.top!=s1.base)pop(s1,&x);push(s2,x);printf(n幃?dāng)聡簶q曯鐨勮礬寰勪負(fù):n);while(s2.top!=s2.base)pop(s2,&x);pop(s2,&y);printf( ,x,y);if(r+%5=0)printf(n);4-1括號(hào)匹配#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char SElemType;ty

20、pedef int Status;typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; Status InitStack(SqStack &S) S.base=(SElemType * )malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; Status Push(SqStack &S,SElemType e) if

21、(S.top-S.base=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; return OK;

22、 Status StackEmpty (SqStack S) if(S.top=S.base) return TRUE; else return FALSE; Status Match(char a,SqStack &S) int i ,n; n=strlen(a); 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.

23、base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;/PushStatus Pop(SqStack &S,SElemType &e) if(S.top=S.base) return ERROR; e=*-S.top; return OK;/PopStatus ClearStack(SqStack &S)S.top = S.base; return OK; Status DestroyStack(SqStack &S) free(S.base); S.base = NULL; S.top = NULL; S.st

24、acksize = 0; return OK; Status StackTraverse(SqStack S,Status(* visit)() return OK;Status visit(SqStack &S) if(S.base=S.top) return ERROR; while(S.base!=S.top) printf(%c,*(S.base); S.base+; return OK;int LineEdit()SqStack S; char ch,c;InitStack(S); while(ch!=EOF) while(ch!=EOF & ch!=n) switch(ch) ca

25、se # : Pop(S,c);break; case : ClearStack(S);break; default : Push(S,ch);break; ch=getchar( ); visit(S); ClearStack(S); if(ch!=EOF) ch=getchar( ); DestroyStack(S); return 0;/ LineEdit5-1數(shù)組#define MAX_ARRAY_DIM 8typedef int ElemType;typedef int Status;typedef struct ElemType *base; int dim; int *bound

26、s; int *constants;Array;Status InitArray(Array &A,int dim,.) int elemtotal,i;va_list ap; if(dimMAX_ARRAY_DIM) return ERROR; A.dim=dim; A.bounds=(int *)malloc(dim*sizeof(int); if(!A.bounds) exit(OVERFLOW); elemtotal=1; va_start(ap,dim); for(i=0;idim;+i) A.boundsi=va_arg(ap,int); if(A.boundsi=0;-i) A.

27、constantsi=A.boundsi+1*A.constantsi+1; return OK;Status DestroyAttay(Array &A) if(!A.base) return ERROR; free(A.base); A.base=NULL; if(!A.bounds) return ERROR; free(A.bounds);A.bounds=NULL; if(!A.constants) return ERROR; free(A.bounds);A.constants=NULL; return OK;Status Locate(Array A,va_list ap,int

28、 &off) int ind,i; off=0; for(i=0;iA.dim;+i) ind=va_arg(ap,int); if(ind=A.boundsi) return OVERFLOW; off+=A.constantsi*ind; return OK;Status Value(Array A,ElemType &e,.) va_list ap;int off,result; va_start(ap,e); if(result=Locate(A,ap,off)=0)return result; e=*(A.base+off); return OK;Status Assign(Arra

29、y &A,ElemType e,.) va_list ap;int result,off; va_start(ap,e); if(result =Locate(A,ap,off)=0)return result; *(A.base+off)=e; return OK;int main() int DIM=2,dim1=3; Array A; int x,y,i,j,k,e; int a,b,c; printf(請輸入二維數(shù)組的維數(shù):); scanf(%d %d,&x,&y); InitArray(A,DIM,x,y); for(i=0;ix;i+) for(j=0;jy;j+) scanf(%

30、d,&e); Assign(A,e,i,j) ; printf(輸出的二維數(shù)組為:n); for(i=0;ix;i+) for(j=0;jy;j+) Value(A,e,i,j); printf(%d ,e); printf(n); printf(請輸入維三數(shù)組的維數(shù):); scanf(%d %d %d,&a,&b,&c); InitArray(A,dim1,a,b,c); for(i=0;ia;i+) for(j=0;jb;j+) for(k=0;kc;k+) scanf(%d,&e); Assign(A,e,i,j,k) ; printf(輸出的三維數(shù)組為:n); for(i=0;ia;i

31、+) for(j=0;jb;j+) for(k=0;kc;k+) Value(A,e,i,j,k); printf(%d ,e); printf(n); printf(n); return 0;6-1快速轉(zhuǎn)至#define MAXSIZE 12500typedef int ElemType;typedef int Status;typedef struct int i,j; ElemType e;Triple;typedef struct Triple dateMAXSIZE+1; int mu,nu,tu;TSMatrix;Status FastTransposeSMatrix(TSMatr

32、ix M,TSMatrix &T) int col,p,t,q; int numM.nu,cpotM.nu; T.mu=M.mu; T.nu=M.nu; T.tu=M.tu; if(T.tu) for(col=1;col=M.nu;+col) numcol=0; for(t=1;t=M.tu;+t) +numM.datet.j; cpot1=1; for(col=2;col=M.nu;+col) cpotcol=cpotcol-1+numcol-1; for(p=1;p=M.tu;+p) col=M.datep.j; q=cpotcol; T.dateq.i=M.datep.j; T.date

33、q.j=M.datep.i; T.dateq.e=M.datep.e; +cpotcol; return 1; int main() TSMatrix M; TSMatrix T; int p; scanf(%d,%d,%d,&M.mu,&M.nu,&M.tu); for (p=1;p=M.tu;p+) scanf(%d %d %d,&M.datep.i,&M.datep.j,&M.datep.e); FastTransposeSMatrix(M,T); for (p=1;p=M.tu;p+) printf(%d,%d,%d,&T.datep.i,&T.datep.j,&T.datep.e);

34、 printf(n);6-2矩陣加法#define MAXSIZE 12500typedef int Status;typedef int ElemType;typedef struct int i,j; ElemType e;Triple;typedef struct Triple dateMAXSIZE+1; int mu,nu,tu;TSMatrix;Status CreatSMatrix(TSMatrix *M)/建立三元組 int row,col,date,k; printf(請輸入行數(shù)列數(shù)和非零元個(gè)數(shù)n); scanf(%d,%d,%d,&(*M).mu,&(*M).nu,&(*M

35、).tu); while( (*M).mu = 0 | (*M).nu ( (*M).mu * (*M).nu ) | (*M).tu MAXSIZE) printf(輸入不正確，請重新輸入n); fflush(stdin); scanf(%d,%d,%d,&(*M).mu,&(*M).nu,&(*M).tu); (*M).date0.i = 0; for( k = 1; k = (*M).tu ; k+) printf(請輸入每個(gè)非零元素的行號(hào)，列號(hào)，數(shù)值n); scanf(%d,%d,%d,&row,&col,&date); (*M).datek.i = row; (*M).datek.j

36、 = col; (*M).datek.e = date; printf(輸入非空元素組成的三元組完畢!n); return OK;Status comp( int a, int b)/比較兩個(gè)數(shù)字的大小AddSmatrix函數(shù)使用 int i; if( a b) i = -1; return i;Status AddSMatrix( TSMatrix &A, TSMatrix &B, TSMatrix *C)/矩陣的相加 Triple *Ap,*Bp,*Ae,*Be,*Ch,*Ce; int i; if( A.mu != B.mu | A.nu != B.nu) /矩陣相加條件是行列必須相等

37、printf(nA and B is not comparedn); return ERROR; if( (*C).date ) free( (*C).date ); (*C).mu = A.mu; (*C).nu = A.nu; Ap = &A.date1; /Ap的初值指向矩陣A的非零元素的首地址 Bp = &B.date1; /Bp的初值指向矩陣B的非零元素的首地址 Ae = &A.dateA.tu; /Ae指向矩陣A的非零元素尾地址 Be = &B.dateB.tu; /Be指向矩陣B的非零元素尾地址 Ch = Ce = (*C).date; /Ch Ce的初值指向矩陣C的非零元素首地

38、址的前一地址 while( Ap = Ae & Bp i, Bp-i ) ) case 1: *Ce = *Ap; Ap+;break; case -1: *Ce = *Bp; Bp+; break; case 0: switch( comp(Ap-j,Bp-j) ) case 0: *Ce = *Ap; Ce-e += Bp-e; if( !Ce-e ) Ce-; Ap+; Bp+; break; case 1: *Ce = *Ap; Ap+;break; case -1: *Ce = *Bp; Bp+; break; if( Ap Ae) /矩陣A的元素全部處理完畢 while( Bp B

39、e) /矩陣B的元素全部處理完畢 while( Ap = Ae) Ce+; *Ce = *Ap; Ap+; (*C).tu = Ce - Ch; /矩陣C的非零元素個(gè)數(shù) return OK;Status Print(TSMatrix &N) int q; for(q=1;q=N.tu;q+) printf(%4d%4d%4dn, N.dateq.i,N.dateq.j,N.dateq.e); return OK;Status DestroySMatrix( TSMatrix &M) /必須使用&接收M，否則銷毀不了/銷毀稀疏矩陣的三元組順序表 if( M.mu = 0 | M.nu M.mu * M.nu) /負(fù)負(fù)相乘能得正數(shù) printf(n不存在矩陣!n); return ERROR; for( int k = 1; k n) e=0; else e=2*i; return e;Status RightChile(SqBiTree T