数据结构note（三）

发表于 2023-07-28 分类于学习，数据结构 Waline：阅读次数：本文字数： 4.2k 阅读时长 ≈ 4 分钟

链表与数组、向量的不同之处

链表与数组、向量不同之处在于，其元素的地址可以任意而不要求连续。元素之间通过指针相互联系。虽然其仍要求各元素在逻辑上具线性次序，但对物理地址未作任何限制，也即“动态存储”策略。

引入列表结构的目的，就在于弥补向量结构在解决某些应用问题时，在功能及性能方面的不足。其中的数据，分散为一系列称作节点（node）的单位，节点之间通过指针相互索引和访问。为了引入新节点或删除原有节点，只需在局部，调整少量相关节点之间的指针。这就意味着，采用动态存储策略，至少可以大大降低动态操作的成本。

单向链表

单向链表由结点构成，每个结点包含两个域：指针域和数据域。最后一个数据的指针域赋NULL.

单向链表的实现

框架的搭建

准备头文件LinkList.h

定义两个class：结点和链表，声明一些需要的接口：

#pragma once
//结点定义（这里数据域没有用抽象的数据类型，以后会改进）
class node {
public:
    int data;//数据域
    node* next;//指针域
};

//链表定义
class list {
public:
    node* head;//指向链表首位node
    int size;//链表结点个数
};

//操作接口
//初始化链表
list* LinkList_init();
//插入数据
void LinkList_Insert(list* list, int pos, int data);
//删除指定位置的值
void LinkList_Del(list* list, int pos);
//获得链表长度
int LinkList_GetSize(list* list);
//返回第一个结点数据
int LinkList_FirstData(list* list);
//释放链表内存
void LinkList_FreeSpace(list* list);
//查找某个值
int LinkList_Search(list* list, int data);
//打印链表结点
void LinkList_Print(list* list);

准备接口定义的文件LinkList.cpp

把每个先前声明好的复制到该文件，并且需要#include "LinkList.h".
准备用于测试的main函数.

具体写操作接口定义

初始化链表LinkList_init()

根据前面定义的class，首先要创建一个链表，再分配一个头结点，头结点不保存数据。

//初始化链表
list* LinkList_init() {
    list* L = new list;
    L->size = 0;
    L->head = new node;
    L->head->data = NULL;//头结点不保存数据
    L->head->next = NULL;
    return L;
}

插入数据

需要处理pos越界的情况以及list、data为NULL的情况，这里由于事先将data设置为了确定的数据类型int，因此理论上可以不进行处理，而这里还是加上了处理的部分以便后续的更改。

//插入数据
void LinkList_Insert(list* list, int pos, int data) {
    if (list == NULL) {
        return;
    }
    if (data == NULL && data!=0) {
        return;
    }
    //友好处理pos越界的情况
    if (pos<0 || pos>list->size) {
        pos = list->size;//让其等于尾部
    }
    //创建新的结点
    node* newnode = new node;
    newnode->data = data;
    newnode->next = NULL;
    //找结点
    //辅助指针变量
    node* pCurrent = list->head;
    for (int i = 0; i < pos; i++) {
        pCurrent = pCurrent->next;
    }//让指针指向pos前的结点位置
    //新结点插入链表
    newnode->next = pCurrent->next;
    pCurrent->next = newnode;

    list->size++;
}

删除指定位置的值

这里就不能友好的处理pos越界的情况了，需要适当的修改。

// 删除指定位置的值
void LinkList_Del(list* list, int pos) {
    if (list == NULL) {
        return;
    }
    if (pos<0 || pos>=list->size) {
        return;
    }
    //定位到删除结点的前一个结点
    node* pCurrent = list->head;
    for (int i = 0; i < pos; i++) {
        pCurrent = pCurrent->next;
    }
    //缓存删除的结点
    node* delnode = pCurrent->next;
    pCurrent->next = delnode->next;
    delete delnode;
    list->size--;
}

获得链表长度

//获得链表长度
int LinkList_GetSize(list* list) {
    if (list == NULL) {
        return -1;
    }
    return list->size;
}

返回第一个结点的数据

//返回第一个数据（不是头结点）
int LinkList_FirstData(list* list) {
    return list->head->next->data;
}

释放链表内存

辅助指针的设置和前面的2、3思路一样，下面需要遍历的时候同理。

//释放链表内存
void LinkList_FreeSpace(list* list) {
    if (list == NULL) {
        return;
    }
    //辅助指针、释放结点内存
    node* pCurrent = list->head;
    while (pCurrent != NULL) {
        //缓存下一个结点
        node* pNext = pCurrent->next;
        delete pCurrent;
        pCurrent = pNext;
    }
    list->size = 0;
    delete list;
}

查找某个值

//查找某个值
int LinkList_Search(list* list, int data) {
    if (list == NULL) {
        return -1;
    }
    if (data == NULL && data != 0) {
        return -1;
    }
    //遍历
    node* pCurrent = list->head->next;
    int i = 0;
    while (pCurrent != NULL) {
        if (pCurrent->data == data) {
            break;
        }
        i++;
        pCurrent = pCurrent->next;
    }
    return i;
}

打印链表结点

//打印链表结点
void LinkList_Print(list* list) {
    if (list == NULL) {
        return;
    }
    //辅助指针变量
    node* pCurrent = list->head->next;
    cout << "the datum of list are：";
    while (pCurrent != NULL) {
        cout << pCurrent->data;
        cout << " ";
        pCurrent = pCurrent->next;
    }
    cout << endl;
}

测试情况

测试的代码如下：

#include <iostream>
#include "LinkList.h"
using namespace std;

int main()
{
    list* list = LinkList_init();
    int a[9] = { 4,6,7,1,5,2,3,0,8 };
    for(int i=0;i<9;i++){
        LinkList_Insert(list, i, a[i]);
    }
    LinkList_Print(list);
    cout << "----after--delete----" << endl;
    LinkList_Del(list, 3);
    LinkList_Print(list);
    cout << "the first data of the list is: " << LinkList_FirstData(list) << endl;
    cout << "the size of the list is: " << LinkList_GetSize(list) << endl;
    cout<<"the data '0' is at: " << LinkList_Search(list, 0) << endl;
    LinkList_FreeSpace(list);
    system("pause");
    return 0;
}

输出：

链表与数组、向量的不同之处

单向链表

单向链表的实现

框架的搭建

测试情况