[数据结构与算法]继续刷--《常见的数据结构》

常见的数据结构

下面继续刷一刷常见的数据结构：链表，队列，二叉查找树。

后面若再碰到其他常用的数据结构体，有机会再补上来。

代码和内容参考或来源于《C Primer Plus》（第六版）第17章，这里是做了个总结，也作为自己的学习备忘。

1. 链表（Link List）

虽然结构不能含有与自身类型相同的结构，但是可以含有指向同类型结构的指针。这种定义是定义链表（Link List）的基础，链表中的每一项都包含着在何处能找到下一项的信息。

1.1 链表——数据结构总结

• 类型名：简单链表（单向链表）
• 类型属性：可以存储一系列项
• 类型操作：
  1.初始化链表为空；
  2.确定链表是否为空；
  3.确定链表是否已满；
  4.获取链表中的项数；
  5.在链表的末尾添加项；
  6.遍历链表，处理链表中的项；
  7.清空链表；

1.2 链表——数据结构的定义

#define T_SIZE   45

typedef struct film
{
    char title[T_SIZE];
    int rating;
}Item;

typedef struct node
{
    Item item;
    struct node *next; //单向链表，双向链表还有个previos的指针
}Node;

typedef Node*  List;

1.3 链表——数据结构的操作

1.3.1 初始化链表，将链表初始化为空链表：

/*
    函数说明：
        初始化链表，将链表初始化为空链表
    参数：
        plist指向一个链表；
    返回值：
        无
*/
void InitializeList(List *plist)
{
    *plist = NULL;
}

1.3.2 判断链表是否为空：

/*
    函数说明：
        判断链表是否为空
    参数：
        plist指向一个已初始化的链表；
    返回值：
        true  : 链表为空
        false : 链表非空
*/
bool ListIsEmpty(const List *plist)
{
    if(NULL == *plist)
        return true;
    else
        return false;   
}

1.3.3 判断链表是否已满：

/*
    函数说明：
        判断链表是否已满
    参数：
        plist指向一个已初始化的链表；
    返回值：
        true  : 链表已满
        false : 链表非满
*/
bool ListIsFull(const List *plist)
{
    Node *  pNode;
    bool isFull = false;
    
    pNode = (Node *)malloc(sizeof(List));

    if(NULL == pNode)
        isFull =  true;
    else
        isFull =  false;
    
    free(pNode);
    pNode = NULL;
    return isFull;
}

1.3.4 获取链表中的项数：

/*
    函数说明：
        获取链表中的项数
    参数：
        plist指向一个已初始化的链表；
    返回值：
        unsigned int  : 链表中的项数
*/
unsigned int ListItemCount(const List *plist)
{
    unsigned int count = 0;
    Node * pNode;

    pNode = *plist;

    while (NULL != pNode)
    {
        pNode = pNode->next;
        count++;
    }
    return count;
}

1.3.5 在链表的末端添加项：

/*
    函数说明：
        在链表的末端添加项
    参数：
        item为待添加至链表的项
        plist指向一个已初始化的链表；
    返回值：
        true  : 添加成功
        false : 添加失败
*/
bool ListAddItem(Item item, List * plist)
{
    Node * pNewNode = NULL;
    Node * pNodeScan = *plist;

    pNewNode = (Node *)malloc(sizeof(Node));
    
    if(NULL == pNewNode)
        return false;

    copyItemToNode(item, pNewNode);
    pNewNode->next = NULL;

    if(NULL == pNodeScan)
    {
        *plist = pNewNode;
    }
    else
    {
        while (pNodeScan->next != NULL){
            pNodeScan = pNodeScan->next;
        }
        pNodeScan->next = pNewNode;
    }
    return true;
}

1.3.6 遍历链表，将函数作用于链表中的每一项：

/*
    函数说明：
        将函数作用于链表中的每一项
    参数：
        plist指向一个已初始化的链表；
        pfun指向一个函数，该函数接受Item类型的参数，且无返回值
    返回值：
        无
*/
void Traverse(const List *plist, void(*pfun)(Item* item))
{
    Node* pNode = NULL;

    if(NULL == *plist)
        return;
    
    pNode = *plist;

    while (NULL != pNode)
    {
        pfun(&pNode->item);
        pNode = pNode->next;
    }
}

