《数据结构第二章线性表》由会员分享，可在线阅读，更多相关《数据结构第二章线性表（57页珍藏版）》请在金锄头文库上搜索。
1、第二章第二章线性表线性表内容提要内容提要:线性表是一种最简单、最常见的数据结构。:本章将详细介绍线性表的基本概念、线性表的逻辑结构特性、线性表两种主要的存储结构以及线性表的一些常见运算，特别是在这两种存储结构上如何实现线性表的基本运算。 第第2章章 线性表线性表2.1 线性表的定义及基本运算2.2 线性表的顺序存储结构及其运算2.3 线性表的链接存储结构及其运算2.4 顺序表和链表的比较2.5 线性表的简单应用举例2.1.1 2.1.1 线性表的定义线性表的定义 线性表是由n（n0）个数据元素（结点）a1, a2, a3, , an组成的有限序列。通常，我们把非空的线性表（n0）记为：A=A=
2、（a a1 1, a, a2 2, a, a3 3, , a, , an n） A是线性表的表名。一个线性表可以用一个标识符来命名。 ai（1in）是表中的数据元素。 n是线性表中数据元素的个数，也称为线性表的长度。n=0的线性表称为空表，此时，表中不包含任何数据元素。特点：特点：1、整个线性表中只有一个元素前面无数据元、整个线性表中只有一个元素前面无数据元素（无前驱），只有一个元素后面没有元素素（无前驱），只有一个元素后面没有元素（无后继），这两个元素分别称为第一个元（无后继），这两个元素分别称为第一个元素和最后一个元素。素和最后一个元素。2 、除第一个元素和最后一个元素以外，线、除第一个元
3、素和最后一个元素以外，线性表中每个数据元素都只有一个前驱和一个性表中每个数据元素都只有一个前驱和一个后继。后继。【例2.3】学生成绩统计表也是一个线性表，见表2.1。在线性表中每个学生的成绩是一个数据元素，它由学号、姓名、数学、外语、物理、总分这6个数据项组成。该线性表的长度为5。2.1.2 线性表的基本运算n n线性表上常用的基本运算有以下9种： 线性表的初始化（initiate）：将线性表设置成一个空表。 求表的长度（length）：求线性表的长度。 取出表的元素（getdata）：访问线性表中的第i个元素。 查找运算（search）：查找线性表中具有某个特征值的数据元素。 插入运算（in
4、sert）：在线性表中的第i个元素之前或之后插入一个新元素。 删除运算（delete）：删除线性表中第i个元素或满足给定条件的第一个元素。 排序运算（sort）：将线性表中的所有元素按给定的关键字进行排序。 归并运算（catenate）：把两个线性表合并为一个线性表。 分离运算（separate）：将线性表按某一要求分解成两个或几个线性表。线性表常用的存储方式有两种：线性表常用的存储方式有两种：顺序存储方式和链接存储方式用顺序存储方式实现的线性表称为顺序表；用链接存储方式实现的线性表称为链表。2.2 线性表的顺序存储结构及运算 2.2.1 2.2.1 线性表的顺序存储结构线性表的顺序存储结构2
5、.2.2 2.2.2 顺序表的基本运算顺序表的基本运算2.2.3 2.2.3 插入和删除运算的时间分析插入和删除运算的时间分析2.2.4 2.2.4 顺序表的优点和缺点顺序表的优点和缺点 2.2.1 线性表的顺序存储结构线性表的顺序存储结构 线线线线性性性性表表表表的的的的顺顺顺顺序序序序存存存存储储储储方方方方法法法法是是是是：将将线线性性表表的的所所有有元元素素按按其其逻逻辑辑顺顺序序依依次次存存放放在在内内存存中中一一组组连连续续的的存存储储单单元元中中，也也就就是是将将线线性性表表的的所所有有元元素素连连续续地地存存放放到到计计算算机机中中相相邻邻的的内内存存单单元元中中，以以保保证证
6、线线性性表表元元素逻辑上的有序性。素逻辑上的有序性。 顺顺顺顺序序序序表表表表的的的的特特特特点点点点是是是是：其其逻逻辑辑关关系系相相邻邻的的两两个个结结点点在在物物理理位位置置上上也也相相邻邻，结结点点的的逻逻辑辑次次序序和和物物理理次次序序一致。一致。 线性表的顺序存储结构可用数组来实现。线性表的顺序存储结构可用数组来实现。线性表的顺序存储结构可用数组来实现。线性表的顺序存储结构可用数组来实现。n n线性表的顺序存储结构可用数组来实现。数组元素的类型就是线性表中数据元素的类型，数组的大小，最好大于线性表的长度。因此，顺序存储结构是把线性表中每个元素a1, a2, a3, , an依次存放
7、到数组下标为0, 1, 2, n1的位置上。n n假设用数组dataMAXSIZE存储线性表 A =（a1, a2, a3, , an） 其顺序存储结构如图2.1所示。图图2.1 2.1 顺序存储结构示意图顺序存储结构示意图 由于线性表中所有结点的数据类型是相同的，因此每个结点占用的存储空间也是相同的。假设每个结点占用d个存储单元，若线性表中第一个结点a1的存储地址为LOC(a1)，那么结点ai的存储地址LOC(ai)可以通过下面的公式计算得到： LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+()+(i i 1) 1) d d（1 1 i i n n）（）（）（）（2.12.
8、1） 式中，LOC(a1)是线性表第一个元素的存储地址，称为线性表的存存储储首首地地址址或基基址址。 顺顺顺顺序序序序存存存存储储储储结结结结构构构构的的的的特特特特点点点点是是是是：在在线线性性表表中中，每每个个结结点点a ai i的的存存储储地地址址是是该该结结点点在在表表中中位位置置i i的的线线性性函函数数，只只要要知知道道基基地地址址和和每每个个结结点点占占用用存存储储单单元元的的个个数数，利利用用地地址址计计算算公公式式就就可可以以直直接接计计算算出出任任一一结结点点的的存存储储地地址址，从从而而实实现现线线性性表表中中数数据据元元素素的的快快速速存存取取，其其算算法法的的时时间间
9、复复杂杂度度为为O(1)O(1)，与与线线性性表表的的长长度度无无关关。由由此此可可知知，顺顺序序表表是是一种具有很高的存取效率的一种具有很高的存取效率的随机存取结构。随机存取结构。随机存取结构。随机存取结构。n n采采用用顺顺序序存存储储结结构构表表示示线线性性表表时时，如如果果将将存存储储数数据据元元素素的的数数组组和和存存储储线线性性表表实实际际长长度度的的变变量量同同时时存存放放在在结结构构类类型型sequenlistsequenlist中中，则则顺顺序序表表的类型定义如下：的类型定义如下：#define MAXSIZE 1000#define MAXSIZE 1000#define
10、MAXSIZE 1000#define MAXSIZE 1000typedeftypedeftypedeftypedef intintintint datatypedatatypedatatypedatatype; ; ; ;typedeftypedeftypedeftypedef structstructstructstruct selistselistselistselist datatypedatatypedatatypedatatype dataMAXSIZE; dataMAXSIZE; dataMAXSIZE; dataMAXSIZE; intintintint last; last
11、; last; last; sequenlistsequenlistsequenlistsequenlist; ; ; ; /* /* /* /* 顺序结构类型为顺序结构类型为顺序结构类型为顺序结构类型为sequenlistsequenlistsequenlistsequenlist */ */ */ */sequenlistsequenlistsequenlistsequenlist *l; *l; *l; *l; /* /* /* /* 定义指针类型定义指针类型定义指针类型定义指针类型 * * * */ / / /datadatadatadata一一维维数数组组存存放放线线性性表表的的元元
12、素素，线线性性表表中中第第1, 1, 2, 2, lastlast个个元元素素分分别别存存放放在在数数组组第第0, 0, 1, 1, lastlast 1 1位置上；位置上；MAXSIZEMAXSIZEMAXSIZEMAXSIZE数组数组datadata能容纳元素的最大值，称能容纳元素的最大值，称顺序表容量顺序表容量顺序表容量顺序表容量；lastlastlastlast线性表当前的实际长度；线性表当前的实际长度；datatypedatatypedatatypedatatype 线性表元素类型，应视具体情况而定。线性表元素类型，应视具体情况而定。顺序表的类型定义如下：顺序表的类型定义如下：n n
13、【例例2.3】学生成绩统计表也是一个线性表，见表2.1。在线性表中每个学生的成绩是一个数据元素，它由学号、姓名、数学、外语、物理、总分这6个数据项组成。该线性表的长度为5。图图2.2 2.2 数据元素为记录的线性表的顺序存储示意图数据元素为记录的线性表的顺序存储示意图 例如，例如，用顺序表存储表2.1所示的学生成绩统计表时，其顺序存储分配情况如图2.2所示：# define MAX 500# define MAX 500typedeftypedef structstruct node node /* /* 定义学生记录结构类型定义学生记录结构类型 * */ / char no10; char
14、no10; /* /* 定义学生的学号定义学生的学号 * */ / char name10;char name10; /* /* 定义学生的姓名定义学生的姓名 * */ / float score5;float score5; /* /* 定义学生各科成绩定义学生各科成绩 * */ / datatypedatatype; ; /* /* 学生记录学生记录为为datatypedatatype */ */typedeftypedef structstruct selistselist datatypedatatype dataMAX; dataMAX;/* data/* data存放学生成绩统计表
15、存放学生成绩统计表 * */ / intint last; last; /* last/* last为学生成绩表中人数为学生成绩表中人数 * */ / sequenlistsequenlist; ; /* /* 顺序表类型为顺序表类型为sequenlistsequenlist */ */sequenlistsequenlist *l; *l; /* /* 定义指针类型定义指针类型 * */ /学生成绩统计表的存储结构的类型说明如下：学生成绩统计表的存储结构的类型说明如下：学生成绩统计表的存储结构的类型说明如下：学生成绩统计表的存储结构的类型说明如下：2.2.2 顺序表的基本运算n n定义线性表
16、的顺序存储结构之后，就可以讨论在该存储结构上如何实现线性表的基本运算了。顺序表的基本运算有：插入运算插入运算删除运算删除运算查找运算查找运算遍历运算遍历运算1在顺序表中插入一个新结点xn n线性表的插入运算线性表的插入运算线性表的插入运算线性表的插入运算是指在表的第是指在表的第是指在表的第是指在表的第i i（1 1i in n+1+1）个位个位个位个位置上，插入一个新的结点置上，插入一个新的结点置上，插入一个新的结点置上，插入一个新的结点x x，使长度为使长度为使长度为使长度为n n的线性表：的线性表：的线性表：的线性表： ( a( a1 1, , , a, ai i 1 1 , , a ai
17、 i , a, ai i+1 +1 , , a, an n ) ) n n变成为长度为变成为长度为n n+1+1的线性表：的线性表： ( a( a1 1, , , a, ai i 1 1, x, , x, a ai i, a, ai i+1+1, , a, an n ) )n n由由于于顺顺序序表表中中结结点点在在计计算算机机中中是是连连续续存存放放的的，若若在在第第i i个个结结点点之之前前插插入入一一个个新新结结点点x x，就就必必须须将将表表中中下下标标位位置置为为i i, , i i+1, +1, , , n n上上的的结结点点依依次次向向后后移移动动到到i i+1, +1, i i+
18、2, +2, , , n n+1+1的的位位置置上上，空空出出第第i i个个位置，然后在该位置上插入新结点位置，然后在该位置上插入新结点x x。n n仅仅当当插插入入位位置置i i= =n n+1+1时时，才才无无须须移移动动结结点点，直直接接将将x x插插到到表表的的末末尾尾。新新结结点点插插入入后后，线线性性表表的长度变成的长度变成n n+1+1。在顺序表中插入一个新结点的过程如下： 检查顺序表的存储空间是否已满，若满则停止插入，退出程序运行； 将第in个结点之间的所有结点依次向后移动一个位置，空出第i个位置； 将新结点x插入第i个位置； 修改线性表的长度，使其加1；若插入成功，则函数返回
19、值为1，否则函数值返回值为0。在顺序表中给定的位置上插入值为在顺序表中给定的位置上插入值为在顺序表中给定的位置上插入值为在顺序表中给定的位置上插入值为x x x x的结点的算法的结点的算法的结点的算法的结点的算法-1-1-1-1 intint insert_listseq(linsert_listseq(l, x, i), x, i)sequenlistsequenlist *l; *l; /* l/* l是是sequenlistsequenlist类型指针变量类型指针变量 * */ /intint i; i; /* /* 给出在顺序表中的插入位置给出在顺序表中的插入位置i i */ */da
20、tatypedatatype x; x;/* /* 给出插入结点数据给出插入结点数据x */x */ intint j; j; if (*l).lastMAXSIZE) if (*l).lastMAXSIZE) /* /* 检查顺序表的长度检查顺序表的长度 * */ / printf(ntprintf(nt溢出错误溢出错误!n); !n); /* /* 打印溢出错误信息打印溢出错误信息 * */ / return (NULL); return (NULL); /* /* 插入失败函数返回插入失败函数返回0 */0 */ else if (i(*l).last+1) else if (i(*l)
21、.last+1) printf(ntprintf(nt该位置不存在该位置不存在!n);!n); return(NULL); return(NULL); /* /* 结点插入失败，函数返回结点插入失败，函数返回0 */0 */* /* 在顺序表中给定的位置上插入值为在顺序表中给定的位置上插入值为x x的结的结点的算法点的算法-2 */-2 */ elseelse /* /* 在第在第i i个结点个结点a ai i 位置插入值为位置插入值为x x的结点的结点 * */ / for(j=(*l).last-1;j=i-1;j-) for(j=(*l).last-1;j=i-1;j-) (*l).da
22、taj+1=(*l).dataj; (*l).dataj+1=(*l).dataj; /* /* 将结点依次向后移动将结点依次向后移动 * */ / (*l).datai-1=x; (*l).datai-1=x; /* /* 将将x x插插入入第第i i个个结结点点(*l).data(*l).datai i-1 -1 */*/ (*l).last=(*l).last+1; (*l).last=(*l).last+1; /* /* 将线性表的长度加将线性表的长度加1 */1 */ return(1); return(1); /* /* 结点插入成功，函数返回结点插入成功，函数返回1 */1 */
23、 /* INSERT_LISTSEQ */* INSERT_LISTSEQ */4 4在顺序表中查找关键字为在顺序表中查找关键字为keykey的结点的结点 查找运算查找运算是在具有n个结点的顺序表中， 查找关键字为key的元素。若查找成功，则函数返回该关键字在表中位置；若查找失败，则函数返回0。在顺序表中的查找过程如下在顺序表中的查找过程如下： 从顺序表的第一个结点（即数组下标为0的结点）开始依次向后查找； 若第i个结点的值等于key，则查找成功，函数返回结点key在表中的位置i+1； 若查找失败，即表中不存在关键字为key的结点，则函数返回0。在顺序表中查找结点关键字为在顺序表中查找结点关键
24、字为在顺序表中查找结点关键字为在顺序表中查找结点关键字为keykeykeykey的算法如下：的算法如下：的算法如下：的算法如下： intintintint search_search_search_search_listseq(llistseq(l, key) , key) /* /* 在顺序表中查找关键字为在顺序表中查找关键字为keykey结点结点 * */ / sequenlistsequenlist *l; *l;/* /* 查找关键字为查找关键字为keykey结点，若找到返回结点，若找到返回keykey在表中位置，否则返回在表中位置，否则返回0 */0 */datatypedataty
25、pe key; key; /* key/* key为要查找的关键值为要查找的关键值 * */ / intint i=0; i=0; datatypedatatype x; x; x=(*l).datai; x=(*l).datai; while (i(*l).last)&(x!= key) while (i(*l).last)&(x!= key) /* last/* last为顺序表实际长度为顺序表实际长度 * */ / i+; x=(*l).datai; i+; x=(*l).datai; if(key=x) return(i+1); if(key=x) return(i+1); /* /*
26、 若查找成功则返回若查找成功则返回keykey在表中位置在表中位置 * */ / else return(NULL); else return(NULL); /* /* 若查找失败，则返回若查找失败，则返回0 */0 */ /* SEARCH_LISTSEQ */ /* SEARCH_LISTSEQ */ 5顺序表的遍历运算 n n遍遍历历：从线性表的第一个元素开始，依次访问线性表的所有元素并且仅访问一次。n n顺序表的遍历： 依次访问数组data0datalast1中的每一个元素。访问时可以根据需要进行任意的处理，例如，在此仅打印该元素的值。void void print_listseq(l
27、print_listseq(l) /* ) /* 顺序表的遍历算法顺序表的遍历算法 * */ / sequenlistsequenlist *l; *l; intint i, n=(*l).last; /* i, n=(*l).last; /* n n是顺序表的实际长度是顺序表的实际长度 * */ / clrscrclrscr();(); /* /* clrscrclrscr为清屏幕函数为清屏幕函数 * */ / for (i=0; in; i+) for (i=0; idata=-999; head-data=-999; rear=head; rear=head; /* /* 尾指针的初值为
28、头结点尾指针的初值为头结点head */head */ clear(); clear(); /* /* 函数是清屏、定位和设置颜色函数是清屏、定位和设置颜色 * */ / printf(ttprintf(tt请随机输入互不相同的正整数以请随机输入互不相同的正整数以0 0作为结作为结:nntt);:nntt); scanf(%dscanf(%d, &x);, &x); /* /* 读入第一个结点的值读入第一个结点的值 * */ / /* /* 建立单链表算法建立单链表算法用尾插法建立带头结点单链表用尾插法建立带头结点单链表-2 */-2 */while (x!=0)while (x!=0) /*
29、 /* 输入数据，以输入数据，以0 0为结束符为结束符 * */ / p=(p=(structstruct node*) node*)malloc(LENmalloc(LEN); ); /* /* 生成一个新结点生成一个新结点 * */ / p-data=x;p-data=x; /* /* 给新结点的数据域赋值给新结点的数据域赋值 * */ / rear-next=p;rear-next=p; /* /* 新结点插入到表尾新结点插入到表尾* *rearrear之后之后 * */ / rear=p; rear=p; /* /* 将尾指针将尾指针rearrear指向新的尾结点指向新的尾结点 * *
30、/ / scanf(%dscanf(%d, &x);, &x); /* /* 输入下一个结点的数据输入下一个结点的数据 * */ / rear-next=NULL; rear-next=NULL; /* /* 将链表最后一个结点将链表最后一个结点rearrear指针域置空指针域置空 * */ / return(head); return(head); /* /* 函数返回单链表的头指针函数返回单链表的头指针head */head */ /* CREATE_HEADREAR */ /* CREATE_HEADREAR */（2）用头插法建立链表）用头插法建立链表 用头插法新建一个带头结点的单链表
31、用头插法新建一个带头结点的单链表过程过程如下：如下： 调用调用mallocmalloc函数，建立链表的头结点函数，建立链表的头结点headhead； 调用调用mallocmalloc函数，建立新的结点函数，建立新的结点p p； 给给新新结结点点的的数数据据域域赋赋值值，将将新新结结点点的的指指针针域域指指向向headhead所指的结点；所指的结点； 将链表头结点将链表头结点headhead的指针域修改为新结点的指针域修改为新结点p p； 重重复复上上述述步步骤骤，直直至至输输入入结结束束标标志志0 0时时为止。为止。图2.7 将新结点p插到单链表head的表头/* /* 建建立立单单链链表表算
32、算法法用用头头插插法法建建立立带带头头结结点点单单链链表表-1 */-1 */linklistlinklist * * hhead_creathhead_creat() () datatypedatatype x; x; linklistlinklist *head, *p; *head, *p;/* head/* head为头指针为头指针 * */ / head=( head=(structstruct node*) node*)malloc(LENmalloc(LEN); ); head-data=-999; /* head-data=-999; /* 给表头结点数据域赋值给表头结点数据域
33、赋值 * */ / head-next=NULL; head-next=NULL; clear(); clear(); /* /* 函数是清屏光标定位和设置颜色函数是清屏光标定位和设置颜色 * */ / printf(ntprintf(nt请随机输入一组正整数以请随机输入一组正整数以0 0结束输入结束输入:nt);:nt); scanf(%dscanf(%d, &x);, &x); /* /* 输入第一个结点数据值输入第一个结点数据值 * */ / 2单链表的查找运算单链表的查找运算链表的查找：由于逻辑相邻的结点并没有存储在物理相邻的单元中，所以链表的遍历或查找运算，不能像顺序表那样随机访问任
34、意一个结点，而只能从链表的头指针head出发，顺着链域next逐个结点往下搜索，直到找到所需要的结点为止或者当链表为空时结束查找。（1 1）按值查找运算）按值查找运算 （2 2）按序号查找运算）按序号查找运算 （1）按值查找运算）按值查找运算n n按值查找运算是在带头结点的单链表中查找是否存在给定值为keyx的结点。 n n按值查找运算的基本思想：从链表的头结点开始，依次将链表中结点的数据域与keyx进行比较，若找到给定值keyx，则查查找找成成功功，函数返回该结点的位置；若没有找到给定值keyx，则查查找找失失败败，函数返回NULL。/* /* 带头结点的单链表的查找算法带头结点的单链表的查
35、找算法按值查找运算按值查找运算 * */ /* /* 查查找找值值为为keyxkeyx的的结结点点，若若找找到到则则返返回回该该结结点点的的位位置置，反反之之则返回则返回0 */0 */linklistlinklist *key_search(head, *key_search(head, keyxkeyx) )linklistlinklist *head; *head;datatypedatatype keyxkeyx; ; linklistlinklist *p=head;*p=head; /* /* 从头结点开始扫描从头结点开始扫描 * */ / while(p!=NULL)&(p-da
36、ta!=while(p!=NULL)&(p-data!=keyxkeyx) ) p=p-next; p=p-next; /* /* 扫描下一个结点扫描下一个结点 * */ / if(p-data= if(p-data=keyxkeyx) ) return(p); /* return(p); /* 查找成功返回指向该结点指针查找成功返回指向该结点指针 * */ / else return (NULL); /* else return (NULL); /* 查找失败，函数返回空指针查找失败，函数返回空指针 * */ / /* KEY_SEARCH */ /* KEY_SEARCH */（2 2）按
37、序号查找运算）按序号查找运算 n n按序号查找运算是在带头结点表长为n的单链表中，查找第i个结点，仅当1in时，i值是合法的。n n其算法的基本思想是：从表的头结点开始查找，用指针p指向当前结点，用j作为计数器累计当前扫描过的结点数。j的初值为0，指向表头结点，当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。 /* /* 从从头头结结点点开开始始查查找找第第i i个个结结点点，若若找找到到则则返返回回结结点点的的位位置，反之返回置，反之返回0 */0 */linklistlinklist *no_search(head, i) *no_search(
38、head, i)linklistlinklist *head; *head;intint i; i; linklistlinklist *p; *p; intint j; j; p=head; j=0; p=head; j=0; /* /* 从头结点开始扫描从头结点开始扫描从头结点开始扫描从头结点开始扫描 * */ / while(p-next!=NULL)&(jnext!=NULL)&(jnext; p=p-next; /* /* 扫描下一个结点扫描下一个结点扫描下一个结点扫描下一个结点 * */ / j+; j+; /* /* 统计已扫描结点的个数统计已扫描结点的个数统计已扫描结点的个数统
39、计已扫描结点的个数 * */ / if(i=j) return(p); if(i=j) return(p); else return(NULL); /* else return(NULL); /* 若找不到，则返回空指针若找不到，则返回空指针若找不到，则返回空指针若找不到，则返回空指针 * */ /* NO_SEARCH */* NO_SEARCH */带头结点单链表上查找算法带头结点单链表上查找算法带头结点单链表上查找算法带头结点单链表上查找算法按序号查找运算按序号查找运算按序号查找运算按序号查找运算本章小结本章小结n n线线性性表表是是一一种种最最基基本本、最最常常用用的的数数据据结结构构
40、。本本章章介介绍绍了了线线性性表表的的定定义义、存存储储结结构构描描述述方方法法及及运运算算，重重点点讨讨论论了了线线性性表表的的两两种种存存储储结结构构顺顺序序表表和和链链表表，以以及及在在这这两两种存储结构上基本运算的实现。种存储结构上基本运算的实现。n n顺顺序序表表是是用用一一维维数数组组来来实实现现的的，表表中中结结点点的的逻逻辑辑次次序序和和物物理理次次序序一一致致。顺顺序序表表是是一一种种随随机机存存储储结结构构，对对表表中中任任一一结结点点都都可可以以在在O(O(1)1)时时间间内内直直接接进进行行存存取取，但但进进行行插插入入、删除、连接、两表的合并等运算时较费时间。删除、连接、两表的合并等运算时较费时间。n n链链表表是是用用指指针针来来实实现现的的，表表中中结结点点的的逻逻辑辑次次序序和和物物理理次次序序不不一一致致。链链表表可可以以分分为为3 3种种：单单链链表表、循循环环链链表表和和双双链链表表。链链表表不不是是随随机机存存储储结结构构，在在链链表表中中任任何何位位置置插插入入和和删删除除结结点点的的运运算算都都是是非非常常方方便便的的，但但对对链链表表的的访访问问并并不方便，必须从头指针开始顺着链依次扫描。不方便，必须从头指针开始顺着链依次扫描。
