首先先说下什么是线性表。线性表是最简单的一种数据结构。通俗的来讲，一个线性表就是以n个数据元素的有限序列（相当于数学中的“有限个元素的数列”）。当n=0时，线性表是空表。 线性结构的特点： <1>:除第一个数据元素以外，每个数据元素都有前驱。 <2>:除最后一个数据元素以外，每个数据元素都有后继。 <3>:除以上两点外，每个数据元素都只有一个前驱和后继。 其次线性表的优缺点； 优点：访问某个位置的数据元素比较方便。 缺点：数据元素的插入和删除比较麻烦。时间复杂度也比较高。 现在来看一下怎么实现的。 先了解下其中的宏定义，以后的数据结构中也会用到同样的名称。
#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status;好了，现在才刚刚开始。 以下代码都是用C语言实现的。 首先是—–线性表的动态分配顺序存储结构——-
#define LIST_INIT_SIZE 100 //线性表初始空间分配量 #define LISTINCREMENT 10 //线性表空间分配的增量 typedef int ElemType; //这里用整型数据类型代替其他数据类型 typedef struct LNode { ElemType *elem; //存储空间的基地址 int lenght; //当前的长度 int listsize; //当前分配的存储容量 }SqList;接下来是创建一个空的线性表：
Status Listinit(SqList &L) { L.elem = (ElemType *)malloc( LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); //分配存储空间失败 L.lenght = 0; //初始空表长度为0 L.listsize = lenght ;//初始存储容量为100 return OK; }然后是对顺序线性表的插入进行的操作：
Status ListInsert(SqList &L, ElemType e, int i) { ElemType *p, *q; if(i<=0 ||i > L.lenght+1) 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-1]; //q为插入的位置 for (p = &L.elem[L.lenght]; p>=q; --p) { *p = *(p-1); //i元素之后的元素往后移动 } *q = e; //插入e L.lenght +=1; return OK; }嗯，看的可能有点不耐烦了，什么乱七八糟的变量名，其实我也不适应。然而需要学习这么课程所以还是耐心点看下去把。 删除操作也很简单直接上代码把：
Status ListDelete(SqList &L, int i, ElemType &e) { int *p, *q; //Status相当于int还是不太习惯写。 if(i<1 ||i > L.lenght) return ERROR; //i值不合法 ，超过了线性表的长度或者在第一个元素前面当然就是不合法了。 q = &L.elem[i-1]; //被删除元素的位置为i,i从0开始的所以是i-1; e = *q; //被删除元素的值赋值给e for (p = q; p< (L.elem + L.lenght-1);p++) { //元素左移 *(p)=*(p+1); } L.lenght--; return OK; }接着看下对线性表中某个元素的查找
int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))//这里是一个指针函数，传参数时只需要穿函数名就行 { int i=0; ElemType *p=L.elem; while(i<L.lenght&&!(*compare)(*p++,e))++i; if(i<L.lenght)return i+1;//因为从0开始的所以是i+1; else return 0; } int compare(ElemType x,ElemType y)//两个数相等的函数 { return x==y; }最后一个合并两个线性表开不开心，终于要结束了。
void mergeList(SqList La, SqList Lb, SqList &Lc) { int *pa, *pb, *pc; //ElemType一样的。 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的剩余元素 }基本操作就基本结束了。接下来放一份完整的代码，仅供参考：
#include <stdio.h> #include<stdlib.h> #include<iostream> using namespace std; //宏定义 #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 Listinit(SqList &L) { L.elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); //分配存储空间失败 L.lenght = 0; //初始空表长度为0 L.listsize = LIST_INIT_SIZE ;//初始存储容量为100 return OK; } //对顺序线性表的插入进行的操作： Status ListInsert(SqList &L, ElemType e, int i) { ElemType *p, *q; if(i<=0 ||i > L.lenght+1) 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-1]; p>=q; --p) { *p = *(p-1); //i元素之后的元素往后移动 } *q = e; //插入e L.lenght +=1; return OK; } //线性表的删除操作： Status ListDelete(SqList &L, int i, ElemType &e) { int *p, *q; //Status相当于int还是不太习惯写。 if(i<1 ||i > L.lenght) return ERROR; //i值不合法 ，超过了线性表的长度或者在第一个元素前面当然就是不合法了。 q = &L.elem[i-1]; //被删除元素的位置为i,i从0开始的所以是i-1; e = *q; //被删除元素的值赋值给e for (p = q; p< (L.elem + L.lenght-1);p++) { //元素左移 *(p)=*(p+1); } L.lenght--; return OK; } //在线性表中查找某个元素 int LocateElem(SqList L,ElemType e,Status(*compare)(ElemType,ElemType))//这里是一个指针函数，传参数时只需要穿函数名就行 { int i=0; ElemType *p=L.elem; while(i<L.lenght&&!(*compare)(*p++,e))++i; if(i<L.lenght)return i+1;//因为从0开始的所以是i+1; else return 0; } int compare(ElemType x,ElemType y)//两个数相等的函数 { return x==y; } //合并两个线性表 void mergeList(SqList La, SqList Lb, SqList &Lc) { int *pa, *pb, *pc; //ElemType一样的。 Listinit(Lc); //初始化LC\pc = Lc.elem; // Lc.lenght = Lc.listsize; Lc.lenght=La.lenght + Lb.lenght; 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的剩余元素 } int main() { SqList La,Lb,Lc; ElemType e; int init,i; Listinit(La); printf("请输入要输入的元素个数：\n"); scanf("%d",&La.lenght); for(int i=0;i<La.lenght;i++)//事例先输入10个数，大小可以自己更改 { scanf("%d",&La.elem[i]); } for(int i=0;i<La.lenght;i++) { printf("%d ",La.elem[i]);//输出顺序线性表 } cout<<endl; printf("请输入要查找的元素\n"); int u; scanf("%d",&u); int z=LocateElem(La,u,compare);//查找元素2是否在该线性表中 if(z) printf("查找的元素在第%d个位置上\n",z); else printf("该线性表中不存在该元素\n"); int mi,w; printf("请输入要插入的元素和位置\n"); scanf("%d%d",&mi,&w); int flag=ListInsert(La,mi,w);//在第w个位置插入一个数据元素 mi if(flag) printf("插入成功\n"); else printf("插入失败\n"); for(int i=0;i<La.lenght;i++) { printf("%d ",La.elem[i]);//输出插入后的顺序线性表 } printf("\n"); int m,k;//被删除的元素赋给m printf("请输入要删除的元素\n"); scanf("%d",&k); ListDelete(La,k,m); for(int i=0;i<La.lenght;i++) { printf("%d ",La.elem[i]); } printf("\n%d元素已经被删除\n",m); Listinit(Lb); printf("请输入另一个线性表的元素个数\n"); scanf("%d",&Lb.lenght); for(int i=0;i<Lb.lenght;i++)//输入另一个顺序线性表 { scanf("%d",&Lb.elem[i]); } for(int i=0;i<Lb.lenght;i++) { printf("%d ",Lb.elem[i]);//输出另一个顺序线性表 } printf("\n"); mergeList(La,Lb,Lc);//合并两个线性表 printf("输出合并后的线性表的长度\n"); for(int i=0;i<Lc.lenght;i++)//输出两个线性表 { printf("%d ",Lc.elem[i]); } return 0; }