单链表的基本操作和应用_单链表的基本操作与应用

一、单链表的特点

1. 有一个head 指针变量，它存放头结点的地址，称之为头指针。
2. 头结点的指针域 head->next，存放首元结点(第一个实际有效结点)的地址。
3. 每个结点都包含一个数据域和一个指针域，数据域存放用户需要的实际数据，指针域存放下一个结点的地址。从头指针 head开始，head 指向头结点，头结点指向首元结点，首元结点指向第二个结点，…，直到最后一个结点。所有结点都是单线联系环环相扣。
4. 最后一个结点不再指向其他结点,称为“表尾结点”,它的指针域为空指针“NULL”,表示链表到此结束。指向表尾结点的指针称为尾指针。
5. 链表各结点之间的顺序关系由指针域next来确定，并不要求逻辑上相邻的结点物理位置上也相邻，也就是说，链表依靠指钍相连不需要占用一片连续的内存空间。
6. 随着处理数据量的增加，链表可以不受程序中变量定义的限制无限地延长(仅受内存总量的限制)。在插入和删除操作中，只需修改相关结点指针域的链接关系，不需要像数组那样大量地改变数据的实际存储位置。链表的使用，可以使程序的内存利用率和时间效率大大提高。

二、创建头结点

typedef struct node{
	int data;//数据
	struct node *next;//next的类型是指向本结构体类型的指针类型
}node,*linklist;
linklist headlist(){
	node*head;//定义头指针变量
	head=(node*)malloc(sizeof(node));//头指针指向分配的头结点内存空间
	head->next=NULL;//头结点的指针域为空
	return head;//返回头结点的地址,即头指针
}

其中,node是结构体类型,linklist是结构体指针类型。linklist head相当于是node *head,也相当于是struct node*head。 

三、链表的建立

1.头插法

void creatlist(linklist head){
	node* s;
	int data;
	while(1){
		scanf("%d",&data);
		if(data==0)//结束循环的条件
			break;
		s=(node*)malloc(sizeof(node));
		s->data=data;
		s->next=head->next;//新结点指向原来的首元结点
		head->next=s;//链表的头结点指向新结点
	}
}
//就是将新结点插入到当前链表的表头结点之后

2.尾插法

void creatlist (linklist head){
	node *r,*s;
	int data;
	r=head;//r指向头结点
	while(1){
		scanf("%d",&data);
		if(data==0){//结束输入退出循环的条件
			break;
		}
		s=(node*)malloc(sizeof(node));//分配结点的内存空间
		s->data=data;
		r->next=s;//原来的结点指向新结点
		r=s;//r指向新结点
	}
	s->next=NULL;//链表的尾结点指针为空
}

四、链表的遍历

void output(linklist head){
	node *p;//循环所用的临时指针
	p=head->next;//p指向链表的首元结点
	while(p){
		printf("%d ",p->data);//输出数据
		p=p->next;//移动临时指针到下一个结点
	}
}
//如果是最后一个结点，指针指向NULL，表示链表中的结点都已输出，循环结束

五、链表的插入

1.在单链表第i个位置上插入新结点

void insert(linklist head,int i){
    node *=head,*s;
    int j=0;
    while(j<i-1&&p){//找到第i-1个结点的地址p
        p=p->next;
        j++;
    }
    if(p){
        s=(node*)malloc(sizeof(node));//定义s指向新分配的空间
        scanf("%s",s->data);
        s->next=p->next;//新结点指向原来的第i个结点
        p->next=s;//新结点成为新链表的第i个结点
    }
}

2.表首位置后添加结点 （同理创建链表的头插法）

3.在链表的最后添加结点

void insertrear(linklist head){
    node *p=head,*s;
    while(p && p->next){//找到最后一个结点的地址p
        p=p->next;
    }
    if(p){
        s=(node*)malloc(sizeof(node));//定义s指向新分配的空间
        scanf("%s",s->data);
        p->next=s;//尾结点的指针指向新结点
        s->next=NULL;//新结点指针指向NULL
    }
}

六、链表的删除

