单链表的基本操作

心已赠人 2021-06-24 15:56 417阅读 0赞

// 单链表.cpp : 单链表的相关操作（两种方法的建立、两种方法的查询、求长、打印、插入、删除、逆序反转）。
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    typedef struct node
    {
    	char data;
    	struct node *next;
    }ListNode;
    typedef ListNode * LinkList;
    bool isvalue=true;
    LinkList creatListF(void)//头插入法
    {
    	LinkList head=NULL;
    	ListNode *s;
    	char ch;
    	cout<<"请输入字符串并回车，则头插入法形成的单链表如下："<<endl;
    	ch=getchar();
    	while(ch!='\n')
    	{
    		s=(ListNode *)malloc(sizeof(ListNode));
    		if(s==NULL)
    			return NULL; 
    		s->data=ch;
    		s->next=head;
    		head=s;//head要不断向前移动，一直指着最前线，这样存储的数据与输入的数据顺序相反
    		ch=getchar();
    	}
    	return head;
    }
    LinkList creatListR(void)//尾插入法
    {
    	LinkList head=NULL,r=NULL;//在创建时，要将head设置为NULL,否则内存出错;LinkList head这样声明只是指向一个未知的值
    	ListNode *s;
    	cout<<"请输入字符串并回车，则尾插入法形成的单链表如下："<<endl;
    	char ch;
    	ch=getchar();
    	while(ch!='\n')
    	{
    		s=(ListNode *)malloc(sizeof(ListNode));
    		s->data=ch;
    		if(head==NULL)
    			head=s;//新结点插入空表 
    		else
    			r->next=s;//如果是头结点，不执行这一步,头结点特别处理
    		r=s;//将指针r后移，使其一直指向最后一个结点
    		if(r!=NULL)
    		r->next=NULL;//对于非空表，将尾结点指针域置空，防止内存读写错误
    		ch=getchar();
    	}
    	/*while(cin>>ch)
    	{
    		s=new ListNode();
    		if(s==NULL)
    			return 0;
    		s->data=ch;
    		if(head==NULL)
    			head=s;
    		else
    			r->next=s;
    		r=s;
    		if(r->next!=NULL)
    			r->next=NULL;
    	}*/
    	return head;
    }
    ListNode GetNodeByPos(LinkList head,int pos)
    {
    	int i=1;
    	while(head&&i<pos)
    	{
    		head=head->next;
    		i++;
    	}
    	if(i==pos)
    		return *head;
    }
    ListNode GetNodeByKey(LinkList head,char key)
    {
    	while(head&&(head->data)!=key)
    		head=head->next;
    	if(head&&head->data==key)
    		return *head;
    }
    void print(LinkList head)
    {
    	while(head!=NULL)
    	{
    		cout<<head->data;
    		head=head->next;
    		if(head!=NULL)
    			cout<<"——> ";
    	}
    	cout<<endl;
    }
    int Length(LinkList head)
    {
    	int len=0;
    	while(head)
    	{
    		head=head->next;
    		len++;
    	}
    	return len;	
    }
    void DeleteNode(LinkList &head,char value)
    {
    	ListNode *ptemp,*qtemp,*current=head;
    	while(current)
    	{
    		ptemp=current->next;	
    		if(current->data==value)//第一种情况：头指针所包含的数据恰好符合要求
    		{
    			qtemp=current;
    			current=current->next;//头指针下移一个数据
    			free(qtemp);//原先的头指针删掉
    			isvalue=false;
    		}
    		else
    		{
    			if(ptemp!=NULL&&ptemp->data==value)
    			{
    				current->next=ptemp->next;
    				free(ptemp);
    				isvalue=false;
    			}
    			else
    				current=current->next;	
    		}					
    	}
    	if(isvalue)
    		cout<<value<<"不在单链表中"<<endl;
    }
    void InsertNode(LinkList &head,char value)
    {
    	int pos,tag=0,index=1;
    	ListNode *ptemp,*newNode;
    	newNode=new ListNode();
    	if(newNode==NULL)
        {
           printf("Memory malloc failture!");
           exit(-1);
        }
    	newNode->data=value;
    	cout<<"请输入插入方式：0——头部；1——尾部；2——中间。"<<endl;
    	cin>>pos;
    	if(pos==2)
    	{
    		cout<<"请输入要出入的位置(插入字符位于该位置的后面)：";
    		cin>>tag;
    	}
    	switch(pos)
    	{
    		case 0:
    			newNode->next=head;
    			head=newNode;
    			break;
    		case 1:
    			ptemp=head;
    			while(ptemp->next!=NULL)
    				ptemp=ptemp->next;
    			ptemp->next=newNode;
    			newNode->next=NULL;
    			break;
    		case 2:
    			ptemp=head;
    			while(index<tag&&ptemp!=NULL)
    			{
    				index++;
    				ptemp=ptemp->next;
    			}
    			if(index!=tag)
    				exit(-1);
    			newNode->next=ptemp->next;
    			ptemp->next=newNode;
    			break;	
    		default:
    			cout<<"输入的出入方式不合法。"<<endl;
    				break;
    	}
    		
    }
    void Reverse(LinkList &head)
    {
    	ListNode *p1,*p2,*p3;
    	if(head==NULL)
    		exit(-1);
    	p1=head;
    	p2=head->next;
    	while(p2!=NULL)
    	{
    		p3=p2->next;
    		p2->next=p1;
    		p1=p2;
    		p2=p3;
    	}
    	head->next=NULL;
    	head=p1;
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	/*LinkList head=creatListF();*/
    	LinkList head=creatListR();
    	print(head);
    
    	/*ListNode node=GetNodeByPos(head,2);
    	cout<<"在单链表中按位置查找："<<node.data<<endl;*/
    	ListNode node=GetNodeByKey(head,'b');
    	cout<<"在单链表中按值查找："<<node.data<<endl;
    
    	cout<<"单链表的长度是："<<Length(head)<<endl;
    
    	cout<<"After DeleteNode():"<<endl;
    	DeleteNode(head,'c');
    	if(!isvalue)
    	{
    		cout<<"删除字符c后，剩余的元素有："<<endl;
    		print(head);
    	}
    		
    	/*cout<<"After InsertNode():"<<endl;
    	InsertNode(head,'w');
    	print(head);*/
    
    	cout<<"After Reverse():"<<endl;
    	Reverse(head);
    	print(head);
    
    
    	system("pause");
    	return 0;
    }

部分内容参考自下面两个网站，在此表示感谢：

[http://www.cnblogs.com/foreverking/articles/2341399.html][http_www.cnblogs.com_foreverking_articles_2341399.html]

[http://hi.baidu.com/windstore/blog/item/db04b3193250eb4643a9ad8e.html][http_hi.baidu.com_windstore_blog_item_db04b3193250eb4643a9ad8e.html]

[http_www.cnblogs.com_foreverking_articles_2341399.html]: http://www.cnblogs.com/foreverking/articles/2341399.html
[http_hi.baidu.com_windstore_blog_item_db04b3193250eb4643a9ad8e.html]: http://hi.baidu.com/windstore/blog/item/db04b3193250eb4643a9ad8e.html