数据结构概论第2章线性表董黎刚浙江工商大学信电学院

数据结构概论第2章线性表董黎刚浙江工商大学信电学院 donglg@zjgsu.edu.cn
，652068( )，信电楼305 浙江工商大学信电学院二○一五年三月 2017年3月16日

1. 线性表的概念

2.1.1 背景线性表中“线性”是什么意思？从形态上就是一条直线，或者说（数据元素）排成一列。与线性函数的“线性”相关。
2.1 线性表的概念

2.1.2 线性结构线性结构：除第一及最后一个元素外，每个元素都只有一个直接前驱（Immediate Predecessor）和只有一个直接后继（Immediate Successor）。又称为一对一结构例子：字母表，学生成绩表非线性结构：一个元素可能有多个直接前趋或直接后继。可能是一对多、多对一或多对多结构例子：多值函数、常量函数、关系网 2.1 线性表的概念

2.1.3 线性表线性表（Linear List）：具有线性结构的数据对象（列表）。特点
同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。有穷性：线性表由有限个数据元素组成，表长度就是表中数据的个数。有序性：线性表中元素相邻数据元素之间存在着序偶关系<ai,ai+1>。 2.1 线性表的概念

2.1.4 线性表抽象数据类型定义 ADT LinearList{
数据元素：D={ai| ai∈D0, i=1,2,…,n ,n≥0，D0为某一数据对象} 结构关系：Ｓ＝｛<ai,ai+1> | ai, ai+1∈D0，i=1,2, …,n-1｝基本操作：（1）InitList（L） - 初始化（2）DestroyList(L) -销毁（3）ClearList(L) – 清空（置零，不销毁线性表）（4）ListLength（L）- 求表长度（5）GetNode（L，i）- 求表中的第i个元素（6）LocateNode（L，x）- 求表中元素x的位置（第?个）（7）InsertList（L，x，i） - 在表中第i个位置插入元素x （8）DeleteList（L，i）- 删掉表中的第i个元素 2.1 线性表的概念

2.1.4 线性表抽象数据类型定义本书中将介绍以下的ADT LinearList Stack Queue String Array
Tree Graph 2.1 线性表的概念

2.1.5 线性表实例职工工资表是线性表。英文字母表（A，B，…，Z）是线性表，表中每个字母是一个数据元素。
一副扑克牌的点数（2，3，…，10，J，Q，K，A）也是一个线性表，其中数据元素是每张牌的点数。学生成绩表是线性表，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、各科成绩及平均成绩等数据项组成。 2.1 线性表的概念

2. 线性表顺序存储结构定义

2.2.1 背景线性表只是逻辑结构，而不是物理结构/存储结构，因此不能直接用于编程（但是可以用于设计算法）。
线性表可以任选某一种基本物理结构来表达。本章我们将介绍线性表分别用顺序结构和链式结构表达。线性表顺序存储结构最典型的例子就是C语言中的数组。 2.2 线性表顺序存储结构定义

2.2.2 相关概念线性表的顺序存储结构是指用一组地址连续、大小相同的存储单元，按逻辑次序依次存储线性表中的各个元素。
采用顺序存储结构的线性表通常称为顺序表（Sequential List）。（说明：也有文献认为只要采用顺序存储结构就是顺序表） 2.2 线性表顺序存储结构定义

只要知道基地址和每个元素的大小，就可立即求出任一元素的存储地址。从编程角度而言，能直接按序号i访问元素的值，这叫随机存取。
2.2.3 顺序表元素的存储位置计算 loc(ai) =loc(a1)+(i-1)×k 线性表的起始位置或基地址只要知道基地址和每个元素的大小，就可立即求出任一元素的存储地址。从编程角度而言，能直接按序号i访问元素的值，这叫随机存取。 2.2 线性表顺序存储结构定义

2.2.4 用C语言定义顺序表 #define maxsize 100 /*maxsize是线性表可能达到的最大长度，这里假设为100 */
typedef int ElemType; /* ElemType的类型可根据实际情况而定，这里假设为int */ typedef struct { ElemType elem[maxsize]；/* 线性表占用的数组空间*/ int last； /*表中最后一个元素下标，空表置为-1*/ } SeqList； ai对应的数组下标是i-1 可以用长度len（空置时为0）代替last（空置时为-1） 2.2 线性表顺序存储结构定义

2.2.4 用C语言定义顺序表 SeqList L; // L是SeqList类型的顺序表
线性表的开始元素a1和终端元素an分别存储在L.elem[0]和L.elem [L.last]中。 2.2 线性表顺序存储结构定义

2.2.4 用C语言定义顺序表 SeqList *L;// L是SeqList类型的指针变量
L=(SeqList *)malloc(sizeof(SeqList)); 线性表的开始元素a1和终端元素an分别存储在 L-> elem[0]和L-> elem [L->last]中。 2.2 线性表顺序存储结构定义

2.2.5 顺序表上实现的基本运算（1）表的初始化 void InitList（SeqList *L）//将表的长度置为0 {
L-＞last = -1； } （2）求表长 int ListLength（SeqList *L）//求表长 return L-＞last+1; } 2.2 线性表顺序存储结构定义

