[线性表 链表实验报告]链表线的性表.docx

[线性表 链表实验报告]链表线性表 实验一：线性表运算的实现 班级 姓名 学号 一、实验预备知识 1 复习C++中编写函数的相关内容 2 复习如何用主函数将多个函数连在一起构成一个C++完整程序 二、实验目的 1 掌握线性表的顺序和链式存储结构 2 熟练运用线性表在顺序存储方式下的初始化、创建、输出、插入和删除运算 3 熟练运用线性表在链式存储方式下的创建、输出、插入和删除运算 三、实验要求 1 编写初始化并创建线性表和输出线性表的算法 2 编写对线性表插入和删除运算算法，要判断位置的合法性和溢出问题 3 编写一个主函数，将上面函数连在一起，构成一个完整的程序 4将实验源程序调试并运行，写出输入、输出结果，并对结果进行分析 四、实验步骤 ◇顺序表实验内容： 1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入 2．初始化并建立顺序表 3．编写顺序表输出算法内存中开辟的单元数为8） 4．依次插入3，21，15三个数，分别插入在第4，6和2位置，每插入一次都要输出一次顺序表 5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次顺序表 ◇单链表实验内容： 1．给定的线性表为L=（12，25，7，42，19，38），元素由键盘输入。

2．建立一个带表头结点的单链表（前插入法和尾插入法都可以） 3．编写单链表输出算法 4．依次插入3，21，15三个数，分别插入在第4，6和12位置，每插入一次都要输出一次单链表 5．删除第5，第3和第12个位置上的元素，每删除一个元素都要输出一次单链表 五、实验程序 ◇顺序表实验 //LinkList.h #define MAXSIZE 8 typedef int DataType; typedef struct{ DataType data[MAXSIZE]; int last; }Seqlist; void creat_seqlist(Seqlist &s); void display_seqlist(Seqlist &s); int insert_seqlist(Seqlist &s, int i, DataType x); int delet_seqlist(Seqlist &s, int i); //LinkList.cpp #include #include"Seqlist.h" void creat_seqlist(Seqlist &s) { int x, i = 0; cout cin>>x; while(x != -1){ s.data[i] = x; cin>>x; i ++; } s.last = i-1; } void display_seqlist(Seqlist &s) { int i; cout for(i = 0; i cout cout } int insert_seqlist(Seqlist &s, int i, DataType x) { int j; if(s.last == MAXSIZE-1){ } cout s.last + 2){ cout= i-1;j --) s.data[j+1] = s.data[j]; s.data[i-1] =x ; s.last ++; return 1; int delet_seqlist(Seqlist &s, int i) { int j; if(i s.last+1){ cout return -1; } for(j = i; j s.data[j-1] = s.data[j]; s.last --; return 1; } //main.cpp #include #include"Seqlist.h" int main() { int x,d,s; Seqlist s_list; creat_seqlist(s_list); cout>d; cout>x; s=insert_seqlist(s_list ,d,x); if(s==1){ cout>d; s=delet_seqlist(s_list,d); } if(s==1){ cout 运行结果: 请输入数据（以输入-1结束） 12 25 7 42 19 38 -1 顺序表为： 12 25 7 42 19 38 插入操作 请输入插入的位置:4 请输入要插入的数据：3 插入后的顺序表为： 12 25 7 3 42 19 38 请输入插入的位置:6 请输入要插入的数据：21 插入后的顺序表为： 12 25 7 3 42 21 19 38 请输入插入的位置:2 请输入要插入的数据：15 表满！ 删除操作 请输入删除元素的位置：5 删除后的顺序表为： 12 25 7 3 21 19 38 请输入删除元素的位置：3 删除后的顺序表为： 12 25 3 21 19 38 请输入删除元素的位置：12 不存在该元素！ Press any key to continue ◇单链表实验 //LinkList.h typedef int DataType; typedef struct Node{ DataType data; struct Node *next; }LNode,*LinkList; void Creat_LinkList(LinkList &L); //创建链表 void Show_LinkList(LinkList &L); //显示数据 LNode * Get_LinkList(LinkList &L, int i); //获得第i个结点的地址 int Insert_linklist(LinkList &L,int i,DataType x); //插入结点 int Delete_LinkList(LinkList &L,int i); //删除结点 //LinkList.cpp #include #include"LinkList.h" void Creat_LinkList(LinkList &L) { LNode *s; L = NULL; s = new LNode; s->next = L; L = s; int x; } //头插法创建带头结点的链表 cout>x; while(x != -1){ s = new LNode; s->next = L; L->data = x; L = s; cin>>x; } void Show_LinkList(LinkList &L) { LNode *p; p = L->next; while(p!=NULL){ coutdata p = p->next; //显示数据 } cout } LNode * Get_LinkList(LinkList &L, int i) { int j = 1; LNode *q; q = L->next; while(q != NULL && j q = q->next; j++; } return q; } //获得第i个结点的地址 int Insert_LinkList(LinkList &L, int i, DataType x)//插入结点 { LNode *p, *s; p = Get_LinkList(L,i-1); if(p == NULL){ } coutdata = x; s->next = p->next; p->next = s; return 1; } int Delete_LinkList(LinkList &L,int i) { LNode *p, *s; p = Get_LinkList(L,i-1); if(p == NULL){ //删除结点 coutnext == NULL){ cout return 0; } else{ s = p->next; p->next = s->next; delete s; return 1; } } //main.cpp #include #include"LinkList.h" int main() { int x,d,s; LinkList H; Creat_LinkList(H); Show_LinkList(H); } cout>d; cout>x; s = Insert_LinkList(H,d,x); if(s == 1){ cout>d; s = Delete_LinkList(H,d); if(s == 1){ cout 运行结果： 请输入数据（以输入-1结束） 12 25 7 42 19 38 -1 单链表为： 38 19 42 7 25 12 插入操作 请输入插入的位置:4 请输入要插入的数据：3 插入后的单链表为： 38 19 42 3 7 25 12 请输入插入的位置:6 请输入要插入的数据：21 插入后的单链表为： 38 19 42 3 7 21 25 12 请输入插入的位置:12 请输入要插入的数据：15 插入位置错误! 删除操作 请输入删除元素的位置：5 删除后的单链表为： 38 19 42 3 21 25 12 请输入删除元素的位置：3 删除后的单链表为： 38 19 3 21 25 12 请输入删除元素的位置：12 插入位置的前驱结点不存在!。