数据结构与算法——链表

1. 用struct自定义数据类型：

   struct Node{
       int data;
       Node*next;
   };
   struct Node*head;//定义头节点为全局变量

2. 操作链表的相关函数：

   （一）InsertAtHead函数：

   void InsertAtHead(int x){//在链表的前端插入节点
       struct Node*temp=new Node;
       temp->data=x;
       temp->next=head;
       head=temp;
   }

   （二）Insert函数：

   void Insert(){//在链表的任意位置插入节点
       int data,n;
       cout<<"插入的位置为：";
       cin>>n;
       cout<<"插入的数字为：";
       cin>>data;
       struct Node*temp1=new Node;
       temp1->data=data;
       temp1->next=NULL;
       if(n==1){
           temp1->next=head;
           head=temp1;
           return;
       }
       Node*temp2=head;
       for(int i=0;i<n-2;i++){
           temp2=temp2->next;//得到n-1号节点的地址
       }
       temp1->next=temp2->next;
       temp2->next=temp1;
   }

   （三）Delete函数：

   void Delete(int n){
       struct Node*temp1=head;
       if(n==1){
           head=temp1->next;
           delete temp1;
           return;
       }
       for(int i=0;i<n-2;i++){
           temp1=temp1->next;
       }
       struct Node*temp2=temp1->next;
       temp1->next=temp2->next;
       delete temp2;
   }

   （四）Print函数：

   void Print(){
       struct Node*temp=head;
       cout<<"List is ";
       while(temp!=NULL){
           cout<<temp->data;
           temp=temp->next;
       }
       cout<<endl;
   }

   （五）完整代码：

   #include<iostream>
   using namespace std;
   struct Node{
       int data;
       Node*next;
   };
   struct Node*head;
   void InsertAtHead(int x){//在链表的前端插入节点
       struct Node*temp=new Node;
       temp->data=x;
       temp->next=head;
       head=temp;
   }
   void Insert(){//在链表的任意位置插入节点
       int data,n;
       cout<<"插入的位置为：";
       cin>>n;
       cout<<"插入的数字为：";
       cin>>data;
       struct Node*temp1=new Node;
       temp1->data=data;
       temp1->next=NULL;
       if(n==1){
           temp1->next=head;
           head=temp1;
           return;
       }
       Node*temp2=head;
       for(int i=0;i<n-2;i++){
           temp2=temp2->next;//得到n-1号节点的地址
       }
       temp1->next=temp2->next;
       temp2->next=temp1;
   }
   void Delete(int n){//删除某一个节点
       struct Node*temp1=head;
       if(n==1){
           head=temp1->next;
           delete temp1;
           return;
       }
       for(int i=0;i<n-2;i++){
           temp1=temp1->next;
       }
       struct Node*temp2=temp1->next;
       temp1->next=temp2->next;
       delete temp2;
   }
   void Print(){//打印链表
       struct Node*temp=head;
       cout<<"List is ";
       while(temp!=NULL){
           cout<<temp->data;
           temp=temp->next;
       }
       cout<<endl;
   }
   int main(){
       int*head=NULL;
       InsertAtHead(2);
   	InsertAtHead(0);
   	Print();
   	Insert();
   	Print();
   	Insert();
   	Print();
   	int n;
   	cin >> n;
   	Delete(n);
   	Print();
   	return 0;
   }

   （六）输出结果：