1 #include<iostream> 2 using namespace std; 3 4 #define OK 1 5 #define ERROR 0 6 #define OVERFLOW -2 7 typedef int Status; //Status 是函数返回值类型，其值是函数结果状态代码。 8 typedef int ElemType; //ElemType 为可定义的数据类型，此设为int类型 9 10 typedef struct LNode 11 { 12 ElemType data; //结点的数据域 13 struct LNode *next; //结点的指针域 14 }LNode,*LinkList; //LinkList为指向结构体LNode的指针类型 15 16 17 Status InitList_L(LinkList &L){ //算法2.5 单链表的初始化 18 //构造一个空的单链表L 19 L=new LNode; //生成新结点作为头结点，用头指针L指向头结点 20 L->next=NULL; //头结点的指针域置空 21 return OK; 22 } 23 24 Status ListInsert_L(LinkList &L,int i,ElemType &e){ //算法2.8 单链表的插入 25 //在带头结点的单链表L中第i个位置之前插入元素e 26 int j; 27 LinkList p,s; 28 p=L;j=0; 29 while(p && j<i-1){p=p->next;++j;} //刚好指向第i-1个节点 30 if(!p||j>i-1) return ERROR; //i大于表长+1或者小于1 当p不为空时如果i小于1的话则插入失败，如果p为空的话表明i大于表长 31 s=new LNode; //生成新结点s p指向当前第i-1的节点位置 32 s->data=e; //将结点s的数据域置为e 33 s->next=p->next; //将结点s插入L中 34 p->next=s; 35 return OK; 36 }//ListInsert_L 37 38 void CreateList_F(LinkList &L,int n){ //算法2.10 (前插法)创建单链表 39 //逆位序输入n个元素的值，建立到头结点的单链表L 40 LinkList p; 41 L=new LNode; 42 L->next=NULL; //先建立一个带头结点的空链表 43 cout<<"请输入 "<<n<<" 个数(以空格隔开，按回车结束)："; 44 for(int i=n;i>0;--i){ 45 p=new LNode; //生成新结点 46 cin>>p->data; //输入元素值 47 p->next=L->next; 48 L->next=p; //插入到表头 49 } 50 }//CreateList_F 51 52 void CreateList_L(LinkList &L,int n){ //算法2.11 (后插法)创建单链表 53 //正位序输入n个元素的值，建立到头结点的单链表L 54 LinkList r,p; 55 L=new LNode; 56 L->next=NULL; //先建立一个带头结点的空链表 57 r=L; //尾指针r指向头结点 58 cout<<"请输入 "<<n<<" 个数(以空格隔开，按回车结束)："; 59 for(int i=0;i<n;i++){ 60 p=new LNode; //生成新结点 61 cin>>p->data; //输入元素值 62 p->next=NULL; 63 r->next=p; //插入到表尾 64 r=p; //r指向新的尾结点 r始终指向当前节点 65 } 66 }//CreateList_L 67 68 Status findValList_L(LinkList L,int i,ElemType &indexVal){ //5.查找位序为i的元素，返回其值 69 LinkList p=L->next;//指向第一个结点 70 int j=1; 71 while(p && j<i){ //找第i个节点 72 p=p->next; 73 ++j; 74 } 75 if(!p||j>i)return ERROR;//i值不合法i大于表长或者是i小于1 76 indexVal=p->data; 77 return OK; 78 } 79 80 Status findIndexList_L(LinkList L,ElemType val,int &index){ //6.依值查找，返回其位序 81 LinkList p=L->next;//指向第一个节点 82 int j=1; 83 while(p){ 84 if(p->data==val){ 85 index=j; 86 return OK; 87 } 88 p=p->next; 89 j++; 90 } 91 return ERROR; 92 } 93 94 Status deleteIndexList_L(LinkList &L,int i){ //7.删除表中第i个元素 95 int j=0; 96 LinkList p=L; //这时要指向头节点，因为当i=1时，下面的循环进不去，也就是if判断不成功，进行删除节点操作 97 while(p && j<i-1){ //指向第i-1个节点 98 p=p->next; 99 j++; 100 } 101 if(!p||j>i-1)return ERROR;//如果p是空的话也就代表i大于表长，或者是 102 LinkList q=p->next;//q节点指向第i个节点 103 if(!q)return ERROR; //根据条件，此处应该判断p的后继是否为空即为i这个特殊情况，举个例子，表长为3时，i为4，到此句的时候就成立，表示表长加1这个位置没有元素 104 p->next=q->next;//链接链表 105 delete q; 106 return OK; 107 } 108 109 Status findMaxList_L(LinkList L,int &index,int &MaxVal){ //8.返回值最大的元素及其在表中位置，引用最大值 110 if(L->next==NULL)return ERROR;//如果是空链表，则返回0 111 LinkList p=L->next->next;//将p指向第二个节点 112 int j=2;//同时同步指针位置 113 MaxVal=L->next->data;//标记第一个节点的值为最大值 114 index=1;//同步最大值的位置 115 while(p){ 116 if(p->data>MaxVal){ 117 MaxVal=p->data; 118 index=j; 119 } 120 p=p->next; 121 j++; 122 } 123 return OK; 124 } 125 126 Status reverseList_L(LinkList &L){ //9.就地逆置算法 127 LinkList p=L->next,q; //先用p来保存原来的第一个节点 128 L->next=NULL;//仍利用原表的空间，此时将头结点指向空 129 if(!p)return ERROR; 130 while(p){ 131 q=p->next;//先用q来保存p节点的next域，用来移动原来的链表 132 p->next=L->next; //仍用L空间，使用插在头结点后面的位置也就是前插法 133 L->next=p; //L（带头节点）时刻指向当前节点p 134 p=q; //将p重新指向原表中后继 135 } 136 return OK; 137 } 138 139 Status delItemList_L(LinkList &L,ElemType item){ //10.删除表中所有值为item的数据元素 140 LinkList p=L,q;//指向头节点，临时指针q 141 bool f=false;//标记链表中是否有item这个元素 142 while(p){ 143 if((q=p->next)&&(q->data==item)){ //先判断是否有这个p->next这个元素 144 if(!f)f=true;//有的话只标记一次就好 145 p->next=q->next; //链接链表 146 delete q; 147 } 148 else p=p->next;//否则才移动p 149 } 150 if(!f)return ERROR; //标记该表中没有此元素 151 return OK; 152 } 153 154 int main() 155 { 156 int i,n,choose; 157 ElemType x; 158 LinkList L,p; 159 160 choose=-1; 161 while(choose!=0) 162 { 163 cout<<"******************************************************************************\n"; 164 cout<<" 1. 建立空链表; 2. 在表中输入指定个数的数据元素\n"; 165 cout<<" 3. 在第i个元素的前插入一个元素; 4. 逐个显示表中数据元素\n"; 166 cout<<" 5. 查找位序为i的元素，返回其值; 6. 依值查找，返回其位序\n"; 167 cout<<" 7. 删除表中第i个元素; 8. 返回值最大的元素及其在表中位置\n"; 168 cout<<" 9. 就地逆置; 10. 删除表中所有值为item的数据元素\n"; 169 cout<<" 0. 退出\n"; 170 cout<<"*******************************************************************************\n"; 171 172 cout<<"请选择:"; 173 cin>>choose; 174 switch(choose) 175 { 176 case 1: //建立一个单链表 177 if(InitList_L(L)) 178 cout<<"成功建立链表!\n\n"; 179 break; 180 case 2: //使用后插法创建单链表 181 cout<<"请输入一个数，代表元素的个数："; 182 cin>>n; 183 CreateList_L(L,n); 184 cout<<"成功创建链表!\n\n"; 185 break; 186 case 3: //单链表的插入 187 cout<<"请输入两个数，分别代表插入的位置和插入数值(用空格间隔，最后回车):"; 188 cin>>i>>x; //输入i和x，i代表插入的位置，x代表插入的数值 189 if(ListInsert_L(L,i,x)) 190 cout<<"成功将"<<x<<"插在第"<<i<<"个位置\n\n"; 191 else 192 cout<<"插入失败!\n\n"; 193 break; 194 case 4: //单链表的输出 195 p=L->next;//指向第一个节点 196 if(!p) 197 cout<<"当前为空链表"<<endl<<endl; 198 else{ 199 cout<<"现在链表里的数分别是："; 200 i=0; 201 while(p){//循环直到为空 202 i++; 203 cout<<p->data<<"，"; 204 p=p->next; 205 } 206 cout<<"共有"<<i<<"个元素。"<<endl<<endl; 207 } 208 break; 209 case 5: //查找位序为i的元素，返回其值 210 cout<<"请输入一个你想要查找该元素的位序："; 211 cin>>i; 212 if(findValList_L(L,i,x)) 213 cout<<"位序为"<<i<<"的元素为"<<x<<".\n"<<endl; 214 else 215 cout<<"输入位序序号不在链表节点序号范围内"<<endl<<endl; 216 break; 217 case 6: //依值查找，返回其位序 218 int index; 219 cout<<"请输入要查找的元素："; 220 cin>>x; 221 if(findIndexList_L(L,x,index)) 222 cout<<"查找元素"<<x<<"在链表中的位序为"<<index<<".\n"<<endl; 223 else 224 cout<<"此元素不在该链表中"<<endl<<endl; 225 break; 226 case 7: //删除表中第i个元素 227 cout<<"请输入删除表中元素的位置："; 228 cin>>i; 229 if(deleteIndexList_L(L,i)) 230 cout<<"第"<<i<<"个位置的元素已被删除.\n"<<endl; 231 else 232 cout<<"输入位置不在当前链表节点序号范围内"<<endl<<endl; 233 break; 234 case 8: //返回值最大的元素及其在表中位置 235 ElemType MaxVal; 236 if(findMaxList_L(L,i,MaxVal)) 237 cout<<"当前链表中最大的元素为"<<MaxVal<<"，其位置为"<<i<<".\n"<<endl; 238 else 239 cout<<"当前为空链表"<<endl<<endl; 240 break; 241 case 9: //就地逆置 242 if(reverseList_L(L)) 243 cout<<"就地成功逆置链表"<<endl<<endl; 244 else 245 cout<<"此表为空链表"<<endl<<endl; 246 247 break; 248 case 10: //删除表中所有值为item的数据元素 249 if(L->next==NULL) 250 cout<<"当前为空链表"<<endl<<endl; 251 else{ 252 cout<<"请输入要删除链表的一个元素："; 253 cin>>x; 254 if(delItemList_L(L,x)) 255 cout<<"删除成功，已经将元素"<<x<<"从链表中删除.\n"<<endl; 256 else 257 cout<<"此链表没有"<<x<<"这个元素.\n"<<endl; 258 } 259 break; 260 } 261 } 262 return 0; 263 }