数据结构笔记——线性表"/>
数据结构笔记——线性表
0. 线性表的基本概念
线性表（List）：零个或多个数据元素的有限序列。
注意线性表首先是一个序列，然后线性表强调是有限的。线性表元素的个数 n ( n ≥ 0 ) n(n\geq0) n(n≥0) 定义为线性表的长度，当 n = 0 n=0 n=0 时称为空表。
线性表的基本操作：
OperationInitList(*L); /* 初始化操作，建立一个空线性表L。*/ListEmpty(L): /* 若线性表L为空，返回ture，否则返回false。*/ClearList(*L); /* 将线性表清空。*/GeiElem(L, i, *e); /* 将线性表L中的第 i 个元素值返回给 e。*/LocateElem(L, e); /* 在线性表中查找元素 e，成功则返回该元素在表中的序号；若失败则返回 0。*/ListInsert(*L, i, e); /* 在线性表 L 中第 i 个元素插入元素 e。*/ListDelete(*L, i, e); /* 删除线性表 L 中第 i 个位置的元素，并用 e 返回其值。*/ListLength(L); /* 返回线性表 L 的元素个数 */
1. 线性表的顺序存储结构
线性表的顺序存储结构，指的是用一段地址连续的存储单元一次存储线性表的数据元素。
线性表的顺序存储的结构代码：
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int*/
typedef struct
{ElemType data[MAXSIZE]; /* 数组，存储数据元素 */int length; /* 线性表当前长度 */
}SqList;
描述顺序存储结构需要三个属性：
- 存储空间的起始位置：数组 data， 它的存储位置就是存储空间的存储位置。
- 线性表的最大存储容量：数组长度 MaxSize。
- 线性表的当前长度：length。
线性表长度和数组长度是不同的概念。
数组长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的。
线性表的长度是线性表中数据元素的个数，随着线性表插入和删除操作的进行，这个量是变化的。
在任意时刻，线性表的长度应该小于等于数组长度。
1.1 顺序存储结构的插入与删除
获得元素操作，实现GetElem操作
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 *//* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */Status GetElem(SqList L, int i, ElemType *e)
{if(L.length==0 || i<1 || i>L.length) return ERROR;*e=L.data[i-1];return OK;
}
插入操作，实现ListInsert操作。
插入算法的思路：
- 如果插入位置不合理，抛出异常；
- 如果线性表长度大于等于数组长度，抛出异常或动态增加容量；
- 从最后一个元素开始向前遍历到第i个位置，分别将他们都往后移动一个位置；
- 将要插入元素填入位置i处；
- 表长加 1。
实现代码如下：
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */Status ListInsert(SqList *L, int i, ElemType e)
{int k;if (L->length == MAXSIZE) /* 顺序线性表已经满 */return ERROR;if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */return ERROR;if (i <= L->length) /* 若插入数据位置不在表尾 */{for(k = L->length-1; k >= i-1; k--) /* 将要插入位置之后的数据元素向后移动一位 */L->data[k+1] = L->data[k];}L->data[i-1] = e; /* 将新元素插入 */L->length++;return OK;
}
删除操作，实现ListDelete操作。
删除算法思路：
- 如果删除位置不合理，抛出异常；
- 取出删除元素；
- 从删除元素为止开始遍历到最后一个元素位置，分别将他们都向前移动一个位置；
- 表长减1。
实现代码如下：
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) *//* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */Status ListDelete(SqList *L, int i, ElemType *e)
{int k;if (L->length == 0) /* 线性表为空 */return ERROR;if (i<1 || i>L->length) /* 删除位置不正确 */return ERROR;*e = L->data[i-1];if (i < L->length) /* 如果删除不是最后位置 */{for(k = i; k<L->length; k++) /* 将删除位置后继元素前移 */L->data[k-1] = L->data[k];}L->length--;return OK;
}
从上面可以看出，线性表的顺序存储结构，在存、读数据时，不管在哪个位置，时间复杂度都是 O(1)；而在插入和删除时，时间复杂度都是 O(n)。这说明，它比较适合元素个数不太变化，而更多是存取数据的应用。
1. 2 线性表顺序存储结构的优缺点
优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间；可以快速地存取表中任意位置的元素。
缺点：删除和插入操作需要移动大量元素；当线性表长度变化较大时，难以确定存储空间容量；造成存储空间的“碎片”。
2. 线性表的链式存储结构
链表包括数据域和指针域，把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。把这两部分组成的数据元素称为结点（Node）。
因为链表的每个结点中只包括一个指针域，所以叫做单链表。我们把链表中第一个结点的存储位置叫做头指针，线性链表的最后一个结点指针为“空”（用NULL或“^”表示）。为了更方便对链表进行操作，通常在单链表的第一个结点前辐射一个结点，称为头结点。
typedef struct Node
{ElemType data;struct Node *next;
}Node;
typedef struct Node *LinkList; /* 定义LinkList */
2.1 单链表的读取
获得链表第i个数据的算法思路：
- 声明一个结点 p 指向链表第一个结点，初始化 j 从1开始；
- 当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加1；
- 若到链表末尾 p 为空，则说明第 i 个元素不存在；
- 否则查找成功，返回结点 p 的数据。
实现代码如下：
/* 初始条件：顺序线性表L已存在，1 ≤ i ≤ ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值 */Status GetElem(LinkList L, int i, ElemType *e)
{int j;LinkList p; /* 声明一结点p */p = L->next; /* 让p指向链表L的第一个结点 */j = 1; /* j为计数器 */while (p && j<i) /* p不为空或者计数器j还没有等于i时，循环继续 */{ p = p->next; /* 让p指向下一个结点 */++j;}if ( !p || j>i )return ERROR; /* 第i个元素不存在 */*e = p->data; /* 取第i个元素的数据 */return OK;
}
2.2 单链表的插入
单链表第 i 个数据插入结点的算法思路：
- 声明一结点 p 指向链表第一结点，初始化 j 从1开始；
- 当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一结点，j 累加 1；
- 若岛链表末尾 p 为空，则说明第i个元素不存在；
- 否则查找成功，在系统中生成一个空结点 s；
- 将数据元素 e 复制给 s->data ；
- 单链表的插入标准语句 s->next = p->next；p->next = s;
- 返回成功。
实现代码算法如下：
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L) */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */Status ListInsert(LinkList *L,int i,ElemType e)
{int j;LinkList p,s;p = *L; j = 1;while (p && j < i) /* 寻找第i个结点 */{p = p->next;++j;}if (!p || j > i)return ERROR; /* 第i个元素不存在 */s = (LinkList)malloc(sizeof(Node)); /* 生成新结点(C语言标准函数) */s->data = e; s->next = p->next; /* 将p的后继结点赋值给s的后继 */p->next = s; /* 将s赋值给p的后继 */return OK;
}
2.3 单链表的删除
单链表第i个数据删除结点的算法思路：
- 声明一结点 p 指向链表第一个结点，初始化 j 从1开始；
- 当 j<i 时，就遍历链表，让 p 的指针向后移动，不断指向下一个结点，j 累加1；
- 若到链表末尾 p 为空，则说明第i个元素不存在；
- 否则查找成功，将欲删除的结点 p->next 赋值给 q；
- 单链表的删除标准语句 p->next = q->next；
- 将 q 结点中的数据赋值给 e，作为返回；
- 释放 q 结点；
- 返回成功。
实现代码如下：
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */Status ListDelete(LinkList *L,int i,ElemType *e)
{int j;LinkList p,q;p = *L;j = 1;while (p->next && j < i) /* 遍历寻找第i个元素 */{p = p->next;++j;}if (!(p->next) || j > i)return ERROR; /* 第i个元素不存在 */q = p->next;p->next = q->next; /* 将q的后继赋值给p的后继 */*e = q->data; /* 将q结点中的数据给e */free(q); /* 让系统回收此结点，释放内存 */return OK;
}
2.4 单链表的整表创建
单链表整表创建的算法思路：
- 生成一结点 p 和计数器变量 i；
- 初始化一空链表 L；
- 让 L的头结点的指针指向 NULL，即建立一个带头结点的单链表；
- 循环：
生成一新结点赋值给 p；
随机生成一数字赋值给 p 的数据域 p->data;
将 p 插入到头结点与前一新结点之间。
实现代码如下：
/* 随机产生n个元素的值，建立带表头结点的单链线性表L（头插法） */void CreateListHead(LinkList *L, int n)
{LinkList p;int i;srand(time(0)); /* 初始化随机数种子 */*L = (LinkList)malloc(sizeof(Node));(*L)->next = NULL; /* 先建立一个带头结点的单链表 */for (i=0; i<n; i++){p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */p->data = rand()%100+1; /* 随机生成100以内的数字 */p->next = (*L)->next; (*L)->next = p; /* 插入到表头 */}
}/* 随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法） */void CreateListTail(LinkList *L, int n)
{LinkList p,r;int i;srand(time(0)); /* 初始化随机数种子 */*L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */r=*L; /* r为指向尾部的结点 */for (i=0; i<n; i++){p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */p->data = rand()%100+1; /* 随机生成100以内的数字 */r->next=p; /* 将表尾终端结点的指针指向新结点 */r = p; /* 将当前的新结点定义为表尾终端结点 */}r->next = NULL; /* 表示当前链表结束 */
}
2.5 单链表的整表删除
单链表整表删除的算法思路如下：
- 声明一结点 p 和 q ；
- 将1第一个结点赋值给 p；
- 循环：
将下一结点赋值给 q；
释放 p；
将 q 赋值给 p。
实现代码如下：
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */Status ClearList(LinkList *L)
{LinkList p,q;p=(*L)->next; /* p指向第一个结点 */while(p) /* 没到表尾 */{q=p->next;free(p);p=q;}(*L)->next=NULL; /* 头结点指针域为空 */return OK;
}
2.6 单链表结构与顺序存储结构的优缺点
3. 静态链表
我们把用数组描述的链表叫做静态链表，为了方便插入数据，通常吧数组建立得大一点，以便有一些空闲空间插入数据而不至于溢出。
/* 线性表的静态链表存储结构 */typedef struct
{ElemType data;int cur; /* 游标(Cursor) ，为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];
让数组的元素都是由两个数据域组成， d a t a data data 和 c u r cur cur。数据域 d a t a data data用于存储要处理的数据，游标 c u r cur cur 相当于单链表的 n e x t next next 指针，存放该元素的后继在数组中的下标。
对数组第一个和最后一个元素做为特殊元素处理，不存数据。通常把未使用的数组元素称为备用链表。第一个元素，即下标为 0 的元素的 cur 存放备用链表的第一个结点的下标；最后一个元素的 cur存放第一个有数值的元素的下标，相当于单链表的头结点的作用。
初始化链表代码：
/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */Status InitList(StaticLinkList space)
{int i;for (i=0; i<MAXSIZE-1; i++) space[i].cur = i+1;space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */return OK;
}
3.1 静态链表的插入操作
辨明数组中哪些分量未被使用，解决方法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。
返回一个下标值的实现代码如下：
/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */int Malloc_SSL(StaticLinkList space)
{int i = space[0].cur; /* 当前数组第一个元素的cur存的值 *//* 就是要返回的第一个备用空闲的下标 */if (space[0]. cur) space[0]. cur = space[i].cur; /* 由于要拿出一个分量来使用了， *//* 所以我们就得把它的下一个 *//* 分量用来做备用 */return i;
}
插入数据元素的代码实现
/* 在L中第i个元素之前插入新的数据元素e */Status ListInsert(StaticLinkList L, int i, ElemType e)
{ int j, k, l; k = MAXSIZE - 1; /* 注意k首先是最后一个元素的下标 */if (i < 1 || i > ListLength(L) + 1) return ERROR; j = Malloc_SSL(L); /* 获得空闲分量的下标 */if (j) { L[j].data = e; /* 将数据赋值给此分量的data */for(l = 1; l <= i - 1; l++) /* 找到第i个元素之前的位置 */k = L[k].cur; L[j].cur = L[k].cur; /* 把第i个元素之前的cur赋值给新元素的cur */L[k].cur = j; /* 把新元素的下标赋值给第i个元素之前元素的ur */return OK; } return ERROR;
}
3.2 静态链表的删除操作
实现代码如下：
/* 删除在L中第i个数据元素 */Status ListDelete(StaticLinkList L, int i)
{int j, k; if (i < 1 || i > ListLength(L)) return ERROR; k = MAXSIZE - 1; for (j = 1; j <= i - 1; j++) k = L[k].cur; j = L[k].cur; L[k].cur = L[j].cur; Free_SSL(L, j); return OK;
}/* 将下标为k的空闲结点回收到备用链表 */void Free_SSL(StaticLinkList space, int k)
{ space[k].cur = space[0].cur; /* 把第一个元素的cur值赋给要删除的分量cur */space[0].cur = k; /* 把要删除的分量下标赋值给第一个元素的cur */
}
更多推荐
数据结构笔记——线性表
发布评论