2023年链表基本操作实验报告.docx

实验2 链表基本操作实验一、实验目的1 .定义单链表的结点类型。2 .熟悉对单链表的一些基本操作和具体的函数定义。3 .通过单链表的定义掌握线性表的链式存储结构的特点。二、实验内容与规定该程序的功能是实现单链表的定义和重要操作。如：单链表建立、输出、插 入、删除、查找等操作。该程序涉及单链表结构类型以及对单链表操作的具体的 函数定义和主函数。程序中的单链表(带头结点)结点为结构类型，结点值为整型。规定：同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关 操作。必须涉及单链表创建、输出、插入、删除操作，其他操作根据个人情况增 减。三、算法分析与设计。1 .创建单链表：Li n kedList L i n k e d L i s t Creat ()创建链表函数Li n k e dList L =Lin k e dLis t I n i t (),p, r;调用初始化链表函数r =L; i指向头结点使用ma Hoc函数动态分派存储空间，指针p指向新开辟的结点，并将元素 存放到新开辟结点的数据域，p= (Link e d L i s t ) mallo c ( s iz e o f (LNode);p->d a t a =x;。r >nc x t =p；将新的结点链接到头结点r之后°r= p ;i指向p结点s canf(”%d ” ,&x);满足条件循环输入链表元素while(x!= f lag)当输入不为一1时循环r->nex t =NULL； return L；将链表结尾赋空值，返回头结点Lr 二L;P r i nt f ("请依次输入链表中的元素,输入T结束rT);scan f ("% d ", &x);whi Ie ( x ! =f la g )p= (Link edList)ma I I o c (s i z e o f (LNode);p->d a ta=x;。r->next=p; r =P； scanf ( " % d ", &x)；r->nex t =NULL; retur n L；)i n t scan () i n t d ;pr i n t千(”请选择要进行的操作n ")；print f ("n").print f ( " 1.初始化 2 .清空 3.求链表长度 4.检查链表是否为空 n ");p r i ntf ("n ")； print f ("5.遍历链表6.从链表中查找元素n”)； r / iiprintf (”7.从链表中查找与给定元素值相同的元素在顺序表中的位置n”)；p r i n t f ( n");pr i nt f ( " 8.向链表中插入元素9 .从链表中删除元素10创建线性表'n "); anwn");printf("其他键退出。n H )；printf ("输入：");scanf ("%d " , &d);r e t u r n (d);mai n () i n t qu i t = 0；i nt i , I ocate；EIemType e;Link edList L , p;w h i I e (!qu i t)s w i tch (sc a n ()。case 1 :L=L i nked List I nit () ;pr in t f ("n") ; b r e ak;。c ase 2:L inkedL i stC I ear (L); p r in t f ("n ");break;。c ase 3: p r intf ("链表长度为 dn", L i nk e d L i st Length (L)；break；。 case 4 : i f (Li n ke d Li stEm p ty (L) pr i nt f ("链表为空rT)； oselse p r i ntf ("链表非空 n ") ; break ；。 case 5： LinkedL i s t T ravers e (L); b reak;。 cas e 6:pi nt f ("请输入待查询元素在链表中的位置：")；。 scanf;。 p =L i nk e dL i s tGet (L, i);。3 if (p) pr i n t f ("链表第%d 个元素的值为：%d n", i , p -> d ata);。else p r i n t f ("查询位置不对的rT)；。 break;。case 7:pr i ntf ("请输入待查询元素的值：”)；。 sea nf ("%d " , &e)；。s 。 locate = Linke d Li s t Locate ( L, e);。 if (loc a te)。p r i n tf ("%d 在链表中的位置是:dn", e, loc ate);。else pr intf("链表中没有值为%d的元素n”，e);。 bre a k;。case 8:print f ("请输入插入元素的位置和值(中间以空格或回车分 隔)：n"); scanf (" d%d"，& i , &e)；。 Li n k e dLi st I n s ert (L , i, e);。 brea k ;。 case 9: i f (L i n ke d L i st L e ngth (L) =0)。pr i ntf (“链表已经为空，不能删除!n“)；6 6elseprintf ("请输入待删除元素的位置：");。scanf ("%d " , & i);。L i nkedL i s t De I(L , i) ;。 break;cas e 1 0 :L=L i n k edLi s tC r eat 0 ；p r i nt f ("n " ) ； brea k ;d efault:quit=1;)2.单链表插入void L in k e dLi s t 1 nsert( L ink e dL i st L, i n t i , E 1 emType x)链表插入函 数(L头指针，i插入位置,x插入元素)L ink e dList p,s;定义结构体类型指针p,sj= 1 ；p=L;定义整型j计数，寻找插入位置,P指针指向头结点p=p-> n ext： j+; 满足条件时p指针后移，j自加1whil e (p&&j<i)当p为真且j <i时循环p=NULL|0<TNp r in t f("插入位置不对的' n");s=(LNode *) ma 1 1 oc ( s iz e o f (LN o d e )；使用malloc函数动态分派存储空间，指针s 指向新开辟的结点,并将插入元素x存放到 新开辟结点s的数据域，将结点s指向i+l 结点位置，第i个结点指向s,实现了链表 元素插入。s->d a ta=x; s ->ne x t =p->n ext; p-> n e xt= s ；3.单链表的删除:p - >n e xt= p >ncx t -> n ext;四、运营结果.单链表初始化请选择要进行的操作二品m二洛不一工吊信雇展二装曾踵而酝庭 捻百卷菱一【仄届菱而百块品案工仄卷粪市面逅至嬴纂庙相百而品翥瀛屏嘉而应承 8前后蝠菽浣纂一；:仄赢美而藤元泰二痴雇函S美 RitSW 值二二一Sei A 11 .创建单链表事会次输火链表中的元素，输入T结束 9 8 0 4 3 5 -6 -12 .求链表长度.检查链表是否为空4空 三 三 kfex 向废.遍历链表物八* 5链表中的元素为:9 8 0 4 3 5 -6.从链表中查找元素入:用地人待查询元素在链表中的位置:1懈蓑第1个亓素粉微：9售地入待查询元素在链表中的位置：2 暴装第2个元素就f知8.从链表中查找与给定元素值相同的元素在顺序表中的位置10己插入到链表中插入元素之后的链表输入：5 链表中的元素为： 98100435-69 .从链表中删除元素输入: 9请输入待删除元素的位第6个元素己从链表申删除位置为6的元素（是3 ）御入：5链表中的元素为:9 8 10 0 4 5 -6.清空单链表胸入：2 触表己经清空五、实验体会通过这次单链表基本操作实验，自己的编程能力有了进一步的提高，结识到自 己以前在思考一个问题上思绪不够开阔，不能灵活的表达出自己的想法，虽然在 打完源代码之后出现了一些错误，但是通过认真查找、修改，最终将错误一一修 正，重要是在写算法分析的时候出现了障碍，通过从网上查找资料，自己也对程 序做了仔细的分析，对单链表创建、插入、删除算法画了具体的N-S流程图。六、C语言版原代码i n c I u d e< s t d i o . h ># i nc I u d e< s td I i b . h >/*定义ElemType为int类型*/type d ef i nt EIemTy p e；define TRUE 1# define FALSE 0define NULL 0# d efine fl a g _1/*单链表的结点类型* /typed e f s t ruct LNod e(。ElemType da ta;。s t rue t LNod e * n ext；LNo d e , *L ink e dLi st ；/*初始化单链表*/Linke d Li s t Li n kedListlnitO(LinkedLi s t L;L= (Link e d L i s t)m a I Ioc (s i zeof (LNo d e);。L-> n ext = NULL;re t u r n L;)/*清空单链表*/void L i nke d L i s t Cl ear (Li n kedLi st L)(L->n e xt=NULL;pri ntf （"链表已经清空n”）；/*检查单链表是否为空*/i nt Link e d L i stEm p ty (L i nkedL i st L) i f (L->next=NULL) ret u r n TRUE ;。eIse retu r n FALSE;/*遍历单链表*/vo i d L in k ed L istTra v er s e (LinkedL i st L)LinkedL i s t p ；p = L->next;if (p二二NULL) pr intf ("单链表为空表 n ”)；e I se(。printf("链表中的元素为:n " );whi I e (p! = N ULL) pr i ntf("%d ", p->data)； p=p->n e xt； ° p r intf ("n");)i nt L i nkedL istLength (L i nk e d Li st L) L i nk e dLi st p;int j;。p = L->next;。j=O;whi Ie( p ! =NU L L )。j + + ; p=p->nex t ;Li n k e d L i st L i n kedL i s tGet (Link edL i st L, i n t i)Link edLi st p; i n t j ;p=L->next; j=1;whi le(p!=NULL&&j< i )p=p->next;j+；)if ( j = i)return p ;e I se r e turn NULL；)i n t Link edL i stL o cate (L i nked List L , EI emT yp e x)(Li nk e d L i st p; int j ；p =L-> n ext;j=1；whi I e (p!=NU LL&&p->dat a !二 x)° p = p->next; j+ + ;)if (p) return j；。else retur n 0；)voi d Li n k edL i stl n s ert (L i n kedL i st L, int i, E I e mT y p e x) (L i n kedLi st p, s ;int j ;j = 1 ；P=L;while (p&&j < i )p = p->next; j +; i f ( p = = NULL| | j> i)p rint千("插入位置不对的n");e I se s 二(LNode *) m a I I o c ( s i zeof (L Nod e );。 s->d a t a=x;s-> n ext= p >nex t ;。 p ->ne x t=s ；P r i nt f ("%d已插入到链表中、n " , x)；)void L i nk e d Li s t De I (Linke d L i st L, i n t i) (LinkedLis t p, q； in t j ；j = 1 ；P=L；whi I e (p >next&&j< i )p=p->nex t ; j+; if (p->next二二NULL)P r in t f ("删除位置不对的n");else q=p->next; p->nex t =q>nex t ; f r e e (q);pr intf ("第%d个元素已从链表中删除n"，i )；1)Li n k e dL i st Li n ked List Cre a t ()(Li nkedL i s t L = L i nkedL i st I nit () , p, r ;E IemType x ;