欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

线性表链式结构的实现

程序员文章站 2022-05-06 12:40:06
...

上一节实现了线性表顺序结构的实现,这节来实现链式结构的线性表。还是利用C++语言来实现。

linklineartable.h

#pragma once
typedef int TypeName;
struct Node
{
    TypeName data;

    Node * next;

}Snode;

typedef struct Node* Pnode;

void initTable(Pnode *node);
bool isEmpty(Pnode *node);
bool findItem(Pnode *node,int position, TypeName *item);
bool insertItem(Pnode *node,const TypeName &item, int position);
bool  deleteItem(Pnode *node,int postion, TypeName *item);
void  clearList(Pnode *node);
int  getLength(Pnode *node);
void display(Pnode *node);

linklineartable.cpp

#include "stdafx.h"
#include <stdlib.h>
#include <iostream>
/*
初始化链式线性表
带表头链式线性表
@param node 头指针 指向表头
*/
void initTable(Pnode *node) {
    //初始化一个头节点
    *node = (Pnode)malloc(sizeof(Node));
    (*node)->next = nullptr;
}

/*
判断链表是否为空表
@return true为空 否则false
*/
bool  isEmpty(Pnode *node) {
    return (*node)->next == nullptr;
}

/*
查找某个位置的数据
@param node 头指针
@param postion 位置 从1开始
@param item 返回的数据
@return  返回是否成功
*/
bool findItem(Pnode *node,int position, TypeName *item) {
    Node *p = (*node)->next;//让p指向第一个元素
    int j = 1;
    //让p循环直到p指针指到要查找的元素那个节点
    while(p&&j < position) {
        p = p->next;
        j++;
    }
    if (p == nullptr) {
        return false;
    }
    *item = p->data;

    return true;

}

/*
在某个位置插入数据
@param node 头指针
@param item 要插入的数据
@param position 要插入的位置 从1开始
@return 返回是否成功
*/
bool insertItem(Pnode *node, const TypeName &item, int position) {
    Node *p = (*node);//让p指向头节点
    int j = 1;
    while(p&&j < position) {
        p = p->next;
        j++;
    }
    if (p == nullptr||j>position) return false;
     Node *q = (Node *)malloc(sizeof(Node));//生成新的结点
    q->data = item;
    //下面两句实现新节点插入
    q->next = p->next;
    p->next = q;

    return true;
}

/*
在某个位置删除数据
@param node 头指针
@param position 要删除的位置 从1开始
@param item 删除节点中的数据
@return 返回是否成功
*/
bool  deleteItem(Pnode *node, int position, TypeName *item) {
    Node *p = (*node);//让p指向头节点
    int j = 1;
    while(p&&j < position) {
        p = p->next;
        j++;
    }
    if (p == nullptr||p->next==nullptr||j>position) return false;
    Node *q = p->next;
    p->next = q->next;
    *item = q->data;
    free(q); //释放要删除节点的空间
    return true;
}
/*
清空表
@param node 头指针
*/
void  clearList(Pnode *node) {
    Node *p = (*node)->next;//让p指向第一个元素
    Node *q = nullptr;
    //循环释放节点
    while (p) {
        q = p->next;
        free(p);
        p = q;
    }
    (*node)->next = nullptr;
}
/*
获取链式线性表的长度
*/
int  getLength(Pnode *node) {
    Node *p =(*node)->next;//让p指向第一个元素
    int j = 0;
    while (p) {
        j++;
        p = p->next;

    }
    return j;
}
void display(Pnode *node) {
    using std::cout;
    using std::endl;
    Node *p = (*node)->next;//让p指向第一个元素
    while(p)
    {
        cout << p->data << "\t";
        p= p->next; 

    }
    cout << endl;
}

main.cpp

测试测试

void LinkLinearTableTest() {
    using std::cout;
    using std::endl;
    using std::boolalpha;
    Node *node = nullptr;
    initTable(&node);
    bool isSuccess=insertItem(&node, 12, 1);
    cout << "isSuccess" <<boolalpha<< isSuccess << endl;
    display(&node);
     isSuccess = insertItem(&node,24, 1);
    cout << "isSuccess" << boolalpha << isSuccess << endl;
    display(&node);
    isSuccess = insertItem(&node,8, 3);
    cout << "isSuccess" << boolalpha << isSuccess << endl;
     display(&node);
    int length = getLength(&node);
    cout << "length" << length << endl;
    TypeName value = 0;
    isSuccess = deleteItem(&node, 4, &value);
    cout << "isSuccess" << isSuccess << endl;
    display(&node);
    cout << "delete value" << value << endl;
    isSuccess=findItem(&node, 4, &value);
    cout << "isSuccess" << isSuccess << endl;
    cout << "find value" << value << endl;
    clearList(&node);
    display(&node);
    isSuccess=isEmpty(&node);
    cout << "isEmpty" << boolalpha << isSuccess << endl;
}

执行情况
线性表链式结构的实现

总结

链式结构适合插入和删除操作很频繁的情况,可以动态的增加元素个数,不会造成空间的浪费,在插入和删除操作中,需先查找要插入和删除的位置,所用时间复杂度为O(n),之后插入和删除元素的时间复杂度都为O(1)。