链表基本操作实验报告

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

2、 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; re

3、turn l;将链表结尾赋空值，返回头结点l头结点l2 .单链表插入void linkedlistinsert(linkedlist l,int i,elemtype x)链表插入函数(l头指针，i插入位置，x插入元素)linkedlist p,s; te义结构体类型指针 p,sj=1;p=l;定义整型j计数，寻找插入位置，p指针指向头结点p=p->next;j+;满足条件时p指针后移，j自力口 1while(p&&j<i) 当p为真且j<i时循环p=null|j<iyprintf("插入位直小止确n");s=(lnode *)mal

4、loc(sizeof(lnode);使用malloc函数动态分配存储空间，指针s指向新开辟的结点，并将插入元素x存放到 新开辟结点s的数据域，将结点 s指向i+1 结点位置，第i个结点指向s,实现了链表 元素插入。s->data=x; s->next=p->next; p->next=s;3 .单链表的删除:p->next=p->next->next;四、运行结果1 .单链表初始化胄选择要进行的操作.初始化 2.清空 3.求链表长馍 4.检查链表是否为空遍历链表6.从链表中查找元素；从捱表中查找与给定元素值相同的元素在顺序表中的位置 响捱表中越道二漫国

5、除运三施函邃 再他犍退出“ * .iix： 12 .创建单链表验沁戒链表中的元素，输入t结束 88435-6-13.求链表长度4检查链表是否为空5 .遍历链表麟帝的土素如 9 0 0 4 3 5-66 .从链表中查找元素啬施入待查询元素在链表中的位置4 也装第1个兀素的情关9俞人:叭待查询元素在链表中的位置;2谯衷第2不元素的值为州施入;6畲植入待查询元素在链表中的位置用询位置不正蠲7.从链表中查找与给定元素值相同的元素在顺序表中的位置元为 7ii有8 :人中 m8.向链表中插入元素插入元素之后的链表pa： 5键表甲的元素为： 9 b 1® g 4 3 5 -69.从链表中删除元素删

6、除位置为6的元素（是3）10.清空单链表1a：2 铺表己经清空h3a： 链表为空五、实验体会经过这次单链表基本操作实验，自己的编程能力有了进一步的提高，认识到自 己以前在思考一个问题上思路不够开阔， 不能灵活的表达出自己的想法，虽然在 打完源代码之后出现了一些错误， 但是经过认真查找、修改，最终将错误一一修 正，主要是在写算法分析的时候出现了障碍， 经过从网上查找资料，自己也对程 序做了仔细的分析，对单链表创建、插入、删除算法画了详细的 n-s流程图。# 、 c 语言版原代码# include<stdio.h># include<stdlib.h>/* 定义 elemt

7、ype 为 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()linkedlist l;l=(linkedlist)malloc(sizeof(lnode);l->next=null;return l;/* 清空单

8、链表*/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;p=l->next;if(p=null) printf(" 单链表为空表n");else

9、printf(" 链表中的元素为： 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->ne

10、xt;j=1;while(p!=null&&j<i)p=p->next;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

11、x) linkedlist p,s;int j;j=1;p=l;while(p&&j<i)p=p->next;j+;if(p=null|j>i)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=

12、1;p=l;while(p->next&&j<i)p=p->next;j+;if(p->next=null)printf(" 删除位置不正确 n");elsen",i);-1 结束 n");q=p->next;p->next=q->next;free(q);printf("第%d个元素已从链表中删除linkedlist linkedlistcreat()linkedlist l=linkedlistinit(),p,r;elemtype x;r=l;printf(" 请依次输入

13、链表中的元素，输入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()int d;printf(" 请选择要进行的操作n");printf("n");printf("1. 初始化 2. 清空 3. 求链表长度4. 检查链表是否为空n");prin

14、tf("n");printf("5. 遍历链表 6. 从链表中查找元素n");printf("n");printf("7. 从链表中查找与给定元素值相同的元素在顺序表中的位置n");printf("n");printf("8. 向链表中插入元素 9. 从链表中删除元素 10 创建线性表n");printf("n");printf(" 其他键退出。 。 。 n");printf(" 输入 : ");scanf(&quo

15、t;%d",&d);return(d); main()int quit=0;int i,locate;elemtype e;linkedlist l,p;while(!quit)switch(scan()case 1:l=linkedlistinit();printf("n");break;case 2:linkedlistclear(l);printf("n");break;case 3:printf(" 链表长度为 %dn",linkedlistlength(l);break;case 4:if(linkedli

16、stempty(l)printf("链表为空 n");else printf(" 链表非空 n");break;case 5:linkedlisttraverse(l);break;case 6:printf(" 请输入待查询元素在链表中的位置:");scanf("%d",&i);p=linkedlistget(l,i);if(p) printf("链表第 阶元素的值为:%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");scanf("%d%d",&i,&a