（贵州省普通高中信息学奥赛CSP-JS NOIP—入门组C++知识点讲解）第14讲 链表

学科竞赛编程 教研研究院 C++ NOIP NOI IOI 1 1 PART ONE 例：跳马。依下图将每一步跳马之后的位置(x,y)放到一个“结点”里，再用“链子穿起来”，形成一条链，相邻两结点间用一个指针将两者连到一起。 结构的概念与应用 1 PART ONE 依上图有7个结点 (x1,y1 (x2,y2) (x6,y6) (x7,y7) 为了表示这种既有数据又有指针的情况，引入结构这种数据类型。 1 PART ONE 1、链表中的元素称为“结点”，每个结点包括两个域：数 据域和指针域； 2、单向链表通常由一个头指针（head)，用于指向链表头； 3、单向链表有一个尾结点，该结点的指针部分指向一个空结点(NULL) 。 元素 地址 数据域 指针域 结点 元素 地址 元素 地址 元素 p p->next p->next->next ...... 头指针 NULL 1 PART ONE 链表的创建(链表的结构) // 类型和变量的说明 struct Node //结构体类型 { int data;//数据域 Node *next;//指针域 }; Node *head,*p,*r;//头指针，结点，尾指针 int x; //元素 1 PART ONE 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<<"不存在"; } 1 PART ONE 取出单链表的第i个结点的数据域 链表的读取 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不存在"; } } 1 PART ONE 链表的插入 在链表中插入一个结点 void insert(Node *head,int i,int x) //插入x到第i个元素之前 { Node *p,*s; int j; j=0; //寻找i-1个结点，插在它的后面 ，相当 于插在了第i个的前面 while((p!=NULL)&&(j<i-1)) { p=p->next; j+=1; } if(p==NULL) cout<<"no this position"; else { s=new Node; s->data=x; s->next=p->next; p->next=s; } } 1 PART ONE void delete(Node *head,int i) { Node *p,*s; int j; p=head; j=0;