目录
1.前言
2.难点
2.1c和c++的引用转换
2.2引入头结点的好处
2.3头插法和尾插法
3.代码段
3.1C语言自定义bool操作
3.2单链表结构体定义
3.3创建新节点
3.4头插法和尾插法
3.5查找
3.6按位序插入
3.7后插和前插
3.8删除
3.9求表长
3.10遍历输出单链表
4.完整代码
1.前言
日期:2023.6.21
书籍:2024年数据结构考研复习指导(王道考研系列)
内容:单链表的实现,结构体定义,初始化,创建新结点,头插和尾插,查询,按位序插入,删除指定节点,输出单链表
2.难点
2.1c和c++的引用转换
符号"&",表示c++中的引用调用,在c语言中可以用指针达到一样的效果
2.2引入头结点的好处
- 由于第一个数据结点的位置被存放在头结点的指针域中,因此在链表的第一个位置上的操作和在表的其他位置上的操作一致,无须进行特殊处理。
- 无论链表是否为空,其头指针都指向头结点的非空指针(空表中头结点的指针域为空)因此空表和非空表的处理也就得到了统一。所以,没事儿写代码就把头指针带着吧
2.3头插法和尾插法
采用头插法建立单链表时,读入数据的顺序与生成的链表中的元素的顺序是相反的。头插法建立单链表的算法虽然简单,但生成的链表中结点的次序和输入数据的顺序不一致。
若希望两者次序一致,则可采用尾插法。该方法将新结点插入到当前链表的表尾,为此必须增加个尾指针r,使其始终指向当前链表的尾结点.
3.代码段
3.1C语言自定义bool操作
//C语言自定义bool操作
#define bool char
#define false 0
#define true 1
3.2单链表结构体定义
typedef int ElemType;
/*单链表结构体定义*/
typedef struct LNode //定义单链表结点类型
{
ElemType data; //每个结点存放一个数据元素
struct LNode *next; //指针指向下一节点
}LNode,*LinkList;
LinkList L; //声明一个指向单链表第一个结点的指针,这种方法代码可读性更强,强调单链表
等价于:文章来源:https://www.toymoban.com/news/detail-494196.html
LNode *L; //声明一个指向单链表第一个结点的指针,但这种方法可读性不强, 无法第一时间看出L是指向整个链表的头指针,还是仅仅是个新的结点。强调的是一个节点。文章来源地址https://www.toymoban.com/news/detail-494196.html
3.3创建新节点
//3.创建新节点函数
LNode* creatNote(int data){//通过传参为节点数据
//[1]为新节点申请空间
LNode* newNode=(LNode*)malloc(sizeof(LNode));
//[2]如果内存满了,则分配失败,返回0
if(newNode==NULL){
printf("内存出现错误,节点分配失败!");
return NULL;
}
//[3]为新节点的数据域和指针域分别赋值
newNode->data=data;
newNode->next=NULL;
return newNode;
}
3.4头插法和尾插法
//4.1.头插法
bool ListHeadInsert(LinkList L,ElemType data){
LNode* newNode=creatNote(data);
newNode->next=L->next;
L->next=newNode;
return true;
}
//4.2.尾插法
bool ListTailInsert(LinkList L,ElemType data){
LNode* newNode = creatNote(data);
LNode* p = L->next;
//[3]遍历链表,找到最后的元素,用工具指针指向它
while (p->next != NULL){
p = p->next;
}//此时的p节点就是最后一个节点
newNode->next = NULL;
p->next = newNode;
}
3.5查找
//5.1按序号查找结点
LNode* GetElem(LinkList L,int i){
int count;
//[1]设置一个变量计数
//[2]设置待返回的结点p,开始指向第一个结点
LNode *p = L->next;
//[3]检查参数
if(i == 0) {p = L; return p;}
if(i < 1) { return NULL;}
//[4]开始循环
while (p != NULL && count < i){
p = p->next;
count++;
}
return p;
}
//5.2按值查找节点
LNode* LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while (p!=NULL&&p->data!=e){
p=p->next;
}
return p;
}
3.6按位序插入
//6.按位序插入
bool ListInsert(LinkList L,int i,ElemType data){
//创建data节点
LNode* newNode=creatNote(data);
LNode* Node=GetElem(L,i-1);//找到i-1节点,然后后插操作
newNode->next=Node->next;
Node->next=newNode;
return true;
}
3.7后插和前插
//7.1.后插节点操作
bool LocateTailInsert(LinkList L,int i,ElemType e){
//[1]生成指向目标节点的指针p
LNode* p = GetElem(L,i-1);
//[2]生成新节点s
LNode* s = creatNote(e);
//[3]插入
s->next = p->next;
p->next = s;
}
//7.2.前插节点操作
bool LocateHeadInsert(LinkList L,int i,ElemType e){
//[1]生成指向目标节点的指针p
LNode* p = GetElem(L,i);
//[2]生成新节点s
LNode* s = creatNote(e);
//[3]插入
ElemType temp = p->data;
s->next = p->next;
p->next = s;
p->data = s->data;
s->data = temp;
}
3.8删除
//8.删除指定节点
bool ElemDelete(LinkList L,int i){
//[1]定位
LNode *p = GetElem(L,i-1);
LNode *q = p->next;
//[2]删除
p->next = q->next;
//[3]释放被删除节点
free(q);
}
bool LocateElemDelete(LinkList L,int i)
{
//[1]定位
LNode *p = GetElem(L,i);
LNode *q = p->next;
//[2]复制数据
p->data = q->data;
p->next = q->next;
//[3]释放结点
free(q);
}
3.9求表长
//9.表长
int ListLength(LinkList L){
int count = 0;
while (L->next != NULL){
L = L->next;
count++;
}
return count;
}
3.10遍历输出单链表
//遍历输出单链表
void Listprint(LinkList L){
LNode* p = L->next;
while (p != NULL){
printf("%d\n",p->data);
p = p->next;
}
printf("\n");
}
4.完整代码
#include <stdio.h>
#include <stdlib.h>
//C语言自定义bool操作
#define bool char
#define false 0
#define true 1
//1.单链表结构体定义
typedef int ElemType;
typedef struct LNode{ //定义单链表结点类型
ElemType data; //每个结点存放一个数据元素
struct LNode *next;//指针指向下一节点
}LNode,*LinkList;
//2.链表的初始化
LinkList ListInit(){
//申请一块LinkList类型的存储空间给L
LinkList L=(LNode*)malloc(sizeof(LinkList));//
//设置L的指针域为空
L->next=NULL;
return L;
}
//3.创建新节点函数
LNode* creatNote(int data){//通过传参为节点数据
//[1]为新节点申请空间
LNode* newNode=(LNode*)malloc(sizeof(LNode));
//[2]如果内存满了,则分配失败,返回0
if(newNode==NULL){
printf("内存出现错误,节点分配失败!");
return NULL;
}
//[3]为新节点的数据域和指针域分别赋值
newNode->data=data;
newNode->next=NULL;
return newNode;
}
//4.1.头插法
bool ListHeadInsert(LinkList L,ElemType data){
LNode* newNode=creatNote(data);
newNode->next=L->next;
L->next=newNode;
return true;
}
//4.2.尾插法
bool ListTailInsert(LinkList L,ElemType data){
LNode* newNode = creatNote(data);
LNode* p = L->next;
//[3]遍历链表,找到最后的元素,用工具指针指向它
while (p->next != NULL){
p = p->next;
}//此时的p节点就是最后一个节点
newNode->next = NULL;
p->next = newNode;
}
//5.1按序号查找结点
LNode* GetElem(LinkList L,int i){
int count;
//[1]设置一个变量计数
//[2]设置待返回的结点p,开始指向第一个结点
LNode *p = L->next;
//[3]检查参数
if(i == 0) {p = L; return p;}
if(i < 1) { return NULL;}
//[4]开始循环
while (p != NULL && count < i){
p = p->next;
count++;
}
return p;
}
//5.2按值查找节点
LNode* LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while (p!=NULL&&p->data!=e){
p=p->next;
}
return p;
}
//6.按位序插入
bool ListInsert(LinkList L,int i,ElemType data){
//创建data节点
LNode* newNode=creatNote(data);
LNode* Node=GetElem(L,i-1);//找到i-1节点,然后后插操作
newNode->next=Node->next;
Node->next=newNode;
return true;
}
//7.1.后插节点操作
bool LocateTailInsert(LinkList L,int i,ElemType e){
//[1]生成指向目标节点的指针p
LNode* p = GetElem(L,i-1);
//[2]生成新节点s
LNode* s = creatNote(e);
//[3]插入
s->next = p->next;
p->next = s;
}
//7.2.前插节点操作
bool LocateHeadInsert(LinkList L,int i,ElemType e){
//[1]生成指向目标节点的指针p
LNode* p = GetElem(L,i);
//[2]生成新节点s
LNode* s = creatNote(e);
//[3]插入
ElemType temp = p->data;
s->next = p->next;
p->next = s;
p->data = s->data;
s->data = temp;
}
//8.删除指定节点
bool ElemDelete(LinkList L,int i){
//[1]定位
LNode *p = GetElem(L,i-1);
LNode *q = p->next;
//[2]删除
p->next = q->next;
//[3]释放被删除节点
free(q);
}
bool LocateElemDelete(LinkList L,int i)
{
//[1]定位
LNode *p = GetElem(L,i);
LNode *q = p->next;
//[2]复制数据
p->data = q->data;
p->next = q->next;
//[3]释放结点
free(q);
}
//9.表长
int ListLength(LinkList L){
int count = 0;
while (L->next != NULL){
L = L->next;
count++;
}
return count;
}
//遍历输出单链表
void Listprint(LinkList L){
LNode* p = L->next;
while (p != NULL){
printf("%d\n",p->data);
p = p->next;
}
printf("\n");
}
int main(){
//[1]定义一个链表
LinkList L = NULL;
// printf("%d",L->next);//可以尝试,此时L->next无法输出
//[2]将链表初始化
L = ListInit();
ListHeadInsert(L,1);
ListHeadInsert(L,2);
ListHeadInsert(L,3);
ListHeadInsert(L,4);
ListHeadInsert(L,5);
ListTailInsert(L,6);
ListTailInsert(L,7);
ListTailInsert(L,8);
ListTailInsert(L,9);
ListTailInsert(L,10);
ListInsert(L,3,666);
ListInsert(L,1,88888);
LocateTailInsert(L,8,6969);
LocateHeadInsert(L,2,3333);
ElemDelete(L,3);
LocateElemDelete(L,5);
Listprint(L);
printf("链表长度为:%d\n",ListLength(L));
return 0;
}
到了这里,关于王道考研数据结构--2.单链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!