线性表

Julia999

线性表的抽象数据类型Operation
IniList（*L）:初始化操作，建立一个空的线性表L。
ListEmpty（*L）：判断线性表是否为空表，若线性表为空，则返回True，否则返回false
ClearList（*L）:将线性表清空
GetElem（L,i，*e）：将线性表L中第i个位置袁术返回给e
LocateElem（L,e）:在线性表L中查找与给定e相等的元素，如果查找成功，返回该元素在表中序号表示成功，否则，返回0表示失败
ListInsert（*L,i,e）：在线性表L中第i个位置插入新元素e
ListDelete（*L，i，*e）：删除线性表中第i个位置元素，并用e返回其值
ListLength（L）：返回线性表L的元素的个数


存储结构：
顺序存储和链式存储


链式存储结构：
我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。这两部分信息组成数据元素称为存储映像，称为结点（Node）
对于线性表来说，总得有个头有个尾，链表也是。链表中第一个结点的存储位置叫头指针，最后一个节点指针为空
头结点的数据域是不存放任何信息的。
头指针：头指针是链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
无论链表是否为空，头指针都不为空。头指针是链表的必要元素
头结点是方便操作和统一而建立的，放在第一个结点之前，其数据域一般是无意义的。头结点不一定是链表的必要元素


头指针指向头结点，头结点中的数据域是不存储信息的。
空链表是这样的：头指针指向头结点，头结点指向NULL


单链表的插入:
假设存储元素e的结点为s，要实现结点P，P->next和s之间逻辑关系的变化。
分析:P有两个成员，一个是s，一个是P->next。s是计划要插入的那个结点（也就是元素e所在的结点）
那么，如何将结点s插入到ai和ai+1之间呢？
第一步：先让s的next指向原先结点的next指向的结点
s->next=P->next
第二步：再让原先的next指向s
P->next=s

思考：能不能将上面的两句换过来呢？
答案：不能。因为当原先的指针指向s之后，P的next就是固定的了，也就是指向了s。如果再让s的next指向P的next，也就变成了自己指向自己了。


单链表第i个数据插入结点的算法思路：
声明一结点p指向链表头结点，初始化j从1开始。
当j<1时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1
若到链表末尾p为空，则说明第i个元素不存在
否则查找成功，在系统中生成一个空结点s
将元素e赋值给s->data。
单链表插入用上面的两个标准语句
返回成功

1. Status ListInsert（LinkList *L，int i，ElemType e）
   
2. {
   
3.      int j;
   
4.      LinkList p,s;
   
5.      p=*L;
   
6.      j=1;
   
7.      while((p->next)&&j<i)  //用于寻找第i个结点
   
8.      {
   
9.             p=->next;
   
10.             j++;
    
11.      }
    
12.      if(!(p->next)||j>i)
    
13.      {
    
14.             return ERROR;
    
15.      }
    
16.      s=(LinkList)malloc(sizeof(Node));
    
17.      s->data=e;
    
18.      s->next=p->next;
    
19.      p->next=s;
    
20.      return OK;
    
21. }

复制代码

单链表的删除：
假设元素a2的结点为q，要实现结点q删除单链表的操作，其实就是将它的前继结点的指针绕过指向后继结点即可
第一步：将p->next指向p->next的next
p->next=p->next->next;
或者：p->next=q->next;


单链表第i个数据删除结点的思路：
声明结点p指向链表的第一个结点，初始化j=1；
当j<1时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
若到链表末尾p为空，则说明第i个元素不存在
否则查找成功，将欲删除节点p->next赋值给q
单链表的删除标准语句p->next=q->next；
将q结点中的数据赋值给e，作为返回
释放q结点

1. Status ListDelete（LinkList *L，int i，ElemType e）
   
2. {
   
3.      int j;
   
4.      LinkList p,s;
   
5.      p=*L;
   
6.      j=1;
   
7.      while(（p->next）&&j<i)  //用于寻找第i个结点
   
8.      {
   
9.             p=->next;
   
10.             j++;
    
11.      }
    
12.      if(!（p->next）||j>i)
    
13.      {
    
14.             return ERROR;
    
15.      }
    
16.     p->next=p->next->next;
    
17.     *e=q->data;
    
18.      free(q);
    
19.      return OK;
    
20. }

复制代码

顺序存储和链式存储：链式存储结构时间复杂度更小


单链表的整表创建的思路：
声明一结点p和计数变量i
初始化一空链表
让L的头结点的指针指向NULL，即建立一个带头结点的单链表
循环实现后继结点的赋值和插入


