第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例.

Presentation on theme: "第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例."— Presentation transcript:

1 第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例

2 2.1. 线性表的逻辑结构及其基本操作 1.线性表的定义： D0为某个数据对象的集合 N为线性表长度
2.1. 线性表的逻辑结构及其基本操作 1.线性表的定义： 线性表是n(n>=0)个相同类型数据元素a0, a1, …，an-1构成的有限序列。 形式化定义： Linearlist = (D, R) 其中： D0为某个数据对象的集合 N为线性表长度

3 2. 线性表的逻辑特征 对一个非空的线性表，有且仅有一个开始结点a1，它没有直接前驱；有且仅有一个终端结点an，它没有直接后继；其它的内部结点ai点都有且仅有一个直接前驱ai-1和直接后继ai+1. 3. 线性表的两个特征 （1）同类性： 每个数据元素ai都必须是相同类型的数据； （2）有序性： 数据元素在表中的位置决定了它的序号.

4 4. 线性表的运算 (1) 置空表：建立一个空表； (2) 存 取：访问线性表的某个元素,使用或改变其值；
(2) 存 取：访问线性表的某个元素,使用或改变其值； (3) 插 入：在第i个位置插入一个同类型的结点； (4) 删 除：删除第i个结点； (5) 求表长：求出线性表中结点的个数； (6) 查 找：在线性表中查找满足某种条件的结点； (7) 合 并：将两个线性表合并成一个线性表； (8) 分 拆：将一个线性表分拆成多个线性表； (9) 排 序：按某数据项的值递增或递减的顺序重新排列； (10)显示，建立，读写盘等.

5 第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例

6 2.2 线性表的顺序存储结构--顺序表 1. 顺序表的定义 用一组地址连续的存储单元依次存放线性表的元素。
顺序存储结构的特点为： )表中逻辑上相邻的结点，存储在相邻的物理位置上；2)可以随机存取表中的元素;3)存储密度大，存储空间利用率高。

7 2. 线性表的地址计算： 设线性表的基地址为LOC(a1), ai的存储地址为：
LOC(ai) = LOC(a1)＋（i－1）*k 1<=i<=n 1 a1 Loc(a1) a1 2 a2 Loc(a1)+k a2 … … i ai Loc(a1)+(i-1)*k ai … … n an Loc(a1)+(n-1)*k an

8 3. 顺序表的类定义 template<class Type>class Array { private:
Type *elements; //数组元素 int ArraySize; //数组元素的个数 int MaxSize; //数组元素的最大个数 BOOL GetArray(); BOOL GetArray(Type *pa); };

9 public: Array(int Size=DefaultSize); Array(Type *pa,int Size=DefaultSize); Array(const Array<Type> &x); ~Array(){ delete []elements; }; Array<Type> & operator = (const Array<Type> &A); Type & operator [] (int i); operator Type * () const { return elements; }; void ClearAll() { ArraySize=0; }; void Init(int size){ ArraySize=size;GetArray(); }; BOOL Delete(int k);//删除第k项 BOOL Insert(int k,Type x);//将数据x插在第k项 int Length() const { return ArraySize; }; int GetMax() const { return MaxSize; };

10 4. 顺序表上的基本运算－插入 template<class Type> BOOL Array<Type>::Insert(int k,Type x) { if(k<0 || k>=ArraySize || ArraySize==MaxSize) return false; for(int i=ArraySize-1;i>=k;i--) elements[i+1]=elements[i]; elements[k]=x; ArraySize++; return true; }

11 4. 顺序表上的基本运算－删除 template<class Type> BOOL Array<Type>::Delete(int k)//删除第k项 { if(k<0 || k>=ArraySize) return false; for(int i=k;i<ArraySize-1;i++) elements[i]=elements[i+1]; ArraySize--; return true; }

12 算法复杂性分析 1、插入 n/2 2、删除 (n-1)/2 3、按序号检索 O(1) 4、按内容检索 (n+1)/2

13 顺序表的优点： 顺序表的缺点: 无须为表示节点间的逻辑关系而增加额外的存储 空间 可以方便的随机存取表中的任一节点 插入和删除运算不方便
无须为表示节点间的逻辑关系而增加额外的存储 空间 可以方便的随机存取表中的任一节点 顺序表的缺点: 插入和删除运算不方便 由于要求占用连续的存储空间，存储分配只能预先进行

14 第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例

15 2.3 线性表的链式存储——单链表 h 不带头节点的链表 h 带头节点的链表

16 单链表结点类的定义：C++ template<class Type> class SListnode {
friend class SList<Type>; private: Type data; SListnode<Type> *next; public: SListnode(){next=NULL;} SListnode(Type data) { this->data=data;next=NULL; } SListnode(const Type &data,SListnode<Type> *next) { this->data=data;this->next=next; } SListnode *nextnode(){return next;} Type Getdata(){ return data; } SListnode<Type> *Getnext(){ return next; } };

17 单链表结点类的定义：C# public class SListNode { public SListNode(int NewData)
data=NewData; next=null; } public int data; public SListNode next;

