链表实验报告

链表实验报告

———————————————————————————————— 作者: ———————————————————————————————— 日期：

《数据结构》实验报告二

系别:嵌入式系统工程系 学号:１1160400３１4 日期：2012年４月９日

班级:嵌入式1１0０3班 姓名：孙立阔 指导教师:申华

一、上机实验的问题和要求：

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

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ｉze 10 ＃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 \ｔdio.h＂ #inclｕdｅ \ｌｏｃ.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->nｅxｔ; }

ｐrinｔf(\Ｕ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(＂％ｃ\＊/ printf(\ｎ\\n\

ｐ->ｄaｔa = c；

ｐ－>next = q-＞next; q->next = p；

} ｝

/*Iniｔ ｔhｅ ｌｉｎklist. */ void Ｉnｉt（LｉnkＬist *L) { int n;

printf(\ｌease ｉｎｐuｔ the ｎuｍｂｅr of the node : \ sｃanf（＂%d\ 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＆&jnext; ++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(\ｉnput tｈｅ daｔa : ＂）;

daｔa ＝ getche(); /*scａnｆ(\＂,&ｄatａ);＊／