数据结构二
一、关于线性表中链表的有头单链表实现方式和无头单链表的实现方式
1.无头单链表的实现方式
#include "stdio.h"
#include "stdlib.h"
struct LNode{ //定义单链表结点类型
int data; //每个节点存放一个数据元素
struct LNode* next;//指针指向下一个节点
};
//创建一个节点
struct LNode* CreateNode(int e){
struct LNode* p=(struct LNode*) malloc(sizeof(struct LNode));
if(!p){
printf("No enough memory to allocate!\n");
exit(0);
}
p->data=e;
p->next=NULL;
return p;
}
//判断不带头的单链表是否为空
int Empty(struct LNode* L){
return L==NULL;//判断表是否为空表
}
//不带头结点按照位序插入
struct LNode* ListInsert(struct LNode* L,int i,int e) {
int j=1;
struct LNode* p=L,*s=NULL;//使用p指针接收L链表的所有的值
if(i<1) return 0;//插入节点应该是第一个
if(i==1){//头节点
L= CreateNode(e);
L->next=p;
return L;
}
while (p!=NULL&&j<i-1){
p=p->next;
j++;
}
if(p==NULL)return 0;//i值不合法
s= CreateNode(e);
s->next=p->next;
p->next=s;
return L;
}
//不带头节点的遍历操作
void ListDisplay(struct LNode* L){
struct LNode* p=L;
int j=1;
while (p!=NULL){
printf("The single-linked-list which hasn't head node has %dth data:%d\n",j,p->data);
p=p->next;
j++;
}
free(p);
}
//删除所有的节点
void ListDelete(struct LNode* L){
struct LNode* p=L,* pr=NULL;
while (p!=NULL){
pr=p;
p=p->next;
free(pr);
}
}
//注意当前测试是不带头节点的单链表
int main(){
//1.创建链表头指针
struct LNode* L= NULL;
//2.判断链表是否为空
printf("The single-linked-list which hasn't head node is %s\n",Empty(L)==1?"empty":"not empty");
//3.进行插值操作
L=ListInsert(L,1,3);
if(L){
printf("The single-linked-list which hasn't head node inserts one date!\n");
}else{
printf("The single-linked-list which hasn't head node can't insert one date!\n");
}
L=ListInsert(L,2,1);
L=ListInsert(L,3,10);
//4.遍历查看值
ListDisplay(L);
//5.删除所有节点
ListDelete(L);
return 0;
}
实现结果：
D:\project\clion\ch1\cmake-build-debug\single_linked_list_no_have_head.exe
The single-linked-list which hasn't head node is empty
The single-linked-list which hasn't head node inserts one date!
The single-linked-list which hasn't head node has 1th data:3
The single-linked-list which hasn't head node has 2th data:1
The single-linked-list which hasn't head node has 3th data:10
Process finished with exit code 0
2. 有头单链表的实现方式
#include "stdio.h"
#include "stdlib.h"
struct LNode{ //定义单链表结点类型
int data; //每个节点存放一个数据元素
struct LNode* next;//指针指向下一个节点
};
//创建一个节点
struct LNode* CreateNode(int e){
struct LNode* p=(struct LNode*)malloc(sizeof(struct LNode));
if(!p){
printf("No enough memory to allocate!\n");
exit(0);
}
p->data=e;
p->next=NULL;
return p;
}
//判断带头链表是否为空
int Empty(struct LNode* L){
return L->next==NULL;
}
//指定节点的后插操作
int InsertNextNode(struct LNode* p,int e){
struct LNode* s= CreateNode(e);
if(p==NULL)
return 0;
s->next=p->next;
p->next=s;
return 1;
}
//带头结点按照位序插入
int ListInsert(struct LNode* L,int i,int e) {
int j=0;
struct LNode* p=NULL;//指针p指向当前扫描的节点
if(i<1)return 0;//不能插入数据
p=L;
while (p!=NULL&&j<i-1){//循环找到第i-1个节点
p=p->next;
j++;
}
if(p==NULL)return 0;//i值不合法
//构建指针进行插入操作
struct LNode* s=CreateNode(e);
s->next=p->next;
p->next=s;
return 1;
}
//按位序删除
int ListDelete(struct LNode* L,int i,int* e){
struct LNode* p=L;
int j=0;
if(i<1)return 0;
while (p!=NULL&&i<j-1){
p=p->next;
j++;
}
if(p==NULL) return 0;//i值不合法
if(p->next==NULL) return 0;//第i-1个节点之后再无节点
struct LNode* q=p->next;//q指向被删节点
*e=q->data;//保存待删节点的数据
p->next=q->next;
free(q);
return 1;
}
//按位序查找
struct LNode* GetElem(struct LNode* L,int i){
struct LNode* p=L;//p指针指向当前扫描的节点
int j=0;
if(i<0) return NULL;
while (p!=NULL&&j<i){//循环查找第i个节点
p=p->next;
j++;
}
return p;
}
//按值查找
struct LNode* LocateElem(struct LNode* L,int e){
struct LNode* p=L->next;
while (p!=NULL&&p->data!=e){
p=p->next;
}
return p;
}
//遍历所有的节点
void ListDisplay(struct LNode* L){
struct LNode* p=L;
int j=0;
while (p!=NULL){
printf("The single-linked-list which has head node has %dth data:%d\n",j,p->data);
p=p->next;
j++;
}
free(p);
}
//删除所有的节点
void ListDeleteAll(struct LNode* L){
struct LNode* p=L,* pr=NULL;
while (p!=NULL){
pr=p;
p=p->next;
free(pr);
}
}
int main(){
//1.创建头指针，并初始化头节点
struct LNode* L=CreateNode(0);//初始化带头结点的链表
//3.判断链表是否为空
printf("The single-linked-list which has head node is %s\n",Empty(L)==1?"empty":"not empty");
//4.插入一个节点
ListInsert(L,1,3);
ListInsert(L,2,10);
ListInsert(L,3,5);
//5.遍历所有节点
ListDisplay(L);
//6.删除第2个节点
int e=0;
ListDelete(L,2,&e);
printf("The single-linked-list which has head node deletes 2th node,node data is %d\n",e);
//7.遍历所有节点
ListDisplay(L);
//8.按位序查找第2个节点
struct LNode* IsFindNodeByKey=GetElem(L,2);
if(IsFindNodeByKey){
printf("The single-linked-list which has head node finds 2th node,data is %d\n",IsFindNodeByKey->data);
}else{
printf("The single-linked-list which has head node doesn't 2th node,data doesn't knows.\n");
}
//9.按值查找第2个节点
struct LNode* IsFindNodeByValue= LocateElem(L,5);
if(IsFindNodeByValue){
printf("The single-linked-list which has head node finds one node which the node value is 5,data is %d\n",IsFindNodeByValue->data);
}else{
printf("The single-linked-list which has head node doesn't find one node which the node value is 5.\n");
}
//10.删除所有节点
ListDeleteAll(L);
return 0;
}
实现结果：
D:\project\clion\ch1\cmake-build-debug\single_linked_list_have_head.exe
The single-linked-list which has head node is empty
The single-linked-list which has head node has 0th data:0
The single-linked-list which has head node has 1th data:3
The single-linked-list which has head node has 2th data:10
The single-linked-list which has head node has 3th data:5
The single-linked-list which has head node deletes 2th node,node data is 3
The single-linked-list which has head node has 0th data:0
The single-linked-list which has head node has 1th data:10
The single-linked-list which has head node has 2th data:5
The single-linked-list which has head node finds 2th node,data is 5
The single-linked-list which has head node finds one node which the node value is 5,data is 5
Process finished with exit code 0