【C++数据结构与算法基础篇 -1】C++实现线性表的插入、删除、查找等操作
实现线性表的插入、删除、求表长、查找给定值 e、查找第 i 个位置元素等基本操作，要求编写的程序以菜单方式工作；用链式存储结构实现一元多项式的相加运算；利用双向链表实现通讯录的建立、删除、检索和列表，并可保存至文件，可重新装入
目录
一、实验目的
1. 掌握线性表的逻辑结构和物理结构实现；
2. 掌握线性表的顺序存储结构和链式存储结构，熟悉对线性表的基本操作， 包括插入、删除、查找、线性表的合并等操作；
3. 熟悉循环链表的实现及其基本操作；
4. 锻炼将理论知识转化为实践操作的能力。
二、实验原理
线性表是最简单的一种数据结构，线性表是由 n（n>=0）个数据元素组成的有限序列。线性表中的数据元素可以是各种各样的，但是同一个线性表中的数据元素必须具有相同的属性，因此具有相同的数据类型。
在计算机内，可以用不同的方式来表示线性表，其中最简单和最常用的方式是用一组地址连续的存储单元依次存储线性表中的元素，其特点是逻辑上相邻的两个数据元素来物理上也相邻，一般可以用一个一维数组来描述线性表的顺序结构，简称为顺序表。线性表的另一种表示形式是链式存储结构（简称链表）的特点是用一组任意的存储单元存储线性表中的数据元素，不要求逻辑上相邻的元素在物理上也相邻，链表中的每个结点可以用结构体类型（C 语言）或类（Java、C++等）来描述，链表又分为单链表、循环链表、双向链表。
三、题目要求
四、代码实现
单链表创建操作（头插法）
//单链表创建操作《头插法)
void CreateList_qian(Linklist &L, int n)
{
Linklist p;
for(int i = 0; i < n ; ++i)
{
p = new LNode;
cout <<"请输入插入第”<< i+1 <<“个插入的数据:";
cin >> p->data;
p->next = L->next;
L->next = p;
}
cout<<"创建成功!"<<endl;
}单链表的创建操作(尾插法)
//单链表的创建操作(尾插法)
void CreateList_wei(Linklist &L,int n)
{
Linklist r;
Linklist p;
r=L;
for(int i = 0 ; i < n ; ++i)
{
p = new LNode;
cout <<"请输入插入第"<< i+1 << "个插入的数据:";
cin >> p->data;
p->next = NULL;
r->next = p;
r = p;
cout <<"创建成功!"<< endl;
Sleep(1000);
}
}打印单链表的Data城
//打印单链表的Data城
void PrintList(Linklist &L, int n)
{
Linklist p;
p = L->next;
int i = 0;
while(p != NULL && i < n)
{
cout <<"第"<< i+1 <<"个节点的Data域为:"<< p->data << endl;
p = p->next;
++i;
}
if(L->next == NULL)
cout <<"该链表为空"<<endl;
Sleep(1000);
}
单链表插入操作
//单链表插入操作
void InserList(Linklist &L,int i,int e)
{
int j = 0;
Linklist p;
p = L;
while(p &&(j< i -1))
{
p = p->next;
++j;
}
if(!p ||(j>i-1))cout <<"插入失败"<<endl;
Linklist s;
s = new LNode;
s->data = e;
s->next =p->next;
p->next = s;
cout<<"插入成功"<<endl;
Sleep(1000);
}单链表删除操作
//单链表删除操作
void Delete(Linklist &L,int i)
{
int j = 0;
Linklist p;
p=L->next;
while((p->next)&&(j<i-1))
{
p = p->next;
++j;
}
if(!(p->next)||(j>i-1))
{
cout<<"删除失败"<<endl;
}else{
Linklist r;
r = p ->next;
p->next = p->next->next;
delete r;
cout<<"删除成功"<<endl;
}
Sleep(1000);
}清空链表
//清空链表
void ClearList(Linklist &L)
{
Linklist p,q;
p=L ->next;
while(p)
{
q = p ->next;
delete p;
p=q;
}
L ->next = NULL;
cout<<"清空成功"<<endl;
Sleep(1000);
}查找定值e、 查找第i个位置元素
//查找定值e
void LocateElem(Linklist &L,int e)
{
int i = 0;
Linklist p;
p =L->next;
while(p->data != e&&p)
{
p = p->next;
++i;
}
cout<<"元素e在第"<<i+1 <<"个节点"<<endl;
Sleep(1000);
}
//查找第i个位置元素
void GetElem(Linklist &L,int i)
{
Linklist p;
int j =1;
int e;
p = L->next;
while(p&&j<i-1)
{
p = p->next;
++j;
}
if(!p||j>i)cout<<"第"<< i<<"个位置元素不存在"<<endl;
e = p->data;
cout<<"第"<<i<<"个元素的Data域为："<<e<<endl;
Sleep(1000);
}创建菜单
void Menu()
{
cout<<" "<<endl;
cout<<"——————————————"<<endl;
cout<<"单链表菜单"<<endl;
cout<<"1.单链表创建操作（前插法）"<<endl;
cout<<"2.单链表创建操作（后插法）"<<endl;
cout<<"3.打印单链表的Data域"<<endl;
cout<<"4.单链表插入操作"<<endl;
cout<<"5.单链表删除操作"<<endl;
cout<<"6.清空单链表"<<endl;
cout<<"7.查找定值e"<<endl;
cout<<"8.查找第i个位置元素"<<endl;
cout<<"9.退出"<<endl;
}主函数
//主函数
int main()
{
Linklist La;
InitList(La);
int i;
do
{
Menu();
cout<<"请输入菜单功能序号：";
cin>>i;
switch(i)
{
case 1:
int a;
cout<<"请输入创建元素个数：";
cin>>a;
CreateList_qian(La,a);
break;
case 2:
int b;
cout<<"请输入创建元素个数:";
cin>>b;
CreateList_wei(La,b);
break;
case 3:
PrintList(La,a);
break;
case 4:
int c;
int e1;
cout<<"请输入插入元素位置:";
cin>>c;
cout<<endl;
cout<<"请输入插入元素的 Data域：";
cin>>e1;
InserList(La, c ,e1);
a++;
break;
case 5:
int d;
cout<<"请输入删除位置：";
cin>>d;
Delete(La,d);
a--;
break;
case 6:
ClearList(La);
break;
case 7:
int e2;
cout<<"请输入元素值：";
cin>>e2;
LocateElem(La,e2);
break;
case 8:
int f;
cout<<"请输入元素位置：";
cin>>f;
GetElem(La,f);
break;
case 9:
break;
}
}
while(i != 9);
}
五、运行结果
线性表插入结果：
删除结果：
求表长结果：
查找给定值e结果：
查找第 i 个位置元素结果：
六、实验总结及体会
这次的线性表实验使我充分了解到线性表的巨大作用，掌握了线性表的创建、删除、插入、合并等操作.使我能够用线性表实现许多功能，对程序又有了更深的了解，并且让我懂得了算法和结构的重要性，让我对这门课程有了更大的兴趣。
1、通过实验还提高了一点改错能力，对于一些常见问题加深了印象；
2、编程需要有耐心，尤其实在单步调试的时候，更是马虎不得，有时候关键就是那么一步，错过了就得从头来过了。、编程需要细心，有时一个不注意小错误就能引出大问题。编程也需要规范，不仅为了他人能看得懂程序，也为了方便自己以后程序的更改与进一步的完善；
3、程序由算法和数据结构组成，一个好的程序不仅算法重要，数据结构的设计也很重要；
4、由于编程的积累，我发现调试程序的速度明显加快了，这是个很好的进步，不过，我编程的速度仍然有待提高
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
14
0- 0
已为社区贡献2条内容
所有评论(0)