c++学习之单链表以及常用的操作

新学数据结构，上我写的代码。
  1 #include <iostream>
  2 #include <cstdlib>
  3 
  4 using namespace std;
  5 
  6 typedef int ElemType;
  7 
  8 struct Node
  9 {
 10     ElemType data;
 11     Node* next;
 12 };
 13 
 14 typedef Node* LinkList;
 15 
 16 //数据域的输入
 17 void input(ElemType* a)
 18 {
 19     cout<<"please enter the date value of the current node: ";
 20     cin >> *a;
 21 }
 22 
 23 //尾插法，我觉得更加符合我的习惯。这里用*L是因为需要将创建的头指针返回到主函数中，所以用指针
 24 void CreateLinkList(LinkList* L,int n,void input(ElemType*))
 25 {
 26     cout<<"this is the tail-insert-proach..."<<endl;
 27     LinkList s;
 28     *L = new Node;
 29     LinkList p = *L;
 30     (*L)->next = NULL;
 31     for(;n>0;n--)
 32     {
 33         s = new Node;
 34         input(&s->data);
 35         s->next = NULL;
 36         p->next = s;
 37         p = s;
 38     }
 39     s->next = NULL;
 40 }
 41 
 42 //链表的销毁
 43 void DestoryList(LinkList *L)
 44 {
 45     cout<<"we are going to delete the linklist..."<<endl;
 46     LinkList q,p = *L;
 47     while(p != NULL)
 48     {
 49         q = p->next;
 50         delete p;
 51         p = q;
 52     }
 53 
 54     *L = NULL;
 55     cout<<"we have destoryed the linklist..."<<endl;
 56 }
 57 
 58 void visit(ElemType* data)
 59 {
 60     cout<<"the data of current node is: "<<*data<<endl;
 61 }
 62 
 63 //链表的遍历，这里不需要将变化返回到主函数中，所以不需要用指针。
 64 void ListTraverse(LinkList L,void visit(ElemType*))
 65 {
 66     LinkList p = L;
 67     p = p->next;
 68     while(p != NULL)
 69     {
 70         visit(&p->data);
 71         p = p->next;
 72     }
 73 }
 74 
 75 
 76 //比较函数
 77 bool compare(ElemType* a,ElemType* b)
 78 {
 79     if(*a == *b)
 80         return true;
 81     else
 82         return false;
 83 }
 84 
 85 //在链表中查找元素e
 86 void LocateElem(LinkList L,ElemType e,bool compare(ElemType*,ElemType*))
 87 {
 88     int i = 0; //记录结点的位置
 89     LinkList p = L;
 90     p = p->next;
 91     i++;
 92     while(p!=NULL)
 93     {
 94         if(compare(&p->data,&e))
 95         {
 96             cout<<"we have found the element in "<<i<<" node"<<endl;
 97         }
 98         p = p->next;
 99         i++;
100     }
101 }
102 
103 //在链表中插入一个数字
104 int ListInsert(LinkList *L,int i,ElemType e)
105 {
106     LinkList p = *L;
107     while(p!=NULL && i>1) //找到第i-1个结点
108     {
109         p = p->next;
110         i--;
111     }
112     if(p==NULL || i<1) return 0; //判断结点存在
113     LinkList s = new Node;  //将结点插入
114     s->data = e;
115     s->next = p->next;
116     p->next = s;
117     return 1;
118 }
119 
120 int ListDelete(LinkList *L,int i,ElemType *ep)
121 {
122     LinkList p = *L;
123     while(p!=NULL && i>1) //找到第i-1个结点
124     {
125         p = p->next;
126         i--;
127     }
128     if(p==NULL || i<1) return 0;
129     LinkList q = p->next;
130     p->next = q->next;
131     *ep = q->data;
132     delete q;
133     return 1;
134 }
135 
136 int main()
137 {
138     LinkList L; //头指针，指向创建的头结点。头结点的data为空，尾结点的next为NULL
139     int n,ep;
140     cout<<"please enter the number of needed nodes(except the head node)..."<<endl;
141     cin>>n;
142     CreateLinkList(&L,n,input);
143     LocateElem(L,3,compare);
144     ListInsert(&L,2,100);
145     ListDelete(&L,2,&ep);
146     cout<<"the delete data value is "<<ep<<endl;
147     ListTraverse(L,visit);
148     DestoryList(&L);
149     return 0;
150 }
下面是程序运行的结果：