归档 分类 标签 关于我 RSS Feed
- 目录 -
表的实现和应用
folder 数据结构   label 数据结构  

概念

表是数据结构中最基本也是重要的结构。表是存储一列有顺序的数据的容器。这很类似于数组的概念，但是数组仅仅是一种数据结构，不包括对于数据的各类操作。

表分为顺序表和链表。顺序表是在内存中连续的一组空间构成，而链表可以由不相邻的空间构成。由于顺序表比较简单，所以我们重点实现链表。

链表

我们首先定义基本的结构体和操作原型。使用 ADT 模型。

#define ElementType int
#include <stdlib.h>
#include <stdio.h>
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
// 各类方法原型
List MakeEmpty( List L );
int IsEmpty( List L );
int IsLast( Position P, List L );
Position Find( ElementType X, List L );
void Delete( ElementType X, List L );
Position FindPrevious(ElementType X, List L);
void Insert( ElementType X, List L, Position P);
void DeleteList( List L );
Position Header( List L );
Position First( List L );
Position Advance( Position P );
ElementType Retrieve( Position P );
// 结构体
struct Node {
    ElementType Element;
    Position Next;
};

这里为了方便，我们定义 ElementType 类型为int类型，故而需要加上 #define ElementType int。

首先实现Makeempty方法。我们使用一个头指针作为表的指针，当然也可以不使用头指针。将一个链表置为空就是将头指针的下一个指针，也就是表头置为NULL，这个宏定义在头文件stdlib.h中。

List
MakeEmpty( List L ) {
    L->Next = NULL;
    return L;
}

接下来，我们实现IsEmpty方法。用于检测一个表是否为空，实际上就是判断头指针是否为空，也就是NULL。

int
IsEmpty( List L ) {
    return L->Next == NULL;
}

实现Find方法，如果没找到，则返回NULL，找到则返回指向这个节点的指针。

Position
Find( ElementType X, List L) {
    Position P = L;
    while (P->Element != X && P != NULL) {
        P = P->Next;
    }
    return P;
}

FindPrevious也是一样的道理，只不过返回前一个节点的地址。

Position
FindPrevious( ElementType X, List L ) {
    Position P;
    P = L;
    while (P->Next->Element != X && P->Next != NULL) {
        P = P->Next;
    }
    return P;
}

接下来，我们利用上一个函数实现Delete函数。

void
Delete( ElementType X, List L ) {
    Position P = FindPrevious(X, L);
    // if find
    if (P->Next != NULL) {
        Position TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell);
    }
}

插入函数为：

// insert temcell of x into the behind of Postion P.
void
Insert( ElementType X, List L, Position P) {
    Position N = (Position)malloc(sizeof(struct Node));
    if (N == NULL) {
        fprintf(stderr, "Out of space!\n");
    }
    N->Element = X;
    N->Next = P->Next;
    P->Next = N;
}

其他的自己另行实现。

这里放出完整的代码：

/* 链表的ADT */
#define ElementType int
#include<stdio.h>
#include<stdlib.h>

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty( List L );
int IsEmpty( List L );
int IsLast( Position P, List L );
Position Find( ElementType X, List L );
void Delete( ElementType X, List L );
Position FindPrevious(ElementType X, List L);
void Insert( ElementType X, List L, Position P);
void DeleteList( List L );
Position Header( List L );
Position First( List L );
Position Advance( Position P );
ElementType Retrieve( Position P );

struct Node {
    ElementType Element;
    Position Next;
};

Position First( List L ) {
    if(!IsEmpty(L)) {
        return L->Next;
    }
}

Position Header( List L ) {
    return L;
}

// Delete a list algorithm
void
DeleteList( List L ) {
    Position P = L->Next;
    if (P != NULL) {
        Position temCell = P;
        P = P->Next;
        free(temCell);
    }
}
// insert temcell of x into the behind of Postion P.
void
Insert( ElementType X, List L, Position P) {
    Position N = (Position)malloc(sizeof(struct Node));
    if (N == NULL) {
        fprintf(stderr, "Out of space!\n");
    }
    N->Element = X;
    N->Next = P->Next;
    P->Next = N;
}

void
Delete( ElementType X, List L ) {
    Position P = FindPrevious(X, L);
    // if find
    if (P->Next != NULL) {
        Position TmpCell = P->Next;
        P->Next = TmpCell->Next;
        free(TmpCell);
    }
}

int
IsEmpty( List L )
{
    return L->Next == NULL;
}

List
MakeEmpty( List L ) {
    L->Next = NULL;
    return L;
}

int
IsLast( Position P, List L ) {
    return P->Next == NULL;
}

Position
FindPrevious( ElementType X, List L ) {
    Position P;
    P = L;
    while (P->Next->Element != X && P->Next != NULL) {
        P = P->Next;
    }
    return P;
}

Position
Find( ElementType X, List L) {
    Position P = L;
    while (P->Element != X && P != NULL) {
        P = P->Next;
    }
    return P;
}

