本文主要是介绍DataStructure_3.List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
3.1线性表是有限序列
- 元素之间是有顺序的，每个元素至多有一个前驱一个后继，首元素无前驱，尾元素无后继
- 在较复杂的线性表里面，一个数据元素可以由若干数据线组成(就比如说花名册，一个学号对应一个学生，符合元素之间的顺序性，但是每个学生名字后面还可以有很多项信息，比如成绩，爱好什么的)
- 线性表常用的几个操作：重置为空表、插入数据、删除数据、查找元素、获取线性表长度。
例题：
将所有的在线性表Lb中但不在La中的数据元素插入到La中：
| cpp代码实现 |
| ds.h #ifndef DSH #define DSH
#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2
//Status是函数的类型，其值是函数结果状态代码 typedef int Status; typedef int ElemType;
#endif |
| List.h #ifndef LISTH #define LISTH #include "ds.h"
#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct{ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量(以sizeof(ElemType)为单位) }List; //俗称顺序表
#endif
Status InitList(List *); void CreateList(List *, int[],int); int ListLength(List); void GetElem(List, int, ElemType *); int LocateElem(List, ElemType, Status (*compare)(ElemType,ElemType)); Status ListInsert(List *, int, ElemType); void PrintList(List); |
| #include <iostream> #include<stdlib.h> #include "List.h" using namespace std; Status InitList(List &L)//构造一个空的线性表L。 { L.elem=(ElemType*)new int(LIST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } //InitList
void CreateList(List &L, int a[],int n)//顺序输入n个数据元素，建立顺序表 { int i; for(i=0;i<n;++i) L.elem[i]=a[i]; //输入元素值 L.length=n; } //CreateList
int ListLength(List L){ return L.length; }
void GetElem(List L, int i, ElemType &e){ e=L.elem[i-1]; }
int LocateElem(List L, ElemType e, Status (*compare)(ElemType,ElemType)){ int i; int *p; i=1; //i的初值为第1元素的位序 p=L.elem; //p的初值为第1元素的存储位置 while(i<=L.length && !(*compare)(*p++,e)) ++i; if (i<=L.length) return i; else return 0; }
Status ListInsert(List &L,int i,ElemType e) /* 在顺序线性表L的第i个位置之前插入新的元素e,i的合法值为1≤i≤ListLength(L)+1 */ { ElemType *newbase,*q,*p; if(i<1 || i>L.length+1) return ERROR; //i值不合法 if(L.length>=L.listsize) { //当前存储空间已满，增加分配 int* newbase=(ElemType*)new int((L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); //存储分配失败 L.elem=newbase; //新基址 L.listsize+=LISTINCREMENT; //增加存储容量 } int* q=&(L.elem[i-1]); //q为插入位置 for(int* p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; //插入位置及之后的元素右移 *q=e; //插入e ++L.length; //表长增1 return OK; } // ListInsert
void PrintList(List L)// 输出顺序表L { int i; cout<<endl; for(i=1;i<=L.length;++i) cout<<L.elem[i-1]<<",";// 输入元素值 cout<<endl; }
int a[]={3,5,8,11}; int b[]={2,6,8,9,11,15,20};
Status equal(ElemType,ElemType); void Union(List &,List);
Status equal(ElemType x,ElemType y){ return x==y; }
void Union(List &La,List Lb){ // 将所有在线性表Lb中但不在La中的数据元素插入到La中 int i; int e; int La_len,Lb_len; La_len=ListLength(La); Lb_len=ListLength(Lb); for(int i=1;i<=Lb_len;i++) { GetElem(Lb,i,e); if(!LocateElem(La,e,equal)) ListInsert(La,++La_len,e); } }//Union
int main() { List La,Lb; InitList(La); InitList(Lb); CreateList(La,a,4); CreateList(Lb,b,7); cout<<"集合A："; PrintList(La); cout<<"集合B："; PrintList(Lb); Union(La,Lb); cout<<"集合A U B："; PrintList(La); return 0; } |
3.2线性表的顺序存储结构
3.2.1 三个属性：①存储空间的起始位置(数组首地址)
②最大存储容量(最大数组元素个数)
③数组长度(存放线性表的存储空间的长度)
线性表当前长度(线性表中数据元素的个数，随着线性表的插入或删除操作的进行，这个量随时变化)任意时刻，线性表的长度小于等于数组的长度
3.2.2 需要注意的是：
- 线性表起始位置是1，但用高级语言实现的时候一维数组起始位置却是0，于是注意线性表的第i个元素是要存储在数组下标为i-1的位置。即a1->La[0]
a2->La[1]…an->La[n-1]
- location(ai)=location(a1)+(i-1)*sizeof(ElemType)//存取时间性能为O(1)，而具有O(1)存取时间性能的存储结构通常称为随机存取结构
- 但在删除或插入数据时，由于变化了一个元素这个元素变化位置后面的所有元素都随之变化，所以取中间元素位置为平均情况，元素移动次数为(n-1)/2，故平均时间复杂度为O(n)所以顺序表比较适合数据元素不太变化，而主要操作是数据的存取的应用。当然还有其他优缺点：
| 优点 | 缺点 |
|
|
3.3链式存储结构
3.3.1 特点是用一组任意的存储单元存储线性表的数据 元素，这组存储单元既可以是连续的也可以不是。所以与顺序存储结构不同，链式存储结构中数据元素是分散在内存中的，这么做的优点是在插入或删除数据时不需要遍历后面的所有元素，只需要"改变"这个元素后面的一个元素即可。但需要付出的代价是每个数据元素不光要存储自身的信息，还需要存储它后继元素的存储地址。
线性表的链式存储结构用高级语言表示为单向链表。
| 数据元素a的存储映像(a.k.a 结点Node) | ||
链表中第一个结点的存储位置(类比数组名)称为头指针，并规定最后一个结点指针为NULL或"^"，同时，还可以在第一个结点前添加一个结点，称为头结点，头结点数据域可以不存也可以存像线性表长度等附加信息；头结点指针域存储着指向第一节点的指针 |
3.3.2 注意：
- 无论链表是否为空，头指针均不为空，头指针是链表的必要元素。
- 若有头结点时，则头指针指向头结点。无头结点时，头指针指向第一结点。
单链表的读取
3.3.3 单链表的读取
核心是工作指针后移，由于单链表结构没定义表长，所以无法事先知道要循环多少次，因此不方便使用for语句来控制循环。时间复杂度最小O(1)最大O(n)，取决于要寻找的i结点的位置。
3.3.4 单链表的插入与删除
3.3.4.1 插入
| 单链表插入标准语句 | s->next=p->next; p->next=s;
a.k.a s.next=p.next; p.next=s; |
单链表第i个结点位置之前插入新数据元素e的算法思路：
①声明一个指针p指向链表头指针和一个计数器j(初始化从1开始)
②当j<i时，就遍历链表(/*while(p && j<i)*/)，让指针p向后移动，不断指向下一节点(/*p=p->next*/)，并且++j
③若到链表末尾p为空，则说明第i个结点不存在
(/*if(!p || j>i) return ERROR*/)
④若查找成功，则在系统中生成一个空结点s，并将数据元素e赋值给空结点s的数据域
(/* s=(LinkList) malloc (sizeof(Node));
| //Node声明语句: typedef struct Node{ ELemType data; struct Node *next; }Node; //LinkList声明语句：typedef struct Node* LinkList； |
s->data=e;*/)
⑤单链表数据插入标准语句
/*s->next=p->next；p->next=s；*/
⑥return OK；
3.3.4.2 删除
删除结点的思路很简单，就是将要删除的结点的前继结点的指针绕过它，直接指向它的后继节点即可。抽象步骤为p->next=p->next->next，设要删除的结点为q，将p->next换为q则得到单链表数据删除标准语句
q=p->next; p->next=q->next;
单链表删除第i个结点并用e返回其值的算法思路：
①主体思路与插入结点基本相同①-③
②若查找成功，将欲删除的结点p->next赋值给q(与插入结点时的q相同，均为新声明的指针，并指向头指针)
/*q=p->next;*/
③使用单链表数据删除标准语句
/* p->next=q->next;*/
④将q指向的待删除结点中的数值赋给e，以返回其值
*e=q->data;
⑤释放q指向的待删除结点/*free(q);*/
⑥return OK
3.3.4.3 注意
- 初始条件：顺序线性表L已存在，且1≤i≤ListLength
- 结点插入代码头
Status ListInsert(LinkList *L，int i，ElemType e){
…
}
- 结点删除代码头
Status ListDelete(LinkList *L，int i，ElemType *e){
…
}
- 对于插入或删除数据越频繁的操作，单链表的优势就越是明显。比如要从第i个位置插入10个结点，单链表只需要在第一次找到第i个位置的指针，此时为O(n)，接下来只是简单地通过赋值移动指针而已，每次都是O(1)；而顺序表在每一次插入都需要移动n-i个结点，每次都是O(n)。
3.3.5 单链表的整表创建
分为头插法(每次始终让新结点在第一的位置)和尾插法(始终让新结点在最后的位置)
| //随机产生n个元素的值，建立代表头结点的单链线性表L（头插法） void CreateListHead(LinkList * L,int n) { LinkList p; int i; srand(time(0)); //随机产生数 *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; //先建立一个带头结点的单链表 for (i=0;i<n;i++) { p = (LinkList)malloc(sizeof(Node)); //生成新结点 p->data = rand()%100+1; //随机生成1001以内的数字 p->next = (*L)->netx; (*L)->next = p; //插入到表头 } }
//随机产生n个元素的值，建立代表头结点的单链线性表L（尾插法） void CreateListTail(LinkList * L,int n) { LinkList p,r; int i; srand(time(0)); //随机产生数 *L = (LinkList)malloc(sizeof(Node)); r = *L; for (i=0;i<n;i++) { p = (LinkList)malloc(sizeof(Node)); //生成新结点 p->data = rand()%100+1; //随机生成1001以内的数字 r->next = p; //将表尾终端结点指向新结点 r = p; //将当前新结点定义为表尾终端结点 } r->next = NULL; //表示当前链表结束 }
|
3.3.6 单链表的整表删除
算法思路：
声明两结点p、q，将第一个结点赋值给p，进入循环{将下一结点赋值给q;释放p;将q赋值给p;},最后使头结点指针域为空/*(*L)->next=NULL;*/
| Status ClearList(LinkList *L) { LinkList p,q; p = (*L) -> next;//p指向第一个结点 while(p){ q = p->next; free(p); p = q; } (*L) -> next = NULL;//头结点指针域为空 return OK; } |
3.3.7 循环链表
将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种首尾相接的单链表称为单循环链表，a.k.a循环链表。好处是解决了从当中一个结点出发访问链表全部结点的问题。
循环链表和单链表的差别就在于循环的判断条件上，原来是判断p->next是否为空而结束循环现在是是否等于头结点而结束循环。
为了能用更短的时间O(1)由链表指针访问到最后一个结点，现在对循环链表改造，不用头指针，而是用指向终端结点的尾指针rear来表示循环链表，此时查找开始结点和终端结点都很方便了，查找终端结点是O(1)，查找开始结点是rear->next->next，也是O(1)。
3.3.8 双向链表
在单链表基础上每个结点增加一个存储前驱结点地址的指针域
| typedef struct DulNode{ ELemType data; struct DulNode *prior;//直接前驱指针 struct DulNode *next;//直接后继指针 }DulNode，*DuLinkList; |
双向链表也可以是循环链表
双向链表插入数据时需要改变两个指针变量，优点是增加量结点的前后结点的可操作性，提升了时间性能，但空间占用会增加，所以是用空间换时间。
如要把结点s插入到结点p和p->next之间，则需要
| s->prior=p； s->next=p->next； p->next->prior=s； p->next=s； |
| 顺序是先搞定s的前驱和后继，再搞定后结点的前驱，再解决前结点的后继。 |
删除操作原理相同，比如要删除结点p
| p->prior->next=p->next； p->next->prior=p->prior； free(p)； |
这篇关于DataStructure_3.List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
