c——链表

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 
  5 typedef int ElementType;        //定义数据类型,可根据需要进行其他类型定义
  6 //链表节点的定义
  7 typedef struct ListNode {
  8     ElementType  Element;        //数据域，存放数据
  9     ListNode* Next;        //指向下一个链表节点
 10 } Node, *PNode;
 11 
 12 //链表创建函数定义
 13 PNode CreateList(void) {
 14     int len ;    //用于定义链表长度
 15     int val ;    //用于存放节点数值
 16     PNode PHead = (PNode)malloc(sizeof(Node));    //创建分配一个头节点内存空间
 17 //头节点相当于链表的哨兵，不存放数据，指向首节点（第一个节点）
 18     if (PHead == NULL) {  //判断是否分配成功
 19         printf("空间分配失败 \n");
 20         exit(-1);
 21     }
 22 
 23     PNode PTail = PHead;    //链表的末尾节点，初始指向头节点
 24     PTail->Next = NULL;    //最后一个节点指针置为空
 25     printf("请输入节点个数：");
 26     scanf("%d", &len);        //输入节点个数
 27     for (int i = 0; i < len; i++) {
 28 
 29         PNode pNew = (PNode)malloc(sizeof(Node));    //分配一个新节点
 30         if (pNew == NULL) {
 31             printf("分配新节点失败\n");
 32             exit(-1);
 33         }
 34         printf("请输入第 %d 个节点的数据：", i + 1);
 35         scanf("%d", &val);    //输入链表节点的数据
 36 
 37         pNew->Element = val;    //把数据赋值给节点数据域
 38         PTail->Next = pNew;    //末尾节点指针指向下一个新节点
 39         pNew->Next = NULL;        //新节点指针指向为空
 40         PTail = pNew;    //将新节点复制给末尾节点
 41     }
 42     printf("创建链表成功\n");
 43     return PHead;    //返回头节点
 44 }
 45 
 46 void TraverseList(PNode List) {
 47     PNode P = List->Next;
 48     printf("遍历链表的值为：");
 49     if(P==NULL) printf("链表为空");
 50     while(P!=NULL) {
 51         printf("%d",P->Element);
 52         P=P->Next;
 53     }
 54     printf("\n");
 55 }
 56 
 57 PNode FindList(PNode List) {
 58     PNode P = List->Next;
 59     int num = 0;
 60     int val = 0;
 61     printf("请输入要查询的数：");
 62     scanf("%d",&val);
 63     while(P!=NULL && P->Element!=val) {
 64         P=P->Next;
 65         ++num;
 66     }
 67     if(P!=NULL) printf("找到的节点为：%d",num+1);
 68     else printf("找不到该节点");
 69     printf("\n");
 70     return P;
 71 }
 72 
 73 void InsertList(PNode List, int pos, int val) {
 74     int position = 0;
 75     PNode P = List;
 76     while(P!=NULL && position<pos-1) {
 77         P = P->Next;
 78         ++position;
 79     }
 80     PNode Tmp = (PNode)malloc(sizeof(Node));
 81     if(Tmp == NULL) {
 82         printf("内存分配失败！");
 83         exit(-1);
 84     }
 85     Tmp->Element = val;
 86     Tmp->Next = P->Next;
 87     P->Next = Tmp;
 88 }
 89 //删除整个链表
 90 void DeleteTheList(PNode List) {
 91     PNode P,Tmp;
 92     P = List->Next;
 93     List->Next = NULL;
 94     while(P!=NULL) {
 95         Tmp = P->Next;
 96         free(P);
 97         P = Tmp;
 98     }
 99     printf("删除链表成功！\n");
100 }
101 //删除链表中的元素
102 void DeleteList(PNode List,int pos) {
103     int position = 0;
104     PNode P = List;
105     while(P!=NULL && position<pos-1) {
106         P = P->Next;
107         ++position;
108     }
109     PNode Tmp = P->Next;
110     P->Next = Tmp->Next;
111     free(Tmp);
112     Tmp=NULL;
113 }
114 //主函数
115 int main() {
116     PNode List = CreateList();    //创建一个指针，使其指向新创建的链表的头指针
117     TraverseList(List);
118     FindList(List);
119     InsertList(List,3,100);
120     TraverseList(List);
121     DeleteList(List,3);
122     TraverseList(List);
123     DeleteTheList(List);
124     TraverseList(List);
125     return 0;
126 }