链表:单链表

链表是线性表另外一种存储结构的体现

也就是链式存储结构

特点是每个数据元素存储的位置都是散的

存储位置间并没有什么特定的关系(紧密相连或者隔一个隔两个)

位置完全是随机的

那么我们要怎么去用线把这些数据元素给串起来呢


链表的结点

在这里你可以把数据元素拆成两部分

一部分是存储数据的变量data

一部分是指向下一个节点的指针next

数据本身所在的区域被叫做数据域

直接指向下一个元素的指针所在的区域就叫做指针域

上图就是一个典型的单链表的结构

前驱元素的指针指向自己的数据域

双向链表会再复杂一点

每个节点除了data和next还有指向上一个元素的prev指针

也就是指针域有两个


链表相比顺序表的优缺点

顺序存储可以方便的读取里面的数据

但对于元素的增删插入效率是比较低的

因为所有元素都连在一块,少了一个排它后面的都得往前走

链表因为大家是散着站的,只是记忆了一下谁排在谁后面

所以要更换位置的话只要跟要换的人的前后打声招呼就可以了


单链表的定义

//一般的结构体的定义

typedef struct List
{
    double value;//数值
    List *next;//指针
}ListNode;//结点

//STL容器的定义

这个我还没有研究,如果之后有空的话

应该会专门开个新坑去写实现方法


单链表的基本运算

//想了想还是懒得放书上的代码了

//这里放一下自己重新写的代码

重点还是在于尾插法,其它并不是特别难

我一开始的时候一直出现段错误

段错误通常是因为指向了空指针或者内存分配的问题

看了看是我head结点没有和之后的结点给连上

需要注意一下

#include<iostream>

typedef char Elemtype;
using namespace std;

struct Node{
    Elemtype data;
    Node *next;
};//单链表里的最小结点

class List{
    public:
        List();
        void CreateList(Elemtype a[],int n);
        void OutputElem();
        void OutputLength();
        void Ifempty();
        void OutLocateElem(int n);
        void OutElemLocate(Elemtype e);
        void InsertInLocate(int n,Elemtype e);
        void DeleteInLocate(int n);
        void DestroyList();

    private:	
        Node *head;
    
};

List::List(){
    head = NULL;
}//初始化单链表 

void List::CreateList(Elemtype a[],int n){
    Node *p,*q;
    head = new Node;
    q = head;

    for(int i=0;i<n;i++){
        p = new Node;
        p->data = a[i];
        q->next = p;
        q = p;
    } 
    q->next = NULL;
    cout<<"创建成功"<<endl;
}//创建单链表 

void List::OutputElem(){
    Node *current = head->next;
    
    while(current != NULL){
        cout<<"该单链表含有元素";
        cout<<current->data<<" ";
        current = current->next;
    }
    cout<<endl;
}//输出元素 

void List::OutputLength(){
    int length = 0;
    Node *p;
    p = head;
    
    while(p->next != NULL){
        length++;
        p = p->next;
    }
    
    cout<<"单链表的长度为"<<length<<endl;
}//输出单链表的长度 

void List::Ifempty(){
    if(head == NULL){
        cout<<"是空表"<<endl;
    }else{
        cout<<"不是空表"<<endl;
    }
    
}//判断是否为空 

void List::OutLocateElem(int n){
    int i=0;
    Node *p = head;
    while(i<n && p!=NULL){
        i++;
        p = p->next;
    }
    if(p == NULL){
        cout<<"不存在"<<endl;
    }else{
        cout<<"第"<<n<<"个元素的值"<<p->data<<endl;
    }
}//输出指定位置的元素 

void List::OutElemLocate(Elemtype e){
    int i=1;
    Node *p = head->next;
    
    while(p!=NULL && p->data != e){
        p = p->next;
        i++;
    }
    
    if(p != NULL){
        cout<<"元素的位置为"<<i<<endl;
    }else{
        cout<<"未找到该元素"<<endl;
    }
}//输出元素的位置

void List::InsertInLocate(int n,Elemtype e){
    int i=0;
    Node *p = head;
    Node *q;
    while(i<n-1 && p!=NULL){
        i++;
        p=p->next;
    }
    if(p!=NULL){
        q = new Node;
        q->data = e;
        q->next = p->next;
        p->next = q;
        cout<<"插入成功"<<endl;
    }else{
        cout<<"找不到可插入的结点"<<endl;
    }
}//在指定位置插入元素

void List::DeleteInLocate(int n){
    int i=0;
    Node *p = head;
    Node *q;
    while(i<n-1 && p!=NULL){
        i++;
        p = p->next;
    }
    if(p!=NULL){
        q = p->next;
        if(q != NULL){
            p->next = q->next;
            delete q;
        }
    }else{
        cout<<"该位置没有元素"<<endl;
    }
    
}//删除指定位置的元素

void List::DestroyList(){
    
}//销毁线性表

int main(){
    
    Elemtype a[5]={'a','b','c','d','e'};
    
    List h;
    h.CreateList(a,5);
    h.OutputElem();
    h.OutputLength();
    h.Ifempty();
    h.OutLocateElem(3);
    h.OutElemLocate('a');
    h.InsertInLocate(4,'f');
    h.OutputElem();
    h.DeleteInLocate(3);
    h.OutputElem();
    
    return 0;
}

参考文献

http://c.biancheng.net/view/1570.html

https://blog.csdn.net/slandarer/article/details/91863177

https://zhuanlan.zhihu.com/p/84950700

http://data.biancheng.net/view/161.html

http://c.biancheng.net/view/351.html

《链表:单链表》有1个想法

  1. Pingback: 数据结构第五版——第二章课后实验题 – 海星peter的海滩

发表评论

您的电子邮箱地址不会被公开。