线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。
一、线性表
1、线性表定义
ADT List
{
数据对象:
数据关系:
基本操作:
InitLIst(&L) //构造空链表
DestroyList(&L) //销毁链表
ClearList(&L) //清空为空表
ListEmpty(&L) //判断空表
LIstLenth(&L) //返回数据元素个数
GetElem(L, i, &e) //返回第i个数据元素存入e
LocateElem(L, e, compare()) //返回第一个满足函数的数据元素,若没有则返回0
PriorElem(L, cur_e, &pre_e) //返回cur_e的前驱
NextElem(L, cur_e, &next_e) //返回cur_e的后继
ListInsert(&L, i, e) //在位置i插入数据元素e
ListDelete(&L, i, &e) //删除第i个元素,并用e返回
ListTraverse(L, visit()) //对L的每个元素调用visit()
}ADT List
2、顺序表示和实现
(1)、定义
线性表的顺序表示:用一组连续的储存单元依次储存线性表的数据元素。
(2)、算法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
| #define INIT_ELEM 100 #define SIZE_ADD 10 typedef struct { Elemtype *elem; int length; int listsize; }List;
void InitList(List &L){ L.p=(Elemtype*)malloc(listsize*sizeof(List)); if(!L.p) exit(error); L.length=0; L.listsize=INIT_ELEM; }
void ListInsert(List &L, int j,ElemType e){ if(i < 1 || i > L.length + 1) return ERROR; if(L.length>= L.listsize){( newbase =(ElemType *)realloc(L.elem, (L.listsize + SIZE_ADD) * sizeof(ElemType));
if(!newbase) exit(error); L.elem = newbase; L.listsize += SIZE_ADD; } q=&(L.elem[i-1]); for(p =&(L.elen[L.length-1]); p>= q; p--) *(p+1)=*p; *q=e; ++L. length; }
void ListDelete(List &L,int i;ElemType &e){ if((i<1)||(i>L.length))return error; p=&(L.elem[i-1]); e=*p; q=L.elem+L.length-1; for(++p;p<=q;++q) *(p-1)=*p; --L.length; }
|
3、链表
(1)、单链表
1 2 3 4
| typedef struct LNode{ ElemType date; struct LNode *next; }LNode,*Linklist;
|
初始化
1 2 3 4 5 6 7 8 9 10 11 12 13
| bool InitLIst(LinkList &L){ L=NULL; return true; }
bool InitList(LinkList &L){ L=(LNode*)malloc(sizeof(LNode)); if(L=NULL)return false; L->next=NULL; return true; }
|
按位插入(leading node)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| bool ListInsert(LinkList &L,int i,ElemType e){ if(i<1)return false; LNode *p; int j=0; p=L; while(p&&j<i-1){ p=p->next; j++; } if(!p)return false; LNode *s=(LNode*)malloc(sizeof(LNode)); s->date=e; s->next=p->next; p->next=s; return true; }
|
指定节点前插操作(不传入头节点)
1 2 3 4 5 6 7 8 9
| bool InsertPriorNode(LNode *p,ElemType e){ if(p==NULL)return false; LNode *s=(LNode*)malloc(sizeof(LNode)); s->next=p->next; p->next=s; s->date=p->date; p->date=e; return true; }
|
删除指定节点
1 2 3 4 5 6 7
| bool DeleteNode(LNode *p){ LNode *q=p->next; p->date=p->next->dete; p->next=q->next; free(q); return true; }
|
尾插法(leading node)
初始化单链表
设置length记录链表长度
while循环{
每次读取一个元素e;
List Insert(L,length+1,e)插到尾部;
length++;
}
头插法(leading node)
初始化单链表
while循环{
每次读取一个数据元素e;
InsertNextNode(L,e);
}
(2)、双链表
1 2 3 4 5 6 7 8 9 10 11
| typedef struct DNode{ ElemType data; struct DNode *prior,*next; }Dnode,*DLinklist;
bool InitDLinkList(DLinkList &L){ L=(DNode*)malloc(sizeof(DNode)); L->prior=NULL; L-.next=NULL; return true; }
|
(3)、循环链表
循环单链表
1 2 3 4 5
| bool Empty(LinkList L){ if(l->next==L)return true; else return false; }
|
循环双链表
1 2 3 4 5 6
| bool InitDLinkList(DLinkList &L){ L=(DNode*)malloc(sizeof(DNode)); if(L==NULL)return false; L->next=L; L->prior=L; }
|
(4)静态链表
1 2 3 4
| typedef struct Node{ ElemType data; int next; }Node;
|