1.3.7 清空链表：

/*
    函数说明：
        清空链表
    参数：
        plist指向一个已初始化的链表；
    返回值：
        无
*/
void EmptyList(List *plist)
{
    Node *  pNodeSave = NULL;

    while (NULL != plist)
    {
        pNodeSave = (*plist)->next;
        free(plist);
        *plist = pNodeSave;
    }
}

2. 队列（Queue）

队列（queue）是具有两个特殊属性的链表。第一，新项只能添加到链表的末尾。从这方面看，队列与简单链表类似。第二，只能从链表的开头移除项。队列是一种“先进先出”（First in, First out，FIFO）的数据形式。

2.1 队列——数据结构总结

• 类型名：队列
• 类型属性：可以存储一系列项
• 类型操作：
  1.初始化队列为空；
  2.确定队列是否为空；
  3.确定队列是否已满；
  4.获取队列中的项数；
  5.在队列的末尾添加项；
  6.在队列开头删除项；
  7.清空队列；

2.2 队列——数据结构的定义

//方便扩展
typedef int Item;
/*
typedef struct item
{
    int kind;
    int size;
}Item;
*/

typedef struct node
{
    Item item;
    struct node *next;
}Node;

typedef struct queue
{
    Node* front;
    Node* rear;
    int items;
}Queue;

2.3 队列——数据结构的操作

2.3.1 初始化队列，初始队列为空：

//初始化队列，初始队列为空
void InitQueue(Queue* pq)
{
    pq->front = NULL;
    pq->rear = NULL;
    pq->items = 0;
}

2.3.2 检查队列是否为空：

//检查队列是否为空
bool QueueIsEmpty(const Queue* pq)
{
    return pq->items == 0;
}

2.3.3 检查队列是否已满：

//检查队列是否已满
bool QueueIsFull(const Queue* pq)
{
    return pq->items == MAX_QUEUE;
}

2.3.4 确定队列中的项数：

//确定队列中的项数
int QueueItemCount(const Queue* pq)
{
    return pq->items;
}

2.3.5 在队列末尾添加项：

//在队列末尾添加项
bool EnQueue(Item item, Queue* pq)
{
    Node* pnew;

    if(QueueIsFull(pq))
        return false;
    
    pnew = (Node*)malloc(sizeof(Node));
    if(NULL == pnew){
        exit(1);
    }

    CopyToNode(item, pnew);
    pnew->next = NULL;

    if(QueueIsEmpty(pq)){
        pq->front = pnew;//项位于队列首端
    }
    else{
        pq->rear->next = pnew;//链接到队列尾部
    }
    pq->rear = pnew;//记录队列尾部的位置

    pq->items++;
    return true;
}

2.3.6 在队列的开头删除项：

bool DeQueue(Item* pItem, Queue* pq)
{
    if(QueueIsEmpty(pq))
        return false;

    Node* pNodeTemp;

    CopyToItem(pItem, pq->front);

    pNodeTemp = pq->front;

    if(pq->front->next != NULL)
        pq->front = pq->front->next;
    else
        pq->rear = NULL;
    
    free(pNodeTemp);
    pNodeTemp = NULL;

    pq->items--;
    return true;
}

2.3.7 清空队列：

//清空队列
void EmptyQueque(Queue* pq)
{
    Item dummy;
    while(!QueueIsEmpty(pq))
        DeQueue(&dummy, pq);
}

一些局部函数：

//局部函数,将项复制给节点
static void CopyToNode(Item item, Node* pn)
{
    if(NULL == pn)
        return;

    pn->item = item;
}

//局部函数，将节点中的项复制出来
static void CopyToItem(Item* pItem, Node* pn)
{
    if(NULL == pn)
        return;

   *pItem = pn->item;
}

3. 二叉查找树（Binary search tree）

