1. 线性表：n个数据元素的有序集合。

线性表是一种常用的。在实际应用中，线性表都是以、队列、、等特殊线性表的形式来使用的。由于这些特殊线性表都具有各自的特性，因此，掌握这些特殊线性表的特性，对于数据运算的可靠性和提高操作效率都是至关重要的。　　线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。

特征：

1．集合中必存在唯一的一个“第一元素”；

2．集合中必存在唯一的一个 “最后元素” ；3．除最后一个元素之外，均有 唯一的后继(后件)；4．除第一个元素之外，均有 唯一的前驱(前件)。

java中的List接口，就是线性表。ArrayList就是顺序线性表，LinkedList就是链表线性表。

2. 线性表的顺序表示：ArrayList

一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。

优点：在于随机访问元素，

缺点：插入和和删除的时候，需要移动大量的元素。

c语言实现代码：

// Test.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include 
    
     #include "stdlib.h"//宏定义#define TRUE   1#define FALSE   0#define OK    1#define ERROR   0#define INFEASIBLE -1#define OVERFLOW -2#define LT(a,b)   ((a)<(b))#define N = 100       #define LIST_INIT_SIZE 100 //线性表初始空间分配量#define LISTINCREMENT   10 //线性表空间分配的增量typedef int Status;typedef int ElemType;typedef struct LNode{
     ElemType  *elem;        //存储空间的基地址 int      lenght;  //当前的长度 int   listsize;      //当前分配的存储容量}SqList;/** *构造空的线性表 */Status initList(SqList &L, int lenght){ if (lenght == 0) lenght = LIST_INIT_SIZE; L.elem = (ElemType *)malloc(lenght * sizeof(ElemType)); if(!L.elem) exit(OVERFLOW);  //分配存储空间失败 L.lenght = 0;     //初始空表长度为0 L.listsize = lenght ;//初始存储容量为100 return OK;}/************************************************************************//* 在第i位置插入e*//************************************************************************/Status insertList(SqList &L, ElemType e, int i){ ElemType *p,  *q; if(i<0 ||i > L.lenght) return ERROR;  //i值不合法 if (L.lenght >= L.listsize) {  ElemType *newbase = (ElemType *)realloc(L.elem ,(L.listsize +LISTINCREMENT)*sizeof(ElemType));  if(!newbase) return OVERFLOW; //存储分配失败    L.elem = newbase;    //新基值  L.listsize += LISTINCREMENT;    //增加存储容量 } q = &L.elem[i];      //q为插入的位置 for (p = &L.elem[L.lenght]; p>=q; --p) {  *p = *(p-1);     //i元素之后的元素往后移动 } *q = e;        //插入e L.lenght +=1; return OK;}/************************************************************************//* 快速排序 *//************************************************************************/void sortList(SqList &L){ }/************************************************************************//* 删除第i位置元素，并用e返回其值                                                                     *//************************************************************************/Status deleteListElem(SqList &L, int i, ElemType &e){ int *p,  *q; if(i<0 ||i > L.lenght) return ERROR;  //i值不合法 q = &L.elem[i];        //被删除元素的位置为i，L.elem就是数组名, e = *q;          //被删除元素的值赋值给e for (p = q; p< (L.elem + L.lenght); p++){ //元素左移  *p = *(p+1); } --L.lenght; return OK;}/************************************************************************//*  快速排序*//************************************************************************/int partition(SqList &L, ElemType low, ElemType high){ ElemType pivotkey = L.elem[low];         //枢轴记录关键字 while (low < high) {      //从表的两端向中间扫描  while (low < high &&  L.elem[high] >= pivotkey ) --high;//高端位置扫描  L.elem[low] = L.elem[high];  //交换数据，小于pivotkey移到低端  L.elem[high] = pivotkey;  while (low < high && L.elem[low] <= pivotkey ) ++low;     //低端扫描  L.elem[high] = L.elem[low];      //交换数据 大于pivotkey移到高端  L.elem[low] = pivotkey;          } return low;}void quickSort(SqList &L, ElemType low, ElemType high){ int pivot; if(low < high) {               pivot =  partition(L,  low,  high);    quickSort(L,  low,  pivot -1);   //低端子表排序  quickSort(L,  pivot +1, high);   //高端子表排序 } }/************************************************************************//* 合并两个线性表*//************************************************************************/void mergeList(SqList La, SqList Lb,  SqList &Lc){ ElemType *pa, *pb, *pc; Lc.listsize =  La.lenght + Lb.lenght; initList(Lc, Lc.listsize);   //初始化LC\pc = Lc.elem; Lc.lenght = Lc.listsize; pc = Lc.elem; pa = La.elem; pb = Lb.elem; while (pa <= &La.elem[La.lenght -1] && pb <= &Lb.elem[Lb.lenght -1]){  if (*pa <= *pb) *pc++ = *pa++;  else *pc++ = *pb++; } while(pa <= &La.elem[La.lenght -1]) *pc++ = *pa++; //插入La的剩余元素 while(pb <= &Lb.elem[Lb.lenght -1]) *pc++ = *pb++; //插入Lb的剩余元素}/************************************************************************//* 打印list*//************************************************************************/void printList(SqList L){ printf("当前值:");  for (int i =0; i
    

