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

《《数据结构》上机实验参考程序.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验一单链表的建立、删除和插入参考程序#include#include#defineN5typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;LNode*CreateList(intn)/*算法2.11,见课本p30*/{/*逆位序(插在表头)输入n个元素的值，建立带表头结构的单链线性表L*/inti;LinkListp,L;L=(LinkList)malloc(sizeof(structLNode));L->

2、next=NULL;/*先建立一个带头结点的单链表*/printf("请输入%d个数据",n);for(i=n;i>0;--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个位

3、置之前插入元素e*/LinkListp=L,s;intj=0;while(p&&jnext;++j;}if(!p

4、

5、j>i-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*/{/*在带头结点的单链

6、线性表L中，删除第i个元素，并由e返回其值*/LinkListp=L,q;intj=0;while(p->next&&jnext;++j;}if(!(p->next)

7、

8、j>i-1)returnL;/*删除位置不合理*/q=p->next;p->next=q->next;*e=q->data;free(q);returnL;}voidListTraverse(LinkListL){LinkListp=L->next;while(p){printf("%d

9、",p->data);p=p->next;}printf("");}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);/*在带头结

10、点的单链线性表L中，删除第i个元素，并由p返回其值*/printf("Deletenumber:%d",*p);printf("Lb=");/*输出链表Lb的内容*/ListTraverse(Lb);}实验二栈的建立、插入和删除参考程序#include#include#defineSTACK_INIT_SIZE100/*存储空间初始分配量*/#defineINC10/*存储空间分配增量*/typedefstruct{char*base;/*在栈构造之前和销毁之后，base值

11、为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,c

12、harx)/*插入元素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).bas