数据结构代码应用举例.doc

2.2.3 顺序表的应用举例#define MAX 100/*定义表长不超过100*/typedef struct nodeint dataMAX; int lenth; LIST; /*lenth变量存放的是表的实际长度，表中的元素存在数组data中， 并且从下标1的单元开始存放。*/#include void merge_list(LIST la,LIST lb ,LIST *lc)/*两个有序表合并*/int i,j,k; i=j=k=1; while(i=la.lenth&j=lb.lenth) if(la.dataidatak=la.datai; k+;i+; else lc-datak=lb.dataj; k+;j+; while(idatak=la.datai; k+;i+; while(jdatak=lb.dataj; k+;j+; lc-lenth=k-1; return;Void main()LIST la,lb,lc; int i,k,m; printf(请输入la顺序表元素，元素为整型量，用空格分开，-99为结束标志：); la.lenth=0;scanf(%d,&i); while(i!=-99)/*输入la顺序表元素，建立有序表*/ k=la.lenth; while (k=1)&(i=k+1;m-) la.datam+1=la.datam; la.datak+1=i;la.lenth+; scanf(%d,&i);printf(nn请输入lb顺序表元素，元素为整型量，用空格分开，-99为结束标志：);lb.lenth=0;scanf(%d,&i);while(i!=-99)/*输入lb顺序表元素，建立有序表*/ k=lb.lenth; while (k=1)&(i=k+1;m-) lb.datam+1=lb.datam; lb.datak+1=i;lb.lenth+; scanf(%d,&i);printf(nla有序表元素列表：);for(i=1;i=la.lenth;i+) printf(%4d,la.datai);printf(n);printf(nlb有序表元素列表：);for(i=1;i=lb.lenth;i+) printf(%4d,lb.datai);printf(n);merge_list(la,lb,&lc);printf(nlc有序表元素列表：);for(i=1;i=lc.lenth;i+) printf(%4d,lc.datai);printf(n);2.3.5 单链表应用举例#include #include typedef struct pnode int coef; /*系数以整型为例*/ int exp; /*指数*/ struct pnode*next;/*指针*/PNODE;PNODE *creat_link(int n) /*顺序输入n个元素的值，建立带表头结点的单链表*/ PNODE *head,*p,*s; int i; head=(PNODE *)malloc(sizeof(PNODE);/*head为表头指针*/ head-next=NULL; /*先建立一个带表头结点的空表*/ p=head; printf(enter coef,exp:n); for(i=1;icoef,&s-exp); /*输入结点的系数和指数*/ s-next=NULL; p-next=s;p=s; /*新结点插入表尾*/ return(head);void padd(PNODE *pa,PNODE *pb) /*以pa和pb为头指针的单链表分别表示两个多项式，实现pa=pa+pb */ PNODE *pre,*qa,*q,*qb; int sum; pre=pa; /*pre始终指向当前和多项式的最后一个结点*/ qa=pa-next;qb=pb-next; /*qa、qb分别指向pa、pb中的当前结点*/ while (qa&qb) /*qa、qb均非空*/ if(qa-exp=qb-exp) /*指数相同*/ sum=qa-coef+qb-coef; if(sum) qa-coef=sum;pre=qa; else pre-next=qa-next;free(qa); qa=pre-next; q=qb;qb=qb-next;free(q); else /*指数不相同*/ if(qa-expqb-exp)pre=qa;qa=qa-next; else pre-next=qb;pre=qb; qb=qb-next;pre-next=qa; if(qb)pre-next=qb; /*链接pb 中剩余结点*/ free(pb);void print_link(PNODE *h)PNODE *p; p=h-next; while(p-next) printf(%d%d+,p-coef,p-exp);p=p-next; if(p-exp) printf(%d%dn,p-coef,p-exp);else printf(%dn,p-coef); void main() PNODE *ha,*hb; /*多项式链表的头指针*/ int la,lb; scanf(%d,%d,&la,&lb); /*输入多项式A和B的项数*/ ha=creat_link(la); print_link(ha); hb=creat_link(lb); print_link(hb); padd(ha,hb); print_link(ha); 实 训 1参考程序#include #include /改成 #include typedef struct node int number; /* 人的序号 */ int cipher; /* 密码 */ struct node *next; /* 指向下一个结点的指针 */NODE;NODE *CreatList(int num) /* 建立循环链表 */ int i; NODE *ptr1,*head; if(ptr1=(NODE *)malloc(sizeof(NODE)=NULL) perror(malloc); return ptr1; head=ptr1; ptr1-next=head; for(i=1;inext=(NODE *)malloc(sizeof(NODE)=NULL) perror(malloc); ptr1-next=head; return head; ptr1=ptr1-next; ptr1-next=head; return head;voidmain() int i,n=30,m; /* 人数n为30个 */ NODE*head,*ptr; int randomize(); head=CreatList(n); for(i=1;inumber=i; head-cipher=rand(); head=head-next; m=rand(); /* m取随机数 */i=0; while(head-next!=head) /* 当剩下最后一个人时，退出循环 */ if(i=m) ptr=head-next; /* ptr记录数到m的那个人的位置 */ printf(number:%dn,ptr-number); printf(cipher:%dn,ptr-cipher); m=ptr-cipher; /* 让m等于数到m的人的密码 */ head-next=ptr-next; /* 让ptr从链表中脱节，将前后两个结点连接起来 */ head=head-next; /* head移向后一个结点 */ free(ptr); /* 释放ptr指向的内存 */ i=0; /* 将i重新置为0，从0再开始数 */ else head=head-next; i+; printf(number:%dn,head-number); printf(cipher:%dn,head-cipher); free(head); /* 让最后一个人也出列 */3.1.2 栈的顺序存储及其基本操作的实现2进栈#include #define MAX 10int sMAX; /*定义数组t，用来存储栈的元素，以整数为例*/int top; /*定义栈顶指针为top*/int push(int s,int x)/*x为要插入的新元素*/ if(top=MAX) printf(stack overflown); /*栈满信息*/ return(0); else stop=x; /*数据入栈*/ top=top+1; /*当栈不满时，栈顶加1*/ printf(okn); return(1); void main() /*主程序*/ int aMAX=1,2,3,4,5; int x=56,i; top=5; if(push(a,x) for(i=0;itop;i+) printf(%3d,ai); /*函数调用*/ 例如栈为1,2,3,4,5，想让元素“56”进栈，调用进栈函数后，栈的内容成为1,2,3,4,5,56。3出栈#include #define MAX 10int sMAX;int top;int pop(int s,int *y) /*参数传递要用指针*/ if(top=0) /*如果栈空*/ printf(stack is emptyn); /*输出栈空信息*/ return 0; else /*如果栈不空*/ top=top-1; /*栈顶指针减1*/ *y=stop; printf(okn); return 1; void main() /*主程序*/ int aMAX=1,2,3,4,5; int y; top=5; if(pop(a,&y) printf(%d,y); /*输出出栈元素*/5多个栈共享存储空间（1）进栈#define MAX 50int sMAX;int t1,t2;int pushd ( int s,int i, int x)/*元素x进第i个栈(i=1,2)*/ if (i2) return(0); if (t2+1=t1) return(0); if(i=1) st1=x; t1+; else st2=x; t2-; return(1);void main() /* 主函数*/int i,j,x,p; for(i=0;i40;j-) /*第二栈输入数据，九个数据*/ scanf(%d,&sj); t2=40; printf(请输入p和x，中间用逗号:n); scanf(%d,%d,&p,&x); /*往第p个栈插入数据x*/ if (pushd ( s,p,x) for (i=0;it2;j-) printf(%5d,sj); （2）出栈#define MAX 50int sMAX;int t1,t2;int popd ( int s, int i)/*第i个栈退栈*/ if (i2) return(0); if (i=1) if(t1=0) return(0); else t1-; else if(t2=MAX-1) return(0); else t2+; return(1);void main() /* 主函数*/int i,j,x; for(i=0;i40;j-)/*第二栈输入数据*/ scanf(%d,&sj); t2=40; scanf(%d,&x); /*第x个数据要进行出栈操作*/ if (popd ( s,x) for (i=0;it2;j-) printf(%5d,sj); 3.1.3 栈的链式存储及其基本操作的实现1进栈#include #include typedef struct node int data; /*这里以整型数据为例*/ struct node*next; /*指针类型，存放下一个结点地址*/NODE;NODE *create_linkstack() /*建立链栈*/ NODE*top,*g; /*定义栈顶指针*/ char j; int a; top=NULL; j=getchar(); while(j!=?) /*判断生成链栈结束标志*/ scanf(%d,&a); g=(NODE*)malloc(sizeof(NODE); g-data=a; g-next=top; top=g; j=getchar(); return(top); /*返回栈顶指针*/NODE * pushstack(NODE*top,int x) NODE*p; /*定义结点p*/ p=(NODE*)malloc(sizeof(NODE); p-data=x; /*将要插入的数据x存储到结点p的数据域中*/ p-next=top; /*将p结点的指针修改为原top的指针*/ top=p; /*将top修改为p*/ return(top); void main() /*主程序*/ int y=34; /*将入栈的元素*/ NODE*top,*p; top=create_linkstack(); /*建立链栈*/ top=pushstack(top, y); /*入栈*/ p=top; while (p!=NULL) printf(%5d,p-data); p=p-next; 2出栈#includetypedef struct node int data; struct node*next;NODE; NODE*popstack(NODE*top，int*q)NODE*p; /*定义q结点*/ if(top!=NULL) /*如果栈不空*/ p=top; /*p指向栈顶结点*/ *q=top-data;/*将要读出的数据放入*q中*/ top=top-next; /*修改top指针*/ free(p); return(top); /*返回栈顶指针*/main() /*主程序*/ int b; NODE*top; top=crea_linkstack();/ 建立链栈的函数见上面*/top=popstack(top,&b);printf(%5d,b); 3.2 队 列3.2.2 队列的顺序存储及其基本操作的实现1进队#define MAX 10int qMAX=1,2,3,4,5;int front=-1,rear=-1;int inqueue(int x)/*插入元素为x*/ if (rear=MAX-1) /*如果队满*/printf(overflown);/*打印溢出*/ return(rear); else /*如果队不满*/ q+rear=x； /*队尾指针加1*/ return(rear);/*插入成功返回队尾指针*/ main() /*主程序*/ int i，h=6; /*将h入队*/ rear=4; rear=inqueue(h); for(i=front+1;i=rear;i+) printf(%d，qi); /*显示整个队的内容*/ 2出队#define MAX 10int qMAX=1,2,3,4,5;int front=-1,rear=-1;int delqueue(int *y) /*出队，出队的值放在y中*/if(front=rear) /*如果队空*/ printf(queue empty)return(front); else /*如果队不空*/ *y=q+front; /*头指针加1，队首结点送入指针y所指向的变量中*/ return(front); main() /*主程序*/ int i,x; rear=4;front=delqueue(&x); for(i=front+1;i=rear;i+) printf(%d,qi); /*显示整个队列*/ 3循环队列（1）进队#define MAX 10int qMAX=1,2,3,4,5;int incq(int x，int*fp,int*rp) int front，rear; front=*fp; rear=*rp; if(rear+1)%MAX=front)/*如果队满*/ return(0); else /*如果队不满*/ rear=(rear+1)%MAX; /*队尾指针加1*/ qrear=x; /*将新元素x插入到队尾*/ *rp=rear; return(1); /*进队成功*/ main() /*主程序*/ int c, i, y=23，a，b; a=0; /*a指向队首*/ b=4; /*b指向队尾*/ c=incq(y,&a,&b); if(c) for(i=0;i=b;i+) printf(%d,qi);/*显示整个队的内容*/（2）出队#define MAX 10 int qMAX=1,2,3,4,5;int delcq(int cq,int *x,int*fp,int*rp) int front,rear; front=*fp; rear=*rp; if(rear=front)/*如果队空*/ return(0); else /*如果队不空*/ front=(front+1)%MAX; /*队首指针加1*/ *x=cqfront; /*将队首元素存入x中*/ *fp=front; return(1); /*出队成功*/ main() /*主程序*/ int front=0,rear=4,x,flag,i; flag=delcq(q，&x，&front,&rear); if(flag) printf(%dn,x); for(i=front;i=rear;i+) printf(%5d,qi); 3.2.3 队列的链式存储及其基本操作的实现1入队#include#include typedef struct node int data; struct node*next;NODE;NODE *front,*rear;NODE *crea_linkq() NODE *s; int x,tag; printf(enter flag); scanf(%d,&tag); front=(NODE *)malloc(sizeof(NODE); front-data=tag; rear=front; printf(enter data x:); scanf(%d,&x); while(x!=tag) s=(NODE *) malloc (sizeof (NODE) s-data=x; rear-next=s; rear=s; scanf(%d,&x); rear-next=NULL; return(front);NODE*pushq(int x) NODE *p; p=(NODE*)malloc(sizeof(node); /*向系统申请一存储单元p*/ p-data=x; /*将要插入的元素x放入p数据域*/ p-next=NULL; /*将p结点的指针域置为NULL*/ rear-next=p; /*原尾结点的指针指向新结点p*/ rear=p; /*新元素入队后的尾结点*/ return(rear);/*返回尾结点*/main() /*主程序*/ NODE *p; int x=34; /*x为要入队的元素*/ front=crea_linkq(); /*调用建立链队的函数，并将front指向队首，rear指向队尾*/ rear=pushq(x); /*调用入队函数*/ p=front-next; /*显示整个队列*/ while (p!=NULL) printf(%d,p-data); p=p-next; 2出队#include#include typedef struct node int data; struct node*next;NODE;NODE *front,*rear;NODE*popq(NODE*front,NODE*rear) int y; NODE*p; if(front=rear) /*判断队空*/ return(NULL); else /*队不空*/ p=front-next; /*将头元素next指针放在p中*/ front-next=p-next; if(p-next=NULL) /*在只有一个元素的情况下*/ rear=front;/*出队后，队空*/ y=p-data; free(p); return(front); /*返回front*/ main() /*主程序*/ NODE*p; front=crea_linkq(); /*调用建立链队的函数，见前述*/ front=popq(front, rear); p=front-next; /*显示整个队列*/ while (p!=NULL) printf(%d,p-data); p=p-next; 实 训 2参考程序#include stdio.h #define N 2 /*停车场容量*/ #define M 5 /*停车单价*/ #define True 1 #define False 0 typedef struct int num; /*车牌号*/ int arrtime; /*到达/离开时间*/ ELEMTP; /*顺序栈的数据元素类型*/ typedef struct ELEMTP elemN; int top; SqStack; /*顺序栈类型*/ typedef struct node int num; /*车牌号/便道上的车辆数量*/ struct node *next; QNode; /*链队列的数据元素类型*/ typedef struct QNode *front, *rear; LQueue; /*链队列类型*/ void InitStack_Sq (SqStack *s); /*初始化栈*/ int Push_Sq(SqStack *s,ELEMTP x); /*入栈*/ ELEMTP Pop_Sq(SqStack *s); /*出栈*/ void InitQueue_L(LQueue *q); /*初始化队列*/ void EnQueue_L (L LQueue *q,int num1); /*入队列*/ int DelQueue_L(LQueue *q); /*出队列*/ void Arrive (SqStack *s1, LQueue *q,ELEMTP x) /*车辆x进入停车场*/ int f; f=Push_Sq(s1,x); if (f=False) /*停车场栈s1已满入便道q */ EnQueue_L(q,x.num); printf(第%d号车停在便道第%d车位上n,x.num,q-front-num); else printf(第%d号车停在停车场第%d车位上n,x.num,s1-top); /* Arrive */ void Delive (SqStack *s1,SqStack *s2, LQueue *q,ELEMTP x) /*车辆x离开停车场*/ int n,f=False; ELEMTP y; QNode *p; while (s1-top0) & (f!=True) /*在栈s1中寻找车辆x */ y=Pop_Sq(s1); if (y.num!=x.num) n=Push_Sq(s2,y); else f=True; if (y.num=x.num) /*寻找到车辆x*/ printf(第%d号车应收费%d元n,y.num,(x.arrtime-y.arrtime)*M); while (s2-top0) /*将栈s2中的车辆倒回到栈s1中*/ y=Pop_Sq(s2); f=Push_Sq(s1,y); n=DelQueue_L(q); if (n!=NULL) /*便道q上的第一辆车入栈s1*/ y.num=n; y.arrtime=x.arrtime; f=Push_Sq(s1,y); printf(第%d号车停在停车场第%d号车位上n,y.num,s1-top); else /*栈s1中未找到车辆x*/ while (s2-top0) /*将栈s2中的车辆倒回到栈s1中*/ y=Pop_Sq(s2); f=Push_Sq(s1,y); p=q-front; /*在便道q上找到车辆x*/ f=False; while (f=False & p-next!=NULL) if (p-next-num!=x.num) p=p-next; else p-next=p-next-next; q-front-num-; if (p-next=NULL) q-rear=q-front; printf(第%d号车离开便道n,x.num); f=True; if (f=False) printf(输入数据错误，停车场和便道上均无%d号车n,x.num); /* Delive */ void Display(SqStack *s1, LQueue *q) /*显示停车场的状况*/ int k; QNode *p; printf(停车场状况:n); if(s1-top!=0) printf(车道 车号n); for(k=0;ktop;k+) printf(%d %dn,k+1,s1-elemk.num); else printf(停车场没有车辆n); printf(便道状况:n); if(q-front-num) printf(车道 车号n); for(k=1,p=q-front-next;p;p=p-next) printf(%d %dn,k+,p-num); else printf(便道没有车辆n); /* Display */ void main() char ch1,ch2; SqStack *s1,*s2; LQueue *q; ELEMTP x; int flag; s1=(SqStack *) malloc (sizeof(SqStack); s2=(SqStack *) malloc (sizeof(SqStack); q=(LQueue *) malloc (sizeof (LQueue); InitStack_Sq(s1); InitStack_Sq(s2); InitQueue_L (q); flag=True; while(flag) printf(请输入您的选择n); printf(S-显示停车场状况n); printf(A-车辆到达n); printf(D-车辆离开n); printf(E-程序结束n); ch1=getchar(); switch (ch1) case S: Display(s1,q);break; case A: printf(输入数据:车牌号，到达时间：); scanf(%d,%d,&x.num,&x.arrtime); Arrive(s1,q,x);break; case D: printf(输入数据:车牌号，离开时间：); scanf(%d,%d,&x.num,&x.arrtime); Delive(s1,s2,q,x);break; case E: flag=False; printf(程序正常结束n); break; default: printf(输入数据错误，重新输入n); ch1=getchar(); /*main*/ void InitStack_Sq (SqStack *s) s-top=0; int Push_Sq(SqStack *s,ELEMTP x) if (s-top=N) return (False); else s-elems-top=x;s-top+; return(True); ELEMTP Pop_Sq(SqStack *s) ELEMTP x; if (s-top=0) x.num=NULL; x.arrtime=NULL; return(x); else s-top-; return (s-elems-top); void InitQueue_L(LQueue *q) q-front=(QNode *)malloc(sizeof(QNode); q-rear=q-front; q-front-next=NULL; q-front-num=0; void EnQueue_L(LQueue *q,int num1) QNode *p; p=(QNode *)malloc(sizeof(QNode); p-num=