线性表上机实习
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;ncout<<\"请输入线性表数据\"<cin>>[n]; //顺序将数据存入顺序表 } //其他存储与此类似，都是直接赋值与数组的某一位插入版块子函数：
void insert(SeqList &L) //插入数据 {
int a,b,c,k;
cout<<\"请输入插入的数及其插入的位置\"<cin>>a>>b;if(b<=0||b>+1)) {cout<<\"不能在该位置插入\"<k=[b-1];[b-1]=a; c=; =+1; while(c>b){[c]=[c-1];c--; //通过循环，实现插入位置后的数据挨个往后移动一位 } [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;icout<<\"请输入数据\"<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<<\"请输入想要删除的结点位置\"<>m;p=l; //将头结点赋给转移指针p while(p&&ip=p->link; //当在单链表中间已查到删除结点或p=NULL时跳出循环 i++; }if(p==NULL) { //当p=NULL跳出循环时，表明链表中没有该结点 cout<<\"该结点不存在，删除错误\"<n=p->link->data; //找到删除接结点将数据取出并显示出来（找结点时是找的前一个结点）cout<<\"被删除的结点元素为: \"<p->link=p->link->link; //将删除结点的前后结点链接起来 }链表的删除，插入操作是类似的，要考虑到加入或减少一个结点后，前后结点的链接关系，以及删除或插入的是最后一个结点时，新空间的开辟与结点收尾等问题。其中删除功能的一部分就是查找功能，显示功能也是从链表的头结点遍历至最后一个，依次输出。
（4）实验结果与分析
③ 心得体会
本次数据结构实习我收获颇丰，以前学过c语言与c++也有经常上机，但以往都是偏向于程序整体的算法设计，没有像这次的实习这样是着重在线性表，链表结构的算法设计上面。这次上机实习，让我更加熟练了结构体及结构体指针的用法，线性表的设计等等，同时在这次实习中，引用，指针，地址这三个的用法曾一度让我混淆，在查阅书籍后才得以解决，也希望老师在课堂上有时间时给我们详细讲解一下，指针，地址，引用三者的使用。
附录：
顺序表源代码:
#include 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<<\"请输入线性表长度\"<>m;for(n=0;ncout<<\"请输入线性表数据\"<>[n]; } =m;cout<<\"您输入的线性表为：\"<cout<<[k]<<\" \"; }cout<void showSeq(SeqList L) //输出线性表数据 {int a=0; while(a< {
cout<<[a]<<\" \"; a++; }
cout<void insert(SeqList &L) //插入数据 {int a,b,c,k;
cout<<\"请输入插入的数及其插入的位置\"<>a>>b;if(b<=0||b>+1)) {cout<<\"不能在该位置插入\"<b) {[c]=[c-1];
c--; }
[b]=k; }
void delate(SeqList &L) //删除数据 {
int wei;
cout<<\"请输入想要删除数据的位置\"<>wei;if(wei<1||wei> { cout<<\"不能在该位置删除\"<[wei-1]=[wei]; wei++; } =; }void find(SeqList L) //查找数据 { int a;
cout<<\"请输入您想查找数的位置\"<>a;if(a<=0||a>) {cout<<\"不能在该位置插入\"<void main() {SeqList L; int xuanze; makeSeq(L); while(1) {
cout<<\"请选择功能\"<cout<>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 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<<\"开辟空间成功，头结点建立\"<void shuru(linklist &l) {int a,k=0;
cout<<\"请输入要存入的结点个数\"<>a;linklist p,q; p=l;
while(p->link!=NULL) {
p=p->link; k++; }
for(int i=0;icin>>q->data; q->link=p->link; p->link=q; p=q; } }void show(linklist l) { cout<<\"链表数据为：\"<link; while(p!=NULL) {cout<data<<\" \"; p=p->link; }cout<void find(linklist l) {int m,i=0;
cout<<\"请输入查找的结点\"<>m;linklist p; p=l->link;
while(p&&ip=p->link; i++; }if(!p) { cout<<\"链表没有这么长,查找错误\"<data<void insert(linklist l) {linklist p,q; int m,n,i=0;
cout<<\"请输入您要插入的结点位置及插入的数据\"<>m>>n; p=l;while(p&&ip=p->link; i++;}
if(p==NULL) {
cout<<\"不能在该位置插入，插入错误\"<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<<\"请输入想要删除的结点位置\"<>m; p=l;while(p&&ip=p->link; i++; } if(p==NULL) {cout<<\"该结点不存在，删除错误\"<n=p->link->data;cout<<\"被删除的结点元素为: \"<link=p->link->link; }void main() {
linklist L; int select; L=chushihua();
while(1) {
cout<<\"请选择功能\"<cout<>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; } } }
