数据结构课件 chapter02_线性表.ppt

第二章 线性表线性表是最简单和最常用的 一种数据结构 本章讨论线性表的定义、顺 序存储结构和链式存储结构 重点是线性表两种不同存储 结构下的操作及其相应的算 法第二章 线性表2.1 线性表的概念及其抽象数据类型 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的应用——一元多项式的表示及相加 2.5 顺序表与链表的综合比较（自学） 2.6 总结与提高（复习作业）2.1 线性表的概念及其抽象数据类型v线性表的逻辑结构›线性表的定义›线性表的特点v线性表的抽象数据类型定义线性表的逻辑结构v线性表的定义›线性表是由n（n>=0）个类型相同的数据元素 组成的有限序列，记做 (a1,a2,…ai-1,ai,ai+1,…an)v第一个元素a1无直接前驱v最后一个元素an无直接后继v每个数据元素ai只有一个直接前驱和一个直接后继v数据元素之间具有一对一的关系v线性表的特点线性表的逻辑结构v线性表的定义v线性表的特点›同一性：线性表由同类数据元素组成›有穷性：线性表由有限个数据元素组成v表长度：表中数据元素的个数›有序性：线性表中相邻数据元素之间存在序偶 关系线性表的抽象数据类型定义ADT List{ 数据元素：D={ai|ai∈D0,i=1,2,…n,n>=0,D0为某一数据对象} 结构关系：R={|ai,ai+1∈D0,i=1,2,…n-1}} 基本操作： (1)InitList(L) 操作前提：L为未初始化的线性表 操作结果：将L初始化为空表 (2)DestroyList(L) 操作前提：线性表L已经存在 操作结果：将L销毁 (3)ClearList(L) 操作前提：线性表L已经存在 操作结果：将L置为空表线性表的抽象数据类型定义数据元素：D={ai|ai∈D0,i=1,2,…n,n>=0,D0为某一数据对象} 结构关系：R={|ai,ai+1∈D0,i=1,2,…n-1} 基本操作： (4)EmptyList(L) 操作前提：线性表L已经存在 操作结果：如果L为空表则返回TRUE，否则返回FALSE (5)ListLength(L) 操作前提：线性表L已经存在 操作结果：如果L为空表则返回0，否则返回表中数据元素的个 数 (6)Locate(L,e) 操作前提：线性表L已经存在，e为合法数据元素值 操作结果：如果L中存在数据元素e，则将“当前指针”指向数据 元素e所在位置并返回TRUE，否则返回FALSE线性表的抽象数据类型定义数据元素：D={ai|ai∈D0,i=1,2,…n,n>=0,D0为某一数据对象} 结构关系：R={|ai,ai+1∈D0,i=1,2,…n-1} 基本操作： (7)GetData(L,i) 操作前提：线性表L已经存在，且i值合法 操作结果：返回线性表L中第i个数据元素的值 (8)InsList(L,i,e) 操作前提：线性表L已经存在，e为合法元素值且i值合法 操作结果：在表中第i个位置之前插入新的数据元素e，L的长度 加1 (9)DelList(L,i,e) 操作前提：线性表L已经存在，e为合法元素值且i值合法 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度 减12.2 线性表的顺序存储v线性表的顺序存储结构›顺序表的定义›地址映像的计算公式›线性表顺序存储的表示v线性表顺序存储结构上的基本操作›查找操作›插入操作›删除操作线性表的顺序存储结构v顺序表的定义演示›线性表的顺序存储是指用一组地址连续的存储 单元依次存储线性表中的各个数据元素，采用 顺序存储结构存放的线性表通常称为顺序表。

›顺序表归纳为：关系线性化、结点顺序存v地址映像的计算公式v线性表顺序存储的表示一组连续的存储 单元存放线性表 的数据元素线性表的顺序存储结构v顺序表的定义演示v地址映像的计算公式›假设线性表中有n个元素，每个元素占k个单元 ，第一个元素的地址为loc(a1)，则第i个元素地 址loc(ai)的计算公式： loc(ai)=loc(a1)+(i-1)*kv线性表顺序存储的表示线性表的顺序存储结构v顺序表的定义演示v地址映像的计算公式v线性表顺序存储的表示说明 #define MaxSize 100/*此处的宏定义变量表示线性表的最大长 度*/ typedef struct list{DataType data[MaxSize]; /*存放线性表的数组*/int last; /*线性表最后一个元素的下标，空表为-1*/ }SeqList;思考：last和len有怎样的关系？线性表的顺序存储结构#define MaxSize 100 typedef struct{DataType data[MaxSize]; int last; }SeqList;#define MaxSize 100 typedef struct{DataType data[MaxSize]; int len; }SeqList;(1)结点类型DataType由线 性表中的元素类型确定。

