实验源程序.doc

附录：实验源程序实验一 + 实验二、线性表操作程序1：顺序存储的线性表和运算#include#define MAXSIZE 100int listMAXSIZE; /*定义一个100的一维数组*/int n;/*insert in a seqlist*/ /*插入一个空表格*/int sq_insert(int list, int *p_n, int i, int x)int j; if (i*p_n) return(1); if (*p_n=MAXSIZE) return(2); for (j=*p_n+1; ji; j-) listj=listj-1; listi=x; (*p_n)+; return(0); 把x插入到listi这个位置，listj之后的元素向后移动，之后再j-，直到ji/*delete in a seq list*/ /*删除一个表格*/int sq_delete(int list, int *p_n, int i) int j; if (i=*p_n) return(1); for (j = i+1; j=*p_n; j+) listj-1 = listj; (*p_n)-; return(0); void main() int i,x,temp; printf(please input the number for nn); printf(n=); scanf(%d,&n); /*在键盘上接收n*/ for (i=0; i=n; i+) printf(list%d=,i); scanf(%d,&listi); /*当i=n时，依次输出list0至 printf(The list before insertion isn); for (i=0; i=n; i+) printf(%d ,listi); printf(n); printf(please input the position where you want to insert a valuenposition=); /*请输入你想要删除的位置*/ scanf(%d,&i); printf(please input the value you want to insert.nx=); scanf(%d,&x); temp=sq_insert(list,&n,i,x); switch(temp) case 0:printf(The insertion is successful!n); printf(The list is after insertion isn);插入的元素在线性表 for(i=0; i=n; i+) printf(%d ,listi); printf(n); printf(%dn,n); break; case 1: case 2:printf(The insertion is not successful!n);break; /*deleting*/ printf(The list before deleting isn); for (i=0; i=n; i+) printf(%d ,listi); printf(n); printf(please input the position where you want to delete a valuenposition=);输入你想要删除的位置 scanf(%d,&i); temp=sq_delete(list,&n,i); switch(temp) case 0:printf(The deleting is successful!n); printf(The list is after deleting isn); 删除的元素在线性表 for(i=0; i=n; i+) printf(%d ,listi); printf(n); printf(%d,n); break; case 1:printf(The deleting is not successful!);break; 关于元素的插入和删除程序2链式存储的线性表和运算#include#include struct node char data; struct node *next; ;typedef struct node NODE;/*This function creates a link_list with N nodes.*/NODE *create_link_list(int n)int i; NODE *head, *p, *q; if (n=0) return NULL; head = (NODE *) malloc(sizeof(NODE); p = head; 指针指向线性表的头结点 printf(Please input %d chars for the link listn,n); for (i=0; idata); q=(NODE *)malloc(sizeof(NODE); printf(test3n); p-next=q; p=q; scanf(%c ,&(p-data); getchar(); p-next=NULL; return (head);/*This function inserts a node whose value is b*/*before the node whose value is a, if the node is not exist,*/*then insert it at the end of the list*/void insert(NODE *p_head, char a, char b) NODE *p, *q; q = (NODE *)malloc(sizeof(NODE); q-data = b; q-next =NULL; if (* p_head = NULL) * p_head = q; else p=(NODE*)malloc(sizeof(NODE); p = * p_head; while (p-data != a & p-next != NULL) p = p-next; q-next = p-next; p-next = q; /*The function deletes the node whose value is a,*/*if success, return 0, or return 1*/int deletenode(NODE *p_head, char a) NODE *p, *q; q=*p_head; if (q=NULL) return(1); if (q-data = a) * p_head = q-next; free(q); return (0); else while (q-data != a & q-next != NULL) p = q; q = q-next; if (q-data = a) p-next = q-next; free(q); return(0); else return(1); void main() NODE *my_head,*p; /* create a link list with m nodes */ int m; char ch_a,ch_b; printf(please input the number of nodes for the link_listnm=); scanf(%d,&m); getchar(); printf(test1n); my_head = (NODE *) malloc(sizeof(NODE); my_head=create_link_list(m); /*Output the link list*/ printf(The link list is like:n); p=my_head; while (p != NULL) printf(%c ,p-data); p=p-next; printf(n); /*insert a node whose value is b before a*/ printf(Please input the position for an ch_a=); getchar(); scanf(%c,&ch_a); getchar(); printf(Please input the value that you want to insertn ch_b=); scanf(%c,&ch_b); getchar(); insert(&my_head,ch_a,ch_b); printf(The link list after insertion is like:n); p=my_head; while (p != NULL) printf(%c ,p-data); p=p-next; printf(n); /*delete a node whose value is a*/ printf(Please input the position for a a=); scanf(%c,&ch_a); getchar(); deletenode(&my_head,ch_a); printf(The link list after deleting is like:n); p=my_head; while (p != NULL) printf(%c ,p-data); p=p-next; printf(n);实验三、栈和队列的应用程序1：顺序栈的实现和运算#include#define MAXN 26char stackMAXN;int top=0;int push(char x) if (top = MAXN) return(1); stacktop+=x; return(0);int pop(char *p_y) if (top = 0) return(1); *p_y = stack-top; return(0);void main() int i; char ch_x,ch_y; printf(input the char you want to pushn); scanf(%c,&ch_x); while(ch_x!=0) if (push(ch_x)=1) printf(failure!n); else printf(success!n); printf(input a char for ch_x to pushnch_x=); getchar(); scanf(%c,&ch_x); i=0; while(stacki!=0) printf(%c , stacki); i+; if (pop(&ch_y)=1) printf(failure!n); else printf(success!n); printf(The pop char is %cn,ch_y); for (i=top-1; i=0; i-) printf(%c , stacki);程序2：链栈的实现和运算#include #include struct nodechar data; struct node *link;typedef struct node NODE;NODE * top = NULL;void push_l(char x) NODE *p; p = (NODE * )malloc(sizeof(NODE); p-data = x; p-link = top; top = p;int pop_l(char *p_y) NODE *p; if (top = NULL) return(1); * p_y = top-data; p = top; top = top-link; free(p); return(0);void main() NODE *p; char ch_x,ch_y; printf(input the char you want to pushn); scanf(%c,&ch_x); while(ch_x!=0) push_l(ch_x); getchar(); scanf(%c,&ch_x); p=(NODE*)malloc(sizeof(NODE); p=top; while(p!=NULL) printf(%c ,p-data); p=p-link; printf(n); if (pop_l(&ch_y)=1) printf(failure!n); else printf(success!n); printf(The pop char is %cn,ch_y); p=(NODE*)malloc(sizeof(NODE); p=top; while(p!=NULL) printf(%c ,p-data); p=p-link; printf(n);程序3：顺序队列的实现和运算#include#define MAXN 26char qMAXN;int head = -1, tail = -1;int en_queue(char x ) if (tail = MAXN-1) return(1); q+tail = x; return(0);int de_queue(char *p_y ) if (head = tail) return(1); *p_y = q+head; return(0);void main() int i; char ch_x,ch_y; printf(input the char you want to enqueuen); scanf(%c,&ch_x); while(ch_x!=0) if (en_queue(ch_x)=1) printf(failure!n); else printf(success!n); printf(input a char for ch_x to enqueuench_x=); getchar(); scanf(%c,&ch_x); i=1; while(qi!=0) printf(%c , qi); i+; if (de_queue(&ch_y)=1) printf(failure!n); else printf(success!n); printf(The dequeue char is %cn,ch_y); for (i=head+1; i=tail; i+) printf(%c , qi);程序4：链式队列的实现和运算#include#includestruct nodechar data; struct node * link;typedef struct node NODE;NODE *head, *tail;void en_queue_l(char x) NODE *p; p = (NODE *)malloc(sizeof(NODE); p-data = x; p-link = NULL; if (head = NULL) head = p; else tail-link = p; tail = p;int de_queue_l(char *p_y) NODE *p; if (head = NULL) return(1); *p_y = head-data; p = head; head = head-link; free(p); return(0);void main() NODE *p; char ch_x,ch_y; printf(input the char you want to enqueuen); scanf(%c,&ch_x); while(ch_x!=0) en_queue_l(ch_x); getchar(); scanf(%c,&ch_x); p=(NODE*)malloc(sizeof(NODE); p=head; while(p!=NULL) printf(%c ,p-data); p=p-link; printf(n); if (de_queue_l(&ch_y)=1) printf(failure!n); else printf(success!n); printf(The dequeue char is %cn,ch_y); p=(NODE*)malloc(sizeof(NODE); p=head; while(p!=NULL) printf(%c ,p-data); p=p-link; printf(n);程序5：循环队列的实现和运算#include#include#define MAXN 26char qMAXN;int head = 0, tail = 0;int en_c_q(char x) tail = (tail + 1) % MAXN; if (tail = head) if (tail = 0) tail = MAXN-1; else tail-; return(1); qtail = x; return(0);int de_c_q(char *p_y) if (head = tail) return(1); head = (head+1) % MAXN; *p_y = qhead; return(0);void main() int i; char ch_x,ch_y; printf(input the char you want to enqueuen); scanf(%c,&ch_x); while(ch_x!=0) if (en_c_q(ch_x)=1) printf(failure!n); else printf(success!n); printf(input a char for ch_x to enqueuench_x=); getchar(); scanf(%c,&ch_x); i=1; while(qi!=0) printf(%c , qi); i+; if (de_c_q(&ch_y)=1) printf(failure!n); else printf(success!n); printf(The dequeue char is %cn,ch_y); for (i=head+1; i=tail; i+) printf(%c , qi);实验四、树和二叉树的操作程序1：二叉树的实现和运算#include #include #include typedef struct btnode char data; /*suppose the data fields type is char*/ struct btnode *lchild; /*left pointer field */ struct btnode *rchild; /*right pointer field */ NODE;void main() NODE *root,*q,n; NODE *create(NODE *p); void preorder(NODE *root); void inorder(NODE *root); void postorder(NODE *root); int t; q=&n; root=create(q); printf(At the first,we create a treen); printf(Please input nodes of treen); if (root=NULL) printf(Its an empty tree!n); else printf(n1.The preordetraverse n); printf( 2.The inordertraverse n); printf( 3.The postordertraverse n); printf( Please choose a kind of ordern); scanf(%d,&t); switch (t) case 1: preorder(root); break; case 2: inorder(root); break; case 3:postorder(root); break; default: printf( The error!); NODE * create(NODE *p) /*create the structure of binary tree */ char ch; NODE *t; scanf(%c,&ch); if(ch= ) p=NULL; else p-data=ch; t=(NODE *)malloc(sizeof(NODE); p-lchild=create(t); t=(NODE*)malloc(sizeof(NODE); p-rchild=create(t); return p;void preorder(NODE *root) /*travel the tree using preorder */ if (root!=NULL) printf( %c, root-data); preorder(root-lchild); preorder(root-rchild); return;void inorder (NODE *root) /*travel the tree using inorder */ if (root!=NULL) inorder(root-lchild); printf( %c , root-data); inorder(root-rchild); return;void postorder(NODE *root) /*travel the tree using postorder */ if (root!=NULL) postorder (root-lchild); postorder (root-rchild); printf( %c , root-data); return;实验五、图的操作程序1：图的实现和运算#include #include #include struct node int vertex; struct node *next; ;struct headnode int vert; struct node *link; ;main() int t,n,i,visit100; int d100; struct headnode *adjlist( ); void dfs( ); void wfs( ); struct headnode *head ; printf(input the sum of nodes:n); scanf(%d,&n); for(i=0;in;i+) scanf(%d,&di); head=adjlist(d,n); printf(1 depth traveln); printf(2 width traveln); printf(please input the way of travellingn); scanf(%d,&t); switch (t) case 1: for(i=0;in;i+) visiti=0; dfs(head,1,visit); break; case 2: wfs(head,n); break; default: printf(The error!); struct headnode *adjlist(d,n) int n; int d ; struct headnode head100 ; struct node *q,*p ; int i,v1; for(i=0; i=0) p=(struct node *) malloc(sizeof(struct node); p-vertex=v1; p-next=headi.link ; headi.link=p; scanf(%d, &v1); return(head);void dfs(head,k,visit) struct headnode head1000; int k,visit ; int i; struct node *p; printf( v%d,k); visitk=1; p=headk-1.link; while ( p!=NULL) if (visitp-vertex=0) dfs(head,p-vertex,visit); p=p-next; ;return;void wfs(head,n)struct headnode *head;int n;int visit1000,q1000,f,r,k,u,m;struct node *p;for(k=0;kvert; r=r+1; visitm=1; while (f!=r) u=qf; f=f+1; printf( v%d,u); p=(head+u-1)-link; while (p!=NULL) if (visitp-vertex-1=0) qr=p-vertex; r=r+1; visitp-vertex-1=1; p=p-next; 程序2：最小生成树#define M 30#define MAX 99#include #include main()void prim();int i,j,n,g100100;printf(input the sum of nodes:n);scanf(%d,&n);printf(input the content of adjtrix:n);for (i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&gij);prim(g,1,n);void prim(g,k,n)int g100100;int k,n;int i,j,min,p;struct int adjvex; int lowcost; closedgeM;for(i=1;i=n;i+) if(i!=k) closedgei.adjvex=k; closedgei.lowcost=gki; closedgek.lowcost=0; for(i=1;i=n;i+) p=1;min=MAX; for(j=1;j=n;j+) if(closedgej.lowcost!=0 & closedgej.lowcostmin) min=closedgej.lowcost; p=j; if (min!=MAX) printf(%d-%d %dn,closedgep.adjvex,p,min); closedgep.lowcost=0; for(j=1;j=n;j+) if (gpjclosedgej.lowcost) closedgej.lowcost=gpj; closedgej.adjvex=p; 程序3：最短路径#define M 30#define MAX 99#include #include main() void prim();int i,j,n,g100100;printf(input the sum of nodes:n);scanf(%d,&n);printf(input the content of adjtrix:n);for (i=1;i=n;i+) for(j=1;j=n;j+) scanf(%d,&gij);prim(g,1,n);void prim(g,k,n)int g100100;int k,n;int i,j,min,p;struct int adjvex; int lowcost; closedgeM;for(i=1;i=n;i+) if(i!=k) closedgei.adjvex=k; closedgei.lowcost=gki; closedgek.lowcost=0; for(i=1;i=n;i+) p=1;min=MAX; for(j=1;j=n;j+) if(closedgej.lowcost!=0 & closedgej.lowcostmin) min=closedgej.lowcost; p=j; if (min!=MAX) printf(%d-%d %dn,closedgep.adjvex,p,min); closedgep.lowcost=0; for(j=1;j=n;j+) if (gpjclosedgej.lowcost) closedgej.lowcost=gpj; closedgej.adjvex=p; 实验六、各种查找操作程序1：线性表查