线性表上机实习
1、实验目的
（1）熟悉将算法转换为程序代码的过程。
（2）了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。
（3）熟练掌握顺序表的基本运算：查找、插入、删除等，掌握顺序表的随机存取特性。
（4）了解线性表的链式存储结构，熟练掌握线性表的链式存储结构的C语言描述方法。
（5）熟练掌握线性链表（单链表）的基本运算：查找、插入、删除等，能在实际应用中灵活选择适当的链表结构。
2、实验要求
（1）熟悉顺序表的插入、删除和查找。
（2）熟悉单链表的插入、删除和查找。
3、实验内容:
① 顺序表
（1）抽象数据类型定义
typedef struct {
TypeData data[maxsize]; //容量为maxsize的静态顺手表
int n; //顺序表中的实际元素个数
}SeqList; //静态顺序表的定义
在本次实验中，首先建立一个空的静态顺序表，然后键盘输入数据存入表中，然后进入菜单选择界面，通过不同的数字输入，实现对顺序表，删除，插入，查找，显示等操作。
（2）存储结构定义及算法思想
在顺序表结构体的定义中，typedef int TypeData 为整型，存储结构如下：
for(n=0;n<m;n++){
cout<<"请输入线性表数据"<<endl;
cin>>L.data[n]; //顺序将数据存入顺序表
} //其他存储与此类似，都是直接赋值与数组的某一位
插入版块子函数：
void insert(SeqList &L) //插入数据
{
int a,b,c,k;
cout<<"请输入插入的数及其插入的位置"<<endl;
cin>>a>>b;
if(b<=0||b>(L.n+1)) {cout<<"不能在该位置插入"<<endl; return;} //判断插入位置是否合法
k=L.data[b-1];L.data[b-1]=a; c=L.n; L.n=L.n+1;
while(c>b){
L.data[c]=L.data[c-1];c--; //通过循环，实现插入位置后的数据挨个往后移动一位
}
L.data[b]=k;
}
顺序表的插入与删除操作类似，在插入与删除后，都要循环调整后面数组的每一位元素，同时记录数据元素的长度的标示符也要跟着改变。 显示操作是通过循环实现表中第一个元素到最后一个元素的输出，查找操作是直接取数组中的查找位输出。
（3）
实验结果与分析
② 单链表
（1）抽象数据类型定义
typedef struct node{
DataType data; //链表的数据类型
struct node *link; //链表的结点指针
}linknode,*linklist; //定义了结构体linklode和结构体指针linklist
在本次实验中，首先程序自己建立一个空的头结点，通过菜单的功能选择“添加链表数据”可自由添加链表的节点数及元素值。在菜单选择中，有“添加链数据”，“插入链表数据”，“删除链表数据”，“查找链表数据”和“显示链表数据”功能，选择不能的功能选择就能实现不同的操作。其中“添加链表数据”可反复批量输入链表数据。
（2）存储结构定义及算法思想
在单链表中，typedef int DataType;DataType data;定义链表存储数据位整型。存储结构如下：
while(p->link!=NULL){
p=p->link; k++; //首先找到单链表的最后结点（如果是只有头结点
} 的单链表则直接跳过），以便后面接着输入数据
for(int i=0;i<a;i++)
{
cout<<"请输入数据"<<endl;
q=(linklist)malloc(sizeof(linknode)); //开辟新的结点空间并转化为linklist指针型
cin>>q->data;
q->link=p->link; //将前面一个结点的指向(及NULL)赋给新开辟的结点的指向
p->link=q; //将插入点前面一个结点指向新开辟的的结点
p=q; //将指明的最后一个一个结点向后移1位到最后一位，以便后面接着输入
}
删除结点子函数：
void delate(linklist &l){ //删除单链表数据
linklist p; int m,n,i=0;
cout<<"请输入想要删除的结点位置"<<endl;
cin>>m;
p=l; //将头结点赋给转移指针p
while(p&&i<m-1) { //查找删除结点的位置
p=p->link; //当在单链表中间已查到删除结点或p=NULL时跳出循环
i++;
}
if(p==NULL) { //当p=NULL跳出循环时，表明链表中没有该结点
cout<<"该结点不存在，删除错误"<<endl; return;
}
n=p->link->data; //找到删除接结点将数据取出并显示出来（找结点时是找的前一个结点）
cout<<"被删除的结点元素为: "<<n<<endl;
p->link=p->link->link; //将删除结点的前后结点链接起来
}
链表的删除，插入操作是类似的，要考虑到加入或减少一个结点后，前后结点的链接关系，以及删除或插入的是最后一个结点时，新空间的开辟与结点收尾等问题。其中删除功能的一部分就是查找功能，显示功能也是从链表的头结点遍历至最后一个，依次输出。
（4）实验结果与分析
③ 心得体会
本次数据结构实习我收获颇丰，以前学过c语言与c++也有经常上机，但以往都是偏向于程序整体的算法设计，没有像这次的实习这样是着重在线性表，链表结构的算法设计上面。这次上机实习，让我更加熟练了结构体及结构体指针的用法，线性表的设计等等，同时在这次实习中，引用，指针，地址这三个的用法曾一度让我混淆，在查阅书籍后才得以解决，也希望老师在课堂上有时间时给我们详细讲解一下，指针，地址，引用三者的使用。
附录：
顺序表源代码:
#include<iostream>
using namespace std;
#define maxsize 50
typedef int TypeData;
typedef struct {
TypeData data[maxsize];
int n;
}SeqList;
void makeSeq( SeqList &L) // 输入线性表数据
{
int m,n,k;
cout<<"请输入线性表长度"<<endl;
cin>>m;
for(n=0;n<m;n++)
{
cout<<"请输入线性表数据"<<endl;
cin>>L.data[n];
}
L.n=m;
cout<<"您输入的线性表为："<<endl;
for(k=0;k<m;k++)
{
cout<<L.data[k]<<" ";
}
cout<<endl;
}
void showSeq(SeqList L) //输出线性表数据
{
int a=0;
while(a<L.n)
{
cout<<L.data[a]<<" ";
a++;
}
cout<<endl;
}
void insert(SeqList &L) //插入数据
{
int a,b,c,k;
cout<<"请输入插入的数及其插入的位置"<<endl;
cin>>a>>b;
if(b<=0||b>(L.n+1)) {cout<<"不能在该位置插入"<<endl; return;}
k=L.data[b-1];L.data[b-1]=a; c=L.n; L.n=L.n+1;
while(c>b)
{
L.data[c]=L.data[c-1];
c--;
}
L.data[b]=k;
}
void delate(SeqList &L) //删除数据
{
int wei;
cout<<"请输入想要删除数据的位置"<<endl;
cin>>wei;
if(wei<1||wei>L.n) { cout<<"不能在该位置删除"<<endl;return; }
while(wei<L.n)
{
L.data[wei-1]=L.data[wei];
wei++;
}
L.n=L.n-1;
}
void find(SeqList L) //查找数据
{
int a;
cout<<"请输入您想查找数的位置"<<endl;
cin>>a;
if(a<=0||a>(L.n)) {cout<<"不能在该位置插入"<<endl; return;}
cout<<"该位置的数据为："<<" "<<L.data[a-1]<<endl;
}
void main()
{
SeqList L;
int xuanze;
makeSeq(L);
while(1)
{
cout<<"请选择功能"<<endl;
cout<<"插入 1"<<endl;
cout<<"删除 2"<<endl;
cout<<"查找 3"<<endl;
cout<<"显示 4"<<endl;
cout<<endl<<"请输入"<<endl;
cin>>xuanze;
switch(xuanze)
{
case 1: insert(L);break;
case 2: delate(L);break;
case 3: find(L);break;
case 4: showSeq(L);break;
default :break;
}
}
}
单链表源代码：
#include<iostream>
using namespace std;
typedef int DataType;
typedef struct node{
DataType data;
struct node *link;
}linknode,*linklist;
linklist chushihua()
{
linklist L;
L=(linklist )malloc(sizeof(linknode));
L->link=NULL;
cout<<"开辟空间成功，头结点建立"<<endl;
return L;
}
void shuru(linklist &l)
{
int a,k=0;
cout<<"请输入要存入的结点个数"<<endl;
cin>>a;
linklist p,q;
p=l;
while(p->link!=NULL)
{
p=p->link;
k++;
}
for(int i=0;i<a;i++)
{
cout<<"请输入数据"<<endl;
q=(linklist)malloc(sizeof(linknode));
cin>>q->data;
q->link=p->link;
p->link=q;
p=q;
}
}
void show(linklist l)
{
cout<<"链表数据为："<<endl;
linklist p;
p=l->link;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->link;
}
cout<<endl;
}
void find(linklist l)
{
int m,i=0;
cout<<"请输入查找的结点"<<endl;
cin>>m;
linklist p;
p=l->link;
while(p&&i<m-1)
{
p=p->link;
i++;
}
if(!p) { cout<<"链表没有这么长,查找错误"<<endl;return;}
cout<<"查找结点的数据位： "<<p->data<<endl;
}
void insert(linklist l)
{
linklist p,q; int m,n,i=0;
cout<<"请输入您要插入的结点位置及插入的数据"<<endl;
cin>>m>>n;
p=l;
while(p&&i<m-1)
{
p=p->link;
i++;
}
if(p==NULL)
{
cout<<"不能在该位置插入，插入错误"<<endl;return;
}
q=(linklist)malloc(sizeof(linknode));
q->data=n;
q->link=p->link;p->link=q;
}
void delate(linklist &l)
{
linklist p; int m,n,i=0;
cout<<"请输入想要删除的结点位置"<<endl;
cin>>m;
p=l;
while(p&&i<m-1)
{
p=p->link;
i++;
}
if(p==NULL)
{
cout<<"该结点不存在，删除错误"<<endl;return;
}
n=p->link->data;
cout<<"被删除的结点元素为: "<<n<<endl;
p->link=p->link->link;
}
void main()
{
linklist L; int select;
L=chushihua();
while(1)
{
cout<<"请选择功能"<<endl;
cout<<"添加链表数据 1"<<endl;
cout<<"插入链表数据 2"<<endl;
cout<<"删除链表数据 3"<<endl;
cout<<"查找链表数据 4"<<endl;
cout<<"显示链表数据 5"<<endl;
cout<<endl<<"请输入"<<endl;
cin>>select;
switch(select)
{
case 1: shuru(L);break;
case 2: insert(L);break;
case 3: delate(L);break;
case 4: find(L);break;
case 5: show(L);break;
default :break;
}
}
}