C2 线性表（结合王道）
2.3线性表的链式表示
优点：对于插入 删除不需要移动大量元素 ,O(1);
缺点：对于存取来说，顺序表直接存，而链式表需要先遍历一遍，然后找一下第i个元素的地址，才能存取。O(n);
正好和顺序表互补起来了。
2.3.1单链表的定义
线性表的链式储存。
typedef struct { Elemtype data; struct LNode *next;//参考struct Date birthday;即定义了一个指向该结构体的指针。 }Lnode,*LinkList; Lnode a;//定义一个结构体变量 LinkList a;//指向结构体的指针
2.3.2 单链表上基本操作的实现
1.采用头插法建立单链表O(n)
有两种：
不建立头结点和建立头结点这两种不同的代码。
头结点的创建思路：
声明一结点p和计数器变量i;
初始化一空链表L；
让L的头结点的指针指向NULL，即建立一个带头结点的单链表；(循环实现后继结点的赋值和插入。)
https://www.bilibili.com/video/BV1os41117Fs?p=12
srand(time(0));/ /*srand()就是给rand()提供种子seed。如果srand每次输入的数值是一样的， 那么每次运行产生的随机数也是一样的，就是说，以一个固定的数值作为种子是一个缺点。 通常的做法是 以这样一句代码srand(unsigned time(NULL));来取代， 这样将使得种子为一个不固定的数， 这样产生的随机数就不会每次执行都一样了*/ int rand(void)； /*功能：产生随机值，从srand (seed)中指定的seed开始， 返回一个[seed, RAND_MAX（0x7fff）)间的随机整数。*/
LinkList List_headinsert (LinkList *L) { LNode *s; int x; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; scanf("%d",&x); while(x!=9999) { s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=L->next; L->next=s; scanf("%d",&x); } return L; }
尝试去编写一下空结点:
LinkList List_headinsert (LinkList *L) { LNode *s; int x; L=NULL; scanf("%d",&x); while(x!=9999) { s=(LNode*)malloc(sizeof(LNode)); s->data=x; s->next=L; L->next=s; scanf("%d",&x); } return L; }
2.采用尾插法建立单链表O(n)
LinkList List_TailInsert(LinkList *L) { int x; L=(LinkList)malloc(sizeof(LNode)); LNode *s,*r=L; scanf("%d",&x); while(x!=9999) { s=(LNode)malloc(sizeof(LNode)); s->data=x; r->next=s r=s; scanf("%d",&x); } r->next=NULL; return L; }
3.按序号查找节点值：O(n)
LNode *GetElem(LinkList L,int i) { int j=1; LNode *p=L->next; if(i==0) return L; if(i<1|| i>length) return NULL;// while(p&&j<i) { p=p->next; j++; } return p;//返回该查找的地址 }
4.按数值查找表结点：O(n) //遍历：如果有返回这个该数值的地址，如果没有，返回NULL LNode *LocateElem(LinkList L,ElemType e) { LNode *p=L->next; while(p!=NULL&&p->data!=e) p=p->next; return p; }
5.插入结点：(后插)
插入到第i个位置，先要找到i-1个位置，即找到前驱节点。这个叫做后插入 p是第i-1个地址，s是插入的新结点地址 p=GetElem(L,i-1);//O(n)。 s->next=p->next;//O(1) p->next=s；//O(1) 前插： s是插入的新节点地址，p是插入的后面一个地址。我先插入到p后面，交换数据 相当于插入到前面。 p=GetElem(L,i+1)；//O(n); s->next=p->next;//O(1) p->next=s;//先插入后面，再换到前面 temp=p->data;//O(1) p->data=s->data;//O(1) s->data=temp;//O(1)
6.删除节点操作： 通过找到前驱节点p来删除第i个结点： p=GetElem(L,i-1);//O(n); q=p->next;//O(1); p->next=q->next;//O(1); free(q);//O(1); 此时p是删除的结点: p=GetElem(L,i);//O(n); q=p->next; p->data=p->next->data; p->next=q->next; free(q); 假设删除第i个结点，而且第i个结点的地址我是知道的。 那么说他的时间复杂度是O(1);
当有头结点时： int length(int i,LinkList L){ if(*L.next=NULL) return 0; int i=0; LinkList p; p=L->next; while(*p.next!=NULL） { p=p->next; i++; } i=i+1; return i; } 当没有头结点的时候： 且当L！=空时候 int length(int i,LinkList L){ int i=0; LinkList p; p=L; while(p!=NULL） { p=p->next; i++; } i=i+1; return i; } 当没有头结点的空指针： int length(LinkList L){ f(L=NULL){ return 0; } } ）``` ### 2.3.3 双链表 ```c 结点类型描述： typedef struct DNode { ElemType data; struct DNode *prior *next; }DNode ,*DLinklist;
(待定)
把单链表和双链表比较起来，你会发现，无论是单链表还是双链表，其按照数值查找的方式与按照位序查找的方式是一样的。时间复杂度都得是O(n);
但是对于插入和删除来说就不一样的，你看前面就知道，插入和删除有前插有后插，前插的话你得先找到这一个元素的上一个元素
双链表的插入：
s->next=p->next; p->next->prior=s; s->prior=p; p->next=s;
对于插入来说:
当已知p的地址的时候，我插入到前面，需要O(n);插入到后面需要O(1);双链表需要O(1);
当我不知道p的地址的时候，三者均为O(n);
双链表的删除： p->next=q->next; q->next->prior=p; free(q);
2.3.3 循环链表
1.循环单链表：
好处：
1.删除，插入处处等价。
2.从任意一点都循环遍历整个表
3.设置尾指针，不设置头指针，这样处理头和尾都是O(1).
2.循环双链表：
当循环链表为空表时候，其头结点的prior与next都相等于L。
2.3.4 静态链表
静态链表借助数组来描述线性表的链式储存结构
#define MaxSize 50 typedef struct{ ElemType data; int next; }SLinkList[MaxSize];
静态链表以next==-1;作为结束的标志;
