数据与结构的第三次实验报告

第三次实验报告庄振涛实验题3-1实现循环单链表的各种基本运算，完成以下功能：初始化循环单链表H。采用尾插法插入a,b,c,d,e。输出循环单链表H。输出循环单链表H的长度。在第3个位置上插入f。输出循环单链表H。删除第2个数据。输出循环单链表H。程序：#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructLNode /*定义单链表结点类型*/{ ElemTypedata;structLNode*next;}LinkList;voidInitList(LinkList*&L){ L=(LinkList*)malloc(sizeof(LinkList)); /*创建头结点*/ L->next=L;}voidDestroyList(LinkList*&L){ LinkList*p=L,*q=p->next; while(q!=L) { free(p); p=q; q=p->next; } free(p);}intListEmpty(LinkList*L){ return(L->next==L);}intListLength(LinkList*L){ LinkList*p=L;inti=0; while(p->next!=L) { i++; p=p->next; } return(i);}voidDispList(LinkList*L){ LinkList*p=L->next; while(p!=L) { printf("%c",p->data); p=p->next; } printf("\n");}intGetElem(LinkList*L,inti,ElemType&e){ intj=0; LinkList*p; if(L->next!=L) /*单链表不为空表时*/ { if(i==1) { e=L->next->data; return1; } else /*i不为1时*/ { p=L->next; while(j<i-1&&p!=L) { j++; p=p->next; } if(p==L) return0; else { e=p->data; return1; } } } else /*单链表为空表时*/ return0;}intLocateElem(LinkList*L,ElemTypee){ LinkList*p=L->next; intn=1; while(p!=L&&p->data!=e) { p=p->next; n++; } if(p==L) return(0); else return(n);}intListInsert(LinkList*&L,inti,ElemTypee){ intj=0; LinkList*p=L,*s; if(p->next==L||i==1) /*原单链表为空表或i==1时*/ { s=(LinkList*)malloc(sizeof(LinkList)); /*创建新结点*s*/ s->data=e; s->next=p->next; /*将*s插入到*p之后*/ p->next=s; return1; } else { p=L->next; while(j<i-2&&p!=L) { j++; p=p->next; } if(p==L) /*未找到第i-1个结点*/ return0; else /*找到第i-1个结点*p*/ { s=(LinkList*)malloc(sizeof(LinkList)); /*创建新结点*s*/ s->data=e; s->next=p->next; /*将*s插入到*p之后*/ p->next=s; return1; } }}intListDelete(LinkList*&L,inti,ElemType&e){ intj=0; LinkList*p=L,*q; if(p->next!=L) /*原单链表不为空表时*/ { if(i==1) /*i==1时*/ { q=L->next; /*删除第1个结点*/ L->next=q->next; free(q); return1; } else /*i不为1时*/ { p=L->next; while(j<i-2&&p!=L) { j++; p=p->next; } if(p==L) /*未找到第i-1个结点*/ return0; else /*找到第i-1个结点*p*/ { q=p->next; /*q指向要删除的结点*/ p->next=q->next; /*从单链表中删除*q结点*/ free(q); /*释放*q结点*/ return1; } } } elsereturn0;externvoidInitList(LinkList*&L); /*以下均为外部函数*/externvoidDestroyList(LinkList*&L);externintListEmpty(LinkList*L);externintListLength(LinkList*L);externvoidDispList(LinkList*L);externintGetElem(LinkList*L,inti,ElemType&e);externintLocateElem(LinkList*L,ElemTypee);externintListInsert(LinkList*&L,inti,ElemTypee);externintListDelete(LinkList*&L,inti,ElemType&e); }voidmain(){ LinkList*h; ElemTypee; printf("(1)初始化循环单链表h\n"); InitList(h); printf("(2)依次采用尾插法插入a,b,c,d,e元素\n"); ListInsert(h,1,'a'); ListInsert(h,2,'b'); ListInsert(h,3,'c'); ListInsert(h,4,'d'); ListInsert(h,5,'e'); printf("(3)输出循环单链表h:"); DispList(h); printf("(4)循环单链表h长度=%d\n",ListLength(h)); printf("(5)在第3个元素位置上插入f元素\n"); ListInsert(h,3,'f'); printf("(6)输出循环单链表h:"); DispList(h); printf("(7)删除h的第2个元素\n"); ListDelete(h,2,e); printf("(8)输出循环单链表h:"); DispList(h);}}结果：实验题3-2实现顺序栈的各种基本运算，完成以下功能：初始化顺序栈S。判断栈S是否非空。依次进栈元素a,b,c,d,e,f。输出顺序栈长度。输出从栈顶到栈底的元素。出栈两次。输出从栈顶到栈底的元素。程序：#include<stdio.h>#include<malloc.h>#defineMaxSize100typedefcharElemType;typedefstruct{ ElemTypeelem[MaxSize]; inttop; /*栈指针*/}SqStack;voidInitStack(SqStack*&s){ s=(SqStack*)malloc(sizeof(SqStack)); s->top=-1;}voidClearStack(SqStack*&s){ free(s);}intStackLength(SqStack*s){ return(s->top+1);}intStackEmpty(SqStack*s){ return(s->top==-1);}intPush(SqStack*&s,ElemTypee){ if(s->top==MaxSize-1) return0; s->top++; s->elem[s->top]=e; return1;}intPop(SqStack*&s,ElemType&e){ if(s->top==-1) return0; e=s->elem[s->top]; s->top--; return1;}intGetTop(SqStack*s,ElemType&e){ if(s->top==-1) return0; e=s->elem[s->top]; return1;}voidDispStack(SqStack*s){ inti; for(i=s->top;i>=0;i--) printf("%c",s->elem[i]); printf("\n");externvoidInitStack(SqStack*&s);externvoidClearStack(SqStack*&s);externintStackLength(SqStack*s);externintStackEmpty(SqStack*s);externintPush(SqStack*&s,ElemTypee);externintPop(SqStack*&s,ElemType&e);externintGetTop(SqStack*s,ElemType&e);externvoidDispStack(SqStack*s);}voidmain(){ ElemTypee; SqStack*s; printf("(1)初始化栈s\n"); InitStack(s); printf("(2)栈为%s\n",(StackEmpty(s)?"空":"非空")); printf("(3)依次进栈元素a,b,c,d,e\n"); Push(s,'a'); Push(s,'b'); Push(s,'c'); Push(s,'d'); Push(s,'e'); printf("(4)栈长度:%d\n",StackLength(s)); printf("(5)从栈顶到栈底元素:");DispStack(s); printf("(6)出栈序列:"); Pop(s,e); printf("%c",e); Pop(s,e); printf("%c",e); printf("\n");printf("(7)从栈顶到栈底元素:");DispStack(s); }结果：实验题3-3 实现单链栈的各种基本运算，完成以下功能：初始化链栈S。判断栈S是否非空。依次进栈元素a,b,c,d,e。输出链栈长度。输出从栈顶到栈底的元素。删除栈顶元素。输出从栈顶到栈底的元素。程序：/*文件名:algo3-3.cpp*/#include<stdio.h>#include<malloc.h>typedefcharElemType;typedefstructlinknode{ ElemTypedata; /*数据域*/ structlinknode*next; /*指针域*/}LiStack;voidInitStack(LiStack*&s){ s=(LiStack*)malloc(sizeof(LiStack)); s->next=NULL;}voidClearStack(LiStack*&s){ LiStack*p=s->next; while(p!=NULL) { free(s); s=p; p=p->next; }}intStackLength(LiStack*s){ inti=0; LiStack*p; p=s->next; while(p!=NULL) { i++; p=p->next; } return(i);}intStackEmpty(LiStack*s){ return(s->next==NULL);}voidPush(LiStack*&s,ElemTypee){ LiStack*p; p=(LiStack*)malloc(sizeof(LiStack)); p->data=e; p->next=s->next; /*插入*p结点作为第一个数据结点*/ s->next=p;}intPop(LiStack*&s,ElemType&e){ LiStack*p; if(s->next==NULL) /*栈空的情况*/ return0; p=s->next; /*p指向第一个数据结点*/ e=p->data; s->next=p->next; free(p); return1;}intGetTop(LiStack*s,ElemType&e){ if(s->next==NULL) /*栈空的情况*/ return0; e=s->next->data; return1;}voidDispStack(LiStack*s){ LiStack*p=s->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");externvoidInitStack(LiStack*&s);extern