3. 顺序表的运算 ——查找

2.3.1 背景查找有两种按照地址/序号找：查找位于给定地址或序号的元素，查找成功时（地址或序号合法）返回元素值，查找失败时（地址或序号不合法）返回失败标志。按照内容找：查找与指定元素值满足某种比较关系的元素，查找成功时（元素存在）返回元素地址或序号，查找失败时（元素不存在）返回失败标志。 2.3 顺序表的运算——查找

2.3.2 按序号查找GetData(L,i) 算法思想：要求查找线性表L中第i个数据元素，其结果是L.elem[i-1]或L->elem[i-1]。算法：顺序表中按序号查找 ElemType GetData(SeqList L，int i) { if(i<1||i> L.last+1) Error(“position error”)； return L.elem[i-1]; /*下标=序号-1，因此减1*/ } 2.3 顺序表的运算——查找

2.3.3 按内容查找Locate（L,e）算法思想：要求查找线性表L中与给定值e相等的数据元素，其结果是：若在表L中找到与e相等的元素，则返回该元素在表中的序号；若找不到，则返回一个“空下标”，即-1。 2.3 顺序表的运算——查找

2.3.3 按内容查找Locate（L,e）算法：顺序表中按内容查找 int Locate(SeqList L，ElemType e) {
i=0; //i为扫描计数器，初值为0，即从第一个元素开始比较 while((i<=L.last)&&(L.elem[i]!=e)) i++; /*顺序扫描，直到找到值为e的元素,或扫描到表尾*/ if(i<=L.last) return(i);/*若找到，则返回其下标*/ else return(-1);/*若没找到，则返回-1*/ } 问题：能通过减少一些操作（比如比较）来改善本算法吗？请参考“查找”章中的“顺序查找法”。 2.3 顺序表的运算——查找

2.3.4 查找实例如果按序号查找，用L.elem[8]就能获得第9个元素的值。
如果要查找元素30，需要从第1个元素4开始从左到右，逐个与30对比是否一致。 2.3 顺序表的运算——查找

4. 顺序表的运算 ——插入和删除

2.4.1 背景顺序表的插入和删除比较费时，他们的平均时间复杂度均为0(n)。 2.4 顺序表的运算——插入和删除

2.4.2 插入实例线性表(4,9,15,28,30,30,42,51,62)，需在第4个元素之前插入一个元素“21”。
2.4 顺序表的运算——插入和删除

2.4.3 插入算法 int InsList(SeqList *L,int i,ElemType e) {
if((i<1) ||(i>L->last+2)) /*首先判断插入位置是否合法*/ 提示出错并退出； if(L->last==maxsize-1) /*判断表是否已满无法插入*/ for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置*/ L->elem[k+1]=L->elem[k]; L->elem[i-1]=e; /*在C语言中数组第i个元素的下标为i-1*/ L->last++; } 2.4 顺序表的运算——插入和删除

2.4.4 插入算法分析表的长度L-＞last+1（设值为n）是问题的规模。移动元素的次数由表长n和插入位置i决定。
算法的时间主要花费在for循环中的元素后移语句上。该语句的执行次数是n-i+1。当i=n+1：移动元素次数为0，即算法最好时间复杂度是0(1)。当i=1：移动元素次数为n，即算法在最坏情况下时间复杂度是0(n)。 2.4 顺序表的运算——插入和删除

2.4.4 插入算法分析移动元素的平均次数为其中pi表示在表中第i个位置上插入一个元素的概率。不失一般性，假设在表中任何合法位置（1≤i≤n+1）上的插入结点的机会是均等的，则 p1=p2=…=pn+1=1/(n+1) 因此，在等概率插入的情况下，移动元素的平均次数为，即平均要移动一半元素（其实不计算也能猜想出这个结果）。所以，插入算法的平均时间复杂度为0(n)。 2.4 顺序表的运算——插入和删除

2.4.5 删除实例将线性表(4,9,15,21,28,30,30,42,51,62)中的第5个元素删除。 2.4 顺序表的运算——插入和删除

2.4.6 删除算法 int DelList(SeqList *L,int i,ElemType * e) {
if((i<1)||(i>L->last+1)) /*首先判断删除位置是否合法*/ 提示出错并退出； if(L->last==-1) /*判断表是否已空无法删除*/ *e=L->elem[i-1]; /*在C语言中数组第i个元素的下标为i-1*/ for(k=i-1;k<L->last;k++) /*为删除元素而移动位置*/ L->elem[k]=L->elem[k+1]; L->last--; } 2.4 顺序表的运算——插入和删除

2.4.7 删除算法分析表的长度L-＞last+1（设值为n）是问题的规模。移动元素的次数由表长n和删除位置i决定。
算法的时间主要花费在for循环中的元素前移语句上。该语句的执行次数是n-i。当i=n：移动元素次数为0，即算法最好时间复杂度是0(1)。当i=1：移动元素次数为n-1，即算法在最坏时间复杂度是0(n)。 2.4 顺序表的运算——插入和删除

2.4.7 删除算法分析移动元素的平均次数为其中pi表示在表中第i个位置上删除一个元素的概率。不失一般性，假设在表中任何合法位置（1≤i≤n）上的删除结点的机会是均等的，则 p1=p2=…=pn+1=1/n 因此，在等概率删除的情况下，移动元素的平均次数为，即平均要移动一半元素（其实不计算也能猜想出这个结果）。所以，删除算法的平均时间复杂度亦为0(n)。 2.4 顺序表的运算——插入和删除

5. 顺序表的运算 ——合并

2.5.1 背景两个顺序表合并，可能是两个无序顺序表的合并，也可能两个有序顺序表的合并。两者的算法不同，时间复杂度也不一样。
有序顺序表的合并实例：有两个顺序表LA（长度为m）和LB（长度为n），其元素均为非递减有序排列，将它们合并成一个顺序表LC，要求LC也是非递减有序排列。 2.5 顺序表的运算——合并

2.5.2 合并算法实例和分析有序顺序表合并算法的（平均、最好、最差）时间复杂度是O(m+n) 。
无序顺序表合并算法的（平均、最好、最差）时间复杂度是O(m)，比如，长度为m的顺序表合并到长度为n的顺序表之后。 2.5 顺序表的运算——合并

2.5.3 有序合并算法 void merge(SeqList *LA,SeqList *LB,SeqList *LC) {
while(i<=LA->last&&j<=LB->last)//当表LA和LB都还没有扫描完 if(LA->elem[i]<=LB->elem[j]) 把LA的元素i插入到LC中 else 把LB的元素j插入到LC中 while(i<=LA->last) //当表LA还没有扫描完将表LA余下的元素赋给表LC while(j<=LB->last) //当表LB还没有扫描完将表LB余下的元素赋给表LC LC->last=LA->last+LB->last+1; } 2.5 顺序表的运算——合并

2.5.4 无序合并算法 SeqList * merge(SeqList *LA,SeqList *LB) {
if(LA->last<LB->last) 交换顺序表指针LA、LB while(j<=LB->last) //当表LB还没有扫描完将表LB余下的元素赋给表LA LA->last=LA->last+LB->last+1; return LA; } 2.5 顺序表的运算——合并

6. 线性表链式存储结构定义

2.6.1 背景顺序结构中，元素是依次存储的，即：在逻辑关系相邻的元素在存储时也是相邻的。因此，顺序结构中各元素的存储位置是有关联的。
这导致的优点是：能随机存取表中元素，也能从任一元素的位置，计算出其他元素的位置。而缺点是：一个元素的插入和删除会影响其他元素的位置移动，而且一般要预先分配空间。 2.6 线性表链式存储结构定义

2.6.1 背景下面将要介绍的链表中，各元素的存储位置没有关系，一个元素的插入和删除不会影响其他元素的位置。
这种情况下，如何知道相邻元素的位置？用指针（pointer），指针中存放了相邻元素的位置，这样就能通过指针找到相邻元素。而且，不需要预先分配空间，可以使用一个元素才分配一个元素的空间。 2.6 线性表链式存储结构定义

2.6.2 链表的定义链式存储结构：一个元素存放在一个结点（Node）中，每个结点包括两个域：数据域用来存储元素；
指针域用来存储直接后继结点的地址（或位置）。采用链式存储结构的线性表称为链表（Linked List）。链表由若干个结点前后链接而成。（说明：也有文献认为只要采用链式存储结构就是链表） 2.6 线性表链式存储结构定义

2.6.2 链表的定义由左图可知，序号在前的元素不一定存放在地址在前的位置上。
我们不关心每个结点的实际位置，可以用箭头来表示链域中的指针，因此，左图的链表就可以表示为更方便的指针图形式（见下图）。 2.6 线性表链式存储结构定义

2.6.3 链表的C语言定义 typedef struct Node / * 结点类型定义 * / { ElemType data；
struct Node * next； }Node, *LinkList；/* LinkList为结构指针类型*/ Node* p; 等价于 LinkList p; 2.6 线性表链式存储结构定义

2.6.3 链表的C语言定义如果定义Node* p; 使用之前先要给它分配空间（因为p只是一个指针）
p=(Node*)malloc(sizeof(Node))；然后使用p->data或p->next,也可以使用（*p）.data或（*p）.next来访问结点中的内容。如果定义Node p; p已经包含了结点空间。因此，可以直接使用p.data或p.next来访问结点中的内容。 2.6 线性表链式存储结构定义

2.6.4 画指针图 2.6 线性表链式存储结构定义

2.6.4 画指针图注意：箭头只能指向结点的外框上，箭头指到结点外框任何位置均可以，表达效果一样，如下所示：
2.6 线性表链式存储结构定义

7. 链表中的头结点

2.7.1 背景链表有有头结点和无头结点之分。为什么要用头结点？ 2.7 链表中的头结点

2.7.2 一些概念表头结点：链表的第一个结点头指针：指向表头结点的指针首元素结点：存储线性表首个元素的结点
头结点：在首元素结点前增加的结点，该结点不存放线性表的数据元素。有时存放表长等附加信息。 2.7 链表中的头结点

2.7.3 头结点的好处若无头结点，线性表中插入或删除首元素结点时，链表的头指针会变化，这导致与插入或删除其他元素的算法不一样；
若有头结点，任何位置的数据元素的插入或删除操作都统一为一种算法，减少了代码量。 2.7 链表中的头结点

2.7.4 有无头结点的比较实例带头结点链表中，删除首元素结点 2.7 链表中的头结点

2.7.4 有无头结点的比较实例无头结点链表中，删除首元素结点 2.7 链表中的头结点

8. 地址传递的函数调用的指针图

2.8.1 背景本节介绍地址传递的函数调用时的指针图。目的在于：熟练指针图的画法体会指针图对于理解程序的好处
彻底理解函数调用中地址传递的含义 2.8 地址传递的函数调用的指针图

2.8.2 实例分析 main() { int a=1, b=3; exchange1(&a, &b);
printf("a=%d,b=%d\n", a, b); exchange2(&a, &b); } 2.8 地址传递的函数调用的指针图

2.8.2 实例分析 void exchange1(int *p1, int *p2) { int temp;
temp=*p1, *p1=*p2, *p2=temp; } void exchange2(int *p1, int *p2) int* p_temp; p_temp=p1, p1=p2, p2=p_temp; 2.8 地址传递的函数调用的指针图

2.8.2 实例分析 main() { int a=1, b=3; exchange1(&a, &b);
exchange1(&a, &b); void exchange1(int *p1, int *p2) 2.8 地址传递的函数调用的指针图

2.8.2 实例分析 void exchange1(int *p1, int *p2) { int temp; temp=*p1；
temp=*p1； *p1=*p2； *p2=temp; //注意a和b中的数据发送了改变 } 2.8 地址传递的函数调用的指针图

2.8.2 实例分析 printf("a=%d,b=%d\n", a, b); exchange2(&a, &b);
void exchange2(int *p1, int *p2) { int* p_temp; p_temp=p1； 2.8 地址传递的函数调用的指针图

2.8.2 实例分析 p1=p2； p2=p_temp; //注意a和b中的数据没有改变 }
p2=p_temp; //注意a和b中的数据没有改变 } printf("a=%d,b=%d\n", a, b); 2.8 地址传递的函数调用的指针图

9. 链表的运算 ——建立链表

2.9.1 背景建立链表有多种方法：始终从头部插入结点（叫头插法）始终从尾部插入结点（叫尾插法）使元素保存有序状态而在合适位置插入
这里考虑前两个方法，第三个方法在后面介绍。 2.9 链表的运算——建立链表

2.9.2 头插法算法思路：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的头结点之后，直至读入结束标志为止。 2.9 链表的运算——建立链表

2.9.2 头插法 Linklist CreateFromHead() { LinkList L; Node *s; int flag=1;
Node *s; int flag=1; L=(Linklist)malloc(sizeof(Node))； L->next=NULL; 2.9 链表的运算——建立链表

2.9.2 头插法 while(flag) //因为flag是1，所以进入循环体执行 { char c=getchar();
//假设用户输入ab$,首先读入‘a’ if(c!=’$’) //‘a’不等于‘$’,因此判断成立 s=(Node*)malloc(sizeof(Node)); s->data=c; 2.9 链表的运算——建立链表

2.9.2 头插法 s->next=L->next; L->next=s; } while(flag)
L->next=s; } while(flag) { //因为flag还是1，继续在循环体内执行 char c=getchar(); //现在读入‘b’ if(c!=’$’) { //‘b’不等于‘$’,因此判断成立 2.9 链表的运算——建立链表

2.9.2 头插法 s=(Node*)malloc(sizeof(Node)); s->data=c;
s->data=c; s->next=L->next; L->next=s; } 2.9 链表的运算——建立链表

2.9.2 头插法 while(flag) //因为flag还是1，继续在循环体内执行 { char c=getchar();
//现在读入‘$’ if(c!=’$’) else //不满足判断，执行else部分 flag=0; } while(flag) //因为flag是0，所以结束循环 return L;//返回结果是： 2.9 链表的运算——建立链表

2.9.3 尾插法 Linklist CreateFromTail() /*将新增的字符追加到链表的末尾*/ { LinkList L;
Node *r, *s; L=(Node *)malloc(sizeof(Node));/*为头结点分配存储空间*/ L->next=NULL; r=L; /*r指针始终动态指向链表的当前表尾*/ c=getchar(); while(c!=’$’)/*输入“$”时flag为0，建表结束*/ 2.9 链表的运算——建立链表

2.9.3 尾插法 s=(Node*)malloc(sizeof(Node)); s->data=c; r->next=s;
r=s; c=getchar(); } r->next=NULL; 2.9 链表的运算——建立链表

10. 链表的运算 ——查找结点

2.10.1 背景两种查找：按元素序号查找，按元素值查找
在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构，而是顺序存取结构。 2.10 链表的运算——查找结点

2.10.2 按元素序号查找 Node * Get(LinkList L, int i) { //假设开始的情况是： Node *p；
Node *p； p=L； j=0； 2.10 链表的运算——查找结点

2.10.2 按元素序号查找 while((p->next!=NULL)&&(j<i)) { //满足条件，因此进入循环体执行
p=p->next； j++； 2.10 链表的运算——查找结点

2.10.2 按元素序号查找 while((p->next!=NULL)&&(j<i))
{ //满足条件，因此继续在循环体中执行 p=p->next； j++； 2.10 链表的运算——查找结点

2.10.2 按元素序号查找 while((p->next!=NULL)&&(j<i))
if（i= =j） else //不满足判断条件，因此执行else部分 return NULL； / * 找不到* / } 2.10 链表的运算——查找结点

2.10.3 按元素值查找 Node *Locate(LinkList L,ElemType key) { Node *p;
p=L->next; / * 从表中第一个结点比较 * / while(p!=NULL) if(p->data!=key) p=p->next; else break; / * 找到结点key，退出循环 * / } return p; 2.10 链表的运算——查找结点

11. 链表的运算——插入或删除结点

背景这里要介绍的是在链表的第i个结点位置（不包括头结点）插入或删除结点。 2.11 链表的运算——插入或删除结点

2.11.2 删除结点算法思路标记待删结点、修改前驱指针、释放结点空间；应先保存(②步)后修改(③步)；若是先③后②，结果会如何？
2.11 链表的运算——插入或删除结点

2.11.2 删除结点 void DelList(LinkList L,int i,ElemType *e) { //假设开始的情况是：
Node *p,*r; p=L; 2.11 链表的运算——插入或删除结点

2.11.2 删除结点 int k =0; while(p->next!=NULL&&k<i-1)
{ //满足条件，因此进入循环体执行 p=p->next; k=k+1; while(p->next!=NULL&&k<i-1) //不满足k<i-1条件，因此跳出循环体 if(k!=i-1) //判断条件不满足，不执行分支部分 2.11 链表的运算——插入或删除结点

2.11.2 删除结点 r=p->next; p->next=p->next->next
p->next=p->next->next *e=r->data; free(r); //r这个变量及值都没有变动，但是不能再使用r指向的那个空间（因为已经释放）。C语言程序中大多量的异常错误，都是因为使用了不该使用的空间。 } 2.11 链表的运算——插入或删除结点

2.11.3 插入结点 void InsList(LinkList L,int i,ElemType e) { Node *pre,*s;
pre=L; int k=0; while(pre!=NULL&&k<i-1) /*先找到第i-1个数据元素的存储位置,使指针pre指向它*/ pre=pre->next; k=k+1; } 2.11 链表的运算——插入或删除结点

2.11.3 插入结点 if(k!=i-1) { printf(“插入位置不合理！”)； return; }
s=(Node*)malloc(sizeof(Node));/*为e申请一个新的结点*/ s->data=e; /*将待插入结点的值e赋给s的数据域*/ s->next=pre->next; pre->next=s; 2.11 链表的运算——插入或删除结点

12. 链表的运算 ——求长度和合并

2.12.1 背景不象顺序表，链接结构中没有用一个变量来记录链表长度，因此长度需要实时来“数”。
两个链表的合并，可能是两个无序链表的合并，也可能两个有序链表的合并。两者的时间复杂度不一样。前者是O(m)（假设n个结点的链表链到m个结点的链表后面，这与顺序表相反），后者是O(m+n)（这与顺序表相同） 2.12 链表的运算——求长度和合并

2.12.2 无序顺序表和链表的合并长度n的顺序表/链表合并到长度为m的顺序表/链表后无序顺序表合并 O(n) 无序链表合并 O(m)
2.12 链表的运算——求长度和合并

2.12.3 求链表的长度 Int ListLength(LinkList L) /*L为带头结点的链表*/ { Node *p;
p=L->next; j=0; /*用来存放链表的长度*/ while(p!=NULL) p=p->next; j++; } return j; 2.12 链表的运算——求长度和合并

2.12.4 有序链表的合并 LinkList MergeLinkList(LinkList LA, LinkList LB) {
Node *pa,*pb; LinkList LC； 2.12 链表的运算——求长度和合并

2.12.4 有序链表的合并 pa=LA->next; pb=LB->next; LC=LA;
LC->next=NULL； r=LC; 2.12 链表的运算——求长度和合并

2.12.4 有序链表的合并 while(pa!=NULL&&pb!=NULL) //满足条件，往下执行 {
if(pa->data<=pb->data)//2大于1，不满足 else r->next=pb; 2.12 链表的运算——求长度和合并

2.12.4 有序链表的合并 r=pb; pb=pb->next; }
while(pa!=NULL&&pb!=NULL)//满足条件，继续执行 { 2.12 链表的运算——求长度和合并

2.12.4 有序链表的合并 if(pa->data<=pb->data)//2小于3，满足 {
r->next=pa; 2.12 链表的运算——求长度和合并

2.12.4 有序链表的合并 r=pa; pa=pa->next;
//到目前为止，LA和LB各有一个元素/结点进入LC。r指针指在LC的末尾。 } 2.12 链表的运算——求长度和合并

2.12.4 有序链表的合并 //当while(pa!=NULL&&pb!=NULL)循环结束，状态如下：
2.12 链表的运算——求长度和合并

2.12.4 有序链表的合并 if(pa) //不满足，执行else else r->next=pb; free(LB);
return(LC); } 2.12 链表的运算——求长度和合并

13. 其他链表—— 循环链表和双向链表

2.13.1 背景从链接方式的角度看，链表可分为单链表、循环链表和双向链表。
循环链表是为了解决用一个指针就能比较方便地在链表头部和尾部操作结点的问题（为了达到同样的方便程度，单链表需要同时用头指针和尾指针两个指针）。双向链表是为了方便找到前驱结点（单链表中无法直接找到前驱结点）。 2.13 其他链表——循环链表和双向链表

2.13.2 循环链表循环链表是一个首尾相接的链表。在单链表中，将终端结点（或称尾结点）的指针域NULL改为指向表头结点即可。
2.13 其他链表——循环链表和双向链表

循环链表循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点。 2.13 其他链表——循环链表和双向链表

2.13.2 循环链表循环链表一般用尾指针，而不用头指针。为什么？尾指针对头部和尾部插入/删除结点都很方便。
头指针对尾部插入/删除结点不方便。如果用头指针，插入/删掉尾部结点时，需要新建一个指针，然后把它一步步移动到尾部，然后才能进行插入/删除操作。 2.13 其他链表——循环链表和双向链表

循环链表的合并操作算法思路 2.13 其他链表——循环链表和双向链表

双向链表在单链表的每个结点里再增加一个指向其直接前驱的指针域prior。我们称之为双(向)链表(Double Linked List)。将头结点和尾结点链接起来，为双（向）循环链表。 2.13 其他链表——循环链表和双向链表

双向链表的操作插入操作删除操作 2.13 其他链表——循环链表和双向链表

14.其他链表 ——静态链表

2.14.1 背景有人说，顺序表和链表的区别之一是：是否连续存放元素。这是错误的，静态链表里面的元素也是连续存放的。
链表可分为动态链表和静态链表。缺省情况下，我们所说的链表是指动态链表。 2.14 其他链表——静态链表

2.14.2 C语言定义 #define Maxsize= 链表可能达到的最大长度 typedef struct {
ElemType data; int next; }Component, StaticList[Maxsize]; int av;//空闲的首结点的下标 Component staticlist[Maxsize]; 等价于 StaticList staticlist； 2.14 其他链表——静态链表

实例 2.14 其他链表——静态链表

15. 链表的综合应用 ——一元多项式的运算

2.15.1 背景一元多项式可按升幂的形式写成： Pn(x) = p0+p1x1+p2x2+…+pnxn，
计算机程序能够很方便地处理数值，但是不方便处理非数值，比如多项式的运算。这时至少有两种方法来解决：一是matlab等仿真工具，二是象本学习点那样用某种数据结构来存储数据，然后运算。可以用一个链表来存放一个多项式，链表中每一个结点存放多项式中每一项的系数和指数。 2.15 链表的综合应用-一元多项式的运算

2.15.2 C语言定义 struct Polynode { int coef;//系数 int exp;//指数
struct Polynode *next; } Polynode , * Polylist; 2.15 链表的综合应用-一元多项式的运算

运算建立一元多项式的链表：通过键盘输入一组多项式的系数和指数，用尾插法建立一元多项式的链表。以输入系数0为结束标志，并约定建立多项式链表时，总是按指数从小到大的顺序排列。两个一元多项式相加：两个多项式中所有指数相同的项的对应系数相加，若和不为零，则构成“和多项式”中的一项；所有指数不相同的项均复抄到“和多项式”中。 2.15 链表的综合应用-一元多项式的运算

2.15.4 建立链表的指针图 Polylist polycreate() { Polynode *head, *rear, *s;
int c,e; rear=head =(Polynode *)malloc(sizeof(Polynode)); 2.15 链表的综合应用-一元多项式的运算

2.15.4 建立链表的指针图 scanf(“%d,%d”,&c,&e);/*键入多项式的系数和指数项*/ //假如用户输入5,17
while(c!=0) /*若c=0，则代表多项式的输入结束*/ { //c!=0满足，因此执行循环体内语句 s=(Polynode*)malloc(sizeof(Polynode));//申请新的结点/ s->coef=c; s->exp=e; 2.15 链表的综合应用-一元多项式的运算

2.15.4 建立链表的指针图 rear->next=s; /*在当前表尾做插入*/ rear=s;
rear=s; scanf(“%d,%d”,&c,&e); //假如用户输入9,8 } 2.15 链表的综合应用-一元多项式的运算

2.15.4 建立链表的指针图 while(c!=0) { //c!=0满足，因此继续执行循环体内语句
s=(Polynode*)malloc(sizeof(Polynode));//申请新的结点 s->coef=c; s->exp=e; rear->next=s; /*在当前表尾插入*/ 2.15 链表的综合应用-一元多项式的运算

2.15.4 建立链表的指针图 rear=s; scanf(“%d,%d”,&c,&e); //假如用户输入0,0 }
scanf(“%d,%d”,&c,&e); //假如用户输入0,0 } while(c!=0) //不满足条件，跳出循环 rear->next=NULL;/*置NULL，以示表结束*/ return(head); 2.15 链表的综合应用-一元多项式的运算

16. 顺序表和链表的比较

背景顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？ 2.16 顺序表和链表的比较

2.16.2 静态和动态顺序表链表静态通常所说的顺序表就是静态顺序表数组第一个元素作为“头结点” 动态
顺序表链表静态通常所说的顺序表就是静态顺序表数组第一个元素作为“头结点” 动态 typedef struct { char *ch; int len; }HString HString *s; 通常所说的链表就是动态链表 2.16 顺序表和链表的比较

2.16.3 优缺点比较（1）顺序表链表优点无需为表示结点间的逻辑关系而增加额外的存储空间；可方便地随机访问表中的任一元素。
顺序表链表优点无需为表示结点间的逻辑关系而增加额外的存储空间；可方便地随机访问表中的任一元素。插入或删除某个元素，不会影响其他元素的位置；存储空间动态分配，存一个元素分配一个结点，节省空间。缺点插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动后面的元素，其效率较低；由于顺序表要求占用连续的存储空间，存储分配只能预先进行分配（而不能需要使用一个元素就分配一个元素的空间）。因此当表长变化较大时，可能会有空间浪费。除了存储数据，也要存储数据的位置；链表中要通过沿着指针逐个移动，才能访问到某个元素。 2.16 顺序表和链表的比较

2.16.3 优缺点比较（2）顺序表链表线性关系如何体现基于相邻存储的先后位置指针是否能随机存取能否时间复杂度
顺序表链表线性关系如何体现基于相邻存储的先后位置指针是否能随机存取能否时间复杂度插入删除差，查找好插入删除好，查找差 2.16 顺序表和链表的比较

如何选择？在下面三种情况之一，我们尽量用顺序表（因为顺序表不仅节省空间而且简单，相比而言，甚至对于编程高手来说，链表的使用也容易出错）没有插入和删除操作插入和删除只在线性表的两头有极少量（只有几个）插入删除操作，且线性表长度较短（比如少于50个） 2.16 顺序表和链表的比较

17. VC++程序的调试

背景调试就是debug（程序除错）。bug本意是臭虫、缺陷、损坏等意思。现在人们将在电脑系统或程序中，隐藏着的一些未被发现的缺陷或问题统称为bug（漏洞）。调试主要指解决逻辑错误（语意错误），而不是语法错误。 2.17 VC++程序的调试

VC++中的调试技术设置断点（breakpoint）。如果你在某一行代码处添加了断点，那么程序运行到断点处即会暂停，不再继续往下运行，直到接到你继续运行的命令单步运行。你每按一下相关按钮，运行一行代码。参看变量。在单步运行中随时了解某个变量的值。在掌握“单步运行”之前，你只能依靠在代码中添加N个printf来输出查看到底是哪里出了问题。这是低效率的。 2.17 VC++程序的调试

调试/Debug工具条在调试运行开始前，工具条如下所示在调试运行开始后，自动弹出以下工具条： 2.17 VC++程序的调试

调试/Debug菜单条调试运行时会自动出现以下的Debug菜单条 2.17 VC++程序的调试

调试实例 2.17 VC++程序的调试

18. VC++程序的异常处理

2.18.1 背景 VC++程序中，经常因为使用无效的指针（地址）而导致出现异常。VC++环境中很容易解决异常问题。

实例 2.18 VC++程序的异常处理

总结

数据结构概论第2章线性表董黎刚浙江工商大学信电学院

Similar presentations

Presentation on theme: "数据结构概论第2章线性表董黎刚浙江工商大学信电学院"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

数据结构概论 第2章 线性表 董黎刚 浙江工商大学信电学院

Similar presentations

Presentation on theme: "数据结构概论 第2章 线性表 董黎刚 浙江工商大学信电学院"— Presentation transcript:

Similar presentations

About project

反馈

数据结构概论第2章线性表董黎刚浙江工商大学信电学院

Presentation on theme: "数据结构概论第2章线性表董黎刚浙江工商大学信电学院"— Presentation transcript: