1 /*  2     线性表之单向链表的一些常见操作  3 */  4 #include <iostream>  5 using namespace std;  6   7 typedef int ElemType;  8 typedef struct LNode  9 { 10     ElemType data; 11     struct LNode* next; 12 }LinkList; 13  14 /* 15 建立单向链表----尾插法 16 */ 17 void CreateLinkList( LinkList* &head , ElemType* arr , int n ) 18 { 19     cout<<"建立链表:"<<endl; 20     LinkList* temp , *rend; 21     head = new LinkList; 22     rend = head; 23     for( int i = 0 ; i<n ; i++ ) 24     { 25         temp = new LinkList; 26         temp->data =http://www.mamicode.com/ arr[i]; 27         rend->next = temp; 28         rend = temp; 29     } 30     rend->next = NULL; 31 } 32  33 /* 34 建立单向链表-头插法 这里我不使用它 个人更倾向于尾插法 35 void CreateLinkList( LinkList* &head , ElemType* arr , int n ) 36 { 37     LinkList* temp; 38     head = new LinkList; 39     head->next = NULL; 40     for( int i = 0 ; i<n ; i++ ) 41     { 42         temp = new LinkList; 43         temp->data = http://www.mamicode.com/arr[i];> 44         temp->next = head->next; 45         head->next = temp; 46     } 47 } 48 */ 49  50 /* 51 输出单向链表 52 */ 53 void printList(LinkList* head) 54 { 55     LinkList* p = head->next; 56     cout<<"输出链表:"<<endl; 57     while( p!=NULL ) 58     { 59         cout<<p->data<<endl; 60         p = p->next; 61     } 62 } 63  64 /* 65 求链表中第x个结点的值 66 */ 67 bool getElemType( LinkList* head , int x , ElemType& value ) 68 { 69     int index = 1; 70     LinkList* p = head->next; 71     if( x<=0 ) 72     { 73         cout<<"fail--error"<<endl; 74         return false; 75     } 76     while( index<x && p!=NULL ) 77     { 78         index++; 79         p = p->next; 80     } 81     if( p==NULL ) 82     { 83         cout<<"damn it.this index is not found"<<endl; 84         return false; 85     } 86     else 87     { 88         cout<<"success-----"<<endl; 89         value = http://www.mamicode.com/p->data; 90     } 91     return true; 92 } 93  94 /* 95 查找特定ElemType的结点标号 96 */ 97 bool getIndex( LinkList* L , ElemType value , int& index ) 98 { 99     int i = 1;100     LinkList* p = L->next;101     while( p!=NULL && p->data!=value )102     {103         p = p->next;104         i++;105     }106     if( p==NULL )107     {108         cout<<"dama it.this value is not found"<<endl;109         return false;110     }111     else112     {113         cout<<"success~~~~~";114         index = i;115     }116     return true;117 }118 119 /*120 插入ElemType的元素到第I个结点的位置121 */122 bool insertElemType( LinkList* &head , int index , ElemType value )123 {124     int i = 1;125     LinkList* p = head;126     LinkList* temp;127     if( index<=0 )128     {129         cout<<"fail--error"<<endl;130         return false;131     }132     while( i<index && p!=NULL )133     {134         i++;135         p = p->next;136     }137     if( p==NULL )138     {139         cout<<"****insert fail****"<<endl;140         return false;141     }142     else143     {144         temp = new LinkList;145         temp->data =http://www.mamicode.com/ value;146         temp->next = p->next;147         p->next = temp;148         cout<<"****insert successfully****"<<endl;149     }150     return true;151 }152 153 /*154 删除第i个结点,并返回该结点的数据信息155 */156 bool deleteNode( LinkList* head , int index , ElemType& value )157 {158     int i = 1;159     LinkList* p = head;160     LinkList* temp;161     if( index<=0 )162     {163         cout<<"---fail error--"<<endl;164         return false;165     }166     while( i<index && p!=NULL )167     {168         i++;169         p = p->next;170     }171     if( p==NULL )172     {173         cout<<"****fail delete***"<<endl;174         return false;175     }176     else177     {178         temp = p->next;179         if( temp==NULL )180         {181             cout<<"****fail delete****"<<endl;182             return false;183         }184         value = http://www.mamicode.com/temp->data;185         p->next = temp->next;186         cout<<"***delete successfully****"<<endl;187         delete temp;188     }189     return true;190 }191 192 /*193 判断链表是否为空表194 */195 bool emptyList( LinkList* head )196 {197     return head->next==NULL;198 }199 200 /*201 求出链表的长度202 */203 int ListLength( LinkList* head )204 {205     int len = 0;206     LinkList* p = head;207     while( p->next!=NULL )208     {209         len++;210         p = p->next;211     }212     return len;213 }214 215 /*216 删除整个链表217 */218 void DestoryList( LinkList* &head )219 {220     LinkList* p = head;221     LinkList* temp = p->next;222     while( temp!=NULL )223     {224         delete p;225         p = temp;226         temp = p->next;227     }228     delete p;229 }230 231 int main()232 {233     int arr[20] = {5,2,0,1,3,1,4};234     LinkList* pList;235     CreateLinkList( pList , arr , 7 );236     printList( pList );237     int value;238     int index;239     if( getElemType( pList , 3 , value ) )240     {241         cout<<"the value is:"<<value<<endl;242     }243     if( getIndex(pList , 1 , index ) )244     {245         cout<<"the index is:"<<index<<endl;246     }247     if( insertElemType( pList , 6 , 11 ) )248     {249         cout<<"成功插入链表元素"<<endl;250         printList( pList );251     }252     253     if( deleteNode( pList , 4 , value ) )254     {255         cout<<"the node deleted ‘ s data is:"<<value<<endl;256         printList( pList );257     }258     if( emptyList( pList ) )259     {260         cout<<"空表"<<endl;261     }262     cout<<"the length is:"<<ListLength(pList)<<endl;263     DestoryList( pList );264     return 0;265 }