二叉查找树是一种结合了二分查找策略的链接结构。二叉树的每个节点都包含一个项和两个指向其他节点（称为子节点）的指针。二叉树的每个节点都包含两个子节点——左节点和右节点，其顺序按照如下规定确定：左节点的项在父节点的项前面，右节点的项在父节点的项后面。

3.1 二叉树——数据结构总结

• 类型名：二叉查找树
• 类型属性：二叉树要么是空节点的集合（空树），要么是有一个根节点的节点集合，每个节点都有两个子树，叫做左子树和右子树。每个子树本身也是一个二叉树，也有可能是空树，二叉查找树是一个有序的二叉树，每个节点包含一个项，左子树的所有项都在根节点项的前面，右子树的所有项都在根节点项的后面。
• 类型操作：
  1.初始化树为空；
  2.确定树是否为空；
  3.确定树是否已满；
  4.获取树中的项数；
  5.在树中查找一个项；
  6.在树中添加一个项；
  7.在树中删除一个项；
  8.遍历树中的各个项；
  9.清空树；

3.2 二叉树——数据结构的定义

#define MAX_ITEMS 10
#define SLEN  20

typedef struct item
{
    char petName[SLEN];
    char petKind[SLEN];
}Item;

typedef struct treeNode
{
    Item item;
    struct treeNode *left; //指向左子树
    struct treeNode *right; //指向右子树
}TreeNode;

typedef struct tree
{
    TreeNode* root;
    int size;
}Tree;

//为了树查找定义的父子树结构
typedef struct pair
{
    TreeNode* parent;
    TreeNode* child;
}Pair;

3.3 二叉树——数据结构的操作

3.3.1 初始化树根节点：

//初始化树根节点
void InitTree(Tree* pTree)
{
    pTree->root = NULL;
    pTree->size = 0;
}

3.3.2 判断树是否为空：

bool TreeIsEmpty(const Tree* pTree)
{
    if(NULL == pTree->root)
        return true;
    else
        return false;
}

3.3.3 判断树是否为满树：

bool TreeIsFull(Tree* pTree)
{
    if(pTree->size >= MAX_ITEMS)
        return true;
    else
        return false;
}

3.3.4 获取当前树中的项数：

//获取当前树中的项数
int TreeItemCount(Tree* pTree)
{
    return pTree->size;
}

3.3.5 判断某个项是否在树中：

//判断某个项是否在树中
bool InTree(const Item* pItem, const Tree* pTree)
{
    return(SeekItemInTree(pItem, pTree).child == NULL ? false : true);
}

