3.1 线性表及逻辑结构 3.2 线性表的顺序存储 3.3 线性表的链式存储 3.4 链式存储结构的应用

Presentation on theme: "3.1 线性表及逻辑结构 3.2 线性表的顺序存储 3.3 线性表的链式存储 3.4 链式存储结构的应用"— Presentation transcript:

1 3.1 线性表及逻辑结构 3.2 线性表的顺序存储 3.3 线性表的链式存储 3.4 链式存储结构的应用
第三章 线性表 3.1 线性表及逻辑结构 3.2 线性表的顺序存储 3.3 线性表的链式存储 3.4 链式存储结构的应用

2 3.1 线性表及逻辑结构 线性表（Linear List）:由n(n>0)个性质相同的数据元素组成的有限序列。线性表的长度即为线性表中元素的个数n(0)，当n＝0时，称该线性表为空表。 线性表举例： 英文字母表：(A, B, C,······, Z) 我国有34个省、市、自治区，组成一个线性表如下： (北京, 天津, 上海,······, 宁夏, 台湾）

3 线性表的有关概念 位序:在一个非空表 (a1 ，a2 ，…，ai，…，an-1 ，an) 中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。 前驱/后继元素：若将线性表记为：(a1, ..., ai-1 , ai , ai+1 , ..., an )，则表中ai-1先于ai，ai先于ai+1，就称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。 注意： 除第一个元素a1元素以外，每一个数据元素有且仅有一个前趋元素， 除最后一个元素以外，每个数据元素有且仅有一 个后继元素。

4 有关线性表运算： 初始化InitList（L）：创建一个空的线性表L。 计数ListLength（L）：求线性表L的长度。
存取GetElem（L,i）：存取第i个数据元素。 插入ListInsert（L，i）：在第i个数据元素之前，插入一个新的数据元素；或在第i个元素后，插入一个新的数据元素。 删除ListDelete（L，i）：删去第i个数据元素。 归并：把两个或两个以上的线性表合并在一起，形成一个新的线性表。

5 分拆：把一个线性表拆成两个或多个线性表。
查找：按某个特定的值查找线性表中的某个元素。 排序：对线性表中的某个元素按某个数据项的值递增（或递减）的顺序进行重新排序。

6 例 3-1 根据实例给出线性表归并的算法 已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC←LA∪LB，且LC中的数据元素仍按值非递减有序排列。设 LA＝（1，5，7，15） LB＝（3，6，8，9，13，15，17） 则 LC＝（1，3，5，6，7，8，9，13，15，15，17）

7 算法思想： 设LC为空表 将LA或LB中的元素逐个插入到LC中即可
具体方法：为使LC中元素按值非递减有序排列，可设两个指针i和j分别指向LA和LB中某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到LC中的元素c为

8 算法3.1 归并算法 Void MergeList（List *La， List *Lb， List *LC） {
算法3.1 归并算法 Void MergeList（List *La， List *Lb， List *LC） { InitList（Lc）； /*构造一个空的线性表Lc*/ i=j=1；k=0； /*指针i和j初始值为1*/ La_len=ListLength（La）； Lb_len=ListLength（Lb）； while（（i<=La_len）＆＆（j＜=Lb_1en） { /* La和Lb均非空*/ GetElem（La，i，ai）； GetElem（Lb，j，bj）； if （ai ＜bj） Listlnsert（Lc，++k，ai）； ++i； } /*将La中的元素插入到表Lc中*/

9 { Listlnsert（Lc，++k，bj）；++i；++j;} { Listlnsert（Lc，++k，bj）；++j;} }
else if (ai = bj ) { Listlnsert（Lc，++k，bj）；++i；++j;} { Listlnsert（Lc，++k，bj）；++j;} } While（i <＝La_len） { /*如果表La没有取完，则将表La中的所剩元素插入到表lc中*/ GetElem（La，i++,ai）； Listlnsert（Lc，++k，ai）； While（j＜＝Lb_len） GetElem（Lb，j++，bj）； Listlnsert（Lc，++k，bj）； }/*MergeList*/ 算法3.1的时间复杂度是O(ListLength(La)+ListLength(Lb))

10 例3-2 利用线性表的基本运算来实现清除线性表LA中多余的重复结点，生成一个新的表LB。如有以下表，LA=(2,3,4,3,5,6,7,4,8,9)存在多余的重复结点，则LB=(2,3,4,5,6,7,8,9)

11 算法思想：从表LA的第一个结点i=1开始，逐个检查结点i以后的位置为k的任一元素，若两点相同，则从表LA中将位置k上数据元素删除掉，当遍历了i后面的所有元素后，i就成为表LA中无重复的结点，然后将i向后移动一个位置。重复上述过程，直到i移到表LA的最后一个元素为止

12 算法实现 ： PURGE（LA）/*清除线性表中重复出现的多余结点*/ List *LA; { int i=1,k,x,y;
int L=lenth(LA); while(i<L) x=get(LA,i);/*取当前第i个结点*/ k=i+1; while(k<=L) y=get(LA,k);/*取当前第k个结点*/

13 算法的时间复杂度：(n-1)+(n-2)+(n-3)+…..+1,即
if(x==y) { Delete(LA,k);/*删除*/ L--; } Else k++; i++; }/*PURGE*/ 算法的时间复杂度：(n-1)+(n-2)+(n-3)+…..+1,即

14 3.2 线性表的顺序存储 3.2.1 顺序存储 数据元素的存储位置：
3.2 线性表的顺序存储 顺序存储 线性表的顺序存储:把线性表的各个数据元素依次存储在一组地址连续的存储单元里 ;用这种方法存储的线性表简称为顺序表 数据元素的存储位置： (1) 第i＋1个数据元素的存储位置LOC（ai+1）和第i个数据元素的存储位置LOC（ai）之间的关系： LOC（ai+1）＝LOC（ai）+m (2) 线性表的第i个数据元素ai的存储位置为：LOC（ai）＝LOC（a1）+(i-1)*m

15 顺序表的特点:表中相邻的元素ai 和ai+1 赋以相邻的存储位置

16 顺序表在C语言的一维数组表示 typedef int datatype；/*定义datatype类型为int*/
#define List_MaxSize 100 /*顺序表的最大长度*/ typedef struct{ datatype data[list_maxsize]; /*将线性表定义为一个数组*/ Int length; /*线性表当前的大小*/ }SqList;

17 3.2.2 顺序结构线性表的运算 表的初始化 求表长 void InitList（SqList *L）
{\\顺序表的初始化即将表的长度设为0 L.Length=0； } 求表长 int ListLength（SqList *L） { \\求表长只需返回L.Length return L.Length;

18 取表中第i个结点 顺序表的结点查询操作 datatype GetNode（L，i） {\\取表中第i个结点只需返回L.data[i-1]即可
if (i<1||i> L.Length-1) Error("position error")； return L.data[i-1]； } 顺序表的结点查询操作 Int search( int x,sqlist *L,int n ) {/*在表长为n 的顺序表中查找结点x在表中的位置*/ int i; for(i=0;i<n;i++) if(x==L.s[i]) break; /*查询到跳出循环*/ return(i+1); /*返回查询结果*/ if(i==n) return(0);

19 顺序表的结点插入操作 ：在线性表的第i-1个数据元素和第i个数据元素之间插入一个新的数据元素，就是要使长度为n的线性表 变成长度为n+1的线性表
例：

20 算法3.6 顺序表插入操作算法 Insert_Sq（SqList *L, int i，int e） {
算法3.6 顺序表插入操作算法 Insert_Sq（SqList *L, int i，int e） { if（i ＜ 1 || i ＞ L. Length) return ERR0R；/* i值不合法*/ if（L.length>list_maxsize-1） return error；/*当前存储空间已满，溢出*/ q = ＆(L.data[i-1])； /*q为插入位置*/ for（p＝＆（L.data[L.length-1]；p＞=q；--p） *(p+1)＝ *p; /*插入位置及之后的元素右移*/ *q＝e； /*插入e*/ ++L.1ength； /*表长增1*/ return OK; } /*Insert_Sq*/ 算法时间复杂度是O(n)

21 顺序表的结点删除操作 删除操作:使长度为n的线性表（a1,…，ai-1 , ai, ,ai+1,…，an ）变成长度为n-1的线性表（a1,…，ai-1 ,ai+1,…，an ） 图示：

22 算法： Delete_Sq（SqList *L，int i ，int ＆e） {
if（(i<1) || i>L.length）） return ERROR；/*i值不合法*/ p＝＆(L.data[i-1])； /*p为被删除元素的位置*/ e＝*p； /*被删除元素的值赋给e*/ q＝L.length-1; /*表尾元素的位置*/ for（++p; p ＜= q；++p） *(p-1)＝ *p； /*被删除元素之后的元素左移*/ --L.length； /*表长减1*/ return e； ｝/*Delete_Sq*/ 事件复杂度O(n)

23 3.2.3 顺序存储结构的特点 优点： 缺点： 无须为表示结点间的逻辑关系而增加额外的存储空间 可以方便地随机存取表中的任一结点
要占用连续的存储空间，并需要静态分配 在插入操作和删除操作时需要移动大量数据

24 3.3 线性表的链式存储 3.3.1 线性链表 线性表的链式存储结构：用一组任意的存储单元来存储线性表的数据元素 结点结构：
3.3 线性表的链式存储 线性链表 线性表的链式存储结构：用一组任意的存储单元来存储线性表的数据元素 结点结构： 数据域（Data Field）：存储数据元素信息的域 指针域(Link Field)：存放直接后继结点或前驱结点地址的域 图示：

25 单链表图示： 事例：

26 结点存储结构： 带头结点的单链表示意图 typedef struct Lnode {/*线性表的单链表存储结构*/
Datatype data; Struct Lnode * next; }LinkList; 带头结点的单链表示意图

27 带头结点单链表初始化算法 建立单链表的算法 Initlist（LinkList *L） {
L = (LinkList*)malloc(sizeof(LNode)); L->next = NULL; } 建立单链表的算法 Create_L（LinkList *L，int n） LinkList*p;int i; initlist（LinkList *L）/*建立一个带头结点的单链表*/ for(i = n;i>0;--i) p = (LinkList*)malloc(sizeof(LNode)); /*生成新结点*/ scanf(&p->data); /*输入元素值*/ p->next =L->next; L->next = p; /*插入到表头*/ } }/* Create_L */

28 单链表的查找操作 单链表的插入操作 单链表的删除操作
3.3.2 线性链表的运算 单链表的查找操作 单链表的插入操作 单链表的删除操作

29 单链表的查找操作 单链表的查找操作算法 VisitElem_L(LinkList *L, int i, Datatype &e ) {
LinkList *p,int j; p = L->next；j=1； While（p！=null ＆＆j<i ） {/*顺指针向后查找，直到p指向第i个元素或p为空*/ p=p->next; ++j; } if（p=null || j>i ） return ERROR； /*第i个元素不存在 */ e＝p-＞data； /*取第i个元素*/ return OK; }/*VisitGetElem_L*/

30 ListNode* LocateNode (LinkList head,DataType key)
按值查找链表 ListNode* LocateNode (LinkList head,DataType key) { ListNode *p=head->next; while(p&&p->data!=key)//直到p为NULL或p->data为key为止 p=p->next; return p; }

31 插入位置： 将结点插入在链表的第一个结点位置 将结点插入在两个结点之间 将结点插入在链表的最后一个结点 插入前后指针变化
单链表的插入操作 插入位置： 将结点插入在链表的第一个结点位置 将结点插入在两个结点之间 将结点插入在链表的最后一个结点 插入前后指针变化

32 单链表的结点前插算法 Insert_Link（LinkList *L，int i, Datatype e） { LinkList*p,*s;
int j; s = (LinkList*)malloc(sizeof(LNode)); /*生成新结点*/ s->data = e; s->next =null; p = L ; j = 0; While(p && j < i-1) p = p->next; ++j; } /*寻找第i-1个结点*/ if(!p||j>i-1) return ERROR; /*i小于1或者大于表长*/ s->next = p->next; p->next = s; return OK; }/*Insert_Link*/

33 单链表的结点后插算法 Insert_Link（LinkList *L，int i, Datatype e） { LinkList*p,*s;
int j; p = L ; j = 0; s = (LinkList*)malloc(sizeof(LNode)); /*生成新结点*/ s->data = e; s->next =null; While(p && j < i) p = p->next; ++j; } /*寻找第i-1个结点*/ if(!p||j>i) return ERROR; /*i小于1或者大于表长*/ s->next = p->next; /*插入L中*/ p->next = s; return OK; }/*Insert_Linnk*/

34 单链表的删除操作 删除前后指针变化：

35 单链表删除算法 Delete_Link（LinkList *L，int i，Datatype ＆e） { Linklist*p,*q;
int j; p = L; j = 0; while(p->next && j<i-1) {/*寻找第i个结点，并令p指向其前趋*/ p = p->next; ++j; } if(!(p->next)||j>i-1) return ERROR; /*删除位置不合理*/ q = p->next; p->next = q->next; /*删除结点*/ e = q->data; free(q); /*释放结点*/ return OK; }/*Delete_Link*/

36 例题：逆序带头结点的单链表 ，使表（a1,…，ai-1 , ai, ,ai+1,…，an ）转换成为（an,…，ai+1 , ai, ,ai-1,…，a1）
算法： void InvertLink(LinkList *Head) { LinkList *P; P = Head->Next; /*P指向原表中第一个待逆置的结点*/ Head->Next = NULL; /*逆表Head初值为空表*/ while (P != NULL) /* 原表中还有未逆置的结点*P */ S = P; P = P->Next; S->Next = Head->Next; Head->Next = S /*将*S 插到逆表Head的头上*/ } } /*InvertLink*/

