首先，线性表是一种最简单的一种数据结构。嗯，简单的说，一个线性表是n个数据元素的有限序列。（元素：可以是int ,float, double 等）

线性表的储存结构是这样的：

在表中a(i - 1)领先于ai ,ai 领先于 a(i+1)，则称 a(i-1)是ai的直接前驱元素，a(i+1)是ai的直接后驱元素。对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点（a1），有且仅有一个终端结点没有后继但有一个前驱结点（an），其它的结点都有且仅有一个前驱和一个后继结点。

线性表的顺序是指用连续的存储单元来存储线性表的数据元素。线性表的顺序存储结构是一种随机存取的存储结构。

其一般有两种顺序存储方式：数组和链表。（分解的用链表，最后附上数组的）

　　（1）用数组来存：　　优点：可以随机访问元素。　　缺点：插入和删除的时候需要移动大量的元素。

　　（2）用链表：　　优点：对于新增和删除很方便，不需要移动元素。　　缺点：不方便随机访问元素，需要一定元素。

　　

 

1.数组的实现

1 #include 
     
       2 #include 
      
        3  4 /******* 创建别名 ******/ 5 typedef int Status; 6 typedef int ElemType; 7  8 /******* 宏定义 *******/ 9 #define TRUE   1  10 #define FALSE   0  11 #define OK    1  12 #define ERROR   0  13 #define INFEASIBLE -1  14 #define OVERFLOW -2  15 16 /******* 线性表的动态分配顺序存储结构 *******/17 #define LIST_INIT_SIZE 100    //线性表存储空间的初始分配量18 #define LISTINCREMENT 10    //线性表存储空间的分配增量19 typedef struct{20     ElemType *elem;    //存储空间基址21     int length;        //当前长度22     int listsize;    //当前分配的存储容量23 }SqList;24 25 /******** 构造一个空的线性表 ********/26 Status InitList_Sq(SqList &L){27     L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));28     //让电脑分配（ElemType）的字节 * LIST_INIT_SIZE 数量个内存空间，然后地址给L.elem29     if (!L.elem)    //存储分配失败30         exit(OVERFLOW);    31     /*32         exit() 是电脑函数33         exit()通常是用在子程序中用来终结程序用的，使用后程序自动结束，跳回操作系统。34         exit(0)表示正常退出，35         exit(x)（x不为0）都表示异常退出36     */37     L.length = 0;    //空表长度为038     L.listsize = LIST_INIT_SIZE;    //初始存储的容量39     return OK;    //构造成功40 }
      
     

对线性表的一些基本操作：

 

