数据结构线性表

数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构1第2章线性表2.1线性表的逻辑结构2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例

作业2上堂课要点回顾线性结构(包括表、栈、队、数组）的定义和特点：仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。2.线性表逻辑结构：“一对一”或1:1存储结构：顺序、链式运算：修改、插入、删除3.顺序存储特征：逻辑上相邻，物理上也相邻；优点：随机查找快O(1)缺点：插入、删除慢O(n)32.3线性表的链式表示和实现2.3.1链表的表示2.3.2链表的实现2.3.3链表的运算效率分析本节小结作业42.3.1链表的表示链式存储特点与链式存储有关的术语补充：结构数据类型及其C语言表示法5用一组地址任意的存储单元存放线性表中的数据元素，即逻辑上相邻，物理上不一定相邻链式存储特点如何表示ai与ai+1之间的逻辑关系？通过指针来实现结点：链式存储特点：数据域(data)指针域(link)数据元素的映象以“结点的序列”表示线性表

称作链表。指示后继元素存储位置6链表示意图：讨论1：每个存储结点都包含两部分：数据域和

。讨论2：在单链表中，除了首元结点外，任一结点的存储位置由

指示。其直接前驱结点的链域的值指针域(链域)链式存储特点（续）头结点

a1a2…...an^例2-3-1画出26个英文字母表的链式存储结构。解：该字母表的逻辑结构为：（a,b,…,y,z）72.与链式存储有关的术语1）结点2）链表3）单链表、双链表、多链表、循环链表4）头指针、头结点和首元结点a1heada2an……循环链表示意图：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。数据元素的存储映像。由数据域和指针域两部分组成；n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。8何谓头指针、头结点和首元结点？头指针头结点首元结点头结点头指针表尾空指针

a1a2…...an^头指针是指链表中存储线性表第一个数据元素a1的结点。

是指链表中第一个结点的存储地址。单链表可由一个头指针唯一确定。有时为了操作方便，在第一个结点前加一个“头结点”，以指向头结点的指针为链表的头指针；数据域内只放空表标志和表长等信息;9一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例2-3-2答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是3110链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点例2-3-2（续）11答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表。^头指针无头结点^头指针头结点有头结点与链式存储有关的术语（续）12与链式存储有关的术语（续）头结点的数据域可以为空，也可存放线性表长度等附加信息，但此结点不能计入链表长度值。答：讨论4.链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，所以要采用结构数据类型。答：什么是结构类型？如何书写表达？

——补充C语言内容

H头结点的数据域讨论3.头结点的数据域内装的是什么？133.补充结构数据类型及其C语言表示法①类型定义和变量说明可以合写为：typedef

structNode{//Node是自定义结构类型名称chardata;//定义数据域的变量名及其类型structNode*next;//定义指针域的变量名及其类型}LNode,*LinkList;//LNode是结构类型的类型名,

//LinkList是指向LNode结构类型的指针类型的类型名以26个字母的链表为例，每个结点都有两个分量：字符型指针型假设每个结点用变量lNode表示，其中两个分量分别用data和*next表示，则：*nextdatalNode14补充：结构类型的C语言表示法②用LNode或LinkList类型声明指向结点的指针变量：

LNode*p,*q;或LinkListp，q；

③每个结点的分量如何表示？*nextdatalnodep方式1：直接用

lnode.data＝'a'；lnode.next=q方式2：先让指针变量p指向该结点的首地址，然后用：

p->data='a';p->next=q;方式3：先让指针变量p指向该结点的首地址，然后用：

(*p).data='a'；(*p).next＝q15设p为指向链表的第i个元素的指针,则第i个元素的数据域写为

，指针域写为

。p->dataai的值p->nextai+1的地址练习16补充：结构类型的C语言表示法（续）④介绍三个有用的库函数（都在<stdlib.h>中）：sizeof(x)——计算变量x的长度；malloc(m)—开辟m字节长度的地址空间，并返回这段空间的首地址；

free(p)——释放指针p所指变量的存储空间，即彻底删除一个变量。问1：LNode结构类型变量的长度m是多少？问2：结构变量lnode的首地址(指针p）是多少？问3：怎样删除结构变量lnode？只能借助其指针删除！m＝sizeof(LNode)；p＝(LNode*)malloc(m)；或p＝(LinkList)malloc(m)；free(p)；172.3.2链表的实现1.单链表的建立和输出2.单链表的修改3.单链表的插入4.单链表的删除5.应用举例6.其它链表形式181.单链表的建立和输出实例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，…，z），请写出C语言程序。难点分析：每个数据元素在内存中是“零散”存放的，其首地址怎么找？又怎么一一链接？实现思路：先开辟头指针，然后陆续为每个数据元素开辟存储空间并赋值，并及时将地址送给前面的指针。19逆位序输入数据元素的值，建立带头结点的单链表操作步骤：1）建立一个“空表”；2）输入数据元素an，建立结点并插入；3）输入数据元素an-1，

建立结点并插入；ananan-14）依次类推，直至输入a1为止。20顺序输入数据元素的值，建立带头结点的单链表操作步骤：1）建立一个“空表”；2）输入数据元素a1，建立结点并插入；3）输入数据元素a2，

建立结点并插入；a1a1a24）依次类推，直至输入an为止。LLp↑L↑pfpf↑pf↑pf↑↑pfp↑21结点的结构体类型定义#include<stdio.h>#include<stdlib.h>typedef

struct

LNode{chardata;

struct

LNode*next;}LNode，*LinkList;22链表的生成（顺序输入数据元素的值）{inti=26;

LinkListpf,p;

intm=sizeof(LNode);//求每个结点占用的存储空间

head=(LinkList)malloc(m);//为头结点申请空间

head->next=NULL;pf=head;while(i){p=(LNode*)malloc(m);//为新结点开新空间！

p->data=26-i+‘a’;//第一个结点值为字符ap->next=pf->next;pf->next=p;//插入到表尾

pf=p；//移动pf指针到下一位置

i--;}}voidbuild(LinkList&head)23链表的输出voiddisplay(LinkListhead){LinkListp;p=head->next;//p指向首元结点while(p){

printf("%c",p->data);p=p->next;}}讨论：要统计链表中数据元素的个数，该如何改写？sum++;intsum=0;printf("元素个数：%d\n",sum);24voidmain(){

LinkListhead;//头指针head

build(&head);//建立字母链表

display(head);//输出字母链表}252.单链表的修改(或读取）L211830754256∧pppj123取元素操作

GetElem(L,i,&e)

（取单链表L的第i个元素给变量e）*e=p->.data难点：单链表中想取得第i个元素，必须从头指针出发寻找（顺藤摸瓜），不能随机存取。在单链表中的实现为:(例如，i=3)26因此，查找第i个元素的基本操作为：

移动指针，比较j和i

。

指针p始终指向线性表中第j个数据元素，其中j为指针移动的次数计数器。

指针p所指示的结点，有时也称为p结点。程序实现如下：单链表的读取（续）27

StatusGetElem_L(LinkListL,inti,ElemType&e){

//L是带头结点的链表的头指针，以e返回第i个元素

}//GetElem_L算法时间复杂度为:O(ListLength(L))LinkListp=L->next;intj=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;e=p->data;returnOK;j为指针移动的次数计数器顺指针向后查，直到p指向第i个元素或p为空判断第i个元素是否存在获取第i个元素单链表的读取（算法实现）LinkListp=L;int

j=0;

可以吗？自己上机试试（当i=0时）结果对吗？28单链表的读取（算法实现）voidmain(){LinkListhead;//头指针headchare='1';inti;

build(&head);//建立字母链表

display(head);//输出字母链表

printf(“\n输入要读取第几个数据元素:");

scanf("%d",&i);

while(i<1){

printf(“\nI的值必须大于0,请重新输入:");

scanf("%d",&i);}

if(GetElem_L(head,i,&e))

printf("第%d个元素是：%c\n",i,e);else

printf("\n%dislargerthanthelistlength\n",i);}293.单链表的插入在链表中插入一个元素的示意图如下：xsbapabpp->nexts->next在单链表中第i个结点之前进行插入新元素的基本操作为:

找到线性表中第i-1个结点；生成要插入的新元素结点;

修改新结点及第i-1个结点的指针。ii-1ii-1i+130StatusListInsert_L(LinkListL,inti,ElemTypee){LinkLists,p=L;intj=0;

while(p&&j<i-1){p=p->next;++j;}

if(!p||j>i)returnERROR;s=(LinkList)malloc(m);s->data=e;

s->next=p->next;p->next=s；

returnOK;}单链表的插入（算法实现）能互换么？要先找到第i-1个元素i大于表长或者小于1生成新结点LinkList

s,p=L->next;intj=1;思考：可以这样做吗？为什么？不可以，因为当i=1时，插入的新元素放在了原来首元素后面314.单链表的删除在链表中删除某元素的示意图如下：cabp删除步骤（即核心语句）：q=p->next;//保存b的指针，靠它才能指向cp->next=q->next;//a、c两结点相连free(q)；

//删除b结点，彻底释放p->next思考：省略free(q)语句行不行？(q->next)××基本操作为：找到第i-1个存在直接后继的结点修改其指向后继的指针，释放被删元素的空间。q32单链表的删除（算法实现）

StatusListDelete_L(LinkListL,inti,ElemType&e){

//删除以L为头指针(带头结点)的单链表中第i个结点

}//ListDelete_L算法的时间复杂度为:O(ListLength(L))LinkListp=L;intj=0;while(p->next&&j<i-1){p=p->next;++j;}

//寻找第i-1个结点，并令p指向它if(!(p->next)||j>i-1)returnERROR;

//删除位置不合理q=p->next;p->next=q->next;

//删除并释放结点e=q->data;

free(q);returnOK;335.应用举例：两个链表的归并（教材P31）算法要求：已知：线性表A、B，分别由单链表LA,LB存储，其中数据元素按值非递减有序排列。要求：将A，B归并为一个新的线性表C,C的数据元素仍按值非递减排列。设线性表C由单链表LC存储。假设：A=（3，5，8，11），B=（2，6，8，9，11）预测：合并后C=（2,3,5,6,8,8,9,11，11）34两个链表的归并（续）

3

511^

8

La头结点

2

3

6

5

Lc

815

18^

2

611

8

Lb

915

18^用链表可表示为：35两个链表的归并（算法分析）算法主要包括：搜索、比较、插入三个操作：搜索：需要两个指针搜索两个链表；比较：比较结点数据域中数据的大小；插入：将两个结点中数据小的结点插入新链表。36PbPcPaLa3

5

8

11^

Lb2

6

8

119

PaPbPa、Pb用于搜索La和Lb，Pc指向新链表当前结点，新链表不开辟新的存储空间LcPc2

PcPaPbPcPcPcPcPaPcPbPcPbPa3

5

8

6

8

9

15

11

18^11

15

18^Pa->data>Pb->data:Pc->next=Pb;Pb=Pb->next;Pa->data<=Pb->data:Pc->next=Pa;Pa=Pa->next;Pc=Pb;Pa=NULL:Pc=Pa;Pc->next=Pb;若Pb=NULL:Pc->next=?Pa37VoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){//按值排序的单链表LA,LB，归并为LC后也按值排序

free(Lb);//释放Lb的头结点}//MergeList_L

pc->next=pa?pa:pb;//插入剩余段

while(pa&&pb)//将pa、pb结点按大小依次插入C中

{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb