内容纲要

线性表的类型定义

线性表的逻辑结构:线性表是一种线性数据结构,数据元素存在一对一的特点。是零个或多个数据元素的有序数列,记为:(a1,a2,……,an)。其中,a1 是第一个数据元素,也称为起始结点;an 是最后一个数据元素,也称为终端结点;n 为数据元素的个数,也称为表长,当n=0 时称为空表。对于元素ai 而言,ai-1称为ai 的直接前驱,ai+1称为ai 的直接后继。在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成。在这种情况下,常把数据元素称为记录,含有大量记录的线性表又称文件。

逻辑特征:

  1. 若至少含有一个元素,则有唯一的起始元素。
  2. 若至少还有一个元素,则有唯一的尾元素。
  3. 除了起始元素外,其他元素有且只有唯一的前驱元素。
  4. 除了尾元素外,其他元素有且只有唯一的后继元素。

线性表的顺序存储结构: 用一组地址连续的存储单元依次存储线性表的数据元素,是一种随机存储的数据结构。 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));
    }
}
最后修改日期:2020年7月13日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。