目录
单链表的优缺点
单链表结点的定义
头插法新建链表
尾插法新建链表
按位查找
按值查找
i 位置插入元素
单链表的删除
单链表的优缺点
优点 | 缺点 |
1. 插入和删除操作不需要移动元素,只需要修改指针 2. 不需要大量的连续存储空间 | 1. 单链表附加指针域,也存在浪费存储空间的缺点。 2. 查找操作需要从表头开始遍历,依次查找,不能随机存取。 |
单链表结点的定义
typedef int ElemType;
typedef struct LNode{ElemType data;//数据域struct LNode *next;//指针域
}LNode, *LinkList;
注意
LNode*是结构体指针,和LinkList完全等价。
头插法新建链表
代码
#include <stdio.h>
#include <stdlib.h>//malloc需要typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;void list_head_insert(LNode* &L) {L = (LinkList) malloc(sizeof(LNode));//申请头节点空间,头指针指向头结点L -> next =NULL;ElemType x;scanf("%d", &x);LNode *s;//用来指向申请的新结点while(x != 9999){s = (LinkList) malloc(sizeof(LNode));s -> data = x;s -> next = L -> next;//s的next指向原本链表的第一个结点L -> next = s;//头结点的next,指向新结点scanf("%d",&x);}
}void print_list(LinkList L){L = L -> next;while(L != NULL){printf("%3d", L -> data);L = L -> next;}printf("\n");
}int main(){LinkList L;//L是链表头指针,LinkList是结构体指针类型list_head_insert(L);//输入数据可以为3,4,5,6,7,9999,头插法新建链表print_list(L);//打印链表return 0;
}
效果
注意
#include <stdlib.h>//malloc需要
尾插法新建链表
代码
#include <stdio.h>
#include <stdlib.h>//malloc需要typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;void list_tail_insert(LNode* &L) {L = (LinkList) malloc(sizeof(LNode));//申请头节点空间,头指针指向头结点L -> next =NULL;ElemType x;scanf("%d", &x);LNode *s, *r = L;//s是用来指向申请的新结点,r始终指向链表尾部while(x != 9999){s = (LinkList) malloc(sizeof (LNode));//为新结点申请空间s -> data = x;r -> next = s;//新结点给尾结点的nextr = s;//r指向新的尾部scanf("%d",&x);}r -> next = NULL;//让尾结点的next为NULL
}void print_list(LinkList L){L = L -> next;while(L != NULL){printf("%3d", L -> data);L = L -> next;}printf("\n");
}int main(){LinkList L;//L是链表头指针,LinkList是结构体指针类型list_tail_insert(L);//输入数据可以为3,4,5,6,7,9999,头插法新建链表print_list(L);//打印链表return 0;
}
效果
按位查找
注意
判断查找位置是否合法
代码
#include <stdio.h>
#include <stdlib.h>//malloc需要typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;void list_tail_insert(LNode* &L) {L = (LinkList) malloc(sizeof(LNode));//申请头节点空间,头指针指向头结点L -> next =NULL;ElemType x;scanf("%d", &x);LNode *s, *r = L;//s是用来指向申请的新结点,r始终指向链表尾部while(x != 9999){s = (LinkList) malloc(sizeof (LNode));//为新结点申请空间s -> data = x;r -> next = s;//新结点给尾结点的nextr = s;//r指向新的尾部scanf("%d",&x);}r -> next = NULL;//让尾结点的next为NULL
}void print_list(LinkList L){L = L -> next;while(L != NULL){printf("%3d", L -> data);L = L -> next;}printf("\n");
}LinkList GetElem(LinkList L,int SearchPos){int i = 0;if(SearchPos < 0){return NULL;}while(L != NULL && i < SearchPos){L = L -> next;i++;}return L;}int main(){LinkList L,search;//L是链表头指针,search是指针,LinkList是结构体指针类型list_tail_insert(L);//输入数据可以为3,4,5,6,7,9999,头插法新建链表print_list(L);//打印链表//按位查找search = GetElem(L,2);if(search != NULL){printf("Succeeded in searching by serial number\n");printf("%d\n",search -> data);}return 0;
}
效果
按值查找
代码
#include <stdio.h>
#include <stdlib.h>//malloc需要typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;void list_tail_insert(LNode* &L) {L = (LinkList) malloc(sizeof(LNode));//申请头节点空间,头指针指向头结点L -> next =NULL;ElemType x;scanf("%d", &x);LNode *s, *r = L;//s是用来指向申请的新结点,r始终指向链表尾部while(x != 9999){s = (LinkList) malloc(sizeof (LNode));//为新结点申请空间s -> data = x;r -> next = s;//新结点给尾结点的nextr = s;//r指向新的尾部scanf("%d",&x);}r -> next = NULL;//让尾结点的next为NULL
}void print_list(LinkList L){L = L -> next;while(L != NULL){printf("%3d", L -> data);L = L -> next;}printf("\n");
}LinkList LocateElem(LinkList L,ElemType SearchVal){while(L){if(L -> data == SearchVal){//吐过找到对应的值,就返回那个结点的地址return L;}L = L -> next;}return NULL;
}
int main(){LinkList L,search;//L是链表头指针,search是指针,LinkList是结构体指针类型list_tail_insert(L);//输入数据可以为3,4,5,6,7,9999,头插法新建链表print_list(L);//打印链表//按值查找search = LocateElem(L,6);if(search != NULL){printf("Search by value succeeded\n");printf("%d\n",search -> data);}return 0;
}
效果
i 位置插入元素
代码
#include <stdio.h>
#include <stdlib.h>//malloc需要typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;void list_tail_insert(LNode* &L) {L = (LinkList) malloc(sizeof(LNode));//申请头节点空间,头指针指向头结点L -> next =NULL;ElemType x;scanf("%d", &x);LNode *s, *r = L;//s是用来指向申请的新结点,r始终指向链表尾部while(x != 9999){s = (LinkList) malloc(sizeof (LNode));//为新结点申请空间s -> data = x;r -> next = s;//新结点给尾结点的nextr = s;//r指向新的尾部scanf("%d",&x);}r -> next = NULL;//让尾结点的next为NULL
}void print_list(LinkList L){L = L -> next;while(L != NULL){printf("%3d", L -> data);L = L -> next;}printf("\n");
}LinkList GetElem(LinkList L,int SearchPos){int i = 0;if(SearchPos < 0){return NULL;}while(L != NULL && i < SearchPos){L = L -> next;i++;}return L;}bool ListFrontInsert(LinkList L,int i,ElemType InsertVal){LinkList p = GetElem(L,i -1 );if(NULL == p){return false;}LinkList q;q = (LinkList) malloc(sizeof (LNode));q -> data = InsertVal;q -> next = p -> next;p -> next = q;return true;
}int main(){LinkList L,search;//L是链表头指针,search是指针,LinkList是结构体指针类型list_tail_insert(L);//输入数据可以为3,4,5,6,7,9999,头插法新建链表bool ret;ret = ListFrontInsert(L,2,99);print_list(L);//打印链表return 0;
}
注意
从函数调用位置,跳转到函数定义位置,ctrl + 鼠标左键点击
效果
单链表的删除
代码
#include <stdio.h>
#include <stdlib.h>//malloc需要typedef int ElemType;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode, *LinkList;void list_tail_insert(LNode* &L) {L = (LinkList) malloc(sizeof(LNode));//申请头节点空间,头指针指向头结点L -> next =NULL;ElemType x;scanf("%d", &x);LNode *s, *r = L;//s是用来指向申请的新结点,r始终指向链表尾部while(x != 9999){s = (LinkList) malloc(sizeof (LNode));//为新结点申请空间s -> data = x;r -> next = s;//新结点给尾结点的nextr = s;//r指向新的尾部scanf("%d",&x);}r -> next = NULL;//让尾结点的next为NULL
}void print_list(LinkList L){L = L -> next;while(L != NULL){printf("%3d", L -> data);L = L -> next;}printf("\n");
}LinkList GetElem(LinkList L,int SearchPos){int i = 0;if(SearchPos < 0){return NULL;}while(L != NULL && i < SearchPos){L = L -> next;i++;}return L;}bool ListDelete(LinkList L,int i){LinkList p = GetElem(L,i-1);//拿到要删除结点的前一个if(NULL == p){return false;}LinkList q = p -> next;//拿到要删除的结点指针p -> next = q -> next;//断链free(q);//释放被删除结点的空间return true;
}int main(){LinkList L,search;//L是链表头指针,search是指针,LinkList是结构体指针类型list_tail_insert(L);//输入数据可以为3,4,5,6,7,9999,头插法新建链表bool ret;ret = ListDelete(L,4);print_list(L);//打印链表return 0;
}
效果