4.1 基本概念

（1）用来存储数据变量叫做数据域。

（2）用来存“直接后继（前趋）元素的地址”的指针叫做指针域。

（3）数据域和指针域构成的元素叫做结点。

（4）”->” 箭头运算是结构体指针访问其指向的成员变量的操作符.

4.2单链表

(1)单链表的定义：

1.  struct Node {

2.   int data;

3.   Node * next;

4.  };

5.  Node * p;

(2)单链表的查找

//（按序号查找）在单链表中查找第i个结点 找到则返回存储位置

1. node *search1(node *l,int i) {

2.   node *p;//新建一个结点指针

3.   int j=0;//建立一个计数器

4.   if(i<=0)return NULL;//判断结点位置的合法性

5.   p=l; //新结点p指向头结点l 从头开始扫描

6.   while(p->next!=NULL&&j<i) {

7.    p=p->next;//指向下一结点

8.    j++;//计数

9.   }

10.  if(i==j) return p;//找到了就返回p指针

11.  else return NULL;

12. }

//（按值查找）在单链表中查找值为e的结点  找到返回结点

1.  node *search2(node *l,int e){

2.   node *p;//新建一个结点指针

3.   p=l->next ;//从第一个结点开始，既头结点后面那个

4.   while(p!=NULL){

5.    if(p->data!=e)p=p->next;//指向下个结点

6.    else break;//找到则退出循环

7.      }

8.   return p;//返回p指针

9.  }

(3)单链表的插入

1.  s->data=e; //将结点s的data设置为e

2.  s->next=p->next; //链表指针的赋值，将p的下一个结点的位置赋值给s的下一个结点

3.  p->next=s; //实现插入，把s接到p的下一个结点上

(4)单链表的删除

4.3双链表

(1)双链表的定义

1.  struct Node{

2.   //data表示数据

3.      int data;

4.   //pre node表示前趋   

5.      Node *pre;

6.   //next node表示后继    

7.      Node *next;

8.  }Node,*a;

(2)双链表的插入

1.  Node->next=p->next;

2.  p->next->pre=Node;

3.  Node->pre=p;

4.  p->next=Node;

(3)双链表的删除

1.  Node->pre->next=Node->next;

2.  Node->next->pre=Node->pre;