单链表

 特别注意：main（）的第二行代码

LNode* L=NULL, * p;                      

这里需要是LNode* L=NULL,不能是LNode* L。因为会报错：使用了可能未初始化的本地指针变量“L”!在vs中会报错，在dev中并不会。

但是LNode *p就不会报错？？？

                                                           

#include <iostream> using namespace std;

typedef int ElemType; typedef int Status;

typedef struct LNode {     ElemType data;              //结点的数据域     struct LNode* next;      //结点的指针域 }LNode , *LinkList ;           //LinkList为指向结构体LNode的指针类型

//1.初始化 Status InitList(LinkList& L) {     L = new LNode;                  //生成新结点作为头结点，用头指针L指向头结点     L->next = NULL;      //头结点的指针域置空,L是结构体指针变量，所以要是L->next     return 1; }

//2.后插法创建单链表 void CreateList_R(LinkList& L, int n) {     LNode* p;     L = new LNode;             //先建立一个带头结点的空链表     L->next = NULL;     LNode* r = L;                //让尾指针指向头节点     cout << "请输入 " << n << " 个数:\n";          //这样也可以直接换行     for (int i = 0; i < n; i++)     {         p = new LNode;         cin >> p->data;         p->next = NULL;         r->next = p;         r = p;                           //r指向新的尾结点     } }

//3.取值（取第几个值）,用e返回             或者是直接return p->data不通过e Status GetElem(LinkList L, int i, ElemType &e) {     LNode* p;     p = L->next;   int j = 1;   //p指向首元节点     while (p && j<i )            //p不为NULL说明链表没结束，j<i 说明没到第i个值     {         p = p->next;  j++;     }     if (!p || j > i) return -1;   //i<0或者 i>n i值不合法     e = p->data;     return 1; }

//4.查找  查找成功返回节点的地址值，查找失败返回NULL LNode* SearchElem_a(LinkList L, ElemType e) {     LNode* p = L->next;      while (p)     {         if (p->data == e)             return p;         p = p->next;     }     return NULL; }

int  SearchElem_b(LinkList L,ElemType e)    //返回是第几个元素 {                 //在带头结点的单链表L中查找值为e的元素     int j = 1;     LNode *p;     p=L->next;     while (p && p->data != e)            //当p为NULL的时候就返回p     {         p = p->next;  j++;     }//寻找满足条件的结点     return j;                                //返回L中的值为e的数据元素的位置，查找失败返回NULL }

//5.插入 Status ListInsert(LinkList& L, int i, ElemType e) {     int j = 0; LNode* p = L;     while (p && j < i - 1)     {         p = p->next; j++;     }     if (!p || j > i - 1)       //i>n+1或者i<1，返回-1     {         return -1;     }     LNode* s;   //s在new分配空间之前是一个野指针     s = new LNode;          //生成新结点s     s->data = e;     s->next = p->next;     p->next = s;     return 1; }

//6.删除 Status ListDelete(LinkList& L, int i, ElemType &e) {     LNode* p = L; int j = 0;     while ((p->next) && j < i-1)       //将指针p定位到被删除节点的上一个节点     {         p = p->next; j++;     }     if ((!p->next) || j > i - 1) return -1;     LNode* q;     q = p->next;     p->next = q->next;     e = q->data;     delete q;     return 1;

}

int main() {     int res, a, b, choose;     LNode* L=NULL, * p;                       //特别注意，这里需要是LNode* L=NULL,不能是LNode* L。                                                                    //会报错      使用了可能未初始化的本地指针变量“L”         cout << "1. 建立链表\n";     cout << "2. 输入数据\n";     cout << "3. 按位置查找\n";     cout << "4. 按值查找\n";     cout << "5. 链表的插入\n";     cout << "6. 链表的删除\n";     cout << "7. 输出数据\n";     cout << "0. 退出\n\n";

    choose = -1;     while (choose != 0)     {         cout << "请选择:";         cin >> choose;         switch (choose)         {         case 1:                    //建立一个单链表             if(InitList(L))                cout << "成功建立链表!\n\n";             break;         case 2:                    //使用后插法创建单链表             CreateList_R(L, 10);             cout << "成功创建链表!\n\n";             break;         case 3:                    //单链表的按序号查找             cout << "请输入一个位置用来查找:";             cin >> a;             if (GetElem(L, a, res))                 cout << "查找成功!第" << a << "个数是：" << res << "\n\n";             else                 cout << "查找失败\n\n";             break;         case 4:                    //单链表的按值查找             cout << "请输入一个数值用来查找:";             cin >> b;             int flag;             flag=SearchElem_b(L, b);             if (flag)                 cout << "查找成功!"<< b<<"是第"<<flag<<"个数\n\n";             else                 cout << "查找失败! " << b << " 没有找到\n\n";             break;         case 5:                    //单链表的插入             cout << "请输入两个数分别代表插入的位置和数值:";             cin >> a >> b;             if (ListInsert(L, a, b))                 cout << "成功将" << b << "插在第" << a << "个位置\n\n";             else                 cout << "插入失败!\n\n";             break;         case 6:                    //单链表的删除             cout << "请输入一个位置用来删除:";             cin >> a;             if (ListDelete(L, a, res))                 cout << "删除成功!被删除的数是：" << res << "\n\n";             else                 cout << "删除失败!\n\n";             break;         case 7:                    //单链表的输出             cout << "现在链表里的数分别是:\n";             p = L->next;             while (p)             {                 cout << p->data << " ";                 p = p->next;             }             cout << endl;             break;         }     }     return 0; }