线性表

             寒假还有将近一个星期啦，前期学习了腩哥的新闻发布系统，很有感触，发现原来代码可以整理得这么规范，以前自己做的东西完全就是想到什么就做什么，完全没有一个整体的思路，学习了之后对开发的整个流程以及代码的规范有了质的提升，真的学得很过瘾，，，以后说不定还会在网页这方面继续深造的！！！多的不想，现在离考研将近一年的时间就是一心一意地好好准备!

          数据结构的整体框架如下:

        线性结构的特点:在元素的非空集合中  

           (1)存在唯一的一个被称作“第一个”的数据元素
           (2)存在唯一的一个被称作“最后一个”的数据元素　　

           (3)除第一个之外，每个元素均只有一个前驱
           (4)除最后一个之外，每个元素均只有一个后继

                                                                                                                               线性表
  一:线性表的顺序表示和实现:

1.特点:逻辑相邻，物理相邻，地址连续

2.分配方式:

(1)静态分配:数组

(2)动态分配:

物理存储结构为:

　　Typedef struct {              //若后面不再用，可省略结构名
　　       ElemType   *elem;         //表基址
　　       int        length;        //表长（特指元素个数）
　　       int        listsize;       //表当前存储容量（字节数）
　　     }SqList;

3.基本操作:

(1)创建(初始化)

　  Status InitList_Sq( SqList &L )
　  { //构造一个空的线性表L。
　　  L.elem = (ElemType*)malloc( LIST_INIT_SIZE * sizeof( ElemType) );//申请内存区域，返回首地址
　　  If  ( ! L.elem )  
              exit ( OVERFLOW ) ;   // 存储分配失败
　　  L.length = 0;                 // 空表当前长度为0
　　  L.listsize = LIST_INIT_SIZE;  // 初始存储容量
　　  return   OK;
　  } // InitList_Sq

(2)向第i个位置插入一个元素

　　status listinsert ( &L,i,e)  {
　　 if (i<1 || i>L.len+1) return ERROR;  // i值不合法
　　 if (L.len = = L.lsize) {     // 当前存储空间已满，增加分配
　　   newbase = (Elemtype * ) realloc(L.elem, (L.listsize +
　　                     LISTINCREMENT) *  (sizeof(ElemType));
　　   if (!newbase) exit(overflow);   // 存储分配失败
　　   L.elem = newbase;              // 新基址
　　   L.listsize += LISTINCREMENT;  }       // 增加存储容量 
　　   q = &(L.elem[i-1]);             // q为插入位置
　　   for (p = &(L.elem[L.len-1]);p>=q;--p)   
　　        *(p+1) = * p;  // 元素后移
　　   *q = e;   ++L.len;  // 插入e，表长增1
　　 return OK; 
　　} //listinsert

    Status ListDelete ( &L,i,&e)   
   {
     if (i<1 || i>L.len ) 
          return ERROR; // 删除位置不合法
     p = &(L.elem[i-1]); // p 为被删除元素的位置
     e = *p;             // 被删除元素的值赋给 e
     q = L.elem + L.len – 1; // 表尾元素的位置地址
     for (p; p<q; ++p)   
           *p =*(p+1); // 被删除元素之后的元素左移
     -- L.len;    // 表长减1
    return OK; 
   } // ListDelete

4.时间复杂度+空间复杂度分析

插入平均移动次数为：n(n+1)/2÷(n+1)＝n/2 ≈ O(n)

删除平均移动次数为:  n(n-1)/2÷n=(n-1)/2≈ O(n)
5.优缺点分析:

优点：可以随机存取表中任一元素(查找方便)

缺点：在插入，删除某一元素时，需要移动大量元素(非查找不方便)

先发表再说，玩去了，晚上再来总结链表

线性表

原文：http://blog.csdn.net/wust__wangfan/article/details/19037071