数据结构之线性表（链式存储结构）

1 typedef struct LNode{
2     ElemType data;          //数据域
3     struct LNode *next;     //指针域，用来指向本节点的直接后继
4 }LNode,*LinkList;           //定义节点，以及头指针

 1 void CreateList(LinkList *L,int n){
 2     //创建一个有n个结点的链表
 3     LinkList p;                                 //新结点
 4     int i;                                      //循环变量
 5     L = (LinkList)malloc(sizeof(LNode));        
 6     L->next = NULL;                             //构建一个带头结点的空链表
 7     for(i=0;i<n;i++){
 8         p = (listLink1)malloc(sizeof(LNode));   //申请申结点的内存
 9         scanf(&(p->data));                      //赋值
10         p->next = L->next;                      
11         L->next = p;                            //插入的表头
12     }
13 
14 }

 1 int ListInsert(LinkList *L,int i,ElemType e){
 2     //向第i个位置之前插入节点，数据域为e
 3     int j;                                  //查找插入位置的辅助变量，用于循环
 4     LinkList p,newNode;
 5     p = *L;                                 //将指针p指向链表头结点
 6     j = 1;                                  //从1开始遍历
 7     while(p&&j<i){
 8         p = p->next;
 9         j = j + 1;
10     }                                       //寻找插入位置，第i-1个节点
11                                             //这里之所以不用for是因为我不知道这个链表的长度
12     if(!p||j>i-1){
13         return 0;
14     }                                       //找到位置后，我们需要对位置j的合理性进行验证
15 
16     //下面就是正式的插入节点了
17     newNode = (LinkList)malloc(sizeof(LNode));
18                                             //申请新节点的内存位置
19                                             
20     newNode->data = e;                      //将e的值存入新节点的数据域
21     newNode->next = p->next;                //新节点的指针域指向第i个位置
22     p->next = newNode;                      //i-1位置的节点的指针域指向新节点
23                                             //但一定要注意上面三步的顺序
24                                             
25     return 1;                               //插入成功       
26 
27 }

 1 int ListDelete(LinkList *L,int i,ElemType *e){
 2     //删除第i个位置的结点，并用e返回其数据域
 3     int j;                                  //寻找删除位置的辅助变量，用于循环
 4     LinkList p,q;
 5     p = *L;                                 //将指针p指向链表头结点
 6     j = 1;                                  //从1开始遍历
 7 
 8     while(p->next&&j<i){
 9         p = p->next;
10         j = j+1;
11     }
12                                             //寻找删除的位置，注意这里是用p->next开始遍历的
13     if(!(p->next)||j>i){
14         return 0;
15     }                                       //判断删除位置是否合理
16                                             //这里要给大家简单解释一下，我们这里要判断的是p->next而不是p
17                                             //原因是，删除的时候要将删除位置的前后两个结点连起来，通过前面的while循环，前结点一定是存在的
18                                             //那么重点就是要判断一下是否存在后继结点了
19                                             //这样就会有另一个问题，最后一个元素怎么删除，答案是尾结点
20                                             //这里我们默认是存在尾结点的，这个尾结点和头结点的作用差不多，为了让最以后一个结点的插入和删除操作和别的结点是一样的
21 
22 
23     q = p->next;                            //让q指向要删除位置的结点
24     p->next = q ->next;                     //让要删除结点的前驱的后继指向要删除点的后继
25     e = q->data;                            //赋值
26     free(q);                                //释放内存
27 
28     return 1;                               //删除成功
29 }

 1 int GetElem(LinkList L,int i,ElemType &e){
 2     int j;                                      //计数变量
 3     LinkList p;                                 
 4 
 5     p = L->next;                                //p指向链表的第一个结点
 6     j = 1;                                      
 7 
 8     while(p && j<i){
 9         p = p->next;                            //p指向下一个结点
10         j = j+1;
11     }
12 
13     if(!p||j>i){
14         return 0;
15     }                                           //判断位置合理性
16                 
17     e = p->next;                                //赋值
18     return 1;                                   //成功
19 }

1 typedef struct DulNode
2 {
3     struct DulNode *prior;                      //前驱指针
4     struct DulNode *next;                       //后继指针
5     ElemType e;                                 //数据域
6 }DulNode,*DuLinkList;

1 s->prior = p;           //把p赋值给s的前驱，如图中的1
2 s->next = p->next;      //把p->next赋值给s的后继，如图中的2
3 p->next->prior = s;     //把s赋值给p-next的前驱，如图中的3
4 p->next = s;            //把s赋值给p的后继，如图中的4

1 P->prior->next = p->next; //把p->next的值赋给p->prior的后继，如图中的①
2 p->next->prior = P->prior;//把p=>prior赋值给p->next的前驱，如图中的②