18 单链表类的定义：C++ template<class Type> class SList// { private:
SListnode<Type> *head; SListnode<Type> *current; };

19 public: SList(); SList(char *fn); void Create(int n,bool InsertInHead); ~SList(); void MakeEmpty(); int Length() const; void SetCurrent(SListnode<Type> *cp) { current=cp; } SListnode<Type> *GetCurrent() { return current; } SListnode<Type> *Getnext() { return current->next; } SListnode<Type> *Gethead(){ return head; } SListnode<Type> *Find(Type value); SListnode<Type> *Getnode(int i);

20 void Insert(Type value,int i);
void Insert(Type value){Insert(value,1);}; void Insert(Type value,bool before); void Remove(Type value); void Delete(int i); void Delete(); Type *Getdata(int i); Type *Current(); Type *First(); Type *Next(); void Modifydata(Type value) {current->data=value;} void Invert()；

21 单链表类的定义：C# public class Slist { private ListNode Head; // 头指针
private ListNode Current; // 当前指针 public Slist() Head=null; Current=null; } void MakeEmpty();//清空单链表 public void Insert(int value, bool before); public void Delete() //删除当前的数据

22 头插法建立单链表 head ④ ③ s ① ② ① 建立新节点 ② 向新节点中添入内容 ③ 使新节点指向链首 ④ 改变头指针

23 头插法建立单链表 linklist *CREATELIST() { char ch; linklist *head,*s;
head＝NULL; ch＝getchar(); while (ch!=‘$’) { s＝malloc(sizeof(linklist)); s->data＝ch; s->next＝head; head＝s; } return(head);

24 尾插法建立单链表 head ③ ④ s ① ② ① 建立新节点 ② 向新节点中添入内容 ③ 将新节点链入链尾 ④ 改变尾指针

25 单个节点的后插操作 p ④ ③ s ① ② ① 建立新节点 ② 向新节点中添入内容 ③ 将新节点链入链中 ④ 改变新节点前一节点的指针

26 单个节点的前插操作 q p ③ ⑤ ④ s ① ② ① 建立新节点 ② 向新节点中添入内容 ③ 查找插入点 ④ 将新节点链入链中
⑤ 改变新节点前一节点的指针

27 改进的前插操作 p a s p p ④ x ⑤ ③ s a ① ②

28 单链表的插入 C++ template<class Type>
void SList<Type>::Insert(Type value,bool before) { if(current==head) before=false; SListnode<Type> *newnode; if(before) SListnode<Type> *p=head; while(p->next!=current) p=p->next; newnode=new SListnode<Type>(value,p->next); p->next=newnode; } else newnode=new SListnode<Type>(value,current->next); current->next=newnode; current=newnode;

29 单链表的插入 C# public void Insert(int value,bool before) {
if(current==head) before=false; SListnode newnode; if(before) SListnode p=head; while(p.next!=current) p=p.next; newnode=new SListnode(value,p.next); p.next=newnode; } else newnode=new SListnode(value,current.next); current.next=newnode; current=newnode;

30 删除后继节点 p ② ① ③ r 存储池

31 删除后继结点 删除运算 DELETEAFTER(linklist *p) { linklist *r; r＝p->next;
p->next＝r->next; free(r); } 删除运算 DELETE(linklist *L,int i) { linklist *p; int j; j＝i-1; p＝GET(L,j); if((p!=NULL)&&(p->next!=NULL)) DELETEAFTER(p); else printf(“error\n”); }

32 循环链表 head rear 非空表 head rear 空表

33 采用尾指针的循环链表 rear

34 两循环链表的链接 ra rb ④ p ① ② ③ 存储池

35 两循环链表的链接 linklist *CONNECT(linklist *ra,linklist *rb) { linklist *p;
p＝ra->next; ra->next＝rb->next->next; free(rb->next); rb->next＝p; return rb; }

36 双链表结点的描述 typedef struct dnode { datatype data; struct dnode *prior,*next; } dlinklist;

37 双链表的前插操作 DINSERTBEFORE(dlinklist *p,datatype x) { dlinklist *s;
s＝malloc(sizeof(dlinklist)); s->data＝x; s->prior＝p->prior; s->next＝p; p->prior->next＝s; p->prior＝s; } p x ⑤ ③ ⑥ ④ s a ① ②

38 双链表的删除操作 DELETENODEp(dlinklist *p) { p->prior->next＝p->next;
p->next->prior＝p->prior; free(p); }

39 第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例

40 静态链表的定义如下： #define maxsize 1024 \\存储池最大容量 typedef int datatype;
typedef int cursor; typedef struct \\结点类型 { datatype data; cursor next; } node; node nodepool[maxsize]; \\存储池 cursor av;

41 初始化可用空间表av INITIALIZE() { int i; for (i=0;i<maxsize-1;i++) nodepool[i].next＝i+1; nodepool[maxsize-1].next＝NULL; av＝1; }

