单链表的基本操作

1、实验题目线性表的链式存储结构小组合作姓名班级学号一、实验目的实验（一）1 .掌握线性表的存储方式、表示方式2 .掌握线性表的基本操作，以及其如何用代码实现实验（二）1 .掌握元素在线性表中的存储以及表示方法，如何取数据元素2 .拓展：将存有偶数个元素的线性表中的奇数项、偶数项分别抽出，组成一个新的线性表，并将新的线性表输出二.实验环境DevC+三、实验内容与步骤实验（一）内容：线性表的链式存储结构，简称链表，有单链表和双链表两类。单链表是一种基本的数据结构，有两部分组成：指针域和数据域，数据域用于存放数据，指针域用于指向下一个结点的位置。为了操作方便,一般为单链表创建一个头结点，指向线性表的的

2、首元素。线性表的最后一个元素的指针域为空，表示链表的结束。通顺序表一样，链表也有许多基本操作，如：(1)单链表的创建(2)单链表元素的插入(3)单链表元素的删除(4)单链表元素的查找(定位)步骤：1 .引入相关的头文件，宏定义2 .创建一个结构体，用于表示链表的结构3 .创建一个空的单链表4 .向单链表中添加数据5 .查找单链表中的元素6 .删除单链表的元素实验(二)内容：已知单链表已创建好，表示为LinkList=a1,b1,a2,b2,.an,bn将单链表拆分，使得a1,a2,.an的成一个单链表，剩余的元素构成一个单链表，编程实现。(1)创建单链表，添加2n个元素(2)将链表拆分为两个子

3、链表步骤：7 .引入相关的头文件，宏定义8 .创建一个结构体，用于表示链表的结构9 .创建一个空的单链表10 .向单链表中添加数据11 .调用拆分链表的函数，用于实现对链表的拆分工作12 .输出拆分后的单链表四、实验过程与分析实验（一）1）引入头文件，进行相关的定义操作#include<stdio.h>#include<stdlib.h>#defineOK1#defineERROR0typedefintElemType;typedefintStatus;typedefstructLNodeElemTypedata;structLNode*next;LNode,*Link

4、List;2）编写链表的初始化函数，用于头结点的初始化操作voidInitList（LinkListL）L->next=NULL;L->data=0;printf（"带有头结点的单链表初始化完毕nn"）;3）单链表的遍历函数，用于输出单链表的结点值/遍历单链表voidPrintList（LinkListL）LNode*p;p=L->next;if（p=NULL）printf（"单链表为空nn"）;return;printf（"单链表的结点值为："力while(p)printf("%d",p->

5、;data);p=p->next;)printf("nn");)4)结点的头插法：用于在头结点之后插入一个结点结点头插法StatusInsertHead(LinkListL)/创建结点LNode*p;ElemTyped;printf("请输入结点的值：")；scanf("%d",&d);p=(LNode*)malloc(sizeof(LNode);p->data=d;p->next=L->next;L->next=p;printf("头插法插入结点成功nn");returnOK

6、;)5)结点的尾插法：用于在链表的末尾，插入一个结点/结点尾插法StatusInsertTail(LinkListL)LNode*p,*q;ElemTyped;printf("请输入结点的值：")；scanf("%d",&d);p=L;q=(LNode*)malloc(sizeof(LNode);q->next=NULL;q->data=d;while(p->next)p=p->next;p->next=q;printf("尾插法创建单链表成功nn");returnOK;)6)单链表元素的查找：用

7、于获取某个位置的元素/获取单链表中的第i个元素StatusGetElem(LinkListL,intloc)inti=0;LNode*p;p=L->next;while(p)i+;if(i=loc)printf("单链表的第d个元素是：dnn",loc,p->data);break;)p=p->next;)if(!p)printf("该位置超过单链表的长度nn");returnERROR;)returnOK;)7)单链表结点的删除删除单链表中的第i个结点StatusDeleteNode(LinkListL,intloc)inti;LNo

8、de*p,*q;p=L;if(!p->next)printf("单链表为空nn");returnERROR;)if(loc<=0)printf("位置必须大于0nn");returnERROR;)for(i=0;i<loc-1;i+)p=p->next;if(!p)/说明单链表结束printf("第个元素不存在n",loc);returnERROR;)q=p->next;p->next=q->next;free(q);printf("结点删除成功n");returnOK;)

9、8)在主函数中调用相关的函数intmain(void)LinkListL;L=(LNode*)malloc(sizeof(LNode);InitList(L);InsertHead(L);InsertHead(L);PrintList(L);InsertTail(L);InsertTail(L);PrintList(L);GetElem(L,4);DeleteNode(L,1);PrintList(L);DeleteNode(L,0);PrintList(L);return0;)9)编译链接源代码，后运行exe文件：二hrevoOeiktQpClinkliit.exe中有头皓点跑单施我初始化完

