2023年链表实验报告

《数据结构》实验报告二

系别：嵌入式系统工程系班级：嵌入式11003班一

学号:__________________姓名:孙立阔____________

日期:2023年4月9日—指导教师:申华

一、上机实验的问题和规定:

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

找、插入与删除。具体实现规定：

1.从键盘输入10个字符，产生不带表头的单链表，并输入结点值。

2.从键盘输入1个字符，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则，

则显示“找不到”。

3.从键盘输入2个整数，一个表达欲插入的位置i,另一个表达欲插入的数值X,将x插入在

相应位置上，输出单链表所有结点值，观测输出结果。

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

5.将单链表中值反复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有

结点值，观测输出结果。

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

7.(★)将单链表分解成两个单链表A和B,使A链表中具有原链表中序号为奇数的元素,

而B链表中具有原链表中序号为偶数的元素，且保持本来的相对顺序，分别输出单链表A

和单链表B的所有结点值，观测输出结果。

二、程序设计的基本思想，原理和算法描述:

(涉及程序的结构，数据结构，输入/输出设计，符号名说明等)

创建一个空的单链表，实现对单链表的查找,插入，删除的功能。

三、源程序及注释：

#defineOK1

#defineERROR0

#defineINFEASIBLE-1

#defineOVERFLOW-2

#defineTRUE1

#defineFALSE0

#defineList_Init_Size10

#defineListlncrement2

typedefcharET;

typedefET*Ep;

typedefintStatus;

typedefstructLNode{

ETdata;

structLNode*next;

。}LNode,*LinkList；

/*LinkListLa,Lb,Lc；*/》

#inc1ude"stdio.h"

#include"al1oc.h"

/"Displaythe1inklist'selements.*/

