线性表的链式表示和实现解析

数学与计算科学学院实验报告实验项目名称线性表的链式表示与实现所属课程名称数据结构实验类型验证型实验日期班级学号姓名成绩2.调试第一次显示错误如下：原因：由于没有头文件及宏定义以及自定义，因此导致许多错误，可能还有许多错误没有显示3. 将以下语句编入VC++6.0中#include "stdio.h"#include "stdlib.h"#define OK 1#define ERROR 0typedef int ElemType;typedef int Status;4.调试第二次显示错误如下：原因：由于算法中许多变量没有定义，因此有许多错误5. 将以下语句加入算法中：int i;LinkList p;（加入创建链表的算法中）LinkList p;int j;（加入查找元素的算法中）LinkList p,s;int j;(加入插入元素的算法中)LinkList p,q;int j;（加入删除元素的算法中）6.调试第三次显示没有错误：7. 现在开始编写主函数：（1）先编写调用创建链表的函数的主函数：如下：void main(){LinkList L;int i,n;scanf("%d",&n);CreateList_L(L,n);for(i=n;i>0;--i)printf("%d ",L->data);printf("\n");}调试显示为：运行显示为：产生了随机数说明for循环语句那里编写错误因此修改为：LinkList p;for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);调试显示为：运行显示为：这次正确了那么继续编写下面的其他主函数，形成的总的主函数为：void main(){LinkList L,p;int i,n;scanf("%d",&n);CreateList_L(L,n);for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);printf("\n");ElemType e;scanf("%d", &i);GetElem_L(L, i, e);printf("%d\n",e);scanf("%d",&i);scanf("%d",&e);ListInsert_L(L, i, e);for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);printf("\n");scanf("%d", &i);ListDelete_L(L,i,e);printf("%d\n",e);for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);printf("\n");}8.调试第四次显示为：9.运行显示结果为：10. 但运行后的界面显得很单调；要是忘记下一个算法是什么就容易输入出错，也不适合大众使用；因此为了将程序优化，所以在主函数中增加以下输入输出语句和条件语句；为了让程序更加严谨，因此还加入一些循环语句以及条件语句，那么主函数语句变为：main(){LinkList L,p;int i,n,x,y,z;ElemType e;printf("请输入您想构建的链式表的元素个数:\n");scanf("%d",&n);printf("请输入您想构建的链式表:\n");CreateList_L(L,n);printf("您构建的链式表是:\n");for(p=L->next;p!=NULL;p=p->next)printf("%d ",p->data);printf("\n");printf("请输入您想查找的元素是第几个元素:\n");scanf("%d", &i);for(x=2;(i<=0||i>n)&&x>=0;--x){switch(x){case 2:printf("输入的数字错误,还有两次重新输入符合要求的数字的机会:\n");break;case 1:printf("输入的数字错误,还有一次重新输入符合要求的数字的机会:\n");break;case 0:printf("输入的数字错误,您的输入机会已经用完\n");return ERROR;printf("%d ",p->data);printf("\n");return 0;}11.调试第五次显示为：、12.运行后结果显示为：这样那么程序就完整了，清晰明了，用户运行的时候也易知道自己要输入什么了【实验结论】（结果）。

