循环链表 - 链式存储结构 - 顺序存储结构 - 线性表

内容纲要

线性表的类型定义

线性表的逻辑结构：线性表是一种线性数据结构，数据元素存在一对一的特点。是零个或多个数据元素的有序数列，记为：(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));
    }
}

线性表

线性表的类型定义

顺序存储结构的运算

单链表的运算

双向循环链表的运算

作者

留言

撰写回覆或留言取消回复

线性表

线性表的类型定义

顺序存储结构的运算

单链表的运算

双向循环链表的运算

作者

留言

撰写回覆或留言 取消回复

撰写回覆或留言取消回复