1 #include 
     
        2 #include 
      
         3   4 /******* 创建别名 ******/  5 typedef int Status;  6 typedef int ElemType;  7   8 /******* 宏定义 *******/  9 #define TRUE   1   10 #define FALSE   0   11 #define OK    1   12 #define ERROR   0   13 #define INFEASIBLE -1   14 #define OVERFLOW -2   15  16 /******* 线性表的动态分配顺序存储结构 *******/ 17 #define LIST_INIT_SIZE 100    //线性表存储空间的初始分配量 18 #define LISTINCREMENT 10    //线性表存储空间的分配增量 19 typedef struct{ 20     ElemType *elem;    //存储空间基址 21     int length;        //当前长度 22     int listsize;    //当前分配的存储容量 23 }SqList; 24  25 /******** 构造一个空的线性表 ********/ 26 Status InitList_Sq(SqList &L){ 27     L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); 28     //让电脑分配（ElemType）的字节 * LIST_INIT_SIZE 数量个内存空间，然后地址给L.elem 29     if (!L.elem)    //存储分配失败 30         exit(OVERFLOW);     31     /* 32         exit() 是电脑函数 33         exit()通常是用在子程序中用来终结程序用的，使用后程序自动结束，跳回操作系统。 34         exit(0)表示正常退出， 35         exit(x)（x不为0）都表示异常退出 36     */ 37     L.length = 0;    //空表长度为0 38     L.listsize = LIST_INIT_SIZE;    //初始存储的容量 39     return OK;    //构造成功 40 } 41  42 /****** 在L中第i个位置之前插入新的元素e *******/ 43 Status insertList(SqList &L, ElemType e, int i){ 44     ElemType *p, *q;    //申明两个类型为ElemType的指针变量 45     if (i < 0 || i > L.length + 1) 46         return ERROR;  //i值不合法(i的合法范围为 1<=i<=L.length+1)  47     if (L.length >= L.listsize) {    //当前的存储空间已满，需要增加分配 48         ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType)); 49         /* 50             先判断当前的指针是否有足够的连续空间，如果有，扩大L.elem指向的地址，并且将L.elem返回； 51             如果空间不够，先按照newsize(L.listsize + LISTINCREMENT)*sizeof(ElemType)指定的大小分配空间， 52             将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来L.elem所指内存区域 53             （注意：原来指针是自动释放，不需要使用free），同时返回新分配的内存区域的首地址。即重新分配存储器块的地址。 54             如果重新分配成功则返回指向被分配内存的指针，否则返回空指针NULL。 55         */ 56         if (!newbase) 57             return OVERFLOW;   //存储分配失败(即newbase 为NULL)   58         L.elem = newbase;               //新基值   59         L.listsize += LISTINCREMENT;    //增加存储容量   60     } 61     q = &L.elem[i - 1];                     //q为插入的位置   62     for (p = &L.elem[L.length]; p >= q; --p) { 63         *(p + 1) = *p;                    //i元素及之后的元素往后移动   64     } 65     *q = e;                             //插入e   66     L.length++;        //表长加1     67     return OK;    //操作成功 68 } 69  70 /******** 删除第i个元素，并用e返回其值 **********/ 71 Status deleteListElem(SqList &L, int i, ElemType &e){ 72     ElemType *p, *q;    //申明两个类型为ElemType的指针变量 73     if (i<1 || i > L.length) 74         return ERROR;  //i值不合法 (i的合法范围是 1<=i<=L.length)  75     p = &L.elem[i - 1];                       //被删除元素的位置为i，L.elem就是数组名,   76     e = *p;                               //被删除元素的值赋值给e 77     q = L.elem + L.length - 1;            //表尾元素的位置 78     for (++p; p <= q; p++){        79         *(p - 1) = *p;        //被删除元素后的元素左移 80     } 81     L.length--;    //表长减一 82     return OK;    //操作成功 83 } 84  85 /************** 比较函数 **************/ 86 Status Integercompare(ElemType x, ElemType y){ 87     if (x == y) 88         return OK; 89     else 90         return ERROR; 91 } 92  93 /****** 在顺序线性表L中查找第i个值与e满足compare()的元素的位序 ******/ 94 int LocateElem_Sq(SqList L, Status e, Status(*compare)(ElemType, ElemType)){ 95     //Status(*compare)(ElemType, ElemType)是一个函数指针 96     int i = 1;    //第一个元素的位序 97     int *p; 98     p = L.elem;    //p为第一个元素的储存位置 99     while (i <= L.length&&!(*compare)(*p++, e))//从头开始一个一个往后比较（当到表尾或找到时跳出）100         i++;101     if (i <= L.length)    //即i在表L 的内部102         return i;    //返回找到的位序103     else104         return 0;    //没有找到105 }106 107 /********* 归并La和Lb得到新的线性表Lc *********/108 void MergeList_Sq(SqList La, SqList Lb, SqList &Lc){109     //已知顺序线性表La ,Lb的元素按值非递减排列110     ElemType *pa, *pb, *pc;        //申明3个类型为ElemType的指针变量111     Lc.listsize = Lc.length = La.length + Lb.length;    //Lc的长度是La的当前长度+Lb的当前长度112     pc = Lc.elem = (ElemType *)malloc(Lc.listsize*sizeof(ElemType));    //将Lc的首地址给pc113     if (!Lc.elem)    114         exit(OVERFLOW);    //存储分配失败(即Lc.elem 为NULL)115     ElemType *pa_last, *pb_last;    //申明2个类型为ElemType的指针变量116     pa_last = La.elem + La.length - 1;    //pa_last 是线性表La的末地址117     pb_last = Lb.elem + Lb.length - 1;    //pb_last 是线性表Lb的末地址118     while (pa <= pa_last && pb <= pb_last){    //判断La和Lb是否遍历完了119         if (*pa <= *pb) 120             *pc++ = *pa++;        //如果*pa <= *pb，则将*pc = *pa;121         else 122             *pc++ = *pb++;        //否则（*pa<*pb），则将*pc = *pb;123     }124     while (pa <= pa_last) *pc++ = *pa++;    //插入La的剩余元素125     while (pb <= pb_last) *pc++ = *pb++;    //插入Lb的剩余元素126 }127 128 int main(){129     //省略130     return 0;131 }
      
     

2.线性链表实现（单链表）

单链表的逻辑存储状态就是这样的。

一般的操作：

