实验二 线性表的链式存储结构

实验二 链式存储线性表的基本操作一、 实验目的1. 掌握用Turbo C2.0上机调试线性表的基本方法。

2. 掌握线性表的基本操作，插入、删除、查找，以及线性表合并等运算在链接存储结构上的运算。

二、 实验内容1.typedef int ElemType;typedef struct LNode { //创建结构体数据类型LNodeElemType data; //存放数值的数据域struct LNode *next; //存放后继结点地址的指针域}LNode;2. 链表的创建：创建n 个结点，利用scanf( )函数为每个结点的数据域赋值，一次将每个结点插入链表，形成一个包含n 个元素的链表。

#define NULL 0#define OVERFLOW 0#define OK 1#define ERROR -1typedef int ElemType;typedef struct LNode { //创建LNode 数据类型ElemType data;struct LNode *next;}LNode;typedef LNode *LinkList; //定义LinkList 指针型数据类型int CreateList_L(LinkList L, int n) { //创建拥有n 个元素的线性链表//int i;struct LNode *p;L->next = NULL; //线性链表初始化，见右图for (i = n; i > 0; --i) { //循环n 次在头结点和第一个结点间插入新结点，形成长度为n 的线性链表p =(LNode*)malloc(sizeof(LNode));scanf("%d",&p->data);p->next = L ->next;L->next =p;}return 1;}data next data nextl1)2)3)int VistList_L(LinkList L) { //遍历链表L中每个结点的函数struct LNode *p;p = L->next;while (p) {printf("%d ",p->data); //访问输出p结点的数据域p = p->next; } //p指针前进一位，指向后继结点printf("\n");return OK;}}lmain(){int m;LNode l;ElemType e;printf("please input the length of the linklist that you want to build");scanf("%d",&m);printf("please give the number that you want to insert");CreateList_L(&l,m); //调用创建链表函数VistList_L(&l); //调用遍历链表结点函数}3. 链表的插入算法：向链表中某个位置上插入一个结点#define NULL 0#define OVERFLOW 0#define OK 1#define ERROR -1typedef int ElemType;typedef struct LNode { //创建LNode 数据类型ElemType data;struct LNode *next;}LNode;typedef LNode *LinkList;int CreateList_L(LinkList L, int n) { //创建包含n 个元素的链表int i;struct LNode *p;L->next = NULL;for (i = n; i > 0; --i) {p =(LNode*)malloc(sizeof(LNode));scanf("%d",&p->data);p->next = L ->next;L->next =p;}return 1;}int ListInsert_L(LinkList L, int i, ElemType e) { //向链表中第i位插入数据e struct LNode *s,*p;int j;p = ; j = 0; //p指针指向线性链表的头结点while (p && j < ) //循环查找第i-1位作为数据e的插入位置{ p = ; ++j; } //p指针向前移动if (!p || j > i-1)return ERROR;s =(LNode*)malloc(sizeof(LNode)); //见下图1）if ( s == NULL) return ERROR;s-> = e; //将插入数据e的值赋值给s结点的数据域1）s->next = ; p->next = ; //旧链断开，新链产生2）3）return OK;}1）2）3）int VistList_L(LinkList L) { //遍历链表所有结点的函数struct LNode *p;p = L->next;while (p) {printf("%d",p->data);p = p->next; }return OK;}main(){int m;LNode l;ElemType e;int i;printf("please input the length of the linklist that you want to build");scanf("%d",&m);printf("please give the number that the initial list have");CreateList_L(&l,m);VistList_L(&l);printf("please input the positon and data of the insert number i&e");scanf("%d,%d",&i,&e);ListInsert_L(&l,i,e);VistList_L(&l);}附：一元多项式的相加#include<stdio.h>#include<stdlib.h>#define LEN sizeof(node)typedef struct polynode /*用单链表存储多项式的结点结构*/{int coef; /*多项式的系数*/int exp; /*指数*/struct polynode *next; /*next是struct polynode类型中的一个成员，它又指向struct polynode类型的数据，以此建立链表*/}node;/*若定为"node,*list;"，意即node*与list同为结构指针类型*/node * create(void) /*指针函数，返回指针类型；用尾插法建立一元多项式的链表的函数*/ {node *h,*r,*s;int c,e;h=(node *)malloc(LEN); /*建立多项式的头结点，为头结点分配存储空间*/r=h; /*r指针始终动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ printf("coef:");scanf("%d",&c); /*输入系数*/printf("exp: ");scanf("%d",&e); /*输入指针*/while(c!=0) /*输入系数为0时，表示多项式的输入结束*/{s=(node *)malloc(LEN); /*申请新结点*/s->coef=c; /*申请新结点后赋值*/s->exp=e; /*申请新结点后赋值*/r->next=s; /*做尾插，插入新结点*/r=s; /*r始终指向单链表的表尾*/printf("coef:");scanf("%d",&c);printf("exp: ");scanf("%d",&e);}r->next=NULL; /*将表的最后一个结点的next置NULL，以示表结束*/return(h);}void polyadd(node *polya, node *polyb)/*一元多项式相加函数，用于将两个多项式相加，然后将和多项式存放在多项式polya中，并将多项式ployb删除*/{node *p,*q,*pre,*temp;int sum;p=polya->next;/*令p和q分别指向polya和polyb多项式链表中的第一个结点*/q=polyb->next;pre=polya; /*位置指针，指向和多项式polya*/while(p!=NULL&&q!=NULL) /*当两个多项式均未扫描结束时，执行以下操作*/{if(p->exp<q->exp) /*若p指向的多项式指数小于q指的指数*/{pre->next=p; /*将p结点加入到和多项式中*/pre=pre->next;p=p->next;}else if(p->exp==q->exp) /*若指数相等，则相应的系数相加*/{sum=p->coef+q->coef;if(sum!=0){p->coef=sum;pre->next=p;pre=pre->next;p=p->next;temp=q;q=q->next;free(temp);}else /*如果系数和为零，则删除结点p与q，并将指针指向下一个结点*/{temp=p->next;free(p);p=temp;temp=q->next;free(q);q=temp;}}else /*若p指数大于q指数*/{pre->next=q; /*p结点不动，将q结点加入到和多项式中*/pre=pre->next;q=q->next;}}if(p!=NULL) /*多项式A中还有剩余，则将剩余的结点加入到和多项式中*/ pre->next=p;else /*否则将B的结点加入到和多项式中*/pre->next=q;}void print(node * p) /*输出函数，打印出一元多项式*/{while(p->next!=NULL){p=p->next;printf(" %d*x^%d",p->coef,p->exp);}}main() /*主函数*/{node * polya,* polyb;printf("Welcome to use!\n");printf("\nPlease input the ploya include coef && exp:\n");polya=create(); /*调用建立链表函数，创建多项式A*/print(polya);printf("\nPlease input the ployb include coef && exp:\n");polyb=create(); /*同理，创建B*/print(polyb);printf("\nSum of the poly is:\n");polyadd(polya,polyb); /*调用一元多项式相加函数*/print(polya); /*调用输出函数，打印结果*/printf("\n");}。

贵州大学实验报告#include<iostream>using namespace std;typedef int Elemtype;struct LNode{Elemtype data;LNode *next;};void BuildLNode(LNode *&hl)/*建立带头结点单链表*/{hl=new LNode;hl->data=NULL;hl->next=NULL;}void ClearList(LNode *&hl)/*清空线性表*/ {LNode *p=hl;LNode *q;while(p!=NULL){q=p->next;delete p;p=q;}hl=NULL;}bool InsertList(LNode *&hl,Elemtype item,int pos)/*在线性表中插入一个元素*/{if(pos<-1){cout<<"位置无效"<<endl;return false;}if(pos==-1||pos==0)pos=1;LNode *p;int i=1;p=hl;while(p!=NULL&&i<pos){p=p->next;i++;}if(p==NULL){cout<<"位置无效"<<endl;return false;}LNode *q;q=new LNode;q->data=item;q->next=p->next;p->next=q;return true;}bool DeleteList(LNode *&hl,int pos)/*删除线性表中的一个元素*/{if(pos<-1){cout<<"位置无效"<<endl;return false;}if(pos==-1||pos==0)pos=1;LNode *p=hl,*q;int i=1;while(p->next!=NULL&&i<pos){p=p->next;i++;}if(p->next==NULL){cout<<"位置无效或该链表为空"<<endl;return false;}q=p->next;p->next=q->next;delete q;return true;}bool GetList(LNode *p,Elemtype &item,int pos)/*线性表中数据的定位*/{if(pos<-1){cout<<"位置无效"<<endl;return false;}if(pos==-1||pos==0)pos=1;int i=0;while(p!=NULL&&i<pos){p=p->next;i++;}if(p==NULL){cout<<"位置无效"<<endl;return false;}item=p->data;return true;}int FindList(LNode *p,Elemtype item)/*线性表中数据的查找*/{int i=0;while(p!=NULL){if(p->data==item)break;i++;p=p->next;}if(p==NULL){cout<<"找不到该元素"<<endl;return 0;}return i;}void DisplayList(LNode *hl)/*显示线性表中所有数据*/{if(hl==NULL){cout<<"该表为空"<<endl;}LNode *p=hl->next;while(p!=NULL){cout<<p->data<<" ";p=p->next;}} void main(){LNode *head;BuildLNode(head);int pos;Elemtype data;for(int i=0;i<10;i++)InsertList(head,2*i+1,i+1);DisplayList(head);cout<<endl;cout<<"一、插入操作"<<endl;cout<<"位置：";cin>>pos;cout<<"数据：";cin>>data;if(InsertList(head,data,pos))cout<<"插入成功"<<endl;elsecout<<"插入失败"<<endl;DisplayList(head);cout<<endl<<endl;cout<<"二、删除操作"<<endl;cout<<"位置：";cin>>pos;if(DeleteList(head,pos))cout<<"删除成功"<<endl;elsecout<<"删除失败"<<endl;DisplayList(head);cout<<endl<<endl;cout<<"三、定位操作："<<endl;cout<<"位置：";cin>>pos;if(GetList(head,data,pos))cout<<"该位置数据为"<<data<<endl;elsecout<<"定位失败"<<endl;cout<<"四、查找操作："<<endl;cout<<"数据：";cin>>data;if(FindList(head,data))cout<<"线性表中第一个等于该数据的位置为"<<FindList(head,data)<<endl;elsecout<<"查找失败"<<endl;ClearList(head);}。

南昌航空大学实验报告课程名称：数据结构实验名称：实验二：线性表的链式存储结构班级： 080611 学生姓名：赖凌学号： 08061101指导教师评定：签名:题目：设计并实现以下算法：给出用单链表存储多项式的结构，利用后接法生成多项式的单链表结构，实现两个多项式相加的运算，并就地逆置相加后的多项式链式。

一、需求分析⒈实现两张线性表的链式存储，合并及删除值相同元素的操作。

⒉在演示过程序中，用户敲击键盘，即可观看演示结果。

⒊程序执行的命令包括：（1）构造线性链表A （2）构造线性链表B （3）求两张表的并（4）删除C中值相同的元素二、概要设计⒈为实现上述算法，需要线性表的抽象数据类型：ADT LinkList List {数据对象：D={a i:|a i∈ElemSet,i=1…n,n≥0}数据关系：R1={<a i-1,a i>|a i-1,a i∈D,i=2,…n≥0}基本操作:Status InitList( LinkList &L)//操作结果：构造一个空的线性链表L。

Status MakeNode ( Link &p, ElemType e );// 分配由p指向的值为e 的结点，并返回ＯＫ；若分配失败，则返回ＥＲＲＯＲStatus Append (LinkList &L,Link s);//将指针s所指（彼此以指针相链接）的一串结点链接在线性链表L的最后一个结点之后，并改变链表L的尾指针指向新的尾结点Status ListEmpty(LinkList L);//若线性链表L为空表，则返回TRUE，否则返回ERROR。

Int ListLength(LinkList L);//返回线性链表中L最后一个结点的位置。

ElemType GetCurElem(Link p);//已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值Position GetHead (LinkList L);//返回线性链表L中头结点的位置Position GetLast( LInkList L);//返回线性链表L中最后一个结点的位置}ADT LinkList2. 本程序有三个模块：⑴主程序模块void main(){初始化；{接受命令；显示结果；｝｝⑵线性链表单元模块：实现线性链表抽象数据类型；⑶结点结构单元模块：定义线性链表中的结点结构。

实验报告课程名称：数据结构与算法分析实验名称：链表的实现与应用实验日期：班级：数媒1401 姓名：范业嘉学号一、实验目的掌握线性表的链式存储结构设计与基本操作的实现。

二、实验内容与要求⑴定义线性表的链式存储表示；⑵基于所设计的存储结构实现线性表的基本操作；⑶编写一个主程序对所实现的线性表进行测试；⑷线性表的应用：①设线性表L1和L2分别代表集合A和B，试设计算法求A和B的并集C，并用线性表L3代表集合C；②（选做）设线性表L1和L2中的数据元素为整数，且均已按值非递减有序排列，试设计算法对L1和L2进行合并，用线性表L3保存合并结果，要求L3中的数据元素也按值非递减有序排列。

⑸设计一个一元多项式计算器，要求能够：①输入并建立多项式；②输出多项式；③执行两个多项式相加；④执行两个多项式相减；⑤（选做）执行两个多项式相乘。

三、数据结构设计1.按所用指针的类型、个数、方法等的不同，又可分为：线性链表（单链表）静态链表循环链表双向链表双向循环链表2.用一组任意的存储单元存储线性表中数据元素，用指针来表示数据元素间的逻辑关系。

四、算法设计1.定义一个链表void creatlist(Linklist &L,int n){int i;Linklist p,s;L=(Linklist)malloc(sizeof(Lnode));p=L;L->next=NULL;for(i=0;i<n;i++){s=(Linklist)malloc(sizeof(Lnode));scanf("%d",&s->data);s->next=NULL;p->next=s; p=s;}}2.（1）两个链表的合并void Mergelist(Linklist &La,Linklist &Lb,Linklist &Lc) {Linklist pa,pb,pc;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else {pc->next=pb;pc=pb;pb=pb->next;} }pc->next=pa?pa:pb;free(Lb);}（2）两个链表的并集Linklist unionlist(Linklist &La,Linklist &Lb){Linklist p1,p2,head,q,s;int flag;head=q=(Linklist)malloc(sizeof(Lnode));p1=La->next;while(p1){flag=0;p2=Lb->next;while(p2){if(p1->data==p2->data){flag=1;break;}p2=p2->next;}if(flag==0){s=(Linklist)malloc(sizeof(Lnode));s->data=p1->data;q->next=s;q=s;}p1=p1->next;}q->next=Lb->next;return head;}3.（1）一元多项式的加法List addpoly(List pa,List pb) //一元多项式的加法{int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){if(pa->expn>pb->expn){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}else if(pa->expn<pb->expn){s=(List)malloc(sizeof(struct Linklist));s->expn=pb->expn;s->coef=pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;}else{n=pa->coef+pb->coef;if(n!=0){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=n;s->next=NULL;p->next=s;p=s;}pb=pb->next;pa=pa->next;}}while(pa!=NULL){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}while(pb!=NULL){s=(List)malloc(sizeof(struct Linklist));s->expn=pb->expn;s->coef=pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;}return pc;}（2）一元多项式的减法List subpoly(List pa,List pb) //一元多项式的减法{int n;List pc,s,p;pa=pa->next;pb=pb->next;pc=(List)malloc(sizeof(struct Linklist));pc->next=NULL;p=pc;while(pa!=NULL&&pb!=NULL){if(pa->expn>pb->expn){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}else if(pa->expn<pb->expn){s=(List)malloc(sizeof(struct Linklist));s->expn=pb->expn;s->coef=-pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;}else{n=pa->coef-pb->coef;if(n!=0){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=n;s->next=NULL;p->next=s;p=s;}pb=pb->next;pa=pa->next;}}while(pa!=NULL){s=(List)malloc(sizeof(struct Linklist));s->expn=pa->expn;s->coef=pa->coef;s->next=NULL;p->next=s;p=s;pa=pa->next;}while(pb!=NULL){s=(List)malloc(sizeof(struct Linklist));s->expn=pb->expn;s->coef=-pb->coef;s->next=NULL;p->next=s;p=s;pb=pb->next;}return pc;}（3）一元多项式的乘法void mulpolyn(polynomail pa,polynomail pb,polynomail &pc) {LNode *p,*q,*s,*hc;p=pa->next;q=pb->next;hc=pc;while(p!=NULL){while(q!=NULL){s=(polynomail)malloc(sizeof(LNode));hc->next=s;hc=hc->next;hc->coef=q->coef*p->coef;hc->expn=q->expn+p->expn;q=q->next;}p=p->next;q=pb->next;}hc->next=NULL;}五、测试结果2.3.六、心得体会（包括对于本次实验的小结，实验过程中碰到的问题等）1.首先书上给的链表输入是倒序的，写的时候想都没想就抄上去了，结果运行时发现问题，可是上网百度依然没有把问题解决，导致最后输出链表倒序的，并且链表的合并并集依旧是倒序的。

江西科技师范大学实验报告课程数据结构B系别大数据科学学院班级22信息管理与信息系统学号********姓名杨圣洲报告规格一、实验目的二、实验原理三、实验仪器四、实验方法及步骤五、实验记录及数据处理六、误差分析及问题讨论目录实验一线性表的顺序存储 (1)实验二线性表的链式存储 (2)实验三二叉树 (3)实验四图 (4)实验五检索 (5)实验六内排序 (6)每次实验课必须带上此本子，以便教师检查预习情况和记录实验原始数据。

实验时必须遵守实验规则。

用正确的理论指导实践必须人人亲自动手实验，但反对盲目乱动，更不能无故损坏仪器设备。

这是一份重要的不可多得的自我学习资料它将记录着你在大学生涯中的学习和学习成果。

请你保留下来，若干年后再翻阅仍将感到十分新鲜，记忆犹新。

它将推动你在人生奋斗的道路上永往直前！实验一线性表的顺序存储实验名称：实验一线性表的顺序存储实验目的：1、掌握线性表顺序存储结构的描述，学会对顺序存储线性表的基本操作。

2、掌握C 语言的结构化程序设计思想，巩固对结构体和数组的运用。

实验原理：C语言结构化程序设计思想，结构体及数组的应用。

实验设备：电脑，TURBO C2.0/WIN-TC/VISUAL C++实验内容：1、顺序表的倒置。

2、顺序表的有序插入。

实验代码：void order_input(list* p, int* count) {int number; printf("输入您想要插入的数字："); scanf("%d", &number);int loc = *count;for (int i = 0; i < *count; i++) {if (p->array[i] > number) {loc = i;break; // 找到位置后退出循环} }// 将元素从 loc 位置开始向右移动一位for (int i = *count; i > loc; i--) {p->array[i] = p->array[i - 1];}// 在 loc 位置插入新元素p->array[loc] = number; (*count)++;}void revers(list* p, int count) {int left = 0; int right = count - 1; int temp;for (int i = 0; i < count / 2; i++) {temp = p->array[right]; p->array[right] = p->array[left]; p->array[left] = temp;right--; left++; } }实验结果：输入几个数字:5 现在开始输入数字：1 3 5 6 8 倒置输出数组：8 6 5 3 1输入要有序插入的数字：7 现在开始输出数组：8 7 6 5 3 1实验心得：通过本次实验，深入理解了有序列表中插入元素的操作，掌握了保持列表有序性的方法。

实验二线性表的链式存储及其操作实验项目：线性表的链表实现：遍历、插入、删除、翻转实验类型: 基础性一【指导思想】用链表存储线性表，实现线性表的基本操作。

二【实验目的及要求】1、复习C语言的指针的定义、链表的使用；2、理解线性表的属性；3、实践线性表的链式实现方法以及相关的操作。

4、要求：提交实验报告，附源程序中填空的内容（10处）、打印运行结果涉及的知识点：线性表的逻辑属性、运算带表头的单链表的操作：定义、输入、输出、链表内容的翻转元素/链表的操作：元素的插入、删除三【实验内容】实现链表的输入、输出、插入、删除、翻转等功能，教师提供主要源代码，其中有10处标出需要学生填空，使得整个程序能正确运行。

问题描述：用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。

链表的头结点存放链表后面的结点个数，初始化时就生成头结点（初值为0）。

链表翻转是把数据逆序（变成降序），注意，头结点不动。

翻转后要再翻转一次，恢复升序后才能插入新元素，否则会出错。

实验步骤：读懂后面附带的源代码，在标注“填空”的位置填写适当的表达式或语句，使得程序完成指定功能。

测试要求：1、连续插入5个实数；要求：插入的元素要分别位于表头、表中、表尾，以确保该插入函数适合于各种情况；2、翻转链表，确认成功后再翻转一次，恢复元素的升序序列；3、删除3个数组元素，删除的元素要分别要位于表头、表中、表尾，以确保该删除函数适合于各种情况；4、删除一个不存在的元素，确认链表的内容没被改变。

//***************************************//////#include <stdio.h>#include "malloc.h"#define null 0struct node{float data;struct node *next;};void insert(float aa,struct node *vq){struct node *newnode,*p;newnode=(struct node *)malloc(sizeof(struct node));newnode->data=aa;p=vq;while ((p->next!=null)&&(p->next->data<aa))/* 填空1 */newnode->data=aa;newnode->next=p->next;/* 填空2 */p->next=newnode;vq->data=vq->data+1;}void dele(float aa,struct node *vq){struct node *p,*q;p=vq;while ((p->next!=null)&&(p->next->data<aa))/* 填空3 */p++;p=p->next;if ((p->next==null)||(p->next->data!=aa))printf("\n%5.1f is not in the link !",aa);else if (p->next->data==aa){q=p->next;p->next=q->next;/* 填空4 */free(q);/* 填空5 */vq->data=vq->data-1;}}void print(struct node *vq){struct node *p;printf("\nthe length of link is %4.0f",vq->data);p=vq->next;printf("\nthe link is:");while (p!=NULL) /* 填空6 */{printf("%5.1f",p->data);/* 填空7 */p=p->next;}}void reverse(struct node *vq){struct node *q,*p;p=vq->next;vq->next=p->next;/* 填空8 */while (p!=null){q=p;p=p->next;/* 填空9 */q->next=p->next /* 填空10 */;vq->next=q;}}main(){int mark=1,op;float aa;struct node *vq;vq=(struct node *)malloc(sizeof(struct node));vq->data=0;vq->next=null;while (mark==1){printf("\nWhich kind of operation will you select ? ");printf("\ninsert---1, delete---2, print---3, reverse---4, exit---0 : ");scanf("%d",&op);switch (op){case 0: mark=0;break;case 1: printf("\nPlease input the new element:");scanf("%f",&aa);insert(aa,vq);print(vq);break;case 2: if (vq->data==0)printf("\n the link is null !",aa);else{printf("\nPlease input the deleted element:");scanf("%f",&aa);dele(aa,vq);print(vq);}break;case 3: print(vq);break;case 4: reverse(vq);print(vq);break;default:printf(" input error!\n");}}}////////***************************************以下是待填空的源代码，请同学们粘贴到系统中填空、运行、测试：/* 链表操作：插入、删除、输出、翻转用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。

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

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

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

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

问题就出在这⾥。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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