头插法建立单链表：
简单来说，就是把新加进的元素放在表头后的第一个位置：
先让新节点的next指向头结点之后
然后让表头的next指向新节点
emm，也就是我们日常生活中的插队....

1. void CreatListHead(LinkList *L,int n)
   
2. {
   
3.     LinkList p;
   
4.     int i;
   
5.     srand(time(0));  //初始化随机种子
   
6.     *L=(LinkList)malloc(sizeof(Node));
   
7.     (*L)->next=NULL;
   
8.     for(i=0;i<n;i++)
   
9.    {
   
10.         p=(LinkList)malloc(sizeof(Node));  //生成新的节点
    
11.         p->data=rand()%100+1;
    
12.         p->next=(*L)->next;
    
13.         (*L)->next=p;
    
14.    }
    
15. }
    
16. 
    

复制代码

尾插法建立单链表：

1. void CreatListTail(LinkList *L,int n)
   
2. {
   
3.     LinkList p,r;   //p是临时节点
   
4.     int i;
   
5.     srand(time(0));  //初始化随机种子
   
6.     *L=(LinkList)malloc(sizeof(Node));
   
7.      r=*L;
   
8.     for(i=0;i<n;i++)
   
9.    {
   
10.         p=(Node*)malloc(sizeof(Node));  //生成新的节点
    
11.         p->data=rand()%100+1;
    
12.        r->next=p;
    
13.        r=p;
    
14.    }
    
15.    r->next=NULL;
    
16. }
    

复制代码

单链表的整表删除：
声明结点p和q；
将第一个节点赋值给p，下一个节点赋值给q
循环执行释放p和q赋值给p的操作

1. 
   
2. Status CreatList（LinkList *L）
   
3. {
   
4.      LinkList p,q;
   
5.      p=(*L)->next;
   
6.      while(p)  
   
7.      {
   
8.            q=p->next;
   
9.            free(p);
   
10.            p=q;
    
11.      }
    
12.      (*L)->next=NULL; //变成一个空表
    
13.      return OK;
    
14. }

复制代码

很容易产生误区：为什么要用q？
p是一个节点，他除了有数据域，还有指针域。当我们释放p的时候，其实是对他整个节点进行删除和内存释放的工作。而我们整表删除是需要一个个节点删除的，所以需要用q来记载p的下一个节点

                               
登录/注册后可看大图

静态链表（用数组描述的链表就叫做静态链表）游标实现法

1. #define MAXSIZE 1000
   
2. typedef struct
   
3. {
   
4.     ElemType data;  //数据
   
5.     int cur;              //游标（Cursor）
   
6. }Component,StaticLinkList[MAXSIZE];

复制代码

我们约定：最后一个游标的值等于第一个有数据的元素的下标。第一个游标指向第一个没有存放数据的下标，剩下的游标指向都是下一个元素的下标，最后一个元素的游标一定是0
（最后一个作为表头，记录第一个有效数据所在的位置，第一个作为内存池，告诉你哪有位置可以插入）


对静态链表进行初始化相当于初始化数组：

1. Status InitList(StaticLinkList space)
   
2. {
   
3.      int i;
   
4.      for(i=0;i<MAXSIZE-1;i++)
   
5.     {
   
6.         space[i].cur=i+1;
   
7.     }
   
8.     space[MAXSIZE-1].cur=0;
   
9.     return OK;
   
10. }

复制代码

我们对数组的第一个和最后一个元素做特殊处理，他们的data不存放数据
我们通常把未使用的数组元素称为备用链表
数组的第一个元素，即下标是0的那个元素的cur就存放备用链表的第一个节点的下标
数组的最后的一个元素，即下标为MAXSIZE-1的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点的作用




静态链表的插入操作：
为了辨明数组中哪些分量未被使用，解决方法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表
每当进行插入时，便可从备用链表上取得第一个节点作为待插入的新节点
首先获取空闲分量的下标：

1. int Malloc_SLL(StaticLinkList space)
   
2. {
   
3.     int i=space[0].cur;
   
4.     if(space[0].cur)
   
5.     {
   
6.         space[0].cur=space[i].cur;
   
7.     //把他的下一个分量作为备用
   
8.     }
   
9.     return i;
   
10. }

复制代码

在静态链表L中第i个元素之前插入新的数据元素：

1. Status ListInsert(StatucLinkList L,int i,ElemType e)
   
2. {
   
3.     int j,j,l;
   
4.     if(i<1||i>ListLength(L)+1)
   
5.     {
   
6.         return ERROR;
   
7.     }
   
8.     j=Malloc_SLL(L);
   
9.     if(j)
   
10.     {
    
11.         L[j].data=e;

复制代码

技巧：把游标当成指针比较好理解。