数据结构表
- WBOYOriginal
- 2016-06-07 15:59:461572browse
数据结构——表 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 < 1 || 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<= L.length && !(*compare)(*p++,e))
++i;
if(i <= L.length)return i;
else return 0;
}
//在线性表中第i个数据元素之前插入数据元素e
int ListInsert(SEQLIST *L,int i,Elemtype e)
{
if(L.length >= L.listsize)
exit(OVERFLOW);
if(i < 1||i>L.length + 1)
return error;//检查i值是否合理
q = &(L.elem[i-1]); //q为插入的位置
for(p = L.elem[Length-1];p >= 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 < 1 ||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 <= pa_last)
*pc++ = *pa++;//插入La的剩余元素
while(pb <= pb_last)
*pc++ = *pb++;//插入Lb的剩余元素
}
算法复杂度为O(La.length + Lb.length)
5、线性表的链表表示LinkedList
一般采用链表来描述
优点：对于新增和删除操作add和remove方便，不需要移动元素 缺点：不方便随机访问元素，因为LinkedList要移动指针
补充：高级操作
复杂度为O(n)
复杂度为O(n)
6、循环链表
常用术语：
1）表示每个数据元素的两个部分信息组合在一起叫做结点；
2）其中表示数据元素内容的部分叫做数据域data
3）表示直接后继元素存储地址的部分叫做指针或指针域next
4）head是头指针，它指向单链表中第一个结点，这是单链表操作的入口点，最后一个结点没有直接后续结点，所以放入NULL
5）为了简化对链表的操作，常在链表的第一个结点之前附加入一个结点，并称为头结点
特征：喎?http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjxicj4KMaOpz9/Q1LHt1tC1xMr9vt3UqsvY1Nq05rSitaXUqtbQtcS05rfFy7PQ8tPrwt+8rcuz0PKyu9K7tqjSu9bCo7vTw9K71+nIztLitcS05rSitaXUqrTmtKLP39DUse21xMr9vt3UqsvYo6jV4tfptOa0orWl1Kq/ydLUysfBrND4tcSjrNKyv8nS1MrHsrvBrND4tcSjqTxicj4KMqOp1Nq21M/f0NSx7bLZ1/fKsaOs1rvE3M2ouf3Nt9a41eu9+MjrwbSx7aOssqLNqLn9w7+49r3hteO1xNa41evT8s/yuvPJqMPoxuTT4L3hteOjrNXi0fm+zbvh1OyzydGw1dK12tK7uPa94bXjus3RsNXS1+6689K7uPa94bXjy/m7qLfRtcTKsbzksru1yKOsvt/T0NXi1tbM2LXjtcS05siht73KvbG7s8bOqsuz0PK05siht73KvaGjPGJyPgo8c3Ryb25nPrLOv7y0+sLroaqhqrXk0M2y2df3yrXP1jwvc3Ryb25nPjwvcD4KPHByZSBjbGFzcz0="brush:sql;">//实现线性表的链式存储结构的类型的定义
typedef struct linklist//结点类型
{
Elemtype elem;
struct linklist *next;
}LINKLIST;
typedef struct//链表类型
{
LINKLIST *head;
}LINK_LIST;
//初始化链表
int InitList(LINK_LIST *L)
{
L->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 && j<i-1)
{
p = p->next;
++j
}//需找第i-1个结点
if(!p || j>i-1)
return error;//i<1或者大于表长加1
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return ok;
}
2）删除结点
//在带头结点的单链线性表L中删除第i个元素，并由e返回其值
int LisyDelete(LinkList *L, int i,ElemType &e)
{
p = L;j = 0;
while(p->next && j < i-1)
{
p = p->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;
}
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 <= pb->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);
}
循环链表的操作和线性链表基本一致，差别在于算法中循环条件不是p或p->next是否为空了，而是它们是否等于头指针。
7、双向链表
