《数据结构代码应用举例》由会员分享,可在线阅读,更多相关《数据结构代码应用举例(54页珍藏版)》请在金锄头文库上搜索。
1、2.2.3 顺序表的应用举例#define MAX 100/*定义表长不超过 100*/ typedef struct node int 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(idatak=la.datai;k+;i+;elselc-datak=lb.dataj;k+;j+;while(idatak
2、=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“,while(i!=-99)/*输入 la 顺序表元素,建立有序表*/k=la.lenth;while (k=1)m-) la.datam+1=la.datam;la.datak+1=i;la.lenth+;scanf(“%d“, printf(“nn 请输入
3、lb 顺序表元素,元素为整型量,用空格分开,-99 为结束标志:“); lb.lenth=0;scanf(“%d“, while(i!=-99)/*输入 lb 顺序表元素,建立有序表*/k=lb.lenth;while (k=1)m-) lb.datam+1=lb.datam;lb.datak+1=i;lb.lenth+;2scanf(“%d“, printf(“nla 有序表元素列表:“); for(i=1;i #include typedef struct pnode int coef; /*系数以整型为例*/int exp; /*指数*/struct pnode*next;/*指针*/
4、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-next=NULL;p-next=s;p=s; /*新结点插入表尾*/return(head); void padd(PNODE *pa,
5、PNODE *pb) /*以 pa 和 pb 为头指针的单链表分别表示两个多项式,实现 pa=pa+pb */PNODE *pre,*qa,*q,*qb;int sum;pre=pa; /*pre 始终指向当前和多项式的最后一个结点*/3习题答案附录附录qa=pa-next;qb=pb-next; /*qa、qb 分别指向 pa、pb 中的当前结点*/while (qaif(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-e
6、xpqb-exp)pre=qa;qa=qa-next;elsepre-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,
7、*hb; /*多项式链表的头指针*/int la,lb;scanf(“%d,%d“, /*输入多项式 A 和 B 的项数*/ha=creat_link(la);print_link(ha);hb=creat_link(lb); print_link(hb);padd(ha,hb);print_link(ha); 4实 训 1 参考程序#include #include /改成 #include typedef struct node int number; /* 人的序号 */int cipher; /* 密码 */struct node *next; /* 指向下一个结点的指针 */ NOD
8、E;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; void mai
9、n() int i,n=30,m; /* 人数 n 为 30 个 */NODE*head,*ptr;int randomize();head=CreatList(n);for(i=1;inumber=i;5习题答案附录附录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(
10、“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 再开始数 */elsehead=head-next;i+;printf(“number:%dn“,head-number);printf(“cipher:%dn“,head-cipher);free(hea
11、d); /* 让最后一个人也出列 */ 3.1.2 栈的顺序存储及其基本操作的实现2进栈#include #define MAX 10 int sMAX; /*定义数组 t,用来存储栈的元素,以整数为例*/ int top; /*定义栈顶指针为 top*/ int push(int s,int x) /*x 为要插入的新元素*/if(top=MAX)printf(“stack overflown“); /*栈满信息*/return(0);6else stop=x; /*数据入栈*/top=top+1; /*当栈不满时,栈顶加 1*/printf(“okn“);return(1); void m
12、ain() /*主程序*/ int aMAX=1,2,3,4,5;int x=56,i;top=5;if(push(a,x)for(i=0;i #define MAX 10 int 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 aM
13、AX=1,2,3,4,5; int y;7习题答案附录附录top=5;if(pop(a, /*输出出栈元素*/ 5多个栈共享存储空间(1)进栈#define MAX 50 int 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+;elsest2=x;t2-;return(1);void main() /* 主函数*/ int i,j,x,p;for(i=0;i40;j-) /*第二栈输入数据
14、,九个数据*/scanf(“%d“,t2=40;printf(“请输入 p 和 x,中间用逗号:n“);scanf(“%d,%d“, /*往第 p 个栈插入数据 x*/if (pushd ( s,p,x) for (i=0;it2;j-)printf(“%5d“,sj); 8(2)出栈#define MAX 50 int sMAX; int t1,t2; int popd ( int s, int i) /*第 i 个栈退栈*/ if (i2)return(0);if (i=1)if(t1=0)return(0);elset1-;elseif(t2=MAX-1)return(0);else t2+;return(1); void main() /* 主函数*/ int i,j,x;for(i=0;i40;j-) /*第二栈输入数据*/scanf(“%d“,t2=40;scanf(“%d“, /*第 x 个数据要进行出栈操作*/if (popd ( s,x) for (i=0;it2;j-)printf(“%5d“,sj);3.1.3 栈的链式存储及其基本操作的实现1进栈#include #include typedef struct node9