(2)数组下标从0开始计数， 即data[0]存放线性表的 第一个元素a1 (3)len=last+1对顺序表的另一种定义线性表顺序存储结构上的基本操作v建立一个顺序存储的线性表算法 描述›算法实现：将线性表的每个元素依次存储到数 组中(*L).MaxSizea1a2……ai……an01……i-1……n-1a1a2……ai……an线性表顺序存储结构上的基本操作void create(SeqList *L){int i;scanf(“%d“, /*输入线性表的长度*/for(i=0;i=0)return ERROR;}if((*L).last==MaxSize-1){printf(“array is full.\n“);return ERROR;}/*插入位置之后的所有元素 依次后移一位*/for(j=(*L).last;j>=i;j--)(*L).data[j+1]=(*L).data[j ];/*将元素e插入位置i之前*/(*L).data[i]=e;/*线性表表长加1*/(*L).last++;return OK; }线性表顺序存储结构上的基本操作v算法分析 p在表尾插入元素，原有元素不需要移动，直接插入即 可 p在表头插入元素，所有元素（n个）依次后移一位， 然后插入新元素›结论：元素的移动次数和插入位置有关›设Eins为平均移动次数，Pi为在第i个位置之前插入元 素的概率，等概率(Pi=1/(n+1))情况下：线性表顺序存储结构上的基本操作v删除操作›将表的第i个元素删除，使长度为n的线性表变 成长度为n-1的线性表。

›算法思想 n将第i个位置的元素赋值给指定变量 n原表删除位置之后的所有元素依次前移一位 n线性表表长减1›动画演示›算法描述›算法分析线性表顺序存储结构上的基本操作a1a2…aiai+1…an-1an*ea1a2……ai+1…an-1an线性表顺序存储结构上的基本操作#define OK 1 #define ERROR 0 int dellist(SeqList *L, int i, DataType *e){int j;if((i(*L).last)){printf(“delete position is illegal.\n“);return ERROR;}if((*L).last==-1){printf(“array is empty.\n“);return ERROR;} /*将删除位置上的元素传递 给指针变量e*/*e=(*L).data[i-1];/*删除位置之后的所有元素 依次前移一位*/for(j=i;jdata表示p所指结点的数据域èp->next表示p所指结点中的指针域请注意区分结点变量和指向结点的指针变量有关指针的几个基本操作的含义q=p;q=p->next;p=p->next;ppqpqpp单链表上的基本运算v初始化单链表 void initlist(LinkList *L){/*L是指向单链表的头指针*//*malloc是动态分配函数，为头结点分配存储空间*/*L=(LinkList)malloc(sizeof(Node));(*L)->next=NULL; }^L L单链表上的基本运算v建立单链表：头插法建表›算法思想：从一个空表开始，每次读入数据， 生成新结点，将读入数据存放到新结点的数据 域中，然后将新结点插入到当前链表的表头结 点之后，直至读入结束标志为止。

›动画演示›算法描述^H 初始化 的空表a1^ss指向新申请的结点s->data=a1插入第一个结点H a1^a2^sa3^sH a2a1^H a3a2a1^H anan-1…a2a1^s->next=H->next;H->next=s;单链表上的基本运算LinkList CreateFromHead(LinkList H){Node *s;DataType e;int flag=1;H=(LinkList)malloc(sizeof(Node));/*初始化空表*/ H->next=NULL;while(flag){/*用flag标志建表是否结束*/scanf(“%d“,if(e!=0){s=(Node *)malloc(sizeof(Node)); /*为新插入结点分配存储空间*/s->data=e;/*指针s指向新插入的结点*/s->next=H->next;H->next=s;}elseflag=0;}return H; }单链表上的基本运算v建立单链表：尾插法建表›算法思想：从一个空表开始，每次读入数据， 生成新结点，将读入数据存放到新结点的数据 域中，然后将新结点插入到当前单链表的表尾 。

›动画演示›算法描述^H 初始化 的空表a1^ss指向新申请的结点s->data=a1插入第一个结点H a1^a2^s在当前单链表表尾 插入第二个结点 H a1a2^a3^s在当前单链表表尾 插入第三个结点 H a1a2…an-1an^r始终指向单链表的表尾r->next=s;r=s;单链表上的基本运算LinkList CreateFromTail(LinkList H){Node *s,*r; DataType e;int flag=1;H=(LinkList)malloc(sizeof(Node));H->next=NULL;r=H;while(flag){scanf(“%d“,if(e!=0){s=(Node *)malloc(sizeof(Node));s->data=e;r->next=s;r=s;}else{flag=0;r->next=NULL;}}return H; }单链表上的基本运算v查找：按序号查找›算法思想：从单链表的头指针指向的头结点出 发，逐个结点向下搜索，直至所说到第i个结点 为止——顺序访问›动画演示›算法描述Node *p=H;while((p->next!=NULL)j++;}if(i==j) return p;else return NULL; }单链表上的基本运算v查找：按值查找›算法思想：从单链表的头指针指向的头结点出 发，逐个将结点值和给定值e作比较，返回查找 结果。

›动画演示›算法描述p=H->next;while(p!=NULL){if(p->data!=key)p=p->next;elsebreak;}return p; }单链表上的基本运算v求单链表长度操作›算法思想：从结点“头”开始“数(p=L->next)”， 用指针p依次指向各个结点，并附设计数器j计数 ，一直“数”到最后一个结点(p->next==NULL) ，从而得到单链表的长度›动画演示›算法描述L a1a2…an-1an^pp=L->next;j=0;p=p->next;j++;p单链表上的基本运算int ListLength(LinkList L){Node *p=L->next;int j=0;while(p!=NULL){ p=。