数据结构实验一-线性表及其应用实验二-栈和队列的应用实验三-树和二叉树的建立和应用

DONGFANGCOLLEGE，FUJIANAGRICULTUREANDFORESTRYUNIVERSITY课程名称：数据结构系别：计算机系年级专业：2010级电子信息工程学号：1050302103姓名：廖少兵任课教师：谢储辉成绩：2012年12月25日实验一线性表及其应用【实验目的】1.熟练掌握线性表的基本操作在顺序存储和链式存储上的实现；2.以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点；3.掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；4.通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的应用和链表的建立等各种基本操作）。【实验内容】1线性表顺序存储的基本操作参考程序：/*线性表顺序存储的基本操作*/#includestdio.h#defineMaxSize50typedefcharElemType;structList{ElemTypelist[MaxSize];intsize;};voidsetnull(structList*p){p-size=0;}intlength(structList*p){return(p-size);}intget(structList*p,inti){if(ip-size)return(-1);elsereturn(p-list[i-1]);}intlocate(structList*p,ElemTypex){inti=0;while(ip-size&&p-list[i]!=x)i++;if(i==p-size)return(-1);elsereturn(i+1);}voidinsert(structList*p,ElemTypex,inti){intj;if(i1&&ip-size+1)printf(位置参数不正确,不能进行插入操作!\n);else{p-size++;for(j=p-size-1;j=i;j--)/*结点向后移动,腾出一个位置*/p-list[j]=p-list[j-1];p-list[j]=x;}}voiddelete(structList*p,inti){intj;if(ip-size||i1)printf(位置参数不正确,不能进行删除操作!\n);else{for(j=i-1;jp-size-1;j++)/*结点向前移动,覆盖该删除的结点*/p-list[j]=p-list[j+1];p-size--;}}display(structList*p){intj;if(p-size==0)printf(该线性表为空,不能显示!\n);else{printf(线性表:);if(p-size==1)/*只有一个结点的情况*/printf(%c,p-list[p-size]);else/*有一个以上结点的情况*/{for(j=0;jp-size-1;j++)printf(%c→,p-list[j]);printf(%c,p-list[j]);/*显示最后一个结点*/}printf(\n);}}main(){structListL;setnull(&L);insert(&L,'a',1);insert(&L,'b',2);insert(&L,'a',1);insert(&L,'c',2);insert(&L,'d',1);insert(&L,'e',2);display(&L);printf(值:%c位置:%d\n,'a',locate(&L,'a'));printf(位置:%d值:%c\n,4,get(&L,4));printf(删除第2个结点后);delete(&L,2);display(&L);printf(删除第2个结点后);delete(&L,2);display(&L);printf(删除第1个结点后);delete(&L,1);display(&L);printf(删除第1个结点后);delete(&L,1);display(&L);}2线性表链式存储的基本操作/*线性表链式存储-单链表的基本操作*/#includestdio.h#includemalloc.htypedefcharElemType;structLNode{ElemTypedata;structLNode*next;}setnull(structLNode**p){*p=NULL;}intlength(structLNode**p){intn=0;structLNode*q=*p;while(q!=NULL){n++;q=q-next;}return(n);}ElemTypeget(structLNode**p,inti){intj=1;structLNode*q=*p;while(ji&&q!=NULL)/*查找第i个结点*/{q=q-next;j++;}if(q!=NULL)/*找到了第i个结点*/return(q-data);elseprintf(位置参数不正确!\n);}intlocate(structLNode**p,ElemTypex){intn=0;structLNode*q=*p;while(q!=NULL&&q-data!=x)/*查找data域为x的第一个结点*/{q=q-next;n++;}if(q==NULL)/*未找到data域等于x的结点*/return(-1);else/*找到data域等于x的结点*/return(n+1);}voidinsert(structLNode**p,ElemTypex,inti){intj=1;structLNode*s,*q;s=(structLNode*)malloc(sizeof(structLNode));/*建立要插入的结点s*/s-data=x;q=*p;if(i==1)/*插入的结点作为头结点*/{s-next=q;*p=s;}else{while(ji-1&&q-next!=NULL)/*查找第i-1个结点*/{q=q-next;j++;}if(j==i-1)/*找到了第i-1个结点,由q指向它*/{s-next=q-next;/*将结点s插入到q结点之后*/q-next=s;}elseprintf(位置参数不正确!\n);}}voiddelete(structLNode**p,inti){intj=1;structLNode*q=*p,*t;if(i==1)/*删除链表的头结点*/{t=q;*p=q-next;}else{while(ji-1&&q-next!=NULL)/*查找第i-1个结点*/{q=q-next;j++;}if(q-next!=NULL&&j==i-1)/*找到第i-1个结点,由q指向它*/{t=q-next;/*t指向要删除的结点*/q-next=t-next;/*将q之后的结点删除*/}elseprintf(位置参数不正确!\n);}if(t!=NULL)/*在t不为空时释放该结点*/free(t);}voiddisplay(structLNode**p){structLNode*q;q=*p;printf(单链表显示:);if(q==NULL)/*链表为空时*/printf(链表为空!);elseif(q-next==NULL)/*链表只有一个结点时*/printf(%c\n,q-data);else{/*链表存在一个以上的结点时*/while(q-next!=NULL)/*显示前面的结点*/{printf(%c→,q-data);q=q-next;}printf(%c,q-data);/*显示最后一个结点*/}printf(\n);}main(){structLNode*head;setnull(&head);insert(&head,'a',1);insert(&head,'b',2);insert(&head,'a',2);insert(&head,'c',4);insert(&head,'d',3);insert(&head,'e',1);display(&head);printf(单链表长度=%d\n,length(&head));printf(位置:%d值:%c\n,3,get(&head,3));printf(值:%c位置:%d\n,'a',locate(&head,'a'));printf(删除第1个结点:);delete(&head,1);display(&head);printf(删除第5个结点:);delete(&head,5);display(&head);printf(删除开头3个结点:);delete(&head,3);delete(&head,2);delete(&head,1);display(&head);}3双链表的基本操作/*双链表的基本操作*/#includestdio.h#includemalloc.htypedefcharElemType;structDNode{ElemTypedata;structDNode*left,*right;}setnull(structDNode**p){*p=NULL;}intlength(structDNode**p){intn=0;structDNode*q=*p;while(q!=NULL){n++;q=q-right;}return(n);}ElemTypeget(structDNode**p,inti){intj=1;structDNode*q=*p;while(ji&&q!=NULL)/*查找第i个结点*/{q=q-right;j++;}if(q!=NULL)/*找到了第i个结点*/return(q-data);elseprintf(位置参数不正确!\n);}intlocate(structDNode**p,ElemTypex){intn=0;structDNode*q=*p;while(q!=NULL&&q-data!=x)/*查找data域为x的第一个结点*/{q=q-right;n++;}if(q==NULL)/*未找到data域等于x的结点*/return(-1);else/*找到data域等于x的结点*/return(n+1);}voidinsert(structDNode**p,ElemTypex,inti){intj=1;structDNode*s,*q;s=(structDNode*)malloc(sizeof(structDNode));/*建立要插入的结点s*/s-data=x;s-left=s-right=NULL;q=*p;if(i==1)/*插入的结点作为表头结点*/{s-right=q;if(q!=NULL)/*原来的双链表不为空*/q-left=s;*p=s;}else{while(ji-1&&q-right!=NULL)/*查找第i-1个结点*/{q=q-right;j++;}if(j==i-1)/*找到了第i-1个结点,由q指向它*/{if(q-right!=NULL)/*q不是最后一个结点*/{s-right=q-right;/*将结点s插入到q结点和之后结点q-right之间*/q-right-left=s;s-left=q;q-right=s;}else/*q是最后一个结点*/{s-left=q;/*将s作为表尾结点*/q-right=s;}}elseprintf(位置参数不正确!\n);}}voiddelete(structDNode**p,inti){intj=1;structDNode*q=*p,*t;if(i==1)/*删除链表的头结点*/{t=q;q=q-right;if(q!=NULL)/*当双链表不只一个结点时*/q-left=NULL;*p=q;}else{while(ji-1&&q-righ