数据结构上机编程汇总.doc

数据结构上机编程汇总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, int 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) /鍦甫澶寸粨鐐圭殑鍗曢摼绾挎觥涓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 &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) /閫嗕綅搴忚緭鍏涓厓绱犵殑鍊硷紝寤虹珛甯澶寸粨鐐圭殑鍗曢摼绾挎觥 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鐨勫厓绱犳寜鍊奸潪閫掑噺鎺掑垪 /褰掑苟la鍜孡b寰楀埌鏂扮殑鍗曢摼绾挎觥c锛孡c鐨勫厓绱犱篃鎸夊奸潪閫掑噺鎺掑垪 linklist *pa , *pb , *pc; pa = la-next; pb = lb-next; lc = pc = pa;/鐢aa鐨勫缁撶偣浣滀负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鐨勫缁撶偣/mergelist_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;/褰撳墠闀垮害 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; /initlist_sqstatus listinsert_sq(sqlist &l, int i, elemtype e) /鍦搴忕嚎鎬觥涓i涓綅缃箣鍓嶆彃鍏柊鐨勫厓绱爀銆? /i鐨勫拰娉曞间负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(overflow); /瀛樺偍鍒嗛厤澶辫触 l.elem = newbase; /鏂板熀鍧 l.listsize+ = listincrement; /澧炲姞瀛樺偍瀹归噺 q = &(l.elemi-1); /q涓烘彃鍏綅缃? for(p = &(l.eleml.length-1);p = q; -p) *(p+1) = *p; /鎻掑叆浣嶇疆鍙婁箣鍚庣殑鍏冪礌鍙崇 *q = e; /鎻掑叆e +l.length; /琛暱澧? return ok;/listinsert_sqstatus listdelete_sq(sqlist &l, int i, elemtype &e) /鍦搴忕嚎鎬鰜vl煱胥垹闄傚馣i煱厓绱狅紝骞剁敤e杩斿洖鍏跺? /i鐨勫悎娉曞间负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 e, status (*compare)(elemtype , elemtype) /鍦搴忕嚎鎬觥涓煡鎵剧1涓奸亣e婊冻compare()鐨勫厓绱犵殑浣嶅簭 /鑻儐氒鍒帮紝鍒烺繑鍥炲叾鍦煱皴殑煰嶅簭锛屽惁鍒烺繑鍥? int i = 1; /i鐨勫垵鍊间负绗?煱饏鷯绱犵殑潒忎綅 p = l.elem; /p鐨勫垵鍊间负绗?煱厓绱犵殑瀛樺偍浣嶇疆 while(i=l.length & !(*compare)(*p+,e) +i; if(i=l.length) return i; else return 0;/locateelem_sqvoid mergelist_sq(sqlist la, sqlist 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.length-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.stacksize+=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 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) aij.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,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(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帏斅嚭杩曯鐨勮矾寰勪负:n);while(s2.top!=s2.base)pop(s2,&x);pop(s2,&y);printf( ,x,y);if(r+%5=0)printf(n);4-1括号匹配#define stack_init_size 100#define stackincrement 10typedef char selemtype;typedef 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(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; 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.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.stacksize = 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) case # : 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数组#define max_array_dim 8typedef int elemtype;typedef int status;typedef struct elemtype *base; int dim; int *bounds; 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.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 &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(array &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(请输入二维数组的维数:); scanf(%d %d,&x,&y); initarray(a,dim,x,y); for(i=0;ix;i+) for(j=0;jy;j+) scanf(%d,&e); assign(a,e,i,j) ; printf(输出的二维数组为:n); for(i=0;ix;i+) for(j=0;jy;j+) value(a,e,i,j); printf(%d ,e); printf(n); printf(请输入维三数组的维数:); 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(输出的三维数组为:n); for(i=0;ia;i+) 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快速转至#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(tsmatrix 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.dateq.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); 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(请输入行数列数和非零元个数n); scanf(%d,%d,%d,&(*m).mu,&(*m).nu,&(*m).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(请输入每个非零元素的行号，列号，数值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)/比较两个数字的大小addsmatrix函数使用 int i; if( a b) i = -1; ret