static Pair SeekItemInTree(const Item* pItem, const Tree* pTree)
{
    Pair look;
    look.parent = NULL;
    look.child = pTree->root;

    if(NULL == look.child)
        return look;

    while(look.child != NULL)
    {
        if(ToLeft(pItem, &(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->left;
        }
        else if(ToRight(pItem, &(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->right;
        }
        else
            break;
    }

    return look;
}

3.3.6 往树中添加新项：

//往树中添加新项
bool TreeAddItem(const Item* pItem ,Tree* pTree)
{
    TreeNode* pNewNode;

    //树已满
    if(TreeIsFull(pTree))
        return false;

    //树中已有相同的项
    if(SeekItemInTree(pItem, pTree).child != NULL)
        return false;

    pNewNode = MakeNode(pItem);
    if(NULL == pNewNode)
        return false;

    if(NULL == pTree->root)
        pTree->root = pNewNode;
    else{
        AddNode(pNewNode, pTree->root);
    }

    pTree->size++;
    return true;
}

//局部函数，使用递归的方法往树中添加新节点
//1.判断待添加项是在当前树节点的左节点还是右节点
//2.判断当前树的子节点的左节点或右节点是否为空，若空则插入，否则继续查找为空的节点
static void AddNode(TreeNode* pNewNode, TreeNode* root)
{
    if(ToLeft(&(pNewNode->item), &(root->item)))
    {
        if(root->left == NULL)
            root->left = pNewNode;
        else
            AddNode(pNewNode, root->left);
    }
    else if(ToRight(&(pNewNode->item), &(root->item)))
    {
        if(root->right == NULL)
            root->right = pNewNode;
        else
            AddNode(pNewNode, root->right);        
    }
    else
        cout<<"already have the Item, NO NEED TO ADD IT AGAIN."<<endl;
}

3.3.7 删除树中的某个项：

//删除树中的某个项
bool TreeDeleteItem(const Item* pItem, Tree* pTree)
{
    Pair look;

    look = SeekItemInTree(pItem, pTree);
    if(NULL == look.child)
        return false;

    if(look.parent == NULL)
        DeleteNode(&(pTree->root));
    else if(look.parent->left == look.child)
        DeleteNode(&(look.parent->left));
    else
        DeleteNode(&(look.parent->right));

    pTree->size--;

    return true;
}

//pTree 指向待删除节点的父节点指针成员（左指针或右指针）的地址
//局部函数，删除某个树节点，并链接好待删除节点的子节点
static void DeleteNode(TreeNode** pTree)
{
    TreeNode* pTemp;

    if((*pTree)->left == NULL)
    {
        //待删除项的左子节点为空，直接将待删除项的右子节点接到左节点上
        pTemp = *pTree;
        *pTree = (*pTree)->right;
        free(pTemp);
        pTemp = NULL;
    }
    else if((*pTree)->right == NULL)
    {
        //待删除项的右子节点为空，直接将待删除项的左子节点接到右节点上
        pTemp = *pTree;
        *pTree = (*pTree)->left;
        free(pTemp);
        pTemp = NULL;
    }
    else
    {
        //待删除项的左右子节点均不为空
        for(pTemp = (*pTree)->left; pTemp->right != NULL; pTemp = pTemp->right)
            continue;

        pTemp->right = (*pTree)->right;
        pTemp = (*pTree);
        (*pTree) = (*pTree)->left;
        free(pTemp);
        pTemp = NULL;
    }
}

3.3.8 遍历树中的各个项：

//遍历树的各个子节点项
void Traverse(const Tree* pTree, void (*pFunc)(Item item))
{
    if(NULL != pTree)
        InOrder(pTree->root, pFunc);
}

//局部函数，遍历某个树节点的各个子节点
static void InOrder(const TreeNode* root, void(*pFunc)(Item item))
{
    if(root != NULL)
    {
        InOrder(root->left, pFunc);
        (*pFunc)(root->item);
        InOrder(root->right, pFunc);
    }
}

3.3.9 清空树：

void UnInitTree(Tree* pTree)
{
    if(pTree != NULL)
        DeleteAllNodes(pTree->root);
    pTree->root = NULL;
    pTree->size = 0;
}

//局部函数，删除某个树节点下的所有子节点
static void DeleteAllNodes(TreeNode* root)
{
    TreeNode* pTemp;
    if(root != NULL)
    {
        // 从上至下地递归删除节点，释放内存
        pTemp = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pTemp);
    }
}

一些局部函数：

//局部函数
static bool ToLeft(const Item* pItem1, const Item* pItem2)
{
    int comp1;

    if(comp1 = strcmp(pItem1->petName, pItem2->petName) < 0)
        return true;
    else if(comp1 == 0 && strcmp(pItem1->petKind, pItem2->petKind) < 0)
        return true;
    else
        return false;
}

//局部函数
static bool ToRight(const Item* pItem1, const Item* pItem2)
{
    int comp1;

    if(comp1 = strcmp(pItem1->petName, pItem2->petName) > 0)
        return true;
    else if(comp1 == 0 && strcmp(pItem1->petKind, pItem2->petKind) > 0)
        return true;
    else
        return false;
}

//局部函数
static TreeNode* MakeNode(const Item* pItem)
{
    TreeNode* pNewNode;

    pNewNode = (TreeNode*)malloc(sizeof(TreeNode));
    if(pNewNode != NULL)
    {
        pNewNode->left = NULL;
        pNewNode->right = NULL;
        pNewNode->item = *pItem;
    }
    return pNewNode;
}