数据结构-计算机系(ppt240)-经营管理(编辑修改稿)

数据结构-计算机系(ppt240)-经营管理(编辑修改稿)内容摘要：

储结构，简称为链表 (Linked List)。 线性链表 链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。 因此，链表中结点的逻辑次序和物理次序不一定相同。 为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针 (pointer)或链 (link)。 这两部分组成了链表中的结点结构： 来自 的资料库下载 其中： data域是数据域，用来存放结点的值。 next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。 链表正是通过每个结点的链域将线性表的 n个结点按其逻辑次序链接在一起的。 由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（ Single Linked)。 显然，单链表中每个结点的存储地址是存放在其前趋结点 next域中，而开始结点无前趋，故应设头指针 head指向开始结点。 同时，由于 终端结点无后继，故终端结点的指针域为空，即null（图示中也可用 ^表示 )。 例 线性表 :(bat， cat， eat， fat， hat， jat，lat， mat) data link 来自 的资料库下载 的单链表示意图如下： …… 110 …… 130 135 …… 160 头指针 head 165 170 …… 200 205 …… ……… …… hat 200 …… . …… cat 135 eat 170 … . …… mat Null bat 130 fat 110 …… …… jat 205 lat 160 …… …… 165 来自 的资料库下载  head bat cat eat mat ^ … 单链表是由表头唯一确定，因此单链表可以用头 指针的名字来命名。 例如：若头指针名是 head，则把链表称为表 head。 用 C语言描述的单链表如下： Typedef char datatype。 Typedef struct node{ datatype data。 struct node *next。 }listnode。 来自 的资料库下载 typedef listnode *linklist。 listnode *p。 linklist head。 注意区分指针变量和结点变量这两个不同的概念。 P为动态变量，它是通过标准函数生成的，即 p=(listnode*)malloc(sizeof(listnode))。 函数 malloc分配了一个类型为 listnode的结点变量的空间，并将其首地址放入指针变量 p中。 一旦 p所指的结点变量不再需要了，又可通过标准函数 free(p) 释放所指的结点变量空间。 来自 的资料库下载  指针变量 P和（其值为结点地址）和结点变量*P之间的关系。 来自 的资料库下载 一、建立单链表 假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符‘ \n‘为输入结束标记。 动态地建立单链表的常用方法有如下两种： 头插法建表 该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。 来自 的资料库下载 linklist createlistf(void) { char ch。 linklist head。 listnode *p。 head=null。 ch=getchar( )。 while (ch!=‵ \n′{ p=(listnode*)malloc(sizeof(listnode))。 p–data=ch。 p–next=head。 来自 的资料库下载 head=p。 ch=getchar( )。 } return (head)。 } 来自 的资料库下载 listlink createlist(int n) { int data。 linklist head。 listnode *p head=null。 for(i=n。 i0。 i){ p=(listnode*)malloc(sizeof(listnode))。 scanf((〝 %d〞 ， amp。 p–data)。 p–next=head。 head=p。 } 来自 的资料库下载 return(head)。 } 尾插法建表 头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。 若希望二者次序一致，可采用尾插法建表。 该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针 r，使其始终指向当前链表的尾结点。 例： 来自 的资料库下载 linklist creater( ) { char ch。 linklist head。 listnode *p， *r。 //(， *head。 ) head=NULL。 r=NULL。 while((ch=getchar( )!=‵ \n′){ p=(listnode *)malloc(sizeof(listnode))。 p–data=ch。 if(head=NULL) head=p。 else 来自 的资料库下载 r–next=p。 r=p。 } if (r!=NULL) r–next=NULL。 return(head)。 } 说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中， 来自 的资料库下载 而其余结点的位置是在其前趋结点的指针域中。 算法中的第一个 if语句就是用来对第一个位置上的插入操作做特殊处理。 算法中的第二个 if语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表 head是空表，尾指针 r亦为空，结点 *r不存在；否则链表 head非空，最后一个尾结点 *r是终端结点，应将其指针域置空。 如果我们在链表的开始结点之前附加一个结点，并称它为 头结点 ，那么会带来以下两个优点： a、由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就 来自 的资料库下载 和在表的其它位置上的操作一致，无需进行特殊处理； b、无论链表是否为空，其头指针是指向头结点 在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。 其算法如下： linklist createlistr1( ){ char ch。 linklist head=(linklist)malloc(sizeof(listnode))。 listnode *p， *r 来自 的资料库下载 r=head。 while((ch=getchar( ))!=‵ \n′{ p=(listnode*)malloc(sizeof(listnode))。 p–data=ch。 p–next=p。 r=p。 } r–next=NULL。 return(head)。 } 来自 的资料库下载 上述算法里动态申请新结点空间时未加错误处理，可作下列处理： p=(listnode*)malloc(sizeof(listnode)) if(p==NULL) error(〝 No space for node can be obtained〞 )。 return ERROR。 以上算法的时间复杂度均为 O(n)。 来自 的资料库下载 二、查找运算 按序号查找 在链表中，即使知道被访问结点的序号 i，也不能象顺序表中那样直接按序号 i访问结点，而只能从链表的头指针出发，顺链域 next逐个结点往下搜索，直到搜索到第 i个结点为止。 因此，链表不是随机存取结构。 设单链表的长度为 n，要查找表中第 i个结点，仅当 1≦i≦n 时， i的值是合法的。 但有时需要找头结点的位置，故我们将头结点看做是第 0 个结点，其算法如下： 来自 的资料库下载 Listnode * getnode(linklist head ， int i) { int j。 listnode * p。 p=head。 j=0。 while(p–next amp。 amp。 jI){ p=p–next。 j++。 } if (i==j) return p。 来自 的资料库下载 else return NULL。 } 按值查找 按值查找是在链表中，查找是否有结点值等于给定值 key的结点，若有的话，则返回首次找到的其值为 key的结点的存储位置；否则返回 NULL。 查找过程从开始结点出发，顺着链表逐个将结点的值和给定值 key作比较。 其算法如下： 来自 的资料库下载 Listnode * locatenode(linklist head， int key) { listnode * p=head–next。 while( p amp。 amp。 p–data!=key) p=p–next。 return p。 } 该算法的执行时间亦与输入实例中的的取值key有关，其平均时间复杂度的分析类似于按序号查找，也为 O(n)。 来自 的资料库下载 三、插入运算 插入运算是将值为 x的新结点插入到表的第 i个结点的位置上，即插入到 ai1与 ai之间。 因此，我们必须首先找到 ai1的存储位置 p，然后生成一个数据域为 x的新结点 *p，并令结点 *p的指针域指向新结点，新结点的指针域指向结点 ai。 从而实现三个结点 ai1， x和 ai之间的逻辑关系的变化，插入过程如： 来自 的资料。