第二章 线性表 线性表 顺序表 链表 顺序表与链表的比较.

Presentation on theme: "第二章 线性表 线性表 顺序表 链表 顺序表与链表的比较."— Presentation transcript:

1 第二章 线性表 线性表 顺序表 链表 顺序表与链表的比较

2 线性表 其中,ai 是表中数据元素，n 是表长度。
定义： n（0）个数据元素的有限序列，记作（a1, …ai-1, ai, ai+1,…, an） 其中,ai 是表中数据元素，n 是表长度。 特点: 同一线性表中元素具有相同特性。 相邻数据元素之间存在序偶关系。 除第一个元素外，其他每一个元素有一个且仅有一个直接前驱。 除最后一个元素外，其他每一个元素有一个且仅有一个直接后继。

3 两集合合并 void union(List &La,List Lb){
La_len=ListLength(La); Lb_len=ListLength(Lb); for(i=1;i<=Lb_len;i++){ GetElem(Lb,i,e); if(!LocateElem(La,e,equal))ListInsert(La,++La_len,e); }

4 void MergeList(List La,List Lb,List &Lc){
InitList(Lc); i=j=1;k=0; La_len=ListLength(La);Lb_len=ListLength(Lb); while((i<=La_len)&&(j<=Lb_len)){//La和Lb均非空 GetElem(La,i,ai);GetElem(Lb,j,bj); if(ai<=bj) {ListInsert(Lc,++k,ai);++i;} else {ListInsert(Lc,++k,bj);++j;} } while(i<=La_len){ GetElem(La,i++,ai);ListInsert(Lc,++k,ai); while(j<=Lb_len){ GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj); }//MergeList

5 顺序表 定义：将线性表中的元素相继存放在一个连续的存储空间中。 存储结构：数组。 特点：线性表的顺序存储方式。 存取方式：顺序存取
顺序存储结构示意图

6 a a+l … a+(i-1)*l … … … a+(n-1)*l idle
顺序表的存储方式： LOC(a i+1) = LOC( a i )+l LOC(a i) = LOC(a1)+(i-1)*l a1 a2 … a i … … … an … i … … … n a a+l … a+(i-1)*l … … … a+(n-1)*l idle

7 顺序表（SeqList）的类型定义 typedef int ListData; typedef struct {
#define ListSize //最大允许长度 typedef int ListData; typedef struct { ListData * data; //存储空间基址 int length; //当前元素个数 }

8 顺序表基本运算 初始化 void InitList ( SeqList & L ) {
L.data = ( ListData * ) malloc ( ListSize * sizeof ( ListData ) ); if ( L.data == NULL ) { printf ( “存储分配失败!\n” ); exit (1); } L.length = 0;

9 按值查找：找x在表中的位置，若查找成功，返回表项的位置，否则返回-1
int Find ( SeqList &L, ListData x ) { int i = 0; while ( i < L.length && L.data[i] != x ) i++; if ( i < L.length ) return i; else return -1; }

10 int IsIn ( SeqList &L, ListData x )
{ int i = 0, found=0; while ( i < L.length &&!found ) if(L.data[i] != x ) i++; else found=1; return found; }

11 求表的长度 提取函数：在表中提取第 i 个元素的值 return L.length; }
int Length ( SeqList & L ) { return L.length; } 提取函数：在表中提取第 i 个元素的值 ListData GetData ( SeqList &L, int i ) { if ( i >= 0 && i < L.length ) return L.data[i]; else printf ( “参数 i 不合理！\n” );

12 int Next ( SeqList &L, ListData x ) {
int i = Find(x); if ( i >=0 && i < L.length-1 ) return i+1; else return -1; } 寻找x的前驱 if ( i >0 && i < L.length ) return i-1;

13 插入  i 插入 x 50  50 顺序表插入时，平均数据移动次数AMN在各表项 插入概率相等时

14 顺序表的插入 int Insert ( SeqList &L, ListData x, int i ) {
//在表中第 i 个位置插入新元素 x if (i < 0 || i > L.length || L.length == ListSize) return 0; //插入不成功 else { for ( int j = L.length; j > i; j-- ) L.data[j] = L.data[j -1]; L.data[i] = x; L.length++; return 1; //插入成功 }

15 顺序表删除平均数据移动次数AMN在各表项
 16 删除 x  顺序表删除平均数据移动次数AMN在各表项 删除概率相等时

16 顺序表的删除 int Delete ( SeqList &L, ListData x ) { //在表中删除已有元素 x
int i = Find (L, x); //在表中查找 x if ( i >= 0 ) { L.length -- ; for ( int j = i; j < L.length; j++ ) L.data[j] = L.data[j+1]; return 1; //成功删除 } return 0; //表中没有 x

17 顺序表的应用:集合的“并”运算 void Union ( SeqList &A, SeqList &B ) {
int n = Length ( A ); int m = Length ( B ); for ( int i = 0; i < m; i++ ) { int x = GetData ( B, i ); //在B中取一元素 int k = Find (A, x); //在A中查找它 if ( k == -1 ) //若未找到插入它 { Insert ( A, x, n ); n++; } }

18 void Intersection ( SeqList &A, SeqList &B ) {
集合的“交”运算 void Intersection ( SeqList &A, SeqList &B ) { int n = Length ( A ); int m = Length ( B ); int i = 0; while ( i < n ) { int x = GetData ( A, i ); //在A中取一元素 int k = Find ( B, x ); //在B中查找它 if ( k == -1 ) { Delete ( A, i ); n--; } else i++; //未找到在A中删除它 }

19 链表（Linked List） 链表是线性表的链接存储表示 单链表 静态链表 循环链表 双向链表

20 单链表(Singly Linked List)
定义：用一组地址任意的存储单元存放线性表中的数据元素。 存储地址 1 7 13 19 25 31 37 数据域 指针域 ZHANG 13 WANG 1 LI null ZHAO 37 WU 7 ZHOU 19 SUN 25 头指针 31

21 data link 存储结构：链式存储结构 特点：存储单元可以不连续。 存取方式：顺序存取。 单链表结构
每个元素由结点(Node)构成, 它包括两个 域:数据域Data和指针域Link data link Node 存储结构：链式存储结构 特点：存储单元可以不连续。 存取方式：顺序存取。

22 单链表的类型定义 typedef char ListData; typedef struct node { //链表结点
ListData data; //结点数据域 struct node * link; //结点链域 } ListNode; typedef ListNode * LinkList; //链表头指针 LinkList first; //链表头指针

23 newnode->link = first ;
单链表的基本运算 插入（三种情况） 第一种情况：在第一个结点前插入 newnode->link = first ; first = newnode; newnode newnode first first （插入前） （插入后）

24 newnode->link = p->link;
第二种情况：在链表中间插入 newnode->link = p->link; p->link = newnode； newnode newnode p p (插入前) (插入后)

25 newnode->link = p->link;
第三种情况：在链表末尾插入 newnode->link = p->link; p->link = newnode； p newnode newnode  p  (插入前) (插入后)

26 int Insert ( LinkList& first, int x, int i ) {
算法描述 int Insert ( LinkList& first, int x, int i ) { //在链表第 i 个结点处插入新元素 x ListNode * p = first; int k = 0; while ( p != NULL && k < i -1 ) { p = p->link; k++; } //找第 i-1个结点 if ( p == NULL && first != NULL ) { printf ( “无效的插入位置!\n” );//终止插入 return 0; } ListNode * newnode = //创建新结点 (ListNode *) malloc ( sizeof (ListNode) );

27 newnode->data = x; if ( first == NULL || i == 1 ) { //插入空表或非空表第一个结点之前 newnode->link = first;//新结点成为第一个结点 if(first==NULL)last=newnode;//若是空表，表尾指针指向新结点 first = newnode; } else {//插在表中间或末尾 newnode->link = p->link; if(p->link ==NULL)last=newnode; p->link = newnode; return 1;

28 删除 在单链表中删除ai结点 p->link = q->link; q = p->link; 删除前 ai-1 ai+1
 ai-1 ai ai+1 p q 删除后

29 int Delete ( LinkList& first, int i ) { ListNode *p, *q;
if ( i == 0 ) //删除表中第 1 个结点 { q = first; first = first->link; } else { p = first; int k = 0; while ( p != NULL && k < i-1 ) { p = p->link; k++; } //找第 i-1个结点

30 if ( p == NULL || p->link == NULL ) {//找不到第
printf ( “无效的删除位置!\n” ); return 0; } else {//删除中间结点或尾结点元素 q = p->link; p->link = q->link; if (q==last) last=p;//删除表尾结点 k= q->data; free ( q ); return k; //取出被删结点数据并释放q

31 表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的: 简化链表操作的实现。
带表头结点的单链表 表头结点位于表的最前端，本身不带数据，仅标志表头。 设置表头结点的目的: 简化链表操作的实现。 非空表 空表 ^ an a1 first

32 插入 q->link = p->link; p->link = q; 插入前 插入后 first first p p q
^ first p p q q ^

33 插入 p p q q

34 int Insert (LinkList first, ListData x, int i ) {
ListNode * p = Locate ( first, i-1 ); if ( p == NULL ) return 0; //参数i值不合理返回0 ListNode * newnode = //创建新结点 (ListNode *) malloc (sizeof (ListNode) ); newnode->data = x; newnode->link = p->link; //链入 p->link = newnode; return 1; }

35 删除 ^ ^ p q p q q = p->link; p->link = q->link; delete q;
删除前 first first ^ 删除后 first ^ first p q p q (非空表） (空表）

36 int delete ( LinkList first, int i ) { ListNode * p, * q
p = Locate ( first, i-1 ); //寻找第i-1个结点 if ( p == NULL || p->link == NULL) return 0;//i值不合理或空表 q = p->link; p->link = q->link; //删除结点 free ( q ); //释放 return 1; }

37 前插法建立单链表 从一个空表开始，重复读入数据： 生成新结点 将读入数据存放到新结点的数据域中 将该新结点插入到链表的前端
直到读入结束符为止。 first first ^ q q ^

38 LinkList createListF ( void ) {
char ch; ListNode *q; LinkList head = //建立表头结点 (LinkList) malloc (sizeof (ListNode)); head->link = NULL; while ( (ch = getchar( ) ) != ‘\n’ ) { q = (listNode *) malloc (sizeof(ListNode)); q->data = ch; //建立新结点 q->link = head->link; //插入到表前端 head->link = q; } return head;

39 后插法建立单链表 ^ ^ ^ ^ 每次将新结点加在链表的表尾； 尾指针r ,总是指向表中最后一个结点，新结点插在它的后面； first r
q r

40 LinkList createListR ( void ) {
char ch; LinkList head = //建立表头结点 (LinkList) malloc (sizeof (ListNode)); ListNode *q, *r = NULL; while ( (ch = getchar( ) ) != ‘\n’ ) { q = (listNode *) malloc (sizeof(ListNode)); q->data = ch; //建立新结点 r ->link = q; r =q; //插入到表末端 } r ->link = NULL; return head;

41 单链表清空 void makeEmpty ( LinkList first ) { ListNode *q;
//删去链表中除表头结点外的所有其它结点 ListNode *q; while ( first->link != NULL ) {//当链不空时，循环逐个删去所有结点 q = first->link; first->link = q->link; free( q ); //释放 } last=first;

42 计算单链表长度 int Length ( LinkList first ) {
ListNode *p = first->link; //指针 p 指示第一个结点 int count = 0; while ( p != NULL ) { //逐个结点检测 p = p->link; count++; } return count;

43 按值查找 ListNode * Find ( LinkList first, ListData value ) {
ListNode * p = first->link; //指针 p 指示第一个结点 while ( p != NULL && p->data != value ) p = p->link; return p; }

44 ListNode * Locate ( LinkList first, int i ) {
按序号查找（定位） ListNode * Locate ( LinkList first, int i ) { //返回表中第 i 个元素的地址 if ( i < 0 ) return NULL; ListNode * p = first; int k = 0; while ( p != NULL && k < i ) { p = p->link; k++; } //找第 i 个结点 if ( k == i ) return p; //返回第 i 个结点地址 else return NULL; }

45 静态链表 用一维数组描述线性链表 1 2 3 4 5 6 1 ZHANG 2 WANG 3 LI 4 ZHAO 5 WU -1 1 2 3 4 5 6 1 ZHANG 2 WANG 6 LI 5 ZHAO WU -1 CHEN 3 （插入chen,删除zhao)修改后 修改前

46 定义 const int MaxSize = 100; //静态链表大小 typedef int ListData; typedef struct node { //静态链表结点 ListData data; int link; } SNode; typedef struct { //静态链表 SNode Nodes[MaxSize]; int newptr; //当前可分配空间首地址 } SLinkList;

47 链表空间初始化 void InitList ( SLinkList SL ) { SL.Nodes[0].link = 1; SL.newptr = 1; //当前可分配空间从 1 开始 //建立带表头结点的空链表 for ( int i = 1; i < MaxSize-1; i++ ) SL.Nodes[i].link = i+1; //构成空闲链接表 SL.Nodes[MaxSize-1].link = -1; //链表收尾 }

48 在静态链表中查找具有给定值的结点 int Find ( SLinkList SL, ListData x ) { int p = SL.Nodes[0].link; //指针 p 指向链表第一个结点 while ( p != -1 )//逐个查找有给定值的结点 if ( SL.Nodes[p].data != x) p = SL.Nodes[p].link; else break; return p; }

49 在静态链表中查找第 i 个结点 int Locate ( SLinkList SL, int i ) {
if ( i < 0 ) return -1;//参数不合理 int j = 0, p = SL.Nodes[0].link; while ( p != -1 && j < i ) {//循环查找第 i 号结点 p = SL.Nodes[p].link; j++; } if ( i == 0 ) return 0; return p;

50 在静态链表第 i 个结点处插入一个新结点 int Insert ( SLinkList SL, int i, ListData x ) {
int p = Locate ( SL, i-1 ); if ( p == -1 ) return 0; //找不到结点 int q = SL.newptr; //分配结点 SL.newptr = SL.Nodes[SL.newptr].link; SL.Nodes[q].data = x; SL.Nodes[q].link = SL.Nodes[p].link; SL.Nodes[p].link = q; //插入 return 1; }

51 在静态链表中释放第 i 个结点 int Remove ( SLinkList SL, int i ) { int p = Locate ( SL, i-1 ); if ( p == -1 ) return 0; //找不到结点 int q = SL.Nodes[p].link; //第 i 号结点 SL.Nodes[p].link = SL.Nodes[q].link; SL.Nodes[q].link = SL.newptr; //释放 SL.newptr = q; return 1; }

52 循环链表 (Circular List) 带表头结点的循环链表
特点:最后一个结点的 link 指针不为NULL，而是指向头结点。只要已知表中某一结点的地址，就可搜寻所有结点的地址。 存储结构:链式存储结构 带表头结点的循环链表 first a0 a1 an-1 (非空表) first (空表)

53 循环链表的插入

54 约瑟夫问题 用循环链表求解约瑟夫问题 n 个人围成一个圆圈，首先第2个人从1开始一个人一个人顺时针报数, 报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。 例如 n = 8 m = 3

55 约瑟夫问题的解法 #include <iostream.h> #include “CircList.h” void Josephus ( int n, int m ) { for ( int i=0; i<n-1; i++ ) { //执行n-1次 for ( int j=0; j<m-1; j++ ) Next ( ); cout << “Delete person ” << getData ( ) << endl; //数m-1个人 Remove ( ); //删去 }

56 CircList<int> clist; int n, m;
void main ( ) { CircList<int> clist; int n, m; cout << “Enter the Number of Contestants?”; cin >> n >> m; for ( int i=1; i<=n; i++ ) clist.insert (i); //形成约 瑟夫环 clist.Josephus (n, m); //解决约瑟夫问题 }

57 多项式及其相加 在多项式的链表表示中每个结点增加了一个数据成员link，作为链接指针。 优点是： 多项式的项数可以动态地增长，不存在存储溢出问题。 插入、删除方便，不移动元素。

58 多项式链表的相加 AH = x6 + 2x8 +7x14 BH = - x4 + 10x6 - 3x10 + 8x14 +4x18

59 Polynomial operator + ( const Polynomial
& ah, const Polynomial & bh ) { Term *pa, *pb, *pc, *p; ListIterator<Element> Aiter ( ah.poly ); ListIterator<Element> Biter ( bh.poly ); //建立两个多项式对象 Aiter、 Biter pa = pc = Aiter.First ( ); // pa 检测指针 pb = Biter.First ( ); // pb 检测指针 pa = Aiter.Next ( ); pb = Biter.Next( ); // pa, pb 越过表头结点 delete pb;

60 while ( Aiter.NotNull ( ) && Biter.NotNull ( ) )
switch ( compare ( pa→exp, pb→exp ) ) { case '=' : pa→coef = pa→coef + pb→coef; p = pb; pb = Biter.Next ( ); delete p; if ( !pa→coef ) { p = pa; pa = Aiter.Next ( ); delete p; } else { pc→link = pa; pc = pa; pa = Aiter.Next ( ); break;

61 case '<' : pc→next = pb; pc = pb; pb = Biter.Next ( ); break;
pc→next = pa; pc = pa; pa = Aiter.Next ( ); } if ( Aiter.NotNull ( ) ) pc→next = pa; else pc→next = pb;

62 双向链表 (Doubly Linked List)
双向链表结点结构： prior data next 指向直接前驱 指向直接后继 first first 非空表 空表

63 双向循环链表的定义 typedef int ListData; typedef struct dnode { ListNode data;
struct dnode * prior, * next; } DblNode; typedef DblNode * DblList;

64 建立空的双向循环链表 void CreateDblList ( DblList & first ) {
first = ( DblNode * ) malloc ( sizeof ( DblNode ) ); if ( first == NULL ) { print ( “存储分配错!\n” ); exit (1); } first->prior = first->next = first; //表头结点的链指针指向自己 }

65 计算双向循环链表的长度 int Length ( DblList first ) {
//计算带表头结点的双向循环链表的长度 DblNode * p = first->next; int count = 0; while ( p != first ) { p = p->next; count++; } return count; }

66 双向循环链表的插入 (非空表) p p q q->prior = p; q->next = p->next;
p->next = q; q->next->prior = q; 在结点 *p 后插入25 first 31 48 15 p first 31 48 25 15 p q

67 双向循环链表的插入 (空表) q p q->prior = p; q->next = p->next;
p->next = q; q->next->prior = q; 在结点 *p 后插入25 p q first 25

68 int Insert ( DblList first, int i, ListData x ) {
DblNode * p = Locate ( first, i-1 ); //指针定位于插入位置 if ( p == first && i != 1) return 0; DblNode * q = ( DblNode * ) malloc ( sizeof ( DblNode ) ); //分配结点 q->data = x; q->prior = p; p->next->prior = q; //在前驱方向链入新结点 q->next = p->next; p->next = q; //在后继方向链入新结点 return 1; }

69 双向循环链表的删除 p p->next->prior = p->prior;
p->prior->next = p->next; first 31 48 15 p 删除48 first (非空表) 31 15

70 p->next->prior = p->prior; p->prior->next = p->next;
双向循环链表的删除 first 31 p 删除31 p->next->prior = p->prior; p->prior->next = p->next;

71 int Remove ( DblList first, int i ) {
DblNode * p = Locate ( first, i ); //指针定位于删除结点位置 if ( p == first ) return 0; p->next->prior = p->prior; p->prior->next = p->next; //删除结点 p free ( p ); //释放 return 1; }

72 顺序表与链表的比较 基于空间的比较 存储分配的方式 顺序表的存储空间是静态分配的 链表的存储空间是动态分配的

73 顺序表与链表的比较 基于时间的比较 存取方式 顺序表可以随机存取，也可以顺序存取 链表是顺序存取的 插入/删除时移动元素个数
顺序表平均需要移动近一半元素 链表不需要移动元素，只需要修改指针

74 结 束