一.单链表的创建

单链表的两种创建方法:尾插法和头插法 两个数据域递增的单链表融合成一个依旧递增的单链表,很简单了注意新链表头结点的就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;
}

二、单链表的增删查

1. 删除之前必须先找到要删结点的前驱结点,所以在查找判断条件要用p->next!=NULL
2. 任何要改变链表本身的操作(如增加,删除,),都不能乱动头结点的位置,而是需要额外定义一个指针指向头结点,然后用这个指针操作

#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;
}