《DS课件数据结构2章节》由会员分享，可在线阅读，更多相关《DS课件数据结构2章节（47页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表,数据结构,2.1 基本概念和运算,2.1.1 线性表的定义 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，表中相 邻元素之间存在着顺序关系。ai为序号为 i 的数据元素（i=1,2,n）将 ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。就是说：对于ai，当 i=2，.，n 时，有且仅有一个直接前趋 ai-1.，当i=1，2，.，n-1 时， 有且仅有一个直接后继 ai+1，而 a1 是表中第一个元素，它没有前趋，an 是最后一个元素无后继。 通常记为：(a1，a2， ai-1，ai，ai+1，an) 其中n为表长， n0 时称为空表。 2.1
2、.2 线性表的特性： 1. 表中所有元素的性质相同。 2. 数据元素个数可增加或减少，但数据元素必须是连续的，且为 线性关系。,3.数据元素在表中的位置只取决于它自身的序号。 2.1.3 线性表的基本操作 设L=（a1,a2, .ai-1, ai , ai+1, , an ）是一线性表 1.插入:在线性表L的第i个元素之前插入一个新元素; 2.删除:删除线性表L的第i个元素； 3.查找:在L中查找具有某个特征值的数据元素; 另外还有:存取、求长度、排序、复制、合并等。 2.2 顺序表 在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储 顺序反映（表示）出来，所以只需存储数据元素的信息
3、； 假设Loc( a0 ) 为表的第0个元素的存储地址，每个数据元素占用 s 个 存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与 第0个元素的存储位置的关系是： Loc(ai ) = Loc( a0 )+ i s,2.2 顺序表,设线性表的基地址为： Loc(a0 ) , 则 ai 的存储地址为： Loc(ai ) = Loc( a0 )+ i s (1=i=n),2.2 顺序表,线性表的定义为： #define M 1000 /假定线性表的最大长度为1000 typedef struct 或 int vM; elemtype key; /例如 typedef int ele
4、mtype; SqList; node aM; elemtype k; int n;,2.2 顺序表,1. 线性表的插入 线性表的插入运算是指在表的第i(0in)个位置上，插入一个 新元素x，使长度为n的线性表 (a0，a i-1，ai，an-1) 变成长 度为n+1的线性表 (a0，a i-1，x，ai，an),插入操作主要步骤： 1）检测线性表是否有 空间可供插入； 2）将顺序表ai 及之后 的所有元素后移 一个位置； 3）将新元素写入空出 位置，表长+1 ；,2.2 顺序表,/*在顺序表的第 i 个元素前插入新元素 x ，顺序表用一维数组L实现， *p指存放长变量的指针变量。若插入成功则
5、返回1，否则返回0*/ int insertsqlist(int i, int x, int L , int *p) int j,n; n=*p; if (in) return(0); /* 下标从 0 至 n-1 */ else for (j=n; ji; j-) Lj=Lj-1; Lj=x; *p=+n; return(1); ,2.2 顺序表,2. 线性表的删除 线性表的删除运算是指将表的第i(1in)元素删除，使长度 为n的线性表：(a0，a i-1，ai，a i+1，an-1) 变成长度为n-1的 线性表(a0，a i-1，a i+1，an-2),2.2 顺序表,/*在顺序表中删除第
6、 i 个元素，顺序表用一维数组L实现，*p是存放 指向表长变量的指针变量。若删除成功则返回1，否则返回0*/ int delsqlist( int i,int L , int *p) int j,n; n=*p; if (i=n) return(0); else for (j=i+1; jn; j+) Lj-1=Lj; *p=-n; return(1); ,2.3 线性表的链式存储结构,顺序表的优点： 无须为表示节点间的逻辑关系而增加额外的存储空间； 可以方便的随机存取表中的任一节点。 顺序表的缺点： 插入和删除运算不方便； 由于要求占用连续的存储空间，存储分配只能预先进行。 因此，在插入和删
7、除操作是经常性操作的应用场合选用顺序存储结构 不太合适，此时可以选用链式存储结构。 定义：用指针表示数据元素之间关系的存储结构称为链式存储结构。,链式存储结构的特点: 插入、删除灵活方便，不需要移动结点，只要改变结点中指针域的 值即可。 适合于线性表是动态变化的,不进行频繁查找操作、但经常进行插入 删除时使用。 注意：链表的查找只能从头指针开始顺序查找。,2.3 链 表,链表是指用一组任意的存储单元来依次存放线性表的结点，这组存 储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的 任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。 为了能正确表示结点间的逻辑关系，在存储
8、每个结点值的同时，还 必须存储指示其后继结点的地址(或位置)信息，这个信息称为指针(pointer) 或链(link)。这两部分组成了链表中的结点结构：,在单链表中，将终端结点的指针域NULL改为指向头结点，就得到了单链形式的循环链表，并简单称为循环链表。 一、带表头的循环链表和 带表头的循环链表：,空表：,2.3.2 单链表的基本运算,链表结点结构定义： typedef struct Node elemtype data; struct Node *next; LinkList; 节点的申请： p=(LinkList *) malloc(sizeof(LinkList); 节点的释放： fr
9、ee(p);,1. 查找 LinkList *LinkSearch(LinkList *L, elemtype x) /* 在头指针为 L 的带表头结点的单链表中查找数据元素值为 x 结点*/ LinkList *p; p=L-next; while (p!=NULL ,LinkList *LLinkSearch( LinkList *L, elemtype x) /*在以 L 为头指针的带表头结点的循环链表中查找结点 x */ LinkList *p; p=L-next; while ( p!=L) if (p-data=x ) return( p ); else p=p-next; ret
10、urn( NULL ); ,2. 插入, 建立新节点s 向新节点中添入内容x 查找插入点 将新节点链入链中 改变新节点前一节点的指针,插入算法： int Linkinsert(LinkList *L, int i ,elemtype x) /* 在单链表中L中第i个数据元素之前插入一个数据元素x */ LinkList *p=L,*s; int j=0; /*教材中s未说明*/ while(p!=NULL return(1) ,3. 删除,删除算法： void delete(LinkList *L, elemtype x); /* 在以 L 为头指针的单链表中，删除值为 x 的结点 */ Li
11、nkList *p, *q; q=L; p=q-next; while (p!=NULL ,在单链表L中删除第i个数据元素 int LinkDelet(LinkList *L, int i, elemtype *s) LinkList *p=L, *q; int j=0; while(p-next!=NULL ,4. 建立单链表算法 /* 线性表的 n 个数据元素存入一维数组 a 中，建立一个带表头的单 链表，其头指针为 h */ NODE *creat( int a , int n) NODE *s, *h; h=(NODE *)malloc(sizeof(NODE); h-data=0;
12、h-link=NULL; for (i=n; i0; i-) s=(NODE *)malloc(sizeof(NODE); s-data=ai-1; s-link=h-link; h-link=s; h-data+; return(h); ,5. 逆置带表头结点的单链表 /* 所谓逆置，即将单链表所有指针逆转，并使头结点指向原来的尾结 点，原来的首结点作为新的尾结点出 */ void nz(NODE *h) NODE *s, *p; p=h-link; h-link=NULL; while (p!=NULL) s=p; p=p-link; s-link=h-link; h-link=s; ,6
13、. 逆置不带表头结点的单链表 NODE *reverse(NODE *h) NODE *p, *q; if (h!=NULL) p=h-link; h-link=NULL; while (p!=NULL) q=p; p=p-link; q-link=h; h=q; return(h); ,2.5 双 向 链 表,双向链表(Double linked list):在单链表的每个结点里再增加一个指 向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链 故称为双向链表。 一、的结点结构描述：,typedef struct node int data; strct node *llin
14、k, *rlink; DNODE;,二、 带表头的双向链表,在双向循环链表中，若 p 是指向表中任一结点的指针， 则有： p=p-llink-rlink=p-rlink-llink,2.4 限定性线性表及其应用,2.4.1栈 一、 栈的定义 栈：栈是限定仅能在表的一端进行插入、删除操作的线性表。 stack:,说明：设（a1, a2, a3, , an ） 是一个栈 称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当 表中没有元素时称为空栈。 称插入元素为进栈（入栈）、删除元素为出栈（退栈）。 a1称为栈底元素，an为栈顶元素。 栈中元素按a1，a2，a3，an的次 序进栈
15、，出栈的第一个元素应为栈顶元 素。换句话说，栈的修改是按后进先出 的原则进行的。因此，栈称为后进先出 表（LIFO）。,二、栈的存储结构与运算 (一) 顺序栈-栈的顺序存储结构 #define maxnum 100 /* 栈的最大容量 */ typedef struct elemtype stackmaxnum; int top; SqStack; (二) 栈的基本运算 (1) 初始化栈 InitStack(SqStack *s) :初始化操作，设定一个空栈 S 。 void InitStack(SqStack *s) s-top=0; ,(2) 进栈 int push(SqStack *s,elemtype x) :将数据元素x插入顺序栈s 中成为新的栈顶元素。 int push(SqStack *s,elemtype x) if (s-top=maxnum) printf(“Stack overflow!n“); return(0); s-stacks-top=x; s-top+; return(1); ,(3) 出栈 int pop(SqStack *s,elemtype *p) :顺序栈s的栈顶元素退栈， 用 *p 保存其值。 int pop(SqStack *s,elemtype *p) if (s-top=0)
