C++笔记 | 链表

为了表示这种既有数据又有指针的情况，引入结构这种数据类型。
1、链表中的元素称为“结点”，每个结点包括两个域：数 据域和指针域；
2、单向链表通常由一个头指针（head)，用于指向链表头；
3、单向链表有一个尾结点，该结点的指针部分指向一个空结点(NULL) 。

链表的创建(链表的结构)

// 类型和变量的说明 
	 struct Node //结构体类型
	 {
	 	int data;//数据域
		 Node *next;//指针域 
	 };  
	 Node *head,*p,*r;//头指针，结点，尾指针
	 int x; //元素 

链表的建立和输出

int mian()
{ 
          cin>>x;//输入数据
	head=new Node;//申请头结点
	r=head;//一开始就这个一个结点，头和尾都是它
	//开始根据读取的数据进行尾插结点
	while(x!=-1)
	{  
		p=new Node;//申请一个新结点
		p->data=x;//数据域元素是x 
		p->next=NULL;//当前p结点作为尾结点
		r->next=p;//让r成为p的直接前趋 
		r=p; //尾指针后移一位
		cin>>x; 
	 }
	 p=head->next;//头指针没有数据，只要从第一个结点开始就行了
	 while(p->next!=NULL)
	 { 
	   cout<<p->data<<" ";
	   p=p-<next; 	
	 } 
	 cout<<p->data<<endl;//最后一个结点的数据单独输出
	 return 0; 
} 

链表的增删改查

链表的查找

//查找"数据域满足一定条件的结点"
  void  zhao ()
  {
  	p=head->next;
  	while(p->data!=x) && (p->next!=NULL) 
	{
		p=p->next;//找不到就继续下一个 
	}
	if(p->data==x)
	{
		cout<<"找到了"; 
	}
	else
	{
		cout<<"不存在";
    } 

链表的读取

void get(Node *head,int i)
{
	Node *p;//结点 
	int j;//记录 
	p=head->next;//从头开始 
	j=1;//从第一个开始
	 while((p!=NULL)&&(j<i))
	 {
	       p=p->next;
	       j+=1; 
	 } 
	 if((p!=NULL)&&(j==i))
	 {
                      cout<<p->data;
	 }
	 else
	 {
                      cout<<"i不存在"; 
	 }	 
} 

求单链表的实际长度

	int len(Node *head)
	{
		int n=0;
		p=head;
		while(p!=NULL)
		{
			n+=1;
			p=p->next;
		}
		return n; //返回链表的结点个数
	}