实现含头结点的单链表
属性包括：data数据域、next指针域
操作包括：插入、删除、查找
注意：单链表不是数组，所以位置从1开始对应首结点，头结点不放数据
第1行先输入n表示有n个数据，接着输入n个数据
第2行输入要插入的位置和新数据
第3行输入要插入的位置和新数据
第4行输入要删除的位置
第5行输入要删除的位置
第6行输入要查找的位置
第7行输入要查找的位置
数据之间用空格隔开，
第1行输出创建后的单链表的数据
每成功执行一次操作（插入或删除），输出执行后的单链表数据
每成功执行一次查找，输出查找到的数据
如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出单链表
样例查看模式?
正常显示查看格式
6?11?22?33?44?55?66
3?777
1?888
1
11
0
5
11?22?33?44?55?66?
11?22?777?33?44?55?66?
888?11?22?777?33?44?55?66?
11?22?777?33?44?55?66?
error
error
44
#include<iostream>
using namespace std;
struct node
{
int data;
node* next;
node()
{
data = 0;
next = NULL;
}
};
class linklist
{
node* root;
int n;
public:
linklist()
{
cin >> n;
//注意root初始！
root = new node;
node* t = root;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
node* p = new node;
p->data = x;
t->next = p;
t = p;//注意向后！
}
display();
}
void Insert(int idx, int d)
{
if (idx<1 || idx>n + 1)
{
cout << "error" << endl;
return;
}
//idx从1开始
node* q = new node;
q = root;
node* t = new node;
t->data = d;
for (int i = 1; i <idx; i++)
{
q = q->next;
}
t->next = q->next;
q->next = t;//不用把t删除了！
n++;
display();
}
void Delete(int idx)
{
if (idx<1 || idx>n)
{
cout << "error" << endl;
return;
}
node* q = new node;
q = root;
for (int i = 1; i < idx; i++)
{
q = q->next;
}
node* t = new node;
t = q->next;
q->next = t->next;
delete t;
n--;
display();
}
void Find(int idx)
{
if (idx<1 || idx>n)
{
cout << "error" << endl;
return;
}
node* q = new node;
q = root;
for (int i = 1; i <= idx; i++)
{
q = q->next;
}
cout << q->data << endl;
}
void display()
{
node* q = new node;
q = root;
for (int i = 1; i <= n; i++)
{
q = q->next;
cout << q->data << " ";
}
cout << endl;
}
};
int main()
{
linklist l;
for (int i = 0; i < 2; i++)
{
int x, y;
cin >> x >> y;
l.Insert(x, y);
}
for (int i = 0; i < 2; i++)
{
int x;
cin >> x;
l.Delete(x);
}
for (int i = 0; i < 2; i++)
{
int x;
cin >> x;
l.Find(x);
}
return 0;
}用C++实现含头结点的单链表，然后实现单链表的两个结点交换位置。
注意不能简单交换两个结点包含数据，必须通过修改指针来实现两个结点的位置交换
交换函数定义可以参考：
swapNode（int ?pa, int pb) ?//pa和pb表示两个结点在单链表的位置序号
swapNode (ListNode * p, ListNode * q) ?//p和q表示指向两个结点的指针
第1行先输入n表示有n个数据，接着输入n个数据
第2行输入要交换的两个结点位置
第3行输入要交换的两个结点位置
第一行输出单链表创建后的所有数据，数据之间用空格隔开
第二行输出执行第1次交换操作后的单链表数据，数据之间用空格隔开
第三行输出执行第2次交换操作后的单链表数据，数据之间用空格隔开
如果发现输入位置不合法，输出字符串error，不必输出单链表
样例查看模式?
正常显示查看格式
5?11?22?33?44?55
1?4
2?6
11?22?33?44?55?
44?22?33?11?55?
error
#include<iostream>
using namespace std;
struct node
{
int data;
node* next;
node()
{
data = 0;
next = NULL;
}
};
class linklist
{
node* root;
int n;
public:
linklist()
{
cin >> n;
//注意root初始！
root = new node;
node* t = root;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
node* p = new node;
p->data = x;
t->next = p;
t = p;//注意向后！
}
display();
}
void Insert(int idx, int d)
{
if (idx<1 || idx>n + 1)
{
cout << "error" << endl;
return;
}
//idx从1开始
node* q = new node;
q = root;
node* t = new node;
t->data = d;
for (int i = 1; i < idx; i++)
{
q = q->next;
}
t->next = q->next;
q->next = t;//不用把t删除了！
n++;
display();
}
void Delete(int idx)
{
if (idx<1 || idx>n)
{
cout << "error" << endl;
return;
}
node* q = new node;
q = root;
for (int i = 1; i < idx; i++)
{
q = q->next;
}
node* t = new node;
t = q->next;
q->next = t->next;
delete t;
n--;
display();
}
int Find(int idx)
{
if (idx<1 || idx>n)
{
cout << "error" << endl;
return -1;
}
node* q = new node;
q = root;
for (int i = 1; i <= idx; i++)
{
q = q->next;
}
return q->data;
}
void display()
{
node* q = new node;
q = root;
for (int i = 1; i <= n; i++)
{
q = q->next;
cout << q->data << " ";
}
cout << endl;
}
void Swap(int x, int y)
{
if (x<1 || x>n || y < 1 || y>n)
{
cout << "error" << endl;
return;
}
//确保x<=y;
if (x > y)swap(x, y);
node* a = new node;
a->data = Find(x);
node* b = new node;
b->data = Find(y);
node* q = new node;
q = root;
for (int i = 1; i <= n; i++)
{
if (i==1&&x==1)
{
b->next = q->next->next;
q->next = b;
q = q->next;
continue;
}
q = q->next;
if (i == x-1)
{
b->next = q->next->next;
q->next = b;
}
if (i == y - 1)
{
a->next = q->next->next;
q->next = a;
break;
}
}
display();
}
};
int main()
{
linklist l;
for (int i = 0; i < 2; i++)
{
int x, y;
cin >> x >> y;
l.Swap(x, y);
}
return 0;
}假定两个单链表是递增有序，定义并实现以下函数，完成两个单链表的合并，继续保持递增有序
int LL_merge(ListNode *La, ListNode *Lb)
第1行先输入n表示有n个数据，接着输入n个数据
第2行先输入m表示有M个数据，接着输入m个数据
输出合并后的单链表数据，数据之间用空格隔开
样例查看模式?
正常显示查看格式
3?11?33?55
4?22?44?66?88
11?22?33?44?55?66?88?
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{
int data;
node* next;
node()
{
data = 0;
next = NULL;
}
};
class linklist
{
node* root;
int n;
public:
linklist()
{
cin >> n;
//注意root初始！
root = new node;
node* t = root;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
node* p = new node;
p->data = x;
t->next = p;
t = p;//注意向后！
}
}
void Insert(int idx, int d)
{
if (idx<1 || idx>n + 1)
{
cout << "error" << endl;
return;
}
//idx从1开始
node* q = new node;
q = root;
node* t = new node;
t->data = d;
for (int i = 1; i < idx; i++)
{
q = q->next;
}
t->next = q->next;
q->next = t;//不用把t删除了！
n++;
display();
}
void Delete(int idx)
{
if (idx<1 || idx>n)
{
cout << "error" << endl;
return;
}
node* q = new node;
q = root;
for (int i = 1; i < idx; i++)
{
q = q->next;
}
node* t = new node;
t = q->next;
q->next = t->next;
delete t;
n--;
display();
}
int Find(int idx)
{
if (idx<1 || idx>n)
{
cout << "error" << endl;
return -1;
}
node* q = new node;
q = root;
for (int i = 1; i <= idx; i++)
{
q = q->next;
}
return q->data;
}
void display()
{
node* q = new node;
q = root;
for (int i = 1; i <= n; i++)
{
q = q->next;
cout << q->data << " ";
}
cout << endl;
}
void Swap(int x, int y)
{
if (x<1 || x>n || y < 1 || y>n)
{
cout << "error" << endl;
return;
}
//确保x<=y;
if (x > y)swap(x, y);
node* a = new node;
a->data = Find(x);
node* b = new node;
b->data = Find(y);
node* q = new node;
q = root;
for (int i = 1; i <= n; i++)
{
if (i==1&&x==1)
{
b->next = q->next->next;
q->next = b;
q = q->next;
continue;
}
q = q->next;
if (i == x-1)
{
b->next = q->next->next;
q->next = b;
}
if (i == y - 1)
{
a->next = q->next->next;
q->next = a;
break;
}
}
display();
}
friend void ll_merge(linklist x, linklist y)
{
node* xr = x.root;
node* yr = y.root;
vector<int>mm;
xr = xr->next;
while (xr)
{
mm.push_back(xr->data);
xr = xr->next;
}
yr = yr->next;
while (yr)
{
mm.push_back(yr->data);
yr = yr->next;
}
sort(mm.begin(), mm.end());
for (int i = 0; i < mm.size(); i++)
{
cout << mm[i] << " ";
}
cout << endl;
}
};
int main()
{
linklist x;
linklist y;
ll_merge(x, y);
return 0;
}N个人坐成一个圆环（编号为1 - N），从第S个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。
例如：N = 3，K = 2，S = 1。2号先出列，然后是1号，最后剩下的是3号。
要求使用循环链表实现。
测试数据有多组
每组包括3个数N、K、S，表示有N个人，从第S个人开始，数到K出列。(2 <= N <= 10^6，1 <= K <= 10,? 1 <= S <= N)
出列的人的编号
样例查看模式?
正常显示查看格式
13?3?1
3?2?1
3?6?9?12?2?7?11?4?10?5?1?8?13?
2?1?3?
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct node
{
int data;
node* next;
node* pre;
node()
{
data = 0;
next = NULL;
pre = NULL;
}
};
class circlelist
{
node* root;
int n, k, s;
public:
circlelist(int nn, int kk, int ss)
{
n = nn;
k = kk;
s = ss;
//注意root初始！
root = new node;
root->next = root;
root->pre = root;
for (int i = n; i>=1;i--)
{
node* p = new node;
p->data = i;
p->next = root->next;
root->next->pre = p;
root->next = p;
p->pre = root;
}
root=root->next;
Delete(root->pre);
n++;//加入虚头结点
}
void Delete(node* d)
{
d->pre->next = d->next;
d->next->pre = d->pre;
delete d;
n--;
}
node* Find(int idx)
{
node* q = root->next;
if (root->data == idx)
{
return root;
}
while (q != root)
{
if (q->data == idx)return q;
q = q->next;
}
return NULL;
}
void game()
{
node* q = Find(s);
int count = 0;//记录到k
while (q != q->next)
{
count++;
q = q->next;
if (count == k)
{
count = 0;
cout << q->pre->data << " ";
Delete(q->pre);
}
}
cout << q->data << " " << endl;
}
};
int main()
{
int n, k, s;
while (cin >> n >> k >> s)
{
circlelist c(n, k, s);
c.game();
}
return 0;
}对于一元多项式p(x)=p0+p1x+p2x2+…+pnxn，每个项都有系数和指数两部分，例如p2x2的系数为p2,指数为2。
编程实现两个多项式的相加。
例如5+x+2x2+3x3，-5-x+6x2+4x4，两者相加结果：8x2+3x3+4x4
其中系数5和-5都是x的0次方的系数，相加后为0，所以不显示。x的1次方同理不显示。
要求用单链表实现。
第1行：输入t表示有t组测试数据
第2行：输入n表示有第1组的第1个多项式包含n个项
第3行：输入第一项的系数和指数，以此类推输入n行
接着输入m表示第1组的第2个多项式包含m项
同理输入第2个多项式的m个项的系数和指数
参考上面输入第2组数据，以此类推输入t组
假设所有数据都是整数
对于每1组数据，先用两行输出两个原来的多项式，再用一行输出运算结果，不必考虑结果全为0的情况
输出格式参考样本数据，格式要求包括：
1.如果指数或系数是负数，用小括号括起来。
2.如果系数为0，则该项不用输出。
3.如果指数不为0，则用符号^表示，例如x的3次方，表示为x^3。
4.多项式的每个项之间用符号+连接，每个+两边加1个空格隔开。
样例查看模式?
正常显示查看格式
2
4
5?0
1?1
2?2
3?3
4
-5?0
-1?1
6?2
4?4
3
-3?0
-5?1
2?2
4
9?-1
2?0
3?1
-2?2
5?+?1x^1?+?2x^2?+?3x^3
(-5)?+?(-1)x^1?+?6x^2?+?4x^4
8x^2?+?3x^3?+?4x^4
(-3)?+?(-5)x^1?+?2x^2
9x^(-1)?+?2?+?3x^1?+?(-2)x^2
9x^(-1)?+?(-1)?+?(-2)x^1
#include<bits/stdc++.h>
using namespace std;
class node
{
public:
int xishu;
int zhishu;
node* next;
node(int a = 0, int b = 0, node* c = NULL)
{
xishu = a;
zhishu = b;
next = c;
}
};
class linknode
{
node* head;
int len;
public:
linknode()
{
head = new node;
len = 0;
}
linknode(int n)
{
len = n;
head = new node;
node* q = head;//尾指针
for (int i = 1; i <= n; i++)
{
int a, b;
cin >> a >> b;
node* p = new node(a, b);
p->next = q->next;
q->next = p;
q = q->next;
}
}
//尾插法
void linkinsert(node* s)
{
node* p = head;
while (p->next != NULL)
{
p = p->next;
}
//p(最后一个) p->next=NULL
node* pp = new node;
*pp = *s;
pp->next = p->next;
p->next = pp;
len++;
}
friend linknode operator +(linknode& la, linknode& lb)
{
linknode l;
node* p = la.head->next;
node* q = lb.head->next;
while (p && q)
{
if (p->zhishu == q->zhishu)
{
int tt = q->xishu + p->xishu;
if (tt)
{
node* s = new node(tt, p->zhishu);
l.linkinsert(s);//尾部插入
}
p = p->next;
q = q->next;
}
else if (p->zhishu < q->zhishu)
{
l.linkinsert(p);
p = p->next;
}
else
{
l.linkinsert(q);
q = q->next;
}
}
while (p)
{
l.linkinsert(p);
p = p->next;
}
while (q)
{
l.linkinsert(q);
q = q->next;
}
return l;
}
void display()
{
node* p = head->next;
while (p)
{
if (p->xishu < 0)
{
cout << "(" << p->xishu << ")";
}
else
{
cout << p->xishu;
}
if (p->zhishu > 0)
{
cout << "x^" << p->zhishu;
}
else if (p->zhishu < 0)
{
cout << "x^(" << p->zhishu << ")";
}
p = p->next;
if (p != NULL)cout << " + ";
}
cout << endl;
}
};
int main()
{
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
linknode q1(n);
q1.display();
cin >> n;
linknode q2(n);
q2.display();
(q1 + q2).display();
}
return 0;
}假设某校有20间宿舍，宿舍编号101，102，...,120。每间只住一名学生。初始部分宿舍已用。用两个链表（已用宿舍链表和可用宿舍链表）维护宿舍的管理，实现宿舍分配、宿舍交回。
约定已用宿舍链表按宿舍号升序链接。初始可用宿舍链表也按宿舍号升序链接。
宿舍分配从可用宿舍链表中摘取第一间宿舍分配给学生。学生交回的宿舍挂在可用宿舍链表最后。
备注：使用list容器或静态链表。不用考虑宿舍分配和交回不成功的情况。
初始宿舍状态，第一行输入n，表示已用宿舍n间
后跟n行数据，每行格式为：学生姓名 宿舍号?
操作次数m，后跟m行操作，操作格式如下：
assign 学生? //为学生分配宿舍，从可用宿舍链表头摘取一间宿舍，
//按宿舍号升序挂在已用宿舍链表中。
return? 宿舍号?? //学生退宿舍，删除已用宿舍链表中对应结点，
//挂在可用宿舍链表尾部。
display_free?? //输出可用宿舍链表信息。
display_used?? //输出已用宿舍链表信息。
display_free依次输出当前可用宿舍链表中的宿舍号，具体格式见样例。
display_used依次输出当前已用宿舍链表中的宿舍号，具体格式见样例。
样例查看模式?
正常显示查看格式
5
李明??103
张三??106
王五??107
钱伟??112
章立??118
8
assign?李四
assign?赵六
return?118
return?101
assign?马山
display_used
assign?林立
display_free
赵六(102)-李明(103)-马山(104)-张三(106)-王五(107)-钱伟(112)
108-109-110-111-113-114-115-116-117-119-120-118-101
#include<bits/stdc++.h>
using namespace std;
int st[200];
struct kenode
{
string name;
int num;
kenode* next;
kenode(string s = "", int a = 0, kenode* c = NULL)
{
name = s;
num = a;
next = c;
}
};
struct yinode
{
int data;
yinode* next;
yinode(int a = 0, yinode* b = NULL)
{
data = a;
next = b;
}
};
class llink
{
int kelen;
int yilen;
kenode* kehead;
yinode* yihead;
public:
llink(int n)
{
kelen = n;
kehead = new kenode;
kenode* q = kehead;
for (int i = 0; i < kelen; i++)
{
string ss;
int a;
cin >> ss >> a;
kenode* p = new kenode(ss, a);
st[a] = 1;
p->next = q->next;
q->next = p;
q = q->next;
}
yihead = new yinode;
yinode* qq = yihead;
yilen = 20 - kelen;
for (int i = 101; i <= 120; i++)
{
if (st[i] == 0)
{
yinode* pp = new yinode(i);
pp->next = qq->next;
qq->next = pp;
qq = qq->next;
}
}
}
int deleteyinode()
{
yinode* p = yihead->next;
yihead->next = p->next;
yilen--;
return p->data;
}
void addkenode(kenode* d)
{
kenode* p = kehead->next;
kenode* s = new kenode;
*s = *d;
while (p != NULL)
{
if (p->num < s->num && (p->next->num > s->num || p->next == NULL))
{
s->next = p->next;
p->next = s;
kelen++;
return;
}
p = p->next;
}
p = kehead;
d->next = p->next;
p->next = d;
kelen++;
}
void addyinode(int n)
{
yinode* p = yihead;
while (p->next != NULL)
{
p = p->next;
}
yinode* pp = new yinode(n);
pp->next = p->next;
p->next = pp;
yilen++;
}
void shifan(int n)
{
kenode* p = kehead;
while (p != NULL)
{
if (p->next->num == n)
{
addyinode(n);
p->next = p->next->next;
kelen--;
break;
}
p = p->next;
}
}
void display_used()
{
kenode* p = kehead->next;
while (p->next)
{
cout << p->name << "(" << p->num << ")-";
p = p->next;
}
cout << p->name << "(" << p->num << ")" << endl;
}
void display_free()
{
yinode* pp = yihead->next;
while (pp->next)
{
cout << pp->data << "-";
pp = pp->next;
}
cout << pp->data << endl;
}
void assign(string nn)
{
kenode* p = new kenode(nn, deleteyinode());
addkenode(p);
}
};
int main()
{
int nn;
cin >> nn;
llink ll(nn);
int m;
cin >> m;
while (m--)
{
string ss;
cin >> ss;
string nn;
if (ss == "display_used")
{
ll.display_used();
}
else if (ss == "display_free")
{
ll.display_free();
}
else if (ss == "assign")
{
cin >> nn;
ll.assign(nn);
}
else if (ss == "return")
{
int aa;
cin >> aa;
ll.shifan(aa);
}
}
return 0;
}