voidprintlk(LinkListL){

LinkListp;

p=L—>next;

while(p){

printf(u%c->",p->data);

p=p->next;

)

printfC'NULLXn")；

I

/*Creatlink1istfromheadnode.*/

voidCreatList(LinkList*L,intn){

inti;

LinkListp,q;

ETstr[20],c;

p=(LinkList)malloc(sizeof(LNode));

p->next=NULL;

*L=q=p;

printf("Pleaseinputthedata:")；

for(i=n;i>0;i-){

p=(LinkList)maHoc(sizeof(LNode));

c=getche();/*scanf("%c",&c)；5f7

printf(n\n\nn);

p->data=c；

p->next=q->next;

q->next=p；

}

/*Initthelinklist.*/

voidInit(LinkList*L){

intn；

printf("Pleaseinputthenumberofthenode:");

scanf("%d",&n);

CreatList(L,n);

)

/*Getthevalueofe1emen11;*/

intGetE1em(LinkListL,inti,ET*e){

intj=1;

LinkListp;

p=L->next;

while(p&&j<i){

p=p—>next；

++j；

)

if(!p|Ij>i)returnTRUE；

*e=p—>data;

returnFALSE;

)

/*InsertaelementafterI*/

intListinsert(LinkList*L,inti,ETe){

/*Addyourowncodes.*/

)

/*DeletetheelementI*/

intListDe1ete(LinkList*L,inti,ET*e)

(

/*Addyourowncodes.*/

)

intInsert(LinkList*L){

inti,flag;

ETdata；

printf("P1easeinputtheposition:");

scanf("%d",&i);

printf('*Pleaseinputthedata;

data=getche();/*scanf("%c"，&data)；*

flag=ListInsert(L,i,data);

returnflag;

)

StatusDelete(LinkList*L){

inti,f1ag;

ETe;

printf(nPleaseinputthenumber:")；

scanf(n%d",&i);

flag=ListDe1ete(L,i,&e);

printf(nDeletedelementis%c\n",e);

returnf1ag;

/*Findtheelement*sposition.*/

intLocateElem(LinkListL,ETe){

inti=0;

LinkListp;

p=L->next;

while(p){

i++；

if(p->data==e)returni;

)

return0;

}

/*AddtheLbaftertheLa.*/

voidUnion(LinkList*La,LinkList*Lb){

LinkListpa,pb;

/*Addyourowncodes.*/

)

/*Mergetwosequenceintoone,don'tchangeanye1ementsin

thesetwo1inklists.Jointwosequencetoone.*/

voidMergeList(LinkList*L1,LinkList*L2,LinkList*L3){

LinkListpa,pb,pc;

/*Addyourowncodes.*/

)

/*ListtheMenu*/

voidMenuList(){

printf("\n\n\n===========================\n")；

printf(”1*******InsertLA\n");

printf(n2*******InsertLB\nM)；

printf(M3*******DeleteLA\n");

printf(M4*******DeleteLB\nn);

printf("5*******UnionLAandLB\n");

printf(n6*******MergeLAandLBtoLC\n");

printf(n7*******printLinkList\nn);

printf("8*******Exit\n");

pr]ntf(—————™—xz——————————————————n)•

/"Selectthemenu*/

voidMenuSelect(LinkList*La,LinkList*Lb){

intseiect,done=1;

LinkListLc；

while(done){

MenuList();

printf("inputtheoperatingcode：");

scanf("%d”,&se1ect);

switch(se1ect){

ocase1:Insert(La);break;

case2:Insert(Lb);break；

case3：Delete(La);break;

case4：Delete(Lb)；break;

case5：Union(La,Lb)；break;

case6:MergeList(La,Lb,&Lc)；

eprintf(”LC:")；printIk(Lc);

。break；

ocase7：printf(ULA：n);printlk(*La)；

printf(nLB:");printlk(*Lb);

obreak;

case8:done=0；break;

default:printf("ERROR\nM);

)

)

)

main(){

LinkListLa,Lb;

printf("LA”)；

Init(&La);

printlk(La);

printf("LB")；

Init(&Lb);

printlk(Lb)；

MenuSe1ect(&La,&Lb);

调试后的代码:

Winc1ude<stdio.h>

Sinc1ude<ma11oc.h>

typedefintDataType;

typedefstructLinkList

(

intdata;

structLinkList*next；

}LinkList;

voidPrintList(LinkList*h)；

LinkList*InitList();

voidInsList(LinkList*h,inti,DataTypex);

voidLocList(LinkList*h,inti);

voidDelList(LinkList*h,inti);

voidmain()

(

inti,n,x；

^LinkList*h;

山=InitList()；

田rintList(h)；

printf(“\n==========\n");

叩0-------EXIT\n");

printfCl---------INSERT"”)；

printf("2--------DELERT'n");

printf("3----------L0CERT\n〃)；

printf("\n\n\n\n");

while(1)

K

，printf("\nSelectXn^);

scanf("%d",&n);

switch(n)

3(

叱ase0:

3exit(0)；

eak;

acase1:

gprintf("pleaseinputtheposition：\n");

»scanf(”%d”,&n);

gprintf(npleaseinputthedata:\n")；

»scanf("%d",&x);

oInsList(h,n,x)；

rintList(h)；

。break；

ase2：

oprintf("pleaseinputyouwanttodeletepo

sition:\n")；

scanf(M%d",&i)；

De1List(h,i);

^PrintList(h);

必break;

gcase3:

。printf(，zp1easeinputyouwanttosearchposition:\n〃)；

scanf(H%dn,&i)；

aLocList(h,i)；

PrintList(h);

»4)reak;

default:

printf("error\n");

gbreak;

)

4

)

LinkList*InitList()

(

，LinkList*h,*s,*r;

inta,c,i;

h=(LinkList*)malloc(sizeof(LinkList));

h—>next=NULL;

r=h;

printf("pleaseinputsome1ink'slength:n);

scanf;

for(i=0;i<c;i++)

，scanf("%d”,&a)；

s=(LinkList*)malloc(sizeof(LinkList));

gs->data=a；

。s->next=r->next;

、r->next=s；

3r=r->next；。

}

returnh;

)

voidInsList(LinkList*h,inti,DataTypex)

(

^LinkList*s,*p;

intj=1;

dP=h;

&s=(LinkList*)malloc(sizeof(LinkList))；

for(j=l;j<i&&p!=NULL；j++)

ep=p->next;

if(p==NULL)

fiprintf("error!\n");

else

(

比一〉data=x；

s->next=p—>next；

师一>next=s；

)

voidDelList(LinkList*h,inti)

(

»LinkList*p,*q;

intj=l;

p=h—>next;

q=p->next；

while(j!=i-1&&q!=NULL)

。｛

«p=p