移动电商网站建设,手机网站和pc网站,wordpress 加入js,c 网站开发引擎概念 链表是线性表的链式存储方式#xff0c;逻辑上相邻的数据在计算机内的存储位置不必须相邻#xff0c; 可以给每个元素附加一个指针域#xff0c;指向下一个元素的存储位 置。 每个结点包含两个域#xff1a;数据域和指针域#xff0c;指针域存储下一个结点的地址逻辑上相邻的数据在计算机内的存储位置不必须相邻 可以给每个元素附加一个指针域指向下一个元素的存储位 置。 每个结点包含两个域数据域和指针域指针域存储下一个结点的地址因此指针指向的类型也是 结点类型 结构体定义 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 (pjpos-1) { p p-next; j; } if (!p||jpos-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 (pindexpos) { 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 (pp-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 indexpos) { p p-next; index; } if (!p-next||indexpos) {//判断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之后在进行pp-next时不用L进行重新赋值就会出问题 p L; } } 单链表的遍历 void printLink(LinkList* L){ if(!L)return false;//链表为空就没必要输出了 LinkNode *p; p L-next;//指向第一个实际的值 while (p){ //不为空的时候执行 coutp.elem ; p p-next; } cout endl; } 循环链表 解答约瑟夫问题 : 有 10 个小朋友按编号顺序 12。。。10 顺时针方向围成一圈。从 1 号开 始顺时针方向 12。。。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 indexpos-1){ p p-next; } s p-next; p-next s-next; retrun true; } 循环链表的输出 void LinkPrint(LinkList *L){ if(!L||LL-next){ cout这个链表是空的endl; return; } LinkNode *P ; p L-next;//因为需要输出值,先让节点指向第一个实际的值 while(p-next!L){ coutp-elem ; p p-next; } coutendl; } 分析:解答约瑟夫问题 初始化头结点, 使用尾插法插入十个学生编号 循环判断,当数到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 (pindexpos-1) { p p-next; index; } if (!p || indexpos) {//判断需要删除值的合法性 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 (pindexpos-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-nextindex 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-nextindex 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 (pindexpos-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 (pindexpos-1) {p p-next;index;}if (!p || indexpos) {//判断需要删除值的合法性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, value10;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 (n0) {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;}
