软件技术基础 线性结构—链表

1、软件技术基础软件技术基础制作主讲段景山链接存储的线性表链接存储的线性表l1.2、 链接存储的线性表（链表）的定义链接存储的线性表（链表）的定义l1.2.1、 链表的引入链表的引入v数组结构的缺点数组结构的缺点:1、在插入、删除时要移动大量的节点、在插入、删除时要移动大量的节点2、表的大小固定。、表的大小固定。预先在申明数组时指定，无法更改预先在申明数组时指定，无法更改v原因：原因：都可归因到：存放的连续性都可归因到：存放的连续性v突破突破离散存放离散存放用指针来表示元素之间的关系。用指针来表示元素之间的关系。链接存储的线性表链接存储的线性表l用链表实现线性表（非连续存储）用链表实现线性表（非连

2、续存储）a1a2a3a4链表的定义链表的定义l1.2.2 链表的定义链表的定义l链点链点datalink元素域元素域链接域链接域元素域（数据元素域）：存放一个数据元素。元素域（数据元素域）：存放一个数据元素。链接域（关系域）：存放指向下一个元素的指针链接域（关系域）：存放指向下一个元素的指针表示表示/记录元素间的关系。记录元素间的关系。元素域元素域 + 链接域链接域 = 结点（链点）结点（链点）链表的要素链表的要素l链表链表a1a2an由链点及链点相互间的链接构成head链表头head链表尾tail链表长度（结点数目）lengthtaillength算法动手做算法动手做l请准备请准备 6 张小

3、纸片在纸片的中间画两个格子。张小纸片在纸片的中间画两个格子。l在最左边格子外面按序写上不同的号码，代表每个链点在最左边格子外面按序写上不同的号码，代表每个链点的地址。写完地址后，像洗扑克牌那样将小纸片交换位的地址。写完地址后，像洗扑克牌那样将小纸片交换位置。在纸片中间一格填写置。在纸片中间一格填写“ax”表示元素值（目的是使表示元素值（目的是使x的大小关系尽量不要和地址大小关系一致）的大小关系尽量不要和地址大小关系一致）l做好卡片后，同组的同学交换卡片，完成后面的内容做好卡片后，同组的同学交换卡片，完成后面的内容l最右边一格代表每个链点的指针变量，在里面填写后继最右边一格代表每个链点的指针变量

4、，在里面填写后继元素的元素的“地址地址”。请将其中的。请将其中的5张卡片按照地址大小排张卡片按照地址大小排成一列，然后再按元素线性关系填写成一列，然后再按元素线性关系填写“地址栏地址栏”形成一形成一个链表。个链表。l做好后，从链表首开始逐个寻找链点，体会链表的结构做好后，从链表首开始逐个寻找链点，体会链表的结构链表的定义链表的定义l定义定义typedef struct node_typeelemtype data;struct node_type * next;node_type ;typedef struct list_typenode_type *head;node_type *tail;

5、/很少用很少用int length;list_type;datanext元素值的类型，如：int 整型char 字符型long 长整型struct 复合型链表的定义链表的定义l链表组织：链表组织：list_type *list;list-head = &a1;a1-next = &a2;a2-next = &a3;an-next = NULL；list-tail = &an;list-length = n;a1a2anheadtailNULL，表示指针的值为“空”，即指针指向空处链表的基本操作链表的基本操作l1.2.3 链表的基本操作链表的基本操作v访问访问v插入插入v删除删除链表的基本操作链

6、表的基本操作l访问操作访问操作v问题描述：访问链表的第问题描述：访问链表的第i个节点个节点v问题分析：问题分析：输入：链表，输入：链表，i输出：链点输出：链点指向链点的指针指向链点的指针v算法实现分析：算法实现分析：a1a2anheadtailtemptemptemp算法动手做算法动手做l回到小纸片中，如何描述我们找到第回到小纸片中，如何描述我们找到第i个节个节点的动作。点的动作。v1、先、先得得到链表首结点（的地址）到链表首结点（的地址）v2、通过、通过“地址地址”，找到链点，找到链点v3、在链点中找到后继元素的、在链点中找到后继元素的“地址地址”v4、记录这个地址，回到、记录这个地址，回到

