西安电子科技大学出版社：《算法与数据结构》课程教学资源（练习题）数组（实例）

数组 #include #include like h #define maX array dim 8 typedef int ElemType typedef struct t ElemType base int dim: int *bounds int *constants B Array Status InitArray (array **A, int dim i int elemtotal, i va list ap if(dimMAX ARRAY DIM)return ERROR A->dimdim: A->bounds=(int *)malloc(dim*sizeof (int)) elemtotal=l va start(ap, dim) for(i=0; ibounds [i]=va arg (ap, int) elemtotal *=A->bounds [il va end (ap) A->base=(ElemType *)malloc(elemtotal*sizeof (Elem Type)) A->constants=(int *)malloc(dim*sizeof (int)) A->constants [dim1]=l for(i=dim-2:i>=0:i) A->constants [i]=A-bounds [i+1]*A->constants[i+1 return OK Status DestroyArray(array *A) i if(!A->base)return ERROR free(A->base) A->base=NULL free(A->bounds) A->boundS=NULL free(A->constants): A->constants=NULL return OK Status Locate (array A, va list ap, int soff) I int i, ind; *off=0 for(i=0; i=A bounds [i])return OVERFLOW

数组 #include #include "likec.h" #define MAX_ARRAY_DIM 8 typedef int ElemType; 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)); elemtotal=1; va_start(ap,dim); for(i=0;ibounds[i]=va_arg(ap,int); elemtotal *=A->bounds[i]; } va_end(ap); A->base=(ElemType *)malloc(elemtotal*sizeof(ElemType)); A->constants=(int *)malloc(dim*sizeof(int)); A->constants[dim-1]=1; for(i=dim-2;i>=0;--i) A->constants[i]=A->bounds[i+1]*A->constants[i+1]; return OK; } Status DestroyArray(Array *A) { if(!A->base)return ERROR; free(A->base); A->base=NULL; free(A->bounds); A->bounds=NULL; free(A->constants); A->constants=NULL; return OK; } Status Locate(Array A,va_list ap,int *off) { int i,ind; *off=0; for(i=0;i=A.bounds[i])return OVERFLOW;

