《数据结构 第2章 线性表》由会员分享，可在线阅读，更多相关《数据结构 第2章 线性表（70页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表第二章 线性表教学时间：6学时 教学目的： 1、理解线性表的基本定义和基本操作； 2、了解线性表的逻辑结构特性是数据元素之间存在着 线性关系； 3、掌握线性表的两种存储结构及其基本操作的实现； 4、比较两种存储结构的异同。 教学内容： 线性表的定义、基本运算、线性表的顺序存储、线性 表的链式存储。课题2： 线性表的顺序存储及运算教学时间：2学时 教学目的：掌握线性表的逻辑结构和存储结构。 教学内容：线性表的定义、基本运算、线性表的顺序存储。 教学重点:线性表的概念；线性表的顺序存储结构。 教学难点：线性表的顺序存储结构。 教学方法：讲授,投影演示教学过程:内容： 2.1线性表的类
2、型定义1线性表的基本操作2例2-13例2-2 2.2线性表的顺序表示和实现1线性表的动态分配顺序存储结构2线性表的插入3线性表的删除课题2： 线性表的顺序存储及运算线性表 定义：线性结构中的所有结点按前驱后继关系可以 排成一个线性序列：（k1，k2，k3，k n）这个序列称为线性表。其中，结点个数n称为线性表的长度，长度为零的 线性表称为空表。线性表逻辑结构：线性结构存储结构运算：定位、插入、删除、查找、排序顺序存储：顺序表链接存储：链表例如，英文字母表(A，B，Z)是一个线性表，表中的每个 字母是一个数据元素(结点)；线性表的类型定义ADT List 数据对象：DaiaiElemSet，i1
3、，2，n，n0 数据关系：Rai-1，aiai-1，aiD，i1，2，n 基本操作：InitList（struct sqlistelemtype datamaxsize;int len;k1k2k3 k i-1k ik i+1 k nn0 1 2 3 i-1 i i+1 n maxsize-1 datalenmaxsize -数组的长度； elemtype-线性表的元素类型（假定 整型）； sqlist-顺序表（用结构体类型描述 ）； data -数组，顺序表的存储空间； len-顺序表当前的长度。2.1顺序表 数据的逻辑结构（k1 , k2 , k3 , , k i-1 , k i , k
4、i+1,k n） 顺序存储（用一维数组来实现）define maxsize 100typedef int elemtype;struct sqlistelemtype *data;int len;k1k2k3 k i-1k ik i+1 k nn0 1 2 3 i-1 i i+1 n maxsize-1 datalenvoid InitList_Sq(sqlist L.data=(elemtype*)malloc(maxsize*sizeof(elemtype);L.len = n0; 1.初始化目标：要求用户从键盘输入所要存储的线性表中的n个元素。void Initsqlist(sqlist
5、 L.len=0; for(i=1;iL.datai; L.len+; 2.输出目标:将所要输出的线性表中的n个元素一一输出显示。 void output(sqlist L) int i; if(L.len0) for(i=1;iL.len) | (i= maxsize-1 ) couti;j-) L.dataj+1=L.dataj; L.datai+1=x; L.len+; 4.删除运算 目的:删除线性表中的第i个元素(i1,n) 删除后：逻辑结构： （k1 , k2 , k3 , , k i-1 , k i+1,k n）存储结构：knki1ki-1k3k2k10 1 2 3 i-1 i i
6、+1 n1 n . maxsize-1 datalenn1时间复杂度：T(n)=O(n-1/2)=O(n)4.删除运算void DelSqlist(sqlist if(iL.len)|(ich p-i2.3线性表的链式存储150ch iA.chA.i指向结构的指针：typedef structchar data;struct node *next; node; node *p;pp-data p-next p-next-data p-next-next 指针赋值：q=p; q=p-next; q=p-next-next;动态分配和释放内存空间：new(p) delete(p);p2.3线性表的
7、链接存储线性链表1.线性链表的概念用链接方法存储的线性表称为线性链表，简称链表。 链表一般可分为单向链表和双向链表两种。 2.单向链表(1)定义 每个结点除数值字段外还包含一个指向后 继结点的指针字段，用来存放后继结点的地址的链表 。(2)结点形式 由两个字段组成，如下图所示。数值字段指针字段2.3线性表的链接存储线性链表2.3.1单向链表Hala2a3a4an(3) 单链表的结构：通常，把链表画成用箭头相连接的结点序列 ，结点之间的箭头表示指针字段的值。用一个称 为头指针的变量HEAD存储开始结点（首结点）的 地址，对于一个空的单链表则HEAD的值为空。(al，a2，a3，an)2.3线性表
8、的链接存储线性链表abchead非空单向链表head空表abheadc带表头结点的非空单向链表head空表2.3.1单向链表 线性表（a,b,c)的单向链表存储结构示意图如下： 算法描述： #define NULL 0typedef char elemtype;struct nodeelemtype data;/数值字段node * next;/指针字段;struct node * head;typedef node * LinkList;data nexthead空表建一个空的带头结点的单项链表head=malloc(sizeof(struct node);/head=new node;he
9、ad-next=NULL;1.建表功能：要求用户从键盘输入元素链接在链表的尾部， 输入 #则结束输入。 2.输出F功能：将所要输出的线性表中的n个元素一一输出显示 。3.定位F功能：在链表中查找第i个结点，若存在则返回该结点 的地址，否则返回表头结点的地址。 4.插入F功能：在第i个结点的后面插入一个数值为x的新结点 。5.删除F功能：删除线性表中的第i个结点。链表的基本运算1.建表-尾插法建立单链表(从右边插入结点)图 在尾部插入建立单链表建表算法-尾插法建立单链表(从右边插入结点) node * createllist() node *head,*p,*q; elemtype ch; he
10、ad=new node; head-next=NULL; p=head; cinch; while(ch!=#) q=new node; q-data=ch; q-next=NULL; p-next=q; p=q; cinch; return head; 1.建表 在链表的头部插入结点建立单链表 链表与顺序表不同，它是一种动态管理的存储结构，链表 中的每个结点占用的存储空间不是预先分配，而是运行时 系统根据需求而生成的，因此建立单链表从空表开始，每 读入一个数据元素则申请一个结点，然后插在链表的头部 ，如图 展现了线性表：（29,76,18,45,25）之链表的建 立过程，因为是在链表的头部插
11、入，读入数据的顺序和线 性表中的逻辑顺序是相反的。 图 在头部插入建立单链表2.输出 若需将单链表按逻辑顺序输出，则必须从头到尾访问 单链表中每一个结点2.输出 void output(node *head) node *p; p=head-next; while(p!=NULL) coutdatanext; coutnext; j+; return p; 4.插入 /在第i个结点的后面插入一个新元素x 插入：q=new node; q-data=x;q-next=p-next;p-next=q;pxab插入xq124.插入void insllist(node *head,int i,elem
12、type x) node *p,*q; p=loc(head,i); q=new node; q-data=x; q-next=p-next; p-next=q; 5.删除pcab删除bq删除：q=p-next;p-next=q-next;delete q;void delllist(node *head,int i) node *p,*q; p=loc(head,i-1); q=p-next; p-next=q-next; delete q; 5.删除单链表应用举例 例2.1 已知单链表H，写一算法将其倒置。即实 现如图的操作。(a)为倒置前，(b)为倒置后。 (a)(b)单链表应用举例 算
13、法思路：依次取原链表中的每个结点，将其作为第一个结点插 入到新链表中去，指针p用来指向当前结点，p为空时结束。算 法如下： void reverse (node *head) node *p;p=head-next; /*p指向第一个数据结点*/head-next=NULL; /*将原链表置为空表H*/ while (p!=NULL) q=p; p=p-next;q-next=head-next; /*将当前结点插到头结点的后面*/head-next=q; 算法2.1 该算法只是对链表中顺序扫描一边即完成了倒置，所以时间性 能为O(n)。 单链表应用举例例2.2 已知单链表L，写一算法，删除其
14、重复结点，即 实现如图2.23的操作。(a)为删除前，(b)为删除后。 算法思路： 用指针p指向第一个数据结点，从它的后继结点开始到表 的结束，找与其值相同的结点并删除之；p指向下一个 ；依此类推，p指向最后结点时算法结束。 图 删除重复结点算法如下： void pur_LinkList(node * h) node *p,*q,*r;p=h-next; /*p指向第一个结点*/if(p=NULL) return;while (p-next!=NULL) q=p; while (q-next!=NULL) /* 从*p的后继开始找重复结点*/if (q-next-data=p-data) r=q-next; /*找到重复结点，用r指向，删除*r */q-next=r-next; delete(r); /*if*/else q=q-next; /*while(q-next)*/p=p-next; /*p指向下一个，继续*/ /*while(p-next)*/ 该算法的时间性能为O(n2)。 例2.3 设有两个单链表A、B，其中元素递增有序，编写 算法将A、B归并成一个按元素值递减（允许有相同值 ）有序的链表C，要求用A、B中的原结点形成，不能重 新申请结点。 算法
