数据结构实验报告

1、 线性表的基本操作实现及其应用 一、实验目的1、熟练掌握线性表的基本操作在两种存储结构上的实现。2、会用线性链表解决简单的实际问题。二、实验内容 题目一、该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示：please input the operation： 1.初始化 2.清空 3.求链表长度 4.检查链表是否为空 5.检查链表是否为满 6.遍历链表（设为输出元素）7.从链表中查找元素 8.从链表中查找与给定元素值相同的元素在表中的位置

2、 9.向链表中插入元素 10. 从链表中删除元素 其他键退出。 其中黑体部分必做三、实验步骤、数据结构与核心算法的设计描述1、单链表的结点类型定义/* 定义DataType为int类型 */typedef int DataType;/* 单链表的结点类型 */typedef struct LNode DataType data; struct LNode *next;LNode,*LinkedList;2、初始化单链表 LinkedList LinkedListInit() 3、 遍历单链表void LinkedListTraverse(LinkedList L) 4、 求单链表的长度int

3、LinkedListLength(LinkedList L) 5、 从单链表表中查找元素 LinkedList LinkedListGet(LinkedList L,int i) /L是带头结点的链表的头指针， 返回第 i 个元素 6、从单链表表中查找与给定元素值相同的元素在链表中的位置 LinkedList LinkedListLocate(LinkedList L, DataType x) 7、 向单链表中插入元素 void LinkedListInsert(LinkedList L,int i,DataType x) / L 为带头结点的单链表的头指针，本算法 / 在链表中第i 个结点之

4、前插入新的元素 x 8、 从单链表中删除元素 void LinkedListDel(LinkedList L,DataType x) 删除以 L 为头指针的单链表中第 i 个结点 9、 用尾插法建立单链表 LinkedList LinkedListCreat( )、函数调用及主函数设计主函数求单链表的长度LinkedListLength(LinkedList L) 从单链表表中查找元素LinkedList LinkedListGet(LinkedList L,int i)向单链表中插入元素 LinkedListInsert(LinkedList L,int i,DataType x)从单链表中

5、删除元素LinkedListDel(LinkedList L,DataType x)用尾插法建立单链表 LinkedList LinkedListCreat( ) 程序调试及运行结果分析实验数据运行时出现：然后选择下列操作：选择8，用尾插法建立链表选则操作2，求链表的长度然后选择操作3，遍历链表然后选择操作4，从链表中查找元素然后选择操作5，从链表中查找与给定元素值相同的元素在表中的位置然后选择个操作6，向链表中插入元素，之后再遍历链表然后选择操作7 从链表中删除元素之后再遍历链表实验总结 通过这次线性表的基本操作实现及其应用实验的学习，我学会了链表的许多基本操作，懂得如何用C语言去编程序，懂

6、得了许多链表方面的知识，也认识到了自己的不足，需要在今后的学习中更加努力，学好接下来的课程。四、主要算法流程图及程序清单1、主要算法流程图：主函数开始界面求链表长度遍历链表查找节点插入元素删除元素建立链表输出数据结束2、程序清单 #include#include#include#include#define MAX_SIZE 100/链表的最大长度typedef int DataType;typedef struct LNodeDataType data;struct LNode *next;LNode,*LinkedList;LinkedList LinkedListInit();/初始化单

7、链表int LinkedListLength(LinkedList L);/求单链表的长度void LinkedListTraverse(LinkedList L);/遍历单链表LinkedList LinkedListGet(LinkedList L,int i);/ 从单链表表中查找元素 LinkedList LinkedListLocate(LinkedList L, DataType x);/从单链表表中查找与给定元素值相同的元素在链表中的位置void LinkedListInsert(LinkedList L,int i,DataType x);/向单链表中插入元素 void Lin

8、kedListDel(LinkedList L,DataType x) ;/从单链表中删除元素LinkedList LinkedListCreat(LinkedList L,int n);/尾插法建立单链表void main()int a;LinkedList L;L=(LinkedList) malloc (sizeof (LNode);L-next=NULL;for(a=1;a=10;a+)coutplease input the operationendl; coutn 1.初始化n 2.求链表长度 n 3.遍历链表（设为输出元素）; coutn 4.从链表中查找元素 n 5.从链表中查

9、找与给定元素值相同的元素在表中的位置; coutn 6.向链表中插入元素n 7. 从链表中删除元素n 8.尾插法建立链表n 9.结束!endl; cout请输入你所需的操作:!a; if(a=1)LinkedListInit();else if(a=2)cout链表长度:LinkedListLength(L)endl;else if(a=3)LinkedListTraverse(L);else if(a=4)int i;cout请输入要查找的位置：i; LinkedListGet(L,i);else if(a=5)int x;cout请输入要查找的数据：x;LinkedListLocate(

10、L, x);else if(a=6)int i,x;cout请输入要插入的位置和数据：ix;LinkedListInsert( L, i, x);else if(a=7) cout请输入要删除的位置：a;LinkedListDel(L,a);else if(a=8)int n; cout请输入要创建的元素个数：n;L=LinkedListCreat(L,n);else if(a=9) exit(0);elsecout输入错误，请重新选择next=NULL; L-data=0;return L;int LinkedListLength(LinkedList L)/求单链表的长度LinkedLis

11、t p;int i=0;p=L;while(p)p=p-next ;i+;return i;void LinkedListTraverse(LinkedList L)/遍历单链表LinkedList m; m=L; while(m!=NULL)coutdata;m=m-next;LinkedList LinkedListGet(LinkedList L,int i)/ 从单链表表中查找元素 LinkedList p;p=L-next;int j=1;while(p&jnext;j+;if(!p|ji) return 0;else coutdata;return p;LinkedList Lin

12、kedListLocate(LinkedList L, DataType x)/从单链表表中查找与给定元素值相同的元素在链表中的位置int i=1,m=0;if(L-next=NULL)return 0;elseLinkedList p=L-next;while(p)if(p-data=x)m+;cout位置为第i个结点next;if(m0)return p;else return 0;void LinkedListInsert(LinkedList L,int i,DataType x)/向单链表中插入元素 LinkedList p,s;int j=0;p=L;while(p&jnext;j

13、+;if(!p|j=i-1)cout插入失败!data=x; s-next=p-next; p-next=s;L-data=LinkedListLength(L);void LinkedListDel(LinkedList L,DataType x) /从单链表中删除元素LinkedList p, q; / p指针指向待删除结点；q为跟踪指针，指向其前驱。 q=p=L; /初始化指针 p=p-next; /q指向第一个结点 while(p!=NULL)&(p-data!=x) q=p; p=p-next; / p!=NULL& p-data!=x,指针后移，继续向后查找 / q始终指向p的前驱 if(p= NULL) printf(X not found); else q-next=p-next;/修改指针, 删除结点X free (p); L-data=LinkedListLength(L); LinkedList LinkedListCreat(LinkedList L,int n)/尾插法建立单链表L=(LinkedList) malloc (sizeof (LNode);L-next = NULL; / 先建立