数据结构实验报告

线性表的基本操作实现及其应用 一、实验目的

1、熟练掌握线性表的基本操作在两种存储结构上的实现。

2、会用线性链表解决简单的实际问题。

二、实验内容

题目一、该程序的功能是实现单链表的定义和操

作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示： please input the operation：

1.初始化 2.清空 3.求链表长度 4.检查链表是否为空

5.检查链表是否为满 6.遍历链表（设为输出元素）7.从链表中查找元素

8.从链表中查找与给定元素值相同的元素在表中的位置

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 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 个结点之前插入新的元素 x }

8、 从单链表中删除元素

void LinkedListDel(LinkedList L,DataType x) { 删除以 L 为头指针的单链表中第 i 个结点 } 9、 用尾插法建立单链表

LinkedList LinkedListCreat( )

㈡、函数调用及主函数设计

主函数 求单链表的长度 LinkedListLength(LinkedList L){ } 从单链表表中查找元素LinkedList LinkedListGet(Lin向单链表中插入元素 LinkedListInsert(LinkedList L,int i) kedList L,int i,DataType x) 从单链表中删除元素LinkedListDel(Lin用尾插法建立单链表 LinkedList LinkedListCreat( ) kedList L,DataType x) ㈢ 程序调试及运行结果分析 实验数据

运行时出现：

然后选择下列操作：选择8，用尾插法建立链表

选则操作2，求链表的长度

然后选择操作3，遍历链表

然后选择操作4，从链表中查找元素

然后选择操作5，从链表中查找与给定元素值相同的元素在表中的位置

然后选择个操作6，向链表中插入元素，之后再遍历链表

然后选择操作7 从链表中删除元素之后再遍历链表

㈣实验总结

通过这次线性表的基本操作实现及其应用实

验的学习，我学会了链表的许多基本操作，懂得如何用C语言去编程序，懂得了许多链表方面的知识，也认识到了自己的不足，需要在今后的学习中更加努力，学好接下来的课程。

四、主要算法流程图及程序清单

1、主要算法流程图：

开始界面 主函数 求链表长度 遍历链表 查找节点 插入元素 删除元素 建立链表 输出数据 结束 2、程序清单 #include #include #include #include

#define MAX_SIZE 100//链表的最大长度 typedef int DataType; typedef struct LNode {

DataType data;

struct LNode *next;

}LNode,*LinkedList;

LinkedList LinkedListInit();//初始化单链表

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 LinkedListDel(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++){ cout<<\"please input the operation\"<cout<<\"\\n 1.初始化\"<<\"\\n 2.求链表长度\"<< \"\\n 3.遍历链表（设为输出元素）\";

cout<<\"\\n 4.从链表中查找元素 \"<<\"\\n 5.从链表中查找与给定元素值相同的元素在表中的位置\";

cout<<\"\\n 6.向链表中插入元素\"<<\"\\n 7. 从链表中删除元素\"<<\"\\n 8.尾插法建立链表\"<<\"\\n 9.结束!\"<cout<<\"请输入你所需的操作:!\"<>a;

if(a==1) {

LinkedListInit(); }

else if(a==2) {

cout<<\"链表长度:\"<}

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( L, x); }

else if(a==6) {

int i,x;

cout<<\"请输入要插入的位置和数据：\"<cin>>i>>x;

LinkedListInsert( L, i, x); }

else if(a==7) {

cout<<\"请输入要删除的位置：\"<>a;

LinkedListDel(L,a); }

else if(a==8) {

int n;

cout<<\"请输入要创建的元素个数：\"<cin>>n;

L=LinkedListCreat(L,n); }

else if(a==9) exit(0); else {

cout<<\"输入错误，请重新选择\"<LinkedList LinkedListInit() //初始化单链表 {

LinkedList L;

L=(LinkedList )malloc(sizeof(LinkedList)); //创建头节点

L->next=NULL; L->data=0;

return L; }

int LinkedListLength(LinkedList L) //求单链表的长度 {

LinkedList 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) {

cout<data; m=m->next; } }

LinkedList LinkedListGet(LinkedList L,int i)

// 从单链表表中查找元素 {

LinkedList p; p=L->next;

int j=1;

while(p&&jp=p->next; j++; }

if(!p||j>i) return 0; else {

cout<data; return p; } }

LinkedList LinkedListLocate(LinkedList L, DataType x)

//从单链表表中查找与给定元素值相同的元素在链表中的位置

{

int i=1,m=0;

if(L->next==NULL) return 0; else {

LinkedList p=L->next; while(p) {

if(p->data==x) {

m++;

cout<<\"位置为第\"<} i++;

p=p->next; }

if(m>0)

return p; else

return 0; } }

void LinkedListInsert(LinkedList i,DataType x)

//向单链表中插入元素 {

LinkedList p,s; int j=0; p=L;

while(p&&jp=p->next; j++; }

if(!p||j>=i-1)

cout<<\"插入失败!\"<s=(LinkedList )malloc(sizeof(LNode));

s->data=x; s->next=p->next; p->next=s; }

L,int

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; // 先建立一个带头结点的单链表

LinkedList q=L;

for (int i = 1; i<=n; i++) {

LinkedList p=(LinkedList) malloc (sizeof (LNode));

cout<<\"请输入数据：\"<>p->data; // 输入元素值

p->next = NULL; q->next = p; // 插入表尾q之后 q=p; //指针后移，使q始终指向表尾

}

L->data=LinkedListLength(L); return L; }