数据结构——表 1、定义： 线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。 2、特
数据结构——表1、定义：
线性表是一个线性结构，它是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。
2、特征/性质
1）集合中必存在唯一的一个第一个元素
2）集合中必存在唯一的一个最后元素
3）除最后一个元素之外，均有唯一的后继
4）除第一个元素之外，均有唯一的前驱
3、线性表的基本操作
1）初始化线性表initlist(l)
2）销毁线性表destorylist(l)
3）清空线性表clearlist(l)
4）求线性表的长度listlength(l)
5）判断线性表是否为空isempty(l)
6）获取线性表l中的某个数据元素内容getelem(l,i,e)
7）检索值为e的数据元素locateelem(l,e)
8）返回线性表l中e的直接前驱元素priorelem(l,e)
9）返回线性表l中e的直接后继元素nextelem(l,e)
10）在线性表l中插入一个数据元素listinsert(l,i,e)
11）删除线性表l中第i个数据元素listdelete(l,i,e)
4、线性表的顺序表示：arraylist
一般使用数组来描述 注意：数组中第i-1的单元存储着线性表中第i个数据元素的内容，换句话说，c语言中数组的下标从“0”开始，如果l是顺序表，则表中第i个数据元素是l.elem[i-1].
优点：在于随机访问元素 缺点：插入和删除的时候，需要移动大量的元素
补充：线性表复杂操作
1、求线性表的并集
思路：扩大线性表la,将存在于线性表lb中不存在线性表la中的数据元素插入到线性表la中去，只需要从线性表lb中依次去取的每个数据元素，并依值在线性表la中进行查访，如果不存在，则插入之
void union(list &la, list lb){ la_len = listlength(la); lb_len = listlength(lb); for(i = 1;i <= lb_len; i++) { getelem(lb, i, e);//取lb中第i个数据元素赋给e if(!locateelem(la,e,equal))//la中不存在和e相同的数据元素，则插之 listinsert(la, ++la_len, e); }}
算法复杂度：o(lalb)
2、线性表合并且按值非递减有序排列
void mergelist(list la, list lb, list &lc){ //已知线性表la和lb的数据元素按值非递减排序 initlist(lc); i = j = 1;k = 0; la_len = listlength(la); lb_len = listlength(lb); while((i <= la_len) && (j <= lb_len)) { getelem(la, i, ai); getelem(lb, j, bj); if(ai <= bj) { listinsert(lc, ++k, ai); ++i; } else { listinsert(lc,++k, bj); ++j; } } while(i <= la_len) { getelem(la,i++,ai); listinsert(lc, ++k, ai); } while(j <= lb_len) { getelem(lb,j++,bj); listinsert(lc,++k,bj); }}
算法复杂度：o(la+lb)
参考代码——典型操作代码实现
//数组定义 typedef struct { elemtype elem[list_max_length]; //指向存放线性表中数据元素 int length; //线性表的当前长度 int listsize; }seqlist; //初始化线性表 int initlist(seqlisi *l) { l.elem = (elemtype *)malloc(list_max_length*sizeof(elemtype));//分配空间 if(l.elem == null) exit(overflow);//存储分配失败 l.length = 0;//空表长度为0 l.listsize = list_max_length;//初始存储容量 return ok; } //销毁线性表 void destorylist(seqlist *l) { if(l.elem) free(l.elem);//释放线性表占据的所有存储空间 } //清空线性表 void clearlist(seqlist *l) { l.length = 0; } //求线性表的长度 int getlength(seqlist l) { return(l.length); } //判断线性表是否为空 int isempty(seqlist l) { if(l.length == 0) return true; return false; } //获取线性表l中某个数据元素的内容 int getelem(seqlist l,int i,elemtype *e) { if(i l.length) return error; *e = l.elem[i-1];//数组中第i-1个单元存储着线性表中第i个数据元素内容 return ok; } //在线性表l中检索值为e的数据元素 int locateelem(seqlist l,elemtype e) { for(i = 0;i < l.length;i++) if(l.elem[i] == e) return i+1; return 0; } //判定l中第一个与e满足关系compare()的数据元素的位序,如果没有，则返0 locateelem(l,e, int (*compare)(elemtype, elemtype)) { i = 1;//i的初值为第一个元素的位序 p = l.elem; //p的初值为第一个元素的存储位置 while(i= q;--p) { *(p+1) = *p; }//出入位置及之后的元素右边移动 *q = e;//插入e l.length++; return ok; } //把线性表中第i个数据元素删除 int listdelete(seqlist *l, int i, elemtype *e) { if(isempty(l)) return error; if(i l.length) return error; p = &(l.elem[i-1]);//p为被删除元素的位置 e = *p; //被删除元素的值赋给e q = l.elem + l.length - 1; //表尾元素的位置 for(p = p+1;p <= q;++p) *(p-1) = *p;//被删除元素之后的元素左移 --l.length; return ok; }
总结:顺序存储结构表示的线性表，在做插入或删除操作的时，平均需要移动大约一半的数据元素；对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；线性表的容量难以扩充
补充：顺序表的合并
void mergelist_sq(sqlist la, sqlist lb, sqlist &lc){ pa = la.elem;pb = lb.elem; lc.listsize = lc.length = la.length + lb.length; pc = lc.elem = (elemtype*)malloc(lc.listsize * sizeof(elemtype)); if(!lc.elem)exit(overflow); pa_last = la.elem + la.length - 1; pb_last = lb.elem + lb.length - 1; while(pa <= pa_last && pb <= pb_last) { if(*pa < *pb) *pc++ = *pa++; else *pc++ = *pb++; } //插入la剩余元素 while(pa head = (*linklist)malloc(sizeof(linklist));//为头结点分配存储单元 if(l->head) { l->head->next = null; return ok; } return error;}//摧毁链表void destorylist(link_list *l){ linklist *p; while(l->head)//依次删除链表中的所有结点 { p = l->head; l->head = l->head->next; free(p); }}//清空链表void clearlist(link_list *l){ linklist *p; while(l->head->next) { p = l->head->next; //p指向链表中头结点后面的第一个结点 l->head->next = p->next;//删除p结点 free(p);//释放p结点占据的存储空间 }}//求链表的长度int listlength(link_list l){ link_list *p; int len; for(p = l->head,len = 0;p->next == null; p=p->next,len++) return len;}//判断链表是否为空int isempty(link_list l){ if(l->head->next == null) return true; return false;}//通过e返回链表l中第i个元素的内容int getelem(link_list l, int i, elemtype *e){ p = l->next; j = 1;//初始化，p指向第一个结点，j为计数器 while(p && j next; ++j; } if(!p || j > i) return error; e = p->elem;//取第i个元素 return ok;}//算法复杂度为o(n)//在链表l中检索值为e的数据元素 linklist *locateelem(link_list l,elemtype e) { linklist *p; for(p = l->head->next; p&&p->elem != e; p=p->next); return(p); } //返回链表l中结点e的直接前驱结点 linklist *priorelem(link_list l,linklist* e) { linklist *p; if(l->head->next == e) return null;//检测为第一个结点 for(p=l->head;p->next&&p->next != e;p = p->next); if(p->next == e) return p; return null； } //返回结点为e的直接后继结点linklist *nextelem(link_list l,linklist* e){ linklist *p; for(p=l->head->next;p&&p!=e;p=p->next); if(p) p=p->next; return p;}补充：高级操作
1）插入结点
//在带头结点的单链线性表l中第i个位置之前插入元素e int listinsert(linklist *l,int i, elemtype) { p = l;j = 0; while(p && jnext; ++j }//需找第i-1个结点 if(!p || j>i-1) return error;//idata = e; s->next = p->next; p->next = s; return ok; }
复杂度为o(n)
2）删除结点
//在带头结点的单链线性表l中删除第i个元素，并由e返回其值int lisydelete(linklist *l, int i,elemtype &e){ p = l;j = 0; while(p->next && j next; ++j;//寻找第i个结点，并令p指向其前驱 } if(!(p->next) || j>i-1) return error; q = p->next; p->next = q->next; e = q->elem; free(q); return ok;}
复杂度为o(n)
3）合并有序链表
void mergelist_l(linklist &la, linklist &lb, linklist &lc){ pa = la->next; pb = lb->next; lc = pc = la;//用la的头结点作为lc的头结点 while(pa && pb)//由于链表的长度是隐藏的，修改循环条件 { if(pa->elem elem) { pc->next = pa; //pc所指结点链接到pc所指结点之后 pc = pa; pa = pa->next; } else { pc->next = pb; pc = pb; pb = pb->next; } } pc->next = pa ? pa : pb; free(fb);}
6、循环链表
循环链表的操作和线性链表基本一致，差别在于算法中循环条件不是p或p->next是否为空了，而是它们是否等于头指针。
7、双向链表