#include<iostream>using namespace std;#define ERROR 0#define OK 1class LNode{private:int num;LNode *next;public:friend LNode* LNodeCreate(); //创建链式线性表friend int GetElem(LNode *H,int i); //L为带头结点的单链表的头指针，当第i个元素存在，输出其值friend int LNodeInsert(LNode *H,int i,int e); //L为带头结点的单链表的头指针，在dii个位置插入元素efriend int LNodedelete(LNode *H,int i); //删除线性表中第i个元素};/*//从头到尾创建线性表LNode* LNodeCreate(){LNode *q,*H,*p;int size;cout<<"请输入线性表元素的个数：";cin>>size;cout<<"请输入线性表这"<<size<<"个元素：";q=H=new LNode;for(int i=0;i<size;i++){p=new LNode;cin>>p->num;H->next=p;H=p;}H->next=NULL;H=q->next;cout<<"刚创建的线性表为：";for(p=H;p!=NULL;p=p->next)cout<<p->num<<" ";cout<<endl<<endl;return H;}*///从尾到头创建线性表LNode* LNodeCreate(){LNode *L=new LNode,*p;L->next=NULL;int size,e;cout<<"请输入线性表元素的个数：";cin>>size;cout<<"请输入线性表这"<<size<<"个元素：";for(int i=size;i>0;--i){p=new LNode;cin>>e;p->num=e;p->next=L->next;L->next=p;}L=p;cout<<"刚创建的线性表为：";for(p=L;p!=NULL;p=p->next)cout<<p->num<<" ";cout<<endl<<endl;return L;}int GetElem(LNode *H,int i){LNode *p; int j=1; //j为计数器p=H;while(p&&j<i){p=p->next;++j;}if(!p&&j>i) return ERROR;cout<<"取出的值为："<<p->num<<endl<<endl;return OK;}int LNodeInsert(LNode *H,int i,int e){LNode *p,*s; int j=1;p=H;while(p&&j<i-1){p=p->next;++j;}s=new LNode;s->num=e;s->next=p->next;p->next=s;cout<<"新的线性表为：";for(p=H;p!=NULL;p=p->next)cout<<p->num<<" ";cout<<endl<<endl;return OK;}int LNodedelete(LNode *H,int i){ LNode *p=H,*q;int j=1;while(p&&j<i-1){p=p->next;++j;}if(!p&&j>i) return ERROR;q=p->next;p->next=q->next;delete(q);cout<<"新的线性表为：";for(p=H;p!=NULL;p=p->next)cout<<p->num<<" ";cout<<endl<<endl;return OK;}int main(){LNode *H;int m;H=LNodeCreate();cout<<"请输入你要取出的元素的位置："; cin>>m;GetElem(H,m);int i,e;cout<<"请输入你要插入的元素的位置："; cin>>i;cout<<"请输入你要插入的元素："; cin>>e;LNodeInsert(H,m,e);int j;cout<<"请输入你要删除的元素的位置："; cin>>j;LNodedelete(H,j);return 0;}。

线性表的链式表⽰和实现（插⼊删除建空合并）题解：后续的功能会不定期更新emmm框架：代码：#include <iostream>#include <cstdio>using namespace std;typedef struct LNode{int data;struct LNode *next;}LNode,*LinkList;int GetElem_L(LinkList L, int i, int &e){LNode *p = L->next;int j = 1;while (p&&j < i){p = p->next;++j;}if (!p || j>i)return0;e = p->data;return1;}int ListInsert_L(LinkList &L, int i, int e){LNode *p = L->next;int j = 1;while (p && j < i-1){p = p->next;++j;}if (!p || j>i-1)return0;LNode *node =(LNode*)malloc(sizeof(LNode));node->data = e;LNode* q = p->next;p->next = node;node->next = q;return1;}int ListDelete_L(LinkList &L, int i, int &e){LNode *p = L->next;int j = 1;while (p->next&&j < i - 1)//注意此处为p->next，因为若是p，则出来的p可能为空 {p = p->next;++j;}if (!p->next || j>i - 1)return0;LNode*q= p->next;e = q->data;p->next = p->next->next;free(q);return1;}void CreateList_L(LinkList &L, int n){printf("Enter the value of the node:");// L = (LinkList)malloc(n*sizeof(LNode)); 如果像这样创建的话，//那就是⽣成连续存储空间的线性表，应该单独对每⼀个节点分配内存空间L = (LinkList)malloc(sizeof(LNode));L->next = nullptr;//先⽣成⼀个表头的单链表for (int i = n;i > 0;--i){LNode *p = (LinkList)malloc(sizeof(LNode));cin>>p->data;p->next = L->next;//插⼊⽅式为向表头的后⼀个插⼊，不然插在表尾太⿇烦 L->next = p;}}void MergeList_L(LinkList &L,LinkList &Lb,LinkList &Lc)//合并{LNode *p=L->next;LNode *pb=Lb->next;LNode *pc=Lc=L;while(p&&pb){if(p->data<=pb->data){pc->next=p;pc=p;p=p->next;}else{pc->next=pb;pc=pb;pb=pb->next;}}pc->next=p?p:pb;free(Lb);}/*int Length_L(LinkList &L)//计算长度{int j=0;LNode *p=L->next;while(p){p=p->next;j++;}return j;}*/ //没⽤到emmmmvoid ShowList(LinkList &L){LNode *p = L->next;while (p){cout<<p->data<<"";p = p->next;}}int main(){LinkList L;cout<<"Enter the length of the linked list:";int num;cin>>num;CreateList_L(L, num);//建表ShowList(L);//展⽰int e1,temp;cout<<"\nTo increase the number of positions:";int place;cin>>place;cout<<"\nEnter the number to insert:";cin>>e1;ListInsert_L(L, place, e1);ShowList(L);cout<<"\nThe number of digits to be deleted:";int place1;cin>>place1;ListDelete_L(L, place1, temp);ShowList(L);printf("\nThe deleted node value is :%d\n", temp);LinkList Lb,Lc;cout<<"\nEnter the length of the linked list:";int num1;cin>>num1;CreateList_L(Lb, num1);//建表cout<<"\nThe two linked lists are:";MergeList_L(L,Lb,Lc);ShowList(L);cout<<endl;return0;}今天也是元⽓满满的⼀天！good luck！。