off+=A constants [i]ind return OK Status Value (array A, ElemType *e i va list int result, off va start(ap, A dim) if((result=Locate(A, ap, &off)) #define n 100 #define max 9999 typedef struct node f union char data int Ival struct node **lchild struct node *archil d: INODE NODE *creat huffman tree(char dat[, int w[, int n I NODE *TIN, *p; int nl, n2, 1, j, v, minl, min2 [TLi]=(NODE *)malloc(sizeof (NODE)) T[i]->val w=w[i] T[i]->lchild=NULL

*off+=A.constants[i]*ind; } return OK; } Status Value(Array A,ElemType *e,...) { va_list ap; int result,off; va_start(ap,A.dim); if((result=Locate(A,ap,&off)) #define N 100 #define MAX 9999 typedef struct node{ union{ char data; int w; }val; struct node *lchild; struct node *rchild; }NODE; NODE *creat_huffman_tree(char dat[],int w[],int n) { NODE *T[N],*p; int n1,n2,i,j,v,min1,min2; for(i=0;ival.w=w[i]; T[i]->lchild=NULL;

T[i]->rchild=NULL for (i=0; ivalw if(vval W=T[n1]->val w+T[n2]->valw p->lchild=T[nl] p->rchild=T[n2] if(T[n1]->lchild==NULL)T[n1]->val data=dat [n1 else T[n1]->val data='s' f(T[n2]->lchild==NULL)T[n2]->val data=dat [n2 else T[n2]->val data=*k T[n1 T[n2]=NULL val.data=’*2 return(p) prn BT(NODE *b) I if(b!=NULL) i printf("%c", b->val data) if(b->lchild!=NULL I printf("(") prn BT(b->lchild) prn BT(b->rchild

T[i]->rchild=NULL; } for(i=0;ival.w; if(vval.w=T[n1]->val.w+T[n2]->val.w; p->lchild=T[n1]; p->rchild=T[n2]; if(T[n1]->lchild==NULL)T[n1]->val.data=dat[n1]; else T[n1]->val.data='*'; if(T[n2]->lchild==NULL)T[n2]->val.data=dat[n2]; else T[n2]->val.data='*'; T[n1]=p; T[n2]=NULL; } p->val.data='*'; return(p); } prn_BT(NODE *b) { if(b!=NULL) { printf("%c",b->val.data); if(b->lchild!=NULL) { printf("("); prn_BT(b->lchild); printf(","); prn_BT(b->rchild);

printf(")") I NODE *h hard[N]={'a’,’b intw[N]={1,3,2,4} h=creat huffman tree(d, w, 4) printf(" \n") prn BT(h) 线性表的顺序存储与实现 #"likes. h #define lIst INit size 100 #define listIncrement 10 typedef int ElemType typedef struct ElemType elem int length int listsize: sLiSt Status InitList Sq(sqList *L)I L->elem=(ElemType *)malloc(LIST INIT SIZE*sizeof (ElemType)) if(! L->elem)exit(OVERFLOW) L-length=O L->listsize=LIST INIT SIze return OK void DestroyList Sq(sqList *L)( if(→>elem){ L-length=0 L->listsize=o void ClearList Sq(sqList *L)I if(L-elem)I L->elem=(ElemType srealloc(L->elem, L->listsize*sizeof(ElemType)) L-length=0;

printf(")"); } } } main() { NODE *h; char d[N]={'a','b','c','d'}; int w[N]={1,3,2,4}; h=creat_huffman_tree(d,w,4); printf("\n"); prn_BT(h); } 线性表的顺序存储与实现 #include "likec.h" #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef int ElemType; typedef struct{ ElemType *elem; int length; int listsize; }SqList; 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; } void DestroyList_Sq(SqList *L){ if(L->elem){ free(L->elem); L->length=0; L->listsize=0; } } void ClearList_Sq(SqList *L){ if(L->elem){ L->elem=(ElemType *)realloc(L->elem,L->listsize*sizeof(ElemType)); L->length=0; } }

Status ListEmpty Sq(sqList L)( if(L. length==O)return TRUE else return False: int ListLength Sq(sqlist L)( return L length Status GetElem Sq(sqlist L, int i, ElemType *e)I if(i=L. length)return ERROR *e=L elem[il return int LocateElem Sq(sglist L, elemType e)i int 1=0; while(iL->length)return ERROR if(L-length==L->listsize)I L->elem=(ElemType *)realloc( L->elem,(L->listsize+LISTINCREMENT)*sizeof (Elem Type))

Status ListEmpty_Sq(SqList L){ if(L.length==0)return TRUE; else return FALSE; } int ListLength_Sq(SqList L){ return L.length; } Status GetElem_Sq(SqList L,int i,ElemType *e){ if(i=L.length)return ERROR; *e=L.elem[i]; return OK; } int LocateElem_Sq(SqList L,ElemType e){ int i=0; while(iL->length)return ERROR; if(L->length==L->listsize){ L->elem=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));

L->listsize=LISTINCreMENT for (j=L->length: j>i&&j; j-)L->elem [j]=L->elem[j-1] L->length+=l return OK Status ListDelete Sq (sqList *L, int 1, ElemType *e)i if(i=L->length)return ERROR L->elem[il for(j=i; jlength-1: j++)L->elem[j]=L->elem[j+1 L->length-=l return oK void ListPrint Sq(sqList L)( for(i=0; inext=NUL; return OK

L->listsize+=LISTINCREMENT; } for(j=L->length;j>i&&j;j--)L->elem[j]=L->elem[j-1]; L->elem[i]=e; L->length+=1; return OK; } Status ListDelete_Sq(SqList *L,int i,ElemType *e){ int j; if(i=L->length)return ERROR; *e=L->elem[i]; for(j=i;jlength-1;j++)L->elem[j]=L->elem[j+1]; L->length-=1; return OK; } void ListPrint_Sq(SqList L){ int i; for(i=0;i typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; Status InitList_L(LinkList *L){ *L=(LinkList)malloc(sizeof(LNode)); if(!(*L))exit(OVERFLOW); (*L)->next=NULL; return OK;

void DestroyList L(LinkList *L)I Linklist p=kL, q while(p)i p=p->next free(g) *LENULL void ClearList L(LinkList *L)( LinkList p=(*L)->next, q while(p)i p=p->next free(g) (*L)->next=NULL Status ListEmpty L(LinkList L)( if(L->next==NULLreturn else return false int ListLength L(LinkList L)[ LinkList p: for(p=L->next: p: p=p->next)i++ return 1 Status GetElem L(LinkList L, int i, ElemType *e) Int J while(l&&j!=i)[ L=L->next f(j==i)(*e=L->data return OK: else return error LinkList LocateElem L (LinkList L, ElemType e)I Linklist p=L->next while(p&&p->data!=e)p=p->next return(p)

} void DestroyList_L(LinkList *L){ LinkList p=*L,q; while(p){ q=p; p=p->next; free(q); } *L=NULL; } void ClearList_L(LinkList *L){ LinkList p=(*L)->next,q; while(p){ q=p; p=p->next; free(q); } (*L)->next=NULL; } Status ListEmpty_L(LinkList L){ if(L->next==NULL)return TRUE; else return FALSE; } int ListLength_L(LinkList L){ LinkList p; int i=0; for(p=L->next;p;p=p->next)i++; return i; } Status GetElem_L(LinkList L,int i,ElemType *e){ int j=-1; while(L&&j!=i){ L=L->next; j++; } if(j==i){*e=L->data; return OK; } else return ERROR; } LinkList LocateElem_L(LinkList L,ElemType e){ LinkList p=L->next; while(p&&p->data!=e) p=p->next; return(p);

Status PriorElem L(LinkList L, ElemType cur e, Elem Type *pre e)I Linklist p, g: p=LocateElem L (L, cur e) if(! p)return ERROR while(g->next! =p)g=g->next if(q=L)return ERROR =q->dat return OK: Status NextElem L (LinkList L, ElemType cur e, Elem Type *next e)I p=LocateElem L(L, cur e if(! p)return ERROR: if( return ERROR > data return OK. Status ListInsert L(LinkList L, int i, ElemType e)( Linklist p=L,q: len=ListLength L(L) if(i=len+1)return ERROR; g=(LinkList)malloc(sizeof(LNode)) q->data=e q->next=p->next return OK: Status ListDelete L(LinkList L, int 1, ElemType *e)i int j=0, len Linklist p=L, g if(i=len)return ERROR while(jl=i)Ip=p->next: j++: K p->next=q->next return OK

} Status PriorElem_L(LinkList L,ElemType cur_e,ElemType *pre_e){ LinkList p,q; p=LocateElem_L(L,cur_e); if(!p)return ERROR; q=L; while(q->next!=p)q=q->next; if(q==L)return ERROR; *pre_e=q->data; return OK; } Status NextElem_L(LinkList L,ElemType cur_e,ElemType *next_e){ LinkList p,q; p=LocateElem_L(L,cur_e); if(!p)return ERROR; q=p->next; if(!q)return ERROR; *next_e=q->data; return OK; } Status ListInsert_L(LinkList L,int i,ElemType e){ int len,j=0; LinkList p=L,q; len=ListLength_L(L); if(i=len+1)return ERROR; q=(LinkList)malloc(sizeof(LNode)); q->data=e; while(j!=i){p=p->next;j++;} q->next=p->next; p->next=q; return OK; } Status ListDelete_L(LinkList L,int i,ElemType *e){ int j=0,len; LinkList p=L,q; len=ListLength_L(L); if(i=len)return ERROR; while(j!=i){p=p->next;j++;} q=p->next; p->next=q->next; *e=q->data; free(q); return OK; }

void ListPrint L(LinkList L)[ LinkList p=L->next for(p; p=p->next)printf("%3d", p->data) printf(" \n") maino char ch. Linklist l. InitList L(&L) ch=getchar o while(ch!=Q)I switch(ch)i case for(m=0;m<10;m++) if(!ListInsert L (L, m, 2*m))printf ("error") ListPrint L(L) case ListInsert L(L, 3, 77) ListPrint L(L) case ClearList L(&L) ListPrint L(L) getchar ch=getchar o 矩阵及其操作 #include like h #define maXsize 1250 typedef int ElemType typedef struct f int 1 Elem TRiple typedef union( Triple data [MAXSIZE+1] int mu, nu, tu:

void ListPrint_L(LinkList L){ LinkList p=L->next; for(;p;p=p->next)printf("%3d",p->data); printf("\n"); } main() { int m; char ch; LinkList L; InitList_L(&L); ch=getchar(); while(ch!='Q'){ switch(ch){ case 'C': for(m=0;m<10;m++) if(!ListInsert_L(L,m,2*m))printf("error"); ListPrint_L(L); break; case 'I': ListInsert_L(L,3,77); ListPrint_L(L); break; case 'L': ClearList_L(&L); ListPrint_L(L); break; } getchar(); ch=getchar(); } } 矩阵及其操作 #include "likec.h" #define MAXSIZE 1250 typedef int ElemType; typedef struct { int i,j; ElemType e; }Triple; typedef union{ Triple data[MAXSIZE+1]; int mu,nu,tu;

F SMAtrix Status Input(SMAtrix *M) i int m, n, t, i, j,k printf( please input line, col and numbers: " scanf(%d%d%d", &m, &n, &t) if(mmum: M->nu=n: M->tu=t for(k=1: kml linl l jdatalk] i=i: M->data[k].j=j: M->data [k]e=e return OK void Output(sMAtrix M) I int m, n, t=l: for (m=1: mmu=. nu: T->nu=M. mu: T->tu=M tu if(M tu)I for(col=l: coldata[ql. i=M data lp]. j T->datang]. j=M data [p].i T->datalql. e=M data lp

}TSMatrix; Status Input(TSMatrix *M) { int m,n,t,i,j,k; ElemType e; printf("Please input line,col and numbers:"); scanf("%d%d%d",&m,&n,&t); if(mmu=m; M->nu=n; M->tu=t; for(k=1;km||in||jdata[k].i=i; M->data[k].j=j; M->data[k].e=e; } return OK; } void Output(TSMatrix M) { int m,n,t=1; for(m=1;mmu=M.nu; T->nu=M.mu; T->tu=M.tu; if(M.tu){ q=1; for(col=1;coldata[q].i=M.data[p].j; T->data[q].j=M.data[p].i; T->data[q].e=M.data[p].e; ++q; } }