线性链式表

发表于 | 更新于 | 分类于 | 阅读次数： | 字数： 2,099 | 阅读时长： 9

链表的定义：

链表就是由多个结点离散分配，彼此通过指针相连，每个结点只有一个前驱结点和后继结点。首节点无前驱结点，为结点无后继结点的一种存储结构。

链表中的一些基本概念：

头结点：链表的第一个有效结点前面的结点，头结点并不存放有效数据，也就是数据域为空，加头结点的主要目的是为了方便链表的操作。

首节点：链表的第一个有效结点，结点包含数据域和指针域。

尾结点：尾结点的指针域为空。

头指针：指向头结点的指针变量，它存放了头结点的地址(在这里注意一下，指针变量存放的是地址，也就是说头指针存放的是头结点的地址,一般通过头指针对链表进行操作)。

链表的种类：

  • 单向链表：

    链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

  • 双向链表：

    一种更复杂的链表是“双向链表”或“双面链表”。每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）。

    双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。

  • 循环链表：

    在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存， 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。

    指向整个列表的指针可以被称作访问指针。

  • 块状链表：

    块状链表本身是一个链表，但是链表储存的并不是一般的数据，而是由这些数据组成的顺序表。每一个块状链表的节点，也就是顺序表，可以被叫做一个块。

    块状链表通过使用可变的顺序表的长度和特殊的插入、删除方式。块状链表另一个特点是相对于普通链表来说节省内存，因为不用保存指向每一个数据节点的指针。

链表的存储结构：

1
2
3
4
5
6
7
8
9
//----------链表的存储结构表示------------
typedef struct LNode{//节点类型
    ElemType  data;//这里表示了每一项，其指数和系数
    struct LNode *next;
}*Link,*Position;
typedef struct{//链表类型
    Link head, tail;//分别指向线性链表中的头结点和最后一个结点
    int len;//指示线性链表中数据元素的个数
}LinkList;//每一项组成一个列表

链式线性表的具体实现代码：

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
//----------链表函数的具体实现代码-----------
Status InitList(LinkList *L){
    // 构造一个空的线性链表
    Link p;
    p = (Link)malloc(sizeof(LNode)); // 生成头结点
    if (p)
    {
        p->next = NULL;
        (*L).head = (*L).tail = p;
        (*L).len = 0;
        return OK;
    }
    else
        return ERROR;//内存分配不够
}//InitList

Status MakeNode(Link *p, ElemType e){
    // 分配由p指向的值为e的结点，并返回OK；若分配失败。则返回ERROR
    *p = (Link)malloc(sizeof(LNode));
    if (!*p)
        return ERROR;
    (*p)->data = e;
    return OK;
}//MakeNode

void FreeNode(Link *p){
    // 释放p所指结点
    free(*p);
    *p = NULL;
}//FreeNode

Status InsFirst(LinkList *L, Link h, Link s){
 // h指向L的一个结点，把h当做头结点，将s所指结点插入在第一个结点之前
    s->next = h->next;
    h->next = s;
    if (h == (*L).tail) // h指向尾结点
        (*L).tail = h->next; // 修改尾指针
    (*L).len++;
    return OK;
}//InsFirst

Position GetHead(LinkList L){
    // 返回线性链表L中头结点的位置
    return L.head;
}//GetHead

Status SetCurElem(Link p, ElemType e){
    // 已知p指向线性链表中的一个结点，用e更新p所指结点中数据元素的值
    p->data = e;
    return OK;
}//SetCurElem

