C程序数据结构.doc

实验一 1顺序表的顺序存储结构综合处理程序的调试及运行程序清单：#define DATATYPE1 int/线性表中数据元素基类型#define MAXSIZE 12/线性表的最大可能长度typedef struct /将定义的一种结构体自定义成一种数据类型 DATATYPE1 datasMAXSIZE;/利用与严重的树祖克申请到连续的内存空间 int last; /last 域将用来记录内存中实际存储的数据元素个数SEQUENLIST;/初始化操作void init_sequenlist(SEQUENLIST *a)int k;for(k=0;kdatask=0;a-last=0;/*插入操作*/int insert(SEQUENLIST *a, DATATYPE1 x,int i)int k;if(ia-last|a-last=MAXSIZE)return 0;elsefor(k=a-last;k=i;k+)a-datask=a-datask-1;a-datasi-1=x;a-last=a-last+1;return 1;/*删除操作*/int del(SEQUENLIST *a,int i)int k;if(ia-last|a-last=0)return 0;elsefor(k=i;klast;k+)a-datask-1=a-datask;a-last-;return 1;/*查找操作*/int locate(SEQUENLIST *a,DATATYPE1 x)int k=1;while(klast&a-datask-1!=x)k+;if(klast)return k;elsereturn -1;/*输出操作*/void print(SEQUENLIST *a)int k;printf(线性表的内容是：n);for(k=0;klast;k+)printf(%5d,a-datask);printf(n);/主函数 main()SEQUENLIST LS，*pl=&ls;int k,n,m;DATATYPE1 x;init_sequenlist(pl);printf(n请输入线性表的长度，注：不能超过%d:,MAXSIZE);scanf(%d,&n);ls.last=n;printf(n请一一输入线性表的各个元素植：);for(k=0;kdatas1;n=b-datas1;p=q=r=2;while(p=2*m&qdatasp=b-datasq)c-datasr+1=a-datasp+1+b-datasq+1;if(c-datasr+1!=0)c-datasr=a-datasp;r=r+2;else if(a-dataspb-datasq)c-datasr+1=a-datasp+1;c-datasr=a-datasp;p=p+2;r=r+2;elsec-datasr+1=b-datasq+1;c-datasr=b-datasq;q=q+2;r=r+2;while(pdatasr+1=a-datasp+1;c-datasr=a-datasp;p=p+2;r=r+2;while(qdatasr+1=b-datasq+1;c-datasr=b-datasq;q=q+2;r=r+2;c-datas1=r/2-1;/*输出函数*/void outlist(SEQUENLIST *a)int k;printf(多项式的内容是：n);for(k=2;klast-1);k+=2)printf(%d,%d,a-datask+1,a-datask);printf(n); main()SEQUENLIST a,b,c,*pa=&a,*pb=&b,*pc=&c;int k=0;printf(请输入第一个多项式的项数：);scanf(%d,*pa-datas1);printf(请输入第一个多项式各项的（指数，系数）；);for(k=1;kdatas1;k+)scanf(%d,%d,&pa-datask*2,&pa-datask*2+1);pa-last=2*pa-datas1+1;printf(请输入第二个多项式的项数：);scanf(%d,&pb-datas1);printf(请输入第二个多项式各项的（指数，系数）；);for(k=1;kdatas1;k+)scanf(%d,%d,&pb-datask*2,&pb-datask*2+1);pb-last=2*pb-datas1+1;polynomial_add(pa,pb,pc);pc-last=2*pc-datas1+1;outlist(pa);outlist(pb);outlist(pc);实验二 单链表及应用实践综合处理程序的调试及运行程序清单：#include #include #define DATATYPE1 int#define NULL 0#define END -1#define D %d#define LEN sizeof(LINKLIST)/*数据类型说明-存储设计*/typedef struct nodeDATATYPE1 data;struct node *next; LINKLIST;/*头插入法建表*/LINKLIST *creatlinkh()LINKLIST *t,*head;DATATYPE1 x;t=(LINKLIST *)malloc (LEN);t-next=NULL;head=t;printf(Input x:n);scanf(D,&x);while(x!=END)t=(LINKLIST *)malloc(LEN);t-data=x;t-next=NULL;t-next=head-next;head-next=t;scanf(D,&x);return(head);/*尾插入法建表*/LINKLIST *creatlinkt()LINKLIST *s,*t,*head;DATATYPE1 x;head=(LINKLIST *)malloc(LEN);head-next=NULL;s=head;printf(Input x:n);scanf(D,&x);while(x!=END)t=(LINKLIST *)malloc(LEN);t-data=x;t-next=NULL;s-next=t;s=t;scanf(D,&x);return (head);/*按值查找元素*/LINKLIST *locate(DATATYPE1 y,LINKLIST *head)LINKLIST *p;p=head-next;while(p!=NULL)if(p-data=y) return p;elsep=p-next;return NULL;void insertafter (DATATYPE1 x,LINKLIST *p)LINKLIST *t;t=(LINKLIST *)malloc(LEN);t-data=x;t-next=p-next;p-next=t;/*删除元素*/int del(LINKLIST *head,DATATYPE1 y)LINKLIST *p,*t;int r=1;p=head;while(p-next!=NULL& p-next-data!=y)p=p-next;if(p-next!=NULL)t=p-next;p-next=t-next;free(t);elser=0;return r;/*结点计数*/int count(LINKLIST *head)int i=0;LINKLIST *p;p=head;while(p-next!=NULL)i+;p=p-next;return i;/*按条件插入元素*/void ifinsert(DATATYPE1 x,DATATYPE1 a,LINKLIST *head)LINKLIST *pnew ,*p;int flag=1;pnew=(LINKLIST *)malloc(LEN);pnew-data=x;pnew-next=NULL;p=head;while(p-next!=NULL & flag=1)p=p-next;if(p-data=a)penw-next=p-next;p-next=pnew;flag=0; if(flag=1)p-next=pnew;pnew-next=NULL;/*在有序表中插入新元素*/void inser_order(DATATYPE1 x,LINKLIST *head)LINKLIST *pr,*pn;pr=head;pn=head-next;while(pn!=NULL& pn-datanext;insertafter(x,pr);/*链表输出函数*/void printlink(LINKLIST *head)LINKLIST *p;p=head;printf(Link is:);while(p-next!=NULL)p=p-next;printf(%d-,p-data);printf(bb n);/*主函数*/ main()LINKLIST *hd1=NULL,*hd2=NULL,*q;int f,select, num1,num2;DATATYPE1 z,c;char yn=y;hd1=creatlinkh();printlink(hd1);hd2=creatlinkt();printlink(hd2);while(yn=y)printf(nn*n);printf(1.结点计数 2。插入元素 3。删除元素 4。查找 5。退出n);printf(nn*n);printf(Please select);switch(select)case 1:num1=count(hd1);num2=count(hd2);printf(Num1 is :%dn,num1);printf(Num2 is :%dn,num2);break;case 2:printf(Inserted data is:);scanf(D,&x);printf(Insert where:);scanf(D),&c;ifinsert(z,c,hd1);printlink(hd1);break;case 3:printf(delete:);scanf(D,&z);f=del(hd1,z);if(f=1)printf(delete is success.n);printlink(hd1);elseprintf(delete is fail.n);printlink(hd1);break;case 4:printf(searched data is :);scanf(D,&z);q=locate(z,hd1);if(1!=NULL)printf(%dn,q-data);elseprintf(search is fail.n);break; case 5:yn=n;break;default:printf(nselect is error,continue?(yes/no):);getchar();scanf(%c,&yn);实验三 顺序栈、链表队列的应用1顺序栈应用实践：利用顺序栈及其基本操作来实现非负十进制数转换成十六进制数之程序。程序的主要结构：#define DATATYPE1 int /*线性表元素的数据类型 */#define MAXSIZE 15 /*线性表的最大可能长度*/*顺序栈之存储设计*/typedef struct DATATYPE1 dataMAXSIZE;int top;SEQSTACK;/*顺序栈初始化操作*/void initstack(SEQSTACK *s)int i;for(i=0;kdatai=0;s-top=0;/*入栈操作*/int push(SEQSTACK *s,DATATYPE1 x)if(s-top=MAXSIZE-1)printf(Overflow.n);return 0;elses-top+;(s-data)s-top=x;/这两句等价于s.data+s-top=xreturn 1;/*出栈操作*/DATATYPE1 pop(SEQSTACK *s)DATATYPE1 x;if(empty(s)printf(Underflow.n);x=NULL;elsex=(s-data)s-top;s-top-; /这两句等价于x=s.datas-top-=xreturn x;/*栈顶元素读取操作*/DATATYPE1 gettop(SEQSTACK *s)DATATYPE1 x;if(empty(s)printf(Stack is empty.n);x=NULL;elsex=(s-data)s-top;return x;/*转换函数*/void d_to_o(unsigned x)int y;char ch;SEQSTACK stack,*s;s=&stack;initstack(s);push(s,#);while(x!=0)y=x%16;if(y10)push(s,y);elseswitch(y)case 10:push(s,A);break;case 11:push(s,B);break;case 12:push(s,C);break;case 13:push(s,D);break;case 14:push(s,E);break;case 15:push(s,F);x=x/16;while (ch=gettop(s)!=#) /*输出栈的内容*/ch=pop(s);if(ch10)printf(%d,ch);elseprintf(%c,ch);/*转换的递归算法*/void d_to_or(unsigned x)int y;if(x/16!=0)d_to_or(x/16);y=x%16;if(y10)printf(%d,y);elseswitch(y)case 10:push(s,A);break;case 11:push(s,B);break;case 12:push(s,C);break;case 13:push(s,D);break;case 14:push(s,E);break;case 15:push(s,F);/*主函数*/main()unsigned x;printf(Input x:);scanf(%d,&x);d_to_o(x);/*用非递归算法来转换*/printfn);d_to_or(x);/*用递归算法来转换*/printf(n);2队列管理模拟算法程序 程序的大概结构：#include #define NULL 0#define DATATYPE1 int /*链式队列的存储设计*/typedef struct qnodeDATATYPE1 data;struct qnode *next;LINKQLIST;typedef struct LINKQLIST *front;LINKQLIST *rear;LINKQUEUE;/*初始化链式队列*/void initlinkqueue(LINKQUEUE *q)q-front=(LINKQLIST *)malloc(sizeof(LINKQLIST);(q-front)-next=NULL;q-rear=q-front;)/*读取队首元素*/DATATYPE1 getlinkfront(LINKQUEUE *q)DATAYPE1 v;if(q-front=q-rear;v=0;elsev=(q-front)-next-data;return v;/*元素入队函数*/void enlinkqueue(LINKQUEUE *q,DATATYPE1 x)LINKQLIST *p;p=(LINKQLIST *)malloc(sizeof(LINKQLIST);p-data=x;p-next=NULL;(q-rear)-next=p;q-rear=(q-rear)-next;/*元素出队函数*/DATATYPE1 dellinkqueue(LINKQUEUE *q)LINKQLIST *p;DATATYPE1 v;if(q-front=q-rear)printf(Queue is empty.n);v=0;elsep=(q-front)-next;(q-front)-next=p-next;if(p-next=NULLq-rear=q-front;v=p-data;free(p);return v;/*队列输出函数*/void outlinkqueue(LINKQUEUE *q)LINKQLIST *p;p=q-front;printf(queue:);while(p!=q-rear)p=p-next;printf(%d,p-data);printf(n);/*主函数*/main()LINKQUEUE lq,*p;p=&lq;initlinkquue(p);printf(Input a integer:);scanf(%d,&j);while(j!=0)if(j%2!=0)enlinkquue(p,j);/*若为奇数，则入队*/elsej=dellinkqueue(p);/若为偶，则队首元素出队outlinkquue(p);printf(nInput a integer:);scanf(%d,&j);实验四 串的存储结构及基本操作的程序实现1 串联接操作的程序实现（1） 基于顺序定长存储结构的串的联接操作实现#include #include #define MAXSIZE 10/*串的顺序定长存储结构之存储设计*/typedef struct nodechar chMAXSIZE;int len;SEQSTRING;/*串联操作函数*/void concat(SEQSTRING *s,SEQSTRING *t1,SEQSTRING *t2)int i,k,n=MAXSIZE-1;if(t1-len+t2-len=n)/第一种情况for(i=0;ilen;i+)s-chi=t1-chi;k=t1-len;for(i=0;ilen;i+,k+)s-chk=t2-chi;s-len=t1.len+t2.len;else if(t1-lenn)/第二种情况for(i=0;ilen;i+)s-chi=t1-chi;k=t1-len;for(i=0;i+t2.lenchi+k=t2-chi;s-len=n;s-chn=0;else /第三种情况for(i=0;ichi=t1-chi;s-len=n;s-chn=0;main()SEQSTRING s1=,0,s2=,0,s3=,0;SEQSTRING *p1,*p2,*p3;printf(请输入第一个串：);gets(s1.ch);s1.len=strlen(s1.ch);printf(请输入第二个串：);gets(s2.ch);s2.len=strlen(s2.ch);p1=&s1;p2=&s2;p3=&s3;printf(n String1:%sn,s1.ch);printf(n String2:%sn,s2.ch);concat(p3,p1,p2);printf(n String3:%sn,s3.ch);（2） 基于堆分配存储结构的串联接操作实现#include #include /*串的堆分配存储结构之存储设计*/typedef struct nodechar *ch;/*存储用malloc()函数申请得到的内存空间的首地址*/int len;HSTRING;/*串联接操作函数*/void concat_h(HSTRING *s,HSTRING *t1,HSTRING *t2)int i,k;s-ch=(char *)malloc(t1-len+t2-len+1);for(i=0;ilen;i+)s-chi=t1-chi;k=t1-len;for(i=0;ilen;i+,k+)s-chk=t2-chi;main()HSTRING t1=for(i=1;ich);2 求子串操作的程序实现（1） 基于串的顺序定长存储结构：#include #include #define MAXSIZE 20/*串的顺序定长存储结构之存储设计*/typedef struct nodechar chMAXSIZE;int len;SEQSTRING;/*求子串操作*/SEQSTRING *substr(SEQSTRING *s,int i,int j)SEQSTRING sub;int n;if(is-len|js-len-(i-1)sub.len=0;sub.ch0=0;else for(n=0;nchi-1+n;sub.chj=0;sub.len=j;return (&sub);/*主函数*/main()SEQSTRING s1=Dong fang,9,*s2;s2=substr(&s1,6,4);printf(%sn,s1.ch);printf(n String2:%sn,s2-ch);（2）基于堆分配存储结构的串联接操作实现#include #include #define NULL 0/*串的堆分配存储结构之存储设计*/typedef struct nodechar *ch;/*存储用malloc()函数申请得到的内存空间的首地址*/int len;HSTRING;/*求子串函数*/HSTRING *substr_h(HSTRING *s,int i,int j)HSTRING sub;int n;if(is-len|js-len-(i-1)sub.len=0;sub.ch0=0;elsesub.ch=(char *)malloc(j+1)*sizeof(char);for(n=0;nchi-1+n;sub.chj=0;sub.len=j;return (&sub);/*主函数*/main()HSTRING str,*s2;int k,n,m,d;printf(请输入串长：);scanf(%d,&n);str.len=n;str.ch=(char *)malloc(n+1)*sizeof(char);printf(请输入串值：);getchar();gets(str.ch);printf(请输入所要求的子串（起始位置，长度）：);scanf(%d,%d,&m,&d);s2=substr_h(&str,m,d);printf(求得的子串是：%sn,s2-ch);实验五 稀疏矩阵的压缩存储表示及转置酸法综合处理程序1 其他线性数据结构-数学中稀疏矩阵的压缩存储表示与实现转置程序#define MAXLEN 10 /*稀疏矩阵的非零元素的最大可能数*/#define DATATYPE1 int /*矩阵元素的类型*/*三元组表存储设计*/typedef struct int i;/*用于存储非0元素的行号*/int j;/*用于存储非0元素的列号*/DATATYPE1 v;/*用于存储非0元素的值*/NODE;typedef struct int m,n,t;/*m存储矩阵的总行数,n存储矩阵的总列数,t存储矩阵的非零元素个数*/NODE dataMAXLEN;SPMATRIX;/*建立三元组表*/void creatmatrix(SPMATRIX *pr)int,i,h,l;DATATYPE1 z;printf(请输入矩阵的总行数，总列数：);scanf(%d,%d,&pr-m,&pr-n);printf(请输入矩阵的非零元素个数：);scanf(%d,&pr-t);printf(请一一输入每个非零元素所对应的三元组（i,j,v）:n);for(i=0;it;i+)scanf(%d,%d,%d,&h,&l,&z);pr-datai.i=h;pr-datai.j=l;pr-datai.v=z;/*矩阵的转置算法*/void transpose(SPMATRIX *b,SPMATRIX *a)int p,q,col;b.m=a.n;b.n=a.m;b.t=a.t;if(a.t!=0)q=1;for(col=1;col=a.n;col+)for(p=1;p=a;p+)if(a.datap.j=col)b.dataq.j=a.datap.i;b.dataq.i=a.datap.j;b.dataq.v=a.datap.v;q+;/*根据三元组输出矩阵*/void printmatrix(SPMATRIX *ma)int i,j,k;DATATYPE1 d;for(i=1;im;i+)d=0;for(k=0;kt;k+)if(i=ma-datak.i&j=ma-datak.j)d=ma-datak;break;printf(%5d,d);printf(n);/*主函数*/main()SPMATRIX a,b,*p1,*p2;p1=&a;p2=&b;creatmatrix(p1);/*建立原始矩阵的三元组表*/printmatrix(p1);/*输出第一个原始矩阵*/printf(n);transpose(p1);/*求原始矩阵的转置矩阵*/printmatrix(p2);/*输出求得的转置矩阵*/实验六 二叉链表的建立、遍历及应用等操作之综合处理程序1 建立二叉链表及遍历二叉树的程序实现#include #define NULL 0/*二叉链表存储设计*/#define DATATYPE2 chartypedef struct node1DATATYPE2 data;struct node1 *lchild,*rchild;BTCHINALR;/*在内存建立二叉链表函数*/BTCHINALR *createbt()BTCHINALR *q,*s30;int j,i;DATATYPE2 x;printf(Input i,x:);scanf(%d,%c,&i,&x);while(i!=0&x!=$)q=(BTCHINALR *)malloc(sizeof(BTCHINALR);q-data=x;q-lchild=NULL;q-rchild=NULL;si=q;if(i!=1)j=i/2;if(i%2=0)sj-lchild=q;elsesj-rchild=q;printf(Input i,x:);scanf(%d,%c,&i,&x);return (s1);/*先序遍历算法函数*/void preorder(BTCHINALR *bt)if(bt!=NULL)printf(%c,bt-data);preorder(bt-lchild);preorder(bt-rchild);/*中序遍历算法函数*/void inorder(BTCHINALR *bt)if(bt!=NULL)inorder(bt-lchild);printf(%c,bt-data);inorder(bt-rchild);/*后序遍历算法函数*/void postorder(BTCHINALR *bt)if(bt!=NULL)postorder(bt-lchild);postorder(bt-rchild);printf(%c,bt-data);/*求叶子结点数函数*/int leaf(BTCHINALR *bt)if(bt=NULL)return (0);else if(bt-lchild=NULL)&(bt-rchild=NULL)return (1);elsereturn (leaf(bt-lchild)+leaf(bt-rchild);/*求二叉树的深度函数*/int treehigh(BTCHINALR *bt)int lh,rh,h;if(bt=NULL)h=0;elselh=treehigh(bt-lchild);rh=treehigh(bt-rchild);b=(lhrh?lh:rh)+1;return h;/*求树的结点总数函数*/int total(BTCHINALR *bt)if(bt=NULL)return 0;else if(bt-lchild=NULL)&(bt-rchild=NULL)return 1;elsereturn (total(bt-lchild)+total(bt-rchild);/*左、右孩子互换函数*/void btchange(BTCHINALR *bt)BTCHINALR *t;if(bt!=NULL)if(bt-lchild!=NULL)btchange(bt-lchild);if(bt-rchild!=NULL)btchange(bt-rchild);/*主函数*/main()BTCHINALR *bt;bt=createbt();preorder(bt);printf(n);inorder(bt);printf(n);postorder(bt);printf(n);printf(t 树的总结点数为：%dn,total(bt);printf(t 数的叶子结点数为：%dn,leaf(bt