数据结构:线性表

线性表

线性表(List):零个或多个数据元素的有限序列。

首先它是一个序列。也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。

然后,线性表强调是有限的。

顺序表与单链表是线性表的两种最基本的存储结构,而静态链表是两者的完美结合,是系统进行动态存储分配的方法基础。线性表的这三种存储结构不但是其他数据结构(如树形结构、图型结构、集合等)存储方法的重要基础,同时本身也有广泛的应用。

线性表应该有以下基本的操作

  • InitList 初始化
  • ListEmpty 判空
  • ClearList 清空
  • GetElem 返回线性表第i个位置的元素
  • ListInsert 在线性表第i个位置插入元素
  • ListDelete 删除线性表的第i个位置的元素
  • ListLength 返回线性表的元素个数

顺序存储结构

可能有人第一次见线性表的顺序存储结构的时候,不禁怀疑:“这不就数组吗?这样定义好麻烦啊。有啥用啊?”

确实,在一些小体量的程序时,这样定义使用很麻烦,不如直接用数组。

但是这样封装起来后,程序就会很规范,虽然代码看上去很臃肿。


另外要实现的功能:

  • 对于已排好序的线性表,删除所有重复元素的算法。
  • 线性表“逆置”算法。
  • 线性表循环左移/右移 k 位的算法。
  • 合并两个已排好序的线性表的算法

下面是代码,结合注释理解

点击查看代码
#include 
#include 
#include 
#include 

#define maxlenglth 1000
#define OK 1
#define ERROR 0

using namespace std;

typedef int Elemtype;
typedef int Status;
typedef int Position;

struct SeqList
{
    Elemtype data[maxlenglth];
    int lenth;
};// 线性表的定义

Status Display(SeqList L);//打 印
SeqList InitList();// 初始化
Position End(SeqList L); // 返回最后的位置
Status Insert(Elemtype t, Position p, SeqList &L); // 在位置p插入元素t
Status Delete(Elemtype t, SeqList &L); //删除所有元素t
Status Sort(SeqList &L); //排序
Status Unique(SeqList &L); //对排完序去重
Status ReverseList(SeqList &L); //翻转(逆置)
Status Merge(SeqList &L1, SeqList L2); //合并两个排好序的
Status Move(SeqList &L, int flag, int step); //移动

int main()
{
    // basic test
    int n1, n2;
    SeqList L1 = InitList();
    SeqList L2 = InitList();
    cout > n1;
    cout > x;
        Insert(x, L1.lenth + 1, L1);
    }
    Display(L1);
    cout > temp;
    Delete(temp, L1);
    Display(L1);

    cout > n2;
    cout > x;
        Insert(x, L2.lenth + 1, L2);
    }
    Display(L2);
    cout > flag;
    cout > step;
    Move(L1, flag, step);
    Display(L1);

    cin >> n1;

    return 0;
}

Status Display(SeqList L)
{
    for(int i = 1; i  L.lenth + 1 || p  p; i -- )
    {
        L.data[i] = L.data[i - 1];
    }
    L.data[p] = t;
    return 0;
}   

