数据结构双向链表

思维导图

练习

双向链表任意位置插入和删除

头文件

#ifndef __HEAD_H__
#define __HEAD_H__


#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef char datatype;
//定义双向链表结构体
typedef struct Node
{
	//数据域
	datatype data;
	//指针域:下一个节点的地址
	struct Node *next;
	//指针域:上一个节点的地址
	struct Node *prev;
}*DoubleLink;

DoubleLink creat();
DoubleLink insert_head(DoubleLink head,datatype element);

void output(DoubleLink head);
DoubleLink insert_rear(DoubleLink head,datatype element);
DoubleLink delete_head(DoubleLink head);
DoubleLink delete_rear(DoubleLink head);
DoubleLink insert_pos(DoubleLink head,int pos,datatype element);
DoubleLink delete_pos(DoubleLink head,int pos);





#endif

主函数

#include "head.h"

int main(int argc, const char *argv[])
{
	DoubleLink head=NULL;
	int n;
	datatype element;
	printf("please enter n");
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		printf("please enter %d element ",i+1);
		scanf(" %c",&element);
		//head=insert_head(head,element);
		head=insert_rear(head,element);
	}
/*
	output(head);
	head=delete_head(head);
	output(head);
	head=delete_rear(head);
	output(head);
*/
	int pos;
	printf("请输入插入的位置");
	scanf("%d",&pos);
	printf("请输入插入的值");
	scanf(" %c",&element);
	head=insert_pos(head,pos,element);
	output(head);
	printf("请输入删除的位置");
	scanf("%d",&pos);
	head=delete_pos(head,pos);
	output(head);

	return 0;
}

自定义函数

#include "head.h"
/*
 * function:    创建
 * @param [ in] 
 * @param [out] 
 * @return      
 */
DoubleLink creat()
{
	DoubleLink s=(DoubleLink)malloc(sizeof(struct Node));
	if(s==NULL)
		return NULL;
	s->data=0;
	s->next=s->prev=NULL;
	return s;
}
/*
 * function:    计算双向链表的长度
 * @param [ in] 
 * @param [out] 
 * @return      
 */
int length(DoubleLink head)
{
	int count=0;
	if(head==NULL)
		return 0;
	DoubleLink p=head;
	while(p!=NULL)
	{
		count++;
		p=p->next;
	}
	return count;
}

/*
 * function:    头插
 * @param [ in] 
 * @param [out] 
 * @return      
 */
DoubleLink insert_head(DoubleLink head,datatype element)
{
	DoubleLink s=creat();
	s->data=element;
	if(head==NULL)
		head=s;
	else
	{
		s->next=head;
		head->prev=s;
		head=s;
	}
	return head;
}
/*
 * function:    遍历输出
 * @param [ in] 
 * @param [out] 
 * @return      
 */
void output(DoubleLink head)
{
	if(head==NULL)
		return;
	DoubleLink p=head;
	while(p->next!=NULL)
	{
		printf("%c",p->data);
		p=p->next;
	}
	printf("%c",p->data);
	puts("");
/*
	while(p!=NULL)
	{
		printf("%c",p->data);
		p=p->prev;
	}
	puts("");
*/
}
/*
 * function:    尾插
 * @param [ in] 
 * @param [out] 
 * @return      
 */
DoubleLink insert_rear(DoubleLink head,datatype element)
{
	DoubleLink s=creat();
	s->data=element;
	if(head==NULL)
		head =s;
	else
	{
		DoubleLink p=head;
		while(p->next!=NULL)
		{
			p=p->next;
		}
		p->next=s;
		s->prev=p;
	}
	return head;
}
/*
 * function:    头删
 * @param [ in] 
 * @param [out] 
 * @return      
 */
DoubleLink delete_head(DoubleLink head)
{
	if(head==NULL)
		return NULL;
	DoubleLink del=head;
	head=del->next;
	head->prev=NULL;
	free(del);
	del=NULL;
	return head;
}
/*
 * function:    尾删
 * @param [ in] 
 * @param [out] 
 * @return      
 */
DoubleLink delete_rear(DoubleLink head)
{
	if(head==NULL)
		return NULL;
	while(head->next==NULL)
	{
		free(head);
		head=NULL;
		return head;
	}
	DoubleLink s=head;
	while(s->next!=NULL)
	{
		s=s->next;
	}
	s->prev->next=NULL;
	free(s);
	s=NULL;
	return head;
}
/*
 * function:    按任意位置插入
 * @param [ in] 
 * @param [out] 
 * @return      
 */

DoubleLink insert_pos(DoubleLink head,int pos,datatype element)
{
	if(pos<0||pos>length(head)+1)
		return head;
	DoubleLink s=creat();
	s->data=element;
	if(pos==1)
	{
		head=insert_head(head,element);
		return head;
	}
	if(pos==length(head)+1)
	{
		head=insert_rear(head,element);
		return head;
	}	
	DoubleLink p=head;
	for(int i=1;i<pos;i++)
	{
		p=p->next;
	}
	s->next=p;
	s->prev=p->prev;
	p->prev->next=s;
	p->prev=s;
	return head;
}
/*
 * function:    按任意位置删除
 * @param [ in] 
 * @param [out] 
 * @return      
 */
DoubleLink delete_pos(DoubleLink head,int pos)
{
	if(head==NULL)
		return NULL;
	if(pos<0||pos>length(head))
		return head;
	if(pos==1)
	{
		head=delete_head(head);
		return head;
	}
	if(pos==length(head))
	{
		head=delete_rear(head);
		return head;
	}
	DoubleLink del=head;
	for(int i=1;i<pos;i++)
	{
		del=del->next;
	}
	DoubleLink p=del->prev;
	p->next=del->next;
	del->next->prev=p;
	free(del);
	del=NULL;
	return head;
}

效果图