摘要:单链表的基本操作,由于太久没有复习数据结构了,导致该忘的都忘了,所以在这里记录重新学习数据结构的笔记,以备以后查看。
单链表
链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
单链表节点定义
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode;
此处定义了一个单链表的结构体,里面包含数据以及下一个数据的单链表指针。
创建节点
LNode *create_LNode(ElemType data){
LNode *ret = (LNode*)malloc(sizeof(LNode));
ret->data = data; //C中将NULL作为空指针之用,C++用nullptr
return ret;
}
此处可以直接传入数据进行创建节点,当创建头节点时可以用NULL进行数据传入;
头插法创建单链表
int create_link_head(LNode *L,ElemType data[],int n){//传入头结点,数组,数组元素的个数
LNode *p;
int i;
L = (LNode*)malloc(sizeof(LNode));
L->data = NULL;
L->next = NULL;
for(i=0;i<n;i++){
p = create_LNode(data[i]);
p->next = L->next;
L->next = p;
}
return L;
}
tips:
因为是头插法,所以插入后的顺序是数组的倒序。
尾插法创建单链表
int create_link_tail(LNode *L,ElemType data[],int n){ //n为插入的个数
LNode *p,*q;
int i;
L = (LNode*)malloc(sizeof(LNode));
L->data = NULL; //申请L为头节点
q = L;
for(i = 0; i< n ;i++){
p = create_LNode(data[i]);
q ->next = p;
q = q->next; //p = q;
}
q ->next = NULL; //将最后一个节点指为NULL
return L;
}
获取链表的长度
int get_length(LNode *L){
int ret =0;
if(L == NULL)
return ret;
while(L->next != NULL){
ret++;
L = L->next;
}
return ret;
}
获取链表中指定位置的节点指针
LNode *get_node(LNode *L,int p){ //p的范围是(1~N)不包含头结点
LNode* ret;
int count = 0;
//ret = L->next;
ret = L;
while( ret != NULL && count< p){
count++;
ret = ret->next;
}
return ret;
}
获取单链表中data值第一次出现的节点指针
LNode *get_first_elem_node(LNode *L,ElemType data){
LNode* ret = L->next;
while(ret != NULL && ret->data != data){
ret = ret->next;
}
return ret;
}
在指定的节点后插入节点
int insert_elem(LNode *L,int p,ElemType data){
LNode *m = NULL;
LNode *n = NULL;
if(p<0 || L->next == NULL)
return 0;
m = get_node(L,p);
n = (LNode*)malloc(sizeof(LNode));
n->next = m->next;
n->data = data;
m->next = n;
return 1;
}
删除节点
删除某个下标的节点,并返回被删除的节点的指针
LNode *delete_node(LNode *L,int p){
LNode *ret = NULL;
LNode *m = NULL;
if(p < 1 || get_length(L)==0 ) //当删除的节点位置小于1或者长度为0时
return 0;
m = get_node(L,p-1);
ret = m->next;
m->next = m->next->next;
return ret;
}
合并表
合并两个元素递增的单链表到一个新的单链表且依然有序
LNode* merge_link(LNode* A,LNode* B,LNode* C){
LNode *p = A->next;
LNode *q = B->next;
LNode *r;
C = (LNode*)malloc(sizeof(LNode));
C->data=NULL;
r = C;
while(p!=NULL && q!=NULL){
if(p->data<=q->data){
r->next=p;
p=p->next;
r=r->next;
}
else{
r->next = q;
q = q->next;
r = r->next;
}
}
//下面的操作是另一个不为空的表剩下都归并到新的表的后面
if(p==NULL)
r->next = q;
if(q==NULL)
r->next = p;
return C;
}
打印单链表
void print_link(LNode *L){
while(L->next){
L = L->next;
printf("%3d",L->data);
}
printf("\n");
}
完整的函数(包含测试部分)
#include <stdio.h>
#include <stdlib.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode;
//初始化节点
LNode *create_LNode(ElemType data){
LNode *ret = (LNode*)malloc(sizeof(LNode));
ret->data = data; //C中将NULL作为空指针之用,C++用nullptr
return ret;
}
//尾插法建立单链表
int create_link_tail(LNode *L,ElemType data[],int n){ //n为插入的个数
LNode *p,*q;
int i;
L = (LNode*)malloc(sizeof(LNode));
L->data = NULL; //申请L为头节点
q = L;
for(i = 0; i< n ;i++){
p = create_LNode(data[i]);
q ->next = p;
q = q->next; //p = q;
}
q ->next = NULL; //将最后一个节点指为NULL
return L;
}
//头插法建立单链表
int create_link_head(LNode *L,ElemType data[],int n){
LNode *p;
int i;
L = (LNode*)malloc(sizeof(LNode));
L->data = NULL;
L->next = NULL;
for(i=0;i<n;i++){
p = create_LNode(data[i]);
p->next = L->next;
L->next = p;
}
return L;
}
//获取单链表的长度
int get_length(LNode *L){
int ret =0;
if(L == NULL)
return ret;
while(L->next != NULL){
ret++;
L = L->next;
}
return ret;
}
//获取链表中指定位置的节点指针
LNode *get_node(LNode *L,int p){
LNode* ret;
int count = 0;
//ret = L->next;
ret = L;
while( ret != NULL && count< p){
count++;
ret = ret->next;
}
return ret;
}
//获取单链表中data值第一次出现的节点指针
LNode *get_first_elem_node(LNode *L,ElemType data){
LNode* ret = L->next;
while(ret != NULL && ret->data != data){
ret = ret->next;
}
return ret;
}
//在指定的节点后插入节点
int insert_elem(LNode *L,int p,ElemType data){
LNode *m = NULL;
LNode *n = NULL;
if(p<0 || L->next == NULL)
return 0;
m = get_node(L,p);
n = (LNode*)malloc(sizeof(LNode));
n->next = m->next;
n->data = data;
m->next = n;
return 1;
}
//删除某个下标的节点,并返回被删除的节点
LNode *delete_node(LNode *L,int p){
LNode *ret = NULL;
LNode *m = NULL;
if(p < 1 || get_length(L)==0 ) //当删除的节点位置小于1或者长度为0时
return 0;
m = get_node(L,p-1);
ret = m->next;
m->next = m->next->next;
return ret;
}
//合并两个元素递增的单链表到一个新的单链表且依然有序
LNode* merge_link(LNode* A,LNode* B,LNode* C){
LNode *p = A->next;
LNode *q = B->next;
LNode *r;
C = (LNode*)malloc(sizeof(LNode));
C->data=NULL;
r = C;
while(p!=NULL && q!=NULL){
if(p->data<=q->data){
r->next=p;
p=p->next;
r=r->next;
}
else{
r->next = q;
q = q->next;
r = r->next;
}
}
if(p==NULL)
r->next = q;
if(q==NULL)
r->next = p;
return C;
}
//打印单链表
void print_link(LNode *L){
while(L->next){
L = L->next;
printf("%3d",L->data);
}
printf("\n");
}
int main()
{
LNode *A,*B,*C;
int i;
LNode* LOCAL;
int data1[5]={9,7,5,3,1};
int data2[7]={2,4,6,8,10,12,14};
A = create_link_head(A,data1,5);
B = create_link_tail(B,data2,7);
print_link(A);
print_link(B);
i = get_length(A);
printf("\nA的长度为:%d\n\n",i);
LOCAL = get_first_elem_node(A,3);
printf("A的第一次出现元素3的指针为:%d\n",LOCAL);
printf("验证LOCAL的data为:%d\n\n",LOCAL->data);
LOCAL = NULL;
LOCAL = get_node(A,2);
printf("A的第2位的指针为:%d\n",LOCAL);
printf("验证LOCAL的data为:%d\n\n",LOCAL->data);
//在指定的节点后插入节点
insert_elem(B,2,5);
print_link(B);
printf("\n");
//删除节点
LOCAL = NULL;
LOCAL= delete_node(B,3);
print_link(B);
printf("验证被删除的LOCAL->data为:%d\n\n",LOCAL->data);
//合并两个单链表
C=merge_link(A,B,C);
print_link(C);
printf("\n");
return 0;
}
tips:
在函数中创建的节点要传出才能使用噢
Comments | 0 条评论