数据结构 单链表&顺序表
顺序表：
一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。
优点：在于随机访问元素，
缺点：插入和和删除的时候，需要移动大量的元素。
链表：
优点：插入或删除元素时很方便，使用灵活。
缺点：存储密度小，空间单位利用效率低
在顺序表中实现的基本运算：
·插入：平均移动结点次数为n/2；平均时间复杂度均为O（n）。
·删除：平均移动结点次数为（n-1）/2；平均时间复杂度均为O（n）。
链表头结点的作用：
总结为：
头结点的作用主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。
顺序表的存储地址必须是连续的，链表可以是连续的，也可以不是连续的；
单链表的相关操作：
定义：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;初始化：
Status initList(LinkList &L){
/*单链表的初始化*/
L = (LinkList)malloc(sizeof(LNode)); //申请一个头节点
if(!L) exit(OVERFLOW); //申请空间失败
L->next=NULL; //建立一个带都节点的空链表
return OK;
/*
需要改变指针的指针，所以参数必须是引用或者是 *L:
(*L) = (Lnode *)malloc(sizeof(Lnode));
(*L)->next=NULL;
return 1;
*/
}创建链表：
void createList(LinkList L, int n){
/*单链表的初始化*/
if (!L) {
initList(L);
}
ElemType data;
LinkList p,q = L;
printf("输入节点数据的个数%d：\r\n", n);
for(int i = 0; i<n; i++) {
p = (LinkList) malloc( sizeof(LNode)); //申请一个新节点
scanf("%d",&data);
p->data = data;
p->next = q->next;
q->next = p;
q = p;
}
}元素插入：
Status insertList(LinkList L, ElemType e, int i){
LinkList s, p = L;
int j = 0;
while (p && j<i){ //寻找i节点
p = p->next;
j++;
}
if (!p ||j >i) return ERROR;
s = (LinkList) malloc(sizeof(LNode)); //生成新节点
s->data = e; s->next = p->next; //插入L中
p->next = s;
return OK;
}元素删除：
Status deleteListElem(LinkList L, int i, ElemType &e){
LinkList p, q;
int j = 0;
p = L;
while (p && j<i){
p = p->next;
++j;
}
if (!p->next || j>i) return ERROR; //删除的位置不对
q = p->next; p->next = q->next;
e = q->data; free(q); //释放节点
return OK;
}链表排序：（插入）
void InsertSort(LinkList L)
{
LinkList list; /*为原链表剩下用于直接插入排序的节点头指针*/
LinkList node; /*插入节点*/
LinkList p;
LinkList q;
list = L->next; /*原链表剩下用于直接插入排序的节点链表*/
L->next = NULL; /*只含有一个节点的链表的有序链表。*/
while (list != NULL) { /*遍历剩下无序的链表*/
node = list, q = L;
while (q && node->data > q->data ) {
p = q;
q = q->next;
}
if (q == L) { /*插在第一个节点之前*/
L = node;
} else { /*p是q的前驱*/
p->next = node;
}
list = list->next;
node->next = q; /*完成插入动作*/
}
}链表归并：
void mergeList(LinkList &La, LinkList &Lb, LinkList &Lc){
LinkList pa, pb, pc;
pa = La->next;
pb = Lb->next;
Lc = pc = La;
while (pa && pb) {
if (pa->data > pb->data) {
pc->next = pb;
pc = pb;
pb =pb->next;
}else{
pc->next = pa;
pc = pa;
pa =pa->next;
}
}
pc->next = pa? pa :pb;
free(Lb);
}区间删除：
void ListDelete_CL(LinkList &CL,ElemType min,ElemType max)
{
LNode *p,*sub;
p = CL;
while (p->next!=CL)
{
sub = p->next;
if (sub->data > min&&sub->data < max) {
p->next = sub->next;
}
// 通俗的说，sub 就是侦查兵，手中同时拿着 p->next 和 sub->next 这两条线，如果这和侦查兵位置被删除，他会把p->next 联到 sub->next 上
else p = p->next;
}
}元素定位：
int ListLocate_L(LinkList L, ElemType x)
{
LNode *p = L;
int ipos = 0;
while(p->next)
{
if(p->data==x) return ipos;
p=p->next;
ipos++;
}
return ipos;
}2-7
设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是
在头部插入新节点，那么新的节点下一个节点指向原来的头结点，新的头结点指针指向新插入的节点；
2-10
在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行
这个样子，S节点就成功插入了。
1-7
在顺序表上进行插入、删除操作时需要移动元素的个数与待插入或待删除元素的位置无关
错误：
假设原顺序表长度为n，在头节点插入（删除），需要移动n(n-1)个元素，尾节点不需要移动；
2-7
要将一个顺序表{a0,a1,……,an−1}中第i个数据元素ai(0≤i≤n-1)删除，需要移动（ ）个数据元素。
ai 是 第 i+1 个元素，需要移动剩下的元素，也就是 n-（i+1） ->B
1-3
将长度分别为m,n的两个单链表合并为一个单链表的时间复杂度为O(m+n)
错误：
合并成一个链表只需要让m的尾节点->next=n头结点，复杂度为 1
两个有序链表合并成一个有序链表的时间复杂度是O(m+n)
2-3
带头结点的单链表h为空的判定条件是
带头结点：h->next=null
不带头结点：h=null
这是单链表判空的两种方式；
2-4
将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是
对于这类题目来说，可以用这个么一个方式来解决，要求的是最小的比较次数，可以假设理想情况：假设其中一个链表中的元素全小于另一个链表里最小的元素
或者是全大于另一个链表里最大的元素，假设表长分别是m，n，那么最少比较次数就是 min(m,n)
2-7
对于一个具有N个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为
这就是常见的坑了，这道题其实是分解成了两道题，单链表询值，和插入操作
查询 O(n) + 插入O(1) = O(n)
2-10
将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（ ）
还是和上面一样的坑，寻找到m表尾，时间复杂度O(m)+链接1 = O(m）
这几道题推荐记下来：
Made by dong