一.单链表的创建
单链表的两种创建方法:尾插法
和头插法
两个数据域递增的单链表融合成一个依旧递增的单链表,很简单了注意新链表头结点的就ok了
#include <iostream>
#include<stdlib.h>
#include<algorithm>
#define maxSize 100
using namespace std;
typedef struct LNode{
int data;
struct LNode *next;
}LNode;
void createLNode1(LNode *&p,int arr[],int n){//尾插法创建单链表
LNode *s,*r;
int i;
p=(LNode *)malloc(sizeof(LNode));
p->next=NULL;//头结点
r=p;
for(i=0;i<n;i++){
s=(LNode *)malloc(sizeof(LNode));
s->data=arr[i];
r->next=s;
r=s;
}
r->next=NULL;
}
void createLNode2(LNode *&p,int arr[],int n){//头插法创建单链表
LNode *s,*r;
int i;
p=(LNode *)malloc(sizeof(LNode));
p->next=NULL;
for(i=0;i<n;i++){
s=(LNode *)malloc(sizeof(LNode));
s->data=arr[i];
s->next=p->next;
p->next=s;
}
}
void printLink(LNode *p){
LNode *q;
q=p->next;
while(q!=NULL){
printf("%d ",q->data);
q=q->next;
}
}
void merge1(LNode *p,LNode *q,LNode *&l){//把p,q两链表融合成一条链表l,并保持数据域递增
LNode *r,*s,*k;
l=(LNode *)malloc(sizeof(LNode));
l->next=NULL;//头结点
k=l;
r=p->next;//指向p链表的结点指针
s=q->next;//指向q链表的结点指针
free(p);
free(q);
while(r!=NULL&&s!=NULL){
if(r->data<s->data){
k->next=r;
k=r;
r=r->next;
}else{
k->next=s;
k=s;
s=s->next;
}
}
if(r!=NULL){
k->next=r;
}
if(s!=NULL){
k->next=s;
}
}
void merge2(LNode *a,LNode *b,LNode *&c){
LNode *p,*q,*r,*s;
p=a->next;
q=b->next;
free(a);
free(b);
c=(LNode *)malloc(sizeof(LNode));
c->next=NULL;
int count1=0;
int count2=0;
while(p!=NULL&&q!=NULL){
if(p->data<q->data){
r=(LNode *)malloc(sizeof(LNode));
r->data=p->data;
r->next=c->next;
c->next=r;
p=p->next;
count1++;
}else{
r=(LNode *)malloc(sizeof(LNode));
r->data=q->data;
r->next=c->next;
c->next=r;
q=q->next;
count2++;
}
}
while(p!=NULL){
s=(LNode *)malloc(sizeof(LNode));
s->data=p->data;
s->next=c->next;
c->next=s;
p=p->next;
}
while(q!=NULL){
s=(LNode *)malloc(sizeof(LNode));
s->data=q->data;
s->next=c->next;
c->next=s;
q=q->next;
}
}
bool compare(int a,int b){
return a>b;
}
int main(int argc, char** argv) {
int arr1[]={12,2,5,46,99,95};
int arr2[]={9,87,26,45,77};
sort(arr1,arr1+6); //sort函数默认是升序. . .
sort(arr2,arr2+5,compare);//默认是升序,要想它降序则要重写compare
LNode *p,*q,*l,*c;
createLNode1(p,arr1,6);
createLNode2(q,arr2,5);//因为是头插法,所以给的数组必须是降序
printLink(p);//打印p链表
printf("\n");
printLink(q);//打印q链表
printf("\n");
// merge1(p,q,l);//把p表和q表融合成递增链表l
// printLink(l);
// printf("\n");
merge2(p,q,c);//把p表和q表融合成递减链表c
printLink(c);
printf("\n");
return 0;
}
二、单链表的增删查
- 删除之前必须先找到要删结点的前驱结点,所以在查找判断条件要用
p->next!=NULL
- 任何要改变链表本身的操作(如
增加,删除,
),都不能乱动头结点的位置,而是需要额外定义一个指针指向头结点,然后用这个指针操作
#include <iostream>
#include<stdlib.h>
typedef struct LNode{
int data;
struct LNode *next;
}LNode;
void createLink(LNode *&p,int arr[],int n){//尾插法创建单链表
int i;
LNode *s,*r;
p=(LNode *)malloc(sizeof(LNode));
p->next=NULL;//创建头结点
r=p;//坑点:头结点一定不能乱动
for(i=0;i<n;i++){
s=(LNode *)malloc(sizeof(LNode));
s->data=arr[i];
r->next=s;
r=s;
}
r->next=NULL;
}
int del(LNode *&p,int key){//删除结点
LNode *r,*q;
r=p;//坑点:要改变链表的操作中,一定不能乱动头结点,而是重新定义一个结点指向头结点
while(r->next!=NULL){//这里用p->next判断是为了找到要删除的前驱结点
if(r->next->data==key){//先找到要删除结点的前驱结点
q=r->next;
r->next=q->next;
free(q);
return 1;
}
r=r->next;
}
return 0;
}
void print(LNode *p){
LNode *q;
q=p->next;
while(q!=NULL){
printf("%d ",q->data);
q=q->next;
}
printf("\n");
}
int main(int argc, char** argv) {
LNode *p;
int arr[]={12,5,89,47,22,36};
createLink(p,arr,6);
printf("删除前: ");
print(p);
del(p,47);
printf("删除后: ");
print(p);
return 0;
}
三、双链表
- 无论单链表还是双链表,删除时都要遵循
先链后断
- 双链表插入和删除时,指针可直接移到要插入或者的位置,不用像单链表一定要移到其前驱结点,因为双链表每个结点自带前驱指针
#include <iostream>
#include<stdlib.h>
typedef struct DLNode{
int data;
struct DLNode *prior;
struct DLNode *next;
}DLNode;
void createDLink(DLNode *&p,int arr[],int n){//创建双链表
int i;
DLNode *r,*s,*q;
p=(DLNode *)malloc(sizeof(DLNode));
p->prior=NULL;
p->next=NULL;
r=p;
for(i=0;i<n;i++){
s=(DLNode *)malloc(sizeof(DLNode));
s->data=arr[i];
r->next=s;
s->prior=r;
r=s;
}
r->next=NULL;
}
int insert(DLNode *&p,int key,int pos){//插入结点(在第pos位置上插入key)
DLNode *r,*s,*q;
int i,count=0;
r=p;
while(r->next!=NULL){
count++;
if(count==pos){
q=r->next;//记录原来第pos位置上的结点
s=(DLNode *)malloc(sizeof(DLNode));
s->data=key;
r->next=s;//r后继指针连接新结点
s->next=q;//新结点后继指针连接原先结点
s->prior=r;//新结点前驱指针指向r
q->prior=s;
return 1;
}
r=r->next;
}
return 0;
}
int search(DLNode *q,int key){//查找结点,返回结点位置
DLNode *p=q->next;
int count=0;
while(p!=NULL){
count++;
if(p->data==key){
return count;
}
p=p->next;
}
return 0;
}
int del(DLNode *&p,int key){//删除结点
DLNode *r,*s,*q,*l;
int i;
r=p->next;
while(r!=NULL){//双链表删除结点就可直接让指针指向要删除的结点,依靠它有前驱指针搞定
if(r->data==key){
q=r->prior;
s=r->next;
q->next=s;
s->prior=q;
free(r);
break;
}
r=r->next;
}
}
void print(DLNode *p){//打印双链表
DLNode *q;
q=p->next;
while(q!=NULL){
printf("%d ",q->data);
q=q->next;
}
printf("\n");
}
int main(int argc, char** argv) {
DLNode *p;
int arr[]={24,22,98,5,46};
createDLink(p,arr,5);//创建链表
print(p);
insert(p,408,3);//插入
print(p);
del(p,98);
print(p);
int n=search(p,5);
if(n){
printf("查找成功,在链表的第%d个位置\n",n);
}else{
printf("链表中没这个东西\n");
}
return 0;
}
链表
评论区