实验目的1．  定义单链表的结点类型。2．  熟悉对单链表的一些基本操作和具体的函数定义。3．  通过单链表的定义掌握线性表的链式存储结构的特点。4．  掌握循环链表和双链表的定义和构造方法。实验内容该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。/* 定义DataType为int类型 */typedef int DataType; /* 单链表的结点类型 */typedef struct LNode{DataType data;     struct LNode *next;}LNode,*LinkedList; /* 初始化单链表 */LinkedList LinkedListInit() /* 清空单链表 */void LinkedListClear(LinkedList L) /* 检查单链表是否为空 */int LinkedListEmpty(LinkedList L) /* 遍历单链表 */void LinkedListTraverse(LinkedList L) /* 求单链表的长度 */int  LinkedListLength(LinkedList L) /* 从单链表表中查找元素 */LinkedList  LinkedListGet(LinkedList L,int  i) /* 从单链表表中查找与给定元素值相同的元素在链表中的位置 */LinkedList  LinkedListLocate(LinkedList  L, DataType  x) /* 向单链表中插入元素 */void  LinkedListInsert(LinkedList L,int i,DataType  x) /* 从单链表中删除元素 */void LinkedListDel(LinkedList  L,DataType x) /* 用尾插法建立单链表 */LinkedList  LinkedListCreat( )

  1 #include <stdio.h>  2 #include <malloc.h>  3 #include <stdlib.h>  4   5 /* 定义DataType为int类型 */  6 typedef int DataType;  7    8 /* 单链表的结点类型 */  9 typedef struct LNode{ 10     DataType data; 11     struct LNode *next; 12 }LNode,*LinkedList; 13   14 /* 1. 初始化单链表 */ 15 LinkedList LinkedListInit() 16 { 17     LinkedList head = (LNode*)malloc(sizeof(LNode)); 18     head->next = NULL; 19     return head; 20 } 21   22 /* 2. 清空单链表 */ 23 void LinkedListClear(LinkedList L) 24 { 25     //L为头指针 26     while(L->next!=NULL){    //依次清空节点，直到头指针指向的下一个节点的地址为空 27         LinkedList t; 28         t = L->next; 29         L->next = t->next; 30         free(t); 31     } 32     return ; 33 } 34   35 /* 3. 检查单链表是否为空 */ 36 int LinkedListEmpty(LinkedList L) 37 { 38     if(L->next==NULL)    //头指针指向的下一个节点地址为空，说明链表为空。否则不为空。 39         return 1; 40     else  41         return 0; 42 } 43   44 /* 4. 遍历单链表 */ 45 void LinkedListTraverse(LinkedList L) 46 { 47     LinkedList p = L->next; 48     while(p){ 49         printf("%d ",p->data);    //遍历输出节点 50         p = p->next; 51     } 52     printf("\n"); 53     return ; 54 } 55   56 /* 5. 求单链表的长度 */ 57 int  LinkedListLength(LinkedList L) 58 { 59     LinkedList p = L->next; 60     int len=0; 61     while(p){ 62         len++;    //遍历一个节点长度+1 63         p = p->next; 64     } 65     return len; 66 } 67   68 /* 6. 从单链表表中查找元素 */ 69 LinkedList  LinkedListGet(LinkedList L,int  i) 70 { 71     int j=1; 72     LinkedList p = L->next; 73     while(p){ 74         if(j==i) 75             return p;  76         p = p->next; 77         j++;    //遍历一个节点长度+1 78     } 79     return NULL; 80 } 81   82 /* 7. 从单链表表中查找与给定元素值相同的元素在链表中的位置 */ 83 int LinkedListLocate(LinkedList  L, DataType  x) 84 { 85     int i=1; 86     LinkedList p = L->next; 87     while(p){ 88         if(p->data=http://www.mamicode.com/=x) 89             return i;  90         p = p->next; 91         i++; 92     } 93     return 0; 94 } 95   96 /* 8. 向单链表中插入元素 */ 97 void  LinkedListInsert(LinkedList L,int i,DataType  x) 98 { 99     int j=1;100     LinkedList p = L->next;101     while(p && j!=i-1){    //找到i的前一个元素102         p = p->next;103         j++;    //遍历一个节点+1104     }105     //找到位置106     if(j==i-1){107         LinkedList q = (LinkedList)malloc(sizeof(LNode));108         q->data =http://www.mamicode.com/ x;109         q->next = p->next;110         p->next = q;111     }112     return ;113 }114 115 /* 9. 从单链表中删除元素 */116 void LinkedListDel(LinkedList  L,DataType x)117 {118     LinkedList p = L->next;119     while(p->next->data!=x){    //找到值为x的前一个元素120         p = p->next;121     }122     //找到位置123     if(p->next->data=http://www.mamicode.com/=x){124         LinkedList q = p->next;125         p->next = q->next;126         free(q);127     }128     return ;129 }130  131 /* 10. 用尾插法建立单链表 */132 LinkedList  LinkedListCreat( LinkedList L,DataType a[],int n )    //讲数组a中的元素以尾插法放入链表中133 {134     LinkedList p = L;135     int i;136     for(i=1;i<=n;i++){137         LinkedList q = (LinkedList)malloc(sizeof(LNode));138         q->data =http://www.mamicode.com/ a[i];139         q->next = NULL;140         p->next = q;141         p = q;142     } 143     return L;144 }145 146 int Menu()147 {148     int in;149     printf("[0] 请先初始化一个链表\n");150     printf("[1] 用尾插法建立单链表\n");151     printf("[2] 检查单链表是否为空\n");152     printf("[3] 遍历单链表\n");153     printf("[4] 求单链表的长度\n");154     printf("[5] 从单链表表中查找元素\n");155     printf("[6] 从单链表表中查找与给定元素值相同的元素在链表中的位置\n");156     printf("[7] 向单链表中插入元素\n");157     printf("[8] 从单链表中删除元素\n");158     printf("[9] 清空单链表\n");159     printf("[10] 按其他键退出\n");160     scanf("%d",&in);161     return in;162 }163 LinkedList Reply(LinkedList head,int in)164 {165     int i,n;166     switch(in){167         case 0:    //初始化一个链表168             head = LinkedListInit();169             printf("初始化成功!\n");170             break;171 172         case 1:    //用尾插法建立单链表173             int a[1001];174             printf("请问你要输入多少个数据？：（最多1000个）\n");175             scanf("%d",&n);    //输入链表大小176             printf("请依次输入数据:\n");177             for(i=1;i<=n;i++) 178                 scanf("%d",&a[i]);    179             head = LinkedListCreat(head,a,n);180             printf("链表建立成功!\n");181             break;182 183         case 2:    //检查单链表是否为空184             if(LinkedListEmpty(head))185                 printf("链表为空\n");186             else 187                 printf("链表不为空\n");188             break;189 190         case 3:    //遍历单链表191             LinkedListTraverse(head);192             break;193 194         case 4:    //求单链表的长度195             printf("链表长度为：%d\n",LinkedListLength(head));196             break;197 198         case 5:    //从单链表中查找元素199             printf("你要查找链表中第几个元素值？\n");200             scanf("%d",&n);201             LinkedList p;202             p = LinkedListGet(head,n);203             printf("第%d个元素值是：%d\n",n,p->data);204             break;205 206         case 6:    //从单链表表中查找与给定元素值相同的元素在链表中的位置207             printf("你要查找的元素值是？\n");208             scanf("%d",&n);209             printf("它是第%d个元素\n",LinkedListLocate(head,n));210             break;211 212         case 7:    //向单链表中插入元素213             printf("请问你要在第几个元素的位置插入？\n");214             scanf("%d",&i);215             printf("请问你要插入的元素值为多少？\n");216             scanf("%d",&n);217             LinkedListInsert(head,i,n);218             printf("插入成功!\n");219             printf("插入之后的链表结构为:\n");220             LinkedListTraverse(head);221             break;222 223         case 8:    //从单链表中删除元素224             printf("请问你要删除值为多少的元素？\n");225             scanf("%d",&n);226             LinkedListDel(head,n);227             printf("删除成功!\n");228             printf("删除之后的链表结构为:\n");229             LinkedListTraverse(head);230             break;231 232         case 9:    //清空单链表233             LinkedListClear(head);234             printf("清空成功!\n");235             break;236 237         default:238             printf("Bye~\n");239             exit(1);240     }241     return head;242 }243 int main()244 {245     int in;    //存储输入命令246     LinkedList head;247     while(1){248         in = Menu();249         head = Reply(head,in);    //响应命令250         printf("\n");251         system("pause");252         system("cls");253     }254     return 0;255 }