第二篇:数据结构与算法-链表

概念

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不必须相邻，

可以给每个元素附加一个指针域，指向下一个元素的存储位 置。

每个结点包含两个域：数据域和指针域，指针域存储下一个结点的地址，因此指针指向的类型也是 结点类型

结构体定义

Typedef struct LinkNode{

        ElemType data;                //数据域

        struct LinkNode *next;      //指针域

}LinkList, LinkNode;//一个头结点和,其余节点 

 单向链表

链表的节点均单向指向下一个节点，形成一条单向访问的数据链 ,

只有需要插入的时候才需要申请的新的节点,删除是不需要新节点的,满足条件即可

链表:删除值,或者插入值,除非你的指针指向没有问题,否则不要直接使用头结点

 初始化

typedef struct LinkList {
    int elem;               //数据域
    struct LinkList* next;  //指针域
}LinkList,LinkNode;         //一个头结点,一个链条的节点
//初始化
bool initList(LinkList*& L) {
    L = new LinkNode;
    if (!L)return false;
    L->next = NULL;
    L->elem = 1;
    return true;
}

 前插法

bool insert_front(LinkList*& L, LinkNode*& node) {
    if (!L || !node) {
        return false;
    }
    node->next = L->next;
    L->next = node;
    return true;
}

尾插法:

bool insert_black(LinkList*& L, LinkNode*& node) {
    if (!L || !node) {
        return false;
    }
    LinkNode* p = NULL;
    p = L;当前节点的下一个节点插入
    while (p->next) {
        p = p->next;
    }
    node->next = NULL;
    p->next = node;
    
    return true;
}

随意位置插入

 bool insert_every(LinkList*& L, int pos, int e) {
    if (!L)return false;

    LinkList* p;
    LinkNode* s;//用这个节点来保存需要插入的值
    int j = 0;
    p = L;//插入是在这个节点之后插入,也就是实际值的前面插入
    while (p&&j<pos-1) {
        p = p->next;
        j++;
    }
    if (!p||j>pos-1) {//判断循环退出之后,位置的合法性
        return false;
    }
    s = new LinkNode;
    s->elem = e;
    s->next = p->next;
    p->next = s;
    return true;
}

 输出指定位置的值

bool printIndex_Value(LinkList*& L, int pos, int& value) {
    if (!L||!L->next) {
        return false;
    }
    LinkList* p = NULL;
    p = L->next;//代表实际值的第一个值,头结点是不算值的
    int index = 1;
    while (p&&index<pos) {
        p = p->next;
        index++;
    }
    if (!p || index > pos) {
        return false;
    }
    value = p->elem;
    return true;
}
//查找指定值是否存在并输出对应位置
bool printValue_Index(LinkList*& L, int value, int& index) {
    if (!L||!L->next) {
        return false;
    }
    LinkList* p = NULL;
    p = L->next;
    index = 1;
    while (p&&p->elem!=value) {
        p = p->next;
        index++;
    }
    if (!p) {
        return false;
    }
    return true;
}

删除指定位置的值 

bool delete_value(LinkList*& L, int pos) {
    if(!L||!L->next){
        return false;
    }
    LinkList* p;
    LinkNode* s;
    p = L;//指向头结点,删除的节点为当前节点的下一个节点
    int index = 1;
    while (p->next && index<pos) {
        p = p->next;
        index++;
    }

    if (!p->next||index>pos) {//判断n值的合法性
        return false;
    }
    s = p->next;
    p->next = s->next;
    delete s;
    return true;
}

 摧毁表

void destoryLink(LinkList*& L) {
    LinkList* p = L;
    while (p) {
        L = L->next;
        cout << "删除元素" << p->elem << endl;
        delete p;//这里删除p之后在进行p=p->next时不用L进行重新赋值就会出问题
        p = L;

    }
}

 

单链表的遍历

 void printLink(LinkList*& L){

        if(!L)return false;//链表为空就没必要输出了

        LinkNode *p;

        p = L->next;//指向第一个实际的值

        while (p){ //不为空的时候执行

                cout<<p.elem<<" ";

                p = p->next;        

        }

        cout <<endl;

}

循环链表

解答约瑟夫问题 : 有 10 个小朋友按编号顺序 1，2，。。。，10 顺时针方向围成一圈。从 1 号开 始顺时针方向 1，2，。。。，9 报数， 凡报数 9 者出列 （显然，第一个出圈为

编号 9 者）。

