C语言-链表

特点

空间不连续，不可以支持随机访问，插入删除的效率高

链表定义

typedef struct NODE{
    int num;
    struct NODE* next;  //指向下一地址的指针
}Node;

链表的创建

//有头指针的头插法
#include
#include

typedef struct NODE {
	int num;
	struct NODE* next;
}Node;

void printList(Node* p) {				//链表打印
	while (p) {
		printf("%d ", p->num);
		p = p->next;
	}
}

void freeList(Node* p) {				//链表的释放
	Node* t = NULL;
	while (p) {
		t = p->next;
		free(p);
		p = t;
	}
}

Node* findNode(Node* p, int num) {		//链表查找
	while (p) {
		if (p->num == num) {
			return p;
		}
		p = p->next;
	}
	return NULL;
}

void deleteNode(Node* p, int num) {		//链表删除
	if (p == NULL) {
		return;
	}
	Node* q = p;
	p = p->next;//p比q多走一步
	while (p) {
		if (p->num == num) {//删除节点
			q->next = p->next;
			free(p);
			break;
		}
		q = p;
		p = p->next;
	}
}

void insertNode(Node* p, int findNum, int newNum) {		//链表添加
	Node* q = p;
	p = p->next;//p比q多走一步
	while (p) {
		if (p->num == findNum) {//插入节点
			Node* t = malloc(sizeof(Node));
			t->num = newNum;
			t->next = p;
			q->next = t;
			break;
		}
		q = p;
		p = p->next;
	}
	//找不到findNum不处理
}


int main() {
	Node* head = malloc(sizeof(Node));
	head->next = NULL;
	int number = 0;
	while (1) {
		scanf("%d", &number);
		if (number <= 0) {
			break;
		}
		Node* p = malloc(sizeof(Node));
		p->num = number;
		p->next = head->next;
		head->next = p;
	}

	//修改节点
	Node* t = findNode(head->next, 10);
	if (t != NULL) {
		t->num = 20;
	}
	//删除节点
	deleteNode(head, 10);
	//增加节点
	insertNode(head, 10, 50);
	//查找节点
	Node* t = findNode(head->next, 10);
	//修改节点
	if (t != NULL) {
		t->num = 20;
	}
	//打印链表
	printList(head->next);
	//释放链表
	freeList(head);

	return 0;
}

链表的打印

void printList(Node* p){
    while(p){
        printf("%d ",p->num);
        p = p->next;
    }
}

链表的释放

void freeList(Node* p){
    Node* t = NULL;
    while(p){
        t = p->next;
        free(p);
        p = t;
    }
}

查找节点

Node* findNode(Node* p,int num){
    while(p){
        if(p->num == num){
            return p;
        }
        p = p->next;
    }
    return NULL;
}

修改节点

Node* t = findNode(head->next,10);
if(t!=NULL){
    t->num = 20;
}

删除节点

void deleteNode(Node* p,int num){
    if(p == NULL){
        return;
    }
    Node* q = p;
    p = p->next;//p比q多走一步
    while(p){
        if(p->num ==num){//删除节点
            q->next = p->next;
            free(p);
            break;
        }
        q = p;
        p = p->next;
    }
}

插入节点

void insertNode(Node* p,int findNum,int newNum){
    Node* q = p;
    p = p->next;//p比q多走一步
    while(p){
        if(p->num == findNum){//插入节点
        Node* t = malloc(sizeof(Node));
        t->num = newNum;
        t->next = p;
        q->next = t;
        break;
        }
        q = p;
        p = p->next;
    }
    //找不到findNum不处理
}