1)顺序表与链式表的比较
顺序表:存储密度高、可以随机存取,但是扩展容量不方便,删除、插入元素开销大。
链式表:需要存储指针信息,不能随机存取,只能依次遍历,删除、插入元素开销小,扩展容量很容易。
2)单链表定义
不带头结点
#include <stdio.h> typedef struct LNode{ int data; struct LNode * next; }LNode,*LinkList; //无头节点 bool InitList(LinkList &L) { L=NULL; //把头指针置空 return true; } //判断链表是否为空,如果为空,头指针指向NULL bool IsListEmpty(LinkList L) { return (L==NULL); } int main(void) { LinkList L; //声明一个指向单链表的指针 InitList(L); printf("%d",IsListEmpty(L)); return 0; }
带头结点
#include <stdio.h> #include <stdlib.h> typedef struct LNode{ int data; struct LNode * next; }LNode,*LinkList; //带头节点 bool InitList(LinkList &L) { L=(LNode *)malloc(sizeof(LNode)); if(L==NULL)return false; //上面头指针指向了头结点,头指针还指向NULL,说明内存空间不足,返回false; L->next=NULL; //头结点置空 return true; } //判断链表是否为空,如果为空,头指针指向NULL bool IsListEmpty(LinkList L) { return (L->next==NULL); } int main(void) { LinkList L; //声明一个指向单链表的指针 InitList(L); printf("%d",IsListEmpty(L)); return 0; }
3)单链表的插入
按序号插入——带头结点(推荐)
#include <stdio.h> #include <stdlib.h> typedef struct LNode{ int data; LNode * next; }LNode,*LinkList; void InitList(LinkList &L) { L=(LNode *)malloc(sizeof(LNode)); //分配一个空间作为头结点,头指针指向头结点 L->next=NULL; //头节点的next域置空 } //按位序插入 bool ListInsert(LinkList &L,int i,int e) { if(i<1) return false; LNode * p=L; //指针p指向头结点 int j=0; //下标j用来记录指针p指向第几个结点 while(p!=NULL&&j<i-1) //循环找到第i-1个结点 { p=p->next; j++; } if(p==NULL) return false; //i值超过了链表的范围,不合法 LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点 s->data=e; //将要插入的数据e存到结点中 s->next=p->next; p->next=s; return true; } int main(void) { LinkList L; //申请一个LinkList类型的头指针 InitList(L); if(ListInsert(L,1,1)) { printf("%d\n",L->next->data); } else printf("Failed!\n"); return 0; }
最好时间复杂度:O(1),最坏时间复杂度:O(n),平均时间复杂度:O(n)
按序号插入——不带头结点
#include <stdio.h> #include <stdlib.h> typedef struct LNode { int data; LNode * next; }LNode,*LinkList; //不带头结点 bool InitList(LinkList &L) { L=NULL; //将头指针置空 return true; } //按位插入 bool ListInsert(LinkList &L,int i,int e) { if(i<1) return false; //非法输入 if(i=1) { LNode * s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=L; L=s; return true; } int j=1; //用来记录p指向第几个结点 //找到第i-1个结点 LNode * p=L; while(p!=NULL&&j<i-1) { p=p->next; j++; } if(p==NULL) return false; LNode * s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return true; } int main(void) { LinkList L;//声明一个头指针 InitList(L); if(ListInsert(L,0,1)) { printf("%d\n",L->data); } else printf("Failed!\n"); return 0; }
指定结点后插操作
bool InsertNextNode(LNode * p,int e) { if(p==NULL) return false; //i值超过了链表的范围,不合法 LNode * s=(LNode *)malloc(sizeof(LNode)); //指针s指向一个新的结点 s->data=e; //将要插入的数据e存到结点中 s->next=p->next; p->next=s; return true; }
时间复杂度:O(1)
指定结点前插操作
#include <stdio.h> #include <stdlib.h> typedef struct LNode { int data; LNode * next; }LNode,*LinkList; void InitList(LinkList &L) { LNode * p; L=(LNode *)malloc(sizeof(LNode)); p=L; p->next=NULL; } //按位插入 bool ListInsert(LinkList &L,int i,int e) { if(i<1) return false; //非法输入 int j=0; //用来记录p指向第几个结点 //找到第i-1个结点 LNode * p=L; while(p!=NULL&&j<i-1) { p=p->next; j++; } if(p==NULL) return false; LNode * s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return true; } //核心代码块,插入制定结点之前 bool InsertPrioList(LNode * p,int e) { if(p==NULL)return false; LNode * s=(LNode *)malloc(sizeof(LNode)); if(s==NULL)return false; //把s插入p结点之后 s->next=p->next; p->next=s; //把p的数据拷贝到s,再把要插入的数据存入p s->data=p->data; p->data=e; return true; } int main(void) { LinkList L; InitList(L); ListInsert(L,1,1); LNode * r=L->next; InsertPrioList(r,5); printf("%d",L->next->data); return 0; }
时间复杂度:O(1)
4)单链表的删除
#include <stdio.h> #include <stdlib.h> typedef struct LNode { int data; LNode * next; }LNode,*LinkList; bool InitList(LinkList &L) { L=(LNode *)malloc(sizeof(LNode)); if(L==NULL)return false; L->next=NULL; return true; } //按位插入 bool ListInsert(LinkList &L,int i,int e) { if(i<1) return false; //非法输入 int j=0; //用来记录p指向第几个结点 //找到第i-1个结点 LNode * p=L; while(p!=NULL&&j<i-1) { p=p->next; j++; } if(p==NULL) return false; LNode * s=(LNode *)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; return true; } //核心代码,按位序删除 bool ListDelete(LinkList &L,int i,int &e) { if(L->next==NULL)return false; if(i<1)return false; //找到第i-1个位置 LNode * p=L; int j=0; while(j<i-1&&p!=NULL) { p=p->next; j++; } if(p==NULL) return false; //在第i-1个位置后执行删除操作 LNode * q=p->next; e=q->data; p->next=q->next; free(q); return true; } void PrintList(LinkList L) { LNode * p=L; while(p->next!=NULL) { p=p->next; printf("%d ",p->data); } printf("\n"); } int main(void) { LinkList L; InitList(L); ListInsert(L,1,1); ListInsert(L,2,2); ListInsert(L,3,3); LNode * p=L; PrintList(L); int e; ListDelete(L,2,e); p=L; PrintList(L); return 0; }
最好时间复杂度:O(1)、最坏、平均时间复杂度O(n).
指定结点的删除
bool DeleteNode(LNode * p) { if(p==NULL) return false; LNode * q=p->next; p->data=q->data; p->next=q->next; free(q); return true; }
时间复杂度:O(1)
[注]若要删除最后一个结点,p->next为NULL,故q不存在data域,这种解法不适用了。
5)单链表的查找
按位查找
LNode * GetElem(LinkList L,int i) { if(i<0) return NULL; LNode * p=L; int j=0; while(j<i&&p!=NULL) { p=p->next; j++; } return p; }
平均时间复杂度:O(n)
按值查找
LNode * GetElem(LinkList L,int i) { if(i<0) return NULL; LNode * p=L; int j=0; while(j<i&&p!=NULL) { p=p->next; j++; } return p; }
表长
int ListLength(LinkList L) { int i=0; LNode * p=L->next; while(p!=NULL) { p=p->next; i++; } return i; }
6)单链表的建立
尾插法
可以通过每一次插入都调用
while 循环 { //取数据元素 ListInsert(LinkList,length+1,e); //插至链表尾部 length++; }
但每次插入一个元素都要从头开始遍历,时间复杂度为O(n^2);可以通过一个指针来指向表尾,每次移动尾指针改良;
LinkList Link_TailInsert(LinkList &L) //正向建立单链表 { //初始化 L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点 LNode * p=L; //指针p指向头结点 //用户输入数据、并依次生成结点,直至用户输入9999退出 int x; scanf("%d",&x); while(x!=9999) { LNode * q=(LNode *)malloc(sizeof(LNode)); p->next=q; p=q; p->data=x; scanf("%d",&x); } p->next=NULL; //尾指针置空,不做这一步,最后尾指针会指向自己 return L; }
头插法
LinkList Link_HeadInsert(LinkList &L) { int a; LNode * p; //初始化 L=(LNode *)malloc(sizeof(LNode)); //头指针指向头结点 L->next=NULL; //必须指向NULL //输入数据、并把输入的数据插入到头结点之后 scanf("%d",&a); while(a!=9999) { p=(LNode *)malloc(sizeof(LNode)); p->data=a; p->next=L->next; L->next=p; scanf("%d",&a); } return L; }
头插法的应用:实现链表的逆置
//法一:通过新建一个链表实现 LinkList ReverseList(LinkList &L) { LNode * p; //指针 LinkList s=(LNode *)malloc(sizeof(LNode)); //生成一个新的链表 s->next=NULL; while(L->next!=NULL) { //从头开始依次取下链表L的结点 p=L->next; //指向要被取下的结点 L->next=p->next; //把取下的数据使用头插法插入到新的链表s p->next=s->next; s->next=p; } return s; } //法二:就地转置,将头结点摘下,然后从第一结点开始,依次前插入到头结点的后面(头插法),直到最后一个结点为止。 LinkList ReverseList2(LinkList &L) { LNode *p,*q; //p指针指向位序为一的结点 p=L->next; L->next=NULL; //取下头结点 //使用头插法把结点从头依次插入头结点后面 while(p!=NULL) { q=p->next; p->next=L->next; L->next=p; p=q; } return L; }
其实以上两个方法基本上原理是相同的,用法二更好,因为是原地转置,用法一也可以再最后把头指针L->s;