7、2从自然语言到算法语言从自然语言到算法语言l如何描述我们在链表上如何描述我们在链表上“逐个去找逐个去找”的动作的动作？v1、先找到链表首结点的地址、先找到链表首结点的地址v2、通过、通过“地址地址”，找到链点，找到链点v3、在链点中找到后继元素的、在链点中找到后继元素的“地址地址”v4、记录这个地址，、记录这个地址，回到回到2p = list-head;while( )p-data p = p-next;p-next 继续完善描述继续完善描述l我们需要的是找到第我们需要的是找到第i个节点个节点v1、先找到链表首结点的地址、先找到链表首结点的地址v2、通过、通过“地址地址”，找到链点，找到链点v

8、3、在链点中找到后继元素的、在链点中找到后继元素的“地址地址”v4、记录这个地址，、记录这个地址，回到回到2p = list-head;while( )p-data p = p-next;p-next counter = 1;counter +;if( counter = i)break;p = list-head;while( )p = p-next;counter = 1;counter +;if( counter = i)break;计数，如果计数到i，就结束node_type *get_node( list, i )while(counter next;int counter ;nod

9、e_type * p;return p;if( p = = NULL) return NULL;p = list-head;counter = 1;a1aiai+1an pa2逐个“数”的动作当in时算法结果怎样？思考访问操作访问操作l注意注意1、p = p-next ;沿链表前进沿链表前进2、循环结束条件、循环结束条件counter = = i 或或 node = = NULLcounter list-length思考如果希望获得值为x的元素，如何实现？while( p-data = x & p != NULL)插入操作插入操作l链表插入操作链表插入操作v问题描述：问题描述：在元素在元素ai

10、前插入新的元素前插入新的元素new_node ;v问题分析：问题分析：输入：链表，输入：链表，location，x输出：插入新元素后的链表。输出：插入新元素后的链表。v算法实现分析算法实现分析算法动手做算法动手做l又回到小纸片，如果要向第又回到小纸片，如果要向第4个节点前放个节点前放入一个新的链点。如何描述这个过程。入一个新的链点。如何描述这个过程。head = 55p = 插入操作插入操作a1aianheadtailai-1.anewa1aianheadtailai-1.anew插入操作插入操作void insertl（list, new_node , location） ai-1-next

11、 = anew ;anew-next = ai ;插入操作插入操作void insertl（list, new_node , location） ?a1ai-1aianpnewnodea2插入操作插入操作void insertl（list, new_node , location） a1ai-1aianpnewnodea2插入操作插入操作void insertl（list, new_node , location） while( counter next;new_node-next = p-next;p-next = new_node;counter = 1;p = list-head; 初始

12、化list-length +;插入操作插入操作a1插入操作插入操作 表首插入表首插入void insertl（list, new_node , location） while( counter next;new_node-next = p-next;p-next = new_node;counter = 1;p = list-head; 初始化if(location = 1)elsenew_node-next = list-head;list-head = new_node;list-length +;思考，教材算法中输入参数的*，与本算法的异同，相应的原因插入操作插入操作 表尾插入表尾插入a

13、1ai-1aianlist-headwhile( counter next;new_node-next = p-next;p-next = new_node;p-next != NULL)NULL p插入操作插入操作else从插入算法中对链表操作的体会从插入算法中对链表操作的体会l1、链表操作往往从表头开始，逐个找到、链表操作往往从表头开始，逐个找到需要的链点需要的链点l2、链表操作的有向性、链表操作的有向性 不能回退；不能回退；l3、链表指针小心使用，谨防丢失。、链表指针小心使用，谨防丢失。l4、不能访问空指针的成员、不能访问空指针的成员l5、插入过程没有对链点内容进行搬移。、插入过程没有对

14、链点内容进行搬移。链表的创建链表的创建create_list( list, x ) while( )new_node-data = x;new_node-next = NULL;new_node-next = list_head;list-head = new_node; new_node = malloc(sizeof(node_type);scanf( “%d”, &x );删除操作删除操作l链表的删除操作链表的删除操作v问题描述：删除元素问题描述：删除元素ai ;v问题分析：问题分析：输入：链表，输入：链表，location输出：删除元素后的链表。输出：删除元素后的链表。v算法实现分析算

15、法实现分析a1ai+1anheadtailai-1.aiai-1-next = ai-next;即即ai-1-next = ai-1-next-next;删除操作删除操作找到找到ai-1执行删除动作执行删除动作void deletel（list, location）注意，从链表上取下的链点注意，从链表上取下的链点ai-1需要用一个临时指针记录下来，需要用一个临时指针记录下来，否则可能丢失否则可能丢失a1ai+1anheadtailai-1.ai删除操作删除操作void deletel（list, location） while( counter next;p-next = p-next-nex

16、t;counter = 1;p = list-head; 初始化if(location = 1)elselist-head = list-head-next;temp = p-next;free(temp);temp = list-head;free(temp);list-length -;从链表删除的链点，一般应该释放其空间删除操作删除操作l注意注意:v对被删除删除链点的处理对被删除删除链点的处理往往需要释放其动态申请的空间往往需要释放其动态申请的空间free（ ）如果希望删除值为x的元素，如何实现？while( p-data = x & p != NULL) 可以吗？while( p-ne

17、xt-data = x & p-next != NULL) 可以吗？l1.2.4 链表的特点链表的特点v、操作的顺序性、操作的顺序性有平均次查找过程。有平均次查找过程。v、离散存放、离散存放不受链表大小限制不受链表大小限制不进行链点内容的搬移不进行链点内容的搬移v查找操作：数组效率优于链表查找操作：数组效率优于链表v插入、删除操作：链表效率优于数组插入、删除操作：链表效率优于数组链表的特点链表的特点上机练习题上机练习题l例、读入一组数建立链表，以负数作为例、读入一组数建立链表，以负数作为输入结束输入结束l算法实现分析算法实现分析v输入：输入：空链表空链表元素值从键盘输入。（从文件读入？）元素值

18、从键盘输入。（从文件读入？）v输出：创建好的链表输出：创建好的链表例、读入一组数建立链表，以负数作为输入例、读入一组数建立链表，以负数作为输入结束结束建立建立框架：框架：上机练习指导上机练习指导main( )x 0; 初始化初始化while (x = 0)read( &x )；插入链表；插入链表；read( int * x)scanf( “data %d: “，x);上机练习题上机练习题每次插在表头或者每次插在表尾？每次插在表头或者每次插在表尾？决定每次插在表尾！决定每次插在表尾！new_node-next = list.tail-next;list.tail-next = new_node;

19、list.header = new_node;list.tail = new_node;上机练习指导上机练习指导list_type * create_list( )初始化；初始化；while( x = 0)read(&x);生成新元素生成新元素插入新元素插入新元素return list;上机练习指导上机练习指导list_type * create_list( )list_type *list;list-length = 0; list-header = NULL;list-tail = NULL;node_type * new_node;int x;list = malloc(sizeof(l

20、ist_type);while( x = 0)new_node = (node_type *)malloc(size_of(struct node_type);new_node-data = x; 假设假设elemtype 就是整数类型就是整数类型new_node-next = NULL;if( list.length next = list.tail-next;list.tail-next = new_node;list.tail = new_node;list.legth +;read(x);return list;read(x);上机练习题上机练习题例例2 2、检查一个（单向）链表，删除

21、其中数据大于、检查一个（单向）链表，删除其中数据大于100100的元素的元素算法实现分析算法实现分析（1 1）逐个检查链表的算法框架）逐个检查链表的算法框架while(current != NULL).current = current-next ;ai+1ai-1.aicurrent上机练习题上机练习题(2) (2) 删除大于删除大于100100的链点的链点if( current-data 100)if( current-data 100)删除该链点删除该链点 必须找到必须找到currentcurrent的前趋链点才能删除的前趋链点才能删除ai+1ai-1.aicurrentlastlast

22、-next = current-next;free(current);current = last-next;删除删除不删除不删除last = current;current = current-next;上机练习题上机练习题(3)(3)边界：第一个元素需要删除时边界：第一个元素需要删除时if(last = = NULL)list-header = current-next;free(current);current = list-header;ai+1a1.aicurrentlast上机练习题上机练习题del_over100(list_type * list)初始化初始化while(curr

23、ent != NULL)if(current-data 100)删除删除current;else走向下一个链点；走向下一个链点；体会体会llast指针的作用指针的作用l思考思考可不可以只用只用一个指针完成算法？可不可以只用只用一个指针完成算法？ 用双向链表来完成本算法，有什么不同？用双向链表来完成本算法，有什么不同？上机练习题上机练习题例例3、将一个单向链表反向连接、将一个单向链表反向连接算法分析算法分析（1）逐个进行的基本框架）逐个进行的基本框架（2）反向操作）反向操作方法一：方法一：header1header2目标目标上机练习题上机练习题a1方法二、直接在原链表的基础上操作方法二、直接在原链表的基础上操作a2a3a4a1a2a3a4ai-2ai-1aiai+1ai+2currentcontinuelastcurre