武汉理工大学数据结构线性表试验报告

武汉理工大学理学院数学系课程实验报告课程名称:数据结构与算法班级数学类1402班日期2015年11月1日成绩评定姓名明钊实验室老师签名学号0121414670211实验名实验一线性表的设计与实现称所用Visuac++6.0,word软件实验实验目的：目掌握在visualc++下线性表的两种存储结构：顺序存储和链式存储各自的编程框架；的及实验内容：插入、删除、内掌握顺序表和单链表下建表、遍历、求前驱、求后继等算法的实现；容一、 实现顺序表的建立、插入数据、删除、遍历、求长度各函数代码及解释如下：StatusSqlistCreate(SqList&L,intlen)〃顺序表的建立函数：从键盘接收数据，依次放入顺序表{inti;for(i=0;i<len;i++){printf("请输入第%d个元素〃工+1);scanf("%d",&L.elem[i]);)return1;L.length=len;)intListLength(SqListL)//求顺序表的长度{printf("\n新表长度为%d",L.length);returnL.length;)voidListPrintf(SqList&L,intlen)//顺序表的遍历{inti;for(i=0;i<len;i++)printf("%d\t",L.elem[i]);)StatusListInsert(SqList&L,inti,ElemTypee)//在第i个元素前插入元素e{ElemType*newbase,*q,*p;if(i<1||i>L.length+1)returnERROR;if(L.length==L.listsize){newbase=(ElemType*)realloc(L.elem,(L.listsize+LIST_INCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LIST_INCREMENT;)q=L.elem+i-1;for(p=L.elem+L.length-1;p>=q;--p)*(p+1)=*p;*q=e;++L.length;ListPrintf(L,L.length);ListLength(L);returnOK;)StatusListDelete(SqList&L,inti,ElemType&e)//删除第i个元素之前的元素(ElemType*p,*q;if(i<1||i>L.length)returnERROR;p=L.elem+i-1;e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;L.length--;returnOK;)测试主程序如下：Voidmain(void){SqListL;InitList(L);printf("初始化L后，L.length=%d,L.listsize=%d,L.elem=%u\n”,L.length,L.listsize,L.elem);intlength;printf("输入表的长度length=");scanf("%d”,&length);ListCreate(L,length);ListPrintf(L,length);intn,m;printf("\n请输入要插入的位置(第n个元素前)n=");scanf("%d",&n);printf("请输入要插入的数据m=〃)；scanf("%d",&m);ListInsert(L,n,m);inti,e;printf("输入要删除的第i个元素i=〃)；scanf("%d",&i);ListDelete(L,i,e);)

实验结果及分析I'C:\Users\Admin\Documents\TencentFiles\1243057114\FiIeRecv\Debug\MySc二、单链表的建立与操作各函数如下:StatusCreateList_L(LinkList&L,intn)//用头插法建立一个长度为n的单链表(inti;LinkListp,s;L->next=NULL;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;p=L;实验结果及分析I'C:\Users\Admin\Documents\TencentFiles\1243057114\FiIeRecv\Debug\MySc二、单链表的建立与操作各函数如下:StatusCreateList_L(LinkList&L,intn)//用头插法建立一个长度为n的单链表(inti;LinkListp,s;L->next=NULL;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;p=L;for(i=n;i>0;i--)(s=(LinkList)malloc(sizeof(LNode));printf（〃输入新节点：〃）;scanf("%d”,&s->data);p->next=s;p=p->next;p->next=NULL;)新表长度为E输入要删除的第i个元素i=4除卜表长1度为5Pre零sanykeytocontinue请鲍人要播入的便置（第n个元素前）n=3请输人要揣入的薮据m=22 3 2 8,L.lengtli=0,L.listsize=10:度lEngtli=S个元素(一共输入5个元素),L.elem=9441032returnOK;)StatusListprintf(LinkList&L)//遍历函数(LinkListp=L;intlen=0,e;p=p->next;while(p)(len++;e=p->data;p=p->next;printf("%d",e);)printf("该链表的长度为%d”,len);returnOK;)StatusListInsert(LinkList&L,inti,ElemTypee)//在第i个元素前插入一个元素e(intj=0;LinkLists,p=L;while(p&&j<i-1){j++;p=p->next;)if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;Listprintf(L);returnOK;)StatusListdelete(LinkList&L,inti,ElemType&e)//删除第i个元素(intj;LinkListp,q;p=L;j=0;while(p->next&&j<i-1){j++;p=p->next;"/循环结束后，p指针指向第i-1个元素，而p->next指向第i个节点if(!(p->next)||j>i-1)return0;//删除位置不合理q=p->next;p->next=q->next;e=q->data;printf("删除的元素为%d”,e);printf("\n");free(q);Listprintf(L);returnOK;)StatusForewardElist(LinkList&L,inti,ElemType&v)//第i个元素的前驱{intj;LinkListp,q;p=L;j=0;if(i==1)return0;while(p->next&&j<i-2){j++;p=p->next;)if(!(p->next)||j>i-2)return0;q=p->next;p->next=q->next;v=q->data;printf("第%d个元素的前驱为v=%d",i,v);returnOK;)StatusBackwardlist(LinkList&L,inti,ElemType&x)//第i个元素的后继(intj;LinkListp,q;P=L;j=0;while(p->next&&j<i-1){j++;p=p->next;)if(!(p->next)||j>i-1||p->next==NULL)return0;q=p->next;p->next=q->next;x=q->data;printf("第%d个元素的后继为x=%d",i,x);returnOK;)测试主函数如下：Voidmain(void){LinkListL;inta;inti,j;int叫intk,l,v,x;ElemTypee;InitList(L);printf(〃请输入初始链表的长度”)；scanf("%d",&a);CreateList_L(L,a);Listprintf(L);printf("要插入的位置(第i个元素前)i二〃)；scanf("%d",&i);printf("要插入的元素m=");scanf("%d",&m);ListInsert(L,i,m);printf(〃删除的位置(第j个元素)j=〃)；scanf(〃%d〃,&j);Listdelete(L,j,e);printf("你要求的第i个元素的前驱〃)；scanf("%d",&k);ForewardElist(L,k,v);printf("你要求的第i个元素的后继〃)；sca