C++链表的实现以及操作

忘是亡心i 2022-05-18 00:57 187阅读 0赞

**链表的声明：**

typedef struct node{
    	int data;
    	node* next;
    }Node,*PNode;

注意:(1).next是指针域，存放下一个节点的存储位置

(2).使用\*PNode可以直接使用PNode p定义指针,不需要每一次都Node\*p

**链表创建：**

PNode creat(){
    	int len;
    	int value;
    PNode PHead=(PNode)malloc(sizeof(Node));
    PNode PTail=PHead;
    PTail->next=NULL;
    printf("请输入节点个数:");
    scanf_s("%d",&len);
    for(int i=0;i<len;i++){
    	PNode PNew=(PNode)malloc(sizeof(Node));
    	printf("第%d个节点的值:",i+1);
    	scanf_s("%d",&value);
    	PNew->data=value;
    	PTail->next=PNew;
    	PNew->next=NULL;
    	PTail=PNew;
    }
    printf("创建链表成功!");
    return PHead;
    }

注意:(1).尾指针的next是NULL要定义，要不然下面的while循环不会终止

(2).使用PNode PNew=(PNode)malloc（sizeof（Node））申请新节点，sizeof（Node）测算Node类型节点需占用的字节数，（PNode）用来进行类型转换，使malloc函数返回一个新的指向Node节点类型的指针，并把该指针赋给PNew

**链表遍历：**

void list(PNode List){
    	PNode P = List->next;  
        printf("遍历链表的值为：");
        if (P == NULL)
            printf("链表为空");
        while (P != NULL)     
        {
    		printf("%d ", P->data);
            P = P->next;
        }
        printf("\n");
    }

**链表查找:**

PNode find(PNode list){
    	PNode p=list->next;
    	int value=0;
    	int i=0;
    	printf("请输入要查询的值");
    	scanf_s("%d",&value);
    	while(p!=NULL&&p->data!=value){
    	i++;
    	p=p->next;
    	}
    	if(p!=NULL){
    	printf("该节点位置:%d",i+1);
    	}else{
    		printf("找不到该节点");
    	}
    	return p;
    }

注意:(1).c语言定义局部int变量，一定要赋予初值，要不然会自动生成随机数字，而全局int变量初值为0

(2).while循环里面写条件，要取p->data，一定要先保证p不能为空

(3).当跳出while循环,要么就是找不到(p==NULL)要么就是找到(p->data==value),此时需要在下面多个一个if语句，判断p不为空，即找到

**链表插入:**

void insert(PNode list,int pos,int value){
    	PNode p=list->next;
    	int i=0;
    	while(p!=NULL){
    		i++;
    		if(i==pos-1){
    		break;
    		}
            p=p->next;
    	}
    	PNode PTemp=(PNode)malloc(sizeof(Node));
    	PTemp->data=value;
    	PTemp->next=p->next;
    	p->next=PTemp;
    }

注意:(1).c语言定义局部int变量，一定要赋予初值，要不然会自动生成随机数字，而全局int变量初值为0

(2).while循环里面写条件，要取p->data，一定要先保证p不能为空

(3).要在第i个元素之前插入一个新元素，需要先找到第i-1个节点的位置

**删除整个链表:**

void deleteAllList(PNode list){
    	PNode PTemp,p;
    	p=list;
    	while(p!=NULL){
    		PTemp=p->next;
    		free(p);
    		p=PTemp;
    	}
    	printf("删除链表成功!");
    }

注意:(1).删除整个链表，要连同头指针要删除掉

(2).要先把p->next存储，要不free(p)后，就找不到p->next,以至于不能循环移动删除节点

**删除链表的指定节点：**

void deleteList(PNode list,int pos){
    	PNode p=list->next;
    	int i=0;
    	while(p!=NULL){
    	i++;
    	if(i==pos-1){
    	break;
    	}
    	p=p->next;
    	}
    	PNode temp=p->next;
    	p->next=temp->next;
    	free(temp);
    }

注意:(1).删除第i节点，同样也要先获取第i-1个节点

(2).同样，也要把p->next先存储，如果使用p->next=p->next->next，等会free（p->next），就会出错，此时的p->next不是一开始的那个

**完整代码:**

#include <stdio.h>
    #include <malloc.h>
    #include <stdlib.h>
    typedef struct node{
    	int data;
    	node* next;
    }Node,*PNode;
    PNode creat();
    void list(PNode PHead);
    PNode find(PNode list);
    void insert(PNode list,int pos,int value);
    void deleteAllList(PNode list);
    void deleteList(PNode list,int pos);
    int main(){
    PNode PHead=creat();
    list(PHead);
    find(PHead);
    insert(PHead,2,5);
    deleteList(PHead,3);
    deleteAllList(PHead);
    system("pause");
    return 0;
    }
    PNode creat(){
    	int len;
    	int value;
    PNode PHead=(PNode)malloc(sizeof(Node));
    PNode PTail=PHead;
    PTail->next=NULL;
    printf("请输入节点个数:");
    scanf_s("%d",&len);
    for(int i=0;i<len;i++){
    	PNode PNew=(PNode)malloc(sizeof(Node));
    	printf("第%d个节点的值:",i+1);
    	scanf_s("%d",&value);
    	PNew->data=value;
    	PTail->next=PNew;
    	PNew->next=NULL;
    	PTail=PNew;
    }
    printf("创建链表成功!");
    return PHead;
    }
    
    void list(PNode List){
    	PNode P = List->next;    
        printf("遍历链表的值为：");
        if (P == NULL)
            printf("链表为空");
        while (P != NULL)        
        {
    		printf("%d ", P->data);
            P = P->next;
        }
        printf("\n");
    }
    
    PNode find(PNode list){
    	PNode p=list->next;
    	int value=0;
    	int i=0;
    	printf("请输入要查询的值");
    	scanf_s("%d",&value);
    	while(p!=NULL&&p->data!=value){
    	i++;
    	p=p->next;
    	}
    	if(p!=NULL){
    	printf("该节点位置:%d",i+1);
    	}else{
    		printf("找不到该节点");
    	}
    	return p;
    }
    void insert(PNode list,int pos,int value){
    	PNode p=list->next;
    	int i=0;
    	while(p!=NULL){
    		i++;
    		if(i==pos-1){
    		break;
    		}
            p=p->next;
    	}
    	PNode PTemp=(PNode)malloc(sizeof(Node));
    	PTemp->data=value;
    	PTemp->next=p->next;
    	p->next=PTemp;
    }
    
    void deleteAllList(PNode list){
    	PNode PTemp,p;
    	p=list;
    	while(p!=NULL){
    		PTemp=p->next;
    		free(p);
    		p=PTemp;
    	}
    	printf("删除链表成功!");
    }
    
    void deleteList(PNode list,int pos){
    	PNode p=list->next;
    	int i=0;
    	while(p!=NULL){
    	i++;
    	if(i==pos-1){
    	break;
    	}
    	p=p->next;
    	}
    	PNode temp=p->next;
    	p->next=temp->next;
    	free(temp);
    }

注意:(1).需要引入3个包

(2).system("pause");可以实现暂停，按任意键进行下一步，可以防止黑色窗口自动关闭，