线性表-单链表
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 2024.8.11/*1. 单链表的定义LinkList 表示 LNode* 类型的指针
*/
typedef struct LNode{int data;struct LNode *next;
}LNode,*LinkList;/* 2. 带头节点的单链表的初始化*L 指向节点的指针 初始化的时候，必须传入 指向 头节点指针的指针 */bool InitList(LinkList *L){*L = (LNode*)malloc(sizeof(LNode));// 检查内存分配是否成功if(*L == NULL) return false;(*L)->next = NULL;return true;
}/*3. 求表长
*/int Length(LinkList L){int len = 0;// p指向第一个节点 LinkList p = L->next;while(p!=NULL){len++;p = p->next;}return len;
}/*4. 按序号查找节点查找第i个节点，返回该节点的指针；如果i大于单链表的长度，返回 NULL
*/LinkList GetElem(LinkList L,int i){// 让 p 指向头节点 LinkList p = L;while(i>0){if(p==NULL){return p;}p=p->next;i--;}return p;
}/*5. 按值查找表节点找到值相同的节点，返回该节点的指针；没有找到，返回NULL
*/LinkList LocateElem(LinkList L,int e){LinkList p = L->next;while(p!=NULL){if(p->data == e){return p;}p = p->next;}return p;
}/*6. 插入节点在 第 i 个位置插入新节点插入成功返回 true, 插入位置i不合法(大于链表长度+1)，返回false
*/
bool ListInsert(LinkList L,int i,int data){if(i <= 0) return false;int j = 0;LinkList p = L;while(j<i-1){if(p==NULL) return false; // i > (len+1)p = p->next;j++;}LinkList s = (LinkList)malloc(sizeof(LNode));if (s == NULL) return false; // 检查内存分配是否成功s->data = data;s->next = p->next;p->next = s;return true;
}/*7. 删除第i个节点，将第i个节点的值赋给 e指向的地址处 删除成功返回 true, 删除失败返回 false
*/bool ListDelete(LinkList L,int i,int *e){if(i <= 0) return false;LinkList p = L; // p 指向头节点 int j = 0; while(j < i-1){if(p == NULL) return false;p = p->next;j++;}if(p->next == NULL) return false; // i 超过长度LinkList s = p->next; // s指向要删除的节点 *e = p->next->data;p->next = s->next;free(s); return true;
}/*8.头插法建立新链表将 输入的值插入到链表的表头，输入 9999 表示结束
*/LinkList List_HeadInsert(LinkList L){int x;LinkList s; // s 指向待插入的新节点 scanf("%d",&x);while(x!=9999){s = (LinkList) malloc(sizeof(LNode));if(s==NULL) break;s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L;
}/*9. 尾插法建立单链表 L 是一个只带头节点的空链表
*/
LinkList List_TailInsert(LinkList L){int x;LinkList t = L; // 尾节点 LinkList s; // 待插入的节点scanf("%d",&x);while(x!=9999){s = (LinkList) malloc(sizeof(LNode));if(s==NULL) break;s->data = x;t->next = s;t = s;scanf("%d",&x);} t->next = NULL;return L;
}// 打印链表
void printList(LinkList L){LinkList p = L->next;while(p!=NULL){printf("%d ",p->data);p = p->next;}printf("\n");
}int main(){// LinkList 指向 LNode 的指针LinkList list;if(InitList(&list)){printf("链表初始化成功\n"); }ListInsert(list,1,1); ListInsert(list,2,2);ListInsert(list,3,3);ListInsert(list,4,4);ListInsert(list,5,5);ListInsert(list,5,-1);if(ListInsert(list,10,5)){printf("插入成功\n"); }else{printf("插入失败\n"); }printList(list);int deleteData;if(ListDelete(list,2, &deleteData)){printf("删除第 2 个节点成功，第2个节点的值 %d \n",deleteData);}else{printf("删除失败\n");}printList(list);int len = Length(list);printf("链表长度 %d \n",len);int n2 = 1;LinkList node2 =LocateElem(list,n2);if(node2 == NULL){printf("链表不存在值为%d的节点 \n",n2);}else {printf("链表存在值为%d的节点，节点数据域：%d \n",n2,node2->data);}int n1 = 1;LinkList node1 = GetElem(list,n1);if(node1 == NULL){printf("链表第 %d 个节点不存在 \n",n1);}else {printf("链表第个 %d 节点数值 %d \n",n1,node1->data); }// 头插 LinkList list2;if(InitList(&list2)){printf("链表初始化成功\n"); }List_HeadInsert(list2);printList(list2);// 尾插LinkList list3;if(InitList(&list3)){printf("链表初始化成功\n"); }List_TailInsert(list3); printList(list3);return 0;
}
