数据结构上机参考程序.doc

数据结构上机参考程序一元多项式表示及相加程序如下:/Add Polynomial Pa and Pb#include#include#include#includeStuct Term float coef; int expn; struct Term *next;LinkList;LinkList *CreateList_L(int n) int i; LinkList *p,*L; L=(LinkList *)malloc(sizeof(LinkList); L-next=NULL; for(i=n;i0;-i) p=(LinkList *)malloc(sizeof(LinkList); printf(“input coef=”); scanf(“%d”,&p-coef);printf(“n”); printf(“input expn=”); scanf(“%d”,&p-expn);printf(“n”);p-next=L-next; L-next=p; /end of forReturn L;/end of function CreateListChar cmp(int qa_expn,int qb-expn) if(qa_expn=qb_expn) return=; else if(qa_expnqb_expn)return; else returnnext; qb=pb-next; pre=pa; while(qa&qb) switch(cmp(qa-expn,qb-expn) case next; break;case=: sum=qa-coef+qb-coef; if(sum!=0.0) qa-coef=sum;pre=qa; else pre-next=qa-next;free(qa); qa=pre-next;u=qb;qb=qb-next; free(u); break; case: u=qb-next; qb-next=qa;pre-next=qb; pre=qb; qb=u; break; /end of switch if(!qa)pre-next=qb; free(qb); return pa;end of Addpolyn() functionVoid main()LinkList *pa,*pb,*pc,*p;int NodeNum_pa,NodeNum_pb; Printf(“input NodeNum_pa:”); Scanf(“%d”,& NodeNum_pa); printf(“Please input the pa.coef and pa.expn”); pa=CreateList_L(NodeNum_pa); Printf(“input NodeNum_pb:”); Scanf(“%d”,& NodeNum_pb); printf(“Please input the pb.coef and pb.expn”); pb= CreateList_L( NodeNum_pb);Pc=Addpolyn(pa,pb);P=pc;printf(“result:n”);while(p-next) p=p-next; printf(“pc.coef=%d, pc.expn=%dn”, p-coef, p- expn ); /end of while getch();end of main() function行编辑程序。例如：输入：whli#ile(s#*s) outchaputchar(*s=#+);输出：while(*s) putchar(*s+);程序如下：#include#include#define SIZE 100#define char SElemTypetypedef struct SElemType sqSIZE int top; SqStack;void push(SqStack *s,SElemType e) if(s-top= =SIZE)printf(“overflow!n”); elses-top=s-top+1 ;s-sqs-top=e; /Pushvoid pop(SqStack *s) if(s-top=-1)printf(“error!n”); else s-top-;/Popmain() int i; SqStack S; SElemType ch;S.top=-1; printf(“Input:n”);ch=getchar(); while(ch!=$) while(ch!=$&ch!=n) switch(ch) case#:Pop(&S);break;case:s.top=-1;break; default:Push(&S,ch);break; ch=getchar(); printf(“Output:n”); for(i=0;i=s.top;i+) printf(“c%”,s.sqi); s.top=-1; if(ch!=$) printf(“Input:”); ch=getchar(); 快速转置程序#include#define SIZE 100typedef struct int i,j; int e;Triple;typedef struct Triple dataSIZE; int mu,nu,tu;TSMatrix;Main()TSMatrix T,M; int t,p,q,col ,numSIZE,cpotSIZE; printf(“Input M.mu,M.nu,M.tu:”); scanf(“%d,%d,%d”,&M.mu,&M.nu,&M.tu); printf(“n”); printf(“Input Matrix M:n”); for(t=1;t=M.tu;t+) scanf(“%d,%d,%d”,&M.datat.i,&M.datat.j ,&M.datat.e); printf(“n”);书中代码建立排序的二叉树和遍历二叉树 #includetypedef struct bnode int data; struct bnode *left,*right; BiTree; BiTree * insert(BiTree *b, BiTree *s) if(b=NULL) b=s; else if(s-data=b-data) ; else if(s-datadata) b=insert(b-left,s); else if(s-datab-data) b=insert(b-right,s); return b;BiTree * createbitree(BiTree* bt) int x; BiTree *s; printf(“Input;”); do scanf(“%d”,&x); s=(bnode *)malloc(sizeof(bnode); s-data=x; s-left=NULL; s-right=NULL; bt=insert(bt,s); while(x!=-1); return bt;void inorder(BiTree * bt) if(bt != NULL) inorder(bt-lchild); printf(%d ,bt-data); inorder(bt-rchild); void main() BiTree*root; root=NULL; root=createbitree(BiTree* root); inorder(BiTree * root);图的遍历(深度优先)#include#define MAX_VERTEX_NUM 20typedef int VertexType;typedef struct ArcNodeint adjvex;Struct ArcNode *nextarc;ArcNode;typedef struct VnodeVerterType data;ArcNode *firstarc;VNode,AdjListMAX_VERTEX_NUM ;int n;boll visitedMAX_VERTEX_NUM ;Void create(AdjList *g)ArcNode *p,*q;int m,s,d,i;Printf(“请输入顶点数和边数:”);Scanf(“%d,%d”,&n,&m);for(i=1;i=n;i+)gi.data=i;gi.firstarc=NULL;for(i=1;i=m;i+)Printf(“第%d条边的起始顶点编号和终止顶点编号:”,i);Scanf(“%d,%d”,&s,&d);While(sn|dn)Printf(“编号超出范围,重新输入:”);Scanf(“%d,%d”,&s,&d);P= malloc(sizeof(ArcNode);P-adjvex=d;P-nextarc=NULL;if(!gs.firstarc) gs.firstarc=p;else q=gs.firstarc; while(q-nextarc) q=q-nextarc; q-nextarc=p; Void dfs(AdjList *g,int m)int w;ArcNode *p;if(!visitedm) printf(“%d”,gm.data);Visitedm=true;P=gm.firstarc;While(p)W=p-adjvex;if(!visitedw) dfs(g,w);P=p-nextarc;Void main()int i;AdjList g;Create(&g);for(i=1;i=n;i+) visitedi=false;for(i=1;i=n;i+) dfs(&g,i);参见书168页图输入:8,181,21,32,12,42,53,13,63,74,24,85,25,86,36,77,37,68,48,5输出:12485367广度搜索 void bfs(