最后一个 出圈者的编号是多少？ 第 5 个 出圈者的编号是多少？

循环链表的初始化是要将,头结点的指针域指向自己

bool initList(LinkList *& L){

        L = new LinkList;

        if(!L) return false;

        L .next = L; //头结点的指针域指向自己

        L.elem = -1;//这个值没有实际作用

        return false;

}

 循环链表尾插法插入数据

bool insert_black(LinkList *&L ,LinkNode *&node){

        if(!L||!node)//因为是插入值,所以需要判断当前节点和插入值的合法性

        LinkNode * p = NULL;//定义一个节点,指向头结点

        p = L;

        while(p->next!=L){  //当p->next为L了,也就是到了实际值的最后一个了

                p = p->next;

        }

        p->next = node; 

        node.next = L;

        return true;

}

 循环链表删除指定位置的数据

bool delete_index_value(LinkList *&L ,int pos){

        if(!L||L == L->next)return false;//判断不为空链表

        LinkNode *p;

        LinkNode *s;

        p = L;//指向头结点

        int index = 0;//用来判断是否到达指定位置的上一个节点

        while(p->next != L &&index<pos-1){

                p = p->next;

        }

        s = p->next;

        p->next = s->next;

        retrun true;

}

循环链表的输出

void LinkPrint(LinkList *&L){

        if(!L||L==L->next){

                cout<<"这个链表是空的"<<endl;

                return;

        }

        LinkNode *P ;

        p = L->next;//因为需要输出值,先让节点指向第一个实际的值

        while(p->next!=L){

                cout<<p->elem<<" ";

                p = p->next;

        }

        cout<<endl;

}

分析:解答约瑟夫问题

        初始化头结点,

        使用尾插法插入十个学生编号

        循环判断,当数到9的时候,就删除这个编号的值

 

#include <iostream>
using namespace std;typedef struct LinkList {int data;struct LinkList* next;
}LinkList, LinkNode;
//初始化
bool initLink(LinkList*& L) {L = new LinkList;if (!L) {return false;}L->next = L;// L->data = -1;//这个节点实际是不计数的return true;
}
//添加元素,使用尾插法
bool insertLink(LinkList*& L, LinkNode* node) {LinkNode* p = NULL;if (!L && !node)return false;p = L;while (p->next != L) {p = p->next;}node->next = L;p->next = node;return true;
}
//遍历
void linkPrint(LinkList*& L) {LinkList* p = NULL;if (!L || L == L->next) {cout << "链表为空!" << endl;return;}p = L->next;//?while (p != L) {cout << p->data << " ";p = p->next;}cout << endl;
}
//循环删除
bool deleteLink(LinkList*& L, int interal) {LinkList* p;LinkList* q;int i = 0, j = 0;//j表示上一个,i表示这一个int times = 0, num = 0;p = L;if (!L || p->next == L) {//判断链表为空cout << "链表为空" << endl;return false;}if (interal < 1)return false;do {i += interal;//这一个的计数,每次相加都为9的倍数while (p->next){if (p->next != L)j++;//L这个节点是不能算数的,L节点只作为辅助节点if (j >= i) break;//当这里跳出的时候p还是上一次的值p->next指针,这一次还没有开始赋值p = p->next;}times++;//加一次算一轮q = p->next;//q就是要出圈的的指针num = q->data;//要出圈的那一个指针的值if (times == 5) {cout << "第五个出圈的是:" << num << endl;}cout << "出圈者: " << q->data << "出圈者的上一个: " << p->data<< "出圈者的下一个: " << q->next->data << endl;p->next = q->next;//要删除p,所以需要将p的指针复位delete q;//这里的q是一个临时节点,用来记录需要删除的节点,避免破坏循环链表的环linkPrint(L);} while (L->next != L);//这里是判断为空的时候，使用P->next !=L是不行的cout << "最后一个出圈的是:" << num << endl;return true;
}
int main(void) {LinkList* L;LinkNode* node;if (initLink(L)) {cout << "初始一个空的循环链表" << endl;}else {cout << "初始化失败" << endl;}int i = 0;while ((++i) <= 10) {node = new LinkNode;node->data = i;node->next = NULL;if (insertLink(L, node)) {cout << "插入成功" << endl;}else {cout << "插入失败" << endl;}}linkPrint(L);////Joseph(L, 9);deleteLink(L, 9);return 0;
}

 双向链表

 单链表中每个结点除了存储自身数据之后，还存储了下一个结点的地址，因此可以轻松访问

