柚子快报邀请码778899分享：html 【数据结构】链表
单链表操作
插入： 传入表头，待插入的值，插入的位置。其中位置
i
i
i 表示原链表第
i
−
1
i-1
i−1 到
i
i
i 之间，也可以理解为新插入的数占据原链表的
i
i
i 位置，然后原
i
i
i 位置及以后要向后移。
算法流程： ①判边界：由上定义，边界值
1
1
1 表示头节点和第一个节点的中间插入，边界值 Head->data+1 表示在最后一个元素之后插入一个数 ②表头表示链表大小的数据域Head->data++ ③链表操作通常都多定义一个p来从头节点开始进行操作 ④开始循环定位，注意while(--i)是先进行--再判断是否为
0
0
0，故循环会使 p 移动至 i-1 位置处 ⑤new出一个新节点，先使新节点s->next=p->next表示新节点指向原来的第
i
i
i 个节点，然后p->next=s表示原第
i
−
1
i-1
i−1 个节点指向新节点。图示如下：
bool insertNode(Node* Head,int val,int i){
if(i<1||i>Head->data+1){
puts("error");
return false;
}
Head->data++;
Node* p=Head;
while(--i){
p=p->next;
}
Node* s=new Node;
s->data=val;
s->next=p->next;
p->next=s;
return true;
}
删除： 传入表头，删除的位置，其中
i
i
i 的边界和插入操作比起来右边界缩短了一节，因为删除操作也是通过对
i
−
1
i-1
i−1 操作来删除节点
i
i
i 的
算法流程： ①判边界，同插入操作 ②表头表示链表大小的数据-- ③循环移动，同插入，最终定位到
i
−
1
i-1
i−1 ④先将第
i
i
i 个节点用指针表示出来，即 Node* s=p->next，然后让第
i
−
1
i-1
i−1 个节点指向第
i
+
1
i+1
i+1 个节点，即p->next=s->next即可
bool removeNode(Node* Head,int i){
if(i<1||i>Head->data){
puts("error");
return false;
}
Node* p=Head;
p->data--;
while(--i){
p=p->next;
}
Node* s=p->next;
p->next=s->next;
delete s;
return true;
}
打印整个链表： 传入表头，循环遍历。注意要先输出再p=p->next，不然输出最后的时候会遇上一个没有数据的空指针
算法流程： ①定义指针Node* p=Head->next使其指向第一个节点 ②输出当前数据域，然后让指针指向下一个（不能反）
void printList(Node* Head){
Node* p=Head->next;
while(p){
cout<
p=p->next;
}
cout< } 创建链表： 一直调用插入即可 void createList(Node* &Head,int* value,int n){ Node* p=Head; for(int i=n;i>=1;i--){ insertNode(Head,value[i],1); } } 删除整个链表： 读取头节点储存的节点个数，循环调用删除 void deleteList(Node* Head){ int n=Head->data; while(n--){ removeNode(Head,1); } } 循环链表： 将最后一个节点的指针域由空改为指向头节点，可以创建头指针时让它指向自己，然后其他操作一致即可实现。 DS单链表–存储结构与操作 #include using namespace std; struct Node{ int data; Node* nxt; }; bool insertNode(Node* Head,int val,int i){ if(i<1||i>Head->data+1){ puts("error"); return false; } Head->data++; Node* p=Head; while(--i){ p=p->nxt; } Node* s=new Node; s->data=val; s->nxt=p->nxt; p->nxt=s; return true; } bool removeNode(Node* Head,int i){ if(i<1||i>Head->data){ puts("error"); return false; } Node* p=Head; p->data--; while(--i){ p=p->nxt; } Node* s=p->nxt; p->nxt=s->nxt; delete s; return true; } void printList(Node* Head){ Node* p=Head->nxt; while(p){ cout< p=p->nxt; } cout< } void createList(Node* &Head,int value[],int n){ Node* p=Head; for(int i=n;i>=1;i--){ insertNode(Head,value[i-1],1); } } void findVal(Node* Head,int i){ if(i<1||i>Head->data){ puts("error"); return ; } Node* p=Head; while(i--){ p=p->nxt; } cout< } int main(){ int n; cin>>n; int* a=new int[n]; for(int i=0;i cin>>a[i]; Node* Head=new Node; Head->nxt=NULL,Head->data=0; createList(Head,a,n); printList(Head); int pos,val; cin>>pos>>val; if(insertNode(Head,val,pos)) printList(Head); cin>>pos>>val; if(insertNode(Head,val,pos)) printList(Head); cin>>pos; if(removeNode(Head,pos)) printList(Head); cin>>pos; if(removeNode(Head,pos)) printList(Head); cin>>pos; findVal(Head,pos); cin>>pos; findVal(Head,pos); return 0; } B. DS单链表–结点交换 #include using namespace std; struct Node{ int data; Node* nxt; }; bool insertNode(Node* Head,int val,int i){ if(i<1||i>Head->data+1){ puts("error"); return false; } Head->data++; Node* p=Head; while(--i){ p=p->nxt; } Node* s=new Node; s->data=val; s->nxt=p->nxt; p->nxt=s; return true; } bool removeNode(Node* Head,int i){ if(i<1||i>Head->data){ puts("error"); return false; } Node* p=Head; p->data--; while(--i){ p=p->nxt; } Node* s=p->nxt; p->nxt=s->nxt; delete s; return true; } void printList(Node* Head){ Node* p=Head->nxt; while(p){ cout< p=p->nxt; } cout< } void createList(Node* &Head,int value[],int n){ Node* p=Head; for(int i=n;i>=1;i--){ insertNode(Head,value[i-1],1); } } void findVal(Node* Head,int i){ if(i<1||i>Head->data){ puts("error"); return ; } Node* p=Head; while(i--){ p=p->nxt; } cout< } bool swapNode(Node* Head,int i,int j){ if((i<1||i>Head->data)||(j<1||j>Head->data)){ puts("error"); return false; } Node* p1=Head; Node* p2=Head; while(--i){ p1=p1->nxt; } while(--j){ p2=p2->nxt; } Node* t1=p1->nxt; Node* t2=p2->nxt; p1->nxt=t2; p2->nxt=t1; Node* tmp=t1->nxt; t1->nxt=t2->nxt; t2->nxt=tmp; return true; } int main(){ int n; cin>>n; int* a=new int[n]; for(int i=0;i cin>>a[i]; Node* Head=new Node; Head->nxt=NULL,Head->data=0; createList(Head,a,n); printList(Head); int posa,posb; cin>>posa>>posb; if(swapNode(Head,posa,posb)) printList(Head); cin>>posa>>posb; if(swapNode(Head,posa,posb)) printList(Head); return 0; } C. DS单链表–合并 #include using namespace std; struct Node{ int data; Node* nxt; }; bool insertNode(Node* Head,int val,int i){ if(i<1||i>Head->data+1){ puts("error"); return false; } Head->data++; Node* p=Head; while(--i){ p=p->nxt; } Node* s=new Node; s->data=val; s->nxt=p->nxt; p->nxt=s; return true; } bool removeNode(Node* Head,int i){ if(i<1||i>Head->data){ puts("error"); return false; } Node* p=Head; p->data--; while(--i){ p=p->nxt; } Node* s=p->nxt; p->nxt=s->nxt; delete s; return true; } void printList(Node* Head){ Node* p=Head->nxt; while(p){ cout< p=p->nxt; } cout< } void createList(Node* &Head,int value[],int n){ Node* p=Head; for(int i=n;i>=1;i--){ insertNode(Head,value[i-1],1); } } void findVal(Node* Head,int i){ if(i<1||i>Head->data){ puts("error"); return ; } Node* p=Head; while(i--){ p=p->nxt; } cout< } Node* mergeList(Node* HeadA,Node* HeadB){ Node* HeadC=new Node; Node* pc=HeadC; HeadC->nxt=NULL,HeadC->data=0; Node* pa=HeadA->nxt; Node* pb=HeadB->nxt; while(pa!=NULL&&pb!=NULL){ if(pa->data>pb->data){ insertNode(HeadC,pb->data,HeadC->data+1); pb=pb->nxt; } else if(pa->data insertNode(HeadC,pa->data,HeadC->data+1); pa=pa->nxt; } else{ insertNode(HeadC,pa->data,HeadC->data+1); pa=pa->nxt; insertNode(HeadC,pb->data,HeadC->data+1); pb=pb->nxt; } } while(pa!=NULL){ insertNode(HeadC,pa->data,HeadC->data+1); pa=pa->nxt; } while(pb!=NULL){ insertNode(HeadC,pb->data,HeadC->data+1); pb=pb->nxt; } return HeadC; } bool swapNode(Node* Head,int i,int j){ if((i<1||i>Head->data)||(j<1||j>Head->data)){ puts("error"); return false; } Node* p1=Head; Node* p2=Head; while(--i){ p1=p1->nxt; } while(--j){ p2=p2->nxt; } Node* t1=p1->nxt; Node* t2=p2->nxt; p1->nxt=t2; p2->nxt=t1; Node* tmp=t1->nxt; t1->nxt=t2->nxt; t2->nxt=tmp; return true; } int main(){ int n; cin>>n; int* a=new int[n]; for(int i=0;i cin>>a[i]; int m; cin>>m; int* b=new int[m]; for(int i=0;i cin>>b[i]; Node* HeadA=new Node; HeadA->nxt=NULL,HeadA->data=0; createList(HeadA,a,n); Node* HeadB=new Node; HeadB->nxt=NULL,HeadB->data=0; createList(HeadB,b,m); Node* HeadC=mergeList(HeadA,HeadB); printList(HeadC); return 0; } D. DS循环链表—约瑟夫环(Ver. I - A) #include using namespace std; struct Node{ int data; Node* nxt; }; bool insertNode(Node* Head,int val,int i){ if(i<1||i>Head->data+1){ puts("error"); return false; } Head->data++; Node* p=Head; while(--i){ p=p->nxt; } Node* s=new Node; s->data=val; s->nxt=p->nxt; p->nxt=s; return true; } bool removeNode(Node* Head,int i){ if(i<1||i>Head->data){ puts("error"); return false; } Node* p=Head; p->data--; while(--i){ p=p->nxt; } Node* s=p->nxt; p->nxt=s->nxt; delete s; return true; } void printList(Node* Head){ Node* p=Head->nxt; while(p){ cout< p=p->nxt; } cout< } void createList(Node* &Head,int value[],int n){ Node* p=Head; for(int i=n;i>=1;i--){ insertNode(Head,value[i],1); } while(p->nxt){ p=p->nxt; } p->nxt=Head->nxt; } void findVal(Node* Head,int i){ if(i<1||i>Head->data){ puts("error"); return ; } Node* p=Head; while(i--){ p=p->nxt; } cout< } Node* mergeList(Node* HeadA,Node* HeadB){ Node* HeadC=new Node; Node* pc=HeadC; HeadC->nxt=NULL,HeadC->data=0; Node* pa=HeadA->nxt; Node* pb=HeadB->nxt; while(pa!=NULL&&pb!=NULL){ if(pa->data>pb->data){ insertNode(HeadC,pb->data,HeadC->data+1); pb=pb->nxt; } else if(pa->data insertNode(HeadC,pa->data,HeadC->data+1); pa=pa->nxt; } else{ insertNode(HeadC,pa->data,HeadC->data+1); pa=pa->nxt; insertNode(HeadC,pb->data,HeadC->data+1); pb=pb->nxt; } } while(pa!=NULL){ insertNode(HeadC,pa->data,HeadC->data+1); pa=pa->nxt; } while(pb!=NULL){ insertNode(HeadC,pb->data,HeadC->data+1); pb=pb->nxt; } return HeadC; } bool swapNode(Node* Head,int i,int j){ if((i<1||i>Head->data)||(j<1||j>Head->data)){ puts("error"); return false; } Node* p1=Head; Node* p2=Head; while(--i){ p1=p1->nxt; } while(--j){ p2=p2->nxt; } Node* t1=p1->nxt; Node* t2=p2->nxt; p1->nxt=t2; p2->nxt=t1; Node* tmp=t1->nxt; t1->nxt=t2->nxt; t2->nxt=tmp; return true; } void JoseLoop(Node* Head,int n,int k,int s){ Node* S=Head; Node* p=Head; for(int i=0;i S=S->nxt; p=S->nxt; if(k==1){ for(int i=1;i cout< p=p->nxt; } } else{ while(p->nxt!=p){ for(int i=1;i S=p; p=p->nxt; } cout< S->nxt=p->nxt; p=p->nxt; } } cout< } int main(){ int n,k,s; while(cin>>n>>k>>s){ int* a=new int[n+1]; for(int i=1;i<=n;i++) a[i]=i; Node* Head=new Node; Head->nxt=NULL; Head->data=0; createList(Head,a,n); JoseLoop(Head,n,k,s); } return 0; } F. DS链表—学生宿舍管理（双向列表容器List） #include #include #include #include using namespace std; int main(){ list list unordered_map unordered_map unordered_map int n,m; cin>>n; for(int i=1;i<=n;i++){ string a; int b; cin>>a>>b; room.push_back(b); bk[b]++; rtop[b]=a; ptor[a]=b; } for(int i=101;i<=120;i++) if(!bk[i]) Free.push_back(i); cin>>m; while(m--){ string a; cin>>a; if(a[0]=='a'){ string b; cin>>b; for(int i=101;i<=120;i++) if(!bk[i]){ bk[i]++; int num=Free.front(); Free.pop_front(); ptor[b]=num; rtop[num]=b; room.push_front(num); break; } } else if(a[0]=='r'){ int b; cin>>b; auto it=find(room.begin(),room.end(),b); room.erase(it); // for(auto t:room) cout< // cout< Free.push_back(b); } else if(a=="display_used"){ room.sort(); int tmp=room.front(); cout< room.pop_front(); for(auto t:room){ cout<<"-"< } cout< room.push_front(tmp); } else{ int tmp=Free.front(); cout< Free.pop_front(); for(auto t:Free) cout<<'-'< Free.push_front(tmp); } } return 0; } 栈 #include using namespace std; template class Node{ public: T data; Node* nxt; }; template class Stack{ public: int MAX_size; int Cur_size; Node void Stack_Init(int x){ MAX_size=x; Top=new Node Top->nxt=NULL; Cur_size=0; } void push(T x){ if(Cur_size>MAX_size){ puts("error"); return; } Node t->data=x; t->nxt=Top; Top=t; Cur_size++; } int size(){ return Cur_size; } void pop(){ if(Cur_size==0){ puts("error"); return; } Top=Top->nxt; Cur_size--; } T top(){ if(Cur_size==0){ puts("error"); return -1; } return Top->data; } }; int main(){ Stack s.Stack_Init(10); for(int i=1;i<=5;i++) s.push(i); cout< for(int i=1;i<=2;i++) s.pop(); cout< cout< for(int i=1;i<=5;i++){ cout< s.pop(); } return 0; } 柚子快报邀请码778899分享：html 【数据结构】链表 好文推荐
发表评论