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

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娌亷湁鍑?guó)櫟\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(請(qǐng)輸入二維數(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(請(qǐng)輸入維三數(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(請(qǐng)輸入行數(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(輸入不正確，請(qǐng)重新輸入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(請(qǐng)輸入每個(gè)非零元素的行號(hào)，列號(hào)，數(shù)值n); scanf(%d,%d,%d,&row,&col,&date); (*m).datek.i = row; (*m).datek.j = 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; ret