下一个结点，以及后面的后继结点，但是如果想访问前面的结点就不行了，

可以在单链表的基础上给每个元素附加 两个指针域，一个存储前一个元素的地址，一个存储

下一个元素的地址。 这种链表称为双向链表

双向链表结构体和初始化

 typedef struct LinkList {
    int data;
    struct LinkList* pre;
    struct LinkList* next;
}LinkList, LinkNode;
bool initList(LinkList*& L) {
    L = new LinkList;
    if (!L)return false;
    cout << "初始化成功" << endl;
    L->next = NULL;
    L->pre = NULL;
    L->data = -1;
    return true;
}

 

双向链表前插法:

bool insert_front(LinkList*& L, LinkNode*& node) {
    if (!L||!node) {
        return false;
    }
    LinkNode* p;//建立一个新节点，用来指向头节点
    p = L;
    if (!p->next) {//当只有一个头结点时
        p->next = node;
        node->next = NULL;
        node->pre = p;
        return true;
    }
    p->next->pre = node;
    node->next = p->next;
    p->next = node;
    node->pre = p;
    return true;
}

双向链表后插法:

bool insert_black(LinkList*& L, LinkNode*& node) {
    if (!L||!node) {
        return false;
    }
    LinkNode* p;
    p = L;
    while (p->next) {
        p = p->next;
    }
    node->next = NULL;
    p->next = node;
    node->pre = p;
    return true;
} 

双向链表删除指定节点

bool delete_index_value(LinkList*& L, int pos) {
    if (!L) {
        return false;
    }
    LinkList* p;
    p = L->next;
    int index = 0;
    while (p&&index<pos-1) {
        p = p->next;
        index++;
    }
    if (!p || index>pos) {//判断需要删除值的合法性
        return false;
    }
    if (!p->next) {
        p->pre->next = NULL;
        delete p;
        return true;
    }
    p->pre->next = p->next;//此时的p是需要删除的节点,所以需要将他的前一个节点的下一个位置,指向p的下一个位置
    p->next->pre = p->pre;//p的下一个位置的前一个节点就是,需要删除的节点p的前一个节点;
    delete p;
    return true;
} 

双向链表输出指定位置的值

 bool print_index_value(LinkList*& L, int pos, int& value) {
    if (!L) {
        return false;
    }
    LinkNode* p;
    p = L->next;
    int index = 0;
    while (p&&index<pos-1) {
        p = p->next;
        index++;
    }
    value = p->data;
    return true;
}

 双向链表在任意位置插入值

//在随意位置插入
bool insert_every(LinkList*& L, int pos, int& value) {
    if (!L) {
        return false;
    }
    LinkNode* p;
    LinkNode* s;
    p = L;
    int index = 0;
    while (p->next&&index <pos-1) {
        p = p->next;
        index++;
    }
    s = new LinkNode;
    s->data = value;
    p->next->pre = s;
    s->next = p->next;
    p->next = s;
    s->pre = p;
    return true;
}

双向链表遍历:

void printLink(LinkList*& L) {
    if (!L) {
        cout << "链表为空" << endl;
        return;
    }
    LinkNode* p;
    p = L;
    cout << endl;
    cout << "顺序输出: ";
    while (p->next) {
        cout << p->next->data << " ";
        p = p->next;
    }
    cout << endl;
    cout << "逆向输出: ";
    while (p->pre) {
        cout << p->data<< " ";
        p = p->pre;
    }
} 

