线性表的操作实现(链表)
- 格式：doc
- 大小：58.00 KB
- 文档页数：6
线性表操作的实现(链表)一．任务链表的定义及其相关操作。
二．训练目的（1）进一步掌握指针变量的用途和程序设计方法。
（2）掌握线性表的结构特征，以及链式存储结构的特点及程序设计方法。
（3）掌握构造链表的基本方法。
（4）掌握链表的插入、删除和查找等算法的设计方法。
三．任务描述线性表是一种重要的线性结构，常采用顺序表或链表作为存储结构，基本的操作有插入、删除和查找等。
线性表的链式存储结构的本质：在逻辑上相邻的两个数据元素a i-1, a i，在存储地址中不一定相邻。
四．任务要求任务分“基本要求”与“拓展要求”两部分，“基本要求”部分为必做题，“拓展要求”部分为选做题。
1．基本要求（1）定义线性表的链式存储结构。
（2）编写建立链表的函数。
（3）编写遍历链表的函数。
（4）编写查找值为 e 的元素, 返回它的位置的函数。
（5）编写在链表中进行插入的函数。
（6）编写在链表中进行删除元素的函数。
（7）编写带菜单的测试主函数并上机运行。
打印出运行结果，并结合程序运行结果进行分析。
2．拓展要求（1）编写销毁链表的函数。
（2）编写求链表的长度的函数。
（3）编写单链表中第一个等于item更新为it的函数。
五．工作过程1．数据结构设计链表的数据元素类型为int。
如下是其定义，请在下划线处填上相应代码，使其完整。
typedef ———— ElemType;typedef struct {ElemType data;——————*next;} LNode;2. 程序的模块结构本次实验的程序模块结构如下图所示。
头文件ds22.h包括数据结构定义及功能函数说明，实现文件ds22.cpp包括功能函数的定义，主文件ds22main.cpp包括主调函数。
3．功能(函数)说明如下是链表的常见操作的函数说明，其中（1）-（6）为必做部分，余下为选做部分。
请为所做部分的操作的函数说明建立头文件ds22.h。
#include<iostream>typedef int ElemType;typedef struct LNode {ElemType data;struct LNode *next;} LNode;LNode *Creat_L();void Insert_L(LNode *L,int i ,ElemType e);ElemType Delete_L(LNode *L,int i);int Locat_L(LNode *L,ElemType e);void Out_L(LNode *L);void Destory(LNode *L);int length(LNode *L);4.功能(函数)定义请为所做部分的操作进行函数定义，并建立源文件ds22.cpp。
#include<iostream>using namespace std;typedef int ElemType;typedef struct LNode {ElemType data;struct LNode *next;//建立线性链表LNode *Creat_L(){LNode *h,*p,*s;int x,n;h=(LNode *)malloc(sizeof(LNode));h->next=NULL;p=h;cout<<"请输入你想输入的数字的个数n：";cin>>n;cout<<"\n 请分别输入链表所保存的值："<<endl;for(int i=1;i<=n;i++){s=(LNode *)malloc(sizeof(LNode));s->next=NULL;cin>>x;s->data=x;p->next=s;p=s;}return(h);}//插入操作void Insert_L(LNode *L,int i ,ElemType e){LNode *p,*s;p=L;int k=0;while(p!=NULL&&k<i-1){p=p->next;k++;}if(k>i-1||p==NULL){cout<<"\n 你插入的位置不合理。
";//就是这不对以后记得修改 }else {s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;}}//删除操作ElemType Delete_L(LNode *L,int i){LNode *p,*s;int k=0;s=L;while(s->next!=NULL&&k<i-1){s=s->next;k++;if(s->next==NULL){cout<<"你删除的位置不合理"; return -1;}//就是这不对以后记得修改 else {p=s->next;s->next=p->next;free(p);}return NULL; }//按值查找int Locat_L(LNode *L,ElemType e){int k=0,m;LNode *p=L;while(p->next!=NULL){p=p->next;k++;if(p->data==e)m=k;else {m=0;break;}}return m;}//遍历链表void Out_L(LNode *L){LNode *p;p=L->next;while(p!=NULL){cout<<p->data<<" ";p=p->next;}}void Destory(LNode *L){LNode *p,*s;int k=0;s=L;while(s!=NULL){p=s->next;s->next=p->next;s=p->next;free(p);}free(s);}int length(LNode *L){LNode *p,*s;int k=0;s=L;p=s->next;s->next=p->next;s=p->next;k++;}return k;}5.界面设计建立源文件ds22main.cpp，设计带菜单的测试函数。
#include<iostream>#include"ds.h"using namespace std;void main(){int k;LNode *p;do{cout<<"\n";cout<<"\n";cout<<"\n 1. 建立单链表 " ;cout<<"\n 2. 插入操作 ";cout<<"\n 3. 删除操作 ";cout<<"\n 4. 查找操作 ";cout<<"\n 5. 销毁";cout<<"\n 6. 长度";cout<<"\n 7. 结束程序运行";cout<<"\n======================================";cout<<"\n 请输入您的选择命令（1，2，3，4，5，6）";cin>>k; cout<<"\n";cout<<"\n";cout<<"\n";switch(k){case 1: {p=Creat_L();;//调用其相应的函数cout<<"\n ok"<<endl;}break;case 2: {int i,e;cout<<"请输入你所想插入的位置i和其对应的值data："<<endl;cin>>i>>e;Insert_L(p,i,e);//调用其相应的函数cout<<"现在的链表变为："<<endl;Out_L(p);cout<<endl;cout<<"\n ok"<<endl;}break;case 4: {int temp,e;cout<<"请输入所查找的值e:";cin>>e;temp=Locat_L(p,e);//调用其相应的函数if(temp!=0)cout<<"序号为："<<temp<<endl;else cout<<"\n \n你输入的数据有误。
";cout<<"\n ok"<<endl;}break;case 3: {cout<<"请输入你所想插入的位置i：";cin>>m;Delete_L(p,m);cout<<"现在的链表变为："<<endl;cout<<"\n";Out_L(p);//调用其相应的函数cout<<"\n ok"<<endl;}break;case 5: Destory(p);break;case 6: cout<<length(p)+1;break;}}while(k!=7);/*switch{}*/cout<<"\n 再见！";cout<<"\n 打回车键，返回。
";}/*main{}*/6. 调试分析设计测试数据，验证所设计函数的正确性。
打印出运行结果，并结合程序运行结果进行分析。
六. 思考题如果要将两个有序链表合并成一个链表，又该如何设计？七．心得体会对整个实验过程做出总结，对重要的算法做出性能分析。
八．实验报告要求每次实验要求提交完整的实验报告,实验报告的基本格式如下：1．设计人员相关信息（1）设计者姓名、学号和班号（2）设计日期（3）上机环境2．程序设计相关信息（1）实验题目（2）实验项目组成（3）实验项目的程序结构（程序中的函数调用关系图）（4）实验项目包含的各个文件中的函数的功能描述（5）算法描述或流程图（6）实验数据和实验结果。