1 #include 
     
        2 #include 
      
         3   4 /******* 创建别名 ******/  5 typedef int Status;  6 typedef int ElemType;  7   8 /******* 宏定义 *******/  9 #define TRUE   1   10 #define FALSE   0   11 #define OK    1   12 #define ERROR   0   13 #define INFEASIBLE -1   14 #define OVERFLOW -2   15  16 /******* 单链表的存储结构 ******/ 17 typedef struct LNode{ 18     ElemType data;    //单链表的数据域 19     struct LNode *next;    //单链表的指针域 20 }LNode, *LinkList;    //*LinkList 是该结构体的指针 21  22 /******* 单链表的创建 ********/ 23 Status ListInit_L(LinkList &L){ 24     L = (LinkList)malloc(sizeof(LNode));    //申请一个头结点 25     if (!L)     26         exit(ERROR);    //申请空间失败（L = NULL） 27     L->next = NULL;        //建立一个空链表 28     return OK;    //操作成功 29 } 30  31 /******* 单链表的初始化 *******/ 32 void ListCreate_L(LinkList &L, int n){ 33     ElemType data1; 34     LinkList p, q;    //创建两个结构体指针 35     q = L;    //q指向L的地址 36     for (int i = 0; i < n; i++) {        //添加n个数据（即要循环n次） 37         p = (LinkList)malloc(sizeof(LNode)); //申请一个新节点   38         scanf("%d", &data1);        //输入数据 39         p->data = data1;            //p的数据域为data1 40         p->next = q->next;            //p的指针域指向 q的指针域指向的地址 41         q->next = p;                //再将q的指针域指向p 42         q = p;            //此时将p赋给q 43         //后面有配图解释 44     } 45 } 46  47 /********* 单链表中寻找元素 *********/ 48 Status GetElem_L(LinkList L, int i, ElemType &e){ 49     //当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR 50     LinkList p; 51     p = L->next;    //初始化，p指向第一个节点 52     int j =    1;    //j为计数器 53     while (p && j
       
        next; 55         j++; 56     } 57     if (!p || j >i)            //第i个元素不存在 58         return ERROR; 59     e = p->data;    //取第i个元素用e储存 60     return OK;        //操作成功 61 } 62  63 /********* 单链表中在第i个位置之前插入元素e ***********/ 64 Status ListInsert_L(LinkList &L, ElemType e, int i){ 65     LinkList s, p = L;     66     int j = 0;    //计数器 67     while (p && j < i - 1){                //顺着指针向后查找第i-1节点   68         p = p->next; 69         j++; 70     } 71     if (!p || j > i - 1)    //i小于1或者大于表长加一   就不是合法范围 72         return ERROR; 73     s = (LinkList)malloc(sizeof(LNode));       //生成新节点   74     s->data = e; 75     s->next = p->next;            //插入L中   76     p->next = s; 77     //后面有配图解释 78     return OK;    //操作成功 79 } 80  81 /****** 删除第i个元素，并由e返回其值 *********/ 82 Status ListDelete_L(LinkList &L, int i, ElemType &e){ 83     LinkList p, q; 84     int j = 0;        //计数器 85     p = L;            //初始化,将L的头指针给p 86     while (p->next && j < i-1){    //寻找第i个节点，并令p指向其前驱 87         p = p->next; 88         ++j; 89     } 90     if (!p->next || j > i-1)  //删除的位置不合理 91         return ERROR; 92     q = p->next;        //删除节点 93     p->next = q->next; 94     e = q->data;        //去其值给e 95     //后面有配图解释 96     free(q);            //释放节点   97     /* 98         free是调用操作系统的函数，将原先分配的内存区域释放 99         与malloc()函数配对使用，释放malloc函数申请的动态内存。100     */101     return OK;102 }103 104 /********* 逆位序输入n个元素的值，初始化单链表L **********/105 void CreateLiet_L(LinkList &L, int n){106     LinkList p;107     ElemType data1;108     for (int i = n; i > 0; i--){109         p = (LinkList)malloc(sizeof(LNode));110         scanf("%d", &data1);    //输入元素值111         p->data = data1;112         p->next = L->next;    //插入到表头113         L->next = p;114     }115 }116 117 /****** 归并La和Lb得到新的单链表Lc，Lc的元素也按非递减排列 *****/118 void mergeList(LinkList  &La, LinkList  &Lb,  LinkList &Lc){  119     LinkList pa, pb, pc;  120     pa  = La->next;  121     pb  = Lb->next;  122     Lc =  pc = La;        //用La的头结点作为Lc的头结点123     while (pa && pa) {        //当pa和pb都不为空的时候124         if (pa->data > pb->data) {  //当pa的数据域大于pb的数据域的时候125             pc->next = pb;            //pc的指针域指向pb126             pc = pb;                //将pb赋给pc127             pb =pb->next;            //pb后移一个128         }else{                        //当pa的数据域小于或等于pb的数据域的时候129             pc->next = pa;            //pc的指针域指向pa130             pc = pa;                //将pa赋给pc131             pa =pa->next;            //pa后移一个132         }  133     }  134     pc->next = pa? pa :pb;            //插入剩余段135     free(Lb);                        //释放Lb的头结点136 }137 138 int main(){139     //略140     return 0;141 }
       
      
     

 

 

 

 （循环链表和双向链表略）