赞
踩
先是定义一个单向链表的节点结构体:
typedef struct Node{
int data;
struct Node *pNext;
}NODE, *PNODE;
那么整个结构体可以抽象成下图:
其中,一个空链表就只有一个头节点(在本篇文章中头节点用于数据的存储,只用于作为索引,当然,你也可以将它和普通节点一样存放数据等):
而n个节点的链表如下(这里n=3):
与“在中间插入一个节点”同样原理,所以这里省略过程:
略。
略。
注:程序仅作参考,不考虑严谨性。
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct Node{ int data; struct Node *pNext; }NODE, *PNODE; PNODE create_List(void); int destory_list(PNODE pHead); int list_is_empty(PNODE pHead); int list_length(PNODE pHead); int insert_node_to_list_head(PNODE pHead, PNODE node); int insert_node_to_list_by_position(PNODE pHead, int position, PNODE node); int insert_node_to_list_tail(PNODE pHead, PNODE node); void remove_list_first_node(PNODE pHead); void remove_list_node_by_position(PNODE pHead, int position); void remove_list_tail_node(PNODE pHead); int midify_list_node(PNODE pHead, int position, int val); void show_all_list_node(PNODE pHead); int main() { PNODE pHead = NULL; /* 先定义一个头结点 */ NODE tmpNode; int ret, pos, val; pHead = create_List(); if(pHead == NULL){ printf("创建链表失败!\n"); return -1; } char ch; while(1){ printf("------------------------------------\n" "a) 添加节点到链表头部\n" "b) 添加节点到链表尾部\n" "c) 添加节点到链表指定位置\n" "d) 删除链表第一个节点\n" "e) 删除链表最后一个节点\n" "f) 删除链表指定位置的节点\n" "g) 修改节点内容\n" "h) 查看链表长度\n" "i) 查看链表内容\n" "z) 退出\n" "请输入你的选择: " ); scanf("%c", &ch); getchar(); switch(ch){ case 'a': printf("请输入新增节点的值:"); scanf("%d", &tmpNode.data); getchar(); ret = insert_node_to_list_head(pHead, &tmpNode); if(ret){ printf("插入节点失败!\n"); break; } printf("操作成功!\n"); break; case 'b': printf("请输入新增节点的值:"); scanf("%d", &tmpNode.data); getchar(); ret = insert_node_to_list_tail(pHead, &tmpNode); if(ret){ printf("插入节点失败!\n"); break; } printf("操作成功!\n"); break; case 'c': printf("请输入节点插入的位置:"); scanf("%d", &pos); printf("请输入新增节点的值:"); scanf("%d", &tmpNode.data); getchar(); ret = insert_node_to_list_by_position(pHead, pos, &tmpNode); if(ret){ printf("插入节点失败!\n"); break; } printf("操作成功!\n"); break; case 'd': remove_list_first_node(pHead); printf("操作成功!\n"); break; case 'e': remove_list_tail_node(pHead); printf("操作成功!\n"); break; case 'f': printf("请输入需要删除的节点位置:"); scanf("%d", &pos); getchar(); remove_list_node_by_position(pHead, pos); break; case 'g': printf("请输入需要修改的节点位置:"); scanf("%d", &pos); getchar(); printf("请输入修改后的值:"); scanf("%d", &val); getchar(); midify_list_node(pHead, pos, val); break; case 'h': printf("链表长度:%d\n", list_length(pHead)); break; case 'i': show_all_list_node(pHead); break; case 'z': destory_list(pHead); return 0; default: printf("输入有误!请重新输入...\n"); break; } } return 0; } PNODE create_List(void) { PNODE tmp = NULL; tmp = (PNODE)malloc(sizeof(NODE)); if(tmp == NULL){ printf("分配节点内存失败!\n"); return NULL; } memset(tmp, 0, sizeof(*tmp)); return tmp; } int destory_list(PNODE pHead) { /* 将"第一个"释放掉,释放掉之后又生成新的"第1个" */ while(pHead->pNext){ remove_list_first_node(pHead); } /* 头节点也要释放掉 */ free(pHead); } int list_is_empty(PNODE pHead) { if(pHead->pNext) return 0; else return 1; } int list_length(PNODE pHead) { PNODE tmp = pHead; int length = 0; while(tmp->pNext){ length++; tmp = tmp->pNext; } return length; } int insert_node_to_list_tail(PNODE pHead, PNODE pNode) { PNODE tmp = pHead; /* 找到尾节点 */ while(tmp->pNext){ tmp = tmp->pNext; } /* 在堆里分配一块内存,用于存放新节点 */ PNODE pNew = (PNODE)malloc(sizeof(NODE)); memcpy(pNew, pNode, sizeof(NODE)); /* 原来的尾节点指向新节点 */ tmp->pNext = pNew; /* 确保新的尾节点的指针为NULL */ pNew->pNext = NULL; return 0; } int insert_node_to_list_by_position(PNODE pHead, int position, PNODE pNode) { PNODE tmp = pHead; int i = 0; /* 找出需要插入的前一个位置 */ while(tmp->pNext && i < position-1){ tmp = tmp->pNext; i++; } /* 如果链表没有那么长则返回 */ if(tmp->pNext == NULL || i < position-1){ printf("链表长度不够!\n"); return -1; } PNODE pNew = (PNODE)malloc(sizeof(NODE)); memcpy(pNew, pNode, sizeof(NODE)); pNew->pNext = tmp->pNext; tmp->pNext = pNew; return 0; } int insert_node_to_list_head(PNODE pHead, PNODE pNode) { #if 1 PNODE pNew = (PNODE)malloc(sizeof(NODE)); memcpy(pNew, pNode, sizeof(NODE)); pNew->pNext = pHead->pNext; pHead->pNext = pNew; return 0; #else return remove_list_node_by_position(pHead, 1, pNode); #endif } void remove_list_first_node(PNODE pHead) { /* 如果是空的链表则不需要操作 */ if(list_is_empty(pHead)){ printf("空链表,无需操作!\n"); return; } /* 将头节点指向第1个节点先保存起来 */ PNODE tmp = pHead->pNext; /* 将头节点指向第1个节点的下一个节点 */ pHead->pNext = pHead->pNext->pNext; /* 释放刚才保存的tmp节点 */ free(tmp); } void remove_list_node_by_position(PNODE pHead, int position) { PNODE tmp = pHead; PNODE tofree = NULL; int i = 0; /* 如果是空的链表则不需要操作 */ if(list_is_empty(pHead)){ printf("空链表,无需操作!\n"); return; } /* 找出需要删除的前一个位置 */ while(tmp->pNext && i < position-1){ tmp = tmp->pNext; i++; } /* 如果链表没有那么长则返回 */ if(tmp->pNext == NULL || i < position-1){ printf("链表长度不够!\n"); return; } /* 将要释放的节点先保存起来 */ tofree = tmp->pNext; /* 指向下一个节点的下一个节点 */ tmp->pNext = tmp->pNext->pNext; /* 释放资源 */ free(tofree); } void remove_list_tail_node(PNODE pHead) { int i = 0; int length = list_length(pHead); PNODE tmp = pHead->pNext; if(length >= 2){ /* 先找到倒数第2个节点 */ while(tmp->pNext && i < length-2){ tmp = tmp->pNext; i++; } /* 将倒数第1个节点释放 */ free(tmp->pNext); /* 将倒数第2个节点的指针指向NULL */ tmp->pNext = NULL; } else{ /* 只有一个节点;同时也能处理空链表 */ remove_list_first_node(pHead); } } int midify_list_node(PNODE pHead, int position, int val) { int i = 0; PNODE tmp = pHead; if(position > list_length(pHead)){ printf("链表长度不够!\n"); return -1; } /* 找出需要修改的位置 */ while(i < position){ tmp = tmp->pNext; i++; } tmp->data = val; return 0; } void show_all_list_node(PNODE pHead) { /* 从第一个节点开始而不是头节点 */ PNODE tmp = pHead->pNext; printf("链表数据如下: \n"); while(tmp != NULL){ printf("%d\n", tmp->data); /* 打印节点的数据 */ tmp = tmp->pNext; /* 切换到下一个节点 */ } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。