【线性表的基本操作实现及其应用 】

线性表的基本操作实现及其应用

1.实验目的
⑴ 熟练掌握线性表的基本操作在两种存储结构上的实现，其中以熟悉各种链表的操作为重点。
⑵ 巩固高级语言程序设计方法与技术，会用线性链表解决简单的实际问题。
2.实验原理与要求
⑴ 按照数据结构实验任务书，提前做好实验预习与准备工作，独立完成。
⑵ 任选一题，多选者并且保质保量完成适当加分。
⑶ 严格按照数据结构实验报告模板和规范，及时完成实验报告。
3.实验内容（实验内容为多选，请在自己所做题目前打“√” ）
⑴ 顺序表的表示与操作实现
完成顺序表建立、输出、插入、删除、查找和统计等基本操作与算法实现
√⑵ 单链表的表示与操作实现
完成单链表建立、输出、插入、删除、查找和统计等基本操作与算法实现
4.实验步骤
（说明：依据实验内容分别说明实验程序中用到的数据类型的定义、主程序的流程以及每个操作（成员函数）的伪码算法、函数实现、程序编码、调试与分析、总结、 附流程图与主要代码）
4.1数据结构与核心算法的设计描述
⑴ 单链表的结点类型定义
/* 定义DataType为int类型 /
typedef int DataType;
/ 单链表的结点类型 */
typedef struct LNode
{ DataType data;
struct LNode *next;
}LNode,*LinkedList;
⑵ 初始化单链表,建立一个带头结点的单链表
LinkedList LinkedListInit()
{LinkedList L;
L=(LinkedList)malloc(sizeof(LNode));
L->next=NULL;
printf(“初始化完成！\n”);
return L;
}
⑶ 清空单链表
void LinkedListClear(LinkedList L)
{ L->next=NULL;
}
⑷ 遍历单链表
void LinkedListTraverse(LinkedList L)
{LinkedList p;
p=L->next;
while(p!=NULL)
{printf(“%d “,p->data);
p=p->next; }
}
⑸ 求单链表的长度
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<i )
{p=p->next; j++; }
if (ji) return p;
else return NULL;
}
⑹ 从单链表表中查找元素
LinkedList LinkedListLocate ( LinkedList L, ElemType x)
{
LinkedList p;
p=L->next;
while ( p!=NULL && p->data != x)
p=p->next;
return p;
}
⑺ 从单链表表中查找与给定元素值相同的元素在链表中的位置
LinkedList LinkedListLocate ( LinkedList L, ElemType x)
{
LinkedList p;
p=L->next;
while ( p!=NULL && p->data != x)
p=p->next;
return p;
}
⑻ 向单链表中插入元素
void LinkedListInsert(LinkedList L, int i, ElemType x)
{LinkedList pre,p,s;int j;
pre=L;j=1;p=L->next;
while(pre&&j<i)
{pre=p;p=p->next;j++;}
if(preNULL)
{printf(“给的i值超过了表长”);exit(0);}
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
pre->next=s;
s->next=p;
return ;
}
⑼ 从单链表中删除元素
void LinkedListDel (LinkedList L,ElemType x)
{ LinkedList pre,p;int j;
pre=L;j=1;p=L->next;
while(p&&p->data!=x)
{pre=p;p=p->next;j++;}
if(p==NULL)
{printf(“表中没有值为x的结点”);exit(0);}
pre->next=p->next;
free§;
}
⑽ 用尾插法建立单链表
LinkedList LinkedListCreat( )
{ LinkedList L=LinkedListInit(),p,r;
ElemType x;
r=L;
printf(“please input data,input -1 is end\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;
}
4.2函数调用及主函数设计
函数的调用关系如下图1所示：

图1. 函数的调用关系
4.3 程序调试及运行结果分析
⑴ 程序调试过程
在编译过程中出现一处错误。

在经过调试后发现是129行的分号是中文符号下的，经过修改程序编译正常。

⑵ 运行结果分析
<1> 程序运行结果：

<2>选择输入“1” 初始化链表 ，测试结果如下：

<3>选择输入“10” ，尾插法建立单链表 ，运行结果如下：

<4>选择输入“3” ，求单链表长度 ，运行结果如下：

<5>选择输入“4”，运行结果如下：

<6>选择输入“5”，遍历单链表，运行结果如下：

<7>选择输入“6”，从链表中查找元素，运行结果如下：

<8>选择输入“7”，查找与给定元素值相同的元素在表中的位置，运行结果如下：

<9>选择输入“8”，向链表插入元素，运行结果如下：

<10>选择输入“9”，从链表中删除元素，运行结果如下：

4.4 实验总结
本次实验是在多次思考调试后才做出来的。经过这次单链表基本操作实验自己的编程能力有了进一步提高，认识到自己以前在思考问题上思路不够开阔，不能灵活的表达出自己的想法。
通过这次实验我知道了只有在切身编程中才能真正地理解掌握。今后更应勤加学习、练习，多看、多练、勤思考，以便更好的掌握数据结构这门至关重要的课程。
5主要算法流程图及程序清单
⑴ 主要算法流程图：
插入算法：

删除算法：

⑵ 程序清单
/* 定义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;
printf(“初始化完成！\n”);
return L;
}
/ 清空单链表 /
void LinkedListClear(LinkedList L)
{ L->next=NULL;
}
/ 检查单链表是否为空 /
int LinkedListEmpty(LinkedList L)
{if(L->next==NULL) return TRUE;
else return FALSE;
}
/ 遍历单链表 */
void LinkedListTraverse(LinkedList L)
{LinkedList p;
p=L->next;
while(p!=NULL)
{printf(“%d “,p->data);
p=p->next;
}
}
// 求单链表的长度
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<i )
{p=p->next; j++; }
if (ji) return p;
else return NULL;
}
// 从单链表表中查找与给定元素值相同的元素在链表中的位置
LinkedList LinkedListLocate ( LinkedList L, ElemType x)
{
LinkedList p;
p=L->next;
while ( p!=NULL && p->data != x)
p=p->next;
return p;
}
// 向单链表中插入元素
void LinkedListInsert(LinkedList L, int i, ElemType x)
{LinkedList pre,p,s;int j;
pre=L;j=1;p=L->next;
while(pre&&j<i)
{pre=p;p=p->next;j++;}
if(preNULL)
{printf(“给的i值超过了表长”);exit(0);}
s=(LNode *)malloc(sizeof(LNode));
s->data=x;
pre->next=s;
s->next=p;
return ;
}
// 从单链表中删除元素
void LinkedListDel (LinkedList L,ElemType x)
{ LinkedList pre,p;int j;
pre=L;j=1;p=L->next;
while(p&&p->data!=x)
{pre=p;p=p->next;j++;}
if(p==NULL)
{printf(“表中没有值为x的结点”);exit(0);}
pre->next=p->next;
free§;
}
// 用尾插法建立单链表
LinkedList LinkedListCreat( )
{ LinkedList L=LinkedListInit(),p,r;
ElemType x;
r=L;
printf(“please input data,input -1 is end\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()
{int d;
printf(“please input the operation\n”);
printf(“1.初始化\n”);
printf(“2.清空\n”);
printf(“3.求链表长度\n”);
printf(“4.检查链表是否为空\n”);
printf(“5.遍历链表\n”);
printf(“6.从链表中查找元素\n”);
printf(“7.从链表中查找与给定元素值相同的元素在链表中的位置\n”);
printf(“8.向链表中插入元素\n”);
printf(“9.从链表中删除元素\n”);
printf(“10.尾插法建立单链表\n”);
printf(“其他键退出\n”);
scanf(“%d”,&d);
return(d);
}
main()
{int quit=0;
int i;
ElemType e;
LinkedList L;
while(!quit)
switch(scan())
{case 1:L=LinkedListInit();break;
case 2:LinkedListClear(L);break;
case 3:printf(“the length is%d\n”,LinkedListLength(L));break;
case4:if(LinkedListEmpty(L))printf(“true\n”);else printf(“false\n”);break;
case 5:LinkedListTraverse(L);break;
case 6:printf(“please input the location.\n”);
scanf(“%d”,&i);
printf(“the num.is %d\n”,LinkedListGet(L,i));
break;
case 7:printf(“please input the element.\n”);
scanf(“%d”,&e);
printf(“the location.is %d\n”,LinkedListLocate(L,e));
break;
case 8:printf(“please input the insert location and insert num.\n”);
scanf(“%d%d”,&i,&e);
LinkedListInsert(L,i,e);
break;
case 9:printf(“please input the deleted element.\n”);
scanf(“%d”,&e);
LinkedListDel(L,e);
break;
case 10:L=LinkedListCreat();break;
default:quit=1;}
}