37 3.3.3 静态链表 实现方法:一维数组 结构 #define StaticTableSize 100 事例：
typedef Struct Slink { Datatype data; Int next; }SlinkTable[StaticTableSize]; 事例：

38 3.3.4 静态链表的运算 静态链表删除操作： DeleteSlinkElement(Slink S,int n) {
静态链表的运算 静态链表删除操作： DeleteSlinkElement(Slink S,int n) { i=S[0].next; //取得静态链表的第一个元素的地址 for (Count=0;Count<=n,Count++) { Pre=i; i=S[i].next;}//在表中查找第n个元素的位置 S[Pre].next=S[i].next; //删除该元素 }

39 静态链表的查找操作 int SearchSL（Slink S，datatype Value） { i=S[0].next;
while (i && S[i].data!=Value) i=S[i].next; return i; }

40 循环链表 :使其最后一个结点的指针指向链表的第一个结点，使链表呈环状，这种形式的线性表叫做循环链表 图示：
循环链表 循环链表 :使其最后一个结点的指针指向链表的第一个结点，使链表呈环状，这种形式的线性表叫做循环链表 图示：

41 结点结构描述： struct Cnode { Int data; struct Cnode *next; }Clinklist;

42 3.3.6 循环链表的运算 循环链表中查找元素为e的结点 VisitElem_L(CLinklist *L, Datatype e ) {
循环链表的运算 循环链表中查找元素为e的结点 VisitElem_L(CLinklist *L, Datatype e ) { Clinklist*p; p = L->next； /*初始化，P指向第一个结点*/ While（p->next!=L ＆＆p->data!=e） p=p->next; if（p->next=L ＆＆p->data!=e） return ERROR； /*元素e不存在 */ Return (p); }/*VisitGetElem_L*/

43 循环链表的合并操作 图示：

44 两个循环链表的链接算法 CLinkList *Connect（CLinklist *rearA，CLinklist *rearB） {
CLinklist *p； p=rearA->next; rearA ->next=rearB->next->next; /*rearB表的第一个结点接在reaA的表尾*/ free(rearB->next); rearB->next=p;/*将链表rearB的第一个结点链接到rearA的最后一个结点之后*/ return rearB;/*返回连接后的循环链表尾指针*/ }/*Connect*/

45 双向链表:每一个结点有两个指针域，一个指针指向其直接前驱结点，另一个指针指向直接后继结点 图示：
双向链表 双向链表:每一个结点有两个指针域，一个指针指向其直接前驱结点，另一个指针指向直接后继结点 图示：

46 结点结构描述 循环双向链表 typedef struct DuLNode {/*线性表的双向链表存储结构*/ DataType data；
Struct DuLNode *priou;/*指向前一结点的指针*/ Struct DuLNode *next; /*指向后一结点的指针*/ }DuLinkList; 循环双向链表

47 3.3.8 双向链表的运算 双向链表的结点删除操作 : 指针变化：
双向链表的运算 双向链表的结点删除操作 : 指针变化： 指针变化：(p-> priou)->next=p->next; (p-> next)-> priou= p-> priou;

48 算法： Delete_DuL（DuLinkList *L，int i，Datatype ＆e） { e = p->data;
p-> priou ->next = p->next; p->next-> priou = p-> priou; /*删除结点*/ free（p）; /*释放空间*/ return e; }/*Delete_DuL*/

49 双向链表的结点插入操作 图示：

50 算法： Insert_DuL(DuLinkList *L,int i,datatype e) {
if(!(s=(DuLlinkList)malloc(sizeof(DuLNode)))) return ERROR; s->data = e; s->next = p->next; p-> next -> priou = s; s->priou = p; p->next = s; return OK; }/*Insert_DuL*/

51 3.3.9 链式存储结构的特点 优点： 缺点： （1）结点空间的动态申请和动态释放，克服了顺序存储结构数据元素最大个数需要预先设定的缺点
链式存储结构的特点 优点： （1）结点空间的动态申请和动态释放，克服了顺序存储结构数据元素最大个数需要预先设定的缺点 （2）链式存储结构中数据元素之间的次序是使用指针来控制的，在插入删除时需要移动大量的数据 缺点： (1)每个结点的指针域需要另外加存储空间 (2)链式存储是一种非随机存储结构，对于任意结点的操作都要首先从开始指针顺链查找该结点，增加了一些操作的算法时间复杂度

52 3.4 链式存储结构的应用 约瑟夫问题 问题描述：设有n个人坐在圆桌周围，从第s个人开始报数，数到m的人出列，然后再从下一个人开始报数，数到m的人又出列，……，如此重复，直到所有的人都出列为止。要求按出列的先后顺序输出每个人的信息 算法： typedef struct Lnode { Datatype data; Struct Lnode * next; }LinkList;

53 void Joseph（int n，int s，int m）
{/*约瑟夫问题*/ int I，j； LinkList *creatlinklist（int）； LinkList *h，* p，*q, *m, *r; if (n<s) return error; h= creatlinklist（int）；/*建立一个带头结点的单链表*/ q=h； for（I=1；I<s;I++）q=q->next;/*找出s结点*/ p=q->next; for(I=1;I<n;I++) { for(j=1;j<m;j++) /*报数，找出数m的结点*/ if(q->next!=null)&& (p->next!=null) q=q->next; p=p->next; }

54 else if (p->next= =null)
{ q=q->next; p=h->next; } else q=h->next; p=p->next; printf(“%c\n”,p->data);/*一个元素出列*/ r=p； if （p->next= =null） p=h->next; q->next=null; p=p->next; if (q->next!=null) q->next=p; else h->next=p; free(r); printf(“%c\n”,(h->next)->data);

55 3.4.2一元多项式求和 多项式：Pn (x) = p0 + p1 xe1+ p2 xe2 + ...+ pn xen 在计算机中的表示
其中，pi（i=1,2,3,n）是系数；ei是相应的指数，且有en>en-1>>e1  0 在计算机中的表示

56 事例：P=13x40+6x30+2x15+4x3+15 Q=10x35-6x30-4x8 运算步骤： 若两项的指数相等，则系数相加
若两项的指数不等，则分别将两项加在结果中

57 运算规则：假设指针qa和qb分别指向多项式A和多项式B中当前进行比较的某个结点，la和lb分别指向qa和qb的前一个结点
（1）指针qa所指结点的指数值 > 指针qb所指结点的指数值，则应取qa指针所指结点插入到“和多项式”链表中去，qa的指针后移 （2）指针qa所指结点的指数值 < 指针qb所指结点的指数值，则应取指针qb所指结点插入到“和多项式”链表中去，qb指针后移 （3）指针qa所指结点的指数值 = 指针qb所指结点的指数值，则将两个结点中的系数相加，若和数不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A的链表中删除相应结点，并释放指针qa和qb所指结点

58 事例： 结果：

59 算法： typedef struct poly { float coef； /*系数*/ int expn； /*指数*/
struct poly *next； /*指针*/ }polynode/**/ Polynode CreatPoly （ polynode *P，int m） po1ynode *r; InitList（P）；/*初始化线性链表P*/ h＝GetHead（P）；/*得到头结点*/ h.coef = 0．0； /*设置头结点的数据元素*/ h.expn = -1； r=p；

60 for（i=1； i＜=m； ++i ） { /*依次输入m个非零项*/ scanf（e.coef，e.expn）； if（LocateElem（p,e）=null） { /*当前链表中不存在该指数项*/ p-> coef =e.coef; p-> expn=e.expn; r->next=p;/*生成结点并插入链表*/ } r->next=p; return（P）； }/*CreatPo1yn*/

61 Ploynode AddPoly(polynode *Pa， polynode *Pb)
{ /*ha和hb分别指向Pa和Pb的头结点*/ ha = GetHead（Pa）； la=ha; hb = GetHead（Pb）； lb=lb; /*qa和qb分别指向Pa和Pb中当前结点*/ qa = la->Next； qb = lb->Next； while(pa!=null＆＆ pb!=null) { /*Pa和Pb均非空，指数比较*/ if (qa->expn > qb->expn) /*多项式Pa中当前结点的指数值小*/ la = qa； qa = qa->Next； }

62 if (qa->expn = qb->expn) /*两者的指数值相等*/
{ sum = qa->coef + qb->coef; if（sum ！＝0．0）） { /*修改多项式Pa中当前结点的系数值*/ qa->coef=sum； la = qa； ｝ else /*系数为0*/ { /*删除多项式Pa中当前结点*/ la->next=qa->next； Free(qa); /*释放空间*/ qa = qa->next； lb->next=qb->next； Free（qb）; /*释放空间*/ qb = qb ->Next； }

63 if (qa->expn < qb->expn)
{/*多项式Pb中当前结点的指数值小*/ lb->next=qb->next； la->Next= qb； qb->next=qa； la=qb; qb=lb->next; } }/*while*/ if（Pb!=null）la->next=qb； /*链接Pb中剩余结点*/ Free（lb）； /*释放Pb的头结点*/ Return（Pa）； }/*addpoly*/

64 3.4.3 在集合方面的应用 应用事例：从终端输入两组数据，分别表示两个集合的元素A和B，要求算出（A-B）U(B-A) 算法：
在集合方面的应用 应用事例：从终端输入两组数据，分别表示两个集合的元素A和B，要求算出（A-B）U(B-A) 算法： int createlink(Slink t) { int head,p,q,item; scanf(“%d”,&item); //输入元素值 p=malloc(s); //用head保留新建链表的链头指针 head=p; s[p].data=item;q=p; while(true) scanf(“%d”,&item); //输入节点值 if (!item) break; //输零结束

65 p=malloc(s); s[p].data=item; s[q].next=p; q=p; } s[q].next=0; reture head; 计算(A-B)U(B-A) int differ(Slink s) { int a,b,p,q,r,tail1,tail2; init(s); //初始化存储栈 a=creatlink(s); //静态链表A建立 b=creatlink(s); //静态链表B建立 p=a;

66 while(s[p].next!=0) p=s[p].next; //遍历A,找tail1 tail1=tail2=p; while(b) { r=b; b=s[b].next; //b为链表b中的后续节点地址 p=a; while(p!=s[tail1].next && s[p].data!=s[r].data) { q=p; p=s[p].next; } if (p==s[tail1].next) s[tail2].next=r; tail2=r; else

67 { if (p= =a) q=a; a=s[a].next; free(s,q); }//释放重复节点所占的空间 else s[q].next=s[p].next ; free(s,p); } free (s,r); s(tail2).next=0; //表尾后续指针置0 return a;