数据结构实验二--链表实验

实验二链表实验一、实验目的1.学会定义单链表的结点类型，实现对单链表的一些基本操作和具体的函数定义，了解并掌握单链表的类定义以及成员函数的定义与调用。2.掌握单链表基本操作及单链表逆置等操作的实现。二、实验要求1．预习C语言中结构体的定义与基本操作方法。2．对单链表的每个基本操作用单独的函数实现。3．编写完整程序完成下面的实验内容并上机运行。4．整理并上交实验报告。三、实验内容1．编写程序完成单链表的下列基本操作：1)用头插入法生成一个链表[13579]，结点的数值从键盘上输入。输出上述链表2)在链表的第1个位置插入元素10,输出上述链表；3)删除链表的第3个元素，输出链表4)求链表的长度，并输出表长。#includestdio.h#includemalloc.h#includestdlib.htypedefstructnode{intdata;structnode*next;}LNODE,*linkedlist;linkedlistlistinit(){linkedlistL;L=(LNODE*)malloc(sizeof(LNODE));if(L==NULL){printf(memorynotenough);exit(0);}L-next=NULL;returnL;}intlistlen(linkedlistL){linkedlistp;intj;p=L-next;j=0;while(p){j++;p=p-next;}returnj;}voidlistins(linkedlistL,inti,intx){linkedlistp,s;intj;p=L;j=0;while(p&&ji-1){p=p-next;j++;}if(!p||ji){printf(positionerror);exit(0);}s=(LNODE*)malloc(sizeof(LNODE));s-data=x;s-next=p-next;p-next=s;}voidlistdel(linkedlistL,inti){linkedlistp,q;intj;p=L;j=0;while(p-next&&ji-1){p=p-next;j++;}if(p-next==NULL||ji){printf(positionerror);exit(0);}q=p-next;p-next=q-next;free(q);}linkedlistlistbuild(){intx;LNODE*L,*p;L=(LNODE*)malloc(sizeof(LNODE));L-next=NULL;scanf(%d,&x);while(x!=0){p=(LNODE*)malloc(sizeof(LNODE));p-data=x;p-next=L-next;L-next=p;scanf(%d,&x);}return(L);}voidmain(){linkedlistL,p;intk;printf(请输入L表的元素：\n);L=listbuild();printf(L表为：\n);p=L-next;while(p!=NULL){printf(%d\n,p-data);p=p-next;}listins(L,1,10);printf(在第一个位置插入10后的L表为：\n);p=L-next;while(p!=NULL){printf(%d\n,p-data);p=p-next;}listdel(L,3);printf(删除第三个元素后的L表为：\n);p=L-next;while(p!=NULL){printf(%d\n,p-data);p=p-next;}k=listlen(L);printf(链表的长度为：%d\n,k);2．构造一个单链表L，其头结点指针为head，编写程序实现将L逆置。（即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。）#includestdio.h#includemalloc.h#includestdlib.htypedefstructnode{intdata;structnode*next;}LNODE,*linkedlist;linkedlistlistinit(){linkedlistL;L=(LNODE*)malloc(sizeof(LNODE));if(L==NULL){printf(memorynotenough);exit(0);}L-next=NULL;returnL;}linkedlistlistbuild(){intx;LNODE*L,*p;L=(LNODE*)malloc(sizeof(LNODE));L-next=NULL;scanf(%d,&x);while(x!=0){p=(LNODE*)malloc(sizeof(LNODE));p-data=x;p-next=L-next;L-next=p;scanf(%d,&x);}return(L);}linkedlistlistinv(linkedlistL){linkedlistp,r;p=L-next;L-next=NULL;while(p!=NULL){r=p-next;p-next=L-next;L-next=p;p=r;}return(L);}voidmain(){linkedlistL,p;printf(请输入L表的元素：\n);L=listinit();L=listbuild();printf(逆置前的L表为：\n);p=L-next;while(p!=NULL){printf(%d\n,p-data);p=p-next;}L=listinv(L);printf(逆置后的L表为：\n);p=L-next;while(p!=NULL){printf(%d\n,p-data);p=p-next;}}四、思考与提高1．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点？#includestdio.h#includemalloc.h#includestdlib.htypedefstructnode{intdata;structnode*next;}LNODE,*linkedlist;linkedlistlistinit(){linkedlistL;L=(LNODE*)malloc(sizeof(LNODE));if(L==NULL){printf(memorynotenough);exit(0);}L-next=NULL;returnL;}linkedlistlistbuild(){intx;LNODE*L,*p;L=(LNODE*)malloc(sizeof(LNODE));L-next=NULL;scanf(%d,&x);while(x!=0){p=(LNODE*)malloc(sizeof(LNODE));p-data=x;p-next=L-next;L-next=p;scanf(%d,&x);}return(L);}linkedlistlistinv(linkedlistL){linkedlistp,r;p=L-next;L-next=NULL;while(p!=NULL){r=p-next;p-next=L-next;L-next=p;p=r;}return(L);}voidmain(){linkedlistLa,Lb,Lc,p,q,r;La=listinit();Lb=listinit();Lc=listinit();printf(请输入La表的元素：\n);La=listbuild();printf(La表为：\n);p=La-next;while(p!=NULL){printf(%d\n,p-data);p=p-next;}La=listinv(La);p=La-next;while(p!=NULL){q=(LNODE*)malloc(sizeof(LNODE));q-data=p-data;q-next=Lb-next;Lb-next=q;p=p-next;if(p!=NULL){r=(LNODE*)malloc(sizeof(LNODE));r-data=p-data;r-next=Lc-next;Lc-next=r;p=p-next;}}printf(Lb表为：\n);p=Lb-next;while(p!=NULL){printf(%d\n,p-data);p=p-next;}printf(Lc表为：\n);p=Lc-next;while(p!=NULL){printf(%d\n,p-data);p=p-next;}}