42 data next 1 2 av 3 1 4 … Maxsize-1 Maxsize-1 NULL

43 结点的分配算法 cursor GETNODE() { cursor p; if (av==NULL) p＝NULL; else
{ p＝av; av＝nodepool[av].next; } return p;

44 结点的回收算法 FREENODE(cursor p) { nodepool[p].next＝av; av＝p; }

45 静态链表查找算法 cursor FINDSTLIST(cursor L,int i) { cursor p; int j; p＝L; j＝0; while ((nodepool[p].next!=NULL)&&(j<i)) { p＝nodepool[p].next; j++; } if (i==j) return(p); else return NULL;

46 静态链表插入算法 int INSERTSTLIST(cursor L,datatype x,int i) { cursor p,s; p＝FINDSTLIST(L,i-1); if (p!=NULL) { s＝GETNODE(); if (s==NULL) { printf(“error\n”); return NULL;} else { nodepool[s].data＝x; nodepool[s].next＝nodepool[p].next; nodepool[p].next＝s; return(1); } { printf(“error\n”); retur NULL;}

47 静态链表删除算法 DELETESTLIST(cursor L,int i) { cursor p,q; p＝FINDSTLIST(L,i-1); if ((p!=NULL)&&(nodepool[p].next!=NULL) { q＝nodepool[p].next; nodepool[p].next＝nodepool[q].next; FREENODE(q); } else printf(“error\n”);

48 顺序表与链表的比较 1、基于空间的考虑 2、基于时间的考虑 3、基于语言的考虑

49 第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例

50 应用实例 以单链表存储结构实现线性表的就地逆转 1、全局变量法 2、参数法

51 la p p la q p p la q p p la p p la 单链表的逆转

52 Linklist *la; Void convers1() linklist *p,*q; P = la->next; la->next = NULL; While (p != NULL); { q = p; p = p->next; q->next = la->next; la->next = q; }

53 Void convers2(linklist *la)
linklist *p,*q; P = la->next; La->next = NULL; While (p != NULL); { q = p; p = p->next; q->next = la->next; la->next = q; }

54 例：在一个给定的线性表中删除元素值在x到y之间的所有元素，要求以较高的效率实现
算法思想：先将向量A中所有在x到y之间的元素置成一个特殊的值0，并不立即删除它们，然后从最后向前依次扫描，删除为0的元素，移动后面的元素。

55 void del(A,n,x,y) int A[]; int n,x,y; { int i,k; for (i=1; i<=n; i++) if (A[i]>=x && A[i]<=y) A[i]=0; for (i=n; i>=1; i--) if (A[i]=0) { for (k=i; k<=(n-1); k++) A[k] = A[k+1]; n--; }

56 例：用不多于3n/2的平均比较次数，在一个线性表中找出最大和最小值的元素
void maxmin(A,n) int A[]; int n; { int max, min, i; for (i=2; i<=n; i++) if (A[i] > max) max = A[i]; else if (A[i] < min) min = A[i]; printf(“max = %d, min = %d\n”, max, min); }

57 分析： 最坏情况：元素以递减顺序排列，（A[i]>max）和 (A[i]<min) 均需比较 n-1 次，所以总的比较次数为：2(n-1) 最好情况：元素以递增顺序排列，（A[i]>max）均成立，不须进行 (A[i]<min) 的比较，所以总的比较次数为：(n-1) 平均： (2(n-1)+n-1)/2 = 3n/2 – 3/2

58 例：一元多项式的相加 typedef struct pnode { float coef; //系数 int exp; //指数 struct pnode *next; //指向下一节点 } polynode; coef exp next

59 多项式 2 + 3X + 5X3 + 2X4 可表示为： 多项式 2 + 3X + 5X3 + 2X4 3 + 2X + 4X2 相加 -1
-1 2 3 1 5 3 2 4 多项式 2 + 3X + 5X3 + 2X4 3 + 2X + 4X2 相加

60 算法思想： 初始化； While (两个链都没处理完) { if (指针指向当前节点的指数项相同) {系数相加，在C链中天加新的节点；
A、B链的指针均前移；} else {以指数小的项的系数添入C链中的新节点； 指数小的相应链指针前移；} } While(A链处理完) { 顺序处理B链；} While(B链处理完) { 顺序处理A链；}

61 q1 A -1 2 3 1 5 3 2 4 q2 B -1 3 2 1 4 2 C -1

62 q1 A -1 2 3 1 5 3 2 4 q2 B -1 3 2 1 4 2 C -1 5

63 q1 A -1 2 3 1 5 3 2 4 q2 B -1 3 2 1 4 2 C -1 5 5 1

64 q1 A -1 2 3 1 5 3 2 4 q2 B -1 3 2 1 4 2 C -1 5 5 1 4 2 …………

65 第二章 线性表 1 线性表的逻辑结构及其基本操作 2 线性表的顺序存储结构 3 线性表的链式存储结构 4 静态链表 5 应用实例