链表 通过struct来完成。
如果node*p，这时候是要p->data或者p->next，这个跟data和next是不是指针无关
如果node p，这时候是要p.data或者p.next，跟data和next无关，如果是node p非指针类型，用.
在申请和删除的时候有malloc和free，new和delete两组。
malloc和free(头文件是#include<stdlib.h>)
typename*p=(typename*)malloc(sizeof(typename)) free(p)
eg:int*p=(int*)malloc(sizeof(int)) free(p)
new和delete
int *p=new int; delete(p)
创建链表具体操作：默认链表带一个空的头节点，pre存储的是当前节点，也就是下一个点的前一个节点，最开始和head一样。尾节点的下一个节点是NULL
设置的过程中，首先是新建节点存信息，再建立节点和pre的联系，并修改新的pre，完成新的点的输入。
#include<stdio.h> #include<iostream> using namespace std; struct node{ int data; node*next; }; node*create(int Array[]) { node*p,*head,*pre; head=new node; head->next=NULL; pre=head; for(int i=0;i<5;i++) { p=new node; p->data=Array[i]; p->next=NULL; pre->next=p; pre=p; } return head; } int main() { int Array[5]={5,1,2,7,6}; node*L=create(Array); L=L->next; while(L!=NULL) { printf("%d ",L->data); L=L->next; } return 0; }
查找出现次数：从头到尾遍历一次即可。
插入元素：找到位置以后，新建节点，把点赋值在上面，然后这个点的next先赋值为原来pre->next，然后再把原先的pre->next变成现在的节点。
PAT A1032
找两个链表的共同元素开始的位置，遍历第一个链表然后标记flag，第二个再读取，注意是五位输出，但是在没有的时候是-1，不用五位输出。
这个属于静态链表。地址为11111，那么点就是a[11111]，a[11111]的next和data里面分别存的是下一个的地点和当前点的数据。没有难度
静态链表不需要头节点。
#include<stdio.h> #include<string.h> #include<iostream> using namespace std; struct node{ char data; bool flag=false; int next; }a[100010]; int main() { int start1,start2,sumnum; node*p=new node; int temp1,temp3; char temp2; scanf("%d %d %d",&start1,&start2,&sumnum); for(int i=1;i<=sumnum;i++) { scanf("%d %c %d",&temp1,&temp2,&temp3); a[temp1].data=temp2; a[temp1].next=temp3; a[temp1].flag=false; } while(start1!=-1) { a[start1].flag=true; start1=a[start1].next; } while(start2!=-1) { if(a[start2].flag==true) { printf("%05d ",start2); return 0; } start2=a[start2].next; } printf("-1"); return 0; }
PAT A1052
这个是给链表排序，给好开头元素，需要注意的是，给定的节点不一定全部都在start开头的节点里面，所以要用address做下标。在输出第一行的时候注意%05d的地址。在从头开始的过程中用flag标记访问过的元素。
在cmp的过程中，如果有flag为假的，直接丢掉后面去。
#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; struct node { int address,data,next; bool flag=false; }a[100010]; bool cmp(node temp1,node temp2) { if(temp1.flag==false||temp2.flag==false) return temp1.flag>temp2.flag; else return temp1.data<temp2.data; } int main() { int sum,start; scanf("%d %d",&sum,&start); int temp1,temp2,temp3; for(int i=1;i<=sum;i++) { scanf("%d %d %d",&temp1,&temp2,&temp3); a[temp1].address=temp1; a[temp1].data=temp2; a[temp1].next=temp3; } int count=0; int tempstart=start; while(tempstart!=-1) { a[tempstart].flag=true; count++; tempstart=a[tempstart].next; } sort(a,a+100010,cmp); if(count==0) { printf("0 -1 "); return 0; } printf("%d %05d ",count,a[0].address); for(int i=0;i<=count-2;i++) { printf("%05d %d %05d ",a[i].address,a[i].data,a[i+1].address); } printf("%05d %d -1 ",a[count-1].address,a[count-1].data); return 0; }
注意需要用到sort的结构体，里面的变量和结构体的名称不能相同。
需要静态链表的通用套路：address直接体现在数组的存储节点中，之后在next中存好下一个的位置，然后有一个data，再有一个flag或者别的点用于存储针对某一特定结果的元素。这个标记如果在遍历后为真进行标记，辅助计算。
对于里面的元素要记得初始化。