1 #include "stdio.h" 2 #include "malloc.h" 3 #define datatype int 4 typedef struct node 5 { 6 datatype data; //链表的数据域 7 struct node *next; //链表的指针域 8 } LNode,*LinkList; 9 10 LinkList Creat_LinkList1( ) //头插入法建立单链表算法 11 { 12 int i; 13 int x; 14 int n; 15 LNode *L; 16 L=(LNode *)malloc(sizeof(LNode)); 17 L->next = NULL; 18 printf("输入单链表的长度（头插法）:"); 19 scanf("%d",&n); 20 printf("输入元素："); 21 for(i=0;i<n;i++) 22 { 23 LNode *p; 24 p=(LNode *)malloc(sizeof(LNode)); 25 scanf("%d",&x); 26 p->data = x; 27 p->next = L->next; 28 L->next = p; 29 } 30 return L; 31 } 32 /*按序号查找 Get_Linklist(L,i) 33 在单链表L中查找第i个元素结点，找到返回其指针，否则返回空*/ 34 LNode *Get_LinkList(LinkList L,int i) 35 { 36 LNode *p; 37 int j; 38 if(L->next==NULL) 39 return NULL; 40 if(i<1) 41 return NULL; 42 j=0; 43 p=L; 44 while(p->next!=NULL&&j<i) 45 { 46 p=p->next; 47 j++; 48 } 49 if(j==i) 50 return p; 51 else 52 return NULL; 53 } 54 /*插入运算 Insert_LinkList(L,i,x) 55 在单链表L的第i个位置上插入值为x的元素*/ 56 int Insert_LinkList(LinkList L, int i, datatype x) 57 { 58 LinkList p; 59 LNode *s; 60 int j; 61 p=L; 62 j=1; 63 while(j<i){ 64 p=p->next; 65 j++; 66 } 67 s=(LNode*)malloc(sizeof(LNode)); 68 s->data=x; 69 s->next=p->next; 70 p->next=s; 71 return 1; 72 } 73 /*删除运算：Del_LinkList(L,i) 74 删除单链表L上的第i个数据结点*/ 75 int Del_LinkList(LinkList L,int i) 76 { 77 int j; 78 LinkList p,q; 79 p=L; 80 j=1; 81 while(j<i) 82 { 83 p=p->next; 84 j++; 85 } 86 q=p->next; 87 p->next = p->next->next; 88 free(q); 89 return 1; 90 } 91 void print(LinkList L) //输出单链表 92 { LNode *p=L; 93 p=L->next; 94 while(p->next!=NULL) 95 { printf("%d->",p->data); //输出表中非最后一个元素 96 p=p->next; 97 } 98 printf("%d ",p->data); //输出表中最后一个元素 99 } 100 void linkcount(LinkList L) 101 { 102 struct a{ 103 int x; 104 int y; 105 }a[100]; 106 int m=0; 107 LinkList p,q; 108 p=(LinkList)malloc(sizeof(LNode)); 109 q=(LinkList)malloc(sizeof(LNode)); 110 while(L->next){ 111 a[m].x=L->next->data; 112 a[m].y=1; 113 p=L->next; 114 while(p->next) 115 { 116 if(L->next->data==p->next->data) 117 { 118 p->next=p->next->next; 119 a[m].y++; 120 } 121 else 122 { 123 p=p->next; 124 } 125 } 126 m++; 127 L=L->next; 128 } 129 printf("该链表中 "); 130 for(int i=0;i<m;i++){ 131 printf("%d出现%d次 ",a[i].x,a[i].y); 132 } 133 } 134 135 void main() 136 { 137 LinkList H; 138 int i,j,k; 139 datatype x; 140 do 141 { 142 printf(" "); 143 printf(" 链表子系统 "); 144 printf(" ******************************* "); 145 printf(" * 1----建 表 * "); 146 printf(" * 2----插 入 * "); 147 printf(" * 3----删 除 * "); 148 printf(" * 4----查 找 * "); 149 printf(" * 5----显 示 * "); 150 printf(" * 6----计 数 * "); 151 printf(" * 0----返 回 * "); 152 printf(" ******************************* "); 153 printf(" 请选择菜单项(0－5)："); 154 scanf("%d",&k);getchar(); 155 if (k==1) 156 H=Creat_LinkList1( ); //用头插入法建立单链表 157 else if (k==2) //在线性表第i位置处插入值为X的元素 158 { 159 printf(" 请输入插入的位置i和数据X(输入格式：i,X):"); 160 scanf("%d,%d",&i,&x); 161 j=Insert_LinkList(H,i,x); 162 } 163 else if (k==3) 164 { printf(" 请输入要删除元素的位置i:"); 165 scanf("%d",&i); 166 j=Del_LinkList(H,i); 167 if (j == 1) printf("删除成功!!"); 168 else printf("删除失败!!"); 169 } 170 else if(k==4) //查找线性表中元素值为x的位置 171 { 172 LNode *p; 173 printf(" 请输入要查找的序号i:"); 174 scanf("%d",&i); 175 p=Get_LinkList(H,i); 176 if (p!=NULL) 177 { print(H);printf("中序号为i的地址是 %d ",p);} 178 else 179 printf("链表中无此序号!! "); 180 } 181 else if (k==5) //输出链表 182 { printf(" 表的存储顺序为："); 183 print(H); 184 } 185 else if (k==6) // 186 { printf(" 计数："); 187 linkcount(H); 188 } 189 }while(k!=0); 190 }
部分运行结果：