10、毕请输入结点的值工10）调用头插法的函数，分别输入10,20,分别回车:带有头结点的单链式初始化完毕请输入结点的俏，10头插法排入结点成功请输入结点的值：20头插法插入结点成功单维融的结点值为；201011）调用尾插法的函数，分别输入30,40J、NJ。iV'7岁，%星产，lHiiR11nLjAVI带仃头结点的用链&初始化完毕请输入结点的值：10女后法插A蓟点成功请输人结点的俏：20女插法插入引点成功单链表的结点值为：2010请输入结点的值；30星插法创建单能表成功请输入结点的假;40尾插法创建单链表成功单链友的豺立伯为：2010304012）查找单链表的第四个元素:带有头结点

11、的单铢表初始化完毕请输入站点的值1W头插法插入结点成功请输入结点的值：20i:插法插入结点成功单链表的结点值为：2010请输入结点的值；30尾插法创建单链表成功请输入结点的值；40虐播法创建单链表成功单链表的结点值为:20103040单链表的第4个元素是；4013）主函数中传入参数，删除单链表的第一个结点:请输入结点的世：1。头插法插入站点成功请输入结点的伯：20实插注法人结点成功单链表的站点仅为：2010请输入结点的值：30尾捕法创建单链表成功请输入结点的俯；40尾插法创建单链表成功单链我的结点值为：20103040单链衣的第4个元素是：40结点删除成功单性表的结点优为；10304014）主

12、函数传入参数，删除第0个未位置的元素，程序报错:C；Usersinechre/oCcsktopClinklist.exe产行头结点的单货去物始化完毕请输入结点的伯；10头插法插入结点成功请输入结点的他；20性播法猫入结点成功单链衣的结点值为:201C请愉入结点的俏：30性插法创建单链衣成功请摘入结点的值：40悭插法创建单链表成功推战我的结点值为：2C103040R链去的第4个元素是：40结点删除成功单链表的结点值为：103040位置必须大于015)最后，输出单链表中的元素：CAUserimecirevoDesl(topCinkli&t.带有头站点的里锦表初始化完毕有输入结点的值二10义

13、播法插入结点成功请输入结点的梢；20头插法插入站点成功平链衣的结点值为：2010请输入结点的值;30尾插法创建单曾表成功请输入结点的值，4Q国摘法创建单藤表成功单依去的结点值为：20103040“镇友的第4个元素足：40结点删除成功单静去的结点伯为：1U3030住置必须大于0健走的结山值为：1。3040ProcessexitedAfter5&75secondsvithre实验(二)1)引入相关的头文件，进行宏定义#include<stdio.h>#include<stdlib.h>typedefstructNodeintdata;structNode*next;

14、Node,*LinkList;2)初始化函数，用于对头结点初始化和插入元素(尾插法)voidinit(LinkListL)inti,n;Node*p;L->data=0;L->next=NULL;printf("线性表初始化完成n");printf("请输入线性表的个数(偶数个)：")；scanf("%d",&n);if(n%2!=0)printf("请输入偶数个数据n");return;for(i=0;i<n;i+)p=(Node*)malloc(sizeof(Node);scanf(&

15、quot;%d",&p->data);p->next=L->next;L->next=p;printf("数据插入完成n");3)单链表的输出函数voidprint(LinkListL)Node*p;p=L->next;printf("线性表的元素为：n");while(p)printf("%d”,p->data);p=p->next;)printf("nn");)4)单链表的拆分函数，把单链表拆分成两个:voidcreate(LinkListL)Node*p,*q

16、,*t;/q指向L1,t指向L2LinkListL1,L2;L1=(Node*)malloc(sizeof(Node);L2=(Node*)malloc(sizeof(Node);L1->next=NULL;L2->next=NULL;L1->data=0;L2->data=0;q=L1;t=L2;p=L->next;while(p)q->next=p;p=p->next;q=q->next;q->next=NULL;t->next=p;p=p->next;t=t->next;t->next=NULL;)print(L1);print(L2);p=L;)5)在主函数中进行函数的调用intmain(void)LinkListL;L=(Node*)malloc(sizeof(Node);init(L);print(L);create(L);return0;)6)编译，连接，运行源代码："FC:IJ5ec5mechrevo>Desktopdivicle,exe物生表初始化完成1请输入线性甚的个数（偶数个）*7）输入8,回车，并输入8个数，用空格分隔开，根据输出信息,可以看出，链表已经拆分为两个线性衣初始化完成请输入线性衣的个数（偶数个）:887654321数据插入化成线性衣的元宏为工123