链表增删改查
#include <cstdio>
#include <string>
#include <sstream>
#include <iostream>
using namespace std;
int str_to_int(const string &temp)
{
int temp_int;
stringstream stream(temp);
stream>>temp_int;
return temp_int;
}
struct node
{
int data;
node * next;
};
void create(node * &L,int n)
{
L=new node;
L->next=NULL;
int elem;
node * p;
for(int i=0;i<n;i++)
{
scanf("%d",&elem);
p=new node;
p->data=elem;
p->next=L->next;
L->next=p;
}
}
void show(node * L)
{
node *p=L->next;
if(p==NULL)
{
printf("Link list is empty\n");
return ;
}
while(p!=NULL)
{
if(p->next==NULL)
{
printf("%d\n",p->data);
}
else
{
printf("%d ",p->data);
}
p=p->next;
}
}
void Delete(node * &L,int n)
{
node * pre=L;
node * p=L->next;
if(p==NULL)
{
printf("delete fail\n");
return ;
}
for(int i=0;i<n-1;i++)
{
pre=p;
p=pre->next;
}
if(p==NULL)
{
printf("delete fail\n");
return ;
}
pre->next=p->next;
free(p);
printf("delete OK\n");
}
void insert(node * &L,int n,int e)
{
node *p=L;
//每次都是要移入到插入位置的
for(int i=0;i<n-1;i++)
{
p=p->next;
if(p==NULL)
{
printf("insert fail\n");
return ;
}
}
node * q;
//关键是使用new方法
q=new node;
q->data=e;
q->next=p->next;
p->next=q;
printf("insert OK\n");
}
void get(node * L,int n)
{
node *p=L;
for(int i=0;i<n;i++)
{
p=p->next;
}
if(p==NULL)
{
printf("get fail\n");
}
else
{
printf("%d\n",p->data);
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
node * L;
create(L,n);
int row;
scanf("%d",&row);
string temp;
getchar();
for(int i=0;i<row;i++)
{
getline(cin,temp);
if(temp[0]=='s')
{
show(L);
}
else if(temp[0]=='d')
{
temp.erase(0,7);
Delete(L,str_to_int(temp));
}
else if(temp[0]=='g')
{
temp.erase(0,4);
get(L,str_to_int(temp));
}
else if(temp[0]=='i')
{
temp.erase(0,7);
int pos=temp.find(' ');
int x=str_to_int(temp.substr(0,pos));
temp.erase(0,pos+1);
insert(L,x,str_to_int(temp));
}
else
{
cout<<"error!"<<temp<<endl;
}
}
}
return 0;
}
链表选择排序法+找到新节点排序位置再插入
#include <iostream>
using namespace std;
typedef struct Node{
int sno;
int grade;
Node *next;
}Node,*List;
void create(Node * &L,int n){
L=new Node;
L->next=NULL;
//空的头结点
int x,y;
Node *p;
for(int i=0;i<n;i++){
cin>>x>>y;
p=new Node;
p->sno=x;
p->grade=y;
//头插法
p->next=L->next;
L->next=p;
}
}
void show(Node *L){
while(L->next!=NULL){
cout<<L->next->sno<<" "<<L->next->grade<<endl;
L=L->next;
}
}
void sortL(Node *&L){
Node *p,*q,*small;
int temp1,temp2;
//选择排序，找出最小的，while已经不够用
for(p=L->next;p->next!=NULL;p=p->next){
//果然是将第一个值当做最小
small=p;
//类似于i，j，指针（j）q向后寻找，最小值放在i（p）
for(q=p->next;q!=NULL;q=q->next){
if(q->sno<small->sno){
small=q;
}
}
if(small!=p){
temp1=p->sno;
temp2=p->grade;
p->sno=small->sno;
p->grade=small->grade;
small->sno=temp1;
small->grade=temp2;
}
}
}
//链表排序和合并
int main()
{
int n,m;
while(cin>>n>>m){
Node *L1,*L2;
create(L1,n+m);
sortL(L1);
show(L1);
}
return 0;
}
#include <cstdio>
struct node
{
int number;
int grade;
node * next;
};
int main()
{
int m,n;
while(~scanf("%d %d",&m,&n))
{
node * L=new node;
L->next=NULL;
for(int i=0;i<m+n;i++)
{
node * temp=new node;
scanf("%d %d",&temp->number,&temp->grade);
node * pre=L;
node * p=L->next;
while(p!=NULL)
{
if(temp->number<p->number)
{
break;
}
else
{
pre=p;
p=p->next;
}
}
temp->next=pre->next;
pre->next=temp;
}
node * p=L->next;
while(p!=NULL)
{
printf("%d %d\n",p->number,p->grade);
p=p->next;
}
}
return 0;
}
单循环链表+合并
#include <cstdio>
struct node
{
int data;
node * next;
};
int main()
{
int m,n;
while(~scanf("%d",&m))
{
node * L1=new node;
L1->next=NULL;
node * rear1=L1;
for(int i=0;i<m;i++)
{
node * temp=new node;
scanf("%d",&temp->data);
rear1->next=temp;
temp->next=L1;
rear1=rear1->next;
}
scanf("%d",&n);
node * L2=new node;
L2->next=NULL;
node * rear2=L2;
for(int i=0;i<n;i++)
{
node * temp=new node;
scanf("%d",&temp->data);
rear2->next=temp;
temp->next=L2;
//直接找到尾部2
rear2=rear2->next;
}
rear1->next=L2->next;
rear2->next=L1;
//delete释放L2结点
delete(L2);
node * p=L1->next;
while(p!=L1)
{
if(p->next==L1)
{
printf("%d\n",p->data);
}
else
{
printf("%d ",p->data);
}
p=p->next;
}
}
return 0;
}
#include <iostream>
using namespace std;
typedef struct Node{
int data;
Node *next;
}Node,*List;
void create(Node * &L,int n){
L=new Node;
L->next=NULL;
//空的头结点
int x;
Node *p;
Node *q=L;
for(int i=0;i<n;i++){
cin>>x;
p=new Node;
p->data=x;
//尾插法
q->next=p;
q=q->next;
}
q->next=L;
}
void show(Node *L,int n){
for(int i=0;i<n;i++){
cout<<L->next->data<<" ";
L=L->next;
}
cout<<endl;
}
void mergeL(Node *&L1,Node *L2,int n,int m){
Node *p=L1,*q=L2;
for(int i=0;i<n;i++) {
p=p->next;
}
for(int i=0;i<m;i++) {q=q->next;
}
p->next=L2->next;
q->next=L1;
}
//链表排序和合并
int main()
{
int n,m;
while(cin>>n){
Node *L1,*L2;
create(L1,n);
cin>>m;
create(L2,m);
mergeL(L1,L2,n,m);
show(L1,n+m);
}
return 0;
}
链表查找和交换
#include <iostream>
using namespace std;
typedef struct Node{
int data;
Node *next;
}Node,*List;
void create(Node * &L,int n){
L=new Node;
L->next=NULL;
//空的头结点
int x;
Node *p;
Node *q=L;
for(int i=0;i<n;i++){
cin>>x;
p=new Node;
p->data=x;
//尾插法
q->next=p;
q=q->next;
q->next=NULL;
}
}
void show(Node *L){
while(L->next!=NULL){
cout<<L->next->data<<" ";
L=L->next;
}
cout<<endl;
}
void findL(Node *&L,int x){
Node *pre=L;
Node *p=L->next;
int temp;
while(p->data<x){
pre=p;
p=p->next;
}
if(x==p->data){
cout<<x<<endl;
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
}else {
Node *s=new Node;
s->data=x;
s->next=p;
pre->next=s;
cout<<"no"<<endl;
}
}
//链表排序和合并
int main()
{
int n,m;
while(cin>>n>>m){
Node *L1;
create(L1,m);
findL(L1,n);
show(L1);
}
return 0;
}
链表如何删除最大值，排序，释放结点
#include <iostream>
#include <stdlib.h>
using namespace std;
typedef struct Node{
int data;
Node *next;
}Node;
Node *InitialList(){
Node *L;
L=(Node *)malloc(sizeof(Node));
L->next=NULL;
return L;
}
Node *createList(Node *List,int data){
Node *p=List;
Node *newNode;
newNode=(Node *)malloc(sizeof(Node));
newNode->data=data;
while(p->next){
p=p->next;
}
p->next=newNode;
p=p->next;
p->next=NULL;
//老师忘记了返回
//老师忘记了返回
return List;
}
//找出最大值，就应该是找到最大值的位置！！
//删除成功
Node *Delete_max(Node *List){
Node *q=List->next;
Node *pre=List;
Node *p=List->next;
int maxL=-1;
while(p->next){
if(p->data>maxL){
maxL=p->data;
}
p=p->next;
}
while(q->data!=maxL){
q=q->next;
pre=pre->next;
}
//如何删除
pre->next=q->next;
free(q);
cout<<maxL<<endl;
return List;
}
//排序不用交换结点，只需要交换数字,很重要！！
Node *sort_List(Node *List){
Node *p,*q,*small;
int temp;
//终于搞好了for循环，主要是边界问题
for(p=List->next;p->next!=NULL;p=p->next)
{
small=p;
//链表循环如何描写,循环边界的控制
for(q=p->next;q!=NULL;q=q->next)
{
//选择交换法最适合链表。选择最小的和当前的交换
if(q->data<small->data)
small=q;
}
if(small!=p){
temp=p->data;
p->data=small->data;
small->data=temp;
}
}
return List;
}
int main(){
Node *L;
L=InitialList();
int x;
while(cin>>x){
L=createList(L,x);
char ch=getchar();
if(ch=='\n') break;
}
//终于成功打印了，按照自己的理解
L=Delete_max(L);
L=sort_List(L);
while(L->next){
Node *temp=L->next;
free(L);
L=temp;
//一开始十个空节点，之后才有值
cout<<L->data<<" ";
}
}
循环链表删除结点
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}LNode,*LinkList;
LinkList createList(int a[],int len){//创建单链表；
LinkList L,p,r;
int i;
if(len<=0){
return NULL;
}
L=(LinkList)malloc(sizeof(LNode));
L->data=a[0];
p=L;
for(i=1;i<len;i++){
r=(LinkList)malloc(sizeof(LNode));
r->data=a[i];
p->next=r;
p=r;
}
p->next=NULL;//表尾；
return L;
}
LinkList changeList(LinkList L){//把单链表变成单循环链表；
LinkList p;
p=L;
while(p->next!=NULL){
p=p->next;//p移至表尾；
}
p->next=L;
return L;
}
LinkList deleteLNode(LinkList L){//从链表中删除结点；
LinkList p,r;
int count=1;
p=L;
while(count<=16){
r=p;//r指向前驱；
p=p->next;//p移至第17个结点；
count++;
}
r->next=p->next;
free(p);
return r->next;//新的头结点；
}
void display(LinkList L){//输出单链表；
if(L!=NULL){
LinkList p;
p=L;
while(p!=NULL){
printf("%d ",p->data);
p=p->next;
}
}
}
int main(){
int a[21],i;
LinkList L,p;
for(i=0;i<21;i++){
a[i]=i+1;
}
L=createList(a,21);
L=changeList(L);
//L=deleteLNode(L);
while(L->next!=L){
L=deleteLNode(L);
}
printf("链表中最后剩下的结点是：%d\n",L->data);
//display(L);
}
链表中的排序操作，链表复制s[k]用法
1 78 90 56
2 89 56 97
3 78 97 95
0
/*输入学生信息：学号，三门课程的成绩，学号为0时结束，将其存储在链表A中，从中找出分数大于平均分的学生，并将该学生信息按平均分降序排列存入到链表B中，最后输出链表B*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{char xuehao[20];
int chengji[3];
float av;
struct node *next;
}stud,*UerInfo;
int main()
{
UerInfo ui;
ui=(UerInfo)malloc(sizeof(stud));
//多个指针指针用完位置变化了
UerInfo p=ui;
UerInfo q=ui;
printf("input students' information:\n");
int cnt=0;
while (1)
{
printf("input 学号：");
scanf("%s",ui->xuehao);
if(strcmp(ui->xuehao,"0")==0)
break;
printf("input 成绩：");
scanf("%d",&ui->chengji[0]);
printf("input 成绩：");
scanf("%d",&ui->chengji[1]);
printf("input 成绩：");
scanf("%d",&ui->chengji[2]);
ui->av=((ui->chengji[0]+ui->chengji[1]+ui->chengji[2])/3);
//创建了新节点
//创建了新节点
ui->next=(UerInfo)malloc(sizeof(stud));
ui=ui->next;
cnt++;
}
int chengji1=0;
int chengji2=0;
int chengji3=0;
while (p&&strcmp(p->xuehao,"0")!=0)
{
//三科成绩相加
chengji1+=p->chengji[0];
chengji2+=p->chengji[1];
chengji3+=p->chengji[2];
p=p->next;
}
float chengji1av=0.0;
float chengji2av=0.0;
float chengji3av=0.0;
float avfinal=0.0;
if(cnt)
{
//算3可平均分和最终评分，平均分计算方法，各科平均数除以三科
chengji1av=(float)chengji1/(float)cnt;
chengji2av=(float)chengji2/(float)cnt;
chengji3av=(float)chengji3/(float)cnt;
avfinal=(chengji1av+chengji2av+chengji3av)/3;
}
printf("高于平均分的有：\n");
UerInfo s;
//复制链表
s=(UerInfo)malloc(cnt*sizeof(stud));
int k=0;
while (q&&strcmp(q->xuehao,"0")!=0)
{
//如何借用s[k].复制链表
s[k].av=q->av;
s[k].chengji[0]=q->chengji[0];
s[k].chengji[1]=q->chengji[1];
s[k].chengji[2]=q->chengji[2];
strcpy(s[k].xuehao,q->xuehao);
k++;
if(q->av>avfinal)
{
//输出高于平均分的学生
printf("%s\n",q->xuehao);
printf("%f\n",q->av);
}
q=q->next;
}
printf("\n降序排列如下：\n");
//如何复制链表
int l,m;
stud temps;
//选择排序，每次选出最大的
for (l=0;l<cnt-1;l++)
{
for (m=l+1;m<cnt;m++)
{
if(s[l].av<s[m].av)
{
//可怕的交换
temps.chengji[0]=s[l].chengji[0];
temps.chengji[1]=s[l].chengji[1];
temps.chengji[2]=s[l].chengji[2];
strcpy(temps.xuehao,s[l].xuehao);
s[l].chengji[0]=s[m].chengji[0];
s[l].chengji[1]=s[m].chengji[1];
s[l].chengji[2]=s[m].chengji[2];
strcpy(s[l].xuehao,s[m].xuehao);
s[m].chengji[0]=temps.chengji[0];
s[m].chengji[1]=temps.chengji[1];
s[m].chengji[2]=temps.chengji[2];
strcpy(s[m].xuehao,temps.xuehao);
}
}
}
for (int i=0;i<cnt;i++)
{
printf("学号：%s\n",s[i].xuehao);
printf("成绩：%d\n",s[i].chengji[0]);
printf("成绩：%d\n",s[i].chengji[1]);
printf("成绩：%d\n",s[i].chengji[2]);
}
return 0;
}
静态链表实现链表部分反转
//输入形式
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
#include <bits/stdc++.h>
using namespace std;
struct node{
int address;
int data;
int next;
};
int main()
{
int N,first,K;
vector<node> shunxu;
vector<node> rev;
cin>>first>>N>>K;
//如何给结点组输入值
node temp;
node addr[100000];
//由于结点的下标是五位数
for(int i=0;i<N;i++){
cin>>temp.address>>temp.data>>temp.next;
addr[temp.address]=temp;
}
//first是头结点下标,接下来就是考虑怎样将分散结点联系起来
int nextAdd=first;
while(nextAdd!=-1){
//我傻了@@，存储起来就好
shunxu.push_back(addr[nextAdd]);
nextAdd=addr[nextAdd].next;
}
int size=shunxu.size(); //输入结点可能有些不在链表中，记录下链表长度
int tempInt=K-1; //翻转个数
while(tempInt<size){
for(int i=tempInt;i>tempInt-K;i--){
rev.push_back(shunxu[i]);
//反转链表，每次反转K个，不足K个反转并退出循环
}
tempInt=tempInt+K;
}
for(int i=tempInt-K+1;i<size;i++){
rev.push_back(shunxu[i]);
//最后没有反转的复制
}
for(int i=0;i<size-1;i++){
rev[i].next=rev[i+1].address;
//如何修改next值，改为下一个元素的Address
printf("%05d %d %05d\n",rev[i].address,rev[i].data,rev[i].next);
}//最后一个结点的处理办法--单独~~
printf("%05d %d %d\n",rev[size-1].address,rev[size-1].data,-1);
return 0;
}
