1 #include<iostream>
  2 #include<cstdlib>
  3 using namespace std;
  4 #define ture 1
  5 #define false 0
  6 #define maxsize 50
  7 #define listincreament 10
  8 #define ok 1
  9 #define error -3
 10 #define overflow -2
 11 typedef int Status;
 12 typedef int ElemType;
 13 typedef struct LNode
 14 {
 15     ElemType data;
 16     struct LNode *next;
 17 } LNode,*LinkList;
 18 //头插法建单链表
 19 void CreatList_head(LinkList &L,int length)//头插法
 20 {
 21     LNode *s;
 22     int x;
 23     L=(LinkList)malloc(sizeof(LNode));
 24     L->next=NULL;//创建头结点
 25     while(length--)
 26     {
 27         cin>>x;
 28         s=(LNode *)malloc(sizeof(LNode));
 29         s->data=http://www.mamicode.com/x;
 30         s->next=L->next;
 31         L->next=s;
 32     }
 33 
 34 }
 35 void CreatList_tail(LinkList &L,int length)//尾插法
 36 {
 37     LNode *p,*s;
 38     int x;
 39     L=(LinkList)malloc(sizeof(LNode));
 40     L->next=NULL;
 41     p=L;
 42     while(length--)
 43     {
 44         cin>>x;
 45         s=(LNode *)malloc(sizeof(LNode));
 46         s->data=http://www.mamicode.com/x;
 47         p->next=s;
 48         s->next=NULL;
 49         p=p->next;
 50     }
 51 }
 52 
 53 LNode* GetElem_order(LinkList &L,int n)//按序号查找节点
 54 {
 55     LNode *p=L;
 56     while(p!=NULL&&n>0)
 57     {
 58         p=p->next;
 59         n--;
 60     }
 61     return p;
 62 }
 63 LNode* GetElem_data(LinkList &L,ElemType e)//按值查找节点
 64 {
 65     LNode *p=L;
 66     while(p!=NULL&&p->data!=e)
 67         p=p->next;
 68     return p;
 69 }
 70 void InsertLNode(LinkList &L,ElemType elem,int pos)
 71 {
 72     LNode *p=L,*s;
 73     pos--;
 74     while(pos>0)
 75     {
 76         p=p->next;
 77         pos--;
 78     }
 79     s=(LNode *)malloc(sizeof(LNode));
 80     s->data=http://www.mamicode.com/elem;
 81     s->next=p->next;
 82     p->next=s;
 83 }
 84 void InsertLNode2(LinkList &L,ElemType elem,int pos)
 85 {
 86     LNode *p=L,*s;
 87     while(pos>0)
 88     {
 89         p=p->next;
 90         pos--;
 91     }
 92     s=(LNode *)malloc(sizeof(LNode));
 93     s->data=http://www.mamicode.com/elem;
 94     s->next=p->next;
 95     p->next=s;
 96     swap(p->data,s->data);
 97 }
 98 //书上介绍的一种方法，将s直接插入到第pos个节点的后面，再交换两个值。。
 99 void DeleteList_order(LinkList &L,int pos)//删除指定序号的节点
100 {
101     LNode *p=GetElem_order(L,pos-1);
102     LNode *q=p->next;
103     p->next=q->next;
104     free(q);
105 }
106 void DeleteList_data(LinkList &L,ElemType elem)//删除指定值的节点
107 {
108     LNode *p=GetElem_data(L,elem);
109     if(p->next!=NULL)//如果p不是最后一个节点，交换p和p下一个节点的值，删除p的下一个节点（逻辑上等同于删除p
110     {
111         LNode *q=p->next;
112         swap(q->data,p->data);
113         p->next=q->next;
114         free(q);
115     }
116     else free(p);//如果p是最后一个节点，那么可以直接删除p。
117 }
118 int showlength(LinkList L)//求表长。
119 {
120     int length=0;
121     while(L->next!=NULL)
122     {
123         length++;
124         L=L->next;
125     }
126     return length;
127 }
128 void showList(LinkList &L)
129 {
130     LNode *p=L->next;
131     while(p!=NULL)
132     {
133         cout<<p->data;
134         if(!(p->next==NULL))
135         {
136             cout<<‘ ‘;
137         }
138         p=p->next;
139     }
140     cout<<endl;
141 }
142 void showpoint(LNode *p)//展示特定节点的信息
143 {
144     if(p!=NULL)
145         cout<<p->data<<endl;
146     else cout<<"not found."<<endl;
147 }
148 
149 //注意：因为生成链表的时候第一个节点是跟在L的后面，即L本身是不存储信息的。
150 //故在按照链表的顺序输出元素值的时候，工作指针p一开始应该指向第一个节点（即L->next)
151 int main()
152 {
153     LNode *L1,*L2,*pos;
154     CreatList_head(L1,10);
155     CreatList_tail(L2,7);
156     showList(L1);
157     showList(L2);
158     pos=GetElem_order(L2,4);
159     showpoint(pos);
160     pos=GetElem_data(L2,99);
161     showpoint(pos);
162     InsertLNode(L1,10,6);
163     InsertLNode2(L2,100,5);
164     showList(L1);
165     showList(L2);
166 
167     DeleteList_order(L1,2);
168     DeleteList_data(L2,100);
169     cout<<"After delete some elem:"<<endl;
170     showList(L1);
171     showList(L2);
172     cout<<"Show the length of linklist:L1 is "<<showlength(L1)<<",while L2 is "<<showlength(L2)<<"."<<endl;
173 }