关于多项式计算的应用

顺序表

多项式计算可以使用顺序表，也可以使用链表。顺序表性对简单，数组下标即对应指数的大小，数值则对应系数的大小。虽然很容易实现，但是对于稀疏多项式来说，他占用了许多空间，因为他是连续的，即使没有对性的指数的项，也要占用一个空间。

/*
    第三章 表的应用——多项式的运算
    顺序表实现
 */
#include<stdio.h>
#include<stdlib.h>
#define MaxDegree 20
#define Max(a, b) ((a)>(b)? (a): (b))
typedef struct Polynomial
{
    //数组，最大范围的数值还应该加一，因为还有一个零次幂
    int CoeffArray[ MaxDegree+1 ];
    //最高指数的大小
    int HighPower;
} *Polynomial;

// 将多项式初始化为零
void ZeroPolynomial(Polynomial);
// 多项式的加法
void addPolynomial(Polynomial, Polynomial, Polynomial);
// 多形式的乘法，难点在于同类多项式的合并，这里使用数组比较容易实现
void MultPolynomal(Polynomial, Polynomial, Polynomial);


void
ZeroPolynomial(Polynomial Poly) {
    int i;
    for(i = 0; i< MaxDegree; i++) {
        Poly->CoeffArray[i] = 0;
    }
    Poly->HighPower = 0;
}

void
addPolynomial(Polynomial Poly1, Polynomial Poly2, Polynomial Polysum) {
    ZeroPolynomial(Polysum);
    Polysum->HighPower = Max(Poly1->HighPower, Poly2->HighPower);
    for (int i = 0; i <= Polysum->HighPower; i++)
    {
        Polysum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i];
    }
}

void
MultPolynomal(Polynomial Poly1, Polynomial Poly2, Polynomial PolyPord) {
    ZeroPolynomial(PolyPord);
    PolyPord->HighPower = Poly1->HighPower + Poly2->HighPower;
    if (PolyPord->HighPower > MaxDegree) {
        fprintf(stderr, "Exceeded array size");
    }
    else {
        for (int i = 0; i <= PolyPord->HighPower; i++)
        {
            for (int j = 0; j <= PolyPord->HighPower; j++)
            {
                // 合并同类型，所以使用了 += 符号。对于数组来说，数组下标代表对应指数，所以实现简单
                PolyPord->CoeffArray[i+j] += Poly1->CoeffArray[i] * Poly2->CoeffArray[j];
            }
        }

    }
}

/* 验证多项式加法和乘法 */
/* (1X^0 + 3X^1 + 2X^2) + (2X^0 + X^1 + 3X^3) = 3X^0 + 4X^1 + 2X^2 + 3X^3*/
/* (1+x)(1-x) = 1-X^2 */
int main(void) {
    Polynomial poly1 = malloc(sizeof(struct Polynomial));
    poly1->CoeffArray[0] = 1;
    poly1->CoeffArray[1] = 3;
    poly1->CoeffArray[2] = 2;
    poly1->HighPower = 2;
    Polynomial poly2 = malloc(sizeof(struct Polynomial));
    poly2->CoeffArray[0] = 2;
    poly2->CoeffArray[1] = 1;
    poly2->CoeffArray[3] = 3;
    poly2->HighPower = 3;
    Polynomial polysum = malloc(sizeof(struct Polynomial));
    addPolynomial(poly1, poly2, polysum);

    printf("HighPower = %d\n", polysum->HighPower);
    for (int i = 0; i <= polysum->HighPower; i++)
    {
        printf("%dX^%d", polysum->CoeffArray[i], i);
        if (i == polysum->HighPower)
            ;
        else
            putchar('+');
    }
    putchar('\n');
    /* 验证乘法 */
    Polynomial poly3 = malloc(sizeof(struct Polynomial));
    Polynomial poly4 = malloc(sizeof(struct Polynomial));
    Polynomial polymult = malloc(sizeof(struct Polynomial));
    // 1+X
    poly3->CoeffArray[0] = 1;
    poly3->CoeffArray[1] = 1;
    poly3->HighPower = 1;
    // 1-X
    poly4->CoeffArray[0] = 1;
    poly4->CoeffArray[1] = -1;
    poly4->HighPower = 1;

    MultPolynomal(poly3, poly4, polymult);
    for (int i = 0; i <= polymult->HighPower; i++)
    {
        printf("%dX^%d", polymult->CoeffArray[i], i);
        if (i == polymult->HighPower)
            ;
        else
            putchar('+');
    }


}

链表

链表的多项式计算比较难

// 第三章——表的应用，多项式加法和乘法——链表实现
#include<stdlib.h>
#include<stdio.h>
#define Max(a, b) ((a) > (b)? (a): (b))
typedef struct Node *PtrToNode;
typedef PtrToNode Polynomial;
struct Node {
    int Coefficient;
    // 指数
    int Exponent;
    PtrToNode Next;
};

