当前位置：首页 > news >正文

安乡网站制作百度网址导航主页

news 2025/8/11 16:51:02

安乡网站制作,百度网址导航主页,网站个免费的空间,一站式营销推广平台概念链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不必须相邻， 可以给每个元素附加一个指针域，指向下一个元素的存储位置。每个结点包含两个域：数据域和指针域，指针域存储下一个结点的地址&…

概念

链表是线性表的链式存储方式，逻辑上相邻的数据在计算机内的存储位置不必须相邻，
可以给每个元素附加一个指针域，指向下一个元素的存储位置。

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

结构体定义

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;}