链表

大体的框架

单链表的定义和基本操作

定义

• 什么是单链表
  • 每个节点包括数据和指向下一个元素的指针
  • 优点：无需连续的存储空间

#定义一个单链表(不带头节点）

typedefstructLNode{//定义单链表节点类型ElemType data;//每个节点存放一个数据元素structLNode*next;//指针指向下一个节点}LNode，*LinkList;//LNode强调是一个节点，LinkList强调是一个链表LinkList p=(LNode*)malloc(sizeof(LNode));//增加一个新的节点，并用指针p指向该节点};

初始化(不带头节点）

boolInitList(LinkList&L){L=NULL;returntrue;}

判空（不带头节点）

boolEmpty(LinkList L){if(L==NULL)returntrue;elsereturnfalse;}

#定义一个单链表（带头节点）

typedefstructLNode{Elemtype data;structLNode*next;}LNode,*LinkList;

初始化一个单链表（带头节点）

boolInitList(LinkList&L){L=(LNode*)malloc(sizeof(LNode));if(L==NULL)//内存不足，分配失败returnfalse L->next=NULL;//头节点之后暂时还没有节点returntrue;}

判空(带头节点)

boolEmpty(LinkList L){if(L->next==NULL)returnfalse;elsereturnfalse;}

#按位序插入

带头结点

• 在第i个位序插入指定元素e
• 头节点可以看作第0个节点

boolListInsert(LinkList&L,inti,ElemType e){if(i<1)//判断输入位序是否合法returnfalse； LNode*p;intj=0;//位序计数器p=L;//头节点是第0个节点while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;if(p==NULL)//判断输入位序是否大于链表总长度，是否合法returnfalse;LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;//最后修改第i-1个节点returntrue;}

不带头节点

• 第1个位置插入需要特殊处理，因为没有头节点

boolListInsert(LinkList&L,inti,ElemType e){if(i<1)returnfalse;if(i==1){//插入第一个位序特殊处理LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=L;L=s;//头指针指向新节点returntrue;}LNode*p;//扫描节点intj=1;//计数器p=L;//从第一个节点开始扫描while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL)//i值不合法returnfalse;LNode*s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;returntrue;//插入成功

#指定元素后插操作

bool InsertNextNode（LNode*p,ElemType e){if(p==NULL)//输入不合法returnfalse;LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL)//内存分配失败returnfalse;s->data=e;//套路s->next=p->next;p->next=s;returntrue;}

在按位序插入中，找到第i-1个节点后直接调用后插函数即可

• return InsertNextNode(p,e);

#前插操作

• 单链表只能往后找wuwuwu
• 只能遍历链表找到指定节点的前驱节点
• 时间复杂度O(n)
• 但其实还有另外一种方法

插入元素

boolInsertPriorNode(LNode*p,ElemType e){if(p==NULL)returnfalse;LNode*s=(LNode*)malloc(sizeof(LNode));if(s==NULL)returnfalse;s->next=p->next;p->next=s;s->data=p->data;p->data=e;returntrue;}

插入节点

boolInsertPriorNode(LNode*p,LNode*s){if(p==NULL||s==NULL)returnfalse;s->next=p->next;p->next=s;Elemtype temp=p->data;p->data=s->data s->data=temp;returntrue;}

• 也就是先后插，再调换
• 这种方式的时间复杂度是O(1)
• 这中偷天换日的操作还是很骚的

#按位序删除

boolListDelete(LinkList&L,inti,ElemType&e){if(i<1)returnfalse;LNode*p;intj=0;p=L;while(p!=NULL&&j<i-1){//循环找到第i-1个节点p=p->next;j++;}if(p==NULL)//i不合法returnfalse;if(p->next==NULL)//i-1之后再无其它节点returnfalse;LNode*q=p->next;//q指向被删除节点e=q->data//e返回删除节点中元素的值p->next=q->next;free(q);returntrue;}

#删除指定节点

• 孩子们，我们依然找不到前驱节点
• 难道还要用头指针遍历链表吗？？？
• 不，牢大有他的小妙招

boolDeleteNode(LNode*p){if(p==NULL)returnfalse;LNode*q=p->next;//令q指向*p的后继节点p->data=p->next->data;//和后继节点交换数据域p->next=q->next;//p指向q的后继free(q);//终于删除了原本的preturntrue;}

• 时间复杂度为O(1)

那如果要删除的指定节点是最后一个节点呢？

• 此时p后面是NULL，那我们只能遍历数组

#按位序查找

//按位查找，返回第 i 个元素（带头结点）LNode*GetElem(LinkList L,inti){if(i<0)returnNULL;LNode*p;//指针p指向当前扫描到的结点intj=0;//当前p指向的是第几个结点p=L;//L指向头结点，头结点是第0个结点（不存数据）while(p!=NULL&&j<i){//循环找到第 i 个结点p=p->next;j++;}returnp;}

#按值查找

//按值查找，找到数据域==e 的结点LNode*LocateElem(LinkList L,ElemType e){LNode*p=L->next;//从第1个结点开始查找数据域为e的结点while(p!=NULL&&p->data!=e)p=p->next;returnp;//找到后返回该结点指针，否则返回NULL}

#求表长

//求表的长度（带头结点）intLength(LinkList L){intlen=0;//统计表长LNode*p=L;while(p->next!=NULL){p=p->next;len++;}returnlen;}

#尾插法建立单链表

LinkList List_TailInsert(LinkList &L){ //正向建立单链表 int x; //设ElemType为整型 L=(LinkList)malloc(sizeof(LNode)); //建立头结点 LNode *s,*r=L; //r为表尾指针 scanf("%d",&x); //输入结点的值 while(x!=9999){ //输入9999表示结束 s=(LNode *)malloc(sizeof(LNode)); s->data=x; r->next=s; r=s; //r指向新的表尾结点 scanf("%d",&x); } r->next=NULL; //尾结点指针置空 return L; }

#头插法建立单链表

• 可以用于链表的逆置

LinkListList_HeadInsert(LinkList&L){//逆向建立单链表LNode*s;intx;L=(LinkList)malloc(sizeof(LNode));//创建头结点L->next=NULL;//初始为空链表，防止脏数据scanf("%d",&x);//输入结点的值while(x!=9999){//输入9999表示结束s=(LNode*)malloc(sizeof(LNode));//创建新结点s->data=x;s->next=L->next;L->next=s;//将新结点插入表头scanf("%d",&x);}returnL;}