链表基本操作实验报告.doc

1、。实验 2链表基本操作实验一、实验目的1 定义单链表的结点类型。2 熟悉对单链表的一些基本操作和具体的函数定义。3 通过单链表的定义掌握线性表的链式存储结构的特点。二、实验内容与要求该程序的功能是实现单链表的定义和主要操作。 如：单链表建立、输出、插入、删除、查找等操作 。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。要求：同学们可参考指导书实验 2 程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。三、 算法分析与设计。1. 创建单链表：LinkedL

2、ist LinkedListCreat( )创建链表函数LinkedList L=LinkedListInit(),p, r;调用初始化链表函数r=L; r指向头结点使用 malloc 函数动态分配存储空间， 指针 p 指向新开辟的结点， 并将元素存放到新开辟结点的数据域，p=(LinkedList)malloc(sizeof(LNode);p-data=x;r-next=p;将新的结点链接到头结点r 之后r=p;r指向 p 结点scanf(%d,&x);满足条件循环输入链表元素while(x!=flag)当输入不为 -1 时循环r-next=NULL; return L;将链表结尾赋空值，返

3、回头结点L头结点 LL.AnA1A2。1。2. 单链表插入void LinkedListInsert(LinkedList L,int i,ElemType x)链表插入函数（L 头指针， i 插入位置， x 插入元素）LinkedList p,s;定义结构体类型指针p,sj=1;p=L;定义整型j 计数，寻找插入位置，p 指针指向头结点p=p-next;j+;满足条件时p 指针后移， j 自加 1while(p&ji)当 p 为真且 ji时循环p=NULL|jdata=x;s-next=p-next; p-next=s;3. 单链表的删除： pbcp-next=p-next-next;。2。

4、四、 运行结果1. 单链表初始化2. 创建单链表3. 求链表长度4. 检查链表是否为空5. 遍历链表6. 从链表中查找元素7. 从链表中查找与给定元素值相同的元素在顺序表中的位置。3。8. 向链表中插入元素插入元素之后的链表9. 从链表中删除元素删除位置为 6 的元素 ( 是 3)10. 清空单链表五、实验体会经过这次单链表基本操作实验， 自己的编程能力有了进一步的提高， 认识到自己以前在思考一个问题上思路不够开阔， 不能灵活的表达出自己的想法， 虽然在打完源代码之后出现了一些错误， 但是经过认真查找、 修改，最终将错误一一修正，主要是在写算法分析的时候出现了障碍， 经过从网上查找资料， 自己

5、也对程序做了仔细的分析，对单链表创建、插入、删除算法画了详细的N-S 流程图。4。六、C语言版原代码# include# include/*定义 ElemType 为 int类型 */typedef int ElemType;# define TRUE 1# define FALSE 0# define NULL 0# define flag -1/* 单链表的结点类型 */typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkedList;/* 初始化单链表 */LinkedList LinkedListInit()L

6、inkedList L;L=(LinkedList)malloc(sizeof(LNode);L-next=NULL;return L;/* 清空单链表 */void LinkedListClear(LinkedList L)L-next=NULL;printf(链表已经清空 n);/* 检查单链表是否为空 */int LinkedListEmpty(LinkedList L)if(L-next=NULL) return TRUE;else return FALSE;/* 遍历单链表 */void LinkedListTraverse(LinkedList L)LinkedList p;。5。

7、p=L-next;if(p=NULL) printf(单链表为空表 n);elseprintf(链表中的元素为： n);while(p!=NULL)printf(%d ,p-data); p=p-next;printf(n);int LinkedListLength (LinkedList L)LinkedList p;int j;p=L-next;j=0;while(p!=NULL)j+;p=p-next;return j;LinkedList LinkedListGet(LinkedList L,int i)LinkedList p;int j;p=L-next;j=1;while(p!=

8、NULL&jnext;j+;if(j=i) return p;else return NULL;int LinkedListLocate(LinkedList L,ElemType x)LinkedList p;int j;p=L-next;j=1;while(p!=NULL&p-data!=x)p=p-next;j+;if(p) return j;else return 0;void LinkedListInsert(LinkedList L,int i,ElemType x)LinkedList p,s;int j;j=1;p=L;。6。while(p&jnext;j+;if(p=NULL

9、|ji)printf(插入位置不正确 n);elses=(LNode *)malloc(sizeof(LNode);s-data=x;s-next=p-next;p-next=s;printf(%d已插入到链表中 n,x);void LinkedListDel(LinkedList L,int i)LinkedList p,q;int j;j=1;p=L;while(p-next&jnext;j+;if(p-next=NULL)printf(删除位置不正确 n);elseq=p-next;p-next=q-next;free(q);printf(第%d 个元素已从链表中删除 n,i);Link

10、edList LinkedListCreat()LinkedList L=LinkedListInit(),p,r;ElemType x;r=L;printf(请依次输入链表中的元素，输入-1 结束 n);scanf(%d,&x);while(x!=flag)p=(LinkedList)malloc(sizeof(LNode);p-data=x;r-next=p;r=p;scanf(%d,&x);r-next=NULL;return L;int scan()。7。int d;printf(请选择要进行的操作 n);printf(-n);printf(1.初始化 2.清空 3.求链表长度 4.检

11、查链表是否为空 n);printf(-n);printf(5.遍历链表 6.从链表中查找元素 n);printf(-n);printf(7.从链表中查找与给定元素值相同的元素在顺序表中的位置n);printf(-n);printf(8.向链表中插入元素9.从链表中删除元素10 创建线性表 n);printf(-n);printf(其他键退出。 n);printf(输入 :);scanf(%d,&d);return(d);main()int quit=0;int i,locate;ElemType e;LinkedList L,p;while(!quit)switch(scan()case 1:

12、L=LinkedListInit();printf(n);break;case 2:LinkedListClear(L);printf(n);break;case 3:printf(链表长度为 %dn,LinkedListLength(L);break;case 4:if(LinkedListEmpty(L)printf(链表为空 n);else printf(链表非空 n);break;case 5:LinkedListTraverse(L);break;case 6:printf( 请输入待查询元素在链表中的位置 :); scanf(%d,&i);p=LinkedListGet(L,i);

13、if(p) printf(链表第 %d个元素的值为 :%dn,i,p-data);else printf(查询位置不正确 n);break;case 7:printf(请输入待查询元素的值:);scanf(%d,&e);locate=LinkedListLocate(L,e);if(locate)printf(%d在链表中的位置是 :%dn,e,locate);else printf(链表中没有值为 %d的元素 n,e);break;case 8:printf(请输入插入元素的位置和值( 中间以空格或回车分隔 ):n);。8。scanf(%d%d,&i,&e);LinkedListInsert(L,i,e);break;case 9:if(LinkedListLength(L