链表是一个线性数据结构
1 #include<cstdio> 2 3 using namespace std; 4 5 struct lian_biao_jie_dian//结构体自己造链表 6 { 7 int next,pre;//next 为下一节点，pre 为上一节点 8 int value;//value 为数值的意思 9 10 lian_biao_jie_dian() 11 { 12 next=pre=0; 13 value=0; 14 }//在结构体中构造函数进行初始化 15 }; 16 17 lian_biao_jie_dian lian_biao[100]; 18 19 int first=0,n=0;//对第一个节点first和链表中的元素个数进行初始化 20 21 void insert(int i,int v)//insert 为插入的意思，此函数是插入函数，有两个值可用，只需要将i节点原来的下一个节点表示出来即可，即为lian_biao[i].next 22 { 23 n+=1;//在通常情况下，链表每个节点都是连着的，n为原来节点的个数，因为要插入一个，所以n+=1 24 25 lian_biao[n].value = v;//链表第n个(即刚插入的)节点的数值为v 26 lian_biao[n].pre = i;//将插入节点插到i节点的后面，即插入节点的向前链接i节点，i为在主函数中输入的值 27 lian_biao[n].next = lian_biao[i].next;//插入节点向后连接的节点就是原来i节点的后面的节点(注意i后面的节点无法用一个字母表示，只能用“lian_biao[i].next”表示，即只能用lian_biao[i]得下一个来表示 28 lian_biao[lian_biao[i].next].pre = n;//i节点的下一个节点(注意不是插入节点)的上一个节点为插入节点 29 lian_biao[i].next = n;//最后一步一定顺序不要错，最后一步才能更改i节点的下一个节点，更改为n 30 }//注意此为插入一个节点，原来的链边在插入时已被更改，不须再删除什么 31 32 33 void delete_node(int i)//此函数为删除节点函数 ，注意只有一个数据可用，前面与后面的节点都得用lian_biao[i].pre和lian_biao[i].next表示 34 { 35 int pre = lian_biao[i].pre;//此语句与下一语句可以定义，也可不定义，定义较为简洁。pre为i节点的上一个节点 36 int next = lian_biao[i].next;//next为i节点的下一个节点 37 38 lian_biao[pre].next = next;//pre为i节点的上一个节点，此语句为i节点的上一个节点的下一个节点为i节点的下一个节点，即将i节点跳过 39 lian_biao[next].pre = pre;//i节点的下一个节点的上一个节点即为i节点的上一个节点，也将i节点跳过 40 if (i==first) first = next;//注意这里有一个特殊情况，如果i节点正好为链表的第一个节点，那么i节点的下一个节点就成了链表的第一个节点 41 }//不用担心i节点为第一个节点或最后一个节点，如果它是，则它的前面或者后面会有无数个0，可进行链接，并且所有的0为空字符，输出时不会输出，所以不影响 42 43 int query(int k)//此函数为给定一个k，求链表中第k个节点的值 44 { 45 int p=first;//先定义p为第一个节点 46 for (int a=1;a<k;a++)//运用for循环，一个个往下推 47 p=lian_biao[p].next;//p从头节点开始，慢慢地等于下一个节点，若想找到k节点，则需要进行k-1次操作，即a<k 48 return lian_biao[p].value;//通过上述向下推，返回的p节点的数值即为所求的k节点的数值 49 }
链表主要掌握添加、删除、查询三个操作即可.....