数据结构（2）—— 线性表链表

文章目录

1. 什么是线性表？2. 线性表的抽象数据类型描述2.1 线性表的顺序存储实现主要操作的实现 2.2 线性表的链式存储实现主要操作的实现 2.3 广义表（Generalized List）2.4 多重链表

同一个问题可以有不同的表示（存储）方法有一个共性问题：有序线性序列的组织和管理

1. 什么是线性表？

线性表（Linear List）：由同类型数据元素构成有序序列的线性结构

表中元素个数称为线性表的长度线性表没有元素时，称为空表表起始位置称为表头，表结束位置称表尾

2. 线性表的抽象数据类型描述

类型名称：线性表（List）数据对象集：线性表是n（≥0）个元素构成的有序序列（a1，a2，……，an）操作集：线性表L∈List，整数i表示位置，元素X∈ElementType List MakeEmpty()：初始化一个空线性表LElementType FindKth(int K,List L)：根据位序K，返回相应元素int Find(ElementType X,List L)：在线性表L中查找X的第一次出现位置void Insert(ElementType X,int i,List L)：在位序i前插入一个新元素Xvoid Delete(int i,List L)：删除指定位序i的元素int Length(List L)：返回线性表L的长度n

2.1 线性表的顺序存储实现

利用数组的连续存储空间顺序存放线性表的各元素

typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; int Last; }; struct LNode L; List PtrL;

访问下标为i的元素：L.Data[i]或PtrL->Data[i] 线性表的长度：L.Last+1或PtrL->Last+1

主要操作的实现

1.初始化（建立空的顺序表）

List MakeEmpty() { List PtrL; PtrL = (List)malloc(sizeof(struct LNode)); PtrL->Last = -1; return PtrL; }

2.查找

int Find(ElementType X,List PtrL) { int i=0; while(i<=PtrL->Last && PtrL->Data[i]!=X) i++; if(i > PtrL->Last) return -1; /*如果没找到，返回-1*/ else return i; /*找到后返回的是存储位置*/ }

查找成功的平均比较次数为(n+1)/2，平均时间性能为O(n)

3.插入（第i个位置上插入一个值为X的新元素）

void Insert(ElementType X,int i,List PtrL) { int j; if(PtrL->Last == MAXSIZE -1) /*表空间已满，不能插入*/ { printf("表满"); return; } if(i<1 || i>PtrL->Last+2) /*检查插入位置的合法性*/ { printf("位置不合法"); return; } for(j=PtrL->Last;j>=i-1;j--) PtrL->Data[j+1] = PtrL->Data[j]; /*将ai~an倒序向后移动*/ PtrL->Data[i-1] = X; /*新元素插入*/ PtrL->Last++; /*Last仍指向最后元素*/ return; }

平均移动次数为n/2，平均时间性能为O(n)

4.删除（删除表的第i个位置上的元素）

void Delete(int i,List PtrL) { int j; if(i<1 || i>PtrL->List+1) { printf("不存在第%d个元素",&i); return; } for(j=i;j<=PtrL->Last;j++) PtrL->Data[j-1] = PtrL->Data[j]; /*将ai+1~an顺序向前移动*/ PtrL->Last--; /*Last仍指向最后元素*/ return; }

2.2 线性表的链式存储实现

不要求逻辑上相邻两个元素物理上也相邻；通过“链”建立起数据元素之间的逻辑关系。插入、删除不需要移动数据元素，只需要修改“链”。

typedef struct LNode *List; struct LNode { ElementType Data; List Next; }; struct LNode L; List PtrL;

主要操作的实现

1.求表长

int Length(List PtrL) { List p = PtrL; /* p指向表的第一个结点 */ int j=0; while(p) { p = p->Next; j++; /*当前p指向的是第j个结点*/ } return j; }

时间性能为O(n)

2.查找 （1）按序号查找：FindKth

List FindKth(int K,List PtrL) { List p = PtrL; int i=1; while(p!=NULL && i<K) { p = p->Next; i++; } if(i==K) return p; /*找到第K个，返回指针*/ else return NULL; /*否则返回空*/ }

（2）按值查找：Find

List Find(ElementType X,List PtrL) { List p=PtrL; while(p!=NULL && p->Data != X) p = p->Next; return p; }

时间性能为O(n)

3.插入（在第i-1个结点后插入一个值为X的新结点）

List Insert(ElementType X,int i,List PtrL) { List p,s; if(i==1) /* 新结点插入在表头 */ { s=(List)malloc(sizeof(struct LNode)); /* 申请、装填结点 */ s->Data = X; s->Next = PtrL; return s; /* 返回新表头指针 */ } p = FindKth(i-1,PtrL); /* 查找第i-1个结点 */ if(p==NULL) /* 第i-1个不存在，不能插入 */ { printf("参数i错误"); return NULL; } else { s = (List)malloc(sizeof(struct LNode)); /* 申请、装填结点 */ s->Data = X; s->Next = p->Next; /* 新结点插入在第i-1个结点的后面 */ p->Next = s; return PtrL; } }

4.删除（删除链表第i个位置上的结点）

List Delete(int i ,List PtrL) { List p,s; if(i==1) /* 如果要删除第一个结点 */ { s = PtrL; /* s指向第1个结点 */ if(PtrL!=NULL) PtrL = PtrL->Next; /* 从链表中删除 */ else return NULL; free(s) /* 释放被删除的结点 */ return PtrL; } }

2.3 广义表（Generalized List）

广义表是线性表的推广对于线性表而言，n个元素都是基本单元素广义表中，这些元素不仅可以是单元素也可以是另一个广义表

typedef struct GNode *GList; struct GNode { int Tag; /* 标志域：0表示结点是单元素，1表示结点是广义表 */ union{ /* 子表指针域Sublist与单元素数据域Data复用，即共用存储空间 */ ElementType Data; GList SubList; }URegion; GList Next; /* 指向后续结点 */ }

2.4 多重链表

多重链表：链表中的结点可能同时隶属于多个链

多重链表中结点的指针域会有多个，如前面例子包含了Next和SubList两个指针域；但包含两个指针域的链表并不一定是多重链表，比如双向链表不是多重链表

多重链表有广泛的用途：基本上如树、图这样相对复杂的数据结构都可以采用多重链表方式实现存储。

---

浙江大学陈越、何钦铭老师的《数据结构》学习笔记