void Insert(int, int, Polynomial);
PtrToNode Find(int, Polynomial);
void ZeroPolynomial( Polynomial);
void AddPolynomial( Polynomial, Polynomial, Polynomial);
void MultPolynomial( Polynomial, Polynomial, Polynomial);
// Poly 为头节点
// 这个插入函数保证了链表中指数为有序的，递增顺序
void
Insert(int Exponent, int Coefficient, Polynomial Poly) {


    // 升序插入，找到一个指数大于此指数的前一个节点
    PtrToNode head = Poly;
    while (head->Next != NULL && head->Next->Exponent < Exponent) {
        head = head->Next;
    }
    // 如果没找到，或者找到了合适的位置，则插入
    if (head->Next == NULL || head->Next->Exponent > Exponent ) {
        PtrToNode P = (PtrToNode)malloc(sizeof(struct Node));
        P->Coefficient = Coefficient;
        P->Exponent = Exponent;
        P->Next = head->Next;
        head->Next = P;
    // if find the Node which have the same Exponent then plus the Coefficient of them.
    // 如果找到了一个相等的指数，则将他们的系数相加
    } else if (head->Next->Exponent == Exponent) {
        head->Next->Coefficient += Coefficient;
    }
}

// make the link list zero.
void
ZeroPolynomial( Polynomial Poly ) {
    Poly->Next = NULL;
}

void
AddPolynomial( Polynomial poly1, Polynomial poly2, Polynomial polysum ) {
    ZeroPolynomial(polysum);
    // 返回第一个节点指数较大的那个链表
    PtrToNode ptr1 = poly1->Next;
    PtrToNode ptr2 = poly2->Next;
    PtrToNode ptrsum = polysum;
    while (ptr1 != NULL && ptr2 != NULL) {
        PtrToNode minptr = ptr1->Exponent < ptr2->Exponent? ptr1: ptr2;
        Polynomial temCell = (PtrToNode)malloc(sizeof(struct Node));
        temCell->Next = NULL;
        if (ptr1->Exponent == ptr2->Exponent) {
            temCell->Exponent = ptr1->Exponent;
            temCell->Coefficient = ptr1->Coefficient + ptr2->Coefficient;
        } else {
            temCell->Exponent = minptr->Exponent;
            temCell->Coefficient = minptr->Coefficient;
        }
        ptrsum->Next = temCell;
        ptrsum = ptrsum->Next;
        ptr1 = ptr1->Next;
        ptr2 = ptr2->Next;
    }
    if (ptr1 == NULL) {
        ptrsum->Next = ptr2;
    } else {
        ptrsum->Next = ptr1;
    }
}

void
MultPolynomial( Polynomial poly1, Polynomial poly2, Polynomial polyPord) {
    ZeroPolynomial(polyPord);
    PtrToNode p1 = poly1->Next;
    PtrToNode p2 = poly2->Next;
    while (p1 != NULL) {
        while (p2 != NULL) {
            int plusExponent = p2->Exponent + p1->Exponent;
            int multCoefficient = p1->Coefficient * p2->Coefficient;
            Insert(plusExponent, multCoefficient, polyPord);
            p2 = p2->Next;
        }
        p1 = p1->Next;
        // 复位第二个多项式的指针
        p2 = poly2->Next;
    }
}
void
print(Polynomial P) {
    P = P->Next;
    while (P != NULL) {
        printf("%dX^%d", P->Coefficient, P->Exponent);
        P = P->Next;
        if (P != NULL) {
            putchar('+');
        }
    }
    putchar('\n');
}

/* 验证链表的多项式算法 */
int
main(void)
{
    // (1+x)
    Polynomial poly1 = (Polynomial)malloc(sizeof(struct Node));
    ZeroPolynomial(poly1);
    Insert(0, 1, poly1);
    Insert(1, 1, poly1);
    print(poly1);
    // (1-x)
    Polynomial poly2 = (Polynomial)malloc(sizeof(struct Node));
    ZeroPolynomial(poly2);
    Insert(0, 1, poly2);
    Insert(1, -1, poly2);
    print(poly2);

    Polynomial polysum = (Polynomial)malloc(sizeof(struct Node));
    ZeroPolynomial(polysum);
    // 加法
    AddPolynomial(poly1, poly2, polysum);
    printf("加法：\n");
    print(polysum);
    Polynomial polymult = (Polynomial)malloc(sizeof(struct Node));
    // 乘法
    MultPolynomial(poly1, poly2, polymult);
    printf("乘法:\n");
    print(polymult);
}

​

最后修改于 2021-06-04

此篇文章的评论功能已经停用。

Chen's Life
不要温柔的走进那个良夜
归档 分类 标签 关于我 RSS Feed
Hugo Theme Diary by Rise
移植自 Makito's Journal.

豫ICP备2021038349号-3
© flyto2035. 本站遵循 CC-BY-NC 4.0 协议
- 目录 -