单链表的优缺点
| 优点 | 缺点 |
| 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;//新结点给尾结点的next
r = 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;//新结点给尾结点的next
r = 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;//新结点给尾结点的next
r = 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位置插入元素
代码
效果