Status LocateElemP(LinkList L, ElemType e, Position *q, int(*compare)(ElemType, ElemType)){
     // 若升序链表L中存在与e满足判定函数compare()取值为0的元素，则q指示L中
    // 第一个值为e的结点的位置，并返回TRUE；否则q指示第一个与e满足判定函数
    // compare()取值>0的元素的前驱的位置。并返回FALSE。（用于一元多项式）
    Link p = L.head, pp;
    do
    {
        pp = p;
        p = p->next;
    } while (p && (compare(p->data, e)<0)); // 没到表尾且p->data.expn<e.expn
    if (!p || compare(p->data, e)>0) // 到表尾或compare(p->data,e)>0
    {
        *q = pp;
        return FALSE;
    }
    else // 找到
    {// 没到表尾且p->data.expn=e.expn
        *q = p;
        return TRUE;
    }
}//LocateElemP

Position NextPos(Link p){
   // 已知p指向线性链表L中的一个结点，返回p所指结点的直接后继的位置
   //  若无后继，则返回NULL
    return p->next;
}//NextPos

ElemType GetCurElem(Link p){
     // 已知p指向线性链表中的一个结点，返回p所指结点中数据元素的值
    return p->data;
}//GetCurElem

Status DelFirst(LinkList *L, Link h, Link *q){ // 形参增加L,因为需修改L
  // h指向L的一个结点，把h当做头结点，删除链表中的第一个结点并以q返回。
  // 若链表为空(h指向尾结点)，q=NULL，返回FALSE
    *q = h->next;
    if (*q) // 链表非空
    {
        h->next = (*q)->next;
        if (!h->next) // 删除尾结点
            (*L).tail = h; // 修改尾指针
        (*L).len--;
        return OK;
    }
    else
        return FALSE; // 链表空
}//DelFirst

Status ListEmpty(LinkList L){
    // 若线性链表L为空表，则返回TRUE，否则返回FALSE
    if (L.len)
        return FALSE;
    else
        return TRUE;
}//ListEmpty

Status Append(LinkList *L, Link s){
  // 将指针s(s->data为第一个数据元素)所指(彼此以指针相链,以NULL结尾)的
  //  一串结点链接在线性链表L的最后一个结点之后,并改变链表L的尾指针指向新
  //  的尾结点
    int i = 1;
    (*L).tail->next = s;
    while (s->next)
    {
        s = s->next;
        i++;
    }
    (*L).tail = s;
    (*L).len += i;
    return OK;
}//Append

Status ListTraverse(LinkList L, void(*visit)(ElemType)){
    // 依次对L的每个数据元素调用函数visit()。一旦visit()失败，则操作失败
    Link p = L.head->next;
    int j;
    for (j = 1; j <= L.len; j++)
    {
        visit(p->data);
        p = p->next;
    }
    cout << "\b "; //退格，每次输出多项式后删掉的最后输出的"+"
    if (L.len == 0)
        cout << "0";
    return OK;
}//ListTraverse

void visit(ElemType e){
    if (e.coef > 0 && e.coef != 1 && e.expn != 0)
    {
        if(e.expn == 1)
            cout<< e.coef << "x+";
        else if (e.expn > 0)
            cout << e.coef << "x^" << e.expn << "+";
        else
            cout << e.coef << "x^(" << e.expn << ")+";
    }
    else if (e.coef < 0 && e.expn != 0)
    {
        if(e.expn == 1)
            cout<< "(" <<e.coef << ")x+";
        else if (e.expn > 0)
            cout << "(" << e.coef << ")x^" << e.expn << "+";
        else
            cout << "(" << e.coef << ")x^(" << e.expn << ")+";
    }
    else if (e.coef == 1 && e.expn != 0)
    {
        if(e.expn == 1)
            cout<< "x+";
        else if (e.expn > 0)
            cout << "x^" << e.expn << "+";
        else
            cout << "x^(" << e.expn << ")+";
    }
    else if (e.expn == 0 && e.coef != 0)
        cout << e.coef<<"+";
    else
        cout << "";//考虑用户输入可能有系数为0的情况
}//visit

这个visit是对一元多项式中的应用。打印一元多项式。

链式线性表的应用：

一元多项式的表示及相加。请点击跳转到一元多项式。

坚持原创技术分享，您的支持将鼓励我继续创作！