链表实验报告————————————————————————————————作者: ————————————————————————————————日期：《数据结构》实验报告二系别:嵌入式系统工程系班级:嵌入式1１0０3班学号:１1160400３１4姓名：孙立阔日期：2012年４月９日指导教师:申华一、上机实验的问题和要求：单链表的查找、插入与删除。

设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除。

具体实现要求:1.从键盘输入1０个字符，产生不带表头的单链表，并输入结点值。

2.从键盘输入1个字符,在单链表中查找该结点的位置。

若找到,则显示“找到了”；否则,则显示“找不到”。

3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值,观察输出结果。

4.从键盘输入１个整数,表示欲删除结点的位置，输出单链表所有结点值,观察输出结果。

5.将单链表中值重复的结点删除,使所得的结果表中个结点值均不相同,输出单链表所有结点值,观察输出结果。

6.删除其中所有数据值为偶数的结点，输出单链表所有结点值,观察输出结果。

7.（★)将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素,而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表Ａ和单链表B的所有结点值，观察输出结果。

二、程序设计的基本思想，原理和算法描述:(包括程序的结构,数据结构，输入/输出设计,符号名说明等）创建一个空的单链表，实现对单链表的查找，插入,删除的功能。

三、源程序及注释：#dｅfiｎｅOK 1#defｉne EＲＲOR 0#ｄefiｎe INFEASIBLE －1#defｉne OVEＲFＬOW －2#deｆine TRUE 1#deｆine FAＬSE ０#defiｎe List_Init_Sｉze10＃defineＬｉstIncreｍent 2ｔyｐｅｄef char ET;tyｐeｄef ET *Ep;ｔｙpedeｆｉnt Statｕs;tｙpedｅｆstｒuct LNode{ﻩＥＴdaｔa;sｔrｕct ＬＮode *nｅxt;}LＮode, *ＬinkＬist;／*ＬiｎkＬｉsｔLa,Ｌb,Lc;*／ﻺ#ｉncｌuｄe"sｔdio.h＂#inclｕdｅ"alｌｏｃ.h"/＊Dｉsplay theｌｉnkｌｉｓt＇s eｌｅmｅnts. ＊/vｏid prｉnｔlk（ＬinkLｉst L) {LinkLiｓt p;ｐ=L->nｅｘt;while (p){ｐrｉntf(＂%c -＞",p->data);ｐ＝p->nｅxｔ;}ｐrinｔf("NＵLL\n＂);}/*Crｅａt ｌinｋlist from head node. *／voｉd CreatＬist(ＬinkＬisｔ＊L,iｎｔn){int i；LiｎkLｉｓｔｐ，q;EＴstr[20],c;p=（ＬinkList)mａｌｌoc(sｉzｅｏf（LＮｏde))；p->nexｔ=ＮＵＬＬ;*L = q = p;prｉntf("Ｐlｅase input thｅｄata: ")；for(ｉ=n;i＞０；i--) {p=(LｉnkLｉｓｔ)maｌｌoｃ(siｚｅof(LNoｄe）);c = getcｈe（)；/*sｃanf(＂％ｃ",&c);＊/printf("\ｎ\n");ｐ->ｄaｔa = c；ｐ－>next = q-＞next;q->next = p；}｝/*Iniｔｔhｅｌｉｎklist. */void Ｉnｉt（LｉnkＬist *L) {int n;printf("Pｌease ｉｎｐuｔthe ｎuｍｂｅr of the node : "); sｃanf（＂%d",&n);CreatLiｓt(L,n）;}/* Ｇet tｈe ｖａluｅoｆeleｍent I; *／int GｅtElem(LiｎkList L,int i,ET *e) {ｉnｔj=1；LinkLiｓt p；p=Ｌ-＞neｘｔ;while（p＆&j<i) {p=ｐ－>next;++j;}if(!ｐ|｜j>ｉ）rｅturn TRUE;*e=ｐ->data；reｔuｒn ＦALＳＥ；}/*Inｓeｒt a eleｍeｎt after Ｉ*／int ＬistInserｔ(ＬinkＬisｔ*L,inｔi,ET e) ｛/＊Ａdd ｙour owｎｃｏdes．*／}/*Deleｔｅthe elｅment I＊/int LisｔDｅletｅ（LinkList *Ｌ，iｎt i,ET*e){／* Adｄyour own ｃodes. *／}inｔInsert(LｉnｋList *L){ｉnt i,flａg;ET ｄaｔａ;printf("Ｐlease inpuｔｔｈeｐoｓｉtiｏn : ");ｓｃaｎf(＂％d",&ｉ);prｉnｔf("Please ｉnput tｈｅdaｔa : ＂）;daｔa ＝getche();/*scａnｆ("%c＂,&ｄatａ);＊／fｌaｇ= LiｓtIｎsert(L，i,dａta);retｕｒn flag;}Statｕs Dｅlｅte(LｉnkList*L）｛inｔi,flag;ＥT e；printf(＂Pｌeasｅinpｕt the nuｍber：");sｃanf("%d",＆i);fｌag ＝ＬｉstDelｅte（Ｌ,ｉ，&e)；printf("Ｄｅlｅｔedｅlemenｔiｓ%c\n",e);rｅｔurnｆlａg;}／＊Fｉnd tｈe eｌemeｎt'ｓposｉtｉoｎ．*/inｔLocateＥleｍ（ＬiｎkLiｓt Ｌ,ＥＴe) {int i＝0;LｉｎkLiｓt p；p ＝L->next;wｈile (p) {i++；if(p-＞dａtａ== ｅ)retuｒｎi;｝return 0;｝/*Adｄthe Lb afteｒthe Lａ．*/ｖｏｉd Uｎion( LiｎkList *Ｌa ,ＬｉｎkLｉst*Lb)｛LinkLisｔpa,pb;／*Aｄd yoｕｒowｎcodes. *／}／*Merge tｗo seqｕence into oｎe,dｏn＇t cｈange anyｅlemｅnts intｈeｓe tｗｏlｉnk ｌiｓts. Joiｎｔｗoｓeｑｕence to one. ＊/voｉd MeｒｇｅLisｔ（LinkList*Ｌ1,LｉｎｋLｉst ＊L2，LinkLｉsｔ*L3) ｛LinkLｉｓt pa，pb,pｃ;/＊Ａddｙour own codes. */}／*Liｓt the Mｅnｕ*/voidＭｅｎuLiｓｔ（){printf("\n\n\ｎ＝＝==＝===＝＝========＝＝====＝=\n");pｒiｎtf(" １**＊**＊＊Iｎseｒt LA＼ｎ＂);printf(" 2*****＊* Inｓｅrt LＢ\ｎ")；pｒｉnｔf(＂3＊****** Ｄelｅte LA＼n");priｎtf(" 4 ******* Dｅleｔe LB＼n＂);priｎtf（" 5 ******* Uniｏn LA and LB＼n"）；printf(" 6 ＊***＊**MergｅLＡand LB to LC\n＂); prｉntf(" 7 ＊**＊**＊prinｔLinｋList\n＂);ｐrinｔｆ（" 8 ***＊*＊＊Ｅxit\n＂);ｐrｉｎｔf(＂＝====＝=＝==＝=====＝====＝==＝=\n＂); }/*Seｌｅcｔthｅｍenu*/voｉｄMenuSeｌecｔ(LiｎkLｉst *La,LiｎkＬist *Lb){ inｔsｅlｅct,ｄone=1;ＬｉnkLｉst Ｌc;whｉle (ｄone) {MeｎuＬiｓｔ（);prinｔf(＂input thｅoｐｅrating ｃode : "）;scanf（＂%ｄ＂,&seｌeｃt);swiｔcｈ(ｓelect)｛caｓe1：Inseｒt(La）；brｅaｋ;ﻩ case 2：Insert(Lb）;brｅａk;ﻩ case３：Deletｅ(La);ｂreaｋ;ﻩ case ４: Delete(Lｂ);bｒeａk;ﻩ case５: Unｉon（Ｌａ，Ｌｂ);brｅak；ﻩ caｓｅ6: MergeLiｓｔ(La,Lb,&Lc)；ﻩﻩｐrｉntf("LC: ＂);printlｋ（Lc）；ﻩbreａk;case 7：ｐrintf("LA: ");prinｔｌk（*Lａ)；ﻩ pｒｉntf("ＬB: ＂);printlk(*Lb);break；ｃasｅ８: done=０;bｒeaｋ;ﻩｄefault: pｒiｎtf(＂ERROR\n");}｝}mａin( ){LinkList La,Ｌb;ｐrｉntf(＂LA");Iｎit（＆Ｌa) ；ｐrintｌk（La);prｉntf（＂ＬB");Inｉt(&Lb) ；pｒｉntlk(Lb);MenuSeleｃｔ(&La,&Lb)；｝调试后的代码:#ｉncｌude<ｓtdio.h>#ｉnｃlude＜ｍａllｏc.h>typｅdef iｎｔ DataType;ｔypｅdef struct ＬinkList{int data；ｓｔruct LinｋList ＊ｎext;}LinｋList；void PｒiｎtList(LｉnkＬist *h)；LinkLisｔ* IniｔLisｔ()；vｏiｄ InsList(ＬinｋＬisｔ *h,int i,ＤatａＴyｐe x）; voｉd LocLisｔ（LiｎkLiｓt *h,int i);vｏid DelList(LｉｎkList *ｈ,iｎｔi）；void maｉn(){iｎt i,ｎ，ｘ；LinkList *ｈ；ﻩh＝IniｔＬist()；PrinｔList（h);printｆ("\ｎ==＝＝=====＝=\n");printf("０--－－－-EXIT\n＂）；ﻩｐrｉntf("1--－---INSEＲT\ｎ");ﻩprｉnｔf（"２--－－-－DEＬEＲＴ\n＂);ﻩpｒｉｎtf("３--－---LOCＥＲT\n")；pｒintｆ(＂\n＝=＝＝＝＝＝＝===\ｎ\n＼n");ﻩwhile(1)ﻩ｛ﻩprintｆ("＼nＳelect\n");ﻩsｃaｎf("%d",&ｎ);switcｈ(n)ﻩ{ﻩcaｓe 0：ﻩﻩﻩexit（０);ﻩbｒｅaｋ；ﻩﻩcase 1:ﻩprintf(＂please inｐuｔｔhｅ position:\n");ﻩｓcanｆ(＂%d",&ｎ);ﻩﻩﻩpｒintf("please ｉｎｐuｔｔhｅ data:＼n"）;ﻩｓcanf("%ｄ",&x);IｎsLｉsｔ(h,n,x);ﻩＰrinｔLisｔ(h);break;ﻩcase 2:pｒintｆ("pｌease input you wanｔｔo delete poｓitiｏn：\n＂);ﻩﻩﻩｓcanf("%d",＆i);ﻩﻩDｅlList（h,i）;ﻩﻩＰrintＬist(h);ﻩbreaｋ;ﻩcase ３:ﻩﻩprintf（"ｐleaｓe inｐut ｙou wａnt to ｓearch pｏsition:＼n")；ﻩsｃanｆ（"%ｄ＂,&i）;ﻩﻩLocList(h,ｉ)；ﻩPriｎtList(ｈ);ﻩﻩｂrｅak;ｄeｆault :ﻩprintf("eｒror＼n"）;ﻩｂｒｅａk；ﻩ｝}ﻩ}LinkLｉst＊ IｎitＬist(）{ﻩ LinｋLｉst *ｈ,*s,*r;ﻩ int a，ｃ,ｉ;ﻩ h=(ＬiｎkLｉst*)mａlｌoｃ(sizeｏf(LinｋLiｓt）)；ﻩh-＞ｎｅxt=NＵＬＬ;r＝h;ﻩ prｉnｔf（"ｐleａse inpuｔ some linｋ's leｎgｔh:"）;ﻩscaｎｆ(＂%d"，&c）；ﻩ for(ｉ=０;i<c;i+＋){sｃanf("%ｄ＂,&ａ);ﻩ s=(LinｋＬｉst*)maｌloc(sizeｏf（LinkLiｓt)）; ﻩ s-＞ｄata＝a;ﻩﻩｓ->nexｔ=ｒ->nｅｘt；ﻩr->nｅxt=s；ﻩﻩ r=ｒ-＞nｅxt;｝ﻩｒetuｒn h;｝voｉd IｎsLisｔ(LinkList *h,ｉnt i,DataType x){LinkＬist *s，*p；ﻩiｎt j＝1;ﻩp=h;ｓ=（LinkList＊)maｌｌoｃ(siｚeｏf(LｉｎkＬist)); ﻩfoｒ(j=1;j<i ＆＆p!=NULL；j+＋)p＝ｐ－＞next;ﻩif(p=＝NUＬＬ)pｒintf("erｒor!\n");ﻩelｓe{ﻩs-＞datａ=x;ﻩs－>next=p->ｎｅｘt;p-＞ｎeｘt＝s;ﻩﻩ}}voｉｄ DelLiｓt(LinkLiｓt ＊h,int i）{ＬiｎｋList *p,*q;ﻩinｔ j=１;p=h->ｎｅｘｔ;ﻩq=ｐ->next;ｗhilｅ（j!=i-1 ＆& q!=NULL)ﻩ｛ﻩp=ｐ-＞nｅxt;ﻩｑ=q－>next;ﻩﻩj++;ﻩ｝if(q=＝ＮULL）pｒｉntf（"ｅrror!\n"）;elｓeﻩ{ｐ->nｅｘt=q－＞ｎeｘt;ﻩﻩfreｅ(ｑ)；}｝voiｄ LｏcＬist(LinｋLisｔ＊h,int i){LinkLｉｓt ＊p;ｉnｔj=1;p=h－＞neｘt;ﻩwhile(p!=ＮULL){ﻩiｆ(p->data==i)ﻩ{ﻩpｒintf（＂position iｓ％d\n",ｊ);ﻩbrｅak;ﻩ}ﻩp＝ｐ->neｘt;ﻩﻩj+＋；}iｆ(p==NULL)ﻩprinｔf("NＯ thiｓ data ｉｎthｅ link＼ｎ"); }void ＰriｎtLｉst（LｉnkLｉst*h）{LinｋＬist *p;ｐ=h->ｎｅxｔ;ﻩwhilｅ（ｐ！=NULＬ)ﻩ{ﻩprintf(" %ｄ->",ｐ->datａ);ｐ=p-＞neｘｔ;ﻩ｝}四、运行输出结果：五、调试和运行程序过程中产生的问题及采取的措施：问题:子函数和主函数前后的调用出现问题,指针的调用不是太明白。