线性表的类型定义
线性表的逻辑结构:线性表是一种线性数据结构,数据元素存在一对一的特点。是零个或多个数据元素的有序数列,记为:(a1,a2,……,an)。其中,a1 是第一个数据元素,也称为起始结点;an 是最后一个数据元素,也称为终端结点;n 为数据元素的个数,也称为表长,当n=0 时称为空表。对于元素ai 而言,ai-1称为ai 的直接前驱,ai+1称为ai 的直接后继。在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录,含有大量记录的线性表又称文件。
逻辑特征:
- 若至少含有一个元素,则有唯一的起始元素。
- 若至少还有一个元素,则有唯一的尾元素。
- 除了起始元素外,其他元素有且只有唯一的前驱元素。
- 除了尾元素外,其他元素有且只有唯一的后继元素。
线性表的顺序存储结构: 用一组地址连续的存储单元依次存储线性表的数据元素,是一种随机存储的数据结构。 LOC(i) = LOC(i-1) + l;LOC(ai)=LOC(a1)+(i-1)*l
优点 | 缺点 |
---|---|
无须为表示表中数据元素的关系而增加额外的存储空间(存储空间利用率高) | 插入和删除操作需要移动表中的大量数据元素 |
可以快速存取表中任意数据元素(随机存取) | 当线性表的长度变化较大时,难以确定表中的存储空间的容量 |
造成存储空间的碎片 |
顺序存储结构的运算
- 初始化InitList(L)。其作用是建立一个空表L(即 建立线性表的构架,但不含任何数据元素)。
- 销毁线性表DestroyList(L)。其作用是释放线性表L的内存空间。
- 求线性表的长度ListLength(L)。其作用是返回线性表L的长度。
- 求线性表中第i个元素GetElem(L,i,e)。其作用是线性表L的第i个元素。
- 按值查找LocateElem(L,e)。若L中存在一个或多个值与x相等的元素,则其作用是返回第一个值为x的元素的逻辑序号。
- 插入元素ListInsert(L,i,e)。其作用是在线性表L的第i个位置上增加一个以x为值的新元素
- 删除元素ListDelete(L,i)。其作用是删除线性表L的第i个元素ai。
- 输出元素值DispList(L)。其作用是按前后次序输出线性表L的所有元素值。
代码实现:
#include<stdio.h>
#include <malloc.h>
//-----------线性表的静态分配顺序存储结构------------
#define MaxSize 100
typedef int ElemType; //假设顺序表中所有元素为int类型
typedef struct {
ElemType date[MaxSize]; //存放顺序表中的元素
int length; //顺序表的实际长度
} SqList; //顺序表类型
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int status;
//----------线性表动态分配顺序存储空间结构-------
#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量
#define LIST_INCREMENT 10 //线性表存储空间的分配增量
#define FALSE 0
#define TRUE 1
#define OK 1
#define ERROR 0
typedef int status;
typedef int ElemType; //元素的数据类型
typedef struct {
ElemType* elem; //存储空间基址
int length; //当前长度
int listsize; //当前分配存储容量
} SqList;
//构造一个空线性表
status InitList(SqList& L) {
L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType*));
if (!L.elem)return ERROR;//存储分配失败
L.length = 0;//初始化表长为0
L.listsize = LIST_INIT_SIZE;//初始化存储容量
return OK;
}
//销毁线性表L
status DestoryList(SqList& L) {
free(L.elem);
L.elem = NULL;
L.length = 0;
L.listsize = 0;
return OK;
}
//求线性表的长度
status ListLength(SqList& L) {
return L.length;
}
//用e返回L中的第i个值1<=i<=ListLength(L)
status GetElem(SqList L, int i, ElemType& e) {
if (i < 1 || i>ListLength(L))
return ERROR;
e = *(L.elem + i - 1);
return OK;
}
//查找值等于e的位置i;
int LocateElem(SqList L, ElemType e) {
ElemType* p;
int i = 1; //i的初值为第一个元素的位序
p = L.elem; //p的初值为第一个元素的存储地址
while (i <= L.length && (*p++ != e))
++i;
if (i <= L.length)
return i;
else
return 0;
}
//插入算法Insert平均时间复杂度O(n),表尾插入为最好情况O(1)
status ListInsert(SqList& L, int i, ElemType e) {
//i的合法值1<=i<=L.length+1
ElemType* p;
if (i < 1 || i > L.length + 1)
return ERROR;
if (L.length >= L.listsize) {
ElemType* newbase = (ElemType*)realloc(L.elem, (L.listsize + LIST_INCREMENT) * sizeof(ElemType));
if (!newbase)
return ERROR; //存储分配失败
L.elem = newbase; //新基址
L.listsize += LIST_INCREMENT; //增加存储容量
}
ElemType* q = L.elem+ i - 1;//q为插入位置
for (p = L.elem+L.length - 1; p >= q; --p)
*(p + 1) = *p; //插入位置之后元素右移
*q = e; //插入e
++L.length; //表增长1
return OK;
}
//删除算法Delete,平均时间复杂度为O(n),表尾删除不移动为最好情况O(1)
status ListDelete(SqList& L, int i, ElemType& e) {
//i的合法值1<=i<=L.length
ElemType* p, * q;
if (i < 1 || i > L.length)
return ERROR;
p = L.elem + i - 1;//被删除位置
e = *p;//被删除元素赋值给e
q = L.elem + L.length - 1;//表尾元素的值
for (++p; p <= q; ++p)
*(p - 1) = *p; //被删除元素之后的元素左移
--L.length;//表长减一
return OK;
}
//输出线性表
void DispList(SqList L) {
int i = 1;
for (int i = 1; i <= L.length; i++)
printf(%d , *(L.elem++));
printf(\n表长:%d\t表容量:%d, L.length, L.listsize);
}
线性表的链式存储结构:n 个结点链结成一个链表,即为线性表(a1,a2,…an)的链式存储结构。结点由数据域和指针域构成。
数据域:存储数据元素信息的为数据域(data)。
指针域:存储直接后继存储位置(指针)的域为指针域或链域(next)。
单链表: 链表的每个结点只包含一个指针域。有带头结点和不带头结点两种,带头结点的可以简化运算的实现过程。
头指针:指向链表中头结点的存储位置。 头结点数据可以存储任何信息,也可不存储。
特征:
- 每个数据元素由结点(Node)构成
- 线性结构
- 结点可以连续,也可以不连续存储。
- 结点的逻辑顺序与物理顺序可以不一致。
- 表可以扩充。
- 链表中的第一个元素结点称为首结点;最后一个元素结点称为尾结点;其指针域为空(NULL);
带头结点单链表图示:
单链表的运算
- 初始化单链表算法InitList(LinkList &L):构造一个空的线性表L
- 销毁单链表算法DestroyList(LinkList &L):销毁线性表L
- 求单链表长度算法ListLength(LinkList L):返回L中数据元素个数
- 求单链表中值为e的元素算法LocateElem(LinkList L, ElemType e):返回L中第1个与e相等的数据元素的位序。
- 单链表的插入算法ListInsert_L(LinkList &L, int i, ElemType e):在带头结点的单链线性表L的第i个元素之前插入元素e
- 单链表的删除算法ListDelete_L(LinkList &L, int i, ElemType &e):在带头结点的单链线性表L中,删除第i个元素,并由e返回其值
- 显示单链表DispList(LinkList L)
代码实现:
#include<stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
//单链表结点的C语言描述
typedef struct node {
ElemType data;
struct node* next;
}LNode,*LinkList;
Status InitList(LinkList& L)
{
L = (LinkList)malloc(sizeof(LNode));//产生头结点使L指向头结点地址
if (!L) return ERROR;//分配失败
L->next = NULL;//指针域为空
return OK;
}
Status Destory(LinkList& L)
{
LinkList p;
while (L){
p = L->next;
free(L);
L = p;
}
return OK;
}
int ListLength(LinkList L)
{
int i = 0;
LinkList p = L->next;//将p指向第一个结点
while (p){
i++;
p = p->next;
}
return i;
}
int LocateElem(LinkList L, ElemType e)
{
int i = 0;
LinkList p = L->next;
while (p){
i++;
if (p->data == e)
return i;//找到元素直接return
p = p->next;
}
return 0;
}
Status ListInsert_L(LinkList& L, int i, ElemType e)
{
LinkList p, s;
p = L;
int j = 0;
while (p &&j < i-1){//找到第i-1个元素
p = p->next;
++j;
}
if (j > i - 1 || !p)
return ERROR;//i小于1或大于表长
s = (LinkList)malloc(sizeof(LNode));//生成新结点
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
Status ListDelete_L(LinkList& L, int i, ElemType& e)
{
LinkList p, q;
p = L;
int j = 0;
while (p && j < i - 1) {//找到第i-1个结点
p = p->next;
++j;
}
if (!(p->next) || j > i - 1)
return ERROR;//删除位置不合理
q = p->next;
p->next = q->next;//删除并释放结点
e = q->data;
free(q);
return OK;
}
void DispList(LinkList L)
{
LinkList p = L->next;
int i;
if (p != NULL) {
printf(\n头结点的地址为:%p\n, L);
for (i = 1; p != NULL; i++) {
printf(第%d个结点的值为%d,地址为%p\n, i, p->data, p);
p = p->next;
}
}
}
静态链表:用数组描述的链表。
优点 | 缺点 |
---|---|
在插入和删除操作时,只需要移动游标,不需要移动元素。 | 没有解决连续存储分配带来的表长难以确定问题。 |
改进了在顺序存储结构中需要移动大量元素的缺点。 | 失去了顺序存储结构随机存取的特性 |
循环链表:是另一种形式的链式存储结构,特点是表中最后一个结点的指针域指向头结点。循环链表的操作和线性链表基本一致,差别仅在于算法中的循环条件不是p 或p->next 是否为空,而是它们是否等于头指针。
循环链表为空表:L->next == L
表尾: p->next == L
双向链表:在前趋和后继方向都能遍历的线性链表。双向链表每个结点的结构由指向其前驱结点的指针域prior,指向其后继结点的指针域next,数据域data构成。
特性:p->prior->next == p == p->next->prior
双向循环链表的运算
- 初始化双向循环链表InitDuLinkList(DuLinkList &L)
- 销毁双向循环链表Destory(DuLinkList& L)
- 双向循环链表长度算法ListLength(DuLinkList L)
- 在L中确定第i个元素前驱的位置指针p:GetElemP(L, i – 1);
- 求单链表中值为e的元素算法LocateElem(DuLinkList L, ElemType e):返回L中第1个与e相等的数据元素的位序。
- 双向循环链表插入算法ListInsert(DuLinkList& L, int i, ElemType e)
- 双向循环链表删除算法ListDelete(DuLinkList L, int i, ElemType &e)
- 打印双向循环链表DispDuLinkList(DuLinkList L)
代码实现:
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef int Status;
#define OK 1
#define ERROR 0
//双向链表结点的C语言描述
typedef struct DuLNode {
ElemType data;
struct DuLNode* piror, * next;
}DuLNode, * DuLinkList;
Status InitDuLinkList(DuLinkList& L)
{
L = (DuLinkList)malloc(sizeof(DuLNode));
if (!L)
return ERROR;//分配失败
L->next = L;
L->piror = L;
return OK;
}
Status Destory(DuLinkList& L)
{
DuLinkList p;
L->piror->next = NULL;//先断链在释放
while (L) {
p = L->next;
free(L);
L = p;
}
return OK;
}
int ListLength(DuLinkList L)
{
int i = 0;
DuLinkList p = L->next;//p指向第一个结点
while (p != L) {//p没到表头
i++;
p = p->next;
}
return i;
}
DuLinkList GetElemP(DuLinkList L, int i)
{
int j = 0;
DuLinkList p = L->next;
while (p != L) {
++j;
if (i == j)
return p;
p = p->next;
}
return L;//空双向链表
}
int LocateElem(DuLinkList L, ElemType e)
{
DuLinkList p = L->next;//指向第一个结点
int i = 0;
while (p != L) {
++i;
if (p->data == e)
return i;//找到元素直接return i
p = p->next;
}
return 0;
}
Status ListInsert(DuLinkList& L, int i, ElemType e)
{
if (i < 1 || i > ListLength(L) + 1)//1<=i<=ListLength(L)+1
return ERROR;
DuLinkList p, s;
p = GetElemP(L, i - 1);//找到第i-1个元素
if (!p)
return ERROR;//没有找到指针P
s = (DuLinkList)malloc(sizeof(DuLNode));
if (!s) return ERROR;//分配失败
s->data = e;
s->next = p->next;
p->next->piror = s;
s->piror = p;
p->next = s;
return OK;
}
Status ListDelete(DuLinkList L, int i, ElemType& e)
{
if (i < 1 || i > ListLength(L))
return ERROR;//i的合法值1<=i<=ListLength(L)
DuLinkList p;
p = GetElemP(L, i);
e = p->data;
if (!p)
return ERROR;//查找失败
p->next->piror = p->piror;
p->piror->next = p->next;
free(p);
return OK;
}
void DispLinkList(DuLinkList L)
{
DuLinkList p = L->next;
int i = 1;
if (p != NULL) {
printf(头指针的地址为%p\n, L);
for (i = 1; p != L; i++) {
printf(当前地址%p的第%d个元素的前驱地址为:%p,数据为%d,后驱地址为%p\n, p, i, p->piror, p->data, p->next);
p = p->next;
}
printf(双向循环表长为%d\n, ListLength(L));
}
}
留言