线性表 | Personal Blog

线性表

发表于

概念

自引用结构

为了说明顺序表的存储结构，需要首先明确所谓 自引用结构

1
2
3
4
5
6
7
struct tnode
{
    char *word;
    int count;
    struct tnode *left;//这句话将left声明为一个指向tnode的指针，是一个指针声明语句。
    struct tnode *right;
}

这是一个经典二叉树的结构体声明，需要注意的是 这个声明的过程是递归的，但它是合法的。在这样一个结构体中，拥有对下一个节点的递归声明。

建表

链表的建立分为两种方式，头插入和尾插入

若为尾插入：
首先将尾指针指向头节点的数据域，之后始终保持指向表尾，有利于进行尾插入
然后每接收一个字符，就申请一个空间，将尾指针指向当前的表尾
最后在结束接收时，将Null值赋给尾指针

若为头插法：
字符的输入顺序与读取顺序相反
为新元素申请空间后，置入数据域，指针指向首元节点，再将头节点的指针指向新元素。

查找

单链表的查询分为按序号查找和按值查找

关于双向链表

一个节点存在前驱指针prior、数据域和后继指针next

用数组模拟实现链表

某些语言没有提供指针，我们可以用数组来实现链表的功能

首先定义一个结构数组，分为存放信息及其关联信息两部分

具体来说，分为数据部分和游标指示器部分；游标指示器充当指针的作用，指示后继结点在结果数组中的数组下标；

自然，由于数组的长度是固定的，其所模拟的链表也是静态链表，所拥有的备用空间也是固定有限的。已用空间和备用空间以-1为界限。

结构数组的结点增加与删除

增加：对于系统而言，增加结点相当于减少备用空间，也就是将备用空间的头节点的地址赋给已用空间的尾结点的游标指示器；再调整指示备用空间头结点的指针。

删除：对于系统而言，删除结点相当于释放已用空间，也就是将被删除结点头插入备用空间；过程与增加结点相反。

利用链式存储结构表示一元多项式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
typedef struct Polynode
{
    int coef;//系数
    int exp;//指数
    Polynode *next;
}Polynode,*Polylist;
Polylist polcreate()
{
    Polynode *head,*rear,*s;
    int c,e;
    h=(Polynode *)malloc(sizeof(Polynode));//头结点
    rear=head;//尾指针
    scanf("%d,%d",&c,&e);
    while(c!=0)//输入结束标志
    {
        s=(Polynode *)malloc(sizeof(Polynode));
        s->coef=c;
        s->exp=e;
        rear->next=s
        rear=s;
        scanf("%d,%d",&c,&e);
    }
    rear->next=NULL;//结束
    return(head);
}