双链表的相关操作

淡淡的烟草味﹌ 2021-06-24 15:56 392阅读 0赞

// DoubleLinkTable.cpp : Defines the entry point for the console application.
    #include "stdafx.h"
    #include<cassert>
    #include<iostream>
    using namespace std;
    typedef struct node
    {
    	char data;
    	struct node *next,*pre;
    }ListNode;
    typedef ListNode * LinkList; 
    LinkList CreateListF(void)//头插入法
    {
    	LinkList head=NULL,ptemp=NULL;
    	head = (ListNode *)malloc(sizeof(ListNode));//头结点初始化
    	head->data = ' ';
    	head->next = NULL;
    	head->pre = NULL;
    	ptemp=head;//用ptemp代替头结点指针
    	ListNode *newNode;
    	cout<<"请输入字符串并回车，则尾插入法形成的单链表如下："<<endl;
    	char ch;
    	ch=getchar();
    	while(ch!='\n')
    	{
    		newNode=(ListNode *)malloc(sizeof(ListNode));
    		if(newNode==NULL)
    			return NULL; 
    		newNode->data=ch;
    
    		if(ptemp->next==NULL)
    		{
    			newNode->next=ptemp;
    			newNode->pre=NULL;
    			ptemp->pre=newNode;
    			ptemp->next=NULL;
    		}
    		else
    		{
    			newNode->next=ptemp;
    			newNode->pre=NULL;
    			ptemp->pre=newNode;
    		}
    		ptemp=newNode;//ptemp要不断向前移动
    		ch=getchar();
    	}
    	head=new ListNode();//重新建立一个空数据的头结点
    	head->data=' ';
    	head->next=ptemp;
    	head->pre=NULL;
    	ptemp->pre=head;
    	return head;
    }
    LinkList CreateListR(void)//尾插入法
    {
    	LinkList head=NULL,ptemp=NULL;
    	head = (ListNode *)malloc(sizeof(ListNode));
    	head->data = ' ';
    	head->next = NULL;
    	head->pre = NULL;
    	ptemp=head;
    	ListNode *newNode;
    	cout<<"请输入字符串并回车，则尾插入法形成的单链表如下："<<endl;
    	char ch;
    	ch=getchar();
    	while(ch!='\n')
    	{
    		newNode=(ListNode *)malloc(sizeof(ListNode));
    		newNode->data=ch;
    		ptemp->next = newNode;
    		newNode->pre = ptemp;
    		newNode->next = NULL;
    		
    		ptemp = ptemp->next;
    		ch=getchar();
    	}
    	return head;
    }
    void DeleteNode(LinkList &head,char value)
    {
    	assert(head != NULL);
    	ListNode *current = NULL;
    	ListNode *temp = NULL;
    	current = head;
    	while( NULL != current->next)
    	{
    		if ( value == current->next->data)
    		{
    			temp = current->next;
    			if(temp->next==NULL)//删除的结点是尾结点
    				current->next=NULL;
    			else                //删除的结点是头或中间结点
    			{
    				current->next = temp->next;
    				temp->next->pre=current;
    			}
    			free(temp);
    		}
    		else
    			current = current->next;
    	}
    }
    void InsertNode(LinkList &head,char value)
    {
    	assert(head!=NULL);
    	int pos,tag,index=0;
    	ListNode *current=head;
    	ListNode *newNode=new ListNode();
    	newNode->data=value;
    	cout<<"请输入插入方式：0——头部；1——尾部；2——中间。"<<endl;
    	cin>>pos;
    	if(pos==2)
    	{
    		cout<<"请输入插入的位置：";
    		cin>>tag;
    	}
    	switch(pos)
    	{
    	case 0:
    		newNode->next=head->next;
    		head->next->pre=newNode;
    		head->next=newNode;
    		newNode->pre=head;
    		break;
    	case 1:
    		while(current->next)
    			current=current->next;
    		current->next=newNode;
    		newNode->pre=current;
    		newNode->next=NULL;
    		break;
    	case 2:
    		while(index<tag&¤t->next!=NULL)
    		{
    			index++;
    			current=current->next;
    		}
    		if(index!=tag)
    			exit(-1);
    		newNode->next=current;
    		newNode->pre=current->pre;
    		current->pre->next=newNode;
    		current->pre=newNode;
    
    		/*newNode->pre=current->pre;
    		current->pre->next=newNode;
    		newNode->next=current;
    		current->pre=newNode;*/
    		break;
    	default:
    		break;
    	}
    
    }
    void print(LinkList head)
    {
    	while(head->next!=NULL)
    	{
    		cout<<head->next->data;
    		head=head->next;
    		if(head->next!=NULL)
    			cout<<"<——> ";
    	}
    	cout<<endl;
    }
    int length(LinkList head)
    {
    	int len=0;
    	while(head->next!=NULL)
    	{
    		len++;
    		head=head->next;
    	}
    		return len;
    }
    void Reverse(LinkList head)
    {
    	if(head->next==NULL)
    		exit(-1);
    	ListNode*p1;
    	p1=head->next;
    	head->next=NULL;
    	p1->pre=NULL;
    
    	ListNode *p2,*p3;
    	p2=p1->next;
    	while(p2)
    	{
    		if(p2->next!=NULL)
    		{
    			p3=p2->next;
    
    			p2->pre->next=p3;
    			p3->pre=p2->pre;
    			p2->next=p1;
    			p1->pre=p2;
    		}
    		else //尾部结点
    		{
    			p2->pre->next=NULL;
    
    			p2->pre=head;
    			head->next=p2;
    			p2->next=p1;
    			p1->pre=p2;
    
    			p3=NULL;
    		}
    		p1=p2;
    		p2=p3;
    	}
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	/*LinkList head=CreateListF();*/
        LinkList head=CreateListR();
    	print(head);
    
    	cout<<"After DeleteNode():"<<endl;
    	DeleteNode(head,'c');
    	cout<<"删除字符c后，剩余的元素有："<<endl;
    	print(head);
    
    	cout<<"After InsertNode():"<<endl;
    	InsertNode(head,'c');
    	cout<<"插入字符c后，链表中的元素有："<<endl;
    	print(head);
    
    	cout<<"链表的长度："<<length(head)<<endl;
    
    	cout<<"After Reverse():"<<endl;
    	Reverse(head);
    	cout<<"反转链表中的元素："<<endl;
    	print(head);
    
    	system("pause");
    	return 0;
    }