线性表数据结构

1.定义和定义时注意的细节
线性表：（1）个数有限（2)都为数据元素且类型相同（3）是一种逻辑结构（顺序表和链表才是存储结构）
操作定义时，&L和L:带&意味着在操作中会对L进行改变，即把参数修改带回来，所以需要带&.
2.顺序表的定义

#define InitSize 10 typedef struct{ Elemtype *data; .......指向顺序表元素的指针（Elemtype是表示指针指向的元素的类型，如果是单链表就是struct LNode)，通过InitList中的malloc 函数使它指向数组的起始地址 int MaxSize; int length; }Sqlist; = struct{ Elemtype *data; int MaxSize; int length; } typedef struct Sqlist; void InitList(Sqlist &L) { L.data=https://www.it610.com/article/(Elemtype *)malloc(InitSize*sizeof(int)); L.length=0; L.MaxSize=InitSize; }

3.顺序表的特点
（1）存储密度大，每个元素只存储数据
（2）随机访问，第i个元素：data[i-1]
(3)拓展容量不便
（4）插入，删除不变
4.顺序表的增删查的时间复杂度（每个元素被的概率乘以平均次数）
插入：O(n)
删除：O(n)
按值查找：O(n)
5.单链表的定义和判断

typedef struct LNode{ Elemtype data; struct LNode *next; ....指向LNode的指针 }LNode,*LinkList; = struct LNode{ Elemtype data; struct LNode *next; ....指向LNode的指针 } typedef struct LNode LNode; typedef struct LNode* LinkList; 初始化： bool InitList(LinkList &L){....带头节点 L=(LNode*)malloc(sizeof(LNode)); L-next=null; }注意：LNode *p表示指向一个节点的指针，用来表示一个节点；LinkList p更多的表示一个单链表的头节点，通常用来定义一个单链表。

【线性表】判断空表：
带头节点：L-next==null;
不带：L==null;
6.单链表的建立

头插法(单链表逆置） LinkList List_HeadInsert(LinkList &L){ LNode *s; int x; InitList(L); scanf("%d",&x); while(x != 999){ s=(LNode *)malloc(sizeof(LNode)); s-data=https://www.it610.com/article/x; s-next=L-next; L-next=s; scanf("%d",&x); } return L; }尾插法 LinkList List_TailInsert(LinkList &L){ LNode *s,*r=L; int x; InitList(L); scanf("%d",&x); while(x != 999){ s=(LNode *)malloc(sizeof(LNode)); s-data=https://www.it610.com/article/x; r-next=s; r=s; scanf("%d",&x); } r-next=null; return L; }

7.双链表的建立

typedef struct DNode{ Elemtype data; struct DNode *prior,*next; ....指向LNode的指针 }DNode,*DLinkList; bool InitDlinkList(DLinkList &L){ L=(DNode*)malloc(sizeof(DNode)); if(L==Null) return false; L-prior=null; L-next=null; return true; }

8.双链表的插入

s-next=p-next; p-next-prior=s; s-prior=p; p-next=s; 必须先完成插入节点s右边的操作再执行左边的操作

不可随机存取，按位按值查找只能遍历
9.循环链表
循环单链表：尾指向头；
循环双链表：尾指向头，头指向尾；
10.静态链表
分配一片集中的区域来存放数据
增删操作不需要大量移动元素
查找只能从头节点开始，容量不能改变
适用场合：（1）不支持指针的低级语言（2）数据元素固定不变的场合
11.总结
（1）顺序表：支持随机存取，大片空间分配不便