#include <iostream>
using namespace std;
typedef struct LinkList {int data;struct LinkList* pre;struct LinkList* next;
}LinkList, LinkNode;
bool initList(LinkList*& L) {L = new LinkList;if (!L)return false;cout << "初始化成功" << endl;L->next = NULL;L->pre = NULL;L->data = -1;return true;
}
//前插法
bool insert_front(LinkList*& L, LinkNode*& node) {if (!L||!node) {return false;}LinkNode* p;//建立一个新节点，用来指向头节点p = L;if (!p->next) {//当只有一个头结点时p->next = node;node->next = NULL;node->pre = p;return true;}p->next->pre = node;node->next = p->next;p->next = node;node->pre = p;return true;
}
//后插法
bool insert_black(LinkList*& L, LinkNode*& node) {if (!L||!node) {return false;}LinkNode* p;p = L;while (p->next) {p = p->next;}node->next = NULL;p->next = node;node->pre = p;return true;
}
//遍历
void printLink(LinkList*& L) {if (!L) {cout << "链表为空" << endl;return;}LinkNode* p;p = L;cout << endl;cout << "顺序输出: ";while (p->next) {cout << p->next->data << " ";p = p->next;}cout << endl;cout << "逆向输出: ";while (p->pre) {cout << p->data<< " ";p = p->pre;}
}
//在随意位置插入
bool insert_every(LinkList*& L, int pos, int& value) {if (!L) {return false;}LinkNode* p;LinkNode* s;p = L;int index = 0;while (p->next&&index <pos-1) {p = p->next;index++;}s = new LinkNode;s->data = value;p->next->pre = s;s->next = p->next;p->next = s;s->pre = p;return true;
}
//输出随意位置的值
bool print_index_value(LinkList*& L, int pos, int& value) {if (!L) {return false;}LinkNode* p;p = L->next;int index = 0;while (p&&index<pos-1) {p = p->next;index++;}value = p->data;return true;
}
//删除指定节点的值
bool delete_index_value(LinkList*& L, int pos) {if (!L) {return false;}LinkList* p;p = L->next;int index = 0;while (p&&index<pos-1) {p = p->next;index++;}if (!p || index>pos) {//判断需要删除值的合法性return false;}if (!p->next) {p->pre->next = NULL;delete p;return true;}p->pre->next = p->next;//此时的p是需要删除的节点,所以需要将他的前一个节点的下一个位置,指向p的下一个位置p->next->pre = p->pre;//p的下一个位置的前一个节点就是,需要删除的节点p的前一个节点;delete p;return true;
}
int main(void) {LinkList* L;LinkNode* node;//初始化initList(L);/*cout << "使用前插法: " << endl;for (int i = 0; i < 10; i++) {node = new LinkNode;node->data = i;node->next = NULL;node->pre = NULL;insert_front(L, node);}printLink(L);*/cout << endl;cout << "使用尾插法: " << endl;for (int i = 0; i < 10; i++) {node = new LinkNode;node->data = i;node->next = NULL;node->pre = NULL;insert_black(L, node);}printLink(L);int pos,value;cout << endl;cout << "请输入需要插入的位置和值";cin >> pos >> value;if (insert_every(L,pos,value)) {cout << "插入成功" << endl;printLink(L);}else {cout << "插入失败" << endl;printLink(L);}cout << endl;int pos1, value1=0;cout << "请输入你需要查找的位置";cin >> pos1;if (print_index_value(L,pos1,value1)) {cout << "位置" << pos1 << "的值是: " << value1 << endl;}//删除指定节点cout << "请输入你需要删除的位置";int pos2;cin >> pos2;if (delete_index_value(L,pos2)) {cout << "删除成功" << endl;printLink(L);}else {cout << "删除失败" << endl;}}

 共享链表

#include <iostream>
using namespace std;typedef struct DoubleLink {struct DoubleLink* pre;struct DoubleLink* next;
}LinkList ,LinkNode;
typedef struct {int elem;LinkNode node;
}DoubleTime;
typedef struct {char elem;int i;LinkNode node1;
}struct1;
//初始化链表
bool initLink(LinkList& L) {//因为node在结构体申请新空间的时候就已经被初始化了L.next = NULL;L.pre = NULL;return true;
}
//后插法
bool insert_black(LinkList& L, LinkNode& node) {LinkList* p = NULL;p = &L;while (p->next) {p = p->next;}p->next = &node;node.pre = p;node.next = NULL;return true;
}
int main(void) {DoubleTime* d = new DoubleTime;DoubleTime* node = NULL;initLink(d->node);d->elem = -1;cout << "请输入需要插入的个数: ";;int n;cin >> n;while (n>0) {node = new DoubleTime;node->elem = n;cout << "值是: " << node->elem << "地址值: " << &node->elem << endl;insert_black(d->node, node->node);n--;}//使用链表遍历元素int offset = offsetof(DoubleTime, node);//计算偏移量LinkList* p;p = &(d->node);while (p->next) {p = p->next;DoubleTime* tmp = (DoubleTime*)((size_t)p - offset);cout << "值是: " << tmp->elem << "地址值是: " << p << endl;}while (p) {DoubleTime* tmp1 = (DoubleTime*)((size_t)p - offset);cout << "删除的值是: " << tmp1->elem << "地址值是: " << p << endl;p = p->pre;delete tmp1;}return 0;}