个人学习-数据结构-线性表，单链表C语言实现

线性表插入算法思路：
       如果插入位置不合理，抛出异常
       如果线性表长度大于等于数组长度，则抛出异常货动态增加容量
       从最后一个元素开始想前遍历到第i个位置，分别将他们都向后移动一个位置
       将要插元素填入位置i处
       表长加1

#define MAXSIZE 20
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;

typedef struct
{
   ElemType data[MAXSIZE];
   int length;
}SqlList;

//获取线性表某个数据
Status GetElem( SqList L, int i,ElemType *e)
{
   if(L.length==0 || i<1 || i>L.length)
      return ERROR;
    *e = L.data[i-1];
    return OK;
}

//插入
Status ListInsert(SqList *L, int i, ElemType *e)
{
      int k;
      if(L->length>=MAXSIZE)
         return ERROR;
      if(i<1|| i>L->length+1)
        return  ERROR;
      if( i<= L->length)
      {
          for(k=L->length-1;k>=i-1；k--)
           {
               L->data[k+1] = L->data[k] ;
           }
      }
      L->data[i-1] = e;
      L->length++;
      return OK;
}

//线性单链表存储结构
typedef struct Node
{
    ElemType type;
    struct Node *next;
} Node;
typedef struct Node   *LinkList;//定义LinkList

单链表的读取算法思路:
1.声明一个结点p指向链表的第一个结点，初始化j从1开始
2.当j<i 时就遍历表，让p指针向后移动，不断指向下一节点，j累加1；
3.若到链表末尾p为空，则说明第i个元素不存在
4.否则查找成功，返回结点p的数据

//单链表的读取
Status GetElem(LinkList L,int i,ElemType *e)
{
     int i,j;
    LinkList p;
    p = L->next;
    j = 1;
    while(p && j<i)
    {
       p = p->next;
       ++j;
     }
    if( !p && j<-=i)
     return ERROR:
    *e = p->data;
    return OK;
}

单链表的插入算法设计思路
1.声明一节点p指向链表第一个结点，初始化j从1开始
2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一节点，j累加1；
3.若到链表末尾p为空，则说明第i个元素不存在;
4.否则查找成功，在系统中生成一个空节点s；
5.将数据元素e赋值给s->data;
6.单链表的标准插入语句 s->next = p->next;    p->next = s;
7.返回成功

//单链表的插入
Status ListInsert(LinkList *L , int i, ElemType  e)
{
    int j;
    LinkList p,s;
    p = *L;
    j = 1;
    while(p && j<i)
    {
      p = p->next;
      ++j;
    }
    if(!p || j<=i)
        return ERROR;    //第i个元素不存在
    s = (LinkList)malloc(sizeof(Node));  //生成新节点
    s->data = e;
    s->next = p->next;   //将p的后继节点赋值给s的后继
    p->next = s;            //将s赋值给p的后继
    return OK;
}

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

//单链表的删除
Status ListDelete(LinkList *L ,int i, ElemType *e)
{
   int j;
    LinkList p,q;
    p = *L;
    j = 1;
    while(p->next && j<i)
    {
      p = p->next;
      ++j;
    }
    if(!(p->next)|| j>=1)
        return ERROR;
    q = p->next;
    p->next = q->next;        //将q的后继赋值给p的后继
    *e = q->data;                //将q结点中的数据给e
    free(q)
    return OK;
}

单链表整表创建的算法思路
1.声明一结点p和计数器变量i；
2.初始化一空链表L;
3.让L的头结点的指针指向NULL,即建立一个带头结点的的单链表
4.循环:
    生成一新节点赋值给p；
    随机生成一数字赋给p的数据域p->data
    将p插入头结点与新节点之间

//单链表的整表创建
void CreateListHead(LinkList *L,int n)
{
   LinkList p;
   int i;
   srand(time(0));                //初始化随机种子
   for(i=0;i<n;i++)
   {
      *L = (LinkList)malloc(sizeof(Node));   
       p->data = rand()%100+1;
       p->next = (*L)->next;
       (*L)->next = p
    }
}

单链表的整表删除的算法设计思路
1.声明一结点p q；
2.将第一个结点赋值给p；
3.循环:
         将下一结点赋值给q;
         释放p;
        将q赋值给p.

//单链表的整表删除
Status ClearList(LinkList *L)
{
    LinkList p,q;
    p = (*L)->next;
    while(p)
    {
          q = p->next;
          free(p);
           p = q;
    }
    (*L)->next = NULL;
    return OK;
}

单链表结构与线性表存储结构的优缺点
存储分配方式
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
时间性能
查找
   顺序存储结构O(1)
   单链表O(1)
插入和删除
  顺序存储结构需要平均移动表长的一半的元素,时间为O(n)
  单链表在线出某位置的指针后，插入和删除时间为O(1)
空间性能
  顺序存储结构需要预先分配好存储空间，分大了，浪费，分小了发生溢出
单链表不需要分配存储空间，只要有就可以分配，元素给叔也不受限制