#include <stdio.h> #include <malloc.h> #include <stdlib.h> //定义了一个数据类型 typedef struct Node { int data; //数据域 struct Node *pNext; //指针域 } NODE, *PNODE; //NODE等价于struct NODE,PNODE等价于stuct Node * PNODE create_list(void); void traverse_list(PNODE pHead); int is_empty(PNODE pHead); int lenth_list(PNODE pHead); void insert_list(PNODE pHead, int pos, int val); int delete_list(PNODE pHead, int pos, int *val); // //int is_full(PNODE pHead); // // void sort_list(PNODE pHead); int main() { PNODE pHead = NULL; //等价于struct Node * pHead = NULL; pHead = create_list(); //create_list()功能:创建一个非循环单链表,并将该链表的头节点的地址赋给pHead traverse_list(pHead); if (is_empty(pHead)) { printf("链表为空"); } else { printf("链表不为空"); } int len = lenth_list(pHead); printf("\n链表为长度: %d", len); sort_list(pHead); printf("\n"); traverse_list(pHead); insert_list(pHead,3,99); printf("\n插入元素的打印\n"); traverse_list(pHead); printf("\n删除第3位的元素后的输出为:\n"); int deleteVal; int deleteFlag = delete_list(pHead, 3, &deleteVal); if(deleteFlag){ printf("\n删除成功:\n"); }else{ printf("\n删除失败:\n"); } traverse_list(pHead); } PNODE create_list(void) { int len; //存放有效节点的个数 int i; int val; //用来临时存放用户输入的结点的值 PNODE pHead = (PNODE) malloc(sizeof(NODE)); if (NULL == pHead) { printf("分配失败,程序终止!\n"); exit(-1); } PNODE pTail = pHead; //尾节点 pTail->pNext = NULL; printf("请输入您需要生产的链表节点的个数: len = "); scanf("%d", &len); for (i = 0; i < len; ++i) { // printf("请输入第%d个节点的值: ", i + 1); // scanf("%d", &val); PNODE pNew = (PNODE) malloc(sizeof(NODE)); if (NULL == pNew) { printf("分配失败,程序终止!\n"); exit(-1); } pNew->data = rand() % 100 + 1; printf("pNew->data的值: ", pNew->data); pTail->pNext = pNew; pNew->pNext = NULL; pTail = pNew; printf("\n", pNew->data); } return pHead; } void traverse_list(PNODE pHead) { PNODE p = pHead->pNext; while (NULL != p) { printf("%d ", p->data); p = p->pNext; } printf("\n"); return; } int is_empty(PNODE pHead) { if (NULL == pHead->pNext) { return 1; } return 0; } int lenth_list(PNODE pHead) { PNODE p = pHead->pNext; int len = 0; while (NULL != p) { ++len; p = p->pNext; } return len; } void sort_list(PNODE pHead) { int i, j, t; int len = lenth_list(pHead); PNODE p, q; for (i = 0, p = pHead->pNext; i < len - 1; ++i, p = p->pNext) { for (j = i + 1, q = p->pNext; j < len; ++j, q = q->pNext) { if (p->data > q->data) { t = p->data; p->data = q->data; q->data = t; } } } return; } /** * 在pHead所指向链表的第pos个节点前面插入一个新的节点,该节点的值为val * @param pHead * @param pos * @param val * @return */ void insert_list(PNODE pHead, int pos, int val){ int i = 0; PNODE p = pHead; //获取插入位置前的节点 while (NULL != p && i<pos -1){ p = p ->pNext; ++i; } if(i > pos - 1 || NULL == p){ return; } //创建新节点 PNODE pNew = (PNODE)malloc(sizeof(NODE)); //异常判断 if(NULL == pNew){ printf("动态分配内存失败!\n"); exit(-1); } //将新元素放在插入位置相邻的2个元素的中间 pNew -> data = val; //定义一个临时节点,保存原来的链表中的 插入位置前指针 其值指向的插入位置后的地址 PNODE pNode = p -> pNext; //新链表中,插入前位置的指针指向要插入元素的地址 p -> pNext = pNew; //新链表中,新插入元素的指针地址指向 原来插入位置后的元素的地址 pNew -> pNext = pNode; return ; } int delete_list(PNODE pHead, int pos, int *val){ int i = 0; PNODE p = pHead; //获取要删除位置前的节点,这里注意头节点不算位置的,i=o时,才指向头指针 while (NULL != p->pNext && i<pos-1){ p = p ->pNext; ++i; } if(i > pos - 1 || NULL == p->pNext){ return 0; } //保存要删除的节点 PNODE q = p -> pNext; *val = q->data; //要删除的节点前的节点 指向 要删除的后的节点 p -> pNext = p ->pNext ->pNext; //释放删除元素的内存 free(q); return 1; }
大功告成!!