Status Delete(Elemtype t, SeqList &L)
{
    Position idx = 0; 
    for(int i = 1; i = maxlenglth)
    {
        cout  temp.lenth)
        {
            j -= temp.lenth;
        }
        if(j 

链式存储结构

关于链表,有三种经典类型:单链表双向链表循环链表

而每种类型又有很多考法

但其核心都是指针域的用法


另外要实现的功能:

  • 对于已排好序的线性表,删除所有重复元素的算法。
  • 线性表“逆置”算法。
  • 线性表循环左移/右移 k 位的算法。
  • 合并两个已排好序的线性表的算法
点击查看代码
#include 
#include 
#include 
#include 
#include 

#define OK 0
#define ERROR 1

using namespace std;

typedef int Elemtype;
typedef int Status;

struct Node{

    Elemtype data;
    Node * next;
};//链表定义

typedef Node * Position;
typedef Node * LIST;

void Creat(LIST head,int size);//创建 
void ForwardInsert(LIST head,Elemtype x);//头插 
void BackInsert(LIST head,int x);//尾插 
void Travel(LIST head);//遍历 
Status IsEmpty(LIST head);//判空 
void AllDelete(LIST head);//删除 
void SomeDataDelete(LIST head,Elemtype x);//删除一个数 
void SomeDataInsert(LIST head,Elemtype x,int num);//在某位置插入一个数 
void Sort(LIST head, int (*cmp)(Elemtype, Elemtype));//冒泡排序 
int Ascend(Elemtype x, Elemtype y);//升序 
int Descend(Elemtype x, Elemtype y);//降序 
Position Locate(Elemtype x, LIST head);
void Unique(LIST head);//去重
Status Reverse(LIST head);//翻转
Status Move(LIST head, int flag, int step);//循环移动
Status Merge(LIST head1, LIST head2);//合并两个排好序的链表
int Len(LIST head);//求链表长
void MergeTest();//合并的测试

int main()
{
    LIST head = (LIST)malloc(sizeof(Node));//头节点 
    head->next = NULL;

    int num, i;
    Elemtype temp;

    cout > num;
    Creat(head,num);
    Travel(head);

    cout > temp;
    ForwardInsert(head,temp);
    Travel(head);

    cout > temp;
    BackInsert(head,temp);
    Travel(head);

    cout > temp;
    SomeDataDelete(head,temp);
    Travel(head);

    cout > temp >> i;
    SomeDataInsert(head,temp,i);
    Travel(head);

    // 排序测试
    cout > flag >> step;
    Move(head, flag, step);
    Travel(head);   

    // 合并测试

    MergeTest();

    AllDelete(head);
    Travel(head);
    free(head);//free掉头节点 

    return 0;
}

void MergeTest()
{
    int num;

    cout next = NULL;
    cout > num;
    Creat(h1,num);
    Sort(h1, Descend);

    LIST h2 = (LIST)malloc(sizeof(Node));
    h2->next = NULL;
    cout > num;
    Creat(h2,num);
    Sort(h2, Descend);

    Merge(h1, h2);
    cout next, p2 = head2->next;
    LIST temp = head1;
    while(p1 != NULL && p2 != NULL)
    {
        if(p1->data data)
        {
            temp->next = p1;
            p1 = p1->next;
        }else
        {
            temp->next = p2;
            p2 = p2->next; 
        }
        temp = temp->next;
    }
    while(p1 != NULL)
    {
        temp->next = p1;
        p1 = p1->next;
        temp = temp->next;
    }

    while(p2 != NULL)
    {
        temp->next = p2;
        p2 = p2->next;
        temp = temp->next;
    }

    temp->next = NULL;
    return OK;
}

Status Move(LIST head, int flag, int step)
{
    int len = Len(head);
    step = step % len;
    if(step == 0)
    {
        return OK;
    }
    if(flag == 0)
    {
        step = len - step;
    }

    LIST p, q, s;
    p = q = s = head;

    p = p->next;

    int idx = 0;
    while(s->next != NULL)
    {
        idx ++;
        s = s->next;
        if(idx == step)
        {
            q = s;
        }
    }

    head->next = q->next;
    s->next = p;
    q->next = NULL;

    return OK;
}
int Len(LIST head)
{
    LIST p = head;
    int cnt = 0;
    while(p->next != NULL)
    {
        cnt ++;
        p = p->next;
    }
    return cnt;
}

void Unique(LIST head)
{
    Elemtype last;
    LIST p, q;
    p = head->next;
    if(p == NULL || p->next == NULL)
    {
        return;
    }
    last = p->data;
    q = p->next;
    while(q != NULL)
    {
        if(q->data == last)
        {
            p->next = q->next;
            free(q);
            if(p->next == NULL)
            {
                q = NULL;
            }else
            {
                q = p->next;
            }
        }else
        {
            last = q->data;
            q = q->next;
            p = p->next;
        }
    }
}
Status Reverse(LIST head)
{
    LIST p, q, s;
    p = q = s = head->next;
    q = p->next;

    while(q != NULL)
    {
        p->next = q->next;
        q->next = s;
        s = q;
        q = p->next;
    }
    head->next = s;
    return OK;
}

Position Locate(Elemtype x, LIST head)
{
    Position p = head;
    while(p->next != NULL)
    {
        if(p->data == x)
        {
            return p;
        }else
        {
            p = p->next;
        }
    }
    return p;/* 如果没有找到 */
}

int Descend(Elemtype x, Elemtype y)
{
    return x > y;
}
int Ascend(Elemtype x, Elemtype y)
{
    return x next == NULL)
    {
        cout next->next==NULL)
    {
        cout next; p1->next != NULL; p1 = p1->next) 
    {
         for (p2 = p1->next; p2!=NULL; p2 = p2->next)
         {
            if ((*cmp)(p1->data, p2->data))
            {
                swap(p1->data, p2->data);
            }
        }
    }
}
void Creat(LIST head, int size)
{
    LIST p = head;
    for(int i = 1;i next = NULL;
        cin >> newnode->data;
        p->next = newnode;
        p = newnode;
    }
}
void ForwardInsert(LIST head, Elemtype x)
{
    LIST newhead = (LIST)malloc(sizeof(Node));
    newhead->data = x;
    newhead->next = head->next;
    head->next = newhead;
    return;
}
void Travel(LIST head)
{
    LIST p = head;
    while(p->next != NULL)
    {   
        p = p->next; 
        cout data next = NULL;
    back->data = x;
    while(p->next != NULL)
    {
        p = p->next;
    }
    p->next = back;
    return;
}
Status IsEmpty(LIST head)
{
    if(head->next == NULL)
    {
        cout next;
    LIST temp = head;
    while(p != NULL)
    {
        temp = p;
        p = p->next;
        free(temp);
    }
    head->next = NULL;
    return;
}
void SomeDataDelete(LIST head, Elemtype x)
{
    LIST p = head->next;
    LIST last = head;
    LIST temp = NULL;
    while(p != NULL)
    {
        if(temp != NULL)
        {
            free(temp);

            temp = NULL;
        }
        if(p->data == x)
        {
            last->next = p->next;
            temp = p;
        }else
        {
            last = last->next;
        }   
        p = p->next;
    }
    return;
}
void SomeDataInsert(LIST head,Elemtype x,int num)
{
    LIST p = head;
    LIST last = head;
    int idx = 0;
    while(p->next != NULL)
    {
        p = p->next;
        idx ++;
        if(idx == num)
        {
            LIST NewNode = (LIST)malloc(sizeof(Node));
            NewNode->data = x;
            last->next = NewNode;
            NewNode->next = p;
        }
        last = last->next;
    }
}

静态链表

静态链表其实就是将指针域游标来代替指针

游标: Cursor

所有它的大小也取决于最先开始建立的数组大小。

这里插入一张《大话数据结构》的图片

数据结构:线性表插图


实现基本功能和逆置的静态链表:

点击查看代码
#include 
#include 
#include 
#include 

#define OK 1
#define ERROR 0

#define MAXSIZE 1000 

using namespace std;

typedef int Status;       
typedef int ElemType;     

typedef struct 
{
    ElemType data;
    int cur;  /* 游标(Cursor) ,为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];

/* 将一维数组space中各分量链成一个备用链表,space[0].cur为头指针,"0"表示空指针 */
Status InitList(StaticLinkList space) 
{
    for(int i = 0; i  ListLength(L) + 1)   
        return ERROR;   
    j = Malloc_SSL(L);   /* 获得空闲分量的下标 */
    if (j)   
    {   
        L[j].data = e;   /* 将数据赋值给此分量的data */
        for(l = 1; l  ListLength(L))   
        return ERROR;   
    k = MAXSIZE - 1;   
    for (j = 1; j > n;
    for(int i = 1; i > e;
        ListInsert(L, i, e);
    }
    ListTraverse(L);
    cout 

说到静态链表,就不得不说它的一个应用:邻接表

邻接表可以用作图的存储,可以存储有向图或无向图

  • idx 游标,可认为是第idx的意思
  • h[N] 有N个顶点,每个点都可能会连有边,h[i]存储顶点i的所有出边指向的点的集合
  • e[N] 存储该节点的出边指向的顶点
  • ne[N] 存储该节点的下一个节点的游标
  • w[N] 存储该节点代表的边的权重
int h[N], e[N], ne[N], idx;

// 添加一条边a->b
void add(int a, int b) //a到b添加一条边 事实上是 头插法
{
    e[idx] = b;//节点idx存储顶点b 
    ne[idx] = h[a];//将节点idx指向的节点 指向 a顶点所指向的节点(头节点)
    h[a] = idx ++ ; //将头指针的指向为新的头节点 
}

// 初始化
idx = 0;
memset(h, -1, sizeof h); //初始化 所有的头指针指向-1 
//这样当遍历的时侯,因为游标不可能出现-1,就可以当作遍历终止条件

参考文献

  • 程杰. 大话数据结构:溢彩加强版[M]. 北京: 清华大学出版社, 2020.

文章来源于互联网:数据结构:线性表

THE END
分享
二维码