void DeleteL(linklist head,int pos){
    node *p=head,*q;
    int pos=0;
    while(j<pos-1&&p){//找到第pos-1个结点的地址p
        p=p->next;
        j++;
    }
    if(p==NULL||p->next==NULL){//第pos个结点不存在
        printf("the pos is ERROR!");
    }else{
        q=p->next;//q指向pos个结点
        p->next=q->next;//连接删除结点两边的结点
        free(q); //释放要删除结点的内存空间
    }
}   

七、链表的查询

node *search(linklist head,int data){
   node *p=head->next;
   while(p){
      if(p->data!=data)
         p=p->next;
      else
         break;//查找成功
    }
    if(p==NULL){
      printf("没有找到值为%d的结点!",data);
    }
    return p;
}

八、链表的长度

int len(linklist head){
	node* p;
	int count=0;
	p=head->next;//指针变量p指向链表的首元结点
	while(p){//结点存在，表示链表没有遍历结束
		count++;//结点个数累计器加1
		p=p->next;//指向当前节点的下一个结点
	}
	return count;//返回结点的个数
}

九、不带头节点的单链表

1.不带头结点单链表的插入

链表的插入操作如果在链表的首位置，则插入时，首先为插入的新结点分配内存，然后将新结点的指针s指向原来首结点(s->next=head)，最后将头指针指向新结点(head=s),这样就完成了插入结点的操作，很显然，这种情况下，头指针发生了改变，所以需要返回新头指针。
链表的插入操作如果插入位置不是首位置，则需要先通过循环找到链表的第i-1个结点的地址p。如果该结点存在，则可以在第i-1个结点后面插入第i个结点。为插入的新结点分配内存，然后向新结点输入数据。插入时，首先将新结点的指针s指向原来第i个结点(s->next=p->next)，然后将第i-1个结点指向新结点(p->next=s)，这样就完成了插入结点的操作，很显然，这种情况下的操作和带头结点的操作是一样的。

2.不带头结点单链表的删除

删除的结点如果是链表的首结点，则定义指针变量q指向待删结点(q=head)，再让头指针指向第二个结点(head=head->next)，成为新的首结点，最后释放原来的首结点(free(q)),则这样就完成了删除首结点的操作。很显然，这种情况下头指针发生了改变，所以需要返回新头指针。
删除的结点如果不是链表的首结点，定义整型变量i来控制循环的次数，然后定义指变量p表示该结点之前的结点。接着利用循环找到要删除的结点之前的结点p;如果该结点存在并且待删除结点存在，则将指针变量q指向待删除结点(q=p->next)，再连接要删除结点两边的结点(p->next=q>next)，并使用free函数将q指向的内存空间进行释放的第i-1个结(free(q))，这样就完成了删除结点的操作。很显然，这种情况下的操作和带头结点的删除操作是一样的。 

十、单链表的应用

1.合并两个升序链表

2.反转链表

迭代：

void reverse(linklist head){
	node*p,*q;
	p=head->next;//p指向首元结点
	head->next=NULL;//将原链表置为空表
	while(q){
		q=p->next;
		p->next=head->next;//将当前结点插入到头结点的后面
		head->next=p;
		p=q;
	}
}

递归： 

3.回文链表 

int huiwen(linklist head){
	node *p=head->next,*h,*s,*r;
	h=(node*)malloc(sizeof(node));//创建一个新链表的头
	h->next=NULL;
	int n=len(head);//求出链表的长度
	int j=1;
	while(p&&j<=n/2){//将原链表的一半结点数据赋给新链表的结点，用头插法创建
		s=(node*)malloc(sizeof(node));
		s->data=p->data;
		s->next=h->next;
		h->next=s;
		p=p->next;
		j++;
	}
	if(n%2){//如果原链表的长度为奇数，p指向p的下一个结点
		j++;
		p=p->next;
	}
	r=h->next;
	while(p&&j<=n){//比较新链表和原链表的后一半结点是否相等
		if(r->data!=p->data){//若不相等返回0，说明不是回文链表
			return 0;
		}
		j++;
		r=r->next;
		p=p->next;
	}
	return 1;//返回1，说明是回文链表
}

4.两两交换链表中的结点

5.删除链表中的重复元素

6.对链表进行插入排序