首页 > 代码库 > 数据结构学习（一）、线性表
数据结构学习（一）、线性表
线性表的概述
线性表拥有零个或多个数据元素的有限序列。首先它是一个序列，也就是元素之间有顺序。
线性表分为静态线性表和动态线性表，常见的有顺序线性表(静态)、单向链表(动态)、双向链表(动态)
线性表抽象数据类型定义
ADT 线性表（List）Data 线性表的数据对象集合为{a1,a2,···,an},每个数据类型均为DataType.另外，除第一个元素外，
其他每个元素均只有一个直接的前驱，除最后一个元素外，其他每个元素均只有一个直接的后驱。Operation InitList(*L) : 初始化线性表，建立一个空的线性表L. ListEmpty(L) : 若为空，返回true ,否则返回false. Clear(*L) : 清除线性表. GetElem(L,i,*e) : 将线性表中的第i个元素值返回给*e. LocateElem(L,e) : 在线性表中查找e. ListInsert(*L,i,e) : 在L的第i个位置插入e. ListDelete(*L,i,*e) : 删除表L的第i个位置元素，并用e返回其值. ListLength(L) : 返回线性表L的元素的个数endADT
顺序表
c语言中的顺序存储可以用一维数组来实现。线性表的顺序存储的结构如下。
#define MAXSIZE 20typedef int ElemType;typedef struct{ ElemType data[MAXSIZE]; int length;}SqList;
初始化操作
#define ERROR 0
#define OK 1
Status InitList(SqList *L){ L->length =0; return OK;}
插入操作
#define ERROR 0
#define OK 1
Status ListInsert(SqList *L,int i, ElemType e){ int k; if(L->length == MAXSIZE) return ERROR; if(i<1 || i>L->length+1) return ERROR; if(i<L->length){ for(k=L->length-1;k>=i-1;k--) L->data[k+1] = L->data[k]; } L->data[i-1] = e; L->length++; return OK;}
删除操作
#define ERROR 0
#define OK 1
Status ListDelete(SqList *L,int i,ElemType *e){ int k; if(L->length ==0 || i<1 || i>L->length) return ERROR; *e = L->data[i-1]; if(i<L->length){ for(k=i;k< L->length;k++) L->data[k-1] = L->data[k]; } L->length--; return OK;}
获取元素操作
#define ERROR 0
#define OK 1
Status GetElem(SqList *L,int i ,ElemType *e){ if(L->length ==0 || i<1 || i>L->length) return ERROR; *e = L->data[i-1]; return OK;}
顺序线性表插入和删除操作需要移动大量的元素，并且空间无法把握，造成存储空间的“碎片”；
因此，我们干脆让所有的元素不再考虑相邻位置，哪儿有位置就到存储到哪里，但是让每个元素
都清楚它的下一个元素的位置在那里。这就是接下来要介绍的单向链表。
单向链表
单向链表的存储结构
typedef struct Node{ ElemType data; struct Node *next;} Node,*LinkList;
单链表的创建
Status InitList(LinkList *L){ *L = (LinkList)malloc(sizeof(Node));/*给头结点分配空间*/ if(!*L) exit(ERROR); *L->next = NULL; return OK; }
创建空头结点，这时此时后继不存在，则结点指针为空。
单链表的插入
Status ListInsert(LinkList *L,int i ,ElemType e){ LinkList p,s; int j; p = *L; j = 1; /* 获取插入点前一个结点；*/ while(p && j<i){ p = p->next; j++; } if(!p || j>i) return ERROR; s = (LinkList)malloc(sizeof(Node)); if(!s) return ERROR; s->data =http://www.mamicode.com/ e; s->next = p->next; p->next = s; return OK; }
单链表删除操作
ElemType ListDelete(LinkList *L,int i,ElemType *e){ LinkList p,q; int j; p = *L; j = 1; while(p && j<i){ p = p->next; j++; } if(!p || j>i) return ERROR; q = p->next; *e = q->data; p->next = q->next; free(q); return OK;}
单向循环链表
对于单向链表，每个结点只存储了向后的结点，到了尾标志就停止了向后链的操作，无法访问它之前的结点。
因此设计了单向循环链接。
此时，我们可以用O(1)的时间访问到第一个结点，但是对于最后一个结点，却需要O(n)时间，因此，我们继续
优化单向循环链表。
如图所示，终端用尾指针rear指示，则查找终端结点是O(1),开始点，为rear->next->next也为O(1)。
单向循环链表的创建
单向循环链表的结构跟单向链表结构相同。
Status InitList(LinkList*L){ *L = (LinkList)malloc(sizeof(Node)); if(!*L) /* 存储分配失败 */ exit(ERROR); (*L)->next = *L; return OK;}
单向循环链表的长度
int ListLength(LinkList L){ int i=0; LinkList p=L->next; /* p指向头结点 */ while(p!=L) /* 没到表尾 */ { i++; p=p->next; } return i;}
单向循环链表插入操作
循环链表插入操作和单向链表插入操作相似，值得注意的是当向末尾插入结点时，需将尾指针指向尾结点。
Status ListInsert(LinkList *L,int i,ElemType e){ int j; LinkList p,s; p=(*L)->next;/* p指向第1个结点 */ j=1; if(i<1||i>ListLength(*L)+1) return ERROR; while(j<i){ /* 寻找第i-1个结点 */ p=p->next; ++j; } s = (LinkList )malloc(sizeof(Node)); if(!s) /* 存储分配失败 */ exit(OVERFLOW); s->data=http://www.mamicode.com/e; s->next=p->next; p->next=s; if(p==*L){ *L = s; } /* 改变尾结点 */ return OK;}
单向循环链表删除操作
循环链表删除操作和单向链表删除操作相似，值得注意的是当删除末尾结点时，需将尾指针指向删除的结点的前一结点。
Status ListDelete(LinkList*L,int i,ElemType *e){ LinkList p,q; int j=1; p = (*L)->next; if(i<1||i>ListLength(*L)) return ERROR; while(j<i){ p=p->next; j++; } q = p->next; *e = q->data; p->next = q->next; if(*L==q) /* 删除的是表尾元素 */ *L=p; free(q); return OK;}
双向循环链表
此时，处于单向循环链表的an位置，但是我想访问an-1位置的数据，我只能重新遍历一次。这样非常浪费时间，有没有更迅速的方法呢？这就是接下来介绍的双向循环链表。
双向循环链表的存储结构
typedef struct DNode{ ElemType data; struct DNode *next; struct DNode *prior;} DNode ,*DLinkList;
双向循环链表的创建
Status InitList(DLinkList *L){ *L = (DLinkList)malloc(sizeof(DNode)); if(!*L) exit(ERROR); (*L)->next = *L; (*L)->data = http://www.mamicode.com/222; (*L)->prior = *L; return OK; }
双向循环链表的长度
int ListLength(DLinkList L){ int i=0; DLinkList p=L->next; while(p!=L) { i++; p=p->next; } return i; }
双向循环链表的插入
Status ListInsert(DLinkList *L,int i,ElemType e){ int j=1,length; DLinkList p,s; p = *L; length = ListLength(*L); if(i<1 ||i>length+1) return ERROR; s = (DLinkList)malloc(sizeof(DNode)); if(!s) exit(ERROR); while(j<i){ p=p->next; j++; } s->prior = p; s->data =http://www.mamicode.com/ e; s->next = p->next; p->next->prior=s; p->next = s; return OK;}
双向循环链表的删除
Status ListDelete(DLinkList *L,int i){ DLinkList p,s; int j=0; p = *L; if(i<0 || i>ListLength(*L)) return ERROR; while(j<=i){ p=p->next; j++; } p->prior->next = p->next; p->next->prior = p->prior; free(p); return OK;}
数据结构学习（一）、线性表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。