合肥学院数据结构实验报告.doc

合肥学院 数学与物理系实验报告课程名称： 数据结构与算法语言 实验项目： 顺序表、链表、栈和队列的应用 实验类别： 综合型 学生姓名： 学 号： 专业班级： 实验时间： 2012.02.122012.04.05 指导教师： 邵桂伟 实验成绩： 一、实验目的：1.了解顺序表的建立及使用；2.了解链表的结构，掌握其使用方法；3.熟悉栈的应用。二、实验要求：1.根据具体问题实现顺序表的查找并输出；2.根据具体问题掌握循环单链表的操作应用；3.根据具体问题实现栈及队列的操作应用。三、实验内容：1.程序实现顺序表的查找（查找成功、不成功两种情况）。2.程序实现循环单链表的建立、插入元素和删除。3.程序实现查找一元素，用栈和队列分别实现。四、数据结构：1. 顺序表的查找typedef structint key;int other;recordtype;typedef structrecordtype rlist_size;int length;recordlist;2. 循环单链表的建立、插入元素和删除typedef struct LNode int data; struct LNode *next;LNode,*LinkList;3.a).队列实现查找元素#define maxlen 100typedef structdatatype datamaxlen;int front;int rear;SeqQueue;b). 栈实现查找元素typedef structint data100; int top;SqStack;五、源程序及结果：1.（1）源程序（小四罗马字体）#include#define LIST_SIZE 10typedef struct int key;int other;Recordtype;typedef structRecordtype rLIST_SIZE;int length;Recordlist;void main()Recordlist p,*L=&p;int i,x,n=0;L-length=10;printf(请输入10个数:n);for(i=0;ilength;i+)scanf(%d,&L-ri.key);printf(请输入待查元素:n);scanf(%d,&x);for(i=0;ilength;i+)if(L-ri.key=x)n=i;if(n=0)printf(没有找到该元素);elseprintf(位置是:%d,n);（2）运行结果(可以使用截图)2.（1）源程序：#include #include #include typedef struct nodeint data;struct node *next;* linklist,LNode;int main()linklist L,newp,p,q,s;int i,n,e,j=1,t;L=(linklist)malloc(100*sizeof(LNode);(*L).next=NULL;printf(n表长:);scanf(%d,&n);printf(n表元素:);p=L;for(i=0;idata); p-next=newp;p=p-next;p-next=NULL;printf(n建立的链表:);s=L-next;while(s!=NULL)printf(%3d,s-data);s=s-next;printf(nn请输入要插入的元素:);scanf(%d,&e);q=L;p=(*L).next;while(p!=NULL & jnext;if(p!=NULL)newp=(linklist)malloc(sizeof(LNode);newp-data=e;newp-next=p-next;p-next=newp;printf(n插入元素后的链表:);s=L-next;while(s!=NULL)printf(%3d,s-data);s=s-next;printf(nn请输入要删除的元素:);scanf(%d,&e); i=0; t=0; p=L-next; while(p!=NULL) i+; if(p-data=e) t=i; break; p=p-next; q=L;p=(*L).next;j=1;while(p!=NULL & jnext;if(p!=NULL)q-next=p-next;t=p-data;free(p);printf(n删除元素后的链表:);s=L-next;while(s!=NULL)printf(%3d,s-data);s=s-next;return 0;（2）运行结果（可以使用截图）3.（1）源程序:A.队列实现元素查找#includestdio.h#includestdlib.h#includeiostream.h#define OK 1#define ERROR 0typedef int status;typedef struct Qnodechar data;struct Qnode *next;Qnode, *queueptr;typedef structqueueptr front;queueptr rear;linkqueue; status ini(linkqueue &Q) /初始化Q.front=Q.rear=(queueptr)malloc(sizeof(Qnode);if(!Q.front)exit(0);Q.front-next=NULL;return OK;status en(linkqueue &Q,char e) /进队Qnode *p;p=(queueptr)malloc(sizeof(Qnode);if(!p)exit(0);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;return OK;status de(linkqueue &Q,char &e) /出队if(Q.front=Q.rear)return ERROR;queueptr p;p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;free(p);return OK;void main()linkqueue Q;ini(Q);char in;char out;char temp;int flag=0; printf(输入要入队的元素（回车间隔，#结束）: n);do scanf(%c,&in); en(Q,in);while(in!=#); printf(输入要查找的元素: ); cinout; /此处C的输入应为 scanf(%c,&out);do de(Q,temp); if(temp=out) printf(查找成功！n ); flag=1; while(de(Q,temp)!=0);if(flag=0) printf(队列中无此元素！n );B栈实现元素查找#include stdio.h#include stdlib.h#include iostream.h#define ERROR 0;#define OK 1;#define TRUE 1;#define FALSE 0;#define LIST_INIT_SIZE 100 #define STACKINCREMENT 10 typedef char SElemType;typedef struct SElemType *top; SElemType *base; int stacksize; SqStack;int InitStack(SqStack &S) /构造 S.base=(SElemType*)malloc(LIST_INIT_SIZE*sizeof(SElemType); if(!S.base) exit(0);S.top=S.base;S.stacksize=LIST_INIT_SIZE; return OK; int GetTop(SqStack &S,SElemType &e) /返e if(S.base=S.top) return ERROR; e=*(S.top-1); return OK; int Push(SqStack &S,SElemType e) /入栈 if(S.top-S.base=S.stacksize) S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(EXIT_FAILURE); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; int Pop(SqStack &S,SElemType &e) /出栈 if(S.top=S.base) return ERROR; e=*(-S.top); return OK; void main()SqStack L;InitStack(L);char r;char t;int flag=0;printf(入栈：（每个以回车间隔,以#结束）：n); do scanf(%c,&r);