链表基本操作实验报告
- 格式：doc
- 大小：133.10 KB
- 文档页数：9
精品文档 . 实验2 链表基本操作实验 一、实验目的 1． 定义单链表的结点类型。 2． 熟悉对单链表的一些基本操作和具体的函数定义。 3． 通过单链表的定义掌握线性表的链式存储结构的特点。 二、实验内容与要求
该程序的功能是实现单链表的定义和主要操作。如：单链表建立、输出、插入、删除、查找等操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。 要求： 同学们可参考指导书实验2程序、教材算法及其他资料编程实现单链表相关操作。必须包括单链表创建、输出、插入、删除操作，其他操作根据个人情况增减。
三、 算法分析与设计。 1.创建单链表： LinkedList 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; 将链表结尾赋空值，返回头结点L
头结点L L ......
^
^ An A1 A2 精品文档
. 2.单链表插入
p s s->data=x; s->next=p->next; p->next=s;
3.单链表的删除： p
p->next=p->next->next;
void LinkedListInsert(LinkedList L,int i,ElemType x) 链表插入函数 （L头指针，i插入位置，x插入元素） LinkedList p,s;定义结构体类型指针p,s j=1;p=L; 定义整型j计数，寻找插入位置，p指针指向头结点 p=p->next;j++; 满足条件时p指针后移，j自加1
while(p&&jp=NULL||jN
printf("插入位置不正确\n"); s=(LNode *)malloc(sizeof(LNode)); 使用malloc函数动态分配存储空间，指针s指向新开辟的结点，并将插入元素x存放到新开辟结点s的数据域，将结点s指向i+1结点位置，第i个结点指向s，实现了链表元素插入。
a b x
b c 精品文档
. 四、 运行结果 1.单链表初始化
2.创建单链表 3.求链表长度 4.检查链表是否为空 5.遍历链表
6.从链表中查找元素
7.从链表中查找与给定元素值相同的元素在顺序表中的位置 精品文档
. 8.向链表中插入元素 插入元素之后的链表 9.从链表中删除元素
删除位置为6的元素(是3) 10.清空单链表
五、 实验体会 经过这次单链表基本操作实验，自己的编程能力有了进一步的提高，认识到自己以前在思考一个问题上思路不够开阔，不能灵活的表达出自己的想法，虽然在打完源代码之后出现了一些错误，但是经过认真查找、修改，最终将错误一一修正，主要是在写算法分析的时候出现了障碍，经过从网上查找资料，自己也对程序做了仔细的分析，对单链表创建、插入、删除算法画了详细的N-S流程图。 精品文档
. 六、 C语言版原代码 # include # include
/* 定义ElemType 为int类型*/ typedef int ElemType; # define TRUE 1 # define FALSE 0 # define NULL 0 # define flag -1
/*单链表的结点类型*/ typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkedList;
/*初始化单链表*/ LinkedList LinkedListInit() {LinkedList 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; 精品文档 . p=L->next; if(p==NULL) printf("单链表为空表\n"); else { 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->next;j=1; while(p!=NULL&&j{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 x) {LinkedList p,s; int j; j=1;p=L; 精品文档 . while(p&&j {p=p->next;j++;} if(p==NULL||j>i) printf("插入位置不正确\n"); else{s=(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&&j{p=p->next;j++;} if(p->next==NULL) printf("删除位置不正确\n"); else {q=p->next;p->next=q->next;free(q); printf("第%d 个元素已从链表中删除\n",i); } }
LinkedList 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()
