#include <iostream>
using namespace std;
struct LinkNode{
int data;
LinkNode* next;
};
int InitLink_L(LinkNode*& L) { //创建空链表
L = new LinkNode;
if (L == 0) return 0;
L->next = 0;
return 1;
}
int PushHead_LinkNode(LinkNode*& L, int x) { //在链表头插入元素x
LinkNode* p = new LinkNode;
if (p == 0) return 0;
p->data = x;
p->next = L->next;
L->next = p;
return 1;
}
void PrintLink_L(LinkNode* L) { //打印链表
LinkNode* p;
p = L->next;
while (p) {
cout << p->data;
p = p->next;
if (p) cout << ' ';
}
cout << endl;
}
void PopHead_LinkNode(LinkNode*& L) { //删除第一个结点
LinkNode* p;
if (L->next) {
p = L->next;
L->next = p->next;
delete p;
}
}
void Clear_LinkNode(LinkNode*& L) { //清空链表元素，不包括头结点
while (L->next) {
PopHead_LinkNode(L);
}
}
void Free_LinkList(LinkNode*& L) {
while (L->next) {
PopHead_LinkNode(L);
}
delete L;
L = 0;
}
int Length_LinkList(LinkNode* L) { //计算单链表的长度
LinkNode* p;
p = L->next;
int len = 0;
while (p) {
len++;
p = p->next;
}
return len;
}
LinkNode* FindAddress_LinkList(LinkNode* L, int i) { //查找单链表第i个结点并返回指针，否则返回空指针
if (i<1 || i>Length_LinkList(L)) return 0;
LinkNode* p;
p = L;
int j = 0;
while (j < i) {
p = p->next;
j++;
}
return p;
}
LinkNode* FindAddress_LinkList2(LinkNode* L, int i) { //查找单链表第i个结点并返回指针，否则返回空指针
LinkNode* p;
int j = 1;
if (i <= 0)
return 0;
p = L;
while (1){
if (p == 0)
return 0;
if (i == j)
return p;
p = p->next;
j++;
}
}
void Insert_LinkNode(LinkNode*& L, int i, int x) { //在第i个位置插入x,不包括链表尾部
if (i < 0 || i > Length_LinkList(L)) return;
LinkNode* p;
if (i == 1)
p = L;
else
p = FindAddress_LinkList2(L, i - 1); //让p指向第i-1个元素
PushHead_LinkNode(p, x); //将x插入以p为头结点的链表头部
}
void Insert_LinkNode2(LinkNode*& L, int i, int x) { //在第i个位置插入x，包括链表尾部
if (i < 0 || i > Length_LinkList(L) + 1) return;
LinkNode* p;
if (i == Length_LinkList(L) + 1) {
LinkNode* q = new LinkNode;
q->data = x;
q->next = 0;
p = L->next;
while (p->next)
p = p->next;
p->next = q;
}
else {
if (i == 1)
p = L;
else
p = FindAddress_LinkList2(L, i - 1); //让p指向第i-1个元素
PushHead_LinkNode(p, x); //将x插入以p为头结点的链表头部
}
}
int DeleteLink_L(LinkNode*& L, int i) { //删除第i个结点
if (i<0 || i>Length_LinkList(L)) return 0;
LinkNode* p;
if (i == 1)
p = L;
else
p = FindAddress_LinkList(L, i - 1); //让p指向第i-1个元素
PopHead_LinkNode(p); //将删除以p为头结点的链表头部
return 1;
}
LinkNode* Search_LinkList(LinkNode* L, int x) { //在单链表中查找x若存在返回指针，否则返回空指针
LinkNode* p;
p = L->next;
while (p) {
if (p->data == x)
return p;
p = p->next;
}
return 0;
}
void UnionLinks(LinkNode* LA, LinkNode* LB, LinkNode*& LC) { //合并链表,合并后依然有序,原来的链表不再存在
LinkNode* a, * b, * c;
c = LC;
a = LA->next; delete LA; LA = 0;
b = LB->next; delete LB; LB = 0;
while (a && b) {
if (a->data <= b->data) {
c->next = a;
c = c->next;
a = a->next;
}
else {
c->next = b;
c = c->next;
b = b->next;
}
if (a) {
c->next = a;
}
if (b) {
c->next = b;
}
}
}
void Merge_LinkList(LinkNode*& LA, LinkNode*& LB, LinkNode*& LC) { //合并链表,合并后依然有序,原来的链表不再存在
LinkNode* a, * b, * c;
c = LC;
a = LA->next; delete LA; LA = 0;
b = LB->next; delete LB; LB = 0;
while (a && b) {
if (a->data <= b->data) {
LA = a->next;
c->next = a;
a = LA;
c = c->next;
}
else {
LB = b->next;
c->next = b;
b = LB;
c = c->next;
}
}
if (a) {
c->next = a;
}
if (b) {
c->next = b;
}
}
int main() {
LinkNode* L;
InitLink_L(L);
PushHead_LinkNode(L, 1);
PushHead_LinkNode(L, 5);
PushHead_LinkNode(L, 3);
PushHead_LinkNode(L, 4);
PrintLink_L(L);
// Insert_LinkNode(L, 2, 8);
cout << FindAddress_LinkList(L, 1)->data;
// PrintLink_L(L);
return 0;
}
/*
int main() {
LinkNode* LA, * LB, * LC;
InitLink_L(LA);
InitLink_L(LB);
InitLink_L(LC);
PushHead_LinkNode(LA, 9);
PushHead_LinkNode(LA, 7);
PushHead_LinkNode(LA, 5);
PushHead_LinkNode(LA, 3);
PushHead_LinkNode(LA, 1);
PushHead_LinkNode(LB, 8);
PushHead_LinkNode(LB, 6);
PushHead_LinkNode(LB, 4);
PushHead_LinkNode(LB, 2);
PrintLink_L(LA);
PrintLink_L(LB);
Merge_LinkList(LA, LB, LC);
// UnionLinks(LA, LB, LC);
PrintLink_L(LC);
return 0;
}
*/
/*
int main() {
LinkNode* L;
InitLink_L(L);
PushHead_LinkNode(L, 1);
PushHead_LinkNode(L, 5);
PushHead_LinkNode(L, 3);
PushHead_LinkNode(L, 4);
PrintLink_L(L);
cout << Length_LinkList(L) << endl;
cout << Search_LinkList(L, 5) << endl;
cout << FindAddress_LinkList(L, 2) << endl;
Insert_LinkNode(L, 5, 7);
PrintLink_L(L);
Insert_LinkNode2(L, 5, 7);
PrintLink_L(L);
DeleteLink_L(L, 2);
PrintLink_L(L);
PopHead_LinkNode(L);
PrintLink_L(L);
Clear_LinkNode(L);
cout << "**" << L << endl;
Free_LinkList(L);
cout << "**" << L << endl;
return 0;
}
*/