浙江大学城市学院实验报告课程名称数据结构基础实验项目名称实验五线性表的链式表示和实现学生姓名专业班级学号实验成绩指导老师（签名）日期一.实验目的和要求1、了解线性表的链式存储结构，学会定义线性表的链式存储结构。

2、掌握单链表、循环单链表的一些基本操作实现函数。

二.实验内容1、设线性表采用带表头附加结点的单链表存储结构，请编写线性表抽象数据类型各基本操作的实现函数，并存放在头文件LinkList.h中（注：教材上为不带表头附加结点）。

同时建立一个验证操作实现的主函数文件test5.cpp，编译并调试程序，直到正确运行。

提示：⑴单向链表的存储结构可定义如下：struct LNode { // 定义单链表节点类型ElemType data; // 存放结点中的数据信息LNode *next; // 指示下一个结点地址的指针}⑵线性表基本操作可包括如下一些：①void InitList (LNode *&H) //初始化单链表②void ClearList(LNode *&H) //清除单链表③int LengthList (LNode *H) //求单链表长度④bool EmptyList (LNode *H) //判断单链表是否为空表⑤ElemType GetList (LNode *H, int pos)//取单链表第pos 位置上的元素⑥void TraverseList(LNode *H) //遍历单链表⑦bool InsertList ( LNode *&H, ElemType item, int pos)//向单链表插入一个元素⑧bool DeleteList ( LNode *&H, ElemType &item, int pos)//从单链表中删除一个元素⑶带表头附加结点的单链表初始化操作的实现可参考如下：void InitList(LNode *&H){ //构造一个空的线性链表H，即为链表设置一个头结点，//头结点的data数据域不赋任何值，头结点的指针域next则为空H=(LNode *)malloc(sizeof(LNode)); // 产生头结点Hif (!H) exit(0); // 存储分配失败，退出系统H->next=NULL; // 指针域为空}2、选做部分：编写一个函数void MergeList(LNode *&La, LNode *&Lb, LNode *&Lc)，实现将两个有序单链表La和Lb合并成一个新的有序单链表Lc，同时销毁原有单链表La和Lb。

数据结构（⼆）：线性表的链式存储结构1、为什么要使⽤链式存储结构？因为我们前⾯讲的线性表的顺序存储结构，他是有缺点的。

最⼤的缺点就是插⼊和删除时需要移动⼤量元素，这显然就需要耗费时间。

要解决这个问题，我们就需要分析⼀下为什么当插⼊和删除时，就要移动⼤量元素，因为相邻两元素的存储位置也具有相邻关系，它们在内存中的位置也是挨着的，中间没有空隙，当然就⽆法快速介⼊，⽽删除之后。

当中就会留出空隙，⾃然就需要弥补。

问题就出在这⾥。

为了解决这个问题，⾃然⽽然的就出现了链式存储结构。

2、线性表链式存储结构的特点：线性表的链式存储结构不考虑元素的存储位置，⽽是⽤⼀组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的，这就意味着，这些数据元素可以存在内存未被占⽤的任意位置。

顺序存储结构：只需要存储数据元素信息。

链式存储结构：除了要存储数据元素信息之外，还要存储⼀个指⽰其直接后继元素的存储地址。

3、关键词：数据域：存储数据元素信息的域。

指针域：存储直接后继位置的域。

指针或链：指针域中存储的信息。

结点（Node）：指针域+数据域组成数据元素的存储映像。

头指针：链表中第⼀个结点的存储位置。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

4、单链表：定义：n个结点链成⼀个链表，即为线性表的链式存储结构，因此此链表的每个结点中只包含⼀个指针域，所以叫做单链表。

PS：线性链表的最后⼀个结点指针为“空”,通常⽤NILL或“^”符号表⽰。

头节点：在单链表的第⼀个结点前附设⼀个结点，成为头结点。

头结点的数据域不可以存储任何信息，可以存储线性表的长度等附加信息，头结点的指针域存储指向第⼀个结点的指针。

5、头结点与头指针的异同（1）头结点头结点是为了操作的统⼀和⽅便⽽设⽴的，放在第⼀个元素的结点之前，其数据域⼀般⽆意义（也可存放链表的长度）有了头结点，对第⼀元素结点前插⼊和删除第⼀结点，其操作就统⼀了头结点不⼀定是链表的必要素（2）头指针头指针式指向第⼀个结点的指针，若链表有头结点，则是指向头结点的指针。