文章目录
- 3.1 单链表
- 3.1.1 单链表的定义
- 3.1.2 单链表的插入
- A.按位序插入(带头结点)
- B.按位序插入(不带头结点)
- C.指定结点的后插操作
- D.指定结点的前插操作
- 3.1.3 单链表的删除
- A.按位序删除
- B.删除指定结点
- 3.1.4 单链表的查找
- A.按位查找
- B.按值查找
- 3.1.5 单链表的建立
- A.尾插法
- B.头插法
- *完整代码 单链表带头结点
- *完整代码 单链表不带头结点
3.1 单链表
3.1.1 单链表的定义
-
定义
线性表的链式存储。
-
结点结构:data+next(结点自身的数据+指向后继的指针)
-
特点:元素分散在内存中,非随机存取的存储结构。
-
局限性:无法逆向检索,有时不方便。(双链表可双向检索)
-
//定义单链表节点类型
typedef struct LNode{ElemType data; //数据域Struct LNode *next; //指针域,指向下一个结点
}LNode,*LinkList;
//注:
//LNode —— 强调返回的是一个结点
//LinkList —— 强调的是一个单链表
-
初始化——带头结点
//带头结点初始化 bool InitList(LinkList &L){L=(LNode*)malloc(sizeof(LNode)); //为头结点分配内存if(L==NULL)return false; //内存不足,分配失败L->next=NULL; //头结点后还没有结点return true; }//带头结点判空 bool Empty(LinkList L){if(L->next==NULL)return true;elsereturn false; }
-
初始化——不带头结点
//不带头结点初始化 bool InitList(LinkList &L){L=NULL;return true; }//不带头结点判空 bool Empty(LinkList L){if(L==NULL)return true;elsereturn false; }
-
带头结点和不带头结点的区别
-
头结点:不存储数据,只指向链表中第一个结点的位置
-
不带头结点,写代码麻烦。原因:
1.带头结点后,链表第一个位置上的结点与其他位置的操作可以一致,不用特殊处理。
2.空表和非空表的处理得到统一。
-
3.1.2 单链表的插入
A.按位序插入(带头结点)
-
将值为e的新结点插入到位置i,步骤:
1.找到要插入的位置,即第i-1个结点;
2.在其后插入新结点,插入步骤如图:
bool ListInsert(LinkList &L,int i,ElemType e){if(i<1)return false;LNode *p; //指针p指向当前扫描到的结点int j=0; //记录当前p指向第几个结点p=L; //初始时,L指向头结点,头结点不存数据//循环找到第i-1个结点,即要插入的位置while(p!=NULL && j<i-1){p=p->next;j++;}if(p==NULL)return false;//i值不合法//插入结点LNode *s=(LNode*)malloc(sizeof(LNode)); //为要插入的结点开辟内存s->data=e; //将数值复值到新结点数据域s->next=p->next; //将新结点和后继结点连接p->next=s; //将新结点和前驱连接return true;
}
- 时间复杂度: O ( n ) O(n) O(n)
B.按位序插入(不带头结点)
-
在非第一个插入时,与带头结点相同。但插入第一位时不同,当在第一位插入时要重新赋值头结点。
-
即在带头结点插入的基础上,插入以下一段即可:
bool ListInsert(LinkList &L,int i,ElemType e){if(i<1)return false;//插入第1个结点的操作与其它结点不同if(i==1){LNode *s=(LNode*)malloc(sizeof(LNode));s->data=e;s->next=L;L=s; //头指针指向新结点return true;}LNode *p; //指针p指向当前扫描到的结点int j=0; //记录当前p指向第几个结点p=L; //初始时,L指向头结点,头结点不存数据//循环找到第i-1个结点,即要插入的位置while(p!=NULL && j<i-1){p=p->next;j++;}if(p==NULL)return false;//i值不合法//插入结点LNode *s=(LNode*)malloc(sizeof(LNode)); //为要插入的结点开辟内存s->data=e; //将数值复值到新结点数据域s->next=p->next; //将新结点和后继结点连接p->next=s; //将新结点和前驱连接return true;
}
- 时间复杂度: O ( n ) O(n) O(n)
- 后续不做特殊说明,则默认为带头结点。
C.指定结点的后插操作
-
即在指定结点p后,插入元素e。
相当于在按位序插入的基础上,省去循环查找第i-1个结点的步骤。
bool InsertNextNode(LNode *p,ElemType e){if(p==NULL)return false;LNode *s=(LNode*)malloc(sizeof(LNode));if(s==NULL)return false;s->data=e;s->next=p->next;p->next=s;return true;
}
- 时间复杂度: O ( 1 ) O(1) O(1)
D.指定结点的前插操作
-
方法一:
传入头结点,遍历链表找到指定节点的前驱结点,再按后插的方式插入。
- 时间复杂度: O ( n ) O(n) O(n)
-
方法二: better!
按后插的方式在指定结点后插入新结点,再交换指定节点和新结点的数值。
- 时间复杂度: O ( 1 ) O(1) O(1)
bool InsertPriorNode(LNode *p,ElemType e){if(p==NULL)return false;LNode *s=(LNode*)malloc(sizeof(LNode));if(s==NULL)return false;s->next=p->next;p->next=s; //连接s和p后s->data=p->data; //p数据复制到sp->data=e; //原s的数据给preturn true; }
或者传入的是新结点,而不是数据时,也同理:
bool InsertPriorNode(LNode *p,LNode *s){if(p==NULL||s==NULL)return false;s->next=p->next;p->next=s; //连接s和p后//交换值ElemType t=p->data;p->data=s->data;s->data=t;return true; }
3.1.3 单链表的删除
A.按位序删除
-
删除第i个结点的步骤
1.找到要插入位置的前驱结点,即第i-1个结点。(如图,q是要删结点)
2.将要删除结点从链表中断开,即前驱结点的next指向要删结点的后驱结点。
3.释放已删除的结点空间。
bool ListDelete(LinkList &L,int i,ElemType &e){if(i<1)return false;LNode *p;p=L; //p从头开始扫描int j=0; //当前p指向第几个结点while(p!=NULL && j<i-1){p=p->next;j++;}if(p==NULL)return false; //i值不合法if(p->next==NULL)return false; //i-1后无结点LNode *q=p->next; //存储要删结点e=q->data; //e存储要删结点的值p->next=q->next; //将要删结点断开free(q);return true;
}
- 时间复杂度: O ( n ) O(n) O(n)
B.删除指定结点
-
方法:
与指定结点的前插操作类似。
1.交换指定结点和其后继结点的数据域;
2.删除指定结点的后继结点。
- 时间复杂度: O ( 1 ) O(1) O(1)
bool DeleteNode(LNode*p){if(p=NULL)return false;LNode*q=p->next; //q指向指定结点p的后继p->data=p->next->data; //与后继结点交换数据p->next=q->next; //将q结点断开(q里存的是要删结点的数据)free(q);return true;
}
-
注:
若要删结点是最后一个结点,这样做有空指针的错误,只能用 从表头依次寻找p前驱的方法来删除。
3.1.4 单链表的查找
A.按位查找
-
查找第i个元素
从链表第一个开始往后循环查找。
i是链表中元素下标。
LNode *GetElem(LinkList L,int i){if(i<0)return NULL;LNode *p=L;int j=0;while(p!=NULL&&j<i){p=p->next;j++;}return p;
}
-
可以用于按位查找、删除中的封装:
B.按值查找
-
找到数据域==e的结点
时间复杂度: O ( n ) O(n) O(n)
LNode* LocateElem(LinkList L,ElemType e){LNode *p=L->next;while(p!=NULL&&p->data!=e)p=p->next;return p;
}
3.1.5 单链表的建立
A.尾插法
-
步骤
1.建立头结点(初始化);
2.定义两个结点:一个指向表头结点s,另一个指向表尾结点r;
3.循环输入结点值,并为新结点开辟空间;
4.在表尾结点后插入新结点;
5.更新表尾结点r,保证r永远指向最后一个结点;
6.退出循环后,尾结点置空。
LinkList List_TailInsert(LinkList &L){int x;L=(LNode*)malloc(sizeof(LNode)); //创建头结点LNode *s,*r=L; //s始终指向表头结点,r指向表尾结点scanf("%d",&x);while(x!=9999){s=(LNode*)malloc(sizeof(LNode)); //创建新结点s->data=x;r->next=s; //将新结点插入r=s; //更新表尾结点的指针,保持r指向最后一个结点scanf("%d",&x);}r->next=NULL; //尾结点指针制空return L;
}
B.头插法
-
注:
头插法的输入和链表的数据是逆置关系:
LinkList List_HeadInsert(LinkList &L){LNode *s;int x;L=(LNode*)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;
}
*完整代码 单链表带头结点
#include<stdio.h>
#include<stdlib.h>#define ElemType inttypedef struct LNode {ElemType data;struct LNode* next;
}LNode,*LinkList;//初始化
bool InitList(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));L->next = NULL;return true;
}//求表长
int Length(LinkList L) {int len = 0;LNode* p = L;while (p->next != NULL) {len++;p = p->next;}return len;
}//头插法建立单链表
LinkList List_HeadInsert(LinkList& L) {L = (LNode*)malloc(sizeof(LNode));L->next = NULL;LNode* s;int x;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_TailInsert(LinkList& L) {int x;L = (LNode*)malloc(sizeof(LNode)); //创建头结点LNode* s, * r = L; //s指向头结点,r指向尾结点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;
}//按序查找
LNode* GetItem(LinkList& L, int i) {LNode* p = L;int j = 0;while (j < i && p != NULL) {p = p->next;j++;}return p;
}//按值查找
int LocateElem(LinkList& L, ElemType e) {LNode* p = L;int j = 0;while (p != NULL && p->data != e) {p = p->next;j++;}return j;
}//按位序插入
bool ListInsert(LinkList& L, int i, ElemType e) {if (i < 0)return false;LNode* p = L;int j = 0;while (j < i-1 && p!= NULL) {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 InsertNextNode(LNode* p, ElemType e) {if (p == NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true;
}//指定结点前插操作
bool InsertPriorNode(LNode* p, ElemType e) {if (p == NULL )return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->next = p->next;p->next = s;s->data = p->data;p->data = e;return true;
}//按位序删除
bool ListDelete(LinkList& L, int i, ElemType& e) {LNode* p = L;int j=0;while (j < i-1 && p != NULL) {p = p->next;j++;}if (p == NULL||p->next==NULL)return false;LNode* q = p->next;e = q->data;p->next = q->next;free(q);return true;
}//删除指定结点
bool DeleteNode(LNode* p) {if (p == NULL)return false;LNode* q = p->next;p->data = p->next->data;p->next = q->next;free(q);return true;
}void PrintList(LinkList& L) {LNode* p = L->next;while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n\n");
}void DestroyList(LinkList& L) {LNode* p = L;while (L) {p = L;L = L->next;free(p);}
}int main() {LinkList L;printf("头插法建立单链表,输入以9999结束:\n");L=List_HeadInsert(L);PrintList(L);DestroyList(L);printf("尾插法建立单链表,输入以9999结束:\n");L=List_TailInsert(L);PrintList(L);printf("求表长:%d\n",Length(L));printf("\n");printf("按位序插入:\n");int pos=1, e=998;ListInsert(L, pos, e);PrintList(L);printf("指定结点的后插操作:\n");LNode* p =L->next;e = 222;InsertNextNode(p, e);PrintList(L);printf("指定结点的前插操作:\n");p = L->next;e = 111;InsertPriorNode(p, e);PrintList(L);printf("按值查找:\n");printf("查找222的位序是:%d\n", LocateElem(L, 222));printf("\n");printf("按序查找:\n");LNode* q = GetItem(L, 2);printf("查找第3个元素值是:%d\n", q->data);printf("\n");printf("按位序删除:\n");int ee;ListDelete(L, pos, ee);printf("删除的结点值:%d\n", ee);PrintList(L);printf("按指定结点删除:\n");p = L->next;DeleteNode(p);PrintList(L);
}
*完整代码 单链表不带头结点
#include<stdio.h>
#include<stdlib.h>#define ElemType inttypedef struct LNode {ElemType data;struct LNode* next;
}LNode, * LinkList;//初始化
bool InitList(LinkList& L) {L=NULL;return true;
}//求表长
int Length(LinkList L) {int len = 0;LNode* p = L;while (p!= NULL) {len++;p = p->next;}return len;
}//头插法建立单链表
LinkList List_HeadInsert(LinkList& L) {L= NULL;LNode* s;int x;//第一个结点要特殊判断scanf("%d", &x);L = (LNode*)malloc(sizeof(LNode));L->data = x;L->next = NULL;scanf("%d", &x);while (x != 9999) {s = (LNode*)malloc(sizeof(LNode));s->data = x;s->next = L;L = s;scanf("%d", &x);}return L;
}//尾插法建立单链表
LinkList List_TailInsert(LinkList& L) {int x;L = NULL;//第一个结点要特殊判断scanf("%d", &x);L = (LNode*)malloc(sizeof(LNode));L->data = x;L->next = NULL;LNode* s, * r = L; //s指向头结点,r指向尾结点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;
}//按序查找
LNode* GetItem(LinkList& L, int i) {LNode* p = L;int j = 0;while (j < i && p != NULL) {p = p->next;j++;}return p;
}//按值查找
int LocateElem(LinkList& L, ElemType e) {LNode* p = L;int i = 0;while (p != NULL && p->data != e) {p = p->next;i++;}return i+1;
}//按位序插入
bool ListInsert(LinkList& L, int i, ElemType e) {if (i < 0)return false;//插入第1个结点的操作与其它结点不同if (i == 1) {LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = L;L = s; //头指针指向新结点return true;}LNode* p = L;int j = 0;while (j < i - 1 && p != NULL) {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 InsertNextNode(LNode* p, ElemType e) {if (p == NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return true;
}//指定结点前插操作
bool InsertPriorNode(LNode* p, ElemType e) {if (p == NULL)return false;LNode* s = (LNode*)malloc(sizeof(LNode));s->next = p->next;p->next = s;s->data = p->data;p->data = e;return true;
}//按位序删除
bool ListDelete(LinkList& L, int i, ElemType& e) {if (i < 1)return false;//删除第1个结点的操作与其它结点不同if (i == 1) {e = L->data;LNode* s = L;L = L->next;free(s);return true;}LNode* p = L;int j = 0;while (j < i - 1 && p != NULL) {p = p->next;j++;}if (p == NULL || p->next == NULL)return false;LNode* q = p->next;e = q->data;p->next = q->next;free(q);return true;
}//删除指定结点
bool DeleteNode(LNode* p) {if (p == NULL)return false;LNode* q = p->next;p->data = p->next->data;p->next = q->next;free(q);return true;
}void PrintList(LinkList& L) {LNode* p = L;while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n\n");
}void DestroyList(LinkList& L) {LNode* p = L;while (L) {p = L;L = L->next;free(p);}
}int main() {LinkList L;printf("头插法建立单链表,输入以9999结束:\n");L = List_HeadInsert(L);PrintList(L);DestroyList(L);printf("尾插法建立单链表,输入以9999结束:\n");L = List_TailInsert(L);PrintList(L);printf("求表长:%d\n", Length(L));printf("\n");printf("按位序插入:\n");int pos = 1, e = 998;ListInsert(L, pos, e);PrintList(L);printf("指定结点的后插操作:\n");LNode* p = L;e = 222;InsertNextNode(p, e);PrintList(L);printf("指定结点的前插操作:\n");p = L;e = 111;InsertPriorNode(p, e);PrintList(L);printf("按值查找:\n");printf("查找222的位序是:%d\n", LocateElem(L, 222));printf("\n");printf("按序查找:\n");LNode* q = GetItem(L, 2);printf("查找第3个元素值是:%d\n", q->data);printf("\n");printf("按位序删除:\n");int ee;ListDelete(L, pos, ee);printf("删除的结点值:%d\n", ee);PrintList(L);printf("按指定结点删除:\n");p = L;DeleteNode(p);PrintList(L);
}