3. 线性表的链表表示LinkedList

一般使用链表 来描述。

优点：对于新增和删除操作add和remove和方便。不需要移动元素。

缺点：不方便随机访问元素，LinkedList要移动指针

代码实现：

// Test.cpp : Defines the entry point for the console application.//#include "stdafx.h"#include 
    
     #include "stdlib.h"//宏定义#define TRUE   1#define FALSE   0#define OK    1#define ERROR   0#define INFEASIBLE -1#define OVERFLOW -2#define LT(a,b)   ((a)<(b))#define N = 100       typedef int Status;typedef int ElemType;typedef struct LNode{
     ElemType  data;     struct LNode   *next; }LNode, *LinkList;/************************************************************************//*初始化链表*//************************************************************************/Status initList(LinkList &L){ /*单链表的初始化*/ L = (LinkList)malloc(sizeof(LNode));    //申请一个头节点 if(!L) exit(OVERFLOW);   //申请空间失败   L->next=NULL;    //建立一个带都节点的空链表 return OK; /*  需要改变指针的指针，所以参数必须是引用或者是 *L: (*L) = (Lnode *)malloc(sizeof(Lnode)); (*L)->next=NULL; return 1;                                                                      */}/************************************************************************//*     创建链表*//************************************************************************/void createList(LinkList L, int n){ /*单链表的初始化*/ if (!L) {  initList(L); } ElemType data; LinkList p,q = L; printf("输入节点数据的个数%d：\r\n", n); for(int i = 0; i
     
      data = data;  p->next = q->next;  q->next = p;  q = p; }}/************************************************************************//* 在第i位置插入e*//************************************************************************/Status insertList(LinkList L, ElemType e, int i){ LinkList s, p = L; int j = 0; while (p && j
      
       next;  j++; } if (!p ||j >i) return ERROR; s = (LinkList) malloc(sizeof(LNode));  //生成新节点 s->data = e; s->next = p->next;   //插入L中 p->next = s; return OK;}/************************************************************************//* 删除第i位置元素，并用e返回其值                                                                     *//************************************************************************/Status deleteListElem(LinkList L, int i, ElemType &e){ LinkList p, q; int j = 0; p = L; while (p && j
       
        next;  ++j; } if (!p->next || j>i)  return ERROR;   //删除的位置不对 q  = p->next; p->next = q->next; e = q->data; free(q);   //释放节点 return OK;}/************************************************************************/  /*  插入排序 */  /************************************************************************/  void  InsertSort(LinkList L){ LinkList  list;    /*为原链表剩下用于直接插入排序的节点头指针*/ LinkList  node;    /*插入节点*/ LinkList  p;   LinkList  q;   list = L->next;    /*原链表剩下用于直接插入排序的节点链表*/ L->next = NULL;    /*只含有一个节点的链表的有序链表。*/ while (list != NULL)   { /*遍历剩下无序的链表*/  node = list, q = L;     while (q && node->data > q->data  ) {   p = q;   q = q->next;  }    if (q == L) {  /*插在第一个节点之前*/   L = node;  }  else {   /*p是q的前驱*/   p->next = node;     }  list = list->next;  node->next = q; /*完成插入动作*/ }}/************************************************************************//* 合并两个线性表*//************************************************************************/void mergeList(LinkList  &La, LinkList  &Lb,  LinkList &Lc){ LinkList pa, pb, pc; pa = La->next; pb = Lb->next; Lc =  pc = La; while (pa && pa) {  if (pa->data > pb->data) {   pc->next = pb;   pc = pb;   pb =pb->next;  }else{   pc->next = pa;   pc = pa;    pa =pa->next;  } } pc->next = pa? pa :pb; free(Lb);}/************************************************************************//* 打印list*//************************************************************************/void printList(LinkList  L){ printf("当前值:"); LinkList p; p = L->next; while(p){  printf("%d ", p->data);   p = p->next; } printf("\r\n"); }void main(){ LinkList  La,Lb,Lc; ElemType e; int init,i; printf("LA:\r\n");   initList(La); createList(La, 5); insertList(La, 7,  3);   printList(La); deleteListElem(La, 3,  e);   printList(La); InsertSort(La); printList(La); printf("Lb:\r\n");   initList(Lb); createList(Lb, 4); InsertSort(Lb); printList(Lb); printf("Lc:\r\n");  initList(Lc); mergeList(La,   Lb,   Lc); printList(Lc);}