《数据结构》上机实验参考程序

1实验一单链表的建立、删除和插入参考程序#includestdio.h#includemalloc.h#defineN5typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;LNode*CreateList(intn)/*算法2.11,见课本p30*/{/*逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L*/inti;LinkListp,L;L=(LinkList)malloc(sizeof(structLNode));L-next=NULL;/*先建立一个带头结点的单链表*/printf(请输入%d个数据\n,n);for(i=n;i0;--i){p=(LinkList)malloc(sizeof(structLNode));/*生成新结点*/scanf(%d,&p-data);/*输入元素值*/p-next=L-next;/*插入到表头*/L-next=p;}returnL;}Lnode*insert(LinkListL,inti,inte)/*算法2.9，见课本p29*/{/*在带头结点的单链线性表L中第i个位置之前插入元素e*/LinkListp=L,s;intj=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnL;/*假如i小于1或者大于表长，则不插入结点，返回原链表*/s=(LinkList)malloc(sizeof(structLNode));s-data=e;s-next=p-next;p-next=s;returnL;}LNode*delete1(LinkListL,inti,int*e)/*算法2.10,见课本p30*/{/*在带头结点的单链线性表L中，删除第i个元素，并由e返回其值*/2LinkListp=L,q;intj=0;while(p-next&&ji-1){/*寻找第i个结点，并令p指向其前趋*/p=p-next;++j;}if(!(p-next)||ji-1)returnL;/*删除位置不合理*/q=p-next;p-next=q-next;*e=q-data;free(q);returnL;}voidListTraverse(LinkListL){LinkListp=L-next;while(p){printf(%d,p-data);p=p-next;}printf(\n);}voidmain(){LinkListLb;int*p=NULL;Lb=CreateList(N);/*逆位序输入n个元素的值*/printf(Lb=);/*输出链表Lb的内容*/ListTraverse(Lb);Lb=insert(Lb,2,9);/*在带头结点的单链线性表L中第i个位置之前插入元素e*/printf(Lb=);/*输出链表Lb的内容*/ListTraverse(Lb);Lb=delete(Lb,3,p);/*在带头结点的单链线性表L中，删除第i个元素，并由p返回其值*/printf(Deletenumber:%d\n,*p);printf(Lb=);/*输出链表Lb的内容*/ListTraverse(Lb);}3实验二栈的建立、插入和删除参考程序#includestdio.h#includemalloc.h#defineSTACK_INIT_SIZE100/*存储空间初始分配量*/#defineINC10/*存储空间分配增量*/typedefstruct{char*base;/*在栈构造之前和销毁之后，base值为NULL*/char*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/}sqstack;voidInitstack(sqstack*s){/*构造一个空栈S*/(*s).base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!(*s).base)exit(0);/*存储分配失败*/(*s).top=(*s).base;(*s).stacksize=STACK_INIT_SIZE;}voidpush(sqstack*s,charx)/*插入元素e为新的元素*/{if(((*s).top-(*s).base)=(*s).stacksize){(*s).base=(char*)realloc((*s).base,((*s).stacksize+INC)*sizeof(char));if(!(*s).base)exit(0);/*存储分配失败*/(*s).top=(*s).base+(*s).stacksize;(*s).stacksize+=INC;}*((*s).top)++=x;}intpop(sqstack*s,char*x){/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回值*/if((*s).top==(*s).base)return0;else{(*s).top=(*s).top-1;*x=*((*s).top);}return1;}main(){sqstacks;charch;4Initstack(&s);push(&s,'a');push(&s,'b');push(&s,'c');pop(&s,ch);printf(%c,ch);pop(&s,ch);printf(%c,ch);pop(&s,ch);printf(%c,ch);}5实验三队列的建立、插入和删除参考程序#includestdio.h#includemalloc.h#includeprocess.h/*exit()*/typedefstructQNode{chardata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;/*队头指针*/QueuePtrrear;/*队尾指针*/}LinkQueue;voidInitQueue(LinkQueue*Q){/*构造一个空队列Q*/(*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));if(!(*Q).front)exit(0);(*Q).front-next=NULL;}voidEnQueue(LinkQueue*Q,chare){/*插入元素e为Q的新的队尾元素*/QueuePtrp=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(0);/*存储分配失败*/p-data=e;p-next=NULL;(*Q).rear-next=p;(*Q).rear=p;}voidDeQueue(LinkQueue*Q,char*e){/*若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR*/QueuePtrp;if((*Q).front==(*Q).rear)exit(0);/*空队列退出*/p=(*Q).front-next;*e=p-data;(*Q).front-next=p-next;if((*Q).rear==p)(*Q).rear=(*Q).front;free(p);}voidprintfQueue(LinkQueueQ){6QueuePtrp;p=Q.front-next;while(p){printf(%3c,p-data);p=p-next;}printf(\n);}main(){LinkQueueQ;chare;InitQueue(&Q);EnQueue(&Q,'a');EnQueue(&Q,'b');EnQueue(&Q,'c');EnQueue(&Q,'d');EnQueue(&Q,'e');printf(Queueelement:);printfQueue(Q);printf(Nowinseraelementinthequeue,outputthequeue:);EnQueue(&Q,'f');printfQueue(Q);DeQueue(&Q,&e);printf(Nowdeleteaelementinthequeue,theelementis:%c\n,e);printf(outputthequeue:);printfQueue(Q);}7实验四循环队列的建立、插入和删除参考程序#includestdio.h#includeprocess.h#includemalloc.h#defineMAX_QSIZE5/*最大队列长度+1*/typedefstruct{int*base;/*初始化的动态分配存储空间*/intfront;/*头指针，若队列不空，指向队列头元素*/intrear;/*尾指针，若队列不空，指向队列尾元素的下一个位置*/}SqQueue;voidInitQueue(SqQueue*Q){/*构造一个空队列Q*/(*Q).base=(int*)malloc(MAX_QSIZE*sizeof(int));if(!(*Q).base)/*存储分配失败*/exit(0);(*Q).front=(*Q).rear=0;}voidEnQueue(SqQueue*Q,inte){/*插入元素e为Q的新的队尾元素*/if(((*Q).rear+1)%MAX_QSIZE==(*Q).front)/*队列满*/exit(0);;(*Q).base[(*Q).rear]=e;(*Q).rear=((*Q).rear+1)%MAX_QSIZE;}voidDeQueue(SqQueue*Q,int*e){/*若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR*/if((*Q).front==(*Q).rear)/*队列空*/exit(0);*e=(*Q).base[(*Q).front];(*Q).front=((*Q).front+1)%MAX_QSIZE;}voidQueueTraverse(SqQueueQ){/*从队头到队尾依次对队列Q中每个元素输出*/inti;i=Q.front;while(i!=Q.rear){8printf(%3d,Q.base[i]);i=(i+1)%MAX_QSIZE;}printf(\n);}voidmain(){intd,i=0;SqQueueQ;InitQueue(&Q);printf(Pleaseinputtheelementsofthequeue(%dnumber),-1istheend:,MAX_QSIZE-1);do{scanf(%d,&d);if(d==-1)break;i++;EnQueue(&Q,d);}while(iMAX_QSIZE-1);DeQueue(&Q,&d);printf(Deletetheelementis:%d\n,d);printf(Nowtheelementsare:\n);QueueTraverse(Q);DeQueue(&Q,&d);printf(Deletetheelementis:%d\n,d);printf(Nowtheelementsare:\n);QueueTraverse(Q);}9实验五数组的顺序存储表示和实现参考程序#includestdarg.h/*标准头文件,提供宏va_start,va_arg,va_end,用于存放变长文件*/#includestdio.h#includemalloc.h#defineMAX_ARRAY_DIM8typedefstruct{int*base;/*数组元素基址，由InitArray分配*/intdim;/*数组维数*/int*bounds;/*数组维界基址，由InitArray分配*